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
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, ¤t_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, ¤t_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.
Last updated
Was this helpful?