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.
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.
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);
}