テキストの58〜59ページ

本文

xv6におけるsleepとwakeupの実装について見てみよう。
sleepに現在のプロセスをSLEEPINGとして印をつけさせ、そしてschedを呼びそのプロセッサを解放し、wakeupは与えられたポインタ上でスリープ中のプロセスを探し、それをRUNNABLEとして印をつける、というのが基本的なアイデアである。

sleepはいくつかの条件チェックから始まる。
現在のプロセスがあり（proc == 0 だとpanic）、ロックを渡されてなければ（lk == 0 でもpanic）ならない。
チェックが終わるとまず、ptable.lockを獲得する。
そのままでは、ptable.lockとlkの両方を保持したままスリープしてしまう。
lkの保持は、（例えばrecvのような）呼び出し側で必要とされる。
lkを保持しているということは、wakeup(chan)を呼びはじめれるプロセス（例えばsendを実行してるプロセス）が他にないということを確実にする。
この時点でsleepはptable.lockを保持し、lkを安全に解放出来るようになる。
他のいくつかのプロセスが、wakeup(chan)を呼び出すかもしれないが、wakeupはptable.lockが獲得可能になるまで実行されないので、sleepがプロセスを確実にスリープさせるまで待たなければならず、起き損ないの問題（前節参照）は起きない。

proc.cのsleep関数

// Atomically release lock and sleep on chan.
// Reacquires lock when awakened.
void
sleep(void *chan, struct spinlock *lk)
{
  if(proc == 0)
    panic("sleep");

  if(lk == 0)
    panic("sleep without lk");

  // Must acquire ptable.lock in order to
  // change p->state and then call sched.
  // Once we hold ptable.lock, we can be
  // guaranteed that we won't miss any wakeup
  // (wakeup runs with ptable.lock locked),
  // so it's okay to release lk.
  if(lk != &ptable.lock){  //DOC: sleeplock0
    acquire(&ptable.lock);  //DOC: sleeplock1
    release(lk);
  }

  // Go to sleep.
  proc->chan = chan;
  proc->state = SLEEPING;
  sched();

  // Tidy up.
  proc->chan = 0;

  // Reacquire original lock.
  if(lk != &ptable.lock){  //DOC: sleeplock2
    release(&ptable.lock);
    acquire(lk);
  }
}

微妙に複雑な場合がある。
もしlkが&ptable.lockと等しい場合、sleepはそれを&ptable.lockとして獲得し、lkとして解放しようとしてデッドロックに陥るだろう。
この場合、sleepはacquireとreleseがお互いに相殺されることを考慮し、それらを完全にスキップする。

この時点で、sleepはptable.lockのみを保持し、スリープチャンネル記録し、プロセスの状態を変更し、schedを呼ぶことで、プロセスをスリープさせる事ができる。

後のどこかの段階で、プロセスはwakeup(chan)を呼ぶだろう。
wakeupはptable.lockを獲得し、実際の処理を行うwakeup1を呼ぶ。
wakeup1はプロセスの状態を操作するし、前節で見たように、ptable.lockはsleepとwakeupがお互いに機会を逃さないようにすることを確実にするので、wakeupがptable.lockを保持する事はとても重要である。
ときおり、スケジューラはptable.lockを既に保持しているときにwakeupを実行する必要があるので、wakeup1として分離されている。
直接wakeup1を呼ぶ例は後で説明する。
wakeup1は、プロセステーブルを走査する。
chanが合致し状態がSLEEPINGなプロセスを見つけたら、そのプロセスの状態をRUNNABLEに変更する。
次にスケジューラが実行されたとき、そのプロセスは実行準備が整ってるとしてスケジューラに扱われるだろう。

proc.cのwakeup1, wakeup関数

// Wake up all processes sleeping on chan.
// The ptable lock must be held.
static void
wakeup1(void *chan)
{
  struct proc *p;

  for(p = ptable.proc; p < &ptable.proc[NPROC]; p++)
    if(p->state == SLEEPING && p->chan == chan)
      p->state = RUNNABLE;
}

// Wake up all processes sleeping on chan.
void
wakeup(void *chan)
{
  acquire(&ptable.lock);
  wakeup1(chan);
  release(&ptable.lock);
}

wakeupは常に、wakeupの条件がなんであれその監視を妨げるようなロックを保持してる間、呼ばれなければならない。（謎）
前節の例では、そのようなロックにあたるのはq->lockである。
スリープ中のプロセスがなぜ起き損ねたくないか、そのための完全な根拠は、スリープするまで条件をチェックする前から常に、条件上もしくはptable.lockもしくは両方のロックを保持する。（謎）
それらのロックの両方を保持してる間、wakeupが実行してから、wakeupはスリープさせる可能性があるものが条件をチェックする前、もしくはスリープさせる可能性があるものそれ自身がスリープした後に実行すべきである。（謎）

ときおり、複数のプロセスが同じチャンネル上でスリープしてる場合がある。
例えば、2つ以上のプロセスが1つのパイプから読み込む場合である。
1回のwakeupの呼び出しは、それらすべてを起こすだろう。
それらのひとつは、最初に実行されsleepを呼びロックを獲得し、そして（パイプの例だと）パイプに書きこまれた何らかのデータを読み込むだろう。
その他のプロセスは、起こされたにも関わらず、読み込むべきデータがないということに気づくだろう。
そういったプロセスの視点から見ると、そのwakeupは”見せかけ”であり、そういったプロセスはまたスリープする必要がある。
こんな理由で、sleepは常に、条件をチェックするループの中で呼ばれるようになっている。

sleepとwakeupの呼び出し側は、チャンネルとして何らかの共通の便利な番号を使うことが出来る。
習慣上、xv6は、ディスクバッファのような、待機に関連したカーネルのデータ構造のアドレスをしばしば使う。
もしsleep/wakeupを2箇所で使ってて、偶然にも同じチャンネルを選択してしまっても、害はない。
見せかけのwakeupに遭遇するだろうが、上記で説明したようなループは、この問題に耐性がある。
sleep/wakeupの魅力の多くは、両方共軽く（スリープチャンネルとして働くような特別なデータ構造を作る必要がない）、間接的なレイヤー（呼び出し側はsleep/wakeupが相互に影響しあう詳細な方法を知る必要がない）を提供するところにある。

感想

sleepとwakeupのxv6における実装の説明です。

今回ちょっと原文の言い回しが難しかったです。
途中かなり謎な段落もありました。

ぶっちゃけ今回は文章読まなくても、ソースと前節の内容を理解できてれば問題ないような気がします。