主观题：h416.(清华1997年试题)设有5个哲学家，共享一张方有5把椅子的桌子，每人分得一把椅子。但是桌子上总共只有5支筷子，在每个人两边各......

(清华1997年试题)设有5个哲学家，共享一张方有5把椅子的桌子，每人分得一把椅子。但是桌子上总共只有5支筷子，在每个人两边各放一支。哲学家中有饥饿时才试图分两次从两边拾起筷子就餐。就餐的条件是：
(1)哲学家想吃饭时，先提出吃饭的要求；
(2)提出吃饭要求，并得到2支筷子后，方可吃饭；
(3)如果筷子已被他人获得，则必须等待该人吃完饭后才能获得筷子；
(4)任何哲学家在自己为拿到2支筷子吃饭之前，决不放下手中的筷子；
(5)刚开始就餐时，只允许2个哲学家请求吃饭。
试问：
(1)描述一个既没有两邻座同时吃饭，又没有人饿死的算法；
(2)在什么情况下，5个哲学家全部吃不上饭？







答案：解：
（1）（5分）

semaphore S[5]={0,0,0,0,0}; //同步信号量，用于阻塞对应的哲学家
semaphore mutex=1; //互斥信号量，用于互斥访问标志变量
int flag[5]={0,0,0,0,0}; //标志变量
Pi ( ) //第i号哲学家的活动过程，i=0,1,2,3,4
{
m=(i+1)%5;
n=(i-1+5)%5;
L1: P(mutex);
if (flag[m]==1 || flag[n]==1 || flag[m]==-2 || flag[n]==-2)
{
V(mutex);
flag[i] = -1;
P(S[i]);
goto L1;
}
flag[i]=1; //flag[i]=1表示第i号哲学家要求吃饭（3分）
V(mutex);
拿起左边筷子;
拿起右边筷子;
吃饭；
放下左边筷子;
放下右边筷子;
P(mutex);
flag[i]=0;
if (flag[m]== -1) //若右边哲学家正在等待，则唤醒之
{ flag[m]= -2; V(S[m]); }
if (flag[n]== -1) //若左边哲学家正在等待，则唤醒之
{ flag[m]= -2 ; V(S[m]); }（2分）
V(mutex);
}
parbegin
P0( );
P1( );
P2( );
P3( );
P4( );
parend

（2）（5分）
去掉“只允许2个哲学家请求吃饭”和“不允许两个邻座同时要求吃饭”的条件，按下面给出的算法：

semaphore chopstick[5]={1,1,1,1,1}; //互斥信号量，用于互斥拿起5根筷子
Pi ( ) //第i号哲学家的活动过程，i=0,1,2,3,4
{
j=(i+1)%5;
while (1) {
P(chopstick[i]); //拿起左边的筷子
P(chopstick[j]); //拿起右边的筷子
吃饭;
V(chopstick[i]); //放下左边的筷子
V(chopstick[j]); //放下右边的筷子（3分）
}
}
parbegin
P0( );
P1( );
P2( );
P3( );
P4( );
parend（2分）
上述算法中，当5个哲学家同时拿起左边的筷子，再拿右边筷子时都将阻塞，此时系统将出现死锁，这种情况下，5个哲学家全部吃不上饭。