写在前面

这个实验是多线程安全和同步的内容，实验地址在这里。说实话，有点简单，用了一天时间就写完了，感觉最近的实验，从实验三之后难度就降低了很多。但是实验的内容还是很有用的，主要学习了一遍线程的切换过程，感觉受益很多，建议看一下课程里对应的多线程部分。我的实验代码在 github 上，感觉这个实验没太多代码和步骤需要分析，主要是基础知识，这里就随便写点我觉得重要的了。

线程调度

线程调度的过程大概是以下几个步骤：

首先是用户线程接收到了时钟中断，强迫CPU从用户空间进程切换到内核，同时在 trampoline 代码中，保存当前寄存器状态到 trapframe 中；
在 usertrap 处理中断时，切换到了该进程对应的内核线程；
内核线程在内核中，先做一些操作，然后调用 swtch 函数，保存用户进程对应的内核线程的寄存器至 context 对象；
swtch 函数并不是直接从一个内核线程切换到另一个内核线程；而是先切换到当前 cpu 对应的调度器线程，之后就在调度器线程的 context 下执行 schedulder 函数中；
schedulder 函数会再次调用 swtch 函数，切换到下一个内核线程中，由于该内核线程肯定也调用了 swtch 函数，所以之前的 swtch 函数会被恢复，并返回到内核线程所对应进程的系统调用或者中断处理程序中。
当内核程序执行完成之后，trapframe 中的用户寄存器会被恢复，完成线程调度。

线程调度过程如下图所示：

xv6线程调度过程

线程调度的过程主要是保存 contex 上下文状态，因为这里的切换全都是以函数调用的形式，因此这里只需要保存被调用者保存的寄存器（Callee-saved register）即可，调用者的寄存器会自动保存。

进程、线程和协程

进程是操作系统资源分配的基本单位，而线程是处理器任务调度和执行的基本单位

在 xv6 中，一个进程只有一个线程，因此本实验中区分不大。

第一个实验的内容很像协程的概念，即用户线程切换时，不进入内核态，而是直接在用户线程上，让用户线程自己主动出让 cpu，而不是接受时钟中断。

更具体的区别可以查一查其他人写的博客。

实验内容

感觉整个实验，最核心的还是任务一，后面两个实验与 xv6 没啥关系。

任务一（Uthread）

实现一个用户线程调度的方法。

这里的“线程”是完全用户态实现的，多个线程也只能运行在一个 CPU 上，并且没有时钟中断来强制执行调度，需要线程函数本身在合适的时候主动 yield 释放 CPU。

第一步，上下文切换

首先是 uthread_switch.S 中实现上下文切换，这里可以直接参考（复制） swtch.S：

	.text

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

先将一些寄存器保存到第一个参数中，然后再将第二个参数中的寄存器加载进来。

第二步，定义上下文字段

从 proc.h 中复制一下 context 结构体内容，用于保存 ra、sp 以及 callee-saved registers：

// Saved registers for user 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 contex;           /* the context of thread */
};

第三步，调度 thread_schedule

在 thread_schedule 中调用 thread_switch：

void 
thread_schedule(void)
{
  // ...................
  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->contex, (uint64)&current_thread->contex);
  } 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
  t->contex.ra = (uint64)func;
  t->contex.sp = (uint64)&t->stack + (STACK_SIZE - 1);
}

线程栈是从高位到低位，因此初始化时栈指针 sp 应该指向数组底部（好像直接加 STACK_SIZE 也行？？）。

返回地址 ra 直接指向该函数的地址就行，这样开始调度时，直接执行该函数（线程）。

任务二（Using threads）

利用加锁操作，解决哈希表 race-condition 导致的数据丢失问题。

主要是，在加大锁还是小锁的问题。如果只加一个锁，锁的粒度很大，会导致丢失性能，结果还不如不加锁的单线程。因此需要将锁的粒度减小，为每个槽位（bucket）加一个锁。

pthread_mutex_t lock[NBUCKET];
static 
void put(int key, int value)
{
  int i = key % NBUCKET;

  pthread_mutex_lock(&lock[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(&lock[i]);
}

static struct entry*
get(int key)
{
  int i = key % NBUCKET;

  pthread_mutex_lock(&lock[i]);
  struct entry *e = 0;
  for (e = table[i]; e != 0; e = e->next) {
    if (e->key == key) break;
  }
  pthread_mutex_unlock(&lock[i]);
  return e;
}

在 main 函数中初始化锁：

  for(int i = 0; i < NBUCKET; i++) {
    pthread_mutex_init(&lock[i], NULL);
  }

任务三（Barrier）

这个做着有点懵，莫名其妙的做完了！？

主要是条件变量：

条件变量是利用线程间共享的全局变量进行同步的一种机制，主要包括两个动作：一个线程等待"条件变量的条件成立"而挂起；另一个线程使"条件成立"（给出条件成立信号）。为了防止竞争，条件变量的使用总是和一个互斥锁结合在一起。

这里是生产者消费者模式，如果还有线程没到达，就加入到队列中，等待唤起；如果最后一个线程到达了，就将轮数加一，然后唤醒所有等待这个条件变量的线程。

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) {
    bstate.nthread = 0;
    bstate.round++;
    pthread_cond_broadcast(&bstate.barrier_cond);
  } else {
    pthread_cond_wait(&bstate.barrier_cond, &bstate.barrier_mutex);
  }
  pthread_mutex_unlock(&bstate.barrier_mutex);
}