第三章-作业参考答案.docx

《第三章-作业参考答案.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章作业参考答案P181第3题：答：现对进程语句进行编号，以方便描述。P1：P2：beginbeginy:=1;①x:=1;⑤y:=y+3;②x:=x+5;⑥V(S1);P(S1);z:=y+1;③x:=x+y;⑦P(S2);V(S2);y:=z+y④z:=z+x;⑧end.end.①、②、⑤和⑥是不相交语句，可以任何次序交错执行，而结果是唯一的。接着无论系统如何调度进程并发执行，当执行到语句⑦时，可以得到x=10，y=4。按Bernstein条件，语句③的执行结果不受语句⑦的影响，故语句③执行后得到z=5。最后，语句④和⑧并发执行

2、，这时得到了两种结果为：语句④先执行：x=10，y=9，z=15。语句⑧先执行：x=10，y=19，z=15。此外，还有第三种情况，语句③被推迟，直至语句⑧后再执行，于是依次执行以下三个语句：z:=z+x；z:=y+1;y:=z+y;这时z的值只可能是y+1=5，故y=z+y=5+4=9，而x=10。第三种情况为：x=10，y=9，z=5。P181第5题：解：设信号量empty，mutex；empty：=100；mutex：=1；parbegin读者进入：beginP(empty)；P(mutex)；登记；P(mutex)；End；读

3、者离开：beginP(mutex)；撤消登记；V(mutex)；V(empty)；End；8/8Parend；P181第6题：答：实质上是两个进程的同步问题，设信号量S1和S2分别表示可拣白子和黑子，不失一般性，若令先拣白子。Main(){intS1=1,S2=0;CobeginP1();P2();Coend}P1(){while(拣子工作没完成){P(S1);拣白子V(S2);}}P2(){while(拣子工作没完成){P(S2);拣黑子V(S1);}}P182第15题：Dijkstra临界区软件算法描述如下：varflag:arr

4、ay[0…n]of(idle,want-in,in_cs);turn:integer;tune:0or1or…or,n-1;processPi(i=0,1,…,n-1)varj;integer;beginrepeatrepeatflag[i]:=want_in;whileturn≠idoifflag[turn]==idlethenturn:=i;flag[i]:=in_cs;j:=0;while(j

5、dle;…untilfalse;8/8end.试说明该算法满足临界区原则。答：为方便描述，把Dijkstra程序的语句进行编号：repeatflag[i]:=want_in;①whileturn≠ido②ifflag[turn]==idlethenturn:=i;③flag[i]:=in_cs;④j:=0;while(j

6、≠in_cs(对于所有j，j≠i)条件时，Pi才能进入它的临界区，而且进程Pi不会改变除自己外的其他进程所对应的flag[j]的值。另外，进程Pi总是先置自己的flag[i]为in_cs后，才去判别Pj进程的flag[j]的值是否等于in_cs，所以，此算法能保证n个进程互斥地进入临界区。(2)不会发生无休止等待进入临界区由于任何一个进程Pi在执行进入临界区代码时先执行语句①，其相应的flag[i]的值不会是idle。注意到flag[i]=in_cs并不意味着turn的值一定等于i。我们来看以下情况，不失一般性，令turn的初值为0，

7、且P0不工作，所以，flag[turn]=flag[0]=idle。但是若干个其他进程是可能同时交替执行的，假设让进程Pj(j=1,2,..,n-1)交错执行语句①后(这时flag[j]=want_in)，再做语句②(第一个while语句)，来查询flag[turn]的状态。显然，都满足turn≠i，所以，都可以执行语句③，让自己的turn为j。但turn仅有一个值，该值为最后一个执行此赋值语句的进程号，设为k、即turn=k(1≤k≦n-1)。接着，进程Pj(j=1,2,..,n-1)交错执行语句④，于是最多同时可能有n-1个进程处

8、于in_cs状态，但不要忘了仅有一个进程能成功执行语句④，将turn置为自己的值。假设{P1,P2,…Pm}是一个已将flag[i]置为in_cs(i=1,2,…,m)(m≤n-1)的进程集合，并且已经假设当前turn=