第 3 章 デッドロックのチュートリアル
このチュートリアルでは、スレッドアナライザを使用して、マルチスレッドプログラム内の潜在的デッドロックおよび実デッドロックを検出する方法について説明します。
チュートリアルでは次のトピックを扱います。
3.1 デッドロックについて
デッドロックという用語は、2 つ以上のスレッドが互いを待機しているために処理がどこへも進まない状況を意味します。デッドロックの原因は、間違ったプログラムロジックや (ロックやバリアーなどの) 同期の不適切な使用など数多くあります。このチュートリアルでは、相互排他ロックの不適切な使用によって生じたデッドロックに焦点を当てます。この種のデッドロックは、マルチスレッドアプリケーションでよく生じます。
2 つ以上のスレッドを含むプロセスが次の 3 つの条件に当てはまるときに、デッドロックが発生する可能性があります。
-
すでにロックを保持しているスレッドが新しいロックを要求する
-
新しいロックの要求が同時に行われる
-
チェーン内の次のスレッドで保持されているロックを各スレッドが待機するという巡回チェーンを、2 つ以上のスレッドが形成する
デッドロック状況の簡単な例を次に示します。
-
スレッド 1 はロック A を保持し、ロック B を要求する
-
スレッド 2 はロック B を保持し、ロック A を要求する
デッドロックには、潜在的デッドロックと実デッドロックの 2 つの種類があり、次のような違いがあります。
-
潜在的デッドロックは、所定の実行で必ず起きるわけではありませんが、スレッドのスケジュールや、スレッドによって要求されたロックのタイミングに依存したプログラムの実行で起きる可能性があります。
-
実デッドロックは、プログラムの実行中に発生するものです。実デッドロックでは、関係するスレッドの実行は滞りますが、プロセス全体の実行は滞ることもあれば、そうでないこともあります。
3.2 デッドロックチュートリアルのソースファイルの入手
このチュートリアルで使用する din_philo.c ソースファイルは、Oracle Solaris システムのディレクトリ /opt/solstudio12.2/prod/examples/tha/din_philo か、Linux システムの /opt/oracle/solstudio12.2/prod/examples/tha/din_philo にあります。例を含んだディレクトリには、手順に関するDEMO ファイルと Makefile ファイルが 1つずつありますが、このチュートリアルではその手順を無視し、Makefile も使用しません。代わりに、ここでは、コマンドを個別に実行していきます。
このチュートリアルに沿って学習するには、例を含んだディレクトリから din_philo.c ファイルを別のディレクトリにコピーするか、自分でファイルを作成し、次のコードリストからコードをコピーしてください。
食事する哲学者の問題をシミュレートする din_philo.c サンプルプログラムは、POSIX スレッドを使用する C プログラムです。このプログラムでは、潜在的デッドロックと実デッドロックの両方が示されます。
3.2.1 din_philo.c のソースコードリスト
din_philo.c のソースコードは次に示すとおりです。
1 /*
2 * Copyright (c) 2006, 2010, Oracle and/or its affiliates. All Rights Reserved.
3 * @(#)din_philo.c 1.4 (Oracle) 10/03/26
4 */
5
6 #include <pthread.h>
7 #include <stdio.h>
8 #include <unistd.h>
9 #include <stdlib.h>
10 #include <errno.h>
11 #include <assert.h>
12
13 #define PHILOS 5
14 #define DELAY 5000
15 #define FOOD 100
16
17 void *philosopher (void *id);
18 void grab_chopstick (int,
19 int,
20 char *);
21 void down_chopsticks (int,
22 int);
23 int food_on_table ();
24
25 pthread_mutex_t chopstick[PHILOS];
26 pthread_t philo[PHILOS];
27 pthread_mutex_t food_lock;
28 int sleep_seconds = 0;
29
30
31 int
32 main (int argn,
33 char **argv)
34 {
35 int i;
36
37 if (argn == 2)
38 sleep_seconds = atoi (argv[1]);
39
40 pthread_mutex_init (&food_lock, NULL);
41 for (i = 0; i < PHILOS; i++)
42 pthread_mutex_init (&chopstick[i], NULL);
43 for (i = 0; i < PHILOS; i++)
44 pthread_create (&philo[i], NULL, philosopher, (void *)i);
45 for (i = 0; i < PHILOS; i++)
46 pthread_join (philo[i], NULL);
47 return 0;
48 }
49
50 void *
51 philosopher (void *num)
52 {
53 int id;
54 int i, left_chopstick, right_chopstick, f;
55
56 id = (int)num;
57 printf ("Philosopher %d is done thinking and now ready to eat.\n", id);
58 right_chopstick = id;
59 left_chopstick = id + 1;
60
61 /* Wrap around the chopsticks. */
62 if (left_chopstick == PHILOS)
63 left_chopstick = 0;
64
65 while (f = food_on_table ()) {
66
67 /* Thanks to philosophers #1 who would like to take a nap
68 * before picking up the chopsticks, the other philosophers
69 * may be able to eat their dishes and not deadlock.
70 */
71 if (id == 1)
72 sleep (sleep_seconds);
73
74 grab_chopstick (id, right_chopstick, "right ");
75 grab_chopstick (id, left_chopstick, "left");
76
77 printf ("Philosopher %d: eating.\n", id);
78 usleep (DELAY * (FOOD - f + 1));
79 down_chopsticks (left_chopstick, right_chopstick);
80 }
81
82 printf ("Philosopher %d is done eating.\n", id);
83 return (NULL);
84 }
85
86 int
87 food_on_table ()
88 {
89 static int food = FOOD;
90 int myfood;
91
92 pthread_mutex_lock (&food_lock);
93 if (food > 0) {
94 food--;
95 }
96 myfood = food;
97 pthread_mutex_unlock (&food_lock);
98 return myfood;
99 }
100
101 void
102 grab_chopstick (int phil,
103 int c,
104 char *hand)
105 {
106 pthread_mutex_lock (&chopstick[c]);
107 printf ("Philosopher %d: got %s chopstick %d\n", phil, hand, c);
108 }
109
110 void
111 down_chopsticks (int c1,
112 int c2)
113 {
114 pthread_mutex_unlock (&chopstick[c1]);
115 pthread_mutex_unlock (&chopstick[c2]);
116 }
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 にいろいろな休眠引数を指定してみます。そして、休眠引数を使用した状態と使用しない状態で複数回プログラムを再実行します。プログラムがハングアップする場合も、最後まで実行する場合もあります。プログラムがハングアップするかどうかは、スレッドのスケジュールと、スレッドによるロックの要求のタイミングによって異なります。
3.4 スレッドアナライザを使用したデッドロックの検索方法
スレッドアナライザを使用して、プログラム内の潜在的デッドロックおよび実デッドロックを確認できます。スレッドアナライザは、Oracle Solaris Studio パフォーマンスアナライザが使用するものと同じ「収集-分析」モデルに従います。
スレッドアナライザを使用するには、次の 3 つの手順を行います。
-
ソースコードをコンパイルする。
-
デッドロック検出実験を作成する。
-
実験結果を検する。
3.4.1 ソースコードをコンパイルする
コードをコンパイルし、必ず -g を指定します。高度な最適化では、行番号や呼び出しスタックなどの情報が間違って報告される場合があるので、高度な最適化は指定しないでください。-g -xopenmp=noopt を付けて OpenMP プログラムをコンパイルし、-g -mt だけを付けて POSIX スレッドプログラムをコンパイルします。
これらのオプションについては、cc(1)、CC(1)、または f95 (1) のマニュアルページを参照してください。
このチュートリアルの場合、次のコマンドを使用してコードをコンパイルします。
% cc -g -o din_philo din_philo.c |
3.4.2 デッドロック検出実験を作成する
-r deadlock オプションを付けてスレッドアナライザの collect コマンドを使用します。このオプションは、プログラムの実行中にデッドロック検出実験を作成します。
このチュートリアルの場合、次のコマンドを使用して、din_philo.1.er というデッドロック検出実験を作成します。
% collect -r deadlock -o din_philo.1.er din_philo |
複数のデッドロック検出実験を作成することによって、デッドロックを検出する可能性を高められます。実験ごとに異なるスレッド数と異なる入力データを使用してください。たとえば、din_philo.c コードで、次の行の値を変更できます。
13 #define PHILOS 5
14 #define DELAY 5000
15 #define FOOD 100
続いて、前述のようにコンパイルして、別の実験結果を収集できます。
詳しくは、collect(1) および collector(1) のマニュアルページを参照してください。
3.4.3 デッドロック検出実験を検証する
スレッドアナライザ、パフォーマンスアナライザ、er_print ユーティリティで、デッドロック検出実験を検証できます。スレッドアナライザおよびパフォーマンスアナライザはどちらも GUI インタフェースを表示します。スレッドアナライザはデフォルトの簡略セットのタブを表示しますが、それ以外はパフォーマンスアナライザと同じです。
3.4.3.1 スレッドアナライザを使用したデッドロック検出実験結果の表示
スレッドアナライザを開始して、din_philo.1.er 実験結果を開くには、次のコマンドを入力します。
% tha din_philo.1.er |
スレッドアナライザは、メニューバー、ツールバー、および各種表示用のタブを含む分割区画で構成されます。
デッドロック検出用に収集された実験結果を開くと、デフォルトで、左側の区画に次のタブが表示されます。
-
「デッドロック」タブ
このタブには、潜在的デッドロックと実デッドロックの一覧が示されます。デフォルトでこのタブが選択されています。各デッドロックに関わるスレッドが示されます。これらのスレッドは、各スレッドがロックを保持し、チェーン内の次のスレッドが保持している別のロックを要求するという巡回チェーンを形成しています。
-
「デュアルソース (Dual Source)」タブ
「デッドロック (Deadlocks)」タブで巡回チェーン内のスレッドを選択し、続いて「デュアルソース (Dual Source)」タブをクリックします。「デュアルソース (Dual Source)」タブには、スレッドがロックを保持したソース位置と、同じスレッドがロックを要求したソース位置が示されます。スレッドがロックを保持し要求したソース行が強調表示されます。
-
「実験」タブ
このタブには、実験でのロードオブジェクトが表示され、エラーおよび警告メッセージが一覧表示されます。
スレッドアナライザ画面の右側区画に次のタブが表示されます。
-
「デッドロック (Deadlocks)」タブから選択したデッドロックの概要情報を示した「概要 (Summary)」タブ。
-
「デッドロック (Deadlocks)」タブから選択したスレッドコンテキストの詳細情報を示した「デッドロックの詳細 (Deadlock Details)」タブ。
3.4.3.2 er_print を使用した、デッドロック検出実験結果の表示
er_print ユーティリティは、コマンド行インタフェースを表示します。インタラクティブセッションで er_print ユーティリティを使用して、セッション中にサブコマンドを指定します。コマンド行オプションを使用して、インタラクティブでない方法でもサブコマンドを指定できます。
次のサブコマンドは、 er_print ユーティリティでデッドロックを調べるときに役立ちます。
-
-deadlocks
このオプションは、実験で検出された潜在的デッドロックおよび実デッドロックについて報告します。(er_print) プロンプトで deadlocks を指定するか、er_print コマンド行で -deadlocks を指定します。
-
-ddetail deadlock_id
このオプションは、指定した deadlock_id を持つデッドロックの詳細な情報を返します。(er_print) プロンプトで ddetail を指定するか、er_print コマンド行で -ddetail を指定します。指定された deadlock_id が all の場合、すべてのデッドロックの詳細情報が表示されます。それ以外では、最初のデッドロックを表す 1 などの単一のデッドロック番号を指定します。
-
-header
このオプションは、実験に関する記述的情報を表示し、すべてのエラーまたは警告を報告します。(er_print) プロンプトで header と指定するか、コマンド行で -header と指定します。
詳細は、collect(1)、tha(1)、analyzer(1)、および er_print(1) のマニュアルページを参照してください。
3.5 デッドロックの実験結果について
この節では、スレッドアナライザを使用して、食事する哲学者のプログラムでのデッドロックを調べる方法について説明します。
3.5.1 デッドロックが発生した実行の検証
次のリストには、実デッドロックになった食事する哲学者のプログラムの実行が示されています。
% cc -g -o din_philo din_philo.c % collect -r deadlock -o din_philo.1.er din_philo Creating experiment database din_philo.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 2: got right chopstick 2 Philosopher 3: got right chopstick 3 (hang) Execution terminated by pressing CTRL-C |
次のコマンドを入力して、er_print ユーティリティで実験結果を検証します。
% er_print din_philo.1.er (er_print) deadlocks |
Deadlock #1, Potential deadlock
Thread #2
Lock being held: 0x215a0, at: grab_chopstick + 0x0000002C, line 106 in "din_philo.c"
Lock being requested: 0x215b8, at: grab_chopstick + 0x0000002C, line 106 in "din_philo.c"
Thread #3
Lock being held: 0x215b8, at: grab_chopstick + 0x0000002C, line 106 in "din_philo.c"
Lock being requested: 0x215d0, at: grab_chopstick + 0x0000002C, line 106 in "din_philo.c"
Thread #4
Lock being held: 0x215d0, at: grab_chopstick + 0x0000002C, line 106 in "din_philo.c"
Lock being requested: 0x215e8, at: grab_chopstick + 0x0000002C, line 106 in "din_philo.c"
Thread #5
Lock being held: 0x215e8, at: grab_chopstick + 0x0000002C, line 106 in "din_philo.c"
Lock being requested: 0x21600, at: grab_chopstick + 0x0000002C, line 106 in "din_philo.c"
Thread #6
Lock being held: 0x21600, at: grab_chopstick + 0x0000002C, line 106 in "din_philo.c"
Lock being requested: 0x215a0, at: grab_chopstick + 0x0000002C, line 106 in "din_philo.c"
Deadlock #2, Actual deadlock
Thread #2
Lock being held: 0x215a0, at: grab_chopstick + 0x0000002C, line 106 in "din_philo.c"
Lock being requested: 0x215b8, at: grab_chopstick + 0x0000002C, line 106 in "din_philo.c"
Thread #3
Lock being held: 0x215b8, at: grab_chopstick + 0x0000002C, line 106 in "din_philo.c"
Lock being requested: 0x215d0, at: grab_chopstick + 0x0000002C, line 106 in "din_philo.c"
Thread #4
Lock being held: 0x215d0, at: grab_chopstick + 0x0000002C, line 106 in "din_philo.c"
Lock being requested: 0x215e8, at: grab_chopstick + 0x0000002C, line 106 in "din_philo.c"
Thread #5
Lock being held: 0x215e8, at: grab_chopstick + 0x0000002C, line 106 in "din_philo.c"
Lock being requested: 0x21600, at: grab_chopstick + 0x0000002C, line 106 in "din_philo.c"
Thread #6
Lock being held: 0x21600, at: grab_chopstick + 0x0000002C, line 106 in "din_philo.c"
Lock being requested: 0x215a0, at: grab_chopstick + 0x0000002C, line 106 in "din_philo.c"
Deadlocks List Summary: Experiment: din_philo.1.er Total Deadlocks: 2
(er_print)
次のスクリーンショットは、スレッドアナライザで表示されたデッドロック情報を示します。
図 3–2 din_philo.c で検出されたデッドロック
スレッドアナライザは、din_philo.c の 2 つのデッドロックを報告します (1 つは潜在的デッドロック、もう 1 つは実デッドロック)。より詳しく調べると、2 つのデッドロックは同一であるとわかります。
デッドロックに関する巡回チェーンは次のとおりです。
|
スレッド 2: アドレス |
|
スレッド 3: アドレス |
|
スレッド 4: アドレス |
|
スレッド 5: アドレス |
|
スレッド 6: アドレス |
チェーン内の最初のスレッド (スレッド #2) を選択し、続いて「デュアルソース (Dual Source)」タブをクリックすると、スレッド #2 がアドレス 0x215a0 でロックを保持していたソースコード内の位置と、アドレス 0x215b8 でロックを要求したソースコード内の位置が表示されます。次のスクリーンショットには、スレッド #2 の「デュアルソース (Dual Source)」タブが示されています。デフォルトのメトリック (排他的デッドロックメトリック) が各ソース行の左側に表示されます。このメトリックは、デッドロックに関与したロック保持またはロック要求オペレーションが、その行で報告された回数を示します。
図 3–3 din_philo.c での潜在的デッドロック
3.5.2 潜在的デッドロックがあるにもかかわらず完了した実行の検証
十分に大きな休眠引数を指定した場合、食事する哲学者プログラムは、実デッドロックを回避でき、通常どおりに終了します。ただし、通常どおりに終了したからといって、プログラムにデッドロックがないことを意味するわけではありません。単に、保持されたロックと要求されたロックが、所与の実行中にデッドロックチェーンを形成しなかったことを意味するだけです。他の実行でタイミングが変更すれば、実デッドロックが生じる可能性があります。次のリストは、40 秒の休眠時間によって、通常どおりに終了する食事する哲学者プログラムの実行を示しています。ただし、er_print ユーティリティとスレッドアナライザは潜在的デッドロックを報告します。
% cc -g -o din_philo_pt din_philo.c % collect -r deadlock -o din_philo_pt.1.er din_philo_pt 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 left chopstick 1 Philosopher 0: eating. Philosopher 0: got right chopstick 0 Philosopher 2: got left chopstick 3 Philosopher 2: 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. % Execution terminated normally |
太字で示された次のコマンドを入力して、er_print ユーティリティで実験結果を検証します。
% er_print din_philo_pt.1.er
(er_print) deadlocks
Deadlock #1, Potential deadlock
Thread #2
Lock being held: 0x215a0, at: grab_chopstick + 0x0000002C, line 106 in "din_philo.c"
Lock being requested: 0x215b8, at: grab_chopstick + 0x0000002C, line 106 in "din_philo.c"
Thread #3
Lock being held: 0x215b8, at: grab_chopstick + 0x0000002C, line 106 in "din_philo.c"
Lock being requested: 0x215d0, at: grab_chopstick + 0x0000002C, line 106 in "din_philo.c"
Thread #4
Lock being held: 0x215d0, at: grab_chopstick + 0x0000002C, line 106 in "din_philo.c"
Lock being requested: 0x215e8, at: grab_chopstick + 0x0000002C, line 106 in "din_philo.c"
Thread #5
Lock being held: 0x215e8, at: grab_chopstick + 0x0000002C, line 106 in "din_philo.c"
Lock being requested: 0x21600, at: grab_chopstick + 0x0000002C, line 106 in "din_philo.c"
Thread #6
Lock being held: 0x21600, at: grab_chopstick + 0x0000002C, line 106 in "din_philo.c"
Lock being requested: 0x215a0, at: grab_chopstick + 0x0000002C, line 106 in "din_philo.c"
Deadlocks List Summary: Experiment: din_philo_pt.1.er Total Deadlocks: 1
(er_print)
|
Deadlock #1, Potential deadlock
Thread #2
Lock being held: 0x215a0, at: grab_chopstick + 0x0000002C, line 106 in "din_philo.c"
Lock being requested: 0x215b8, at: grab_chopstick + 0x0000002C, line 106 in "din_philo.c"
Thread #3
Lock being held: 0x215b8, at: grab_chopstick + 0x0000002C, line 106 in "din_philo.c"
Lock being requested: 0x215d0, at: grab_chopstick + 0x0000002C, line 106 in "din_philo.c"
Thread #4
Lock being held: 0x215d0, at: grab_chopstick + 0x0000002C, line 106 in "din_philo.c"
Lock being requested: 0x215e8, at: grab_chopstick + 0x0000002C, line 106 in "din_philo.c"
Thread #5
Lock being held: 0x215e8, at: grab_chopstick + 0x0000002C, line 106 in "din_philo.c"
Lock being requested: 0x21600, at: grab_chopstick + 0x0000002C, line 106 in "din_philo.c"
Thread #6
Lock being held: 0x21600, at: grab_chopstick + 0x0000002C, line 106 in "din_philo.c"
Lock being requested: 0x215a0, at: grab_chopstick + 0x0000002C, line 106 in "din_philo.c"
Deadlocks List Summary: Experiment: din_philo_pt.1.er Total Deadlocks: 1
(er_print)
次のスクリーンショットには、スレッドアナライザインタフェースでの潜在的デッドロック情報が示されています。
図 3–4 din_philo.c での潜在的デッドロック
3.6 デッドロックの修正と誤検知について
潜在的デッドロックと実デッドロックを取り除くには、哲学者は食事しようとする前にトークンを受け取る必要があるとするトークンのシステムを使用した方法があります。使用可能なトークンの数は、テーブルの哲学者の人数より少なくする必要があります。哲学者はトークンを受け取ると、テーブルのルールに従って食事できます。それぞれの哲学者は食事が終わればトークンを返し、プロセスを繰り返します。次の擬似コードは、トークンシステムを使用したときの、各哲学者のロジックを示します。
while (there is still food on the table)
{
get token
grab right fork
grab left fork
eat some food
put down left fork
put down right fork
return token
}
以降の節では、トークンのシステムの 2 つの異なる実装について詳しく説明します。
3.6.1 トークンを使用した哲学者の規制
次のリストは、トークンシステムを使用する修正バージョンの食事する哲学者プログラムを示します。このソリューションには 4 つのトークン (食事する人数より 1 少ない) が組み入れられ、したがって同時に 4 人の哲学者しか食事できません。このバージョンのプログラムは din_philo_fix1.c と呼ばれます。
ヒント –
/opt/solstudio12.2/prod/examples/tha/din_philo または /opt/oracle/solstudio12.2/prod/examples/tha/din_philo ディレクトリから din_philo_fix1.c をコピーします。
1 /*
2 * Copyright (c) 2006, 2010, Oracle and/or its affiliates. All Rights Reserved.
3 * @(#)din_philo_fix1.c 1.3 (Oracle) 10/03/26
4 */
5
6 #include <pthread.h>
7 #include <stdio.h>
8 #include <unistd.h>
9 #include <stdlib.h>
10 #include <errno.h>
11 #include <assert.h>
12
13 #define PHILOS 5
14 #define DELAY 5000
15 #define FOOD 100
16
17 void *philosopher (void *id);
18 void grab_chopstick (int,
19 int,
20 char *);
21 void down_chopsticks (int,
22 int);
23 int food_on_table ();
24 void get_token ();
25 void return_token ();
26
27 pthread_mutex_t chopstick[PHILOS];
28 pthread_t philo[PHILOS];
29 pthread_mutex_t food_lock;
30 pthread_mutex_t num_can_eat_lock;
31 int sleep_seconds = 0;
32 uint32_t num_can_eat = PHILOS - 1;
33
34
35 int
36 main (int argn,
37 char **argv)
38 {
39 int i;
40
41 pthread_mutex_init (&food_lock, NULL);
42 pthread_mutex_init (&num_can_eat_lock, NULL);
43 for (i = 0; i < PHILOS; i++)
44 pthread_mutex_init (&chopstick[i], NULL);
45 for (i = 0; i < PHILOS; i++)
46 pthread_create (&philo[i], NULL, philosopher, (void *)i);
47 for (i = 0; i < PHILOS; i++)
48 pthread_join (philo[i], NULL);
49 return 0;
50 }
51
52 void *
53 philosopher (void *num)
54 {
55 int id;
56 int i, left_chopstick, right_chopstick, f;
57
58 id = (int)num;
59 printf ("Philosopher %d is done thinking and now ready to eat.\n", id);
60 right_chopstick = id;
61 left_chopstick = id + 1;
62
63 /* Wrap around the chopsticks. */
64 if (left_chopstick == PHILOS)
65 left_chopstick = 0;
66
67 while (f = food_on_table ()) {
68 get_token ();
69
70 grab_chopstick (id, right_chopstick, "right ");
71 grab_chopstick (id, left_chopstick, "left");
72
73 printf ("Philosopher %d: eating.\n", id);
74 usleep (DELAY * (FOOD - f + 1));
75 down_chopsticks (left_chopstick, right_chopstick);
76
77 return_token ();
78 }
79
80 printf ("Philosopher %d is done eating.\n", id);
81 return (NULL);
82 }
83
84 int
85 food_on_table ()
86 {
87 static int food = FOOD;
88 int myfood;
89
90 pthread_mutex_lock (&food_lock);
91 if (food > 0) {
92 food--;
93 }
94 myfood = food;
95 pthread_mutex_unlock (&food_lock);
96 return myfood;
97 }
98
99 void
100 grab_chopstick (int phil,
101 int c,
102 char *hand)
103 {
104 pthread_mutex_lock (&chopstick[c]);
105 printf ("Philosopher %d: got %s chopstick %d\n", phil, hand, c);
106 }
107
108
109
110 void
111 down_chopsticks (int c1,
112 int c2)
113 {
114 pthread_mutex_unlock (&chopstick[c1]);
115 pthread_mutex_unlock (&chopstick[c2]);
116 }
117
118
119 void
120 get_token ()
121 {
122 int successful = 0;
123
124 while (!successful) {
125 pthread_mutex_lock (&num_can_eat_lock);
126 if (num_can_eat > 0) {
127 num_can_eat--;
128 successful = 1;
129 }
130 else {
131 successful = 0;
132 }
133 pthread_mutex_unlock (&num_can_eat_lock);
134 }
135 }
136
137 void
138 return_token ()
139 {
140 pthread_mutex_lock (&num_can_eat_lock);
141 num_can_eat++;
142 pthread_mutex_unlock (&num_can_eat_lock);
143 }
この修正バージョンの食事する哲学者プログラムをコンパイルし、複数回それを実行してみます。トークンのシステムは、箸を使用して食事しようとする人の人数を制限し、これによって実デッドロックおよび潜在的デッドロックを回避します。
コンパイルするには、次のコマンドを使用します。
cc -g -o din_philo_fix1 din_philo_fix1.c |
実験結果を収集する
collect -r deadlock din_philo_fix1 -o din_philo_fix1.1.er |
3.6.1.1 誤検知レポート
トークンのシステムを使用するときでも、スレッドアナライザは、まったく存在していないのにこの実装の潜在的デッドロックを報告します。これが誤検知です。潜在的デッドロックについて詳しく説明した次のスクリーンショットを見てください。
図 3–5 潜在的デッドロックの誤検知レポート
チェーンの最初のスレッド (スレッド #2) を選択し、「デュアルソース (Dual Source)」タブをクリックして、スレッド #2 がアドレス 0x216a8 でロックを保持していたソースコード位置と、アドレス 0x216c0 でロックを要求したソースコードでの位置を確認します。次の図には、スレッド #2 の「デュアルソース (Dual Source)」タブが示されています。
図 3–6 誤検知の潜在的デッドロックのソース
din_philo_fix1.c の get_token() 関数は、while ループを使用してスレッドを同期します。スレッドは、トークンの取得に成功するまで、while ループ外に出ません (これは、num_can_eat が 0 より大きいときに起こります)。while ループは同時に食事する人を 4 人に制限します。ただし、while ループによって実装された同期は、スレッドアナライザには認識されません。スレッドアナライザは、5 人の哲学者全員が同時に箸を掴んで食事しようとしていると想定しているので、潜在的デッドロックを報告します。次の節では、スレッドアナライザが認識する同期を使用することによって、同時に食事する人の人数を制限する方法について詳しく説明します。
3.6.2 トークンの代替システム
次のリストには、トークンのシステムを実装する代替方法が示されています。この実装方法でも 4 つのトークンを使用するので、同時に 4 人しか食事しようとしません。ただし、この実装方法は、sem_wait() と sem_post() セマフォールーチンを使用して、食事する哲学者の人数を制限します。このバージョンのソースファイルは din_philo_fix2.c と呼ばれます。
ヒント –
/opt/sunstudio12.2/prod/examples/tha/din_philo または /opt/oracle/solstudio12.2/prod/examples/tha/din_philo ディレクトリから、din_philo_fix2.c をコピーします。
次のリストでは、din_philo_fix2.c について詳しく説明します。
1 /*
2 * Copyright (c) 2006, 2010, Oracle and/or its affiliates. All Rights Reserved.
3 * @(#)din_philo_fix2.c 1.3 (Oracle) 10/03/26
4 */
5
6 #include <pthread.h>
7 #include <stdio.h>
8 #include <unistd.h>
9 #include <stdlib.h>
10 #include <errno.h>
11 #include <assert.h>
12 #include <semaphore.h>
13
14 #define PHILOS 5
15 #define DELAY 5000
16 #define FOOD 100
17
18 void *philosopher (void *id);
19 void grab_chopstick (int,
20 int,
21 char *);
22 void down_chopsticks (int,
23 int);
24 int food_on_table ();
25 void get_token ();
26 void return_token ();
27
28 pthread_mutex_t chopstick[PHILOS];
29 pthread_t philo[PHILOS];
30 pthread_mutex_t food_lock;
31 int sleep_seconds = 0;
32 sem_t num_can_eat_sem;
33
34
35 int
36 main (int argn,
37 char **argv)
38 {
39 int i;
40
41 pthread_mutex_init (&food_lock, NULL);
42 sem_init(&num_can_eat_sem, 0, PHILOS - 1);
43 for (i = 0; i < PHILOS; i++)
44 pthread_mutex_init (&chopstick[i], NULL);
45 for (i = 0; i < PHILOS; i++)
46 pthread_create (&philo[i], NULL, philosopher, (void *)i);
47 for (i = 0; i < PHILOS; i++)
48 pthread_join (philo[i], NULL);
49 return 0;
50 }
51
52 void *
53 philosopher (void *num)
54 {
55 int id;
56 int i, left_chopstick, right_chopstick, f;
57
58 id = (int)num;
59 printf ("Philosopher %d is done thinking and now ready to eat.\n", id);
60 right_chopstick = id;
61 left_chopstick = id + 1;
62
63 /* Wrap around the chopsticks. */
64 if (left_chopstick == PHILOS)
65 left_chopstick = 0;
66
67 while (f = food_on_table ()) {
68 get_token ();
69
70 grab_chopstick (id, right_chopstick, "right ");
71 grab_chopstick (id, left_chopstick, "left");
72
73 printf ("Philosopher %d: eating.\n", id);
74 usleep (DELAY * (FOOD - f + 1));
75 down_chopsticks (left_chopstick, right_chopstick);
76
77 return_token ();
78 }
79
80 printf ("Philosopher %d is done eating.\n", id);
81 return (NULL);
82 }
83
84 int
85 food_on_table ()
86 {
87 static int food = FOOD;
88 int myfood;
89
90 pthread_mutex_lock (&food_lock);
91 if (food > 0) {
92 food--;
93 }
94 myfood = food;
95 pthread_mutex_unlock (&food_lock);
96 return myfood;
97 }
98
99 void
100 grab_chopstick (int phil,
101 int c,
102 char *hand)
103 {
104 pthread_mutex_lock (&chopstick[c]);
105 printf ("Philosopher %d: got %s chopstick %d\n", phil, hand, c);
106 }
107
108 void
109 down_chopsticks (int c1,
110 int c2)
111 {
112 pthread_mutex_unlock (&chopstick[c1]);
113 pthread_mutex_unlock (&chopstick[c2]);
114 }
115
116
117 void
118 get_token ()
119 {
120 sem_wait(&num_can_eat_sem);
121 }
122
123 void
124 return_token ()
125 {
126 sem_post(&num_can_eat_sem);
127 }
この新しい実装方法は、セマフォー 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() の呼び出しを認識し、哲学者全員が同時に食事しようとしているわけではないと判断します。
注 –
適切なセマフォールーチンとリンクするように、-lrt を付けて din_philo_fix2.c をコンパイルする必要があります。
din_philo_fix2.c をコンパイルするには、次のコマンドを使用します。
cc -g -lrt -o din_philo_fix2 din_philo_fix2.c |
プログラム din_philo_fix2 のこの新しい実装方法を複数回実行すると、どの場合も通常どおり終了し、ハングアップしないことがわかります。
この新しいバイナリで実験を作成する
collect -r deadlock -o din_philo_fix2.1.er din_philo_fix2 |
次の図に示すように、din_philo_fix2.1.er の実験結果から、スレッドアナライザが実デッドロックも潜在的デッドロックも報告していないことがわかります。
図 3–7 din_philo_fix2.c で報告されないデッドロック
スレッドアナライザが認識するスレッドおよびメモリー割り当て API のリストについては、付録 A スレッドアナライザで認識される APIを参照してください。
- © 2010, Oracle Corporation and/or its affiliates