《哲学家吃通心面包问题》由会员分享，可在线阅读，更多相关《哲学家吃通心面包问题（2页珍藏版）》请在金锄头文库上搜索。
1、哲学家吃通心面包哲学家就餐问题是在计算机科学中的一个经典问题，用来演示在 并行计算中多线程同步 （Synchronization）时产生的问题。在1971年，著名的计算机科学家艾兹格迪科斯彻提岀了一个同步问题，即假设有五台计算 机都试图访问五份共享的磁带驱动器。稍后，这个问题被托尼霍尔重新表述为哲学家就餐 问题。这个问题可以用来解释死锁和资源耗尽。问题描述哲学家就餐问题可以这样表述，假设有五位哲学家围坐在一张圆形餐桌旁，做以下两件事情 之一：吃饭，或者思考。吃东西的时候，他们就停止思考，思考的 时候也停止吃东西。餐 桌中间有一大碗意大利面，每两个哲学家之间有一只餐叉。因为用一只餐叉很难吃到意大
2、利 面，所以假设哲学家必须用两只餐叉吃东西。他们只能使用自己左右手边的那两只餐叉。 哲学家就餐问题有时也用米饭和筷子而不是意大利面和餐叉来描述，因为很明显，吃米饭必 须用两根筷子。哲学家就餐问题的演示哲学家从来不交谈，这就很危险，可能产生死锁,每个哲学家都拿着左手的餐叉，永远都在 等右边的餐叉（或者相反）。即使没有死锁，也有可能发生资源耗尽。例如，假设规定当哲学家等待另一只餐叉超过五 分钟后就放下自己手里的那一只餐叉，并且再等五分钟后进行下一次尝试。这个策略消除了 死锁（系统总会进入到下一个状态），但仍然有可能发生“活锁”。如果五位哲学家在完全相 同的时刻进入餐厅，并同时拿起左边的餐叉，那么这
3、些哲学家就会等待五分钟，同时放下手 中的餐叉，再等五分钟，又同时拿起这些餐叉。在实际的计算机问题中，缺乏餐叉可以类比为缺乏共享资源。一种常用的计算机技术是资源 加锁，用来保证在某个时刻，资源只能被一个程序或一段代码访问。当一个程序想要使用 的资源已经被另一个程序锁定，它就等待资源解锁。当多个程序涉及到加锁的资源时，在某 些情况下就有可能发生死锁。例如，某个程序需要访问两个文件，当两个这样的程序各锁 了一个文件，那它们都在等待对方解锁另一个文件，而这永远不会发生。解法服务生解法 一个简单的解法是引入一个餐厅服务生，哲学家必须经过他的允许才能拿起餐叉。因为服务 生知道哪只餐叉正在使用，所以他能够作
4、出判断避免死锁。为了演示这种解法，假设哲学家依次标号为A至E。如果A和C在吃东西，则有四只餐叉在 使用中。B坐在A和C之间，所以两只餐叉都无法使用，而D和E之间有一只空余的餐叉。 假设这时D想要吃东西。如果他拿起了第五只餐叉，就有可能发生死锁。相反，如果他征 求服务生同意，服务生会让他等待。这样，我们就 能保证下次当两把餐叉空余出来时，一 定有一位哲学家可以成功的得到一对餐叉，从而避免了死锁。资源分级解法另一个简单的解法是为资源（这里是餐叉）分配一个偏序或者分级的关系，并约定所有资 源都按照这种顺序获取，按相反顺序释放，而且保证不会有两个无关资源同时被同一项工作 所需要。在哲学家就餐问题中，资
5、源（餐 叉）按照某种规则编号为1至5,每一个工作单元 （哲学家）总是先拿起左右两边编号较低的餐叉，再拿编号较高的。用完餐叉后，他总是先 放下编号较高的餐叉，再放下编号较低的。在这种情况下，当四位哲学家同时拿起他们手 边编号较低的餐叉时，只有编号最高的餐叉留在桌上，从而第五位哲学家就不能使用任何一 只餐叉了。而且，只有一位哲学家能使用最高编号的餐叉，所以他能使用两只餐叉用餐。 当他吃完后，他会先放下编号最高的餐叉，再放下编号较低的餐叉，从而让另一位哲学家 拿起后边的这只开始吃东西。尽管资源分级能避免死锁，但这种策略并不总是实用的，特别是当所需资源的列表并不是事 先知道的时候。例如，假设一个工作单
6、元拿着资源3和5,并决定需要资源2,则必须先要释 放5,之后释放3,才能得到2,之后必须重新按顺序获取3和5。对需要访问大量数据库记录 的计算机程序来说，如果需要先释放高编号的记录才能访问新的记录，那么运行效率就不 会高，因此这种方法在这里并不实用。这种方法经常是实际计算机科学问题中最实用的解法，通过为分级锁指定常量，强制获得锁 的顺序，就可以解决这个问题。Chandy/Misra 解法1984年，K. ManiChandy和J. Misra提出了哲学家就餐问题的另一个解法，允许任意的用户 （编号P,.,行）争用任意数量的资源。与迪科斯彻的解法不同的是味療请月这里编号可以 是任意的。1对每一对竞争一个资源的哲学家，新拿一个餐叉，给编号较低的哲学家。每只餐叉 都是干净的”或者脏的”。最初，所有的餐叉都是脏的。2当一位哲学家要使用资源（也就是要吃东西）时，他必须从与他竞争的邻居那里得 至I。对每只他当前没有的餐叉，他都发送一个请求。3当拥有餐叉的哲学家收到请求时，如果餐叉是干净的，那么他继续留着，否则就擦 干净并交出餐叉。4当某个哲学家吃东西后，他的餐叉就变脏了。如果另一个哲学家之前请求过其中的 餐叉，那他就擦干净并交出餐叉。这个解法允许很大的并行性，适用于任意大的问题。
