1. 序章

食事する哲学者の問題は、マルチスレッド環境での同期の問題を説明し、それらを解決するための手法を説明するために使用される古典的な問題の1つです。 Dijkstraは最初にこの問題を定式化し、テープドライブ周辺機器にアクセスするコンピューターに関してそれを提示しました。

現在の定式化は、クイックソートソートアルゴリズムの発明でも知られているTonyHoareによって提供されました。 この記事では、このよく知られた問題を分析し、一般的な解決策をコーディングします。

2. 問題

上の図は問題を表しています。 円形のテーブルの周りに座って、食べたり考えたりして人生を過ごしている5人の静かな哲学者(P1 – P5)がいます。

彼らが共有するための5つのフォーク(1 – 5)があり、食べることができるようにするには、哲学者は両手にフォークを持っている必要があります。 食べた後、彼はそれらの両方を置きます、そしてそれからそれらは同じサイクルを繰り返す別の哲学者によって選ばれることができます。

目標は、哲学者が飢えて死ぬことなく食事と思考の目標を達成するのに役立つスキーム/プロトコルを考え出すことです。

3. 解決策

最初の解決策は、各哲学者を次のプロトコルに従わせることです。

while(true) { 
    // Initially, thinking about life, universe, and everything
    think();

    // Take a break from thinking, hungry now
    pick_up_left_fork();
    pick_up_right_fork();
    eat();
    put_down_right_fork();
    put_down_left_fork();

    // Not hungry anymore. Back to thinking!
}

上記の擬似コードが説明しているように、各哲学者は最初に考えています。 一定の時間が経過すると、哲学者は空腹になり、食べたいと思うようになります。

この時点で、彼はどちらかの側のフォークに手を伸ばし、両方を手に入れたら、を食べ始めます。 食事が終わったら、哲学者はフォークを下に置き、隣人が利用できるようにします。

4. 実装

各哲学者をRunnableインターフェイスを実装するクラスとしてモデル化して、別々のスレッドとして実行できるようにします。 各哲学者は、左側と右側の2つのフォークにアクセスできます。

public class Philosopher implements Runnable {

    // The forks on either side of this Philosopher 
    private Object leftFork;
    private Object rightFork;

    public Philosopher(Object leftFork, Object rightFork) {
        this.leftFork = leftFork;
        this.rightFork = rightFork;
    }

    @Override
    public void run() {
        // Yet to populate this method
    }

}

哲学者にアクションを実行するように指示する方法もあります–食べる、考える、または食べる準備としてフォークを取得する:

public class Philosopher implements Runnable {

    // Member variables, standard constructor

    private void doAction(String action) throws InterruptedException {
        System.out.println(
          Thread.currentThread().getName() + " " + action);
        Thread.sleep(((int) (Math.random() * 100)));
    }

    // Rest of the methods written earlier
}

上記のコードに示されているように、各アクションは、呼び出しスレッドをランダムな時間中断することによってシミュレートされるため、実行順序は時間だけで強制されることはありません。

それでは、Philosopherのコアロジックを実装しましょう。

フォークの取得をシミュレートするには、2つのPhilosopherスレッドが同時にフォークを取得しないようにロックする必要があります。

これを実現するために、 synchronized キーワードを使用して、フォークオブジェクトの内部モニターを取得し、他のスレッドが同じことを行わないようにします。 Javaのsynchronizedキーワードのガイドは、こちらにあります。 ここで、[X63X] run()メソッドをPhilosopherクラスに実装します。

public class Philosopher implements Runnable {

   // Member variables, methods defined earlier

    @Override
    public void run() {
        try {
            while (true) {
                
                // thinking
                doAction(System.nanoTime() + ": Thinking");
                synchronized (leftFork) {
                    doAction(
                      System.nanoTime() 
                        + ": Picked up left fork");
                    synchronized (rightFork) {
                        // eating
                        doAction(
                          System.nanoTime() 
                            + ": Picked up right fork - eating"); 
                        
                        doAction(
                          System.nanoTime() 
                            + ": Put down right fork");
                    }
                    
                    // Back to thinking
                    doAction(
                      System.nanoTime() 
                        + ": Put down left fork. Back to thinking");
                }
            }
        } catch (InterruptedException e) {
            Thread.currentThread().interrupt();
            return;
        }
    }
}

このスキームは、前述のスキームを正確に実装しています。 Philosopher はしばらく考えてから、食べることにします。

この後、彼は左右のフォークを手に入れて食べ始めます。 終わったら、彼はフォークを下に置きます。 また、各アクションにタイムスタンプを追加します。これは、イベントが発生する順序を理解するのに役立ちます。

プロセス全体を開始するために、5つの Philosophers をスレッドとして作成し、それらすべてを開始するクライアントを作成します。

public class DiningPhilosophers {

    public static void main(String[] args) throws Exception {

        Philosopher[] philosophers = new Philosopher[5];
        Object[] forks = new Object[philosophers.length];

        for (int i = 0; i < forks.length; i++) {
            forks[i] = new Object();
        }

        for (int i = 0; i < philosophers.length; i++) {
            Object leftFork = forks[i];
            Object rightFork = forks[(i + 1) % forks.length];

            philosophers[i] = new Philosopher(leftFork, rightFork);
            
            Thread t 
              = new Thread(philosophers[i], "Philosopher " + (i + 1));
            t.start();
        }
    }
}

各フォークを汎用Javaオブジェクトとしてモデル化し、哲学者の数だけ作成します。 哲学者同期キーワードを使用してロックしようとする左右のフォークを渡します。

