哲学家就餐问题的问题解法

如题所述

一个简单的解法是引入一个餐厅服务生,哲学家必须经过他的允许才能拿起餐叉。因为服务生知道哪只餐叉正在使用,所以他能够作出判断避免死锁。
为了演示这种解法,假设哲学家依次标号为A至E。如果A和C在吃东西,则有四只餐叉在使用中。B坐在A和C之间,所以两只餐叉都无法使用,而D和E之间有一只空余的餐叉。假设这时D想要吃东西。如果他拿起了第五只餐叉,就有可能发生死锁。相反,如果他征求服务生同意,服务生会让他等待。这样,我们就能保证下次当两把餐叉空余出来时,一定有一位哲学家可以成功的得到一对餐叉,从而避免了死锁。 另一个简单的解法是为资源(这里是餐叉)分配一个偏序或者分级的关系,并约定所有资源都按照这种顺序获取,按相反顺序释放,而且保证不会有两个无关资源同时被同一项工作所需要。在哲学家就餐问题中,资源(餐叉)按照某种规则编号为1至5,每一个工作单元(哲学家)总是先拿起左右两边编号较低的餐叉,再拿编号较高的。用完餐叉后,他总是先放下编号较高的餐叉,再放下编号较低的。在这种情况下,当四位哲学家同时拿起他们手边编号较低的餐叉时,只有编号最高的餐叉留在桌上,从而第五位哲学家就不能使用任何一只餐叉了。而且,只有一位哲学家能使用最高编号的餐叉,所以他能使用两只餐叉用餐。当他吃完后,他会先放下编号最高的餐叉,再放下编号较低的餐叉,从而让另一位哲学家拿起后边的这只开始吃东西。
尽管资源分级能避免死锁,但这种策略并不总是实用的,特别是当所需资源的列表并不是事先知道的时候。例如,假设一个工作单元拿着资源3和5,并决定需要资源2,则必须先要释放5,之后释放3,才能得到2,之后必须重新按顺序获取3和5。对需要访问大量数据库记录的计算机程序来说,如果需要先释放高编号的记录才能访问新的记录,那么运行效率就不会高,因此这种方法在这里并不实用。
这种方法经常是实际计算机科学问题中最实用的解法,通过为分级锁指定常量,强制获得锁的顺序,就可以解决这个问题。 1984年,K. Mani Chandy和J. Misra提出了哲学家就餐问题的另一个解法,允许任意的用户(编号P1, ..., Pn)争用任意数量的资源。与迪科斯彻的解法不同的是,这里编号可以是任意的。
1.对每一对竞争一个资源的哲学家,新拿一个餐叉,给编号较低的哲学家。每只餐叉都是“干净的”或者“脏的”。最初,所有的餐叉都是脏的。
2.当一位哲学家要使用资源(也就是要吃东西)时,他必须从与他竞争的邻居那里得到。对每只他当前没有的餐叉,他都发送一个请求。
3.当拥有餐叉的哲学家收到请求时,如果餐叉是干净的,那么他继续留着,否则就擦干净并交出餐叉。
4.当某个哲学家吃东西后,他的餐叉就变脏了。如果另一个哲学家之前请求过其中的餐叉,那他就擦干净并交出餐叉。
这个解法允许很大的并行性,适用于任意大的问题。

温馨提示:答案为网友推荐,仅供参考
相似回答