「食事する哲学者の問題」の版間の差分
削除された内容 追加された内容
35行目:
== 解法 ==
=== 哲学者の位置により右手か左手を優先する解法 ===
この解法では、哲学者の人数が偶数人であるという大前提を置く（人数が奇数の場合には適用できない）。哲学者を「グループEven」と「グループOdd」の2グループに分類し、隣どうしの哲学者は必ず違うグループになるようにする（この分類は偶数でなければできない）。そして、「グループEven」の哲学者は必ず先に右のフォークを取ろうとするものとし、「グループOdd」は先に必ず左から、とする。そのようにすると依存関係の循環は存在しないため、問題は発生しなくなる。
=== ウェイターを配する解法 ===
比較的単純な解法は、食卓にウェイターを配置することでなされる。哲学者らはフォークを手に取る際に必ずウェイターの許可を取ることとする。ウェイターはどのフォークが使われているかを把握しているので、デッドロックを防ぐよう調停することができる。4本のフォークが使用中のとき、最後のフォークを哲学者が要求した場合、ウェイターが許可するのを待つ必要があり、使用中のフォークが解放されるまで許可は与えられない。哲学者が常に右のフォークより先に左のフォークをとる（あるいは逆）よう決めておけば、話は単純化される。ウェイターは[[セマフォ]]と呼ばれるダイクストラが1965年に導入した概念のように振る舞う<ref>[[エドガー・ダイクストラ|Dijkstra, Edsger W.]] ''EWD-123.'' E.W. Dijkstra Archive. Center for American History, [[テキサス大学オースティン校|University of Texas at Austin.]] ([http://www.cs.utexas.edu/users/EWD/ewd01xx/EWD123.PDF original]; [http://www.cs.utexas.edu/users/EWD/transcriptions/EWD01xx/EWD123.html transcription])</ref>。
| |||