3.3 食事する哲学者の問題

食事する哲学者とは、昔からよく使われてきたシナリオで、仕組みは次のとおりです。0 から 4 の番号が付けられた 5 人の哲学者が、考えながら円卓に座っています。やがて、個々の哲学者は空腹になり食事しようと考えます。テーブルには麺を乗せた大皿がありますが、各哲学者は使用できる箸を 1 本しか持っていません。食事するには、箸を共有する必要があります。各哲学者の (テーブルに向かって) 右側の箸には、その哲学者と同じ番号が付けられています。

図 3-1 食事する哲学者

各哲学者は最初に、自分の番号の付いた自身の箸に手を伸ばします。哲学者は、自身に割り当てられた箸を手にすると、隣の哲学者に割り当てられた箸に手を伸ばします。両方の箸を手にすると、食事できます。食事が終わると、箸をテーブルの元の位置に、左右に 1 本ずつ戻します。このプロセスは、麺がなくなるまで繰り返されます。

3.3.1 哲学者がデッドロックに陥るしくみ

デッドロックが実際に起こるのは、哲学者全員が自身の箸を手に持ち、隣の哲学者の箸が使用できるようになるのを待機している、次のような状況です。

• 哲学者 0 は箸 0 を手に持って箸 1 を待機している

• 哲学者 1 は箸 1 を手に持って箸 2 を待機している

• 哲学者 2 は箸 2 を手に持って箸 3 を待機している

• 哲学者 3 は箸 3 を手に持って箸 4 を待機している

• 哲学者 4 は箸 4 を手に持って箸 0 を待機している

この状況では誰も食事できず、哲学者たちはデッドロック状態に陥ります。プログラムを何度も実行するとわかります。つまりこのプログラムは、ハングアップすることもあれば、最後まで実行できることもあるのです。次の実行例は、このプログラムがハングアップする様子を示しています。

prompt% cc din_philo.c
prompt% a.out
Philosopher 0 is done thinking and now ready to eat.
Philosopher 2 is done thinking and now ready to eat.
Philosopher 2: got right  chopstick 2
Philosopher 2: got left chopstick 3
Philosopher 0: got right  chopstick 0
Philosopher 0: got left chopstick 1
Philosopher 0: eating.
Philosopher 4 is done thinking and now ready to eat.
Philosopher 4: got right  chopstick 4
Philosopher 2: eating.
Philosopher 3 is done thinking and now ready to eat.
Philosopher 1 is done thinking and now ready to eat.
Philosopher 0: got right  chopstick 0
Philosopher 3: got right  chopstick 3
Philosopher 2: got right  chopstick 2
Philosopher 1: got right  chopstick 1
(hang)

Execution terminated by pressing CTRL-C

3.3.2 哲学者 1 の休眠時間の導入

デッドロックを回避する 1 つの方法は、哲学者 1 が自分の箸に手を伸ばす前に待機するというものです。コードの観点からは、自分の箸に手を伸ばす前に、指定した時間 (sleep_seconds)、哲学者 1 を休眠状態にすることができます。十分休眠した場合、プログラムは実デッドロックなしに終了できます。実行可能ファイルに対する引数として休眠する秒数を指定できます。引数を指定しない場合、哲学者は休眠しません。

次の擬似コードは各哲学者のロジックを示します。

   while (there is still food on the table)
      {
        if (sleep argument is specified and I am philosopher #1)
           {
             sleep specified amount of time
           }

        grab right fork
        grab left fork
        eat some food
        put down left fork
        put down right fork 
      }

次のリストは、哲学者 1 が自分の箸に手を伸ばすまでに 30 秒間待機するようにしたプログラムを 1 回実行した様子を示しています。プログラムの実行は完了し、5 人の哲学者全員が食事し終わります。

% a.out 30
Philosopher 0 is done thinking and now ready to eat.
Philosopher 0: got right  chopstick 0
Philosopher 0: got left chopstick 1
Philosopher 4 is done thinking and now ready to eat.
Philosopher 4: got right  chopstick 4
Philosopher 3 is done thinking and now ready to eat.
Philosopher 3: got right  chopstick 3
Philosopher 0: eating.
Philosopher 2 is done thinking and now ready to eat.
Philosopher 2: got right  chopstick 2
Philosopher 1 is done thinking and now ready to eat.
Philosopher 0: got right  chopstick 0
Philosopher 0: got left chopstick 1
Philosopher 0: eating.
Philosopher 0: got right  chopstick 0
Philosopher 0: got left chopstick 1
Philosopher 0: eating.
Philosopher 0: got right  chopstick 0
Philosopher 0: got left chopstick 1
Philosopher 0: eating.
Philosopher 0: got right  chopstick 0
Philosopher 0: got left chopstick 1
Philosopher 0: eating.
Philosopher 0: got right  chopstick 0
Philosopher 0: got left chopstick 1
Philosopher 0: eating.
Philosopher 0: got right  chopstick 0
Philosopher 0: got left chopstick 1
Philosopher 0: eating.
Philosopher 0: got right  chopstick 0
Philosopher 0: got left chopstick 1
Philosopher 0: eating.
Philosopher 0: got right  chopstick 0
Philosopher 0: got left chopstick 1
Philosopher 0: eating.
Philosopher 0: got right  chopstick 0
Philosopher 0: got left chopstick 1
Philosopher 0: eating.
...
Philosopher 0: got right  chopstick 0
Philosopher 0: got left chopstick 1
Philosopher 0: eating.
Philosopher 0: got right  chopstick 0
Philosopher 0: got left chopstick 1
Philosopher 0: eating.
Philosopher 0: got right  chopstick 0
Philosopher 0: got left chopstick 1
Philosopher 0: eating.
Philosopher 0: got right  chopstick 0
Philosopher 0: got left chopstick 1
Philosopher 0: eating.
Philosopher 0: got right  chopstick 0
Philosopher 0: got left chopstick 1
Philosopher 0: eating.
Philosopher 0: got right  chopstick 0
Philosopher 0: got left chopstick 1
Philosopher 0: eating.
Philosopher 0: got right  chopstick 0
Philosopher 0: got left chopstick 1
Philosopher 0: eating.
Philosopher 0: got right  chopstick 0
Philosopher 0: got left chopstick 1
Philosopher 0: eating.
Philosopher 0 is done eating.
Philosopher 4: got left chopstick 0
Philosopher 4: eating.
Philosopher 4 is done eating.
Philosopher 3: got left chopstick 4
Philosopher 3: eating.
Philosopher 3 is done eating.
Philosopher 2: got left chopstick 3
Philosopher 2: eating.
Philosopher 2 is done eating.
Philosopher 1: got right  chopstick 1
Philosopher 1: got left chopstick 2
Philosopher 1: eating.
Philosopher 1 is done eating.
%

Execution terminated normally

プログラムを数回実行して異なる休眠引数を指定してみてください。哲学者 1 が箸を取る前に短時間しか待機しないとどうなるか、あるいは長い時間待機させたらどうなるかを観察するために、実行可能ファイル a.out にいろいろな休眠引数を指定してみます。そして、休眠引数を使用した状態と使用しない状態で複数回プログラムを再実行します。プログラムがハングアップする場合も、最後まで実行する場合もあります。プログラムがハングアップするかどうかは、スレッドのスケジュールと、スレッドによるロックの要求のタイミングによって異なります。