哲学家进餐问题实现

《哲学家进餐问题实现》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、哲学家进餐问题实现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);/*把右侧筷子放回桌子*/}}分析：假如所有的哲学家都同时拿起左侧筷子，看到右侧筷子不可用，又都放下左侧筷子

2、，等一会儿，又同时拿起左侧筷子，如此这般，永远重复。对于这种情况，即所有的程序都在无限期地运行，但是都无法取得任何进展，即出现饥饿，所有哲学家都吃不上饭。B．算法描述：规定在拿到左侧的筷子后，先检查右面的筷子是否可用。如果不可用，则先放下左侧筷子，等一段时间再重复整个过程。分析：当出现以下情形，在某一个瞬间，所有的哲学家都同时启动这个算法，拿起左侧的筷子，而看到右侧筷子不可用，又都放下左侧筷子，等一会儿，又同时拿起左侧筷子……如此这样永远重复下去。对于这种情况，所有的程序都在运行，但却无法取得进展，即出现饥饿，所有的哲学家都吃不上饭。(2)描述一种没有人饿死（永远拿不到筷子）算法。考虑

3、了四种实现的方式（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

4、);//请求进入房间进餐wait(chopstick[i]);//请求左手边的筷子wait(chopstick[(i+1)%5]);//请求右手边的筷子eat();signal(chopstick[(i+1)%5]);//释放右手边的筷子signal(chopstick[i]);//释放左手边的筷子signal(room);//退出房间释放信号量room}}B．原理：仅当哲学家的左右两支筷子都可用时,才允许他拿起筷子进餐。方法1：利用AND型信号量机制实现：根据课程讲述，在一个原语中，将一段代码同时需要的多个临界资源，要么全部分配给它，要么一个都不分配，因此不会出现死锁的情形。当某些资

5、源不够时阻塞调用进程;由于等待队列的存在，使得对资源的请求满足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（）之前的取左侧和右侧筷子的操作进行保护，使之成为一个原子操作，这样可以防止死锁的出现。伪码：

6、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(mutex);eat();signal(chopstick[(I+1)]%5);signal(chopstick[I]);}}C．原理：规定奇数号的哲学家先拿起他左边的筷子,然后再去拿他右边的筷子;而偶数号的哲学家则相反.按此规定,将是1,2号哲学家竞争1号筷子,3,4号哲学家竞

7、争3号筷子.即五个哲学家都竞争奇数号筷子,获得后,再去竞争偶数号筷子,最后总会有一个哲学家能获得两支筷子而进餐。而申请不到的哲学家进入阻塞等待队列，根FIFO原则，则先申请的哲学家会较先可以吃饭，因此不会出现饿死的哲学家。伪码：semaphorechopstick[5]={1，1，1，1，1};voidphilosopher(inti){while(true){think();if(i%2==0)//偶数哲学家，先右后左。{wait(chops