居眠り床屋問題

計算機科学における居眠り床屋問題（いねむりとこやもんだい、sleeping barber problem）とは、典型的なプロセス間通信およびプロセス間での同期に関する問題である。客がいる限り働いたまま、客がいなければ休んだままということを繰り返す理容師に例えられることからついた名称。理容師と客の挙動で、前述したプロセス間の問題を表現する。

問題

理容師が一人だけいる床屋を考えてみる。この店には理容椅子が一脚あり、待合室には椅子がいくつか置かれている。理容師は整髪を終えると客を帰し、待合室で次の客が待っていないか調べる。もし客がいたら理容椅子に座らせ、髪を切り始める。客がいなかった場合は、理容師は昼寝を始める。一方、客は来店したらまず理容師が何をしているのか調べる。もしも理容師が昼寝をしていたら、理容師を起こして自分の髪を切らせる。理容師が他の客の髪を切っていたら、待合室の椅子に座る。ただし待合室に空きがなければ、客は髪を切らずに黙って帰る。

上記の挙動で床屋は順調に機能し、理容師は客がいなくなるまで髪を切っては、また客が来るまでは昼寝することができると思われる。しかし実際にはいくつもの潜在的な問題があり、それらはスケジューリングにおける一般的な問題の具体例となる。

問題は、理容師や客の挙動（待合室を調べる、理容師を調べる、待合室の椅子に座るなど）に要する時間が不明だということにある。たとえば、来店した客はまだ仕事中の理容師を見たら待合室に向かう。そしてその客が待合室の椅子に腰を下ろすまでの間に、理容師が髪を切り終えて待合室の様子を調べる。しかし厳密には待合室に客がいない（まだ誰も椅子に腰を下ろしていない）ので、理容師は昼寝を始めてしまう。理容師は客に起こされるのを待ち続け、一方で客は理容師に呼ばれるのを待ち続ける。そして二人め以降の客は、既に待合室に客がいるので、理容師が寝ているかどうかを調べようとせず、ついに床屋は機能しなくなってしまう。

また二人の客が同時に来店するケースでは、理容師がまだ仕事中かつ待合室に椅子がもともと一つしかない場合、二人とも椅子に座ろうとしてしまう。

居眠り床屋問題はエドガー・ダイクストラの考案であるという説がある。

解法

いくつかの解法が存在する。解決の鍵はミューテックス(mutex)で、これは登場人物のうちミューテックスを持つ一人だけが状態を変更できる（同時に二人以上の状態が変更しない）ことを保証するものである。理容師は待合室を調べるまえにミューテックスを得なければならず（そして別の客の髪を切り始めるか昼寝を始めるかする時にmutexを開放する）、一方で客は入店するときにミューテックスを得なければならない（そして理容椅子か待合室の椅子に座った時にミューテックスを開放する）。これにより先述の問題は両方とも解決する。また、システムの状態（待合室の人数や理髪椅子の状態）を変更するのにも、いくつかのセマフォが必須となる。

複数の居眠り床屋問題(multiple sleeping barbers problem)は、実装と注意点において類似するが、複数の理容師と待機する客との調整に関してさらなる複雑さがある。

実装

以下の擬似コードは理容師と客との同期を保証しデッドロックも起こらないが、客のリソーススタベーションは起こるかもしれない。PとVはセマフォが提供する関数。

必要な変数（先述のとおり）:

 + Semaphore Customers = 0
 + Semaphore Barber = 0
 + Semaphore accessSeats (mutex) = 1
 + int NumberOfFreeSeats = N //待合室の空席の数

理容師のプロセス（またはスレッド）:

 while(true) { //無限ループ
   P(Customers) //客を調べようとする - いなければ昼寝する
   P(accessSeats) //この時点で理容師は目を覚ましている - 空席の数を変更しようとする
   NumberOfFreeSeats++ //空席が一つできた
   V(Barber)  //髪を切り始める
   V(accessSeats) //もはやロックは必要としない
   //ここでは髪を切っている最中
 }

客のプロセス（またはスレッド）:

 while(true) { //無限ループ
   P(accessSeats) //待合室の椅子に座ろうとする
   if ( NumberOfFreeSeats > 0 ) { //空席がある場合
     NumberOfFreeSeats-- //空席を一つ埋める
     V(Customers) //理容師が仕事中か調べようとする
     V(accessSeats) //もはやロックを必要としない
     P(Barber) //自分に順番が回ってきたが、理容師が何かしていれば待つ
     //ここでは髪を切られている最中
   } else { //空席がない場合
     //残念でした
     V(accessSeats) //しかしロックを開放するのを忘れてはいけない
     //客は黙って帰る
   }
 }

参考文献

Modern Operating Systems (2nd Edition) by Andrew S. Tanenbaum (ISBN 0-13-031358-0)
The Little Book of Semaphores by Allen B. Downey, http://greenteapress.com/semaphores
Cooperating sequential processes by E.W. Dijkstra. Technical Report EWD-123, 1965, Technological University, Eindhoven, The Netherlands.

問題

解法

実装

参考文献

関連項目