[xv6]:sleep-and-wakeup

类似于pthread中的条件变量，xv6中也实现了与pthread_cond_wait()和pthread_cond_broadcast()类似的操作

在xv6中的对应api为sleep()以及wakeup()

• sleep()

  oid
  sleep(void *chan, struct spinlock *lk)
  {
    struct proc *p = myproc();
    
    // 这里有两把锁, 一把是进程锁，一把是给定的lk
    // 当进程调用该函数时，其需要获取进程锁p->lock, 因为接下来需要修改进程的state
    // 同时进程还需要释放lk, 因为这是sleep函数所要求的
    // 注意这里lk与p->lock是同一把锁的问题, 如果是同一把锁，那么acquire()操作就会造成死锁
    if(lk != &p->lock){  //DOC: sleeplock0
      acquire(&p->lock);  //DOC: sleeplock1
      release(lk);
    }
  
    // Go to sleep.
    p->chan = chan;
    p->state = SLEEPING;
  
    // 此时进程还持有着p->lock
    sched();  // p->lock被scheduler释放 
    // 此时进程已经从调度返回, 已经在scheduler()中重新获得了锁
    // Tidy up.
    p->chan = 0;
  
    // Reacquire original lock.
    if(lk != &p->lock){
      release(&p->lock);
      acquire(lk);
    }
  }

• wakeup()

  // 唤醒所有睡在chan上的进程
  // 这里的实际操作其实就是将进程的状态改为(RUNNABLE)可调度
  void
  wakeup(void *chan)
  {
    // 在调用wakeup时，会持有sleep()中指定的锁lk
    struct proc *p;
    for(p = proc; p < &proc[NPROC]; p++) {
      acquire(&p->lock);
      // wakeup什么时候进入该行?
      // 有两种情况: 
      // 1. sleep()中的lk与p->lock不是同一把锁, 那么在sleep()中的sched()进入scheduler()
      // 并且释放p->lock之后，wakeup()可以进入该行，此时p->state == SLEEPING, 没有丢失唤醒
      // 2. sleep()中的lk与p->lock是同一把锁, 这种情况和上面一样，也是在schedule()释放p->lock之后
      if(p->state == SLEEPING && p->chan == chan) {
        p->state = RUNNABLE;
      }
      release(&p->lock);
    }
  }

丢失唤醒

下面是一个会产生丢失唤醒的例子

s->count = 0;

void V(struct semaphore *s)
{
  acquire(&s->lock);
  s->count += 1;
  wakeup(s);
  release(&s->lock);
}

void P(struct semaphore *s)
{
  while (s->count == 0)
    sleep(s);
  acquire(&s->lock);
  s->count -= 1;
  release(&s->lock);

• 假设当进程p1调用P, 进入第11行，发现s->count == 0, 准备进入第12行
• 此时发生计时器中断，进程p2调用V, s->count变为1, 然后进入第5行，调用wakeup(), 尽管此时并没有进程睡在信号量s之上
• 计时器再次中断，进程p1重新开始执行，进入第12行，陷入sleep(), 而此时s->count却是1而不是0， 这就叫丢失唤醒
• 当发生丢失唤醒之后，除非再次有进程调用V, 否则进程p1将一直陷入睡眠

xv6的实现中不会发生丢失唤醒的问题, 因为其在进行state的设置之前先获取了p->lock, 这样如果其它进程想要调用wakeup唤醒state还未设置为SLEEPING的进程时就会陷入阻塞

虚假唤醒

当多个进程睡在同一个条件之下，就有可能发生虚假唤醒的问题，xv6的实现也可能发生这种情况

• 例子

  • 假设当前有进程p1, p2, 他们都调用了sleep(g->chan, g->lock), 即睡在同一个条件，同一把锁之上

    while (read(fd) == 0) 
        sleep(&g->chan, &g->lock);
    release(g->lock);

  • 此时进程p3对文件写入,调用wakeup(), 进程p1, p2都被唤醒，此时它们会对g->lock进行竞争，假设p1先抢到了g->lock

  • 其使用read()将文件fd中的内容全部读取完毕, 然后进入第三行, 释放锁

  • 计时器发生中断，调度到进程p2,进程p2抢到锁，执行read(), 却发现此时文件是空的, 它被唤醒了却什么都做不了, 这就叫虚假唤醒

  虚假唤醒最有效的解决方案就是将sleep()置于循环当中，当发生虚假唤醒时，使被唤醒的进程再度sleep(0)