logo

TechCodeview

ダイニング哲学者の問題

食事の哲学者の問題は、5 人の哲学者が円形のテーブルの周りに座っており、彼らの仕事は交互に考え、食事をすることであるという古典的な同期の問題です。テーブルの中央には麺の入った丼が置かれ、哲学者ごとに 5 本の箸が置かれます。哲学者が食事をするには、右と左の両方の箸が必要です。哲学者は、哲学者のすぐ左と右の両方の箸が利用可能な場合にのみ食事をすることができます。哲学者のすぐ左と右の両方の箸が利用できない場合、哲学者は（左または右の）箸を置き、再び考え始めます。

食事の哲学者は、大規模な同時実行制御の問題を実証しているため、これは古典的な同期の問題です。

Javaはファイルを1行ずつ読み取ります
ダイニング哲学者の問題

テーブルを囲んで座る5人の哲学者

ダイニング哲学者の問題 - 以下のコードで食事の哲学者問題を理解しましょう。問題を正確に理解するために図 1 を参照として使用しました。 5 人の哲学者は P0、P1、P2、P3、P4 で表され、5 本の箸は C0、C1、C2、C3、C4 で表されます。

ダイニング哲学者の問題 
 Void Philosopher { while(1) { take_chopstick[i]; take_chopstick[ (i+1) % 5] ; . . . EATING THE NOODLE . put_chopstick[i] ); put_chopstick[ (i+1) % 5] ; . . THINKING } }

上記のコードについて説明しましょう。

Philosopher P0 が食事をしたいとすると、Philosopher() 関数に入り、実行されます。 take_chopstick[i]; これを行うことで、それは保持されます C0箸 その後実行されます take_chopstick[ (i+1) % 5]; これを行うことで、それは保持されます C1箸 ( i =0 なので (0 + 1) % 5 = 1)

同様に、Philosopher P1 が食事をしたいとすると、Philosopher() 関数に入り、実行されます。 take_chopstick[i]; これを行うことで、それは保持されます C1箸 その後実行されます take_chopstick[ (i+1) % 5]; これを行うことで、それは保持されます C2箸 (i =1 なので、(1 + 1) % 5 = 2)

しかし、実際には Chopstick C1 は哲学者 P0 によってすでに使用されているため利用できません。そのため、上記のコードでは問題が発生し、競合状態が発生します。

ダイニング哲学者問題の解決策

箸を表すためにセマフォを使用します。これはまさに食事の哲学者問題の解決策として機能します。食事の哲学者問題の解決には、待機操作と合図操作が使用されます。箸を選ぶ場合は待機操作を実行し、箸を放す場合は合図セマフォを実行できます。

