课程地址：https://pdos.csail.mit.edu/6.S081/2020/schedule.html
Lab 地址：https://pdos.csail.mit.edu/6.S081/2020/labs/thread.html
我的代码地址：https://github.com/Amroning/MIT6.S081/tree/thread
xv6手册：https://pdos.csail.mit.edu/6.S081/2020/xv6/book-riscv-rev1.pdf
相关翻译：https://xv6.dgs.zone/labs/requirements/lab7.html
参考博客：https://blog.miigon.net/posts/s081-lab7-multithreading/

学习笔记记录，如有错误恳请各位大佬指正

Lab7: Multithreading

实现⽤户级线程；优化并发程序，使用线程提速程序；实现同步屏障

线程具有状态，可以随时保存线程的状态并暂停线程的运行，并在之后通过恢复状态来恢复线程的运行。线程的状态包含了三个部分：

• 程序计数器（Program Counter），它表示当前线程执行指令的位置
• 保存变量的寄存器
• 程序的Stack。每个线程都有属于自己的Stack，Stack记录了函数调用的记录，并反映了当前线程的执行点

线程会运行在所有可用的CPU核上，每个CPU核会在多个线程之间切换

Uthread: switching between threads (moderate)

您的工作是提出一个创建线程和保存/恢复寄存器以在线程之间切换的计划，并实现该计划。完成后，make grade应该表明您的解决方案通过了uthread测试。

​ 该实验需要完善user/uthread.c中的thread_create()和thread_schedule()，以及user/uthread_switch.S中的thread_switch，实现创建线程的初始化工作，以及实现线程调度。最好先把uthread.c代码读一遍

context 结构体用于进程间/线程间的上下文切换，切换到不同的进程/线程时，保存进程、线程的最小上下文信息。context 只需要保存 callee-saved 寄存器，sp 和 ra，因为这些寄存器在函数调用之间需要保持一致。当发生进程间/线程切换时，调用者在调用切换函数前已经保存了 caller-saved 寄存器，因此只需保存这些 callee-saved 、ra和sp寄存器即可

和下面的代码结合来看

​ 内核已经有scheduler() 和 swtch() 的功能，可以直接参考来写。uthread_switch.S中实现上下文切换的功能，保存当前线程寄存器，读取新线程的的寄存器。可以看着swtch.S来写：

# uthread_switch.S
	.text

	/*
         * save the old thread's registers,
         * restore the new thread's registers.
         */

	.globl thread_switch
thread_switch:
	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 */

​ 和进程的context结构体一样，给线程也写一个context结构体：

// uthread.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;
};

​ 在线程结构体中加入context结构体：

// uthread.c
struct thread {
    char       stack[STACK_SIZE]; /* the thread's stack */
    int        state;             /* FREE, RUNNING, RUNNABLE */
    struct context context;       // 在线程结构体中添加 context 结构体
};

​ 这样就可以在调度函数thread_schedule中加入线程切换函数thread_switch，在上面thread_switch函数的声明中修改传入参数：

// uthread.c
extern void thread_switch(struct context* old, struct context* new);

...
    
void 
thread_schedule(void)
{
  ......

  if (current_thread != next_thread) {         /* switch threads?  */
    next_thread->state = RUNNING;
    t = current_thread;
    current_thread = next_thread;
    thread_switch(&t->context, &next_thread->context);		//加上
  } else
    next_thread = 0;
}

​ 切换线程的工作就完成了。再来是创建线程时，需要对线程初始化。线程创建函数thread_create(void (*func)())，线程创建后，就要执行函数func：

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;

  // 返回地址,thread_switch线程切换执行完后返回到ra，设置成线程函数func，就可以切换后执行func
  t->context.ra = (uint64)func;

  // 栈指针，将线程的栈指针指向其独立的栈，栈的生长是从高地址到低地址，所以要将 sp 设置为指向 stack 的最高地址
  t->context.sp = (uint64)&t->stack + (STACK_SIZE - 1);
}

​ 到此可以启动xv6，执行uthread验证是否完成实验。

Using threads (moderate)

完整要求请在本帖顶部链接查看

​ 示例中，两个线程插入丢失了很多原本应该插入的键值，这是因为源代码notxv6/ph.c中，不同的线程可以同时执行put和get。假如线程1执行put函数，发现key1不存在，要执行insert在一个散列桶插值的时候，切换到了线程2，线程2也是要插入同一个散列桶的同一个位置，完成了key2的插入，切换回了线程1，线程1继续执行insert，导致key2被覆盖

​ 因此要在并发写共享数据的地方加锁，首先是声明一个线程锁：

// ph.c
pthread_mutex_t lock;

main函数中初始化锁：

