哲学家就餐.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,哲学家用餐,问题：,哲学家就餐问题中，一组哲学家围坐在一个圆桌旁，每个哲学家的左边都只有一只筷子（当然他的右边也有一只筷子，但是这是他右边哲学家的左边的筷子），他们吃完了就思考，思考了一会就会饿，饿了就想吃，然而，为了吃饭，他们必须获得左边和右边的筷子进餐完毕，放下筷子继续思考。,五个人五只筷子该如何进行用餐啊,利用记录型信号量解决：,进分析可知，放在桌子上的筷子是临界资源，在一段时间内允许一位哲学家使用。为了实现对筷子的互斥使用，可以用一个信号量表示一只筷子，由这五个信号量构成信号量数组。其描述如下：,Var,chopstick:array0,4of semaphore;,所有信号量均被初始化为,1,，第,i,位哲学家的活动课描述为：,repeat:,wait(chopsticki,);,Wait(chopstick(i+1)mod5);,eat;,signal(chopsticki,);,signal(chopstick(i+1mod5);,Think;,until false,但是这样有可能造成死锁，如何解决？,(1),至多只允许四个哲学家同时进餐,以保证至少有一个哲学,家能够进餐,最终总会释放出他所使用过的两支筷子,从而可,使更多的哲学家进餐,.,其伪码是：,Semaphore chopstick5=1,1,1,1,1;,Semaphore room=4;,Void,philosopher(int,i),while(true,),Think();,Wait(room,);/,请求进入房间进餐,wait(chopsticki,);/,请求左手边的筷子,wait(chopstick(i+1)%5);/,请求右手边的筷子,eat();,signal(chopstick(i+1)%5);/,释放右手边的筷子,singal(chopsticki,);/,释放右手边的筷子,singal(room,);,可采用以下几种解决方法来解决死锁,：,(2),仅当哲学家的左右两支筷子都可用时,才允许他拿起筷子进餐,.,其伪码：,Semaphore chopstick5=1,1,1,1,1;,Void,philosopher(int,I),while(true,),Think();,Swait(chopstick(I+1)%5,，,chopstickI,);,eat();,Ssignal(chopstick(I+1)%5,，,chopstickI,);,(3),规定奇数号的哲学家先拿起他左边的筷子,然后再去拿他右边的筷子,;,而偶数号的哲学家则相反,.,按此规定,将是,1,2,号哲学家竞争,1,号筷子,3,4,号哲学家竞争,3,号筷子,.,即五个哲学家都竞争奇数号筷子,获得后,再去竞争偶数号筷子,最后总会,1,个哲学家能获得两支筷子而进餐,.,其伪码为：,Semaphore chopstick5=1,1,1,1,1;,void,philosopher(int,i),While(true,),Think();,If(i%2=0)/,偶数号哲学家，先右后左,Wait(chopsticki+1mod5);,Wait(chopsticli,);,eat();,signal(chopstick(i+1)mod5);,singal(chopsticki,);,else,Wait(chopsticli,);,Wait(chopsticki+1mod5);,eat();,singal(chopsticki,);,signal(chopstick(i+1)mod5);,经过分析，我们决定采用第三种方法来解决死锁问题，其主函数如下：,void main(),int i,time;,/,初始化,for(i=1;i=people;+i),Tmani=0;,EatTimei=0;,Eatingi=0;,Thinkingi=1;,time=0;,for(;n=meat;),+time;,printf(=,这是第,%d,秒的开始,=n,time);,eat();,thinking();,eatting();,printf(=,这是第,%d,秒的结束,=nn,time);,printf(,哈哈,盘子里已经没有肉了,.n);,获得筷子的程序：,int getkey(int i),/key();,if(i!=1),if(i%2!=0)/,奇数就从左手开始拿筷子,然后再到右手。,if(Tmani-1=0)/i-1,为第,i,个哲学家的左边的筷子表示该筷子可用，表示正在被用,Tmani-1=1;,if(Tmani=0),Tmani=1;,return 1;,else,Tmani-1=0;,return 0,；,else,return 0;,else /,偶数先从右手开始拿筷子。,if(Tmani=0)/i-1,为第,i,个哲学家的左边的筷子表示该筷子可用，表示正在被用,Tmani=1;,if(Tmani-1=0),Tmani-1=1;,return 1;,else,Tmani=0;,return 0;,else,return 0;,开始,是否还有食物？,结束,等待,吃饭,NO,释放左边的筷子,释放右边的筷子,拿起左,(,奇,)/,右（偶）边的筷子,拿起右,(,奇,)/,左,(,偶,),边的筷子,YES,YES,YES,NO,NO,函数流程图：,最终的结果：,分析：界面显示出哲学家思考，吃肉状态，有吃肉则,表明两支筷子均拿到了，思考的则表明未能拿到两支,筷子而在等待。,设计结论：,1,根据我们所选的方法，达到了使哲学家吃肉的,时候不会有人饿死的目的。,2,实现随机的选取第,N,个哲学家能拿到两支筷子，,吃第,N,块肉，而吃肉时间在,3,秒内的一个随机数,3,实现了记录吃肉时间,对本设计过程及方法、手段的改进建议：,1,、因为所用的工具是,vc+6.0,，所以界面上不够美观，,看的时候也比较麻烦。可以使用一些有生成窗口语,言编写，如,C#,。,2,、最后代码上最好再设计一个模,块，使其自动记录每个哲学家用餐，思考，吃肉总,数的情况。使用户便于观察。,谢谢！,