Uthread: switching between threads
为用户态的线程系统设计并实现上下文切换机制，实现创建线程、在线程切换时保存和恢复寄存器的功能。 uthread.c中对线程的定义如下：
struct thread {
char stack[STACK_SIZE]; /* the thread's stack */
int state; /* FREE, RUNNING, RUNNABLE */
struct context ctx;
};
其中context用于在线程切换时保存和恢复线程上下文，由callee-save寄存器组成，context定义为:
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;
};
对应地，线程切换时保存和恢复线程上下文对寄存器的操作也就和进程切换时的swtch相同：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
.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 */
在线程创建时，thread_create的参数为在线程中要执行的函数，在所有线程中找到一个空闲状态的线程，将其状态设置为RUNNABLE，并设置sp寄存器为栈的最高地址，ra寄存器为函数指针，这样在thread_scheduler调用thread_swtch返回时，将从返回地址处开始执行，并从栈的高地址向下增长。代码如下：
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
t->ctx.sp = (uint64)&t->stack + (STACK_SIZE - 1);
t->ctx.ra = (uint64)func;
}
在thread_schedule中，在从当前的所有线程中选择出合适执行的线程后，调用thread_swtch函数，首先将当前的callee-save寄存器现场保存到当前线程的context中以备下次被调度时恢复，然后从选择出的将要执行的线程的context中读取寄存器的值并恢复，代码如下：
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(??, ??);
*/
thread_switch((uint64)&t->ctx, (uint64)&next_thread->ctx);
} else
next_thread = 0;
}
Using threads
主要是解决多个线程并发访问哈希表时引起的数据竞争问题，通过给get和put两种操作访问共享数据资源，也就是哈希表时加锁，来避免数据竞争引起数据丢失，由于目前并不需要考虑性能，因此直接在put和get两部分的开始和末尾处加锁和解锁，代码如下：
static
void put(int key, int value)
{
int i = key % NBUCKET;
pthread_mutex_lock(&put_lock);
// is the key already present?
struct entry *e = 0;
for (e = table[i]; e != 0; e = e->next) {
if (e->key == key)
break;
}
if(e){
// update the existing key.
e->value = value;
} else {
// the new is new.
insert(key, value, &table[i], table[i]);
}
pthread_mutex_unlock(&put_lock);
}
static struct entry*
get(int key)
{
int i = key % NBUCKET;
pthread_mutex_lock(&get_lock);
struct entry *e = 0;
for (e = table[i]; e != 0; e = e->next) {
if (e->key == key) break;
}
pthread_mutex_unlock(&get_lock);
return e;
}
在使用锁前，首先需要对锁进行初始化：
pthread_mutex_init(&put_lock, NULL);
pthread_mutex_init(&get_lock, NULL);
Barrier
实现一个barrier，每个线程在barrier处等待，直到所有的线程都已经运行到了这一点。barrier通过pthread库提供的条件变量来实现。
pthread提供了两个API，pthread_cond_wait(&cond, &mutex) 使线程在条件变量cond上等待，并释放mutex锁。pthread_cond_broadcast(&cond) 用于唤醒所有在条件变量cond上等待的线程。
在barrier.c中，barrier结构体定义为：
struct barrier {
pthread_mutex_t barrier_mutex;
pthread_cond_t barrier_cond;
int nthread; // Number of threads that have reached this round of the barrier
int round; // Barrier round
} bstate;
其中barrier_mutex作为互斥锁，用于保护bstate中的临界资源，包括nthread和round，barrier_cond作为pthread_cond_wait和pthread_cond_broadcast的参数，用于使线程等待或唤醒线程。nthread表示当前轮次到达barrier的线程数，round表示当前barrier所在的轮次。
当每个线程执行到barrier函数时，首先加锁，然后使nthread+1并判断当前是否所有线程都到达barrier处，如果仍有线程未到达barrier，释放锁并使自己休眠，否则使轮次+1，调用broadcast唤醒所有线程，并重置bstate.nthread，代码如下：
static void
barrier()
{
// YOUR CODE HERE
//
// Block until all threads have called barrier() and
// then increment bstate.round.
//
pthread_mutex_lock(&bstate.barrier_mutex);
bstate.nthread++;
if (bstate.nthread >= nthread) {
bstate.round++;
pthread_cond_broadcast(&bstate.barrier_cond);
bstate.nthread = 0;
} else {
pthread_cond_wait(&bstate.barrier_cond, &bstate.barrier_mutex);
}
pthread_mutex_unlock(&bstate.barrier_mutex);
}
执行测试, 顺利通过：
1
2
3
4
5
6
7
8
❯ ./barrier 2
OK; passed
❯ ./barrier 3
OK; passed
❯ ./barrier 4
OK; passed