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

削除された内容追加された内容

インライン

2020年7月5日 (日) 22:46時点における版

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

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

問題

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

近年では、食器を「フォーク」ではなく「箸」として紹介する例も見られる^[4]。箸ならば、「1人が2本確保しなければ食事ができない」という制限が少しは自然だが、箸は1本ずつ分けて左右に置くものではないという点では却って不自然さが増しており、海外の文献でも日本通の著者などがそのように言及していることもある。本稿では古い形式のまま、スパゲティーを2本のフォークで食べる、とした設定のまま解説する。

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

デッドロックの可能性は、このモデルで示せるわかりやすい問題だが、それ以外にも解決が必要な点は指摘できる。たとえばデッドロックを回避できる簡単な解だが有用性の無いものに、常に固定された隣り合わない2人の哲学者（5人の場合）だけが食事できる、というものがある。これは公平性が無く、残りの食事できない哲学者の観点からは飢餓の問題でもある。1個だけのトークンを用意し、常に交代で１人だけが食事できる、という手法は確実な解ではあるが効率が悪い（並列処理の問題として見た場合、並列処理が可能であるにもかかわらず、それが活用されない）。といったように、さまざまな角度から検討できる。

解説

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

例えば、それぞれの哲学者が次のように振る舞うとする。

左のフォークが得られるまで思索して待ち、フォークを取り上げる。
右のフォークが得られるまで思索して待ち、フォークを取り上げる。
食事する。
右のフォークを置く。
左のフォークを置く。
最初にもどって繰り返す。

この解法は正しくない。このやりかたではデッドロックが発生し、全哲学者が左のフォークを持ち、右のフォークが持てるようになるのを待つという状況が発生しうる（その場合、右のフォークは決して得られない）^[5]。

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

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

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

解法

哲学者の位置により右手か左手を優先する解法

この解法では、哲学者の人数が偶数人であるという大前提を置く（人数が奇数の場合には適用できない）。哲学者を「グループEven」と「グループOdd」の2グループに分類し、隣どうしの哲学者は必ず違うグループになるようにする（この分類は偶数でなければできない）。そして、「グループEven」の哲学者は必ず先に右のフォークを取ろうとするものとし、「グループOdd」は先に必ず左から、とする。そのようにすると依存関係の循環は存在しないため、問題は発生しなくなる。

ウェイターを配する解法

比較的単純な解法は、食卓にウェイターを配置することでなされる。哲学者らはフォークを手に取る際に必ずウェイターの許可を取ることとする。ウェイターはどのフォークが使われているかを把握しているので、デッドロックを防ぐよう調停することができる。4本のフォークが使用中のとき、最後のフォークを哲学者が要求した場合、ウェイターが許可するのを待つ必要があり、使用中のフォークが解放されるまで許可は与えられない。哲学者が常に右のフォークより先に左のフォークをとる（あるいは逆）よう決めておけば、話は単純化される。ウェイターはセマフォと呼ばれるダイクストラが1965年に導入した概念のように振る舞う^[6]。

具体的に説明するため、哲学者を時計回りにAからEまでラベル付けする。AとCが食事中で、4本のフォークが使われているとする。BはAとCの間に座っているので、どちらのフォークも入手できないのに対し、DとEの間には未使用のフォークが1本残っている。ここでDが食事したいとする。彼が5番目のフォークを取ると、デッドロックが発生する可能性がある。そこでDがウェイターにフォークをとってもよいか尋ね、待つよう命じられれば、AかCが食事を終えてフォークを置いたとき、少なくとも1人の哲学者が両手にフォークを持つことができることが確実となる。したがって、デッドロックは起きない。

リソース階層による解法

もう1つの単純な解法は、リソース（この場合はフォーク）に半順序を割り当てる方法で、リソースの要求順序は常にリソースの順序の通りに行い、リソース解放はその逆の順序に行う。そして、順序的に無関係なリソースをあるユニットが同時に使うことはないとする。リソース（フォーク）に1から5までの番号を付与し、動作ユニット（哲学者）は常に番号の小さい方のフォークを先にとり、それから番号の大きい方のフォークをとる。個々の哲学者がとるフォークの番号は決まっている。そして、フォークを置く場合は番号の大きい方を先に置き、それから番号の小さい方のフォークを置く。この場合、5人の哲学者のうち4人が同時に番号の小さい方のフォークをとると、番号の一番大きいフォークだけが残ることになり、5番目の哲学者はフォークをとることができない。さらに、その番号が一番大きいフォークをとれる哲学者は1人しかいないため、その哲学者だけが両方のフォークを持って食事できる。彼が食事を終えてフォークを置くとき、まず番号の大きい方から置き、続いて番号の小さい方のフォークを置くので、後者のフォークを待っていた哲学者がそのフォークをとって食事を始められるようになる。

