|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ 居眠り ： [いねむり] 1. (n,vs) dozing 2. nodding off ・ 眠り ： [ねむり] 【名詞】 1. sleep ・ 床屋 ： [とこや] 【名詞】 1. barber ・ 問 ： [もん] 【名詞】 1. problem 2. question ・ 問題 ： [もんだい] 【名詞】 1. problem 2. question ・ 題 ： [だい] 1. (n,vs) title 2. subject 3. theme 4. topic
計算機科学における居眠り床屋問題(sleeping barber problem)とは、典型的なプロセス間通信およびプロセス間での同期に関する問題である。客がいる限り働いたまま、客がいなければ休んだままということを繰り返す理容師に例えられることからついた名称。理容師と客の挙動で、前述したプロセス間の問題を表現する。 == 問題 == 理容師が一人だけいる床屋を考えてみる。この店には理容椅子が一脚あり、待合室には椅子がいくつか置かれている。理容師は整髪を終えると客を帰し、待合室で次の客が待っていないか調べる。もし客がいたら理容椅子に座らせ、髪を切り始める。客がいなかった場合は、理容師は昼寝を始める。一方、客は来店したらまず理容師が何をしているのか調べる。もしも理容師が昼寝をしていたら、理容師を起こして自分の髪を切らせる。理容師が他の客の髪を切っていたら、待合室の椅子に座る。ただし待合室に空きがなければ、客は髪を切らずに黙って帰る。 上記の挙動で床屋は順調に機能し、理容師は客がいなくなるまで髪を切っては、また客が来るまでは昼寝することができると思われる。しかし実際にはいくつもの潜在的な問題があり、それらはスケジューリングにおける一般的な問題の具体例となる。 問題は、理容師や客の挙動（待合室を調べる、理容師を調べる、待合室の椅子に座るなど）に要する時間が不明だということにある。たとえば、来店した客はまだ仕事中の理容師を見たら待合室に向かう。そしてその客が待合室の椅子に腰を下ろすまでの間に、理容師が髪を切り終えて待合室の様子を調べる。しかし厳密には待合室に客がいない（まだ誰も椅子に腰を下ろしていない）ので、理容師は昼寝を始めてしまう。理容師は客に起こされるのを待ち続け、一方で客は理容師に呼ばれるのを待ち続ける。そして二人め以降の客は、既に待合室に客がいるので、理容師が寝ているかどうかを調べようとせず、ついに床屋は機能しなくなってしまう。 また二人の客が同時に来店するケースでは、理容師がまだ仕事中かつ待合室に椅子がもともと一つしかない場合、二人とも椅子に座ろうとしてしまう。 居眠り床屋問題はエドガー・ダイクストラの考案であるという説がある。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「居眠り床屋問題」の詳細全文を読む スポンサード リンク
|