ウェイターを配する解法

ウィキペディア小見出し辞書

ウェイターを配する解法

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/06/04 23:33 UTC 版)

「食事する哲学者の問題」の記事における「ウェイターを配する解法」の解説

比較的単純な解法は、食卓にウェイターを配置することでなされる。哲学者らはフォークを手に取る際に必ずウェイターの許可を取ることとする。ウェイターはどのフォークが使われているかを把握しているので、デッドロックを防ぐよう調停することができる。4本のフォークが使用中のとき、最後のフォークを哲学者が要求した場合、ウェイターが許可するのを待つ必要があり、使用中のフォークが解放されるまで許可は与えられない。哲学者が常に右のフォークより先に左のフォークをとる（あるいは逆）よう決めておけば、話は単純化される。ウェイターはセマフォと呼ばれるダイクストラが1965年に導入した概念のように振る舞う。 具体的に説明するため、哲学者を時計回りにAからEまでラベル付けする。AとCが食事中で、4本のフォークが使われているとする。BはAとCの間に座っているので、どちらのフォークも入手できないのに対し、DとEの間には未使用のフォークが1本残っている。ここでDが食事したいとする。彼が5番目のフォークを取ると、デッドロックが発生する可能性がある。そこでDがウェイターにフォークをとってもよいか尋ね、待つよう命じられれば、AかCが食事を終えてフォークを置いたとき、少なくとも1人の哲学者が両手にフォークを持つことができることが確実となる。したがって、デッドロックは起きない。