食事する哲学者の問題
食事する哲学者の問題(しょくじするてつがくしゃのもんだい、Dining Philosophers Problem)とは、並列処理に関する問題を一般化した例である。古典的なマルチプロセスの同期(排他制御)問題であり、大学レベルの計算機科学課程にはほぼ確実に含まれている。
1965年、エドガー・ダイクストラは5台のコンピュータが5台のテープ装置に競合アクセスするという同期問題を提示した。間もなく、この問題はアントニー・ホーアによって「食事する哲学者の問題」に変形して語られることとなった。
他の哲学者がそのフォークを要求したことがあったら、そのフォークを clean 状態にして送る。
この解法は大規模な並列実行でも適用可能である。
スタベーション問題も解決できる。clean と dirty のラベルは、最も長く食事にありつけていないプロセスを優先し、最近食事したプロセスの優先順位を下げる効果がある。哲学者がフォークを手放さずに2回続けて食事できないという規定を設けた解法と比べてみると、上に述べた解法の方が柔軟だが、傾向は後者と同じだということがわかる。
この分析から、彼らはフォークの配布とその clean / dirty 状態による優先レベルのシステムを導き出した。彼らはこのシステムを非環状グラフで表せるかもしれないとし、もしそうなら、その動作は環状グラフに変換できないことになる。それは、デッドロックが起きないことを保証しているのと等しい。しかし、システムが最初に完全に対称な状態(例えば、哲学者が全員左のフォークを持っている状態)に初期化される場合、グラフは最初から環状になり、デッドロックを防ぐことができない。小さい識別番号の哲学者が dirty 状態のフォークを持つよう初期化することで、初期状態を非環状グラフにできる。