请教哲学家就餐的线程算法!

Question

1.大家都记得这个关于死锁的经典例子吧,就是说譬如:5个哲学家围坐在一个桌上,每个左右分别有一个叉子,每个哲学家就餐时就得先从左边然后到右边拿叉子.当思考的时候就放下左右两个叉子.
  现在的版本是:当哲学家用完叉子的时候,他们把叉子放在一个筷笼里.当哲学家要就餐的时候,他们就从筷笼里取出下两根可用的筷子.请问:这能消除死锁的可能吗?仅仅通过减少可用的筷子数目就能重新引入死锁吗?(我觉得第一个问题总是不会死锁.因为它已经缺少了循环等待资源这个条件,但从生活上又觉得这会死锁,真的迷糊了!)2.在一个餐馆中,假如:一个厨师,几个服务员,当有顾客来下订单时,服务员就得把订单交由该厨师.然后厨师把菜做好后就把原订单交给一个正在等待的服务员(可能几个服务员都在等,此时就用notifyAll()),但要指明是哪一个服务员区获得了订单.(这个问题希望大家能提供一个源码)
谢谢了!!

Answer 1

与生产者消费都有一定关系，但却已抽象成哲学家就餐问题了。如果按楼主描述的情况，绝对会死锁。典型的问题是这样描述的：五个哲学家，生活方式是交替地进行思考与吃饭。哲学家们共座一张桌面，分别座在五张椅子上。共有五个碗与五支筷子，平时一个哲学家思考，想吃饭时，就取其左右靠他最近的筷子。只有他拿到两支筷子才能吃饭。吃完后，把筷子放回原处，重新思考。如果五个哲学家同时（瞬间）想吃饭，这样无论使用信号量还是管程，都会死锁。
因此，如果使用记录型信号量，可以有几个解决办法：
1）至多四个哲学家同时吃饭。那一个就让他饿着。
2）判断，只有两根筷子同时可用时，才能拿起。
3）仅允许奇数号拿左边的筷子，其他的先拿右边的筷子。
这样可以如下解决：
var chopstick:array[0,1,2,3,4] of semaphore;所有信号量被初始化为1,第i个哲学家的活动可以描述为：
repeat
    wait(chopstick[i]);
    wait(chopstick[(i+1)mod5]);
    
    eat;    signal(chopstick[i]);
    signal(chopstick[(i+1)mod5]);    think;
util false;这样交替执行P，V操作就可以实现解决同步问题。也可以使用管程机制来实现。但是也需要引入一个新的数据结构：想吃饭状态。这样就有三种状态。
其他情况还要大家补充。