セマフォ: セマフォは S の整数変数であり、初期化とは別に 2 つの標準アトミック操作 (wait と signal) によってのみアクセスされます。その定義は次のとおりです。

 1. wait( S ) { while( S <= 0) ; s--; } 2. signal( s ) { s++; < pre> <p>From the above definitions of wait, it is clear that if the value of S <= 0 then it will enter into an infinite loop(because of the semicolon; after while loop). whereas job signal is to increment value s.< p> <p>The structure of the chopstick is an array of a semaphore which is represented as shown below -</p> <pre> semaphore C[5]; </pre> <p>Initially, each element of the semaphore C0, C1, C2, C3, and C4 are initialized to 1 as the chopsticks are on the table and not picked up by any of the philosophers.</p> <p>Let&apos;s modify the above code of the Dining Philosopher Problem by using semaphore operations wait and signal, the desired code looks like</p> <pre> void Philosopher { while(1) { Wait( take_chopstickC[i] ); Wait( take_chopstickC[(i+1) % 5] ) ; . . . EATING THE NOODLE . Signal( put_chopstickC[i] ); Signal( put_chopstickC[ (i+1) % 5] ) ; . . THINKING } } </pre> <p>In the above code, first wait operation is performed on take_chopstickC[i] and take_chopstickC [ (i+1) % 5]. This shows philosopher i have picked up the chopsticks from its left and right. The eating function is performed after that.</p> <p>On completion of eating by philosopher i the, signal operation is performed on take_chopstickC[i] and take_chopstickC [ (i+1) % 5]. This shows that the philosopher i have eaten and put down both the left and right chopsticks. Finally, the philosopher starts thinking again.</p> <h3>Let&apos;s understand how the above code is giving a solution to the dining philosopher problem?</h3> <p>Let value of i = 0( initial value ), Suppose Philosopher P0 wants to eat, it will enter in Philosopher() function, and execute <strong>Wait( take_chopstickC[i] );</strong> by doing this it holds <strong>C0 chopstick</strong> and reduces semaphore C0 to 0 <strong>,</strong> after that it execute <strong>Wait( take_chopstickC[(i+1) % 5] );</strong> by doing this it holds <strong>C1 chopstick</strong> ( since i =0, therefore (0 + 1) % 5 = 1) and reduces semaphore C1 to 0</p> <p>Similarly, suppose now Philosopher P1 wants to eat, it will enter in Philosopher() function, and execute <strong>Wait( take_chopstickC[i] );</strong> by doing this it will try to hold <strong>C1 chopstick</strong> but will not be able to do that <strong>,</strong> since the value of semaphore C1 has already been set to 0 by philosopher P0, therefore it will enter into an infinite loop because of which philosopher P1 will not be able to pick chopstick C1 whereas if Philosopher P2 wants to eat, it will enter in Philosopher() function, and execute <strong>Wait( take_chopstickC[i] );</strong> by doing this it holds <strong>C2 chopstick</strong> and reduces semaphore C2 to 0, after that, it executes <strong>Wait( take_chopstickC[(i+1) % 5] );</strong> by doing this it holds <strong>C3 chopstick</strong> ( since i =2, therefore (2 + 1) % 5 = 3) and reduces semaphore C3 to 0.</p> <p>Hence the above code is providing a solution to the dining philosopher problem, A philosopher can only eat if both immediate left and right chopsticks of the philosopher are available else philosopher needs to wait. Also at one go two independent philosophers can eat simultaneously (i.e., philosopher <strong>P0 and P2, P1 and P3 &amp; P2 and P4</strong> can eat simultaneously as all are the independent processes and they are following the above constraint of dining philosopher problem)</p> <h3>The drawback of the above solution of the dining philosopher problem</h3> <p>From the above solution of the dining philosopher problem, we have proved that no two neighboring philosophers can eat at the same point in time. The drawback of the above solution is that this solution can lead to a deadlock condition. This situation happens if all the philosophers pick their left chopstick at the same time, which leads to the condition of deadlock and none of the philosophers can eat.</p> <p>To avoid deadlock, some of the solutions are as follows -</p> <ul> <li>Maximum number of philosophers on the table should not be more than four, in this case, chopstick C4 will be available for philosopher P3, so P3 will start eating and after the finish of his eating procedure, he will put down his both the chopstick C3 and C4, i.e. semaphore C3 and C4 will now be incremented to 1. Now philosopher P2 which was holding chopstick C2 will also have chopstick C3 available, hence similarly, he will put down his chopstick after eating and enable other philosophers to eat.</li> <li>A philosopher at an even position should pick the right chopstick and then the left chopstick while a philosopher at an odd position should pick the left chopstick and then the right chopstick.</li> <li>Only in case if both the chopsticks ( left and right ) are available at the same time, only then a philosopher should be allowed to pick their chopsticks</li> <li>All the four starting philosophers ( P0, P1, P2, and P3) should pick the left chopstick and then the right chopstick, whereas the last philosopher P4 should pick the right chopstick and then the left chopstick. This will force P4 to hold his right chopstick first since the right chopstick of P4 is C0, which is already held by philosopher P0 and its value is set to 0, i.e C0 is already 0, because of which P4 will get trapped into an infinite loop and chopstick C4 remains vacant. Hence philosopher P3 has both left C3 and right C4 chopstick available, therefore it will start eating and will put down its both chopsticks once finishes and let others eat which removes the problem of deadlock.</li> </ul> <p>The design of the problem was to illustrate the challenges of avoiding deadlock, a deadlock state of a system is a state in which no progress of system is possible. Consider a proposal where each philosopher is instructed to behave as follows:</p> <ul> <li>The philosopher is instructed to think till the left fork is available, when it is available, hold it.</li> <li>The philosopher is instructed to think till the right fork is available, when it is available, hold it.</li> <li>The philosopher is instructed to eat when both forks are available.</li> <li>then, put the right fork down first</li> <li>then, put the left fork down next</li> <li>repeat from the beginning.</li> </ul> <hr></=></p></=>

最初に、箸がテーブルの上にあり、どの哲学者も持ち上げていないため、セマフォ C0、C1、C2、C3、および C4 の各要素は 1 に初期化されます。

JavaScript 演算子

セマフォ操作 wait と signal を使用して、上記のダイニング哲学者問題のコードを変更してみましょう。目的のコードは次のようになります。

 void Philosopher { while(1) { Wait( take_chopstickC[i] ); Wait( take_chopstickC[(i+1) % 5] ) ; . . . EATING THE NOODLE . Signal( put_chopstickC[i] ); Signal( put_chopstickC[ (i+1) % 5] ) ; . . THINKING } }

上記のコードでは、最初の wait 操作が take_chopstickC[i] と take_chopstickC [ (i+1) % 5] に対して実行されます。これは哲学者が箸を左右から持ち上げたことを示しています。その後、食事の機能が実行されます。

哲学者 i の食事が完了すると、take_chopstickC[i] と take_chopstickC [(i+1)%5] に対してシグナル操作が行われます。これは、哲学者が左右両方の箸を食べて置いたことを示しています。最後に、哲学者は再び考え始めます。

上記のコードがどのようにして食事の哲学者問題の解決策を与えているのかを理解しましょう。

i の値を 0(初期値) として、Philosopher P0 が食べたいとすると、Philosopher() 関数に入って実行します。 待ちます( take_chopstickC[i] ); これを行うことで、それは保持されます C0箸 そしてセマ​​フォ C0 を 0 に減らします 、 その後実行されます Wait( take_chopstickC[(i+1) % 5] ); これを行うことで、それは保持されます C1箸 ( i =0 なので、 (0 + 1) % 5 = 1) となり、セマフォ C1 が 0 になります。

同様に、Philosopher P1 が食事をしたいとすると、Philosopher() 関数に入り、実行されます。 待ちます( take_chopstickC[i] ); こうすることで保持しようとします C1箸 でもそれはできないだろう 、 セマフォ C1 の値は哲学者 P0 によってすでに 0 に設定されているため、無限ループに入ります。そのため、哲学者 P1 は箸 C1 を取ることができませんが、哲学者 P2 が食べたい場合は哲学者に入ります。 ()関数を入力して実行します 待ちます( take_chopstickC[i] ); これを行うことで、それは保持されます C2箸 セマフォ C2 を 0 に減らし、その後実行します。 Wait( take_chopstickC[(i+1) % 5] ); これを行うことで、それは保持されます C3箸 (i =2 であるため、(2 + 1) % 5 = 3) となり、セマフォ C3 が 0 に減ります。

したがって、上記のコードは、哲学者の食事の問題に対する解決策を提供します。哲学者は、哲学者のすぐ左と右の両方の箸が利用可能な場合にのみ食事をすることができ、そうでない場合、哲学者は待つ必要があります。また、一度に 2 人の独立した哲学者が同時に食事をすることもできます (つまり、哲学者 P0 と P2、P1 と P3、P2 と P4 すべてが独立したプロセスであり、食事の哲学者問題の上記の制約に従っているため、同時に食べることができます）

上記の食事の哲学者問題の解決策の欠点

食事の哲学者問題の上記の解決策から、隣接する 2 人の哲学者が同時に食事をすることはできないことが証明されました。上記の解決策の欠点は、この解決策がデッドロック状態を引き起こす可能性があることです。この状況は、すべての哲学者が同時に左の箸を取ると発生し、デッドロック状態が発生し、哲学者は誰も食べられなくなります。

デッドロックを回避するための解決策のいくつかは次のとおりです。

  • テーブル上の哲学者の最大数は 4 名を超えてはなりません。この場合、哲学者 P3 は箸 C4 を使用できるため、P3 は食事を開始し、食事手順が終了したら両方の箸 C3 を置きます。これで、箸 C2 を持っていた哲学者 P2 も箸 C3 を使用できるようになり、同様に、食べた後に箸を置き、他の哲学者が食事をできるようになります。
  • 偶数の位置にいる哲学者は、右の箸、次に左の箸を選ぶ必要があり、奇数の位置にいる哲学者は、左の箸、次に右の箸を選ぶ必要があります。
  • 両方の箸（左と右）が同時に利用できる場合にのみ、哲学者は自分の箸を持つことを許可されるべきです
  • 最初の 4 人の哲学者 (P0、P1、P2、P3) は全員、左の箸、次に右の箸を選択する必要がありますが、最後の哲学者 P4 は、右の箸、次に左の箸を選択する必要があります。これにより、P4 は最初に右の箸を持つように強制されます。P4 の右の箸は C0 であり、すでに哲学者 P0 が保持しており、その値は 0 に設定されています。つまり、C0 はすでに 0 であるため、P4 は無限の世界に閉じ込められます。ループと箸 C4 は空のままです。したがって、哲学者 P3 は左 C3 と右​​ C4 の両方の箸を持っているため、食事を開始し、食べ終わったら両方の箸を置き、他の人に食べさせることでデッドロックの問題が解消されます。

この問題の設計は、デッドロックを回避するという課題を示すことでした。システムのデッドロック状態とは、システムの進行が不可能な状態です。各哲学者が次のように行動するよう指示される提案を考えてみましょう。

  • 哲学者は、左のフォークが利用できるようになるまで考え、利用可能になったらそれを保持するように指示されます。
  • 哲学者は、適切なフォークが利用できるまで考え、利用可能になったらそれを保持するように指示されます。
  • 哲学者は両方のフォークが利用できるときに食べるように指示されます。
  • 次に、右のフォークを最初に置きます
  • 次に左フォークを置きます
  • 最初から繰り返します。