哲学家就餐问题--计算机操作系统.doc

13、分析下面用信号量解决哲学家进餐问题的同步算法是否满足同步机制的准则。若不满足，说明为什么，并给出满足同步机制准则的同步算法。Var chopstick : array0,4 of semaphore ;Chopstick0:=chopstick1:=chopstick2:=chopstick3:=chopstick4:=1;Pi: repeat wait(chopsticki); wait(chopstick(i+1)mod 5); eat ; signal(chopsticki); signal(chopstick(i+1)mod 5); think; until false;答：该算法不满足同步机制的“有限等待”原则，即每个哲学家都只拿一个筷子时就会产生死锁。下面给出三种解决办法。1、互斥申请资源设置信号量mutex初值为4，即最多可以有4个哲学家同时申请筷子。这样保证了4个哲学家中至少有1人可以拿到两个筷子就餐而不发生死锁。 mutex=4 Pi(i=0,1,4); Repeat wait(mutex); wait(chopsticki); wait(chopstick(i+1) mod 5);signal(mutex);Eat ;signal(chopsticki);signal(chopstick(i+1)mod 5);think;until false ;2、改变申请资源次序规定奇数号哲学家先拿起左边的筷子，然后再去拿右边的筷子；偶数号哲学家正好相反。也即拿到一个筷子的哲学家才有权去拿下一个筷子，而没有拿到筷子的哲学家则退出竞争。这样就不会出现5个哲学家都只拿一个筷子的情况。pi(i=0,1,4) repeat if odd(i) then /*如果i 为奇数*/ begin wait(chopsticki); wait(chopstick(i+1)mod 5); end else begin wait(chopstick(i+1)mod 5); wait(chopsticki); endeat ; signal(chopsticki); signal(chopstick(i+1)mod 5); think; until false;3、采用AND型信号量机制AND型同步机制的思想是：将进程所需要的所有资源一次性全部分配给它，但只要有一个资源不能分配给该进程，则其它所有资源也不能分配给它。pi (i=0,1,4) repeat Swait(chopsticki, chopstick(i+1)mod 5); eat ; Ssignal(chopstick(i+1)mod 5, chopsticki); think; until false;15、设有5位哲学家，共享一张放有5把椅子的桌子，每人分得一把椅子。但是，桌上总共有5支筷子，在每人两边分开各放一支。哲学家只有在饥饿时方可分两次从两边抢占筷子就餐。就餐的条件如下：哲学家想吃饭时，先提出吃饭请求。提出吃饭请求时，并拿到两支筷子后，方可吃饭。如筷子已被他人获得，则必须等待此人吃饭后才能获取筷子。任一哲学家在自己未拿到两支筷子吃饭之前，决不放下手中的筷子。刚开始就餐时，只允许两个哲学家吃饭。试问：1） 描述一个保证不会出现两个邻座同时要求吃饭的算法。2） 描述一个即没有两邻座同时吃饭，又没有人饥饿的算法。3） 在什么情况下，5个哲学家全部吃不上饭。答为了保证不会出现相邻的两个哲学家同时提出吃饭的请求，特设置信号量S0S4来互斥两两相邻的哲学家吃饭请求，其初值均为1。注意：对第I 个哲学家来说，他的两个邻座分别为(I+1)mod 5和(I+4)mod 5，第I个哲学家的左右邻座定位如图所示。i(I+1)mod 5(I+2)mod 5(i+4)mod 5(I+3) mod 5此外，5支筷子也为临界资源，即chopstick0chopstick4初值为1。由于禁止两相邻的哲学家同时申请，因此也就不存在同时竞争请求筷子的问题。（但可能申请的筷子正在别的哲学家手上），故可以去掉公用信号量mutex，相应的同步算法如下：begin s0=s1=s2=s3=s4=1; chopstick0=chopstick1=chopstick2=chopstick3=chopstick4=1; cobeginPi (I=0,1,2,3,4);Begin Repeat P(sI); /*第I 个哲学家提出吃饭请求*/ P(s(I+1)mod 5 )/*禁止左邻哲学家提出申请；如果左邻哲学家已经提出申请，则阻塞哲学家I的此次请求*/ P(s(I+4) mod 5);/*禁止右邻哲学家提出申请；如果右邻哲学家已提出申请，则阻塞哲学家I 的此次申请*/ P(chopstickI); P(chopstick(I+1) mod 5 V(sI);/*哲学家I 的申请结束*/ V(sI+1 mod 5) /*取消哲学家I的左邻哲学家申请的禁止*/ V(sI+4 mod 5)/*取消对右邻哲学家申请的禁止*/ Eat ; V(chopstickI); V(chopstickI+1 mod 5); Think ; Until false;End; Coend; End;(2)为了保证没有两个邻座同时吃饭，特设置变量r0r4z来记录哲学家的吃饭情况。此外，设置信号量s0s4来控制04号哲学家的吃饭过程，其初值为0。由于不存在两邻座同时吃饭，因此，筷子已不是临界资源。相应的同步算法如下：begin mutex=1; r0=r1=r2=r3=r4=0; s0=s1=s2=s3=s4=0; cobegin Pi (I=0,1,2,3,4) repeat P(mutex); If(r(I+1)mod 5=1)or (r(I+4)mod 5=1) then /*如果第I 个哲学家左右邻桌有一人以上正在就餐，则阻止此次申请*/ begin V(mutex);/*在阻塞自己之前，先释放公用信号量以便其它进程进入*/ P(sI); End; Else Begin RI=1; V(muetex); End; Eat; P(mutex); RI=0;/*清除给自己设置的吃饭标志*/ If(rI+3mod 50) and (s(I+4)mod 5=-1) then V(s(I+4)mod 5); /*第I 个哲学家右邻（即（I4）mod 5）已提出过申请（即s(I+4)mod 5=-1）并在其右邻（即s(I+3)mod 5）没有进餐的情况下，解除对申请的阻塞*/ if(r(I+2)mod 5=0 and (S(I+1)mod5=-1) then V(s(I+1)m