デッドロックの修正と誤検知について
潜在的デッドロックと実デッドロックを取り除くには、哲学者は食事しようとする前にトークンを受け取る必要があるとするトークンのシステムを使用した方法があります。使用可能なトークンの数は、テーブルの哲学者の人数より少なくする必要があります。哲学者はトークンを受け取ると、テーブルのルールに従って食事できます。それぞれの哲学者は食事が終わればトークンを返し、プロセスを繰り返します。次の擬似コードは、トークンシステムを使用したときの、各哲学者のロジックを示します。
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 つの異なる実装について詳しく説明します。
トークンを使用した哲学者の規制
次のリストは、トークンシステムを使用する修正バージョンの食事する哲学者プログラムを示します。このソリューションには 4 つのトークン (食事する人数より 1 少ない) が組み入れられ、したがって同時に 4 人の哲学者しか食事できません。このバージョンのプログラムは din_philo_fix1.c と呼ばれます。
ヒント - サンプルアプリケーションをダウンロードした場合、din_philo_fix1.c ファイルを OracleDeveloperStudio12.5-Samples/ThreadAnalyzer/din_philo ディレクトリからコピーできます。
1 /*
2 * Copyright (c) 2006, 2011, Oracle and/or its affiliates. All Rights Reserved.
3 */
4
5 #include <pthread.h>
6 #include <stdio.h>
7 #include <unistd.h>
8 #include <stdlib.h>
9 #include <errno.h>
10 #include <assert.h>
11
12 #ifdef __linux__
13 #include <stdint.h>
14 #endif
15
16 #define PHILOS 5
17 #define DELAY 5000
18 #define FOOD 100
19
20 void *philosopher (void *id);
21 void grab_chopstick (int,
22 int,
23 char *);
24 void down_chopsticks (int,
25 int);
26 int food_on_table ();
27 int get_token ();
28 void return_token ();
29
30 pthread_mutex_t chopstick[PHILOS];
31 pthread_t philo[PHILOS];
32 pthread_mutex_t food_lock;
33 pthread_mutex_t num_can_eat_lock;
34 int sleep_seconds = 0;
35 uint32_t num_can_eat = PHILOS - 1;
36
37
38 int
39 main (int argn,
40 char **argv)
41 {
42 int i;
43
44 pthread_mutex_init (&food_lock, NULL);
45 pthread_mutex_init (&num_can_eat_lock, NULL);
46 for (i = 0; i < PHILOS; i++)
47 pthread_mutex_init (&chopstick[i], NULL);
48 for (i = 0; i < PHILOS; i++)
49 pthread_create (&philo[i], NULL, philosopher, (void *)i);
50 for (i = 0; i < PHILOS; i++)
51 pthread_join (philo[i], NULL);
52 return 0;
53 }
54
55 void *
56 philosopher (void *num)
57 {
58 int id;
59 int i, left_chopstick, right_chopstick, f;
60
61 id = (int)num;
62 printf ("Philosopher %d is done thinking and now ready to eat.\n", id);
63 right_chopstick = id;
64 left_chopstick = id + 1;
65
66 /* Wrap around the chopsticks. */
67 if (left_chopstick == PHILOS)
68 left_chopstick = 0;
69
70 while (f = food_on_table ()) {
71 get_token ();
72
73 grab_chopstick (id, right_chopstick, "right ");
74 grab_chopstick (id, left_chopstick, "left");
75
76 printf ("Philosopher %d: eating.\n", id);
77 usleep (DELAY * (FOOD - f + 1));
78 down_chopsticks (left_chopstick, right_chopstick);
79
80 return_token ();
81 }
82
83 printf ("Philosopher %d is done eating.\n", id);
84 return (NULL);
85 }
86
87 int
88 food_on_table ()
89 {
90 static int food = FOOD;
91 int myfood;
92
93 pthread_mutex_lock (&food_lock);
94 if (food > 0) {
95 food--;
96 }
97 myfood = food;
98 pthread_mutex_unlock (&food_lock);
99 return myfood;
100 }
101
102 void
103 grab_chopstick (int phil,
104 int c,
105 char *hand)
106 {
107 pthread_mutex_lock (&chopstick[c]);
108 printf ("Philosopher %d: got %s chopstick %d\n", phil, hand, c);
109 }
110
111
112
113 void
114 down_chopsticks (int c1,
115 int c2)
116 {
117 pthread_mutex_unlock (&chopstick[c1]);
118 pthread_mutex_unlock (&chopstick[c2]);
119 }
120
121
122 int
123 get_token ()
124 {
125 int successful = 0;
126
127 while (!successful) {
128 pthread_mutex_lock (&num_can_eat_lock);
129 if (num_can_eat > 0) {
130 num_can_eat--;
131 successful = 1;
132 }
133 else {
134 successful = 0;
135 }
136 pthread_mutex_unlock (&num_can_eat_lock);
137 }
138 }
139
140 void
141 return_token ()
142 {
143 pthread_mutex_lock (&num_can_eat_lock);
144 num_can_eat++;
145 pthread_mutex_unlock (&num_can_eat_lock);
146 }この修正バージョンの食事する哲学者プログラムをコンパイルし、複数回それを実行してみます。トークンのシステムは、箸を使用して食事しようとする人の人数を制限し、これによって実デッドロックおよび潜在的デッドロックを回避します。
コンパイルするには、次のコマンドを使用します。
% cc -g -o din_philo_fix1 din_philo_fix1.c
実験結果を収集する
% collect -r deadlock -o din_philo_fix1.1.er din_philo_fix1
誤検知レポート
トークンのシステムを使用するときでも、スレッドアナライザは、まったく存在していない場合にもこの実装の潜在的デッドロックを報告します。これが誤検知です。潜在的デッドロックについて詳しく説明した次のスクリーンショットを見てください。
図 10 潜在的デッドロックの誤検知レポート
チェーンの最初のスレッド (スレッド #2) を選択し、「デュアルソース」ビューをクリックして、スレッド #2 がアドレス 0x216a8 でロックを保持していたソースコード位置と、アドレス 0x216c0 でロックを要求したソースコードでの位置を確認します。次の図には、スレッド #2 の「デュアルソース」ビューが示されています。
図 11 誤検知の潜在的デッドロックのソース
din_philo_fix1.c の get_token() 関数は、while ループを使用してスレッドを同期します。スレッドは、トークンの取得に成功するまで、while ループ外に出ません (これは、num_can_eat が 0 より大きいときに起こります)。while ループは同時に食事する人を 4 人に制限します。ただし、while ループによって実装された同期は、スレッドアナライザには認識されません。スレッドアナライザは、5 人の哲学者全員が同時に箸を掴んで食事しようとしていると想定しているので、潜在的デッドロックを報告します。次のセクションでは、スレッドアナライザが認識する同期を使用することによって、同時に食事する人の人数を制限する方法について詳しく説明します。
トークンの代替システム
次のリストには、トークンのシステムを実装する代替方法が示されています。この実装方法でも 4 つのトークンを使用するので、同時に 4 人しか食事しようとしません。ただし、この実装方法は、sem_wait() と sem_post() セマフォールーチンを使用して、食事する哲学者の人数を制限します。このバージョンのソースファイルは din_philo_fix2.c と呼ばれます。
ヒント - サンプルアプリケーションをダウンロードした場合、din_philo_fix2.c ファイルを OracleDeveloperStudio12.5-Samples/ThreadAnalyzer/din_philo ディレクトリからコピーできます。
次のリストでは、din_philo_fix2.c について詳しく説明します。
1 /*
2 * Copyright (c) 2006, 2011, Oracle and/or its affiliates. All Rights Reserved.
3 */
4
5 #include <pthread.h>
6 #include <stdio.h>
7 #include <unistd.h>
8 #include <stdlib.h>
9 #include <errno.h>
10 #include <assert.h>
11 #include <semaphore.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 int 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 int sleep_seconds = 0;
31 sem_t num_can_eat_sem;
32
33
34 int
35 main (int argn,
36 char **argv)
37 {
38 int i;
39
40 pthread_mutex_init (&food_lock, NULL);
41 sem_init(&num_can_eat_sem, 0, PHILOS - 1);
42 for (i = 0; i < PHILOS; i++)
43 pthread_mutex_init (&chopstick[i], NULL);
44 for (i = 0; i < PHILOS; i++)
45 pthread_create (&philo[i], NULL, philosopher, (void *)i);
46 for (i = 0; i < PHILOS; i++)
47 pthread_join (philo[i], NULL);
48 return 0;
49 }
50
51 void *
52 philosopher (void *num)
53 {
54 int id;
55 int i, left_chopstick, right_chopstick, f;
56
57 id = (int)num;
58 printf ("Philosopher %d is done thinking and now ready to eat.\n", id);
59 right_chopstick = id;
60 left_chopstick = id + 1;
61
62 /* Wrap around the chopsticks. */
63 if (left_chopstick == PHILOS)
64 left_chopstick = 0;
65
66 while (f = food_on_table ()) {
67 get_token ();
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 return_token ();
77 }
78
79 printf ("Philosopher %d is done eating.\n", id);
80 return (NULL);
81 }
82
83 int
84 food_on_table ()
85 {
86 static int food = FOOD;
87 int myfood;
88
89 pthread_mutex_lock (&food_lock);
90 if (food > 0) {
91 food--;
92 }
93 myfood = food;
94 pthread_mutex_unlock (&food_lock);
95 return myfood;
96 }
97
98 void
99 grab_chopstick (int phil,
100 int c,
101 char *hand)
102 {
103 pthread_mutex_lock (&chopstick[c]);
104 printf ("Philosopher %d: got %s chopstick %d\n", phil, hand, c);
105 }
106
107 void
108 down_chopsticks (int c1,
109 int c2)
110 {
111 pthread_mutex_unlock (&chopstick[c1]);
112 pthread_mutex_unlock (&chopstick[c2]);
113 }
114
115
116 int
117 get_token ()
118 {
119 sem_wait(&num_can_eat_sem);
120 }
121
122 void
123 return_token ()
124 {
125 sem_post(&num_can_eat_sem);
126 }
この新しい実装方法は、セマフォー 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 の実験から、スレッドアナライザが実デッドロックも潜在的デッドロックも報告していないことがわかります。
図 12 din_philo_fix2.c で報告されないデッドロック
スレッドアナライザが認識するスレッドおよびメモリー割り当て API のリストについては、スレッドアナライザで認識される APIを参照してください。