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