この解法はダイクストラが最初に提案したものの1つである。

リソース階層を使った解法はデッドロックを防げるが、常に実用的とは言えず、特に必要とされるリソースが最初から全部把握できない場合には有効ではない。例えば、ある動作ユニットが3番と5番のリソースを持っていて、さらに2番のリソースが必要になったとき、リソース獲得順序を守るために5番と3番のリソースを一旦解放しないと2番のリソースを獲得できない。そうしてから3番、5番という順序で獲得し直す。データベースの多数のレコードにアクセスするコンピュータプログラムがあった場合、新たなレコードにアクセスするために番号の大きいレコードを全て一旦解放しなければならないとしたら、あまり効率的に動作できないだろう。

モニタを使った解法

下のコード例で示した解法では、フォークが明示的に出てこない。哲学者は両隣の哲学者が食事中でないときだけ食事できる。これはつまり、2本目のフォークを取れない哲学者は必ずフォークを一旦置いて待ち、改めて1本目から試行するという方式である。

フォークごとのロックがないため、哲学者は両隣の哲学者の状態に基づいて食事を開始するかを決めなければならないが、その状態情報が古くないことを保証する必要がある。哲学者2が哲学者1が食事していないことを確認し、次に哲学者3を見るとしたとき、1は2が3を見ている間に食事を始めるかもしれない。この解法ではそのような状況を防ぐため、単一の相互排他ロックを使う。これは特定のフォークに結びついたものではなく、哲学者らの状態を変更する手続きそのものに対応したものである。それがモニタという機構である。手続き test、pickup、putdown はモニタに結びついており、1つの相互排他ロックを共有する。食事できるようになるのを待っている哲学者はフォークを持ってはいない点に注意が必要である。食事したい哲学者がいると、モニタは1つ目のフォークを手放させ、2本目も入手可能になった時点で1本目から再試行させる。食事が終わったら、哲学者はモニタにシグナルを送り、両方のフォークが利用可能な状態になったことを知らせる。

なお、例に挙げたコードではリソーススタベーションを防げない。例えば、1番と3番の哲学者が食事する期間が常にオーバーラップしていると、2番の哲学者はずっと食事できないことになる。

スタベーションを防ぐには、空腹な哲学者が食事できなかった回数を保持し、それがある限度を越えた場合に哲学者の状態を Hungry から Starving に変更する。そして、フォークを与えるかどうかを判断する際に両隣がどちらも Starving でないことという条件を加える必要がある。

どちらかの隣人が Starving だったために食事できなかった哲学者は、事実上その隣人の隣人が食事を終えるのを待つことになる。このように依存関係が追加されることで並行性が減っていく。Starving とするしきい値を大きくすれば、そのような影響を抑えることができる。

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 状態にして送る。

この解法は大規模な並列実行でも適用可能である。

スタベーション問題も解決できる。clean と dirty のラベルは、最も長く食事にありつけていないプロセスを優先し、最近食事したプロセスの優先順位を下げる効果がある。哲学者がフォークを手放さずに2回続けて食事できないという規定を設けた解法と比べてみると、上に述べた解法の方が柔軟だが、傾向は後者と同じだということがわかる。

この分析から、彼らはフォークの配布とそのclean/dirty状態による優先レベルのシステムを導き出した。彼らはこのシステムを非環状グラフで表せるかもしれないとし、もしそうなら、その動作は環状グラフに変換できないことになる。それは、デッドロックが起きないことを保証しているのと等しい。しかし、システムが最初に完全に対称な状態（例えば、哲学者が全員左のフォークを持っている状態）に初期化される場合、グラフは最初から環状になり、デッドロックを防ぐことができない。小さい識別番号の哲学者がdirty状態のフォークを持つよう初期化することで、初期状態を非環状グラフにできる。

解法の例

次のコードは、Pascalで書かれた解法の例である（モニタを使用）。

