居眠り床屋問題
理容師が一人だけいる床屋を考えてみる。この店には理容椅子が一脚あり、待合室には椅子がいくつか置かれている。理容師は整髪を終えると客を帰し、待合室で次の客が待っていないか調べる。もし客がいたら理容椅子に座らせ、髪を切り始める。客がいなかった場合は、理容師は昼寝を始める。一方、客は来店したらまず理容師が何をしているのか調べる。もしも理容師が昼寝をしていたら、理容師を起こして自分の髪を切らせる。理容師が他の客の髪を切っていたら、待合室の椅子に座る。ただし待合室に空きがなければ、客は髪を切らずに黙って帰る。
上記の挙動で床屋は順調に機能し、理容師は客がいなくなるまで髪を切っては、また客が来るまでは昼寝することができると思われる。しかし実際にはいくつもの潜在的な問題があり、それらはスケジューリングにおける一般的な問題の具体例となる。