哲学家进餐问题
目录
问题描述 #
有五个哲学家，他们的生活方式是交替地进行思考和进餐，哲学家们共用一张圆桌，分别坐在周围的五张椅子上，在圆桌上有五个碗和五支筷子，平时哲学家进行思考，饥饿时便试图取其左、右最靠近他的筷子，只有在他拿到两支筷子时才能进餐，该哲学家进餐完毕后，放下左右两只筷子又继续思考。
约束条件如下：
- 只有拿到两只筷子时，哲学家才能吃饭。
- 如果筷子已被别人拿走，则必须等别人吃完之后才能拿到筷子。
- 任一哲学家在自己未拿到两只筷子吃完饭前，不会放下手中已经拿到的筷子。
解决方案 #
当哲学家饥饿时，总是先去拿他左边的筷子，执行wait(chopstick[I])，成功后，再去拿他右边的筷子，执行wait(chopstick[I+1]%5)；成功后便可进餐。进餐毕，先放下他左边的筷子，然后再放下右边的筷子。当五个哲学家同时去取他左边的筷子，每人拿到一只筷子且不释放，即五个哲学家只得无限等待下去，引起死锁。
信号量解决 #
- 至多允许四位哲学家进餐，将最后一个哲学家停止申请资源，断开环路。最终能保证有一位哲学家能进餐，用完释放两只筷子，从而使更多的哲学家能够进餐。增加一个信号量定义semaphore count=4。
- 奇数号哲学家先拿他左边的筷子，偶数号哲学家先拿他右边的筷子。这样破坏了同方向环路，一个哲学家拿到一只筷子后，就阻止了他邻座的一个哲学家吃饭。
管程法解决 #
在用信号量机制解决同步问题时，往往比较繁琐，采用面向对象的思想，将资源及资源的共享操作封装起来，用管程来管理，实现哲学家进餐问题，使用起来更加方便。
原理：不是对每只筷子设置信号量，而是对每个哲学家设置信号量。
test()函数有以下作用：
- 如果当前处理的哲学家处于饥饿状态并且两侧的哲学家不在吃饭状态，则当前哲学家通过
test函数试图进入吃饭状态。 - 如果通过
test进入吃饭状态不成功，那么当前的哲学家就在该信号量阻塞等待。直到其他哲学家进程通过test将该哲学家的状态设置为eating - 当一个哲学家进程调用
put_forks放下筷子时，会通过test测试它的邻居，如果邻居处于饥饿状态，且该邻居的邻居不在吃饭状态，则该邻居进入吃饭状态
由上，该算法不会出现死锁。但是该算法会出现某个哲学家始终无法吃饭的情况。即当该哲学家的左右两个哲学家交替处在吃饭的状态的时候，则该哲学家始终无法进入吃饭状态。
但是该算法可以实现对于任意多位哲学家的情况都能获得最大的并行度，因此具有重要的意义。