操作系统习题答案(3).pdf

操作系统习题答案第-(3)CH3应用题参考答案1、有三个并发进程：R负责从输入设备读入信 息块，M负责对信息块加工处理；P负责打印输 出信息块。今提供；1）一个缓冲区，可放置K个信息块；2）二个缓冲区，每个可放置K个信息块；试用信号量和P、V操作写出三个进程正确工 作的流程。答：1）var B:array 0,k-1 of item;sread:semaphore:=k;smanage:semaphore:=0;swrite:semaphore:=0;rptr:integer:=O;mptr:integer:=O;wptr：integer:=0;x:itemcobeginprocess reader;processmanager;process writer;begin beginbeginLI:read a message intox;L2:P(smanage)；(swnte);P(sreadx:=Bmptr;x:=Bswrite;Brptr:=x;L3：P);mptr:=(mptr+l)wptr:=(wptr+l)mod k;modk;Rptr:=(rptr+1)modk；manage the messageV(sread);V(smanage);Bmptr:=x;print the message in x;GotoV(s write);goto L3;End;gotoL2;end;coendin x;LI；End;2)var A,B:array 0 5 k-1 of item;sPutl:semaphore:=k;SPut2:semaphore:=k;sgetl:semaphore:=0;sget2:semaphore:=0;putl：integer：=0;put2：integer:=0;getl：integer：=0;get2:integer:=O;cobeginprocessreaderprocessn manager;process Writer;begin beginbeginLI:read a message into x;L2:P(sgetl);L3:P(sgetZ);P(SPutl);x：=A getl;x：=Bget2;Aputl:=x；getl：(getl+1)mod k；get2:=(get2+1)mod k;Putl:=(putl+1)mod k;V(sputl);V(sput2);V(sgetl);manage the message into x;print the message in x;GotoP(sput2);goto L3;Put2:=(put2+1)mod k;V(sget2);Goto L2;End;CoendLI；2设有n个进程共享一个互斥段，如果：(1)每次只允许一个进程进入互斥段；(2)每次最多允许m个进程(m簇n)同时进入互斥段。试问：所采用的信号量初值是否相同？信号量值的变化范围如何？答：所采用的互斥信号量初值不同。1)互斥信号量初值为1,变化范围为Ln+1,1 o当没有进程进入互斥段时，信号量值为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有两个优先级相同的进程Pl和P2,各自执行的操作如下，信号量S1和S2初 值均为0。试问Pl、P2并发执行后，x、y、z的值各为多少？P1:P2:BeginbeginY:=l;x:=l;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;Endend答：现对进程语句进行编号，以方便描述.P1:P2:beginbeginy：=1;x:=1;y：=y+3；X：x+5;V(S1)；P(S1)；Z:Y+1；X：封Y；P(s2);V(S2);Y:=z+y;z：=Z+X；Endend、和是不相交语句，可以任何次序交错执行，而结果是唯一的。接着无论系统如何调度进程并发执行，当执行到语句时，可以得到x=10,y=4 o按Bernstein 条件，语句的执行结果不受语句的影响，故语句 执行后得到z=5。最后，语句和 并发执行，这时得到了两种结果为:语句 先执行：x=10,y=9,z=150 语句 先执行：x=10,y=19,z=15此外，还有第三种情况，语句 被推迟，直至语句后再执行，于是依次执 行以下三个语句：7：二z+X:z:=y+1;y：=z+y;这时z的值只可能是y+1=5,故y=Z+Y=5+4=9,而x=10 o第三种情况为：x=10,Y=9,Z=5 o4有一阅览室，读者进入时必须先在一张登记表上登记，该表为每一座位列出 一个表目，包括座号、姓名，读者离开时要注销登记信息；假如阅览室共有100 个座位。试用：1)信号量和P、V操作；2)管程，来实现用户进程的同步 算法。答：1)使用信号量和P、v操作：var name：array 1 100of A;A=recordnumber：integer;name：string;endfor i:=1 to 100 do A i .number：i；A i.name:null;mutex,seatcount:semaphore;i:integer；mutex:=1;seatcount:=100;cobeginprocess readeri(var readename：string)(i=l,2)P(seatcount);P(mutex);for i:=1 to 100 do i+if A i.name=null then A i.name：readername；reader get the seat number=i；/*AI.numberV(mutex)进入阅览室，座位号i,座下读书；P(mutex);Ainame：null;V(mutex);V(seatcount);离开阅览室；)coend2)使用管程操作:TYPE readbook=monitorVAR R:condition;I,seatcount：integer;name：array 1:100 of string;DEFINE rcadercome,readerleave;USE check,wait,signal,release;Procedure readercome(reademame)begincheck(IM);if seatcount 三 100 wait(R,IM)seatcount:=seatcount+1;for i=l to 100 do i+if namei=null then namei:=readername;get the seat number=i;release(IM);endprocedure readerleave(reademame)begincheck(IM);seatcount;for i=1 to 1 00 do i+if name i readername then name i :null;release(IM);endbeginseatcount:=1OO;name:=null;endcobeginprocess readeri(i=1,2.)beginreadercome(reademame read the book;readerleave(readername leave the readroom;););endcoend.5.在一个盒子里，混装了数量相等的黑白围棋子现在用自动分拣系统把黑 子、白子分开，设分拣系统有二个进程P1和P2,其中P1拣白子；P2拣黑子。规定每个进程每次拣一子；当一个进程在拣时，不允许另一个进程去拣；当一 个进程拣了一子时，必须让另一个进程去拣.试写出两进程P1和P2能并发正 确执行的程序。答1：实质上是两个进程的同步问题，设信号量si和s2分别表示可拣白子和 黑子，不失一般性，若令先拣白子。var SI,S2:semaphore;SI:=1;S2：=0；cobeginprocess Pl begin repeat P(S1)；拣白子V(S2);until false;end process P2 begin repeat P(S2);拣黑子 V(S1);until false;end coend.答2:TYPE pickup-chess=MONITORVAR flag:boolean;S-black,s-white:codition;DEFINE pickup-black,pickup-white;USE wait,signal,check,release;procedure pickup-black;begincheck(IM);if flag then wait(s-black,IM);flag:=true;pickup a black;signal(S-white,IM);release(IM);endprocedure pickup-white;begincheck(IM);if not flag then wait(S-white,IM);flag:=false;pickup a white;signal(S-black,IM);release(IM);endbeginflag:=true;endmain()cobeginprocess-B();process-W();coend)process-B()beginpickup-chess.pickup-black();other;endprocess-W()beginpickup-chess.pickup-white();other;end6管程的同步机制使用条件变量和wait及signal,尝试为管程设计一种仅仅 使用一个原语操作的同步机制。答：可以采用形如waituntil 条件表达式的同步原语。如waituntil(numbersum+number 0、S=0、S0表示还有共享资源可供 使用。S阅表示共享资源正被进程使用但没有进程等待使用资源。S0表示 资源已被分配完，还有进程等待使用资源。10(1)两个并发进程并发执行，其中，A、B、C、D、E是原语，试给出 可能的并发执行路径。end;Process PProcess QbeginbeginA;D;B；E；c；end:(2)两个并发进程Pl和P2并发执行，它们的程序分别如下：P 1 P2repeat repeatk:=k X2;print k;k:=k+l;k:=0;until false;until false;若令k的初值为5,让Pl先执行两个循环，然后，P1和P2又并发执行 了一个循环，写出可能的打印值，指出与时间有关的错误。答:(1)共有10种交错执行的路径:A、E，D E c C、c B B、DEE、B D A、,AA D CE;比、E c c、D B B、B D AAAD夕 夕 夕 E c c DEEc B B、。B D A c、A A D B(2)把语句编号，以便于描述：Pl P2repeat repeatk:=k X 2；printk；k:=k+l；k:=0；until false;until false;1)K 的初值为5,故Pl执行两个循环后，K=23 o2)语句并发执行有以下情况：、,这时的打印值为：47,这时的打印值为：23,这时的打印值为：46,这时的打印值为：46,这时的打印值为：23,这时的打印值为：23由于进程P1和P2并发执行，共享了变量K,故产生了 结果不唯一。11证明信号量与管程的功能是等价的:(1)用信号量实现管程；(2)用管程实现信号量。答：(1)用信号量实现管程；Hoare是用信号量实现管程的一个例子，详见课文内容。下面介绍另一种简单 方法：每一个管程都对应一个mutex,其初值为1,用来控制进程互斥调用管 程。再设一个初值为0的信号量，用来阻塞等待资源的进程。相应的用信号量 实现的管程库过程为：Var mutex,c:semaphore;mutex:=1;c:=0;void enter-monitor()/*进入管程代码，保证互斥P(mutex);)void leave-monitor-normally()/*不发信号退出管程V(mutex);void leave-with-sigal(c)/*在条件c上发信号并退出管程，释放一个等 待c条件的进程。注意这时没有开放管程，因为刚刚被释放的进程己在管程 中。V(c);)void wait(c)/*等待条件c,开放管程V(mutex);P(c)；(2)用管程实现信号量。TYPE semaphore=monitorVAR S;condition;C:integer;DEFINE P,V;USE check,wait,signal,release;procedure Pbegincheck(IM);C:=C-1:ifC0then wait(S,IM);release(IM);endprocedure Vbegincheck(IM):C:=C+1;ifC 0 then signal(S,IM);release(IM);endbeginC:=初值；End.12证明消息传递与管程的功能是等价的：(1)用消息传递实现管程；(2)用管程实现消息传递。答：(1)用消息传递实现管程；用消息传递可以实现信号量(见13(2),用信号量可以实现管程(见11(1),那么，把两种方法结合起来，就可以用用消息传递实现管程。(2)用管程实现消息传递。TYPE mailbox=monitorVAR r,k,count:integer;buffer：array0-n-l of message;full,empty:condition;DEFINE add,get;USE check,wait,signal,release;procedure add(r);begincheck(IM);if count=n then wait(fiillJM);buffer r:=message;r:=(r+l)mod ncount:=count+1;if count=1 then sighal(empty,IM);release(IM);end procedure get(m);begincheck(IM);if count=0 then wait(empty,IM);m:=buffer k；count:=count-1;if count=n-l then signal(full,IM);release(IM);endbeginr:=0;k:=0;count:=0;end13证明信号量与消息传递是等价的：(1)用信号量实现消息传递；(2)用消息传递实现信号量。答：(1)用信号量实现消息传递；1)把消息队列组织成一个共享队列，用一个互斥信号量管理对该队列的入队 操作和出队操作.2)发送消息是一个入队操作，当队列存储区满时，设计一个同步信号量阻塞 send操作。3)接收消息是一个出队操作，当队列存储区空时，设计另一个同步信号量阻 塞receive 操作。(2)用消息传递实现信号量。1)为每一个信号量建立一个同步管理进程，它包含了一个计数器，记录信号 量值；还为此信号量设立一个等待进程队列2)应用进程执行P或V操作时，将会调用相应P、V库过程。库过程的功能 是：把应用进程封锁起来，所执行的P、V操作的信息组织成消息，执行send 发送给与信号量对应的同步管理进程，之后，再执行receive操作以接收同步 管理进程的应答。3)当消息到达后，同步管理进程计数并查看信号量状态。如果信号量的值为 负的话，执行P操作的应用进程被阻塞，挂到等待进程队列，所以，不再要送 回答消息。此后，当V操作执行完后，同步管理进程将从信号量相应队列中选 取一个进程唤醒，并回送一个应答消息。正常情况下，同步管理进程回送一个 空应答消息，然后，解锁执行P、V操作的应用程序。14使用(1)消息传递，(2)管程，实现生产者和消费者问题。答：(1)见课文ch3 3.5.4 节。(2)见课文Ch3 3.4.3 节。15试利用记录型信号量和P、V操作写出一个不会出现死锁的五个哲学家进餐 问题的算法。答：var fbrki:array 0 4 of semaphore;fbrki:=l;cobeginprocess Pi/*i=0,1,2,3*/beginLI:思考：P(forki);/*i=4,P(fork 0)*/P(forki+1 mod 5)/*i=4P(fork 4)*/吃通心面；V(forki;V(fork(i+l mod 5);goto LI;end;)coend;16 Dijkstra 临界区软件算法描述如下：var flag：array0-n of(idle,want-in,in_cs);turn:integer;tune:O or 1 or or,n-1;process Pi(i=0,l,n-1)var j;integer;beginrepeatrepeatflag i:want_in;while turn W1 doif flag turn=idle then turn:=i;flagi:=ip_cs;j：=。；while(j n)&(j=l or flagj Win_cs)doj:=j+1;until j Nn:critical section;flag i:=idle;until false;end.试说明该算法满足临界区原则。答：为方便描述，把Dijkstra 程序的语句进行编号：repeatflagi:=want_in；while turn Wido if flagtrun=idle then turn:=i；flagi:=in_cs；j：=O；while(j n)&(j=l or flagj Win_cs)doj:=j+1；until j Nn;critical section;flagi:=idle；(1)满足互斥条件当所有的巧都不在临界区中，满足Win_cs(对于所有j,j Wi)条 件时，Pi才能进入它的临界区，而且进程Pi示会改变除自己外的其他进程所 对应的flagfj的值。另外，进程Pi总是先置自己的为in_cs后，才 去判别Pj进程的的值是否等于in_cs所以，此算法能保证n个进程互 斥地进入临界区。(2)不会发生无休止等待进入临界区由于任何一个进程Pi在执行进入临界区代码时先执行语句，其相应的 flagi的值不会是idle。注意到flagi=in_cs并不意味着turn的值一定 等于i。我们来看以下情况，不失一般性，令turn的初值为0,且P0不工作，所以，flag turn=flag 0=idle。但是若干个其他进程是可能同时交替执行的，假设让进程Pj(j=l,2，n-l)交错执行语句 后(这时flagj=want_in),再做语句(第一个while语句)，来查询flagturn的状态。显然，都满 足turn Wi,所以，都可以执行语句，让自己的turn为j。但turn仅有 一个值，该值为最后一个执行此赋值语句的进程号，设为k、即tum=k(l Wk n和nWn时，每个 进程最多可以请求多少个这类资源时，使系统一定不会发生死锁？答：当辰n时，每个进程最多请求1个这类资源时，系统一定不会发生死锁。当mn时，如果m/n不整除，每个进程最多可以请求“商+1”个这类资源,否则为“商“个资源，使系统一定不会发生死锁？22 N个进程共享M个资源，每个进程一次只能申请释放一个资源，每个进程 最多需要M个资源，所有进程总共的资源需求少于M+N个，证明该系统此时不 会产生死锁。答卜设max(i)表示第i个进程的最大资源需求量，need(i)表示第i个 进程还需要的资源量，alloc(i)表示第i个进程已分配的资源量。由题中 所给条件可知：max(1)+-+max(n)=(need(1)+,+need(n)+(alloc(l)+alloc(n)m+n如果在这个系统中发生了死锁，那么一方面m个资源应该全部分配出去，alloc(1)T-Falloc(n)=m另一方面所有进程将陷入无限等待状态。可以推出need(l)+,+need(n)n上式表示死锁发生后，n个进程还需要的资源量之和小于n,这意味着此刻至 少存在一个进程i,need(i)=0,即它已获得了所需要的全部资源。既然该进程已获得了它所需要的全部资源，那么它就能执行完成并释放它占有的资 源，这与前面的假设矛盾，从而证明在这个系统中不可能发生死锁。答2：由题意知道，nXmm+n 是成立的，等式变换 nX(m-1)+n n+m即 nX(m-l)m于是有 nX(m-1)+lm+1或 nX(m-1)+1 Cm这说明当n个进程都取得了最大数减1个即(m-1)个时，这时至少系统还 有一个资源可分配。故该系统是死锁无关的。23 一条公路两次横跨运河，两个运河桥相距100米，均带有闸门，以供船只通 过运河桥。运河和公路的交通均是单方向的。运河上的运输由驳船担负。在一 驳船接近吊桥A时就拉汽笛警告，若桥上无车辆，吊桥就吊起，直到驳船尾P通 过此桥为止。对吊桥B也按同样次序处理。一般典型的驳船长度为200米，当 它在河上航行时是否会产生死锁？若会，说明理由，请提出一个防止死锁的办 法，并用信号量来实现驳船的同步。答：当汽车或驳船未同时到达桥a时，以任何次序前进不会产生死锁。但假设 汽车驶过了桥A,它在继续前进，并且在驶过桥B之前，此时有驳船并快速地 通过了桥A,驳船头到达桥B,这时会发生死锁。因为若吊起吊桥B让驳船通 过，则汽车无法通过桥B；若不吊起吊桥B让汽车通过，则驳船无法通过桥B。可用两个信号量同步车、船通过两座桥的动作。var Sa,Sb:semaphore;Sa:=Sb:=l;cobeginprocess 驳船beginP(Sa);P(Sb);船过桥A、B;V(Sa);V(Sb);endprocess 汽车beginP(Sa);P(Sb);车过桥A、B;V(Sa);V(Sb);end)coend24 Jurassic 公园有一个恐龙博物馆和一个花园，有m个旅客租卫辆车，每 辆车仅能乘一个一旅客。旅客在博物馆逛了 一会，然后，排队乘坐旅行车，挡 一辆车可用喊飞它载入一个旅客，再绕花园行驶任意长的时间。若n辆车都己 被旅客乘坐游玩，则想坐车的旅客需要等待。如果一辆车己经空闲，但没有游 玩的旅客了，那么，车辆要等待。试用信号量和P、V操作同步m个旅客和n辆 车子。答：这是一个汇合机制，有两类进程：顾客进程和车辆进程，需要进行汇合、即顾客要坐进车辆后才能游玩，开始时让车辆进程进入等待状态var scl,sck,sc,Kx,xc,mutex:semaphore;sck:=kx:=sc:=xc:=O；scl:=n；mutex:=1;sharearea：一个登记车辆被服务乘客信息的共享区；cobeginprocess 顾客 i(i=l,2,)beginP(scl);/*车辆最大数量信号量P(mutex);/*封锁共享区，互斥操作在共享区sharearea 登记被服务的顾客的信息：起始和到达地点，行驶时间V(sck);/*释放一辆车，即顾客找到一辆空车P(Kx)；/*待游玩结束之后，顾客等待下车V(scl);/*空车辆数加1EndProcess 车辆 j(j=l,2,3)BeginL:P(sck);/*车辆等待有顾客来使用在共享区sharearea登记那一辆车被使用，并与顾客进程汇合；V(mutex);/*这时可开放共享区，让另一顾客雇车V(kx);/*允许顾客用此车辆车辆载着顾客开行到目的地；V(xc);/*允许顾客下车Goto L;Endcoend25今有k个进程，它们的标号依次为1、2、k,如果允许它们同时读 文件file，但必须满足条件：参加同时读文件的进程的标号之和需小于K,请使用：1)信号量与P、v操作，2)管程，编写出协调多进程读文件的程 序。答1:1)使用信号量与P、v操作var waits,mutex:semphore;numbersum:integer:=0;wait:=0；mutex:=l;cobeginprocess readeri(var number:integer;)beginP(mutex);L:if numbersum+number 三 K then V(mutex);P(waits);gotoL；Then numbersum:numbersum+number;V(mutex);Read file;P(mutex);numbersum:=numbersum-number;V(waits);V(mutex);2)使用管程：TYPE sharefile=MONITORVAR numbersum,n:integer;SF:codition;DEFINE startread,endread;USE wait,signal,check,release;procedure startread(var number：integer:);begincheck(IM);L:if(number+numbersum)三 K then wait(SF,IM);goto L;Numbersum:=numbersum+number;release(IM);endprocedure endread(var number:integer;);begincheck(IM);numbersum:=numbersum-number;signal(SF?IM);release(IM);endbegin numbersum:=Oend.main()cobeginprocess-i();coend process-i()var number:integer;beginnumber:=进程读文件编号;startread(number);read F;endread(number);end 26、设当前的系统状态如下：系统此时Available=(l,l,2):1)计算各个进程还需要的资源数Cki-Aki?(2)系统是否处于安全状态，为什么？(3)P2 发出请求向量request2(l,o,l),系统能把资源分给它吗？(4)若在P2申请资源后，若P1发出请求向量req够stl(1,0,1),系统能把资源分给它吗？(5)若在P1申请资源后，若P3发出请求向量request3(0,0,1),系统能把资源分给它吗？答：(1)P1,P2,P3,P4 的 Cki.Aki 分别为：(2,2,2)、(1,0,2)、(1,0,3)、(4,2,0)(4)系统处于安全状态，存在 安全序：P2,P1,P3,P4(5)可以分配，存在安全序列：P2,P1,P3,P4.(6)不可以分配，资源不足。(7)不可以分配，不安全状态。27系统有A、B、C、D共4种资源，在某时刻进程PO、Pl、PZ、P3和P4对资源的占有和需求情况如表，试解答下列问题：系统此时处于安全状态吗？若此时P2发出request2(l、2、2、2),系统能分配资源给它吗？为什 么？答：(1)系统处于安全状态，存在安全序列：P0,P3,P4,P1,P2 o(2)不能分配，否则系统会处于不安全状态。28把死锁检测算法用于下面的数据，并请问：Available=(1,0,2,0)(1)此时系统处于安全状态吗？(2)若第二个进程提出资源请求request2(0,0,1,0)系统能分配资源给它吗？(3)执行(2)之后，若第五个进程提出资源请求request5(0,0,1,0)系统能分配资源给它吗？答：(1)此时可以找出进程安全序列：P4,P1,P5,P2,P3 o故系统处 于安全状态。(2)可以分配，存在安全序列：P4,P1,P5,P2,P3 o(3)不可分配，系统进入不安全状态。29)考虑一个共有巧0个存储单元的系统，如下分配给三个进程，P1最大需 求70,己占有25；以P2最大需求60,己占有40;P3 最大需求60,己 占有45。使用银行家算法，以确定下面的任何一个请求是否安全。(l)P4进程到达，P4最大需求60,最初请求25个。(2)P4 进程到达，P4最大需 求60,最初请求35。如果安全，找出安全序列；如果不安全，给出结果分配 情况。答：(1)由于系统目前还有150-25-40-45=40个单元，P4进程到达，把25个单 元分给它。这时系统还余15个单元，可把15个单元分给P3,它执行完后会 释放60个单元。于是可供P1(还要45个单元)，P2(还要20个单元)，P4(还 要35个单元)任何一个执行。安全序列为：(1)P4进程到达，P4最大需求60,最初请求35 o如果把35个单元分给P4,系统还余5个单元，不再能满足任何一个进程的需求，系统进入不安全状态。30有一个仓库，可存放X、Y两种产品，仓库的存储空间足够大，但要求：(1)每次只能存入一种产品X或Y,(2)满足-NX产品数量-Y产品数量其中，N和M是正整数，试用信号量与P、V操作实现产品X与Y的入库过 程。答：本题给出的表达式可分解为制约条件：-NX产品数量-Y产品数量X产品数量-Y产品数量M也就是说，X产品的数量不能比Y产品的数量少N个以上，X产品的数量不能 比Y产品的数量多M个以上。可以设置两个信号量来控制X、Y产品的存放数 量：SX表示当前允许X产品比Y产品多入库的数量，即在当前库存量和Y产品不 入库的情况下，还可以允许SX个X产品入库；初始时，若不放Y而仅放X产品，则SX最多为M-1个。sy表示当前允许Y产品比x产品多入库的数量，即在当前库存量和x产品不 入库的情况下，还可以允许sy个Y产品入库.初始时，若不放X而仅放Y产 品，则sy最多为N-l个。当往库中存放入一个X产品时，则允许存入Y产 品的数量也增加1,故信号量sy应加1：当往库中存放入一个Y产品时，则 允许存入X产品的数量也增加1,故信号量sx应加1.var mutex:semaphore=1/*互斥信号量*/sx,sy:semaphore;sx=M-1;sy=N-1;cobeginprocess X repeatP(sx);P(mutex);将X产品入库;V(mutex);V(sy);until false process Y repeatP(sy);P(mutex);将Y产品入库；V(mutex);V(px);until false)coend.31有一个仓库可存放A、B两种零件，最大库容量各为m个。生产车间不断 地取A和B进行装配，每次各取一个.为避免零件锈蚀，按先入库者先出库的 原则。有两组供应商分别不断地供应A和B,每次一个。为保证配套和合理库 存，当某种零件比另一种零件超过n(nm)个时，暂停对数量大的零件的 进货，集中补充数量少的零件.试用信号量与P、V操作正确地实现它们之间 的同步关系。答：按照题意，应满足以下控制关系：A零件数量-B零件数量Wn;B 零件数 量-A零件数量Wn:A 零件数量Wm;B零件数量Wm.四个控制关系分别用 信号量sa、sb、empty 1和empty2实施。为遵循先入库者先出库的原则，A、B零件可以组织成两个循形队列，并增加入库指针ini、in2和出库指针outl、out2来控制顺序。并发程序编制如下：Var empty 1,empty2,fulll,full2:semaphore;Mutex,sa,sb:semaphore;Ini,in2,outl,out2:integer;Bufferl,buffer2:array0 m-1of item;Empty 1:=empty2:=m;Sa:=sb:=n;Ini:=in2=outl:=out2:=0;CobeginProcess producerArepeatP(emptyl);P(sa);P(mutex);Buffer 1 in 1:=A 零件；Inl:=(inl+l)mod m;V(mutex);V(sb);V(fulll);Untile false;)Process producer BrepeatP(empty2);P(sb);P(mutex);Buffer2in2:=B 零件;In2:=(in2+l)mod m;V(mutex);V(sa);V(full2);Untile false;Process takerepeatP(fulll);P(foll2);P(mutex);Take from buffer 1 out 1 and buffer2out2 中的 A B 零件；Out 1:=(out 1+1)mod m;Out2:=(out2+1)mod m;V(mutex);V(emptyl);V(empty2);把A和B装配成产品；Until falseCoend.32进程Al、A2、Anl通过m个缓冲区向进程Bl、B2、Bn2不断 地发送消息.发送和接收工作符合以下规则：(1)每个发送进程每次发送一个消息，写进一个缓冲区，缓冲区大小与消息 长度相等；(2)对每个消息，Bl、BZ、二、BnZ都需接收一次，并读入各自的数据区 内；(3)当M个缓冲区都满时，则发送进程等待，当没有消息可读时，接收进程 等待.试用信号量和PV操作编制正确控制消息的发送和接收的程序。答：本题是生产者一消费者问题的一个变形，一组生产者Al,A2,Anl和 一组消费者B1,B2，Bn2共用m个缓冲区，每个缓冲区只要写一次，但 需要读n2次。因此，可以把这一组缓冲区看成n2组缓冲区，每个发送者需要 同时写n2组缓冲区中相应的n2个缓冲区，而每一个接收者只需读它自己对应 的那组缓冲区中的对应单元。应设置一个信号量mutex实现诸进程对缓冲区的互斥访问；两个信号量数组 emptyn2和fiinn2描述n2组缓冲区的使用情况.其同步关系描述如下：var mutex,emptyn2,fulln2:semaphore;integer;mutex=l;fbr(i=0;i=n2-l;i+)emptyi=m;Fulli=0;main()cobeginAl()；A2();Anl();Bl()；B2();Bn2();coendsend()/*进程Ai发送消息*/int i;for(i=0;i=n2-l;i+)；P(emptyi);P(mutex);将消息放入缓冲区;V(mutex);for(i=0；i 0 then wait(R,IM);rc:=rc+1;signal(R,IM);release(IM);end;procedure end-read;begincheck(IM);rc:=rc-l;If rc=0 then signal(W,IM);release(IM);end;procedure start-write;begincheck(IM);wc:=wc+1;if rc 0 or wc 1 then wait(W,IM):release(IM);end;procedure end-write;begincheck(IM);wc:=wc-l:if wc 0 then signal(W,IM);else signal(R,IM);release(IM);end;beginrc:=0;wc:=0;R:=0;W:=0;end.Cobegin process Plbegin call read-writer.start-read;Read;call read-riter.end-read;end;process P2beginCall read-wr