PROGRAM d_p;
   CONST
      DoomsDay = FALSE;

   MONITOR dining_philosophers;  // モニタ宣言開始
      CONST
         Eating   = 0;   
         Hungry   = 1;
         Thinking = 2;
      VAR
         i       : INTEGER; // ループ変数初期化
         state   : ARRAY [0..4] OF INTEGER; // Eating、Hungry、Thinking
         can_eat : ARRAY [0..4] OF CONDITION; // 哲学者それぞれに対応
         // 箸がそろうまで、空腹の哲学者を置く

      PROCEDURE test(k : INTEGER);
      BEGIN
         IF (state[k] = Hungry)
            AND (state[(k+4) MOD 5] <> Eating)
            AND (state[(k+1) MOD 5] <> Eating) THEN
         BEGIN
            state[k] := Eating;
            SIGNALC(can_eat[k]); // 待ち状態の者がいればその状態を終了させる
         END; 
      END; 

      PROCEDURE pickup(i: INTEGER);
      BEGIN
         state[i] := Hungry;
         WRITELN('philosopher ',i,' hungry');
         test(i); // 隣の人は食事中か? 
         IF state[i] <> Eating THEN
            WAITC(can_eat[i]);  // 隣人の食事が終わるまで待つ
         WRITELN('philosopher ',i,' eating');
      END; 

      PROCEDURE putdown(i : INTEGER);
      BEGIN
         state[i] := Thinking;
         WRITELN('philosopher ',i,' thinking');
         test( (i+4) MOD 5); // 左の隣人が食事するチャンスを与える
         test( (i+1) MOD 5); // 右の隣人が食事するチャンスを与える
      END;  

   BEGIN // モニタを初期化
      FOR i := 0 TO 4 DO state[i] := Thinking;
   END;  // モニタ定義の終わり

   PROCEDURE philosopher(i : INTEGER);
   BEGIN
      REPEAT
         pickup(i);  // 箸をとる
         putdown(i); // 箸をおく
      UNTIL DoomsDay;
   END; 

BEGIN // 主プログラム
   COBEGIN  // 5つのプロセスを同時に開始
      philosopher(0); philosopher(1); philosopher(2);
      philosopher(3); philosopher(4);
   COEND;
END

次のコードは、Javaで書かれた解法の例である（セマフォを使用）。

import java.util.concurrent.Semaphore;
import java.util.Random;
import java.util.Vector;

public class Philosopher extends Thread
{
    private static final Random rand = new Random();
    private static int event=0;
    private static String binary="";
    private int id;
    private Semaphore sem;
    private static Vector<Object[]> vector = new Vector<Object[]>();

    public Philosopher(int i, Semaphore s)
    {
        id = i;
        sem = s;
        binary = binary + "0";
    }

    private void busy()
    {
        try
        {
            sleep(rand.nextInt(1000));
        } catch (InterruptedException e){}
    }

    private void thinking()
    {
        String str = "Philosopher " + id + " is thinking";
        vector.add( this.addToObject(System.currentTimeMillis(), event , str) );
        event++;
        busy();
    }

    private void eating()
    {
        String str ="Philosopher " + id + " is hungry and is trying to pick up his chopsticks";
        vector.add( this.addToObject(System.currentTimeMillis(), event , str) );
        event++;
        busy();
        str = "Philosopher " + id + " is eating";
        this.oneToBinary(id);
        vector.add( this.addToObject(System.currentTimeMillis(), event , str) );
        event++;
        busy();
        str = "Philosopher " + id + " finished eating, and puts away his chopsticks";
        this.zeroToBinary(id);
        vector.add( this.addToObject(System.currentTimeMillis(), event , str) );
        event++;
    }

    private Object[] addToObject(long t, int i,String s ){
        Object[] o = new Object[4];
        o[3] = s;
        o[2] = i;
        o[1] = binary;
        o[0] = t;
        return o;
    }

    private void oneToBinary(int i){
        binary = binary.substring(0,i) + "1" + binary.substring(i+1);
    }

    private void zeroToBinary(int i){
        binary = binary.substring(0,i) + "0" + binary.substring(i+1);
    }

    @Override
    public void run()
    {
        for (int i = 0; i < 10; ++i)
        {
            thinking();
            try
            {
                sem.acquire();
            } catch (InterruptedException e){}
            eating();
            sem.release();
        }
    }

