一种消除潜在死锁和实际死锁的方法是使用一种令牌机制,该机制要求哲学家必须收到令牌后才能尝试进餐。可用令牌的数量必须少于餐桌前哲学家的人数。当哲学家收到令牌后,他可以根据餐桌规则尝试进餐。每位哲学家在进餐后归还令牌,然后重复该过程。以下伪代码显示了使用令牌机制时每位哲学家的逻辑:
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 }
以下几节将详细介绍令牌机制的两种不同实现。
下面列出了使用令牌机制的哲学家就餐程序的修正版本。该解决方案结合了四个令牌,比就餐人数少一个,因此最多有四位哲学家可同时尝试进餐。该版本的程序称为 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 |
即使是使用令牌机制,线程分析器也会报告该实现存在潜在死锁(虽然并不存在死锁)。这是一个误报。请参考以下包含潜在死锁详细信息的屏幕抓图。
选择循环链中的第一个线程(线程 2),然后单击 "Dual Source"(双源)标签,可以看到线程 2 在地址 0x216a8
持有锁的对应源代码位置,以及该线程在 0x216c0
请求锁的对应源代码位置。下图显示了对应于线程 2 的 "Dual Source"(双源)标签。
din_philo_fix1.c 中的 get_token() 函数使用 while 循环来同步线程。线程在成功获得令牌之前不会离开 while
循环(当 num_can_eat
大于 0 时可成功获得令牌)。while
循环将同时就餐的人数限制为 4。但是,线程分析器无法识别由 while
循环实现的同步。它认为所有五位哲学家同时尝试抓取筷子并进餐,因此报告了一个潜在死锁。下一节将详细说明如何使用线程分析器可识别的同步来限制同时就餐的人数。
下面列出了令牌机制的另一种实现。该实现仍然使用四个令牌,所以最多有四个就餐者可同时尝试进餐。但是,该实现使用 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
初始化为 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 实验中的任何实际死锁或潜在死锁,如下图所示:
有关线程分析器可识别的线程和内存分配 API 的列表,请参见附录 A。