哲学家就餐问题 Dining philosophers problem #经典问题

不二如是

是在计算机科学中的一个经典问题，用来演示在并发计算中多线程同步（Synchronization）时产生的问题。

由著名的计算机科学家艾兹格·迪科斯彻提出了一个同步问题，即假设有五台计算机都试图访问五份共享的磁带驱动器。

稍后，这个问题被托尼·霍尔重新表述为哲学家就餐问题。

这个问题可以用来解释死锁和资源耗尽。

1965年，Dijkstra提出并解决了一个他称之为哲学家就餐的同步问题。

从那时起，每个发明新的同步原语的人都希望通过解决哲学家就餐问题来展示其同步原语的精妙之处。

这个问题可以简单地描述如下：五个哲学家围坐在一张圆桌周围，每个哲学家面前都有一盘通心粉。

由于通心粉很滑，所以需要两把叉子才能夹住。

相邻两个盘子之间放有一把叉子，餐桌如上图所示。

哲学家的生活中有两种交替活动时段：即吃饭和思考（这只是一种抽象，即对哲学家而言其他活动都无关紧要）。

当一个哲学家觉得饿了时，他就试图分两次去取其左边和右边的叉子，每次拿一把，但不分次序。

如果成功地得到了两把叉子，就开始吃饭，吃完后放下叉子继续思考。

关键问题是：能为每一个哲学家写一段描述其行为的程序，且决不会死锁吗？

要求拿两把叉子是人为规定的。

给你个直观的程序解法：

1. #define N 5 //哲学家数目
   
2. 
   
3. void Philosopher(int,i) // i,哲学家编号 ，[0,4]
   
4. {
   
5.         while(TRUE)
   
6.         {
   
7.                 think();                //哲学家思考
   
8.                 take_fork(i);        //拿起左边叉子
   
9.                 take_fork((i+1) % N);        //拿起右边叉子，%模运算
   
10.                 eat();                        //吃
    
11.                 put_fork(i);        ／/将左叉子放回桌上
    
12.                 put_fork((i+1) % N);        //将右叉子放回桌上
    
13.         }
    
14. }

复制代码

过程take_fork将一直等到所指定的叉子可用，然后将其取用。

不过，这种显然的解法是错误的。

如果五位哲学家同时拿起左面的叉子，就没有人能够拿到他们右面的叉子，于是发生死锁。

“如果哲学家在拿不到右边叉子时等待一段随机时间，而不是等待相同的时间。

这样发生互锁的可能性就很小了，事情就可以继续了。”

这种想法是对的，而且在几乎所有的应用程序中，稍后再试的办法并不会演化成为一个问题。

例如，在流行的局域网以太网中，如果两台计算机同时发送包，那么每台计算机等待一段随机时间之后再尝试。

在实践中，该方案工作良好。

但是，在少数的应用中，人们希望有一种能够始终工作的方案。

它不能因为一串不可靠的随机数字而导致失败（想象一下核电站中的安全控制系统）。

做如下改进，它既不会发生死锁又不会产生饥饿：使用一个二元信号量对调用think之后的五个语句进行保护。

在开始拿叉子之前，哲学家先对互斥量 mutex执行down操作。

在放回叉子后，他再对mutex执行up操作。

从理论上讲，这种解法是可行的。

但从实际角度来看，这里有性能上的局限：在任何一时刻只能有一位哲学家进餐。

而五把叉子实际上可以允许两位哲学家同时进餐。

1. #define N 5 //哲学家数目
   
2. #define LEFT (i+N-1)%N  //i的左邻居编号
   
3. #define RIGHT(i+1)%N-1  //i的右邻居编号
   
4. #define THINKING 0                 //哲学家思考
   
5. #define HUNGRY 1                 //哲学家是图拿起叉子
   
6. #define EATING 2        //哲学家进餐
   
7. 
   
8. typedef in semaphore;         //信号量是一种特殊的整形数据
   
9. int state(N);                        //数组用来跟踪记录每位哲学家的状态
   
10. semaphore mutex=1;      //临界区的互斥
    
11. 
    
12. void Philosopher(int,i) // i,哲学家编号 ，[0,N-1]
    
13. {
    
14.         while(TRUE)         //无限循环
    
15.         {}
    
16. }
    
17. 
    
18. void take_forks(int i) // i,哲学家编号 ，[0,N-1]
    
19. {
    
20.         down(&mutex);                //进入临界区
    
21.         state[i] = HUNGRY;         //记录哲学家i处于饥饿状态
    
22.         test(i);                        //尝试获取两把叉子
    
23.         up(&mutex);                        //离开临界区
    
24.         down(&s[i]);                //如果得不到需要的叉子测阻塞
    
25. }
    
26. 
    
27. void put_forks(i)                // i,哲学家编号 ，[0,N-1]
    
28. {
    
29.         down(&mutex);                //进入临界区
    
30.         state[i] = THINKING;／／哲学家已经就餐完毕
    
31.         test(LEFT);                        //检查左边的邻居现在可以吃吗
    
32.         test(RIGHT);                //检查右边的邻居现在可以吃吗
    
33.         up(&mutex);                        //离开临界区
    
34. }
    
35. 
    
36. void test(i)
    
37. {
    
38.         if(statep[i] == HUNGRY && state[LEFT] != EATING $ state[RIGHT] != EATING)
    
39.         {
    
40.         state[i] = EATING;
    
41.         up(&s[i]);
    
42.         }
    
43. }

复制代码

该程序使用了一个信号量数组，每个信号量对应一位哲学家，这样在所需的叉子被占用时，想进餐的哲学家就被阻塞。

注意，每个进程将过程philosopher作为主代码运行。

而其他过程take_forks、put_forks和test只是普通的过程，而非单独的进程。