多线程是通过多路复用实现的，给每个进程独占CPU的幻觉。多路复用就是从一个进程切换到另外一个进程，切换时机是以下两种：
- 进程等待IO、子进程结束、sleep时会通过sleep和wakeup机制来切换。
- 时间片轮转。
一、Uthread: switching between threads
1 目的
用户态线程，相当于一个线程在多个执行流上运行，需要在不同任务上切换，切换时需要保存callee-saved寄存器到context中，而caller-saved寄存器是存放在栈帧。
2 问题分析
- 首先创建用户线程，需要在线程列表上寻找空槽位保存待执行的函数指针；
- 线程调度，在线程列表上寻找一个就绪态的线程，然后调用thread_switch来切换。thread_switch是一段汇编代码，会读取寄存器并保存在context中，然后恢复寄存器内容；
- yield会将当前线程修改为就绪态并schedule。
3 代码实现
3.1 数据结构
首先定义context来保存寄存器；再定义线程数据结构，每个线程包含一个context用于保存上下文，还有一个stack放置到sp上用于该线程的栈。
代码语言：c复制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;
};
struct thread all_thread[MAX_THREAD];
struct thread *current_thread;
extern void thread_switch(struct context* old, struct context* new);
3.2 初始化
thread 0就是main线程，这个thread对象是用来保存main切换时的上下文的。进程刚开始执行一定是main函数，此时还没有用户线程的概念，初始化并schedule后从会切换到线程上，此时就会将main函数的信息保存到all_thread[0].context上。每个线程执行完后主动调用schedule切换到其他线程上，否则就会直接结束，等待所有的用户线程都执行完就还剩一个就绪态的all_thread[0]，在main函数上结束。
代码语言：c复制
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;
}
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);
}3.3 创建线程
创建线程需要遍历线程列表寻找空槽位，然后修改状态，最重要的是设置ra和sp。之所以是ra(返回地址)而不是pc，因为当时还在thread_switch，返回后就是目标线程执行流。
代码语言：c复制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->context.ra=(uint64)func;
//sp设置为栈最高地址
t->context.sp=(uint64)&t->stack (STACK_SIZE-1);
}3.4 线程调度
从当前线程后一个开始遍历，查找就绪态线程。如果新选择的线程不是当前线程，就调用thread_switch来切换。
代码语言：c复制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 threadsn");
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(&t->context,¤t_thread->context);
} else
next_thread = 0;
}thread_switch是一段汇编代码，会读取寄存器切换context，参照内核的swtch.S，如下：
代码语言：c复制 .text
/*
void thread_switch(struct context *old, struct context *new);
* save the old thread's registers,
* restore the new thread's registers.
*/
.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 */3.5 yield
代码语言：c复制void
thread_yield(void)
{
current_thread->state = RUNNABLE;
thread_schedule();
}二、Using Threads
1 目的
通过pthread创建线程并发读写哈希表，为了性能考虑，必须使用分段锁，在put和get上加锁来保护。
为了提供效率，不再采用全局锁，而是分段锁，需要了解pthread_mutex_t，本实验目的注重pthread的使用。
2 代码实现
2.1 数据结构
添加分段锁mutextable来支持并发读写。
代码语言：c复制#define NBUCKET 5
#define NKEYS 100000
struct entry {
int key;
int value;
struct entry *next;
};
struct entry *table[NBUCKET];
pthread_mutex_t mutextable[NBUCKET];
int keys[NKEYS];
int nthread = 1;2.2 主要逻辑
代码语言：c复制//初始化锁
for (size_t i = 0; i < NBUCKET; i ){
pthread_mutex_init(&mutextable[i],NULL);
}
//添加分段锁，避免missing
static struct entry*
get(int key)
{
int i = key % NBUCKET;
pthread_mutex_lock(&mutextable[i]);
struct entry *e = 0;
for (e = table[i]; e != 0; e = e->next) {
if (e->key == key) break;
}
pthread_mutex_unlock(&mutextable[i]);
return e;
}
static
void put(int key, int value)
{
int i = key % NBUCKET;
pthread_mutex_lock(&mutextable[i]);
// 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(&mutextable[i]);
}
三、Barrier
栅栏，每个线程在某个点等待其他线程，调用barrier。如果bstate.nthread==nthread则表示一组线程已经到齐，唤醒所有线程继续往下执行，否则就等待。
static int nthread = 1; //这组线程数量
static int round = 0;
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;
static void
barrier_init(void)
{
assert(pthread_mutex_init(&bstate.barrier_mutex, NULL) == 0);
assert(pthread_cond_init(&bstate.barrier_cond, NULL) == 0);
bstate.nthread = 0;
}
static void
barrier()
{
pthread_mutex_lock(&bstate.barrier_mutex);
bstate.nthread ;
if(bstate.nthread==nthread){
bstate.round ;//一轮结束
bstate.nthread=0;
pthread_cond_broadcast(&bstate.barrier_cond);
}else{
pthread_cond_wait(&bstate.barrier_cond,&bstate.barrier_mutex);
}
pthread_mutex_unlock(&bstate.barrier_mutex);
}四、测试结果
测试结果
