食事する哲学者の問題

食事する哲学者の問題（Dining Philosophers Problem）とは、並列処理に関する問題を一般化した例である。古典的なマルチプロセスの同期（排他制御）問題であり、大学レベルの計算機科学課程にはほぼ確実に含まれている。
1965年、エドガー・ダイクストラは5台のコンピュータが5台のテープ装置に競合アクセスするという同期問題を提示した。間もなく、この問題はアントニー・ホーアによって「食事する哲学者の問題」に変形して語られることとなった。

問題

5人の哲学者が食事したり、考え事をしたりしている。かれらの前には、真ん中にスパゲッティの入った大きなボールが置かれた丸い食卓がある。その食卓には5枚の皿が置かれ、皿と皿の間にフォークが1本ずつ置かれている。
近年では、食器を「フォーク」ではなく「箸」として紹介する例が増えている。箸ならば、「1人が2本確保しなければ食事ができない」という制限がより自然である。本稿では古い形式のまま、スパゲティーを2本のフォークで食べる、とした設定のまま解説する。
スパゲッティをボールから取って自分の皿によそうには2本のフォークを必要とし、哲学者は一度に1本のフォークしかテーブルから取ることができない（左右の手で同時に両側にある2本のフォークを取ることはできない、という意味。まずどちらかの側のフォークを取ってから、逆の側のフォークを取る）。哲学者同士は決して会話をしない。このため、5人が左のフォークを手にとって右のフォークが食卓に置かれるのを待つという危険なデッドロック状態が発生する可能性がある。
問題はどのように行動の規律を設定すれば（並行性アルゴリズム）、それぞれの哲学者が飢えずに済むか、すなわち食事と思索を永遠に続けられるか、である。

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

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

ウェイターを配する解法

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

解法の例

次のコードは、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]);
        }
    }}