Question

利用记录型信号量写一个哲学家进餐问题的算法

题目如上，要求是不会出现死锁。

Answer 1

1
void philosopher(int i)
{
while (TRUE) {
think( );
take_fork(i);
take_fork((i+1) % N);
eat( );
put_fork(i);
put_fork((i+1) % N);
}
}

2
semaphore chopstick[5]={1，1，1，1，1};
semaphore room=4;
void philosopher(int i)
{
while(true)
{
think();
wait(room); //请求进入房间进餐
wait(chopstick[i]); //请求左手边的筷子
wait(chopstick[(i+1)%5]); //请求右手边的筷子
eat();
signal(chopstick[(i+1)%5]); //释放右手边的筷子
signal(chopstick[i]); //释放左手边的筷子
signal(room); //退出房间释放信号量room
}
}
3
semaphore chopstick[5]={1，1，1，1，1};
void philosopher(int I)
{
while(true)
{
think();
Swait(chopstick[(I+1)]%5,chopstick[I]);
eat();
Ssignal(chopstick[(I+1)]%5,chopstick[I]);
}
}
4
semaphore mutex = 1 ;
semaphore chopstick[5]={1，1，1，1，1};
void philosopher(int I)
{
while(true)
{
think();
wait(mutex);
wait(chopstick[(I+1)]%5);
wait(chopstick[I]);
signal(mutex);
eat();
signal(chopstick[(I+1)]%5);
signal(chopstick[I]);
}
}
5：
semaphore chopstick[5]={1，1，1，1，1};
void philosopher(int i)
{
while(true)
{
think();
if(i%2 == 0) //偶数哲学家，先右后左。
{
wait (chopstick[ i + 1 ] mod 5) ;
wait (chopstick[ i]) ;
eat();
signal (chopstick[ i + 1 ] mod 5) ;
signal (chopstick[ i]) ;
}
Else //奇数哲学家，先左后右。
{
wait (chopstick[ i]) ;
wait (chopstick[ i + 1 ] mod 5) ;
eat();
signal (chopstick[ i]) ;
signal (chopstick[ i + 1 ] mod 5) ;
}
}

Answer 2

正确答案：除了为每只筷子设置一个初值为l的信号量chopstick[i](i=0…4)外还需再设置一个初值为4的信号量Sm以限制同时就餐的哲学家人数不超过4。第i个哲学家的活动可描述为：
此题有多种解决方法。其中之一是只允许4个哲学家同时进餐，以保证至少有一个哲学家可以进餐，最终才可能由他释放出其所用过的两只筷子，从而使更多的哲学家可以进餐。为此，需设置一个信号量Sm来限制同时进餐的哲学家数目，使它不超过4，故Sm的初值也应置成4(也可想象成桌上有4块令牌，只有拿到令牌的哲学家才能进餐，这样，令牌就是一种临界资源，故可为它们设置一个初值为4的信号量Sm)。