Javaにおける食事哲学者問題

Posted on: 2019-10-18 2019-11-05
Tags: Algorithms, Java Concurrency

1前書き

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

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

2問題

リンク:/uploads/dp0.png%20662w[]

上の図は問題を表しています。 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

インターフェースを実装するクラスとしてモデル化し、それらを別々のスレッドとして実行できるようにします。それぞれの

Philosopher

は、彼の左右両側にある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
    }

}
私たちには、行動を実行するように

Philosopher

に指示する方法もあります – 食べることに備えてフォークを食べる、考える、または取得する:
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
}
上記のコードに示すように、各アクションは呼び出しスレッドをランダムな時間中断することによってシミュレートされるため、実行順序は時間だけでは強制されません。

それでは、「哲学者」のコアロジックを実装しましょう。

フォークの取得をシミュレートするには、2つの

Philosopher

スレッドが同時にそれを取得しないようにフォークをロックする必要があります。これを実現するために、

これを実現するには、

synchronized

キーワードを使用してforkオブジェクトの内部モニタを取得し、他のスレッドが同じことをしないようにします。 Javaの

synchronized

キーワードの手引きは

ここ

にあります。

Philosopher

クラスに

run（）

メソッドを実装します。
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;
        }
    }
}
この計画はまさに先に述べたものを実装しています。

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

プロセス全体をキックスタートするために、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
すべての

__Philosopher

は最初は思考から始め、

Philosopher 1__が左右のフォークを拾い上げ、それから両方を下に向けて食べ、そしてその後にPhilosopher 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
この状況では、それぞれの

__Philosopher

__は彼の左フォークを獲得しましたが、彼の隣人はすでにそれを獲得したので、彼の右フォークを獲得することはできません。この状況は一般に「循環待機」として知られており、デッドロックを引き起こしてシステムの進行を妨げる条件の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行目にあります。ここでは、最後の哲学者が左ではなく右のフォークに最初に到達する条件を紹介します。これは循環待機状態を破り、デッドロックを回避することができます。

以下の出力は、すべての

__Philosopher

__がデッドロックを引き起こすことなく、考えて食べて食べる機会を得たケースの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. 結論

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

この記事のコードはhttps://github.com/eugenp/tutorials/tree/master/core-java-concurrency[over on GitHub]にあります。