食事する哲学者の問題

出典: フリー百科事典『ウィキペディア（Wikipedia）』

食事する哲学者の問題（Dining Philosophers Problem）とは、並列処理に関する問題を一般化した例である。古典的なマルチプロセスの同期問題であり、大学レベルの計算機科学課程にはほぼ確実に含まれている。

1971年、エドガー・ダイクストラは5台のコンピュータが5台のテープ装置に競合アクセスするという同期問題を提示した。間もなく、この問題はアントニー・ホーアによって「食事する哲学者の問題」に変形して語られることとなった。

[編集] 問題

5人の哲学者が食事したり、考え事をしたりしている。かれらのいる大学には、真ん中にスパゲッティの入った大きなボールが置かれた丸い食卓がある。その食卓には5枚の皿が置かれ、皿と皿の間にフォークが1本ずつ置かれている。

食事する哲学者の問題

スパゲッティをボールから取って自分の皿によそうには2本のフォークを必要とし、哲学者は一度に1本のフォークしかテーブルから取ることができない。（左右の手で同時に両側にある2本のフォークを取ることはできない、という意味。まずどちらかの側のフォークを取ってから、逆の側のフォークを取る。）哲学者同士は決して会話をしない。このため、5人が左のフォークを手にとって右のフォークが食卓に置かれるのを待つという危険なデッドロック状態が発生する可能性がある。

本来、デッドロック問題の解説手段として使われた。このシステムがデッドロックに到るのは「満たされない要求の円環」が存在する場合である。例えば、哲学者 P₁ が哲学者 P₂ の手にしているフォークを待っていて、P₂ は哲学者 P₃ のものを……といったように円環形に要求が連鎖する。

タイミングによっては、ある哲学者が両方のフォークを取れない状況がデッドロックとは別に発生する。これをリソーススタベーションと呼ぶ（スタベーションとは「飢餓」であり、この用語も「食事する哲学者の問題」のアナロジーに付随したジョークが起源である）。例えば、一方のフォークを取った状態でもう一方のフォークを5分間待ったら、一旦フォークを置いて5分間待ってから再度食事を試みるという規則を設定する。この方法ではデッドロックは回避される（システムは異なった状態に変化していく）が、ライブロック状態は回避できない。もし5人の哲学者が全く同時に食卓に着いたとしたら、いっせいに左のフォークを取って5分間右のフォークを待ち、左のフォークをいっせいに置いて5分間待つという状況が発生する。

使えるフォークのない状態は、実際のコンピュータプログラミングでは共有リソースのロックされた状態に対応する。リソースのロックは一度にひとつのプログラム（またはコード）だけがそのリソースにアクセスすることを保証する手段である。あるプログラムが欲しいリソースが他のプログラムによってロックされている場合、そのプログラムはアンロックされるのを待つ。複数のプログラムがロックされるリソースに関わる場合、状況によってはデッドロックが発生する。例えば、プログラムが処理をするのにふたつのファイルを必要としているとする。そのような2つのプログラムが各々1つだけファイルをロックしていたら、どちらのプログラムも相手がロックしているファイルを永遠に待ち続けるだろう。

[編集] 解法

[編集] ダイクストラの解法

ひとつの解法は、フォークに順番を付け、哲学者が所定の順番でフォークを手に取るというものである。この解法では、哲学者を P₁, P₂, P₃, P₄, P₅とし、フォークを F₁, F₂, F₃, F₄, F₅ とする。一番目の哲学者(P₁)は一番目のフォーク(F₁)を取ってから二番目のフォーク(F₂)を取る。P₂ から P₄ の哲学者も同様の手順で F_x+1 のフォークを取る前に F_x を取る。ただし、哲学者 P₅ は F₅ のフォークを取る前に F₁ のフォークを取ろうとする。この P₅ の動作の違いが非対称性を生み、デッドロックを回避させる。

スタベーションを防ぐことができるかは、ミューテックスを実現する手法がどうであるかに依存する。スピンロックやビジーウェイトによる実装では、それらの手法が持つタイミング問題によってスタベーションが発生する可能性がある。この問題を優先順位の逆転と呼ぶ。キューなどを利用したミューテックスならば、フォークへのアクセスの平等性が確保され、スタベーションは発生しない。

ダイクストラの解法は任意の哲学者間の衝突に対応するよう拡張可能だが、常にフォークが正しく順番付けされる必要がある。

[編集] Chandy / Misra の解法

1984年、K. M. Chandy と J. Misra は食事する哲学者の問題に別の解法を提案した。それは、任意のエージェント（P₁, ..., P_n）が任意のリソース（R₁, ..., R_m）を獲得しようとする状況に拡張されたものである。ダイクストラの解法とは異なり、順番付けも任意である。彼らはこの一般化された問題を以下のような解法で解決した。

あるリソースを獲得しようとする2人の哲学者の組合せそれぞれについて、フォークを1個生成して識別番号の小さい哲学者に与える。このフォークは dirty と clean の2つの状態があって、初期状態は dirty である。
哲学者がリソースをいくつか組み合わせて使用したい場合（つまり、食事したい場合）、競合している隣人からフォークをもらわなければならない。そのような自分が持っていない全フォークについて要求メッセージを送る。
要求メッセージを受け取ったフォークを持つ哲学者は、持っているフォークが clean なら持ち続けるが、dirty ならそれを手放す。フォークを要求した側に送る際、それを clean 状態にする。
食事が終わると、フォークは dirty 状態になる。他の哲学者がそのフォークを要求したことがあったら、そのフォークを clean 状態にして送る。