食事する哲学者

　「食事する哲学者」の問題は、並行処理の研究課題としてダイクストラにより提案された。その内容は以下の通り。

　円卓を囲んで５人の哲学者が思策にふけりつつ、時に応じて食事を取る。食事は円卓中央の皿に山盛りにされたスパゲッティである。しかし、このスパゲッティはあまりにもからまりあっているので、食べるときには両手にフォークを持って食べなければならない[*1]。
　フォークは、哲学者と哲学者の間に１本ずつ、都合５本が置いてある。つまり、右隣の哲学者が食事をしている最中は、右側のフォークは使用中であり、自分では使えないことになる。左についても同じ。
　ここで問題は、５人の哲学者が一人も飢えることがないように、食事をさせるプログラムを書くことである。

　この問題は並行処理のモデル化であり、フォークが共有資源にあたる。また、フォークを哲学者たちが取り合う部分がCritical Sectionとなる。

　一つの解答例を考えよう。次のような素朴なプログラムはどうだろう。　哲学者はまず右手のフォークが空くのを待ち、それが確保できたら、今度は左手のフォークを待つ。左も確保できたら食事を始めるというものである。
　このアルゴリズムは簡単に破綻する。５人の哲学者が同時に右手のフォークを取った場合を考えてみよう。全員が左手のフォークが空くのを待っているが、全員が右手のフォークを離さないので、永遠に左手のフォークは空かない。従って５人の哲学者は、右手にフォークを握り締めたまま、次第に飢えていくだろう。これは「デッドロック」の典型例である。
　また、そこまで極端でなくとも、特定の哲学者が飢えることも有り得る。たとえば、ある哲学者の両隣の哲学者が意地悪をして、二人が交代で食事を取ったら、真ん中の哲学者いつまでたっても左右のフォークが揃わず、飢えてしまうことになる。これはロックアウトと呼ばれる現象である。

　食事する哲学者の問題は、非常に単純ながら、資源共有と競合、Critical Sectionの問題を具体的に取り扱うことができ、並行プログラミングの題材として、よく議論される。逐次的アルゴリズムでいえば、８クイーン[*2]に匹敵する著名な問題と言えよう。

[*1]	わざとらしい設定ですね:-)
[*2]	コンピュータサイエンスや高度なアルゴリズムを志すものであれば、８クイーンくらいは知ってないとまずい。８クイーンについては別稿で説明する。