// ph.c
int
main(int argc, char *argv[])
{
  pthread_t *tha;
  void *value;
  double t1, t0;
  pthread_mutex_init(&lock, NULL);
  ......

在put函数执行的时候加上锁：

static 
void put(int key, int value)
{
  pthread_mutex_lock(&lock);
    
  int i = key % NBUCKET;

  // 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(&lock);
}

put相当于写操作，get相当于读操作。在多线程环境中，读写操作一般都是并发进行的，在读操作中也是会发生写操作的，为了确保数据一致性和线程安全，读操作也需要加锁。在这个实验中，main函数里，get操作是在put操作结束后才执行的，即可以保证，get执行的时候不会有线程执行put操作共享数据，所以这里不用给get加锁。但为了保持良好的线程编程思想，最好还是加上锁。

这个时候可以通过 ph_safe测试：

$ ./ph 1
100000 puts, 4.855 seconds, 20597 puts/second
0: 0 keys missing
100000 gets, 4.847 seconds, 20629 gets/second
$ ./ph 2
100000 puts, 5.685 seconds, 17591 puts/second
1: 0 keys missing
0: 0 keys missing
200000 gets, 11.184 seconds, 17882 gets/second

​ 从上面的数据也可以看到，多线程已经不会丢失键了，保证了线程安全。但是也可以看到，两个线程的性能比单线的还要低，没有实现多线程提升性能的功能。因为上面的代码中给整个put操作加上了锁，每一个时刻只能有一个线程执行put操作，这和单线程就没什么区别了，加上添加了锁操作，上锁、释放锁、锁竞争都是有开销的，所以会比单线程性能更低

​ 多线程提升效率常用的一个做法是降低锁的粒度，减少加锁的范围。观察代码可以知道，不同散列桶的put操作不会互相影响，同一时刻操作不同的散列桶不会造成线程安全问题，所以在这里只要给散列桶加锁，保证不同的线程不会同时操作同一个散列桶就可以了，这样就降低了锁的粒度。

​ 修改代码，把线程锁改成散列桶数量大小的锁类型的数组，即给每一个散列桶声明一把锁

// ph.c
pthread_mutex_t lock[NBUCKET];

​ 初始化锁：

int
main(int argc, char *argv[])
{
  pthread_t *tha;
  void *value;
  double t1, t0;

  if (argc < 2) {
    fprintf(stderr, "Usage: %s nthreads\n", argv[0]);
    exit(-1);
  }
  nthread = atoi(argv[1]);
  tha = malloc(sizeof(pthread_t) * nthread);
  srandom(0);
  assert(NKEYS % nthread == 0);
  for (int i = 0; i < NKEYS; i++) {
    keys[i] = random();
  }

  for (int i = 0;i < NBUCKET;++i)				//在执行put前初始化锁
      pthread_mutex_init(&lock[i], NULL);
    
  ......

​ 在执行put操作的时候，针对散列桶上锁：

static 
void put(int key, int value)
{
  int i = key % NBUCKET;

  pthread_mutex_lock(&lock[i]);

  ......

  pthread_mutex_unlock(&lock[i]);
}

​ 重新编译执行测试：

$ ./ph 1
100000 puts, 4.944 seconds, 20227 puts/second
0: 0 keys missing
100000 gets, 4.870 seconds, 20532 gets/second
$ ./ph 2
100000 puts, 2.832 seconds, 35310 puts/second
1: 0 keys missing
0: 0 keys missing
200000 gets, 4.529 seconds, 44156 gets/second
$ ./ph 4
100000 puts, 2.018 seconds, 49552 puts/second
0: 0 keys missing
1: 0 keys missing
2: 0 keys missing
3: 0 keys missing
400000 gets, 4.684 seconds, 85399 gets/second

​ 从数据可以看出，不仅保证了线程安全，多线程也有了性能上的提升，可以通过ph_safe和ph_fast测试

Barrier(moderate)

完整要求请在本帖顶部链接查看

​ 线程调用barrier之后，bstate中的线程数nthread应该+1。然后判断当前进入屏障的线程数是否达到全局的nthread，如果未达到，就调用pthread_cond_wait，让当前线程睡眠，等待线程数达到要求。如果达到了，需要做的事有：bstate中的轮数round+1；清空bstate的线程数；唤醒其他正在睡眠的线程。

​ 需要考虑的是上锁的位置。可能出现的情况：线程1进入屏障后，bstate中的线程数nthread+1，但未达到全局nthread，线程1正要睡眠，此时线程2进入屏障，达到了全局nthread，调用pthread_cond_wait唤醒所有线程，之后线程1才进入睡眠，导致线程1没被唤醒。因此在bstate中的线程数nthread+1，到调用pthread_cond_wait进入睡眠这个过程应该上锁。调用pthread_cond_wait的时候回释放当前的锁，避免其他线程拿不到锁

​ 据此可以写出代码：

// notxv6/barrier.c
static void 
barrier()
{
  // YOUR CODE HERE
  //
  // Block until all threads have called barrier() and
  // then increment bstate.round.
  //
    pthread_mutex_lock(&bstate.barrier_mutex);
    if (++bstate.nthread < nthread)
        pthread_cond_wait(&bstate.barrier_cond, &bstate.barrier_mutex);
    else {
        bstate.nthread = 0;
        bstate.round++;
        pthread_cond_broadcast(&bstate.barrier_cond);
    }
    pthread_mutex_unlock(&bstate.barrier_mutex);
}

此时可以验证实验是否通过