テキストの55〜57ページ

本文

ロックは、CPU同士やプロセス同士がお互いに干渉し合うのを避けるのに役立ち、スケジューリングは、複数のプロセスがCPUを共有するのに役立つ。
しかしこれまで、我々はプロセス間通信を楽にするような概念は持ち合わせていなかった。
“スリープ”（sleep）と”ウェイクアップ”（wakeup）はその間隙を埋め、あるプロセスがあるイベントを待つためにスリープさせ、一度イベントが起きたら他のプロセスにそのプロセスをウェイクアップさせる事を可能にする。
スリープとウェイクアップは、しばしば順序協調（シーケンスコーディネーション, sequence coordination, オレオレ訳なので注意）、条件付き同期化（コンディショナルシンクロナイゼーション, conditional synchronization, こちらもオレオレ訳なので注意）の機構と呼ばれる。
OS学的に他の似たような機構はたくさんある。

我々が何を言いたいかハッキリさせるために、シンプルな生産者/消費者（producer/consumer）キューについて考えてみよう。
このキューは、プロセッサとデバイスドライバを同期化するためにIDEドライバによって使われたキューに似ている。（第2章参照）
しかし、抽象的なすべてのIDE特有のコードはない。
このキューは、ひとつのプロセスが他のプロセスにゼロじゃないポインタを送ることが出来る。
送信側と受信側はそれぞれひとつしかなく、それぞれ別のCPUで実行されていると仮定すると、以下の実装は正しい。

struct q {
  void *ptr;
};

void*
send(struct q *q, void *p)
{
  while(q->ptr != 0)
    ;
  q->ptr = p;
}

void*
recv(struct q *q)
{
  void *p;

  while((p = q->ptr) == 0)
    ;
  q->ptr = 0;
  return p;
}

sendは、キューが空（ptr == 0）になるまでループし、そしてキューの中にポインタpをセットする。
recvは、キューに何か入ってる状態になるまでループし、ポインタを取り出す。
別のプロセスで実行されるとき、sendとrecvは両方ともq->ptrを編集するが、sendはq->ptrがゼロのときだけ書き込み、recvはq->ptrがゼロじゃないときだけ書き込むので、お互いに踏みつけることはない。

上記の実装は多分正しいが、効率が悪い。
送信側がたまにしか送信しない場合、受信側はポインタが来るのを期待してループしてる間、その時間のほとんどを消費してしまうだろう。
sendがポインタをセットしたときに受信側に通知する方法があれば、受信側のCPUは（その通知を待ってる間、他の）もっと生産的な仕事を見つけることができただろう。

次のように動作する、sleepとwakeupという関数の組について想像してみよう。
sleep(chan)は、ウェイトチャンネル（wait channel）と呼ばる任意の値であるchan上でスリープする。
sleepは、呼び出したプロセスをスリープさせ、他の仕事のためにCPUを解放する。
wakeup(chan)は、chan上でスリープしてるすべてのプロセス（もしあるなら）を起こし、それらのsleepの呼び出しを戻らせる。
chan上で待っているプロセスがない場合、wakeupは何もしない。
sleepとwakeupを使うことによって、我々はキューの実装を次のように改良出来る。

void*
send(struct q *q, void *p)
{
  while(q->ptr != 0)
    ;
  q->ptr = p;
  wakeup(q);  /* wake recv */
}

void*
recv(struct q * q)
{
  void* p;

  while((p = q->ptr) == 0)
    sleep(q);
  q->ptr = 0;
  return p;
}

recvは、スピンする代わりにCPUを解放するようになった。素敵だ。
しかしながら、このインターフェイスによるsleepとwakeupの設計が直接的ではなく、起き損ない問題（lost wakeup probrem）として知られているものから被害を受けることが分かる。（図4-2参照）
recvが215行目でq->ptr == 0であるということを見つけ、sleepを呼ぶことを決定すると仮定しよう。
recvがsleep出来る前、sendは他のCPUで実行されていて、それはq->ptrを非ゼロに変更しwakeupを呼ぶ。
そのときwakeupはスリープ中のプロセスが無いので結果的に何もしない。
そしてrecvは216行目の実行を続行し、sleepを呼びスリープする。
これは問題を引き起こす。
recvはすでにポインタが届いてるのにスリープして待つ事になる。
次のsendは、recvがキューのポインタを取り出すのを待ち続け停止するだろう。
この時点でシステムはデッドロックに陥るだろう。

図4-2 起き損ない問題の例

この問題の根源は、recvはq->ptr == 0のときだけスリープしなければならないというインバリアントが、都合の悪い瞬間に実行されているsendによって侵害されるというところにある。
このインバリアントを保護するために、我々は、sleepを呼び出したプロセスがスリープしたあとにsleepによって解放されるようなロックを導入する。
これは、上記の例のような起き損ないを避ける。
一度sleepを呼び出したプロセスが再度起きたら、sleepは戻る前にそのロックを再獲得する。
次のコードがあり得るとしたい。

struct q {
  struct spinlock lock;
  void *ptr;
}

void*
send(struct q *q, void *p)
{
  acquire(&q->lock);
  while(q->ptr != 0)
    ;
  q->ptr = p;
  wakeup(q);
  release(&q->lock);
}

void*
recv(struct q *q)
{
  void* p;

  acquire(&q->lock);
  while((p = q->ptr) == 0)
    sleep(q, &q->lock);
  q->ptr = 0;
  release(&q->lock);
  return p;
}

recvがq->lockを保持するという事実は、recvがq->ptrをチェックしsleepを呼ぶ間に、sendがwakeupを実行することを防ぐ。
もちろん、このままだと送信側のプロセスがwakeupを呼ぶのを妨害し、デッドロックに陥るので、受信側のプロセスは、スリープしてる間q->lockは保持しないほうがいい。
だから、sleepがアトミックにq->lockを開放し、プロセスを眠りに導くということが必要である。

完全な送信側/受信側の実装では、前回のsendで送られた値を受信側が取り出すのを待つときにも、send内でスリープするようになってるだろう。

感想

プロセス間通信と、その際の強力なツールになるsleepとwakeupについての話です。
重要なのは、ここではまだ実際のコードは一切出てきてないという事です。
実際のコードは多分次の節で出てきます。

最後の例では、変なタイミングでsleepやwakeupが実行されないようにロックが導入されてますが、そのままだとrecvがロックを保持してデータが届くのを待っている間、sendは何も出来ない（acquireで止まる）ということになります。
これを避けるために、sleep内では（本文ではコードは示されてませんが）通常の獲得→解放という順序とは逆に、q->lockを解放してから獲得するようになってるので、受信側がスリープ中（データ待ち中）はsendが実行可能になるということになります。