MIT 6.S081 Lab 6: Multithreading

7 Nov 2022

The dignity and glory of the person liesnot in sophistication but in honesty.

6.S081课程的第六个Lab，为 xv6 添加用户级线程与使用 pthread 库实现线程安全的hash table 与 barrier。

Uthread: switching between threads

为一个用户级线程系统设计上下文切换机制并实现。

和xv6内核级线程切换不一样的是，这个用户级线程没有常驻CPU的 scheduler 线程负责调度。但整体上仍然可以参考内核线程切换。

这里切换线程上下文不需要保存 caller-saved register，因为在调用 thread_schedule 函数时，已经有了保存。这里只用考虑 callee-saved register 保证切换时不丢失寄存器信息。

struct thread {
  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;

  char       stack[STACK_SIZE]; /* the thread's stack */
  int        state;             /* FREE, RUNNING, RUNNABLE */
};

我们的目标是确保当 thread_schedule() 第一次运行一个给定的线程时，该线程在自己的堆栈中执行传递给 thread_create()的函数。这可以通过寄存器 ra 保存函数地址(指令地址)，sp 保存线程栈地址(数据地址)实现。这里要小心的是，xv6基于小端系统，栈增长向下(从大到小)。所以 sp 指向栈区的高地址。

// in user/uthread.c file
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;
  t->ra = (uint64)func;
  t->sp = (uint64)(t->stack+STACK_SIZE);
}

另一个目标是确保 thread_switch 保存被切换走的线程的寄存器，恢复被切换到的线程的寄存器，并返回到后一个线程的指令中最后离开的点(指令地址，用 ra )。我们须决定在哪里保存/恢复寄存器；修改结构线程以保存寄存器是一个好主意。你需要在 thread_schedule 中添加对thread_switch的调用。而 thread_switch 的实现，我完全参考内核的线程切换，

// in user/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 */

Using threads

本质上将一个 hash table 用 pthread 库改成线程安全的结构。其实只用加锁就行。为了保证时间效率(作业要求)，每个 bucket 配一个锁。用细粒度的锁减少 contention。比较简单，这里不放代码了。

Barrier

Barrier 是应用程序中的一个点，所有参与的线程都必须在这个点等待，直到所有其他参与的线程也到达该点。我们需要使用pthread条件变量，类似于xv6的睡眠和唤醒。

这个 assignment 的要求有两个关键，

我们的实现必须处理一连串的 barrier call，并且用 bstate.round记录轮的数目(一轮就是一组线程调用barrier)。当所有的线程都到达屏障点时，我们需要增加 bstate.round。
还必须考虑一种情况：一个线程在其他线程退出障碍之前再次调用barrier。也就是上一轮的线程还没完全离开，下一轮的线程已经准备进入了。特别是，这个 assignment 要求我们重用 bstate，即全局只有一个 bstate.nthread。我们需要确保，当上一轮仍然在使用它时, 新一轮的线程(测试用例是循环中运行)不会增加 bstate.nthread。

为了解决这类情况，我增加一个信号量 bstate.leaving 指示当前是线程进入barrier阶段，还是线程离开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
  int leaving;  // if leaving is 1, all threads doesn't leave the barrier.
                // if leaving is 0, threads of last round have leaved the barrier
} bstate;

本质上 pthread_cond_wait 类似一个睡眠操作，而 pthread_cond_broadcast 类似唤醒操作。代码实现如下，

// in notxv6/barrier.c file
static void 
barrier()
{
  // Block until all threads have called barrier() and
  // then increment bstate.round.
  //
  pthread_mutex_lock(&bstate.barrier_mutex);
  while(bstate.leaving) {
    pthread_cond_wait(&bstate.barrier_cond, &bstate.barrier_mutex);
  }
  bstate.nthread += 1;
  if (bstate.nthread < nthread)
  {
    pthread_cond_wait(&bstate.barrier_cond, &bstate.barrier_mutex);  // go to sleep on cond, releasing lock mutex, acquiring upon wake up  
    bstate.nthread -= 1;
  } else {
    bstate.nthread -= 1;
    bstate.round += 1;
    bstate.leaving = 1;
  }

  if(bstate.nthread == 0) {
    bstate.leaving = 0;

    pthread_cond_broadcast(&bstate.barrier_cond);     // wake up every thread sleeping on cond
    pthread_mutex_unlock(&bstate.barrier_mutex);
  } else if(bstate.nthread == nthread - 1){
    pthread_cond_broadcast(&bstate.barrier_cond);     // wake up every thread sleeping on cond
    pthread_mutex_unlock(&bstate.barrier_mutex);
  } else {
    pthread_mutex_unlock(&bstate.barrier_mutex);
  }
}

在所有线程的执行状态下，我们始终用 bstate.nthread 指示到达的 barrier 的线程数，bstate.round 指示轮数，用 bstate.leaving 指示当前是否为离开 barrier 阶段。我仅用一个锁保护这些共享变量，一个条件变量指示变化(其实可以再分细粒度，但代码会变得复杂，我取简单实现)。此处，我们需要保证线程进入与离开 critical section 时，以上三个字段保持 invariant 。
在 lock 与 cond_wait(放弃锁睡眠)之间进行条件判断，当前如果属于 leaving 阶段，则睡眠等待。
增加 bstate.nthread 后判断是否全部线程到达，除了最后一个到达的线程，其他线程转向睡眠。
最后一个到达的线程直接离开 barrier 并负责切换 bstate.leaving ，唤醒之前到达的线程；最后一个离开的线程也要唤醒“可能存在的”、“下一轮的”、提前准备进入barrier的线程。p.s.这里其实可以分为两个条件变量的。

一个值得小心的点，broadcast 必在 critical section 内，否则，如果先 unlock 再 broadcast，在 broadcast 前，一个线程可能先 lock 仍未 sleep/cond_wait，导致最后导致这个唤醒被错过。示例

错误调用序列，

waker	sleeper
unlock/release	…
…	lock/acquire
broadcast/signal/wakeup	…
…	cond_wait/sleep

Conclusion

这节课将之前 Scheduling 的知识比较好地联系在一起。第一个作业考验对线程切换的熟悉；第二个只要知道锁的粒度与使用就能通过；最后一个作业有点难度也有价值，需要对并发算法与锁的底层逻辑有一定了解。

Reference

system-programming