哲人进餐方案是一个结构如下的经典方案:五个哲人,其编号为零到四,坐在圆桌旁思考。随着时间的推移,不同的个人感到饿了,决定去吃面条。桌子上有一个盛有面条的大浅盘,但是每个哲人只有一根筷子可以使用。为了吃面条,他们必须共用筷子。每个哲人左侧(哲人面向餐桌而坐)的筷子具有与该哲人相同的编号。
每个哲人首先去拿带有其编号的筷子。当他拿到指定给自己的筷子后,他将去拿指定给其邻桌的筷子。拿到两根筷子后,他就可以吃了。吃完后,他将筷子放回桌子上的原始位置,一侧放置一根。重复该过程,直到将面条吃完。
当每个哲人都持有他自己的筷子并等待邻座的筷子变为可用时,会发生实际死锁:
哲人 0 持有筷子 0,但等待筷子 1 |
哲人 1 持有筷子 1,但等待筷子 2 |
哲人 2 持有筷子 2,但等待筷子 3 |
哲人 3 持有筷子 3,但等待筷子 4 |
哲人 4 持有筷子 4,但等待筷子 0 |
在这种情况下,没有人可以吃,这些哲人处于死锁状态。多次重新运行该程序,您将看到该程序可能有时挂起,或有时运行直到完成。
运行哲人进餐程序,并查看它完成还是发生死锁。它可能挂起,如以下样例运行所示:
prompt% cc din_phil.c -mt 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
潜在死锁的一种可能解决方案是,哲人 1 在拿他的筷子之前先等待。就代码而言,可以让他在拿自己的筷子之前休眠指定的时间 (sleep_seconds)。如果他休眠的时间足够长,则程序可能完成而不会发生实际死锁。您可以将他休眠的秒数作为可执行程序的参数进行指定。如果您不指定参数,则哲人不休眠。
下列伪代码显示了每个哲人的逻辑:
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 秒,程序是如何运行的。程序运行直到完成,所有五个哲人都吃完了。
% 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
尝试运行几次该程序,指定不同的休眠参数。如果哲人在拿自己的筷子前仅等待很短的时间,会发生什么情况?如果他等待更长的时间,又会怎么样?尝试为可执行的 a.out 指定不同的休眠参数。将该程序重新运行几次,使用或不使用休眠参数。有时程序会挂起,有时则可以完成运行。程序是否挂起取决于线程的调度,以及线程请求锁定的时间。