-
哲学家就餐问题
是在
计算机科学
中的一个经典问题，
用来演示在
并行计算
中
多线程同步
(Synchronization)
时产生的问题。
在
< br>1971
年，著名的计算机科学家
艾兹格·迪科斯彻
提出了一个同步问题，即假设有五台计算机都试图访
问五份共享的磁
带驱动器。稍后，这个问题被
托尼·霍尔
重新表述为哲学家就餐
问题。这个问题可以用来
解释死锁和资源耗尽。
哲学家就餐问题可以这样表述，假设有五位哲学家围坐在一张圆形餐桌旁，做以下两件事情之一：吃饭
，
或者思考。吃东西的时候，他们就停止思考，思考的时候也停止吃东西。餐桌中间有一
大碗意大利面，每
两个哲学家之间有一只餐叉。
因为用一只餐叉
很难吃到意大利面，
所以假设哲学家必须用两只餐叉吃东西。
他
们只能使用自己左右手边的那两只餐叉。哲学家就餐问题有时也用米饭和筷子而不是意大利面和餐叉来
描述，因为很明显，吃米饭必须用两根筷子。
哲
学家从来不交谈，这就很危险，可能产生
死锁
，每个哲学家都拿
着左手的餐叉，永远都在等右边的餐叉
（或者相反）。
即使没有死锁，也有可能发生
资源耗尽
。例如
，假设规定当哲学家等待另一只餐叉超过五分钟后就放下自
己手里的那一只餐叉，并且再
等五分钟后进行下一次尝试。这个策略消除了死锁（系统总会进入到下一个
状态），但仍
然有可能发生“活锁”。如果五位哲学家在完全相同的时刻进入餐厅，并同时拿起左边的餐
叉，那么这些哲学家就会等待五分钟，同时放下手中的餐叉，再等五分钟，又同时拿起这些餐叉。
在实际的计算机问题中，缺乏餐叉可以类比为缺乏共享资源。一种常用的计
算机技术是资源加锁，用来保
证在某个时刻，
资源只能被一个程
序或一段代码访问。
当一个程序想要使用的资源已经被另一个程序锁定，
它就等待资源解锁。当多个程序涉及到加锁的资源时，在某些情况下就有可能发生死锁。例如，某个程序
需要访问两个文件，当两个这样的程序各锁了一个文件，那它们都在等待对方解锁另一个
文件，而这永远
不会发生。
[
编辑
]
服务生解法
一个简单的解法是引入一
个餐厅服务生，哲学家必须经过他的允许才能拿起餐叉。因为服务生知道哪只餐
叉正在使
用，所以他能够作出判断避免死锁。
为了演示这种解法，假设
哲学家依次标号为
A
至
E
。如果
A
和
C
在吃东西，则有四只餐叉在使用中。
B
坐
在
A
和
C
之间，所以两只餐叉都无法使用，而
D
和
E
之间有一只空余的餐叉。假设这时
D
想要吃东西。如
果他拿起了第五只餐叉，就有可能发生死锁。相反，如果他征
求服务生同意，服务生会让他等待。这样，
我们就能保证下次当两把餐叉空余出来时，<
/p>
一定有一位哲学家可以成功的得到一对餐叉，
从而避免了死锁。<
/p>
[
编辑
]
资源分级解法
另一个简单的解法是为
资源（这里是餐叉）分配一个
偏序
或者分级的关系，并约定所有
资源都按照这种顺
序获取，
按相反顺序释放，
< br>而且保证不会有两个无关资源同时被同一项工作所需要。
在哲学家就餐问题中，<
/p>
资源（餐叉）按照某种规则编号为
1
至<
/p>
5
，每一个工作单元（哲学家）总是先拿起左右两边编号较低的餐
叉，再拿编号较高的。用完餐叉后，他总是先放下编号较高的餐叉，再放下编号较低的。
在这种情况下，
当四位哲学家同时拿起他们手边编号较低的餐叉时，只有编号最高的餐叉
留在桌上，从而第五位哲学家就
不能使用任何一只餐叉了。而且，只有一位哲学家能使用
最高编号的餐叉，所以他能使用两只餐叉用餐。
当他吃完后，他会先放下编号最高的餐叉
，再放下编号较低的餐叉，从而让另一位哲学家拿起后边的这只
开始吃东西。
尽管资源分级能避免死锁，
但这种策略并不总是
实用的，
特别是当所需资源的列表并不是事先知道的时候。
例如
，假设一个工作单元拿着资源
3
和
5<
/p>
，并决定需要资源
2
，则必须先要释放<
/p>
5
，之后释放
3
，才能得到
2
，
之后必须重新按顺序获
取
3
和
5
。对
需要访问大量数据库记录的计算机程序来说，如果需要先释放高编
号的记录才能访问新的
记录，那么运行效率就不会高，因此这种方法在这里并不实用。
这种方法经常是实际计算机科学问题中最实用的解法，通过为分级锁指定常量，强制获得锁的顺序，就可
以解决这个问题。
[
编辑
]
Chandy/Misra
解法
1984
年，
K.
Mani
Chandy
和
J.
Misra
提出了哲学家就餐问题的另一个解法，
允许
任意的用户
（编号
P
1
,
...,
P
n
）争用任意数量的资源。与迪科斯彻的解法不同的是
[
< br>来源请求
]
，这里编号可以是任意的。
< br>
1.
对每一对竞争一个资源
的哲学家，新拿一个餐叉，给编号较低的哲学家。每只餐叉都是“干净的”
或者“脏的”
。最初，所有的餐叉都是脏的。
2.
当一位哲学家要使用资源（也就是要吃东西）时，他必须从与他竞争的邻居那里得到。对
每只他
当前没有的餐叉，他都发送一个请求。
3.
当拥有餐叉的哲学家收到请求时
，如果餐叉是干净的，那么他继续留着，否则就擦干净并交出餐
叉。
4.
当某个哲学家吃东西后，
他的餐叉就变脏了。如果另一个哲学家之前请求过其中的餐叉，那他就
擦干净并交出餐叉
。
这个解法允许很大的并行性，适用于任意大的问题。
我们自己考试上交的哲学家进餐程序
#include
#include
#include
void
main()
{
int
x1,x2;//1-5
的随机数
int i,N;//N
循环次数
int
flag=-1;//flag
记录信号量的全局变量
printf(
请输入循环次数
N:
scanf(
for(i=1;i<=N;i++)
{
x1=rand()%5+1;
if(flag==-1)
{
pr
intf(
第
%d
次循环第
%d
个哲学家可以单独进餐
!
flag=x1;
}
x2=rand()%5+1;
if(flag==-1)
{
pr
intf(
第
%d
次循环第
%d
个哲学家可以单独进餐
!
flag=x2;
}
else
if(abs(flag-x2)==2||abs(flag-x2)==3)
{
printf(
第
%d
次循环第
%d
个和第
%d
个哲学家可以同时进餐
!
flag=x2;
}
else
printf(
第
%d
次循环第
%d
个哲学家思考
!
printf(
}
}
解决哲学家进餐问题为避免死锁，课本上有这个解决方法：
至多只允许有四位哲学家同时去拿左边的筷子，最终能保
证至少有一位哲学家能够进餐，并能用毕时
能释放出他用过的两只筷子，从而使更多的哲
学家能够进餐。
1
．
哲学家进餐问题：
(1)
在什么情况下
5
个哲学家全部吃不上饭？
考虑两种实现的方式，如下：
A.
算法描述：
void
philosopher(int i)
/*i
：哲学家编号，从
0
到
4*/
{
while (TRUE) {
think( );
/*
哲学家正在思考
*/
take_fork(i);
/*
取左侧的筷子
*/
take_fork((i+1) % N);
/*
取左侧筷子；％为取模运算
*/
eat( ); /*
吃饭
*/
put_fork(i);
/*
把左侧筷子放回桌子
*/
put_fork((i+1) % N);
/*
把右侧筷子放回桌子
*/
}
}
分析：假如所有的哲学家都同时拿起左侧筷子，看到右侧筷
子不可用，又都放下左侧筷子，
等一会儿，又同时拿起左侧筷
子，如此这般，永远重复。对于这种情况，即所有的程序都在
无限期地运行，但是都无法取得任何进展，即出现饥饿，所有哲学家都吃不上饭。
B
．
算法描述：
规定在拿到左侧的筷子后
，先检查右面的筷子是否可用。如果不可用，则先放下左侧筷子，
等一段时间再重复整个过程。
分析：
当出现以下情形，在某一个瞬间，所有的哲学家都同时启动这个算法，拿起左侧的筷
<
/p>
子，而看到右侧筷子不可用，又都放下左侧筷子，等一会儿，又同时拿起左侧筷子??如此