MIT6.S081 lab7 Multithreading

这个实验主要是熟悉多线程编程，比较容易。

第一个实验线程切换，这个只要理解xv6的线程调度就能解决，甚至代码都可以直接抄。

第二个实验哈希表加锁。关键代码量不到两行，甚至分桶加锁也是。

第三个实验同步屏障，这个还有意思一点。

Barrier

a point in an application at which all participating threads must wait until all other participating threads reach that point too.

同步屏障：它是一个点，任何参与线程都必须等到其他所有参与线程达到这个点之后，才能继续执行下去。

一个应用的例子就是Java的CountDownLatch。

怎么实现？

我们在barrier的初始化时，肯定是想知道有多少个参与线程，需要一个字段nthread记录。我们还需要知道当前有多少个进程达到了point，需要一个cnt字段。

为了实现同步，我们利用了posix的互斥锁和条件变量。

struct barrier {
  pthread_mutex_t barrier_mutex;
  pthread_cond_t barrier_cond;
  int cnt;
  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;
  bstate.cnt = nthread;
}

显而易见，cnt由互斥锁保护。调用barrier函数就是增加cnt的过程，增加完cnt我们再比较cnt和nthread。

• 如果cnt==nthread，那么我们就唤醒所有睡眠的线程，并且重置cnt为0。
• 如果cnt<nthread，那么就睡眠。

static void barrier(){
  pthread_mutex_lock(&bstate.barrier_mutex);
  //对当前round调用barrier的线程进行计数
  bstate.nthread+=1;
  if(bstate.nthread<nthread){
     pthread_cond_wait(&bstate.barrier_cond,&bstate.barrier_mutex);
  }else{   
      bstate.round+=1;//进入下一个round 
      bstate.nthread=0;//下一round的 bstate.nthread清零
      pthread_cond_broadcast(&bstate.barrier_cond); // wake up every thread sleeping on cond
  }
  pthread_mutex_unlock(&bstate.barrier_mutex);
}

噢，多么直观并且能通过测试。

细节

Hint中有一句：Make sure that a thread that leaves the barrier and races around the loop doesn’t increase bstate.nthread while a previous round is still using it.

举例子来说，轮次1的N个线程都到达了屏障，其中有一个线程A离开了屏障，进入了下一轮2。那么此时要小心注意A在轮次2不能增加 bstate.nthread ，因为轮次1的其他线程还在使用bstate.nthread。

那么我们看代码，轮次1的其余线程其实都到达了pthread_cond_wait(&bstate.barrier_cond,&bstate.barrier_mutex);，被唤醒后不依赖bstate.nthread，线程被唤醒后的操作就是释放锁并返回。

即便到轮次2，A又获得了锁并成功增加了bstate.nthread，但此时bstate.nthread为1，A线程其实又会睡眠释放锁，这就给轮次1的其余线程拿锁的机会。

让我们来看错误的实现：

static void barrier(){
  pthread_mutex_lock(&bstate.barrier_mutex);
  bstate.nthread+=1;
  pthread_cond_broadcast(&bstate.barrier_cond); 
  while(bstate.nthread<nthread)
	{
     pthread_cond_wait(&bstate.barrier_cond, &bstate.barrier_mutex);
  }
 	if(bstate.nthread == nthread)
  {   
      bstate.round+=1;//进入下一个round 
      bstate.nthread=0;//下一round的 bstate.nthread清零
     
  }
  pthread_mutex_unlock(&bstate.barrier_mutex);
}

使用条件变量的惯例是包裹在循环中，但在这里的反而适得其反。轮次1的线程wait返回后，还需要检查bstate.nthread变量，而这个变量是可能会被轮次2的线程A影响的（存在一种时序，A先获得了锁）。