Lab 6 Uthread: switching between threads

Design the context switch mechanism for a user-level threading system

Task

In this exercise you will design the context switch mechanism for a user-level threading system, and then implement it.

Your job is to come up with a plan to create threads and save/restore registers to switch between threads, and implement that plan.

Lab: user-level threads and alarm

Expected Result

~/classes/6828/xv6$ **make qemu**
…
$ **uthread**
thread_a started
thread_b started
thread_c started
thread_c 0
thread_a 0
thread_b 0
thread_c 1
thread_a 1
thread_b 1
…
thread_c 99
thread_a 99
thread_b 99
thread_c: exit after 100
thread_a: exit after 100
thread_b: exit after 100
thread_schedule: no runnable threads

Hints

complete thread_create to create a properly initialized thread so that when the scheduler switches to that thread for the first time decide where to save/restore registers. You can add fields to struct thread into which to save registers.

Solution

Save registers info in thread

// Saved registers for kernel context switches.
struct context {
  uint64 ra;
  uint64 sp;

  *// callee-saved*
  uint64 s0;
  uint64 s1;
  uint64 s2;
  uint64 s3;
  uint64 s4;
  uint64 s5;
  uint64 s6;
  uint64 s7;
  uint64 s8;
  uint64 s9;
  uint64 s10;
  uint64 s11;
  *// uint64 fs0;*
  *// uint64 fs1;*
  *// uint64 fs2;*
  *// uint64 fs3;*
};

Add context to thread.

struct thread {
  char       stack[STACK_SIZE]; */* the thread's stack */*
  int        state;             */* FREE, RUNNING, RUNNABLE */*
  struct context context;      *// swtch() here to run process*
};

Setup jump function and stack in thread creation

void 
thread_create(void (*func)())
{
  struct thread *t;

  for (t = all_thread; t < all_thread + MAX_THREAD; t++) {
    if (t->state == FREE) break;
  }
  t->state = RUNNABLE;
  // YOUR CODE HERE
  memset(&t->context, 0, sizeof t->context);
  t->context.ra = (uint64)func;

  t->context.sp = (uint64)(t->stack + STACK_SIZE); 
}

Note:

• Set up ra return address register to point to the thread function, so switch thread will jump to the function.

• In the standard RISC-V calling convention, the stack grows downward and the stack pointer is always kept 16-byte aligned.

• Set stack pointer to stack top.

Implement context switch

    .text

/* Switch from current_thread to next thread_thread, and make
 * next_thread the current_thread.  Use t0 as a temporary register,
 * which should be caller saved. */

/*
Caller-saved registers (AKA volatile registers, or call-clobbered) 
are used to hold temporary quantities that need not be preserved across calls.

Callee-saved registers (AKA non-volatile registers, or call-preserved) are 
used to hold long-lived values that should be preserved across calls.
*/

    .globl thread_switch
thread_switch:
    /* YOUR CODE HERE */
    sd ra, 0(a0)
    sd sp, 8(a0)
    sd s0, 16(a0)
    sd s1, 24(a0)
    sd s2, 32(a0)
    sd s3, 40(a0)
    sd s4, 48(a0)
    sd s5, 56(a0)
    sd s6, 64(a0)
    sd s7, 72(a0)
    sd s8, 80(a0)
    sd s9, 88(a0)
    sd s10, 96(a0)
    sd s11, 104(a0)

    ld ra, 0(a1)
    ld sp, 8(a1)
    ld s0, 16(a1)
    ld s1, 24(a1)
    ld s2, 32(a1)
    ld s3, 40(a1)
    ld s4, 48(a1)
    ld s5, 56(a1)
    ld s6, 64(a1)
    ld s7, 72(a1)
    ld s8, 80(a1)
    ld s9, 88(a1)
    ld s10, 96(a1)
    ld s11, 104(a1)

    ret    /* return to ra */

We save ra, sp, and all callee saved registers. This assembly function is called be thread scheduler, to switch from current thread to next runnable one. This function saves registers info in thread->context, and load registers from new thread’s context, then jump executing the new thread.

Complete thread scheduler

Define struct and vars

struct thread {
  char       stack[STACK_SIZE]; /* the thread's stack */
  int        state;             /* FREE, RUNNING, RUNNABLE */
  struct context context;      // swtch() here to run process
};
struct thread all_thread[MAX_THREAD];
struct thread *current_thread;
extern void thread_switch(struct context*, struct context*);

Find next runnable thread

  struct thread *t, *next_thread;
  next_thread = 0;
  t = current_thread + 1;
  for(int i = 0; i < MAX_THREAD; i++){
    if(t >= all_thread + MAX_THREAD)
      t = all_thread;
    if(t->state == RUNNABLE) {
      next_thread = t;
      break;
    }
    t = t + 1;
  }

Try to find next one, if reaches the end then start from beginning. If none of them is available, current_thread is unchanged and resume.

Switch thread

if (current_thread != next_thread) {
    next_thread->state = RUNNING;
    t = current_thread;
    current_thread = next_thread;
    // Invoke thread_switch to switch from t to next_thread:
    thread_switch(&t->context, &current_thread->context);
  }

