实验文档

概述

这次实验主要涉及多线程编程，和之前的实验不太一样，比较偏向于应用层面，除了任务一外都是在宿主机上编写多线程程序，应该是xv6不支持系统级的多线程。

内容

Uthread: switching between threads

这个任务要求对一个程序填空，这个程序在用户层面实现了多线程的调度。但实际上这个调度和xv6内核的进程调度非常相似。

首先是对thread_schedule函数进行填空，只需要调用切换函数就行了，根据文档的说明，这个切换函数是保存当前线程用到的所有callee-saved寄存器，然后将这些寄存器全部赋值为下一个线程里保存的值，联想到xv6内核里的context结构体就是用来保存这些寄存器的，所以直接复制过来并作为thread结构体的一个属性，那么调用切换函数就会像这样：

thread_switch((uint64)(&t->context), (uint64)(&current_thread->context));

thread_switch()在uthread_switch.S里实现，这里我不贴代码了，因为和kernel文件夹里的swtch.S里的内容基本一样。

注意文档里的这句话：

One goal is ensure that when thread_schedule() runs a given thread for the first time, the thread executes the function passed to thread_create(), on its own stack.

这里不是说在thread_schedule()中需要检查线程是否第一次运行，如果是则转入对应函数；而是说thread_schedule()在运行刚才加入的切换代码后，自动开始运行对应函数。这就需要在thread_create初始化线程的时候，把它保存的ra寄存器的值赋成对应函数的入口地址，这样在切换结束后运行汇编代码中的ret就自动跳转到ra指向的位置了；另一个需要初始化的是sp寄存器，因为每个线程都各自有一个栈，所以要让自己的sp寄存器指向自己的栈底，由于栈地址从高向低增长，所以sp寄存器赋为栈数组的最高地址：

  t->context.ra = (uint64)func;
  t->context.sp = (uint64)t->stack + STACK_SIZE;

Using threads

这个任务要求解决一个程序中的竞争问题。通常两个线程的竞争出现在同时写的过程中，所以把put函数用锁包起来，同时为了速度，一个桶弄一个锁：

  int i = key % NBUCKET;

  // is the key already present?
  pthread_mutex_lock(lock + i);
  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);

其实我个人觉得只有insert那个地方需要加锁，因为两个线程同时修改一个键的过程不管加不加锁都是一个结果无法预测的行为（先后不明），所以程序肯定不会同时修改一个键。不过既然时限给的是1.25倍，文档的意思应该是整个函数都得加锁。

Barrier

这个任务要求解决一个程序中的同步问题。核心是理解pthread_cond_wait这个函数的功能，我没理解好文档中的注释，结果遇到了各种奇怪的问题。pthread_cond_wait这个函数在调用时会释放锁，隐含的意思就是在执行这个函数前必须先锁上；函数在阻塞结束被唤醒时会获取锁，隐含的意思就是在这个函数调用结束后需要释放锁：

    pthread_mutex_lock(&bstate.barrier_mutex);
    bstate.nthread++;
    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);

另外一点就是pthread_mutex_lock的调用必须放在前面，如果只在else后面调用的话，可能会出现死锁问题，即如果第一个线程加了nthread以后运行得比较慢，还没有运行cond_wait的时候另一个线程跑得快，把cond_broadcast给运行了，那么第一个线程运行到cond_wait就卡死了，没有线程去唤醒它，所以这整个if语句必须是个原子操作，不能并行。

总结一下，这次实验基本没怎么涉及操作系统的理论，重点还是并行程序的应用。不过不管是国内还是国外，操作系统课在进程（线程）这一章节教的也基本上都是竞争、同步、死锁这些应用上的问题，可能进程（线程）的独特之处就在这里，虽然是操作系统中的重点部分，但最值得关注的还是应用上的问题。