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