Ref: Full Uthread Package

#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"

*/* Possible states of a thread: */*
#define FREE        0x0
#define RUNNING     0x1
#define RUNNABLE    0x2

#define STACK_SIZE  8192
#define MAX_THREAD  4

*// Saved registers for kernel context switches.*
struct context {
  uint64 ra;
  uint64 sp;

  *// callee-saved*
  uint64 s0;
  uint64 s1;
  uint64 s2;
  uint64 s3;
  uint64 s4;
  uint64 s5;
  uint64 s6;
  uint64 s7;
  uint64 s8;
  uint64 s9;
  uint64 s10;
  uint64 s11;
};

struct thread {
  char       stack[STACK_SIZE]; */* the thread's stack */*
  int        state;             */* FREE, RUNNING, RUNNABLE */*
  struct context context;      *// swtch() here to run process*
};
struct thread all_thread[MAX_THREAD];
struct thread *current_thread;
extern void thread_switch(struct context*, struct context*);

void 
thread_init(void)
{
  *// main() is thread 0, which will make the first invocation to*
  *// thread_schedule().  it needs a stack so that the first thread_switch() can*
  *// save thread 0's state.  thread_schedule() won't run the main thread ever*
  *// again, because its state is set to RUNNING, and thread_schedule() selects*
  *// a RUNNABLE thread.*
  current_thread = &all_thread[0];
  current_thread->state = RUNNING;
}

void 
thread_schedule(void)
{
  struct thread *t, *next_thread;

  */* Find another runnable thread. */*
  next_thread = 0;
  t = current_thread + 1;
  for(int i = 0; i < MAX_THREAD; i++){
    if(t >= all_thread + MAX_THREAD)
      t = all_thread;
    if(t->state == RUNNABLE) {
      next_thread = t;
      break;
    }
    t = t + 1;
  }

  if (next_thread == 0) {
    printf("thread_schedule: no runnable threads\n");
    exit(-1);
  }

  if (current_thread != next_thread) {         */* switch threads?  */*
    next_thread->state = RUNNING;
    t = current_thread;
    current_thread = next_thread;
    */* YOUR CODE HERE*
** Invoke thread_switch to switch from t to next_thread:*
**/*
    thread_switch(&t->context, &current_thread->context);
  } else
    next_thread = 0;
}

void 
thread_create(void (*func)())
{
  struct thread *t;

  for (t = all_thread; t < all_thread + MAX_THREAD; t++) {
    if (t->state == FREE) break;
  }
  t->state = RUNNABLE;
  *// YOUR CODE HERE*
  memset(&t->context, 0, sizeof t->context);
  t->context.ra = (uint64)func;
  */**
*In the standard RISC-V calling convention,*
*the stack grows downward and the stack pointer is*
*always kept 16-byte aligned.*
**/*
  t->context.sp = (uint64)(t->stack + STACK_SIZE); *// how does stack grow?*
}

void 
thread_yield(void)
{
  current_thread->state = RUNNABLE;
  thread_schedule();
}

volatile int a_started, b_started, c_started;
volatile int a_n, b_n, c_n;

void 
thread_a(void)
{
  int i;
  printf("thread_a started\n");
  a_started = 1;
  while(b_started == 0 || c_started == 0)
    thread_yield();

  for (i = 0; i < 100; i++) {
    printf("thread_a %d\n", i);
    a_n += 1;
    thread_yield();
  }
  printf("thread_a: exit after %d\n", a_n);

  current_thread->state = FREE;
  thread_schedule();
}

void 
thread_b(void)
{
  int i;
  printf("thread_b started\n");
  b_started = 1;
  while(a_started == 0 || c_started == 0)
    thread_yield();

  for (i = 0; i < 100; i++) {
    printf("thread_b %d\n", i);
    b_n += 1;
    thread_yield();
  }
  printf("thread_b: exit after %d\n”, b_n);

  current_thread->state = FREE;
  thread_schedule();
}

void 
thread_c(void)
{
  int i;
  printf(“thread_c started\n”);
  c_started = 1;
  while(a_started == 0 || b_started == 0)
    thread_yield();

  for (i = 0; i < 100; i++) {
    printf(“thread_c %d\n”, i);
    c_n += 1;
    thread_yield();
  }
  printf("thread_c: exit after %d\n", c_n);

  current_thread->state = FREE;
  thread_schedule();
}

int 
main(int *argc*, char **argv*[]) 
{
  a_started = b_started = c_started = 0;
  a_n = b_n = c_n = 0;
  thread_init();
  thread_create(thread_a);
  thread_create(thread_b);
  thread_create(thread_c);
  thread_schedule();
  exit(0);
}

心得

过去五年一直不理解的coroutine现在顿悟了，x86的繁琐和陈旧被risc-v的精简直接击垮。纤程的本质就是context switch，将储存器存入stack, 将另一个纤程的储存器从它的stack读出，将program counter设置好，这，就是fiber.