3.5 修复死锁并了解误报
除了哲人在开始进餐前等待的策略，我们还可以使用令牌机制，在该机制中，哲人必须在收到令牌后才能尝试进餐。可用令牌的数量必须少于餐桌前哲人的数量。当哲人收到令牌后，他可以按照餐桌规则尝试进餐。进餐后，每个哲人返还令牌并重复该过程。下列伪代码显示了使用令牌机制时每个哲人的逻辑：
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
}
以下部分将详细说明令牌机制的两种不同实现方法。
3.5.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 /* Wrap around the chopsticks. */
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 大于 0 时将发生这种情况）之前，线程不会离开 while 循环。while 循环将同时进餐的人数限制为 4。但是线程分析器无法识别 while 循环实现的同步。它假定所有 5 个哲人都尝试同时取筷子并进餐，因此报告了一个潜在死锁。下一部分将详细说明如何使用线程分析器可识别的同步限制同时进餐的人数。
3.5.2 另一种令牌机制
以下列表显示了令牌机制的另一种实现。该实现仍使用 4 个令牌，因此同时尝试进餐的人数不会超过 4 个。但是，该实现使用 sem_wait() 和 sem_post() 信号例程来限制进餐的哲人数量。该版本的源文件称为 din_philo_fix2.c。
注 –
必须使用 -lrt 编译 din_philo_fix2.c，以链接正确的信号例程。
以下列表详细说明了 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 /* Wrap around the chopsticks. */
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 初始化为 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