欢迎来到天天文库
浏览记录
ID:57294994
大小:117.50 KB
页数:13页
时间:2020-08-10
《哲学家进餐问题(操作系统)课件.ppt》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、哲学家进餐问题主讲人:次仁桑珠问题描述设有五个哲学家,共用一张放有五把椅子的餐桌,每人坐在一把椅子上,桌子上有五个碗和五只筷子,每人两边各放一只筷子。哲学家们是交替思考和进餐,饥饿时便试图取其左右最靠近他的筷子。(1)只有拿到两只筷子时,哲学家才能吃饭。(2)如果筷子已被别人拿走,则必须等别人吃完之后才能拿到筷子。怎样才能保证哲学家不被饿死呢?摘 要:解决“哲学家进餐”问题首先要找出对应的控制关系,设定相应的控制信号量。避免死锁也是解决该类问题的关键。关键词:进程同步;信号量;临界资源;临界区;死锁算法Avoidphilosopher(inti)/*i:哲学家编号,从0到4*
2、/{while(TRUE){think();/*哲学家正在思考*/take_fork(i);/*取左侧的筷子*/take_fork((i+1)%N);/*取右侧筷子;%为取模运算*/eat();/*吃饭*/put_fork(i);/*把左侧筷子放回桌子*/put_fork((i+1)%N);/*把右侧筷子放回桌子*/}}算法分析:当出现以下情形,在某一个瞬间,所有的哲学家都同时启动这个算法,拿起左侧的筷子,而看到右侧筷子不可用,又都放下左侧筷子,等一会儿,又同时拿起左侧筷子……如此这样永远重复下去。对于这种情况,所有的哲学家都吃不上饭。算法改善:至多只允许四个哲学家同时进餐,
3、以保证至少有一个哲学家能够进餐,最终总会释放出他所使用过的两支筷子,从而可使更多的哲学家进餐。改进后的算法Asemaphorefork[5]={1,1,1,1,1};semaphoreroom=4;voidphilosopher(inti){while(true){think();wait(room);//请求进入房间进餐wait(fork[i]);//请求左手边的筷子wait(fork[(i+1)%5]);//请求右手边的筷子eat();signal(fork[(i+1)%5]);//释放右手边的筷子signal(fork[i]);//释放左手边的筷子signal(room
4、);//退出房间释放信号量room}}算法B思想规定奇数号的哲学家先拿起他左边的筷子,然后再去拿他右边的筷子;而偶数号的哲学家则相反.按此规定,将是1,2号哲学家竞争1号筷子,3,4号哲学家竞争3号筷子.即五个哲学家都竞争奇数号筷子,获得后,再去竞争偶数号筷子,最后总会有一个哲学家能获得两支筷子而进餐。而申请不到的哲学家进入阻塞等待队列,根据FIFO原则,则先申请的哲学家会较先可以吃饭,因此不会出现饿死的哲学家。semaphorefork[5]={1,1,1,1,1};voidphilosopher(inti){while(true){think();if(i%2==0)//
5、偶数哲学家,先右后左。{wait(fork[i+1]mod5);wait(fork[i]);eat();signal(fork[i+1]mod5);signal(fork[i]);}Else//奇数哲学家,先左后右。{wait(fork[i]);wait(fork[i+1]mod5);eat();signal(fork[i]);signal(fork[i+1]mod5);}}综上所述,解决这一类问题的关键是找出对应的控制关系,设定相应的控制信号量。另外,产生死锁是在用信号量进行流程控制过程中常会遇到的一个问题,因此如何避免死锁就是解决该类问题的关键。Thankyou!
此文档下载收益归作者所有