第 3 章 デッドロックのチュートリアル
このチュートリアルでは、スレッドアナライザを利用して、マルチスレッドプログラム内の実デッドロックに加え、潜在的デッドロックを検出する方法を説明します。「デッドロック」という用語は、2 つ以上のスレッドが互いを待つ状態になり、永久にその実行が妨げられる (滞る) 状態を表します。デッドロックの原因は、プログラムロジックの誤り、同期機構や境界の不適切な使用など数多く存在します。このチュートリアルでは、相互排他ロックの不適切な使用によって発生するデッドロックに焦点を当てます。この種のデッドロックは、マルチスレッドアプリケーションでよく起きます。2 つ以上のスレッドを持つプロセスで、次の 3 つの条件が成立すると、デッドロックになる可能性があります。
-
すでにロックを保持しているスレッドが新しいロックを要求し、かつ
-
それらの新しいロック要求の発生タイミングが同時で、かつ
-
2 つ以上のスレッドが、それぞれチェーン内で次のスレッドが保持するロックを待つ循環チェーンを形成している。
次に簡単なデッドロック状態の例を示します。
|
スレッド 1 がロック A を保持していて、ロック B を要求 |
|
スレッド 2 がロック B を保持していて、ロック A を要求 |
デッドロックは、潜在的デッドロックと実デッドロックの 2 種類に分けることがで き、次のような相違があります。
-
潜在的デッドロックはプログラムを実行すると必ず発生するわけではなく、スレッドのスケジューリングやスレッドによるロック要求のタイミングによって、プログラムの実行時に発生する可能性があるデッドロックです。
-
これに対し実デッドロックは、プログラムの実行中に発生するデッドロックです。実デッドロックでは、関係するスレッドの実行は滞りますが、プロセス全体の実行は滞ることもあれば、そうでないこともあります。
3.1 食事する哲学者のソースファイル
食事する哲学者 (dining-philosophers) の問題をシミュレートするサンプルプログラムは、POSIX スレッドを使用した C プログラムです。ソースファイルの名前は din_philo.c です。このプログラムは潜在的および実デッドロックの両方を提示できます。次は、このファイルのコードリストで、このあとにコードについて解説します。
/* din_philo.c */
1 #include <pthread.h>
2 #include <stdio.h>
3 #include <unistd.h>
4 #include <stdlib.h>
5 #include <errno.h>
6 #include <assert.h>
7
8 #define PHILOS 5
9 #define DELAY 5000
10 #define FOOD 50
11
12 void *philosopher (void *id);
13 void grab_chopstick (int,
14 int,
15 char *);
16 void down_chopsticks (int,
17 int);
18 int food_on_table ();
19
20 pthread_mutex_t chopstick[PHILOS];
21 pthread_t philo[PHILOS];
22 pthread_mutex_t food_lock;
23 int sleep_seconds = 0;
24
25
26 int
27 main (int argn,
28 char **argv)
29 {
30 int i;
31
32 if (argn == 2)
33 sleep_seconds = atoi (argv[1]);
34
35 pthread_mutex_init (&food_lock, NULL);
36 for (i = 0; i < PHILOS; i++)
37 pthread_mutex_init (&chopstick[i], NULL);
38 for (i = 0; i < PHILOS; i++)
39 pthread_create (&philo[i], NULL, philosopher, (void *)i);
40 for (i = 0; i < PHILOS; i++)
41 pthread_join (philo[i], NULL);
42 return 0;
43 }
44
45 void *
46 philosopher (void *num)
47 {
48 int id;
49 int i, left_chopstick, right_chopstick, f;
50
51 id = (int)num;
52 printf ("Philosopher %d is done thinking and now ready to eat.\n", id);
53 right_chopstick = id;
54 left_chopstick = id + 1;
55
56 /* 箸が一巡した */
57 if (left_chopstick == PHILOS)
58 left_chopstick = 0;
59
60 while (f = food_on_table ()) {
61
62 /* 箸を手に取る前にうたた寝をする哲学者 1 のおかげで、ほかの
63 * 哲学者達は、デッドロックに陥ることなく食事をすることが
64 * できます。
65 */
66 if (id == 1)
67 sleep (sleep_seconds);
68
69 grab_chopstick (id, right_chopstick, "right ");
70 grab_chopstick (id, left_chopstick, "left");
71
72 printf ("Philosopher %d: eating.\n", id);
73 usleep (DELAY * (FOOD - f + 1));
74 down_chopsticks (left_chopstick, right_chopstick);
75 }
76
77 printf ("Philosopher %d is done eating.\n", id);
78 return (NULL);
79 }
80
81 int
82 food_on_table ()
83 {
84 static int food = FOOD;
85 int myfood;
86
87 pthread_mutex_lock (&food_lock);
88 if (food > 0) {
89 food--;
90 }
91 myfood = food;
92 pthread_mutex_unlock (&food_lock);
93 return myfood;
94 }
95
96 void
97 grab_chopstick (int phil,
98 int c,
99 char *hand)
100 {
101 pthread_mutex_lock (&chopstick[c]);
102 printf ("Philosopher %d: got %s chopstick %d\n", phil, hand, c);
103 }
104
105 void
106 down_chopsticks (int c1,
107 int c2)
108 {
109 pthread_mutex_unlock (&chopstick[c1]);
110 pthread_mutex_unlock (&chopstick[c2]);
111 }
3.2 食事する哲学者のシナリオ
食事する哲学者のシナリオは、次のような構成を持つ古典的なシナリオです。0 から 4 の番号が振られた 5 人の哲学者が丸いテーブルに向かって座り、思索しています。時間の経過とともに、空腹になり、食事をとることにします。テーブルには麺の盛られた大皿がありますが、哲学者が使用できる箸は 1 人に 1 本しかありません。食事をするためには、箸を共用することになります。それぞれの哲学者の、テーブルに向かって左側にある箸には、その哲学者と同じ番号が振られています。
哲学者は、最初に自分の箸 (自分と同じ番号の 1 本の箸) を取ろうとします。自分に割り当てられた箸を取ると、次に、自分の隣の人に割り当てられた箸に手を伸ばします。両方の箸を手にすると、食事ができます。食事を終えると、哲学者はテーブル上の元の位置に 2 本の箸を戻します。麺がなくなるまで、このプロセスが繰り返されます。
3.2.1 哲学者がデッドロックに陥る状況
実デッドロックは、哲学者全員がそれぞれに自分の箸を手にしていて、隣の哲学者の箸が使い終わるのを待つときに発生します。
|
哲学者 0 は箸 0 を手にしていて、箸 1 を待つ |
|
哲学者 1 は箸 1 を手にしていて、箸 2 を待つ |
|
哲学者 2 は箸 2 を手にしていて、箸 3 を待つ |
|
哲学者 3 は箸 3 を手にしていて、箸 4 を待つ |
|
哲学者 4 は箸 4 を手にしていて、箸 0 を待つ |
この状況では誰も食事をすることができず、哲学者はデッドロック状態となります。プログラムを何回か実行します。実行が滞ることもあれば、最後まで実行されることもあることがわかります。
食事する哲学者プログラムを実行して、実行が完了するか、またはデッドロックになるかを確認します。 次の実行例に見られるように、実行は滞る可能性があります。
prompt% cc din_phil.c -mt 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) CTRL-C を押して実行を終了します
3.2.2 哲学者 1 のスリープ時間の導入
潜在的デッドロックに対して考えられる 1 つの解決策は、哲学者 1 が時間を置いてから箸を取るようにすることです。コード面から言うと、箸を取ろうとする前に、指定した時間 (sleep_seconds)、 哲学者 1 をスリープさせることができます。このスリープが十分に長ければ、プログラムは実デッドロックなしに終了する可能性があります。実行可能ファイルの引数としてスリープする秒数を指定できます。引数を指定しなかった場合、哲学者はスリープしません。
次の擬似コードは、各哲学者のロジックを示しています。
while (テーブルにはまだ食事がある)
{
if (スリープのための引数が指定されていて、自身は哲学者 1 である)
{
指定された時間スリープする
}
右の箸を持つ
左の箸を持つ
食事をする
左の箸を置く
右の箸を置く
}
次のリストは、哲学者 1 が 30 秒経過してから自分の箸を取るようなプログラムの実行を示しています。プログラムは最後まで実行され、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. % 実行は正常に終了します
スリープ引数の値を変更しながら、何回かプログラムを実行してみます。哲学者 1 がほんの短い時間で箸を取ろうとした場合はどうなりますか。また、もっと長い時間待つようにした場合はどうですか。実行可能ファイル a.out のスリープ引数の値を変更してみてください。スリープ引数あり、またはスリープ引数なしで、何回かプログラムを実行します。プログラムの実行が滞ることがありますが、最後まで実行されることもあります。プログラムの実行が滞るかどうかは、スレッドのスケジューリングと、スレッドによるロックの要求のタイミングによって異なります。
3.3 スレッドアナライザを使用したデッドロックの検出方法
スレッドアナライザを使用して、プログラムに潜在的および実デッドロックがあるかどうかを検査できます。スレッドアナライザは、Sun Studio パフォーマンスアナライザが使用している「収集解析」モデルと同じモデルに従っています。スレッドアナライザの使用に必要な手順は、次の 3 つです。
-
ソースコードをコンパイルする。
-
デッドロック検出用実験を作成する。
-
実験結果を検証する。
3.3.1 ソースコードのコンパイル
必ず -g を指定してコードをコンパイルしてください。最適化レベルが高いと、行番号や呼び出すスタックなどの情報が誤って報告されることがあるため、最適化レベルを高くしないでください。OpenMP プログラムのコンパイルでは -g -xopenmp=noopt を使用し、 POSIX スレッドプログラムのコンパイルでは -g -mt のみを使用してください。
詳細は、cc.1、CC.1、または f95.1 を参照してください。
3.3.2 デッドロック検出用実験の作成
-r deadlock オプションを付けて、スレッドアナライザの collect コマンドを使用してください。このオプションは、プログラムの実行中にデッドロック検出用実験を作成します。
デッドロック検出用実験をいくつか作成すると、デッドロックを検出できる可能性が大きくなります。実験ごとにスレッド数と入力データを変更してください。
詳細は、collect.1 および collector.1 を参照してください。
3.3.3 実験結果の検証
tha コマンド、analyzer コマンド、または er_print ユーティリティーを使用して、デッドロック検出実験を検証することができます。スレッドアナライザとアナライザでは GUI インタフェースが使用でき、er_print ではコマンド行インタフェースを使用します。
詳細は、tha.1、analyzer.1、および er_print.1 を参照してください。
3.3.3.1 スレッドアナライザインタフェース
スレッドアナライザ は、メニューバー、ツールバー、および各種表示用のタブを含む分割区画で構成されています。デフォルトでは、左側の区画に次の 3 つのタブが表示されます。
-
「デッドロック」タブ
スレッドアナライザがプログラム内で検出した潜在的および実デッドロックの一覧を表示します。デフォルトでは、このタブが選択されています。デッドロックごとに関係するスレッドが表示されます。これらスレッドは、1 つのスレッドがロックを保持するとともに、同じチェーン内の次のスレッドが保持する別のロックを要求する循環チェーンを形成しています。
-
「デュアルソース」タブ
循環チェーン内のスレッドを選択し、「デュアルソース」タブをクリックします。「デュアルソース」タブに、そのスレッドがロックを保持したソース位置と、ロックを要求したソース位置の両方が示されます。スレッドがロックを保持または要求したソース行は強調表示されます。
-
「実験」タブ
実験の負荷オブジェクトを示すとともに、エラーおよび警告メッセージを表示します。スレッドアナライザの右側の区画には、次の 2 つのタブが表示されます。
-
「概要」タブ - 「デッドロック」タブで選択されたデッドロックの概要情報を表示します。
-
「デッドロックの詳細」タブ - 「デッドロック」タブで選択されたデッドロックの詳細情報を表示します。
-
3.3.3.2 er_print インタフェース
左側の区画と異なり、右側の区画には「デッドロックの詳細」タブがあり、「デッドロック」タブで選択されたスレッドの詳細情報を表示します。er_print を使用してデッドロックを検証する際に特に有用なサブコマンドを次に示します。
-
-deadlocks
実験で検出された潜在的および実デッドロックをすべて報告します。
-
-ddetail deadlock_id
deadlock_id に指定されたデッドロックの詳細情報を返します。deadlock_id に all を指定すると、
er_printはすべてのデッドロックの詳細情報を表示します。 -
-header
実験に関する説明を表示し、エラーと警告を報告します。
詳細は、er_print.1 を参照してください。
3.4 実験結果について
この節では、スレッドアナライザを使用して、食事する哲学者プログラムのデッドロックを調査する方法を説明します。最初に実デッドロックになる実行を検証し、そのあとで、正常終了するが、デッドロックの可能性がある実行を調べます。
3.4.1 デッドロックになる実行の検証
次のリストは、食事する哲学者プログラムが実デッドロックになる実行を示しています。
prompt% cc din_philo.c -mt -g prompt% collect -r deadlock a.out 実験データベース tha.1.er の作成中 ... Philosopher 1 is done thinking and now ready to eat. Philosopher 2 is done thinking and now ready to eat. Philosopher 3 is done thinking and now ready to eat. Philosopher 0 is done thinking and now ready to eat. Philosopher 1: got right chopstick 1 Philosopher 3: got right chopstick 3 Philosopher 0: got right chopstick 0 Philosopher 1: got left chopstick 2 Philosopher 3: got left chopstick 4 Philosopher 4 is done thinking and now ready to eat. Philosopher 1: eating. Philosopher 3: eating. Philosopher 3: got right chopstick 3 Philosopher 4: got right chopstick 4 Philosopher 2: got right chopstick 2 Philosopher 0: got left chopstick 1 Philosopher 0: eating. Philosopher 1: got right chopstick 1 Philosopher 4: got left chopstick 0 Philosopher 4: eating. Philosopher 0: got right chopstick 0 Philosopher 3: got left chopstick 4 Philosopher 3: eating. Philosopher 4: got right chopstick 4 Philosopher 2: got left chopstick 3 Philosopher 2: eating. Philosopher 3: got right chopstick 3 Philosopher 1: got left chopstick 2 Philosopher 1: eating. Philosopher 2: got right chopstick 2 Philosopher 0: got left chopstick 1 Philosopher 0: eating. Philosopher 1: got right chopstick 1 Philosopher 4: got left chopstick 0 Philosopher 4: eating. Philosopher 0: got right chopstick 0 Philosopher 3: got left chopstick 4 Philosopher 3: eating. Philosopher 4: got right chopstick 4 Philosopher 2: got left chopstick 3 Philosopher 2: eating. Philosopher 3: got right chopstick 3 Philosopher 1: got left chopstick 2 Philosopher 1: eating. Philosopher 2: got right chopstick 2 Philosopher 0: got left chopstick 1 Philosopher 0: eating. Philosopher 1: got right chopstick 1 Philosopher 4: got left chopstick 0 Philosopher 4: eating. Philosopher 0: got right chopstick 0 Philosopher 3: got left chopstick 4 Philosopher 3: eating. Philosopher 4: got right chopstick 4 Philosopher 2: got left chopstick 3 Philosopher 2: eating. Philosopher 2: got right chopstick 2 Philosopher 3: got right chopstick 3 (hang) CTRL-C を押して実行を終了します % er_print tha.1.er (er_print) deadlocks デッドロック #1, 潜在的デッドロック スレッド #2 ロック保持中: 0x215a8, 位置: grab_chopstick + 0x0000002C, 行 101 "din_philo.c" ロック要求中: 0x215c0, 位置: grab_chopstick + 0x0000002C, 行 101 "din_philo.c" スレッド #3 ロック保持中: 0x215c0, 位置: grab_chopstick + 0x0000002C, 行 101 "din_philo.c" ロック要求中: 0x215d8, 位置: grab_chopstick + 0x0000002C, 行 101 "din_philo.c" スレッド #4 ロック保持中: 0x215d8, 位置: grab_chopstick + 0x0000002C, 行 101 "din_philo.c" ロック要求中: 0x215f0, 位置: grab_chopstick + 0x0000002C, 行 101 "din_philo.c" スレッド #5 ロック保持中: 0x215f0, 位置: grab_chopstick + 0x0000002C, 行 101 "din_philo.c" ロック要求中: 0x21608, 位置: grab_chopstick + 0x0000002C, 行 101 "din_philo.c" スレッド #6 ロック保持中: 0x21608, 位置: grab_chopstick + 0x0000002C, 行 101 "din_philo.c" ロック要求中: 0x215a8, 位置: grab_chopstick + 0x0000002C, 行 101 "din_philo.c" デッドロック #2, 実デッドロック スレッド #2 ロック保持中: 0x215a8, 位置: grab_chopstick + 0x0000002C, 行 101 "din_philo.c" ロック要求中: 0x215c0, 位置: grab_chopstick + 0x0000002C, 行 101 "din_philo.c" スレッド #3 ロック保持中: 0x215c0, 位置: grab_chopstick + 0x0000002C, 行 101 "din_philo.c" ロック要求中: 0x215d8, 位置: grab_chopstick + 0x0000002C, 行 101 "din_philo.c" スレッド #4 ロック保持中: 0x215d8, 位置: grab_chopstick + 0x0000002C, 行 101 "din_philo.c" ロック要求中: 0x215f0, 位置: grab_chopstick + 0x0000002C, 行 101 "din_philo.c" スレッド #5 ロック保持中: 0x215f0, 位置: grab_chopstick + 0x0000002C, 行 101 "din_philo.c" ロック要求中: 0x21608, 位置: grab_chopstick + 0x0000002C, 行 101 "din_philo.c" スレッド #6 ロック保持中: 0x21608, 位置: grab_chopstick + 0x0000002C, 行 101 "din_philo.c" ロック要求中: 0x215a8, 位置: grab_chopstick + 0x0000002C, 行 101 "din_philo.c" デッドロック一覧の概要: 実験: tha.1.er 総デッドロック数: 2 (er_print)
次のスクリーンショットは、スレッドアナライザでのこのデッドロック情報を示しています。
スレッドアナライザは、din_philo.c について 2 つのデッドロック (潜在的と実デッドロック 1 つずつ) を報告しています。よく見ると、2 つのデッドロックは同一であることがわかります。このデッドロックに関係している循環チェーンは次のようなものです。
|
スレッド 2: |
|
アドレス |
|
スレッド 3: |
|
アドレス |
|
スレッド 4: |
|
アドレス |
|
スレッド 5: |
|
アドレス |
|
スレッド 6: |
|
アドレス |
チェーンの最初のスレッド (スレッド #2) を選択し、「デュアルソース」タブをクリックして、スレッド #2 のロック保持が発生したアドレス 0x215a8 に対応するソースコード位置と、ロック要求が発生したアドレス 0x215c0 に対応するソースコード位置を確認します。次のスクリーンショットは、スレッド 2 の「デュアルソース」タブを示しています。デフォルトメトリック (「排他的デッドロック」メトリック) は各ソース行の左側に表示されます。このメトリックは、その行について、1 つのデッドロックに関係するロック保持またはロック要求動作が報告された回数を示します。
3.4.2 デッドロックの可能性があるが正常終了する実行の検証
食事する哲学者プログラムは、十分なスリープ引数値を指定すると、実デッドロックを回避し、正常に終了することができます。ただし、正常終了は、プログラムがデッドロックにならないことを意味するわけではありません。単に、実行中に、保持および要求されたロックによってデッドロックチェーンが形成されなかっただけです。別の実行でタイミングが変われば、実デッドロックが発生する可能性があります。次のリストは、食事する哲学者プログラムが正常終了する実行を示しています。ただし、er_print ユーティリティーとスレッドアナライザからは潜在的デッドロックが報告されます。
% cc din_philo.c -mt -g % collect -r deadlock a.out 40 Creating experiment database tha.2.er ... Philosopher 0 is done thinking and now ready to eat. Philosopher 2 is done thinking and now ready to eat. Philosopher 1 is done thinking and now ready to eat. Philosopher 3 is done thinking and now ready to eat. Philosopher 2: got right chopstick 2 Philosopher 3: got right chopstick 3 Philosopher 0: got right chopstick 0 Philosopher 4 is done thinking and now ready to eat. Philosopher 0: got left chopstick 1 Philosopher 0: eating. Philosopher 3: got left chopstick 4 Philosopher 3: eating. Philosopher 0: got right chopstick 0 Philosopher 4: got right chopstick 4 Philosopher 2: got left chopstick 3 Philosopher 2: eating. Philosopher 0: got left chopstick 1 Philosopher 0: eating. Philosopher 3: got right chopstick 3 Philosopher 2: got right chopstick 2 Philosopher 4: got left chopstick 0 Philosopher 4: eating. Philosopher 0: got right chopstick 0 Philosopher 3: got left chopstick 4 Philosopher 3: eating. Philosopher 0: got left chopstick 1 Philosopher 0: eating. Philosopher 4: got right chopstick 4 Philosopher 2: got left chopstick 3 Philosopher 2: eating. Philosopher 4: got left chopstick 0 Philosopher 4: eating. Philosopher 3: got right chopstick 3 Philosopher 2: got right chopstick 2 Philosopher 0: got right chopstick 0 Philosopher 3: got left chopstick 4 Philosopher 3: eating. Philosopher 0: got left chopstick 1 Philosopher 0: eating. Philosopher 0: got right chopstick 0 Philosopher 2: got left chopstick 3 Philosopher 2: eating. ... Philosopher 0: got left chopstick 1 Philosopher 0: eating. Philosopher 4: got right chopstick 4 Philosopher 3: got right chopstick 3 Philosopher 4: got left chopstick 0 Philosopher 4: eating. Philosopher 0: got right chopstick 0 Philosopher 3: got left chopstick 4 Philosopher 0: got left chopstick 1 Philosopher 0: eating. Philosopher 3: eating. Philosopher 0: got right chopstick 0 Philosopher 2: got left chopstick 3 Philosopher 2: eating. Philosopher 0: got left chopstick 1 Philosopher 0: eating. Philosopher 4: got right chopstick 4 Philosopher 3: got right chopstick 3 Philosopher 2: got right chopstick 2 Philosopher 4: got left chopstick 0 Philosopher 4: eating. Philosopher 4 is done eating. Philosopher 3: got left chopstick 4 Philosopher 3: eating. Philosopher 0: got right chopstick 0 Philosopher 0: got left chopstick 1 Philosopher 0: eating. Philosopher 3 is done eating. Philosopher 2: got left chopstick 3 Philosopher 2: eating. Philosopher 0 is done 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. % 実行は正常に終了します % er_print tha.2.er (er_print) deadlocks デッドロック #1, 潜在的デッドロック スレッド #2 ロック保持中: 0x215a8, 位置: grab_chopstick + 0x0000002C, 行 101 "din_philo.c" ロック要求中: 0x215c0, 位置: grab_chopstick + 0x0000002C, 行 101 "din_philo.c" スレッド #3 ロック保持中: 0x215c0, 位置: grab_chopstick + 0x0000002C, 行 101 "din_philo.c" ロック要求中: 0x215d8, 位置: grab_chopstick + 0x0000002C, 行 101 "din_philo.c" スレッド #4 ロック保持中: 0x215d8, 位置: grab_chopstick + 0x0000002C, 行 101 "din_philo.c" ロック要求中: 0x215f0, 位置: grab_chopstick + 0x0000002C, 行 101 "din_philo.c" スレッド #5 ロック保持中: 0x215f0, 位置: grab_chopstick + 0x0000002C, 行 101 "din_philo.c" ロック要求中: 0x21608, 位置: grab_chopstick + 0x0000002C, 行 101 "din_philo.c" スレッド #6 ロック保持中: 0x21608, 位置: grab_chopstick + 0x0000002C, 行 101 "din_philo.c" ロック要求中: 0x215a8, 位置: grab_chopstick + 0x0000002C, 行 101 "din_philo.c" デッドロック一覧の概要: 実験: tha.2.er 総デッドロック数: 1 (er_print)
次のスクリーンショットは、スレッドアナライザインタフェースに表示された潜在的ロック情報を示しています。
3.5 デッドロックの解決と誤検出について
デッドロックを解決する方法としては、待ち時間をおいて食事をとるようにする方法のほかに、トークンを用いたシステムを使用して、哲学者がトークンを受け取ってから食事をとるようにする方法もあります。用意するトークンの数は、席についている哲学者の人数より少なくします。哲学者は、トークンを受け取ったあと、テーブルの規則に従って食事をとることができます。食事をしたあと、哲学者はトークンを返却し、プロセスを繰り返します。次の擬似コードは、トークンを用いたシステムを使用したときの各哲学者のロジックを示します。
while (テーブルにはまだ食事がある)
{
トークンを取得
右の箸を持つ
左の箸を持つ
食事をする
左の箸を置く
右の箸を置く
トークンを返却
}
後述の節では、2 つの異なるトークンを用いたシステムについて詳しく説明します。
3.5.1 トークンによる哲学者の制限
次のリストは、トークンを用いたシステムを使用するように修正された食事する哲学者プログラムのバージョンを示しています。このバージョンでは、食事をする人数より 1 つ少ない 4 つのトークンが組み込まれているため、同時に食事をできる哲学者が 4 人を超えることはありません。 このバージョンのプログラム名は din_philo_fix1.c です。
1 #include <pthread.h>
2 #include <stdio.h>
3 #include <unistd.h>
4 #include <stdlib.h>
5 #include <errno.h>
6 #include <assert.h>
7
8 #define PHILOS 5
9 #define DELAY 5000
10 #define FOOD 50
11
12 void *philosopher (void *id);
13 void grab_chopstick (int,
14 int,
15 char *);
16 void down_chopsticks (int,
17 int);
18 int food_on_table ();
19 int get_token ();
20 void return_token ();
21
22 pthread_mutex_t chopstick[PHILOS];
23 pthread_t philo[PHILOS];
24 pthread_mutex_t food_lock;
25 pthread_mutex_t num_can_eat_lock;
26 int sleep_seconds = 0;
27 uint32_t num_can_eat = PHILOS - 1;
28
29
30 int
31 main (int argn,
32 char **argv)
33 {
34 int i;
35
36 pthread_mutex_init (&food_lock, NULL);
37 pthread_mutex_init (&num_can_eat_lock, NULL);
38 for (i = 0; i < PHILOS; i++)
39 pthread_mutex_init (&chopstick[i], NULL);
40 for (i = 0; i < PHILOS; i++)
41 pthread_create (&philo[i], NULL, philosopher, (void *)i);
42 for (i = 0; i < PHILOS; i++)
43 pthread_join (philo[i], NULL);
44 return 0;
45 }
46
47 void *
48 philosopher (void *num)
49 {
50 int id;
51 int i, left_chopstick, right_chopstick, f;
52
53 id = (int)num;
54 printf ("Philosopher %d is done thinking and now ready to eat.\n", id);
55 right_chopstick = id;
56 left_chopstick = id + 1;
57
58 /* 箸が一巡した */
59 if (left_chopstick == PHILOS)
60 left_chopstick = 0;
61
62 while (f = food_on_table ()) {
63 get_token ();
64
65 grab_chopstick (id, right_chopstick, "right ");
66 grab_chopstick (id, left_chopstick, "left");
67
68 printf ("Philosopher %d: eating.\n", id);
69 usleep (DELAY * (FOOD - f + 1));
70 down_chopsticks (left_chopstick, right_chopstick);
71
72 return_token ();
73 }
74
75 printf ("Philosopher %d is done eating.\n", id);
76 return (NULL);
77 }
78
79 int
80 food_on_table ()
81 {
82 static int food = FOOD;
83 int myfood;
84
85 pthread_mutex_lock (&food_lock);
86 if (food > 0) {
87 food--;
88 }
89 myfood = food;
90 pthread_mutex_unlock (&food_lock);
91 return myfood;
92 }
93
94 void
95 grab_chopstick (int phil,
96 int c,
97 char *hand)
98 {
99 pthread_mutex_lock (&chopstick[c]);
100 printf ("Philosopher %d: got %s chopstick %d\n", phil, hand, c);
101 }
102
103 void
104 down_chopsticks (int c1,
105 int c2)
106 {
107 pthread_mutex_unlock (&chopstick[c1]);
108 pthread_mutex_unlock (&chopstick[c2]);
109 }
110
111
112 int
113 get_token ()
114 {
115 int successful = 0;
116
117 while (!successful) {
118 pthread_mutex_lock (&num_can_eat_lock);
119 if (num_can_eat > 0) {
120 num_can_eat--;
121 successful = 1;
122 }
123 else {
124 successful = 0;
125 }
126 pthread_mutex_unlock (&num_can_eat_lock);
127 }
128 }
129
130 void
131 return_token ()
132 {
133 pthread_mutex_lock (&num_can_eat_lock);
134 num_can_eat++;
135 pthread_mutex_unlock (&num_can_eat_lock);
136 }
この修正されたバージョンの食事する哲学者プログラムをコンパイルして、何回か実行してみてください。このトークンを用いたシステムは、箸を使用する人数を制限することで、実および潜在的デッドロックを回避します。
3.5.1.1 誤検出の報告
前述のトークンを用いたシステムを使用したシステムの実装で、潜在的デッドロックが存在しないにもかかわらず、スレッドアナライザからは潜在的デッドロックが報告されます。これは誤検出です。潜在的デッドロックの詳細情報を示す次のスクリーンショットを検出してみましょう。
チェーンの最初のスレッド (スレッド #2) を選択し、「デュアルソース」タブをクリックして、スレッド #2 のロック保持が発生したアドレス 0x215a8 に対応するソースコード位置と、ロック要求が発生したアドレス 0x215c0 に対応するソースコード位置を確認します。次のスクリーンショットは、スレッド #2 の「デュアルソース」タブを示しています。
din_philo_fix1.c 内の get_token() 関数が while ループを使用して、スレッドの同期を取っています。トークンの獲得に成功しない限り (num_can_eat がゼロより大きくなったときに獲得)、スレッドが while ループを離れることはありません。この while ループは、同時に食事をする人を 4 人に制限します。しかし、while ループによって実装されている同期機構は、スレッドアナライザによって認識されません。スレッドアナライザは 5 人の哲学者全員が同時に箸をとって食事をしようとするとみなすため、潜在的デッドロックを報告します。次の節では、スレッドアナライザが認識する同期機構を使用することによって同時に食事をする人数を制限する方法を詳しく説明します。
3.5.2 トークンを用いたシステムのもう一つの例
次のリストは、トークンを用いたシステムのもう一つの例を示しています。この実装でもトークンは 4 つであるため、同時に食事をしようとする人が 4 人を超えることはありません。しかし、この実装では sem_wait() および sem_post() のセマフォールーチンを使用して、食事をする哲学者の人数を制限します。このバージョンのソースファイル名は din_philo_fix2.c です。
注 –
din_philo_fix2.c のコンパイルでは -lrt オプションを使用し、適切なセマフォールーチンとリンクさせます。
din_philo_fix2.c のコード詳細を次に示します。
1 #include <pthread.h>
2 #include <stdio.h>
3 #include <unistd.h>
4 #include <stdlib.h>
5 #include <errno.h>
6 #include <assert.h>
7 #include <semaphore.h>
8
9 #define PHILOS 5
10 #define DELAY 5000
11 #define FOOD 50
12
13 void *philosopher (void *id);
14 void grab_chopstick (int,
15 int,
16 char *);
17 void down_chopsticks (int,
18 int);
19 int food_on_table ();
20 int get_token ();
21 void return_token ();
22
23 pthread_mutex_t chopstick[PHILOS];
24 pthread_t philo[PHILOS];
25 pthread_mutex_t food_lock;
26 int sleep_seconds = 0;
27 sem_t num_can_eat_sem;
28
29
30 int
31 main (int argn,
32 char **argv)
33 {
34 int i;
35
36 pthread_mutex_init (&food_lock, NULL);
37 sem_init(&num_can_eat_sem, 0, PHILOS - 1);
38 for (i = 0; i < PHILOS; i++)
39 pthread_mutex_init (&chopstick[i], NULL);
40 for (i = 0; i < PHILOS; i++)
41 pthread_create (&philo[i], NULL, philosopher, (void *)i);
42 for (i = 0; i < PHILOS; i++)
43 pthread_join (philo[i], NULL);
44 return 0;
45 }
46
47 void *
48 philosopher (void *num)
49 {
50 int id;
51 int i, left_chopstick, right_chopstick, f;
52
53 id = (int)num;
54 printf ("Philosopher %d is done thinking and now ready to eat.\n", id);
55 right_chopstick = id;
56 left_chopstick = id + 1;
57
58 /* 箸が一巡した */
59 if (left_chopstick == PHILOS)
60 left_chopstick = 0;
61
62 while (f = food_on_table ()) {
63 get_token ();
64
65 grab_chopstick (id, right_chopstick, "right ");
66 grab_chopstick (id, left_chopstick, "left");
67
68 printf ("Philosopher %d: eating.\n", id);
69 usleep (DELAY * (FOOD - f + 1));
70 down_chopsticks (left_chopstick, right_chopstick);
71
72 return_token ();
73 }
74
75 printf ("Philosopher %d is done eating.\n", id);
76 return (NULL);
77 }
78
79 int
80 food_on_table ()
81 {
82 static int food = FOOD;
83 int myfood;
84
85 pthread_mutex_lock (&food_lock);
86 if (food > 0) {
87 food--;
88 }
89 myfood = food;
90 pthread_mutex_unlock (&food_lock);
91 return myfood;
92 }
93
94 void
95 grab_chopstick (int phil,
96 int c,
97 char *hand)
98 {
99 pthread_mutex_lock (&chopstick[c]);
100 printf ("Philosopher %d: got %s chopstick %d\n", phil, hand, c);
101 }
102
103 void
104 down_chopsticks (int c1,
105 int c2)
106 {
107 pthread_mutex_unlock (&chopstick[c1]);
108 pthread_mutex_unlock (&chopstick[c2]);
109 }
110
111
112 int
113 get_token ()
114 {
115 sem_wait(&num_can_eat_sem);
116 }
117
118 void
119 return_token ()
120 {
121 sem_post(&num_can_eat_sem);
122 }
この新しい実装では、セマフォー num_can_eat_sem を使用して、同時に食事をとることができる哲学者の人数を制限します。このセマフォー num_can_eat_sem は、哲学者の人数より 1 人少ない 4 に初期化されます。食事をとろうとする前に哲学者は get_token() を呼び出し、この関数によって sem_wait(&num_can_eat_sem) が呼び出されます。sem_wait() の呼び出しにより、呼び出し元の哲学者はこのセマフォーの値が正になるまで待機し、正になると、1 を引いてセマフォー値を変更します。食事を終えると、哲学者は return_token() を呼び出し、この関数によって sem_post(&num_can_eat_sem) が呼び出されます。この sem_post() の呼び出しにより 1 が追加されてセマフォー値が変更されます。スレッドアナライザは sem_wait() および sem_post() の呼び出しを認識し、哲学者全員が同時に食事をとろうとしていないと判定します。
この新しいプログラム実装を何回か実行すると、その都度正常に終了し、実行が滞らないことがわかります。また、次のスクリーンショットが示すように、スレッドアナライザは実デッドロックと潜在的デッドロックのどちらも報告しません。
スレッドアナライザが認識するスレッドおよびメモリー割り当て API 一覧は、付録 A 「スレッドアナライザのユーザー API」 を参照してください。
- © 2010, Oracle Corporation and/or its affiliates