このコードを実行すると、次のような出力になります。 sleep()メソッドが異なる間隔で呼び出されることが主な理由で、出力は以下に示すものとは異なる可能性があります。

Philosopher 1 8038014601251: Thinking
Philosopher 2 8038014828862: Thinking
Philosopher 3 8038015066722: Thinking
Philosopher 4 8038015284511: Thinking
Philosopher 5 8038015468564: Thinking
Philosopher 1 8038016857288: Picked up left fork
Philosopher 1 8038022332758: Picked up right fork - eating
Philosopher 3 8038028886069: Picked up left fork
Philosopher 4 8038063952219: Picked up left fork
Philosopher 1 8038067505168: Put down right fork
Philosopher 2 8038089505264: Picked up left fork
Philosopher 1 8038089505264: Put down left fork. Back to thinking
Philosopher 5 8038111040317: Picked up left fork

すべての哲学者は最初に考え始め、哲学者1 が左右のフォークを拾い上げ、次に食べて両方を下に置きます。 「哲学者5」がそれを取り上げます。

5. ソリューションの問題:デッドロック

上記の解決策は正しいように見えますが、デッドロックが発生するという問題があります。

デッドロックとは、各プロセスが他のプロセスによって保持されているリソースの取得を待機しているために、システムの進行が停止する状況です。

上記のコードを数回実行し、コードがハングすることを確認することで、同じことを確認できます。 上記の問題を示すサンプル出力は次のとおりです。

Philosopher 1 8487540546530: Thinking
Philosopher 2 8487542012975: Thinking
Philosopher 3 8487543057508: Thinking
Philosopher 4 8487543318428: Thinking
Philosopher 5 8487544590144: Thinking
Philosopher 3 8487589069046: Picked up left fork
Philosopher 1 8487596641267: Picked up left fork
Philosopher 5 8487597646086: Picked up left fork
Philosopher 4 8487617680958: Picked up left fork
Philosopher 2 8487631148853: Picked up left fork

この状況では、哲学者のそれぞれが左フォークを取得していますが、隣人がすでに取得しているため、右フォークを取得できません。 この状況は一般に循環待機として知られており、デッドロックが発生してシステムの進行を妨げる状態の1つです。

6. デッドロックの解決

上で見たように、デッドロックの主な理由は、各プロセスが他のプロセスによって保持されているリソースを待機する循環待機条件です。 したがって、デッドロック状態を回避するには、循環待機条件が解除されていることを確認する必要があります。 これを実現するにはいくつかの方法がありますが、最も簡単な方法は次のとおりです。

最初に右のフォークに手を伸ばす人を除いて、すべての哲学者は最初に左のフォークに手を伸ばします。

コードに比較的小さな変更を加えることで、既存のコードにこれを実装します。

public class DiningPhilosophers {

    public static void main(String[] args) throws Exception {

        final Philosopher[] philosophers = new Philosopher[5];
        Object[] forks = new Object[philosophers.length];

        for (int i = 0; i < forks.length; i++) {
            forks[i] = new Object();
        }

        for (int i = 0; i < philosophers.length; i++) {
            Object leftFork = forks[i];
            Object rightFork = forks[(i + 1) % forks.length];

            if (i == philosophers.length - 1) {
                
                // The last philosopher picks up the right fork first
                philosophers[i] = new Philosopher(rightFork, leftFork); 
            } else {
                philosophers[i] = new Philosopher(leftFork, rightFork);
            }
            
            Thread t 
              = new Thread(philosophers[i], "Philosopher " + (i + 1));
            t.start();
        }
    }
}

変更は、上記のコードの17〜19行目にあります。ここでは、最後の哲学者が左ではなく右のフォークに最初に到達する条件を導入しています。 これにより、循環待機状態が解消され、デッドロックを回避できます。

次の出力は、すべての哲学者がデッドロックを引き起こすことなく考えて食べる機会を得たケースの1つを示しています。

Philosopher 1 88519839556188: Thinking
Philosopher 2 88519840186495: Thinking
Philosopher 3 88519840647695: Thinking
Philosopher 4 88519840870182: Thinking
Philosopher 5 88519840956443: Thinking
Philosopher 3 88519864404195: Picked up left fork
Philosopher 5 88519871990082: Picked up left fork
Philosopher 4 88519874059504: Picked up left fork
Philosopher 5 88519876989405: Picked up right fork - eating
Philosopher 2 88519935045524: Picked up left fork
Philosopher 5 88519951109805: Put down right fork
Philosopher 4 88519997119634: Picked up right fork - eating
Philosopher 5 88519997113229: Put down left fork. Back to thinking
Philosopher 5 88520011135846: Thinking
Philosopher 1 88520011129013: Picked up left fork
Philosopher 4 88520028194269: Put down right fork
Philosopher 4 88520057160194: Put down left fork. Back to thinking
Philosopher 3 88520067162257: Picked up right fork - eating
Philosopher 4 88520067158414: Thinking
Philosopher 3 88520160247801: Put down right fork
Philosopher 4 88520249049308: Picked up left fork
Philosopher 3 88520249119769: Put down left fork. Back to thinking

コードを数回実行することで、システムが以前に発生したデッドロック状態から解放されていることを確認できます。

7. 結論

この記事では、有名な食事する哲学者の問題と循環待機とデッドロックの概念について説明しました。 デッドロックを引き起こす単純なソリューションをコーディングし、循環待機を中断してデッドロックを回避するための単純な変更を行いました。 これはほんの始まりに過ぎず、より洗練されたソリューションが存在します。

この記事のコードは、GitHubにあります。