二、操作系统进程管理（11）——经典同步问题（5）哲学家进餐问题

1.哲学家进餐问题
    （1）问题描述：一张圆桌上坐着5名哲学家，每两个哲学家之间的桌子上摆一根筷子，桌子的中间是一碗米饭。哲学家们倾注毕生的精力用于思考和进餐，哲学家在思考时，并不影响他人。只有当哲学家饥饿时，才试图拿起左、右两根筷子（一根一根地拿起）。如果筷子已在他人手上，则需等待。饥饿的哲学家只有同时拿起两根筷子才可以开始进餐，当进餐完毕后，放下筷子继续思考。

    （2）关系分析。系统中5个哲学家进程，5位哲学家与左右邻居对其中间筷子的访问是互斥关系。

    （3）整理思路。这个问题中只有互斥关系，但与之前遇到的问题不同的是，每个哲学家进程需要同时持有两个临界资源才能开始吃饭。如何避免临界资源分配不当造成的死锁现象，是哲学家问题的精髓。

    （4）信号量设置。定义互斥信号量数组chopstick[5]={1,1,1,1,1}用于实现对5个筷子的互斥访问。并对哲学家按0~4编号，哲学家i左边的筷子编号位i，右边的筷子编号位（i+1）%5。

    （5）错误示范：如果5个哲学家并发地拿起了自己左手边的筷子，每位哲学家循环等待右边的人放下筷子（阻塞）。会发生"死锁"。

    （6）哲学家进餐死锁问题解决方案如下：

1. 最多允许四个哲学家同时进餐。这样可以保证至少有一个哲学家是可以拿到左右两只筷子的。
2. 要求奇数号哲学家先拿左边的筷子，然后再拿右边的筷子，而偶数号哲学家刚好相反。用这种方法可以保证如果相邻的两个奇偶号哲学家都想吃饭，那么只会有其中一个可以拿起第一只筷子，另一个会直接阻塞。这就避免了占有一支后再等待另一只的情况。
3. 仅当一个哲学家左右两支筷子都可用时才允许他抓起筷子。

思路三的实现如下：

semaphore chopstick[5]={1,1,1,1,1};
semaphore mutex = 1;     // 互斥地取筷子Pi (){                   //i号哲学家的进程while(1){P(mutex);P(chopstick[i]); // 拿左P(chopstick[(i+1)%5]); // 拿右V(mutex);吃饭…V(chopstick[i]); // 放左V(chopstick[(i+1)%5]); // 放右思考…}
}

思路分析：

假如0、2号哲学家进程想拿筷子：

0号哲学家进程先执行P(mutex)操作，然后执行P操作，拿起了左边的筷子，此时发生了进程切换，2号哲学家进餐执行P(mutex)操作，因为0号进程还没执行V(mutex)操作，2号进程阻塞。0号进程拿起右边筷子，并执行V(mutex)操作，2号进程被激活，顺利执行下面的操作。

 假如刚开始0号哲学家进程顺利执行，在吃饭：

如果此时1号进程也想吃饭，P(mutex)操作能顺利通过，但是当它尝试拿左边的筷子时，会发生阻塞。发生调度，2号进程也想吃饭，执行P(mutex)操作，但是此时1号进程还没有执行V(mutex)操作，还没有释放，所以此时2号进程会阻塞在P(mutex)。（虽然此时2号哲学家进程左右两边的筷子都可以用，但它依然拿不起左右两边的筷子）

假设哲学家0 拿到了筷子，后哲学家4想要尝试拿去筷子：

此时4号右边的筷子不可用，但4号仍然会先拿起左边的筷子并在等待右边的筷子。（具体分析和上面类似） 

因此这种方法并不能保证只有两边的筷子都可用时，才允许哲学家拿起筷子。

更准确的说法应该是：各哲学家拿筷子这件事必须互斥的执行。这就保证了即使一个哲学家在拿筷子拿到一半时被阻塞，也不会有别的哲学家会继续尝试拿筷子。这样的话，当前正在吃饭的哲学家放下筷子后，被阻塞的哲学家就可以获得等待的筷子了。

     （7）小结：哲学家进餐问题的关键在于解决进程死锁。（一个进程需要同时持有多个临界资源）

这些进程之间只存在互斥关系，但是与之前接触到的互斥关系不同的是，每个进程都需要同时持有两个临界资源，因此就有"死锁"问题的隐患。