操作系统(第三版)孙钟秀主编课后习题3应用题参考答案

《操作系统教程》（第三版）CH3应用题参考答案1CH3应用题参考答案1有三个并发进程：R负责从输入设备读入信息块，M负责对信息块加工处理；P负责打印输出信息块。今提供；1）一个缓冲区，可放置K个信息块；2）二个缓冲区，每个可放置K个信息块；试用信号量和P、V操作写出三个进程正确工作的流程。答：1）varB:array[0,k-1]ofitem;sread:semaphore:=k;smanage:semaphore:=0;swrite:semaphore:=0;rptr:integer:=0;mptr:integer:=0;wptr:integer:=0;x:itemcobeginprocessreader;beginL1:readamessageintox;P(sread);B[rptr]:=x;rptr:=(rptr+1)modk;V(smanage);gotoL1;end;processmanager;beginL2:P(smanage);x:=B[mptr];mptr:=(mptr+1)modk;managethemessageinx;B[mptr]:=x;V(swrite);gotoL2;end;processwriter;beginL3:P(swrite);x:=B[wptr];wptr:=(wptr+1)modk;V(sread);Printthemessageinx;gotoL3;end;coend2）varA,B:array[0,k-1]ofitem;sput1:semaphore:=k;sput2:semaphore:=k;sget1:semaphore:=0;sget2:semaphore:=0;put1:integer:=0;put2:integer:=0;get1:integer:=0;get2:integer:=0;cobeginprocessreader;beginL1:readamessageintox;processmanager;beginL2:P(sget1);processwriter;beginL3:P(sget2);《操作系统教程》（第三版）CH3应用题参考答案2P(sput1);A[put1]:=x;put1:=(put1+1)modk;V(sget1);GotoL1;end;x:=A[get1];get1:=(get1+1)modk;V(sput1);Managethemessageintox;P(sput2);B[put2]:=x;put2:=(put2+1)modk;V(sget2);GotoL2;end;x:=B[get2];get2:=(get2+1)modk;V(sput2);Printthemessageinx;GotoL3;end;coend2设有n个进程共享一个互斥段，如果：(1)每次只允许一个进程进入互斥段；(2)每次最多允许m个进程（m≤n）同时进入互斥段。试问：所采用的信号量初值是否相同？信号量值的变化范围如何？答：所采用的互斥信号量初值不同。1）互斥信号量初值为1，变化范围为[-n+1，1]。当没有进程进入互斥段时，信号量值为1；当有1个进程进入互斥段但没有进程等待进入互斥段时，信号量值为0；当有1个进程进入互斥段且有一个进程等待进入互斥段时，信号量值为-1；最多可能有n-1个进程等待进入互斥段，故此时信号量的值应为-(n-1)也就是-n+1。2）互斥信号量初值为m，变化范围为[-n+m，m]。当没有进程进入互斥段时，信号量值为m；当有1个进程进入互斥段但没有进程等待进入互斥段时，信号量值为m-1；当有m个进程进入互斥段且没有一个进程等待进入互斥段时，信号量值为0；当有m个进程进入互斥段且有一个进程等待进入互斥段时，信号量值为-1；最多可能有n-m个进程等待进入互斥段，故此时信号量的值应为-(n-m)也就是-n+m。3有两个优先级相同的进程P1和P2，各自执行的操作如下，信号量S1和S2初值均为0。试问P1、P2并发执行后，x、y、z的值各为多少？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+yz:=z+x;end.end.答：现对进程语句进行编号，以方便描述。P1：P2：beginbeginy:=1;①x:=1;⑤y:=y+3;②x:=x+5;⑥《操作系统教程》（第三版）CH3应用题参考答案3V(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。最后，语句④和⑧并发执行，最后结果为：语句④先执行：x=10，y=9，z=15。语句⑧先执行：x=10，y=19，z=15。4有一阅览室，读者进入时必须先在一张登记表上登记，该表为每一座位列出一个表目，包括座号、姓名，读者离开时要注销登记信息；假如阅览室共有100个座位。试用：1）信号量和P、V操作；2）管程，来实现用户进程的同步算法。答：1)使用信号量和P、V操作：varname:array[1..100]ofA;A=recordnumber:integer;name:string;endfori:=1to100do{A[i].number:=i;A[i].name:=null;}mutex,seatcount:semaphore;i:integer;mutex:=1;seatcount:=100;cobegin{processreaderi(varreadername:string)(i=1,2,…){P(seatcount);P(mutex);fori:=1to100doi++ifA[i].name=nullthenA[i].name:=readername;readergettheseatnumber=i;/*A[i].numberV(mutex)进入阅览室，座位号i，座下读书;P(mutex);A[i]name:=null;V(mutex);V(seatcount);离开阅览室;}}coend.《操作系统教程》（第三版）CH3应用题参考答案45在一个盒子里，混装了数量相等的黑白围棋子。现在用自动分拣系统把黑子、白子分开，设分拣系统有二个进程P1和P2，其中P1拣白子；P2拣黑子。规定每个进程每次拣一子；当一个进程在拣时，不允许另一个进程去拣；当一个进程拣了一子时，必须让另一个进程去拣。试写出两进程P1和P2能并发正确执行的程序。答：实质上是两个进程的同步问题，设信号量S1和S2分别表示可拣白子和黑子，不失一般性，若令先拣白子。varS1,S2:semaphore;S1:=1;S2:=0;cobegin{processP1beginrepeatP(S1);拣白子V(S2);untilfalse;endprocessP2beginrepeatP(S2);拣黑子V(S1);untilfalse;end}coend.6设公共汽车上，司机和售票员的活动分别如下：司机的活动：启动车辆：正常行车；到站停车。售票员的活动：关车门；售票；开车门。在汽车不断地到站、停车、行驶过程中，这两个活动有什么同步关系？用信号量和P、V操作实现它们的同步。答：在汽车行驶过程中，司机活动与售票员活动之间的同步关系为：售票员关车门后，向司机发开车信号，司机接到开车信号后启动车辆，在汽车正常行驶过程中售票员售票，到站时司机停车，售票员在车停后开门让乘客上下车。因此，司机启动车辆的动作必须与售票员关《操作系统教程》（第三版）CH3应用题参考答案5车门的动作取得同步；售票员开车门的动作也必须与司机停车取得同步。应设置两个信号量：s1、s2；s1表示是否允许司机启动汽车(其初值为0)；s2表示是否允许售票员开门(其初值为0)。用P、V原语描述如下：vars1，s2：semaphore；s1=0；s2=0;cobegin{driver();busman();}coenddriver()beginwhile(1){P(s1)启动车辆；正常行车；到站停车；V(s2);}endbusman()beginwhile(1){关车门；，V(s1)售票；P(s2)开车门；上下乘客；}end7在信号量S上作P、V操作时，S的值发生变化，当S＞0、S=0、S0时，它们的物理意义是什么？答：S的值表示它代表的物理资源的使用状态：S0表示还有共享资源可供使用。S=0表示共享资源正被进程使用但没有进程等待使用资源。S0表示资源已被分配完，还有进程等待使用资源。《操作系统教程》（第三版）CH3应用题参考答案68(1)两个并发进程并发执行，其中，A、B、C、D、E是原语，试给出可能的并发执行路径。ProcessPProcessQbeginbeginA；D；B；E；C；end；end；(2)两个并发进程P1和P2并发执行，它们的程序分别如下：P1P2repeatrepeatk:=k×2;printk;k:=k+1;k:=0;untilfalse;untilfalse;若令k的初值为5，让P1先执行两个循环，然后，P1和P2又并发执行了一个循环，写出可能的打印值，指出与时间有关的错误。答：(1)共有10种交错执行的路径：A、B、C、D、E；A、B、D、E、C；A、B、D、C、E；A、D、B、E、C；A、D、B、C、E；A、D、E、B、C；D、A、B、E、C；D、A、B、C、E；D、A、E、B、C；D、E、A、B、C。(2)把语句编号，以便于描述：P1P2repeatrepeatk:=k×2;①printk;③k:=k+1;②k:=0;④untilfalse;untilfalse;1)K的初值为5，故P1执行两个循环后，K=23。2)语句并发执行有以下情况：①、②、③、④，这时的打印值为：47③、④、①、②，这时的打印值为：23①、③、②、④，这时的打印值为：46①、③、④、②，这时的打印值为：46③、①、②、④，这时的打印值为：23③、①、④、②，这时的打印值为：23由于进程P1和P2并发执行，共享了变量K，故产生了‘结果不唯一’。9另一个经典同步问题：吸烟者问题(patil，1971)。三个吸烟者在一个房间内，还有一个香烟供应者。为了制造并抽掉香烟，每个吸烟者需要三样东西：烟草、纸和火柴，供应者有丰富货物提供。三个吸烟者中，第一个有自己的烟草，第二个有自己的纸和第三个有自己的火柴。供应者随机地将两样东西放在桌子上，允许一个吸烟者进行对健康不利的吸烟。当吸烟者完成吸烟后唤醒供应者，供应者再把两样东西放在桌子上，唤醒另一《操作系统教程》（第三版）CH3应用题参考答案7个吸烟者。试采用：(1)信号量和P、V操作，(2)管程编写他们同步工作的程序。答：(1)用信号量和P、V操作。varS,S1,S2,S3;semaphore;S:=1;S1:=S2:=S3:=0;flag1,flag2,flag3:Boolean;flag1:=flag2:=flag3:=true;cobegin{process供应者beginrepeatP(S);取两样香烟原料放桌上，由flagi标记;/*flage1、flage2、flage3代表烟草、纸、火柴ifflag2&flag3thenV(S1);/*供纸和火柴elseifflag1&flag3thenV(S2);/*供烟草和火柴elseV(S3);/*供烟草和纸untilefalse;endprocess吸烟者1beginrepeatP(S1);取原料;做香烟;V(S);吸香烟;untilefalse;process吸烟者2beginrepeatP(S2);取原料;做香烟;V(S);吸香烟;untilefalse;p