食事する哲学者の問題 解法の例

ウィキペディア

食事する哲学者の問題

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/06/04 23:33 UTC 版)

解法の例

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