哲学家进餐问题.pdfVIP

1．哲学家进餐问题：

(1)在什么情况下5个哲学家全部吃不上饭？

考虑两种实现的方式，如下：

A.

算法描述：

voidphilosopher(inti)/*i：哲学家编号，从0到4*/

{

while(TRUE){

think();/*哲学家正在思考*/

take_fork(i);/*取左侧的筷子*/

take_fork((i+1)%N);/*取左侧筷子；％为取模运算*/

eat();/*吃饭*/

put_fork(i);/*把左侧筷子放回桌子*/

put_fork((i+1)%N);/*把右侧筷子放回桌子*/

}

}

分析：假如所有的哲学家都同时拿起左侧筷子，看到右侧筷子不可用，又都放下

左侧筷子，

等一会儿，又同时拿起左侧筷子，如此这般，永远重复。对于这种情况，即所有

的程序都在

无限期地运行，但是都无法取得任何进展，即出现饥饿，所有哲学家都吃不上饭。

B．

算法描述：

规定在拿到左侧的筷子后，先检查右面的筷子是否可用。如果不可用，则先放下

左侧筷子，

等一段时间再重复整个过程。

分析：当出现以下情形，在某一个瞬间，所有的哲学家都同时启动这个算法，拿

起左侧的筷

子，而看到右侧筷子不可用，又都放下左侧筷子，等一会儿，又同时拿起左侧筷

子……如此

这样永远重复下去。对于这种情况，所有的程序都在运行，但却无法取得进展，

即出现饥饿，

所有的哲学家都吃不上饭。

(2)描述一种没有人饿死（永远拿不到筷子）算法。

考虑了四种实现的方式（A、B、C、D）：

A．原理：至多只允许四个哲学家同时进餐,以保证至少有一个哲学家能够进餐,

最终总会释

放出他所使用过的两支筷子,从而可使更多的哲学家进餐。以下将room作为信

号量，只允

许4个哲学家同时进入餐厅就餐，这样就能保证至少有一个哲学家可以就餐，

而申请进入

餐厅的哲学家进入room的等待队列，根据FIFO的原则，总会进入到餐厅就餐，

因此不会

出现饿死和死锁的现象。

伪码：

semaphorechopstick[5]={1，1，1，1，1};

semaphoreroom=4;

voidphilosopher(inti)

{

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

}

}

B．原理：仅当哲学家的左右两支筷子都可用时,才允许他拿起筷子进餐。

方法1：利用AND型信号量机制实现：根据课程讲述，在一个原语中，将一段

代码同时需

要的多个临界资源，要么全部分配给它，要么一个都不分配，因此不会出现死锁

的情形。当

某些资源不够时阻塞调用进程;由于等待队列的存在，使得对资源的请求满足

FIFO的要求，

因此不会出现饥饿的情形。

伪码：

semaphorechopstick[5]={1，1，1，1，1};

voidphilosopher(intI)

{

while(true)

{

think();

Swait(chopstick[(I+1)]%5,chopstick[I]);

eat();

Ssignal(chopstick[(I+1)]%5,chopstick[I]);

}

}

方法2：利用信号量的保护机制实现。通过信号量mutex对eat（）之前的取左

侧和右侧筷

子的操作进行保护，使之成为一个原子操作，这样可以防止死锁的出现。

伪码：

semaphoremutex=1;

semaphorechopstick[5]={1，1，1，1，1};

voidphilosopher(intI)

{

while(true)

{

think();

wait(mutex);

wait(chopstick[(I+1)]%5);

wait(chopstick[I]);

signal