「食事する哲学者の問題」の版間の差分

 

== 問題 ==

 

[[Image:An illustration of the dining philosophers problem.png|thumb|200px|食事する哲学者の問題]]

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

 

 

=== 解説 ===

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

 

 

食事する哲学者の問題は、[[排他制御]]にまつわる様々な問題を説明すべく一般化し抽象化したものである。哲学者らが食事に際して経験する様々な障害は、実際のコンピュータプログラミングで共有リソースに排他的にアクセスする必要がある場合の様々な困難に対応している。これらの問題は[[並行計算]]の分野で研究されている。ダイクストラのもともとの設問は、磁気テープ装置のような外部周辺機器に関するものだった。しかし、食事する哲学者の問題で取り上げられていることは、複数のプロセスが一群のデータを更新しようとしたときに生じる問題として一般化できる。[[オペレーティングシステム]]の[[カーネル]]のように多数のプロセスが並行動作するのを扱うシステムでは、数千の[[ロック (情報工学)|ロック]]や同期機構を使い、[[デッドロック]]、[[リソーススタベーション]]、データ破壊などが起きないようそれら機構の使い方を厳密に守らなければならない。