    public static void main(String[] args)
    {
        final int N = 5;
        Semaphore sem = new Semaphore(N, true);
        Philosopher[] philosopher = new Philosopher[N];

        // 哲学者を生成
        for (int i = 0; i < N; i++) {
          philosopher[i] = new Philosopher(i, sem);
          philosopher[i].start();
        }
        // 完了を待ち合わせる
        for (int i = 0; i < N; i++) {
          try {
            philosopher[i].join();
          } catch(InterruptedException ex) {
            return;
          }
        }

        for (int i = 0; i < vector.size(); i++) {
            Object[] o = vector.get(i);
            System.out.printf("%d %d %s %s\n", o[0], o[2], o[1], o[3]);
        }
    }
}

脚注

^ Dijkstra, Edsger W. EWD-1000. E.W. Dijkstra Archive. Center for American History, University of Texas at Austin. (original; transcription)
^ J. Díaz; I. Ramos (1981). Formalization of Programming Concepts: International Colloquium, Peniscola, Spain, April 19–25, 1981. Proceedings. Birkhäuser. pp. 323 , 326. ISBN 978-3-540-10699-9
^ Hoare, C. A. R. (2004年). “Communicating Sequential Processes”. usingcsp.com (originally published in 1985 by Prentice Hall International). 2012年7月16日閲覧。
^ 海外での例
^ Dijkstra, Edsger W. EWD-310. E.W. Dijkstra Archive. Center for American History, University of Texas at Austin. (original; transcription)
^ Dijkstra, Edsger W. EWD-123. E.W. Dijkstra Archive. Center for American History, University of Texas at Austin. (original; transcription)

参考文献

Silberschatz, Abraham; Peterson, James L. (1988). Operating Systems Concepts. Addison-Wesley. ISBN 0-201-18760-4
Chandy, K.M.; Misra, J. (1984). The Drinking Philosophers Problem. ACM Transactions on Programming Languages and Systems.
Dijkstra, E. W. (1971, June). Hierarchical ordering of sequential processes. Acta Informatica 1(2): 115–138.
Lehmann, D. J., Rabin M. O, (1981). On the Advantages of Free Choice: A Symmetric and Fully Distributed Solution to the Dining Philosophers Problem. Principles Of Programming Languages 1981 (POPL'81), pp. 133–138.

外部リンク

食事する哲学者の問題（Javaアプレット）（英語）（フランス語）（ドイツ語）
食事する哲学者
哲学者たちの食事
ObjectClub - diningPhilosopher
Discussion of the problem with solution code for 2 or 4 philosophers
Discussion of various solutions 1
Discussion of various solutions 2
Discussion of a solution using continuation based threads (cbthreads)
Distributed symmetric solutions
Programming the Dining Philosophers with Simulation
Interactive example of the Philosophers problem （Javaアプレット）
Satan Comes to Dinner
Wot No Chickens?
ThreadMentor
Solving The Dining Philosophers Problem With Asynchronous Agents
Rosetta Code: Dining philosophers - 各種言語での実装例

[1] Dijkstra, Edsger W. EWD-1000. E.W. Dijkstra Archive. Center for American History, University of Texas at Austin. (original; transcription)

[2] J. Díaz; I. Ramos (1981). Formalization of Programming Concepts: International Colloquium, Peniscola, Spain, April 19–25, 1981. Proceedings. Birkhäuser. pp. 323 , 326. ISBN 978-3-540-10699-9

[3] Hoare, C. A. R. (2004年). “Communicating Sequential Processes”. usingcsp.com (originally published in 1985 by Prentice Hall International). 2012年7月16日閲覧。

[4] 海外での例

[5] Dijkstra, Edsger W. EWD-310. E.W. Dijkstra Archive. Center for American History, University of Texas at Austin. (original; transcription)

[6] Dijkstra, Edsger W. EWD-123. E.W. Dijkstra Archive. Center for American History, University of Texas at Austin. (original; transcription)

[1]

[2]

[3]

[4]

[5]

[6]

@@ 78行目: / 78行目: @@
 次のコードは、[[Pascal]]で書かれた解法の例である（[[モニタ (同期)|モニタ]]を使用）。
-<source lang="pascal">
+<syntaxhighlight lang="pascal">
 PROGRAM d_p;
    CONST
@@ 141行目: / 141行目: @@
    COEND;
 END
+</syntaxhighlight>
-</source>
 次のコードは、Javaで書かれた解法の例である（[[セマフォ]]を使用）。
-<source lang="java">
+<syntaxhighlight lang="java">
 import java.util.concurrent.Semaphore;
@@ 259行目: / 259行目: @@
 }
+</syntaxhighlight>
-</source>
 == 脚注 ==