CH3应用题参考答案

更新时间：2024-03-11 02:21:01 阅读量：综合文库文档下载

说明：文章内容仅供预览，部分内容可能不全。下载后的文档，内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的，是否完整无缺。

《操作系统教程》（第三版）CH3应用题参考答案

CH3 应用题参考答案

有三个并发进程：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 := 0 ; mptr : integer := 0 ; wptr : integer := 0 ; x : item cobegin

process reader ; process manager; begin begin

L1: read a message into x ; L2: P(smanage) ; P(sread) ; x := B[mptr] ; B[rptr]:= x ; mptr :=(mptr+1) mod rptr := ( rptr+1) mod k; k; V(smanage) ; manage the message in goto L1 ; x ; end ; B[mptr] := x; V(swrite) ;

goto L2; end ;

coend

2） var A, B : array [0,k-1] of item ;

sput1 : semaphore := k ; sput2 : semaphore := k ; sget1 : semaphore := 0 ; sget2 : semaphore := 0 ; put1 : integer := 0 ; put2 : integer := 0 ; get1 : integer := 0 ; get2 : integer := 0 ; cobegin process reader ; process manager ; begin begin

L1: read a message into x ; L2: P(sget1) ;

process writer ; begin

L3: P(swrite) ; x := B[wptr] ;

wptr :=(wptr +1) mod k;

V(sread) ;

Print the message in x ;

goto L3 ; end ;

process writer ; begin

L3 : P(sget2) ;

《操作系统教程》（第三版）CH3应用题参考答案

P(sput1) ;

A[put1] := x ;

put1 := (put1+1) mod k ; V(sget1) ; Goto L1 ; end ;

x :=A[get1];

get1 :=(get1+1) mod k; V(sput1) ;

Manage the message into x; P(sput2) ; B[put2] := x ;

put2 := (put2+1) mod k ; V(sget2) ; Goto L2 ; end ;

x :=B[get2] ;

get2 :=(get2+1) mod k; V(sput2) ;

Print the message in x ; Goto L3 ; end ;

coend

设有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。

有两个优先级相同的进程P1和P2，各自执行的操作如下，信号量S1和S2初值均为0。试问P1、P2并发执行后，x、y、z的值各为多少？

P1： P2： begin begin

y:=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.

答：现对进程语句进行编号，以方便描述。

P1： P2： begin begin

y:=1; ① x:=1; ⑤ y:=y+3; ② x:=x+5; ⑥

《操作系统教程》（第三版）CH3应用题参考答案

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。最后，语句④和⑧并发执行，最后结果为：

语句④先执行：x=10，y=9，z=15。语句⑧先执行：x=10，y=19，z=15。

有一阅览室，读者进入时必须先在一张登记表上登记，该表为每一座位列出一个表目，包括座号、姓名，读者离开时要注销登记信息；假如阅览室共有100个座位。试用：1）信号量和P、V操作；2）管程，来实现用户进程的同步算法。

答：1) 使用信号量和P、V操作：

var name: array[1..100] of A;

A=record number:integer; name:string; end

for i:=1 to 100 do {A[i].number:=i; A[i].name:=null;} mutex,seatcount:semaphore; i:integer;mutex:=1;seatcount:=100; cobegin {

process readeri(var readername:string)(i=1,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; /*A[i].number V(mutex)

进入阅览室，座位号i，座下读书;

P(mutex);

A[i] name:=null; V(mutex); V(seatcount); 离开阅览室; } } coend.

《操作系统教程》（第三版）CH3应用题参考答案

2) 使用管程操作：

TYPE readbook=monitor VAR R:condition;

i,seatcount:integer; name:array[1..100] of string; DEFINE readercome,readerleave; USE check,wait,signal,release; procedure readercome(readername)

begin check(IM);

if seatcount≥100 wait(R,IM) seatcount:=seatcount+1; for i=1 to 100 do i++

if name[i]==null then name[i]:=readername; get the seat number=i; release(IM); end

procedure readerleave(readername) begin

check(IM); seatcount--; for i=1 to 100 do i++

if name[i]==readername then name[i]:=null; release(IM); end begin

seatcount:=100;name:=null; end cobegin {

process readeri(i=1,2.?) begin

readercome(readername); read the book;

readerleave(readername); leave the readroom; end } coend. 5

在一个盒子里，混装了数量相等的黑白围棋子。现在用自动分拣系统把黑子、白子分开，设分拣系统有二个进程P1和P2，其中P1拣白子；P2拣黑子。规定每个进程每次拣一子；当一个进程在拣时，不允许另一个进程去拣；当一个进程拣了一子时，必须让另一个进程去拣。

《操作系统教程》（第三版）CH3应用题参考答案

试写出两进程P1和P2能并发正确执行的程序。

答：实质上是两个进程的同步问题，设信号量S1和S2分别表示可拣白子和黑子，不失一

般性，若令先拣白子。

var S1,S2:semaphore;

S1:=1;S2:=0; cobegin {

process P1 begin repeat P(S1); 拣白子

V(S2); until false; end

process P2 begin repeat P(S2); 拣黑子

V(S1); until false;

end } coend.

6 管程的同步机制使用条件变量和Wait及Signal，尝试为管程设计一种仅仅使用一个原语

操作的同步机制。答：可以采用形如waituntil <条件表达式>的同步原语。如waituntil (numbersum+number

7 设公共汽车上，司机和售票员的活动分别如下：

司机的活动：启动车辆：正常行车；到站停车。售票员的活动：关车门；售票；开车门。

在汽车不断地到站、停车、行驶过程中，这两个活动有什么同步关系？用信号量和P、V操作实现它们的同步。

答：在汽车行驶过程中，司机活动与售票员活动之间的同步关系为：售票员关车门后，向司机发开车信号，司机接到开车信号后启动车辆，在汽车正常行驶过程中售票员售票，到站时司机停车，售票员在车停后开门让乘客上下车。因此，司机启动车辆的动作必须与售票员关车门的动作取得同步；售票员开车门的动作也必须与司机停车取得同步。

《操作系统教程》（第三版）CH3应用题参考答案

应设置两个信号量：s1、s2；s1表示是否允许司机启动汽车(其初值为0)；s2表示是否

允许售票员开门(其初值为0)。用P、V原语描述如下： var s1，s2：semaphore；

s1=0； s2=0; cobegin {

driver ( ); busman ( ); } coend driver ( ) begin

while(1) {

P(s1)

启动车辆；正常行车；到站停车； V(s2);

}

end

busman ( ) begin

while(1) {

关车门；， V(s1) 售票； P(s2) 开车门；上下乘客；

}

end

8 一个快餐厅有4类职员：（1）领班：接受顾客点菜；（2）厨师：准备顾客的饭菜；（3）

打包工：将做好的饭菜打包；（4）出纳员：收款并提交食品。每个职员可被看作一个进程，试用一种同步机制写出能让四类职员正确并发运行的程序。答：典型的进程同步问题，可设四个信号量S1、S2、S3和S4来协调进程工作。

var S1,S2,S3,S4:semaphore; S1:=1;S2:=S3:=S4:=0; cobegin

{ process P1

begin

《操作系统教程》（第三版）CH3应用题参考答案

repeat

有顾客到来; P(S1);

接受顾客点菜； V(S2); untile false; end process P2 begin repeat P(S2);

准备顾客的饭菜； V(S3); untile false; end process P3 begin repeat P(S3);

将做好的饭菜打包； V(S4); untile false; end process P4 begin repeat P(S4);

收款并提交食品； V(S1); untile false; end

}

coend.

9 在信号量S上作P、V操作时，S的值发生变化，当S＞0、S=0、S<0时，它们的物理

意义是什么？答：S的值表示它代表的物理资源的使用状态：S>0表示还有共享资源可供使用。S=0表示共享资源正被进程使用但没有进程等待使用资源。S<0表示资源已被分配完，还有进程等待使用资源。

10 (1)两个并发进程并发执行，其中，A、B、C、D、E是原语，试给出可能的并发执行路

径。

Process P Process Q begin begin

《操作系统教程》（第三版）CH3应用题参考答案

A； D；

B； E； C； end； end；

(2) 两个并发进程P1和P2并发执行，它们的程序分别如下： P1 P2 repeat repeat k:=k×2; print k; k:=k+1; k:=0; until false; until false;

若令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) 把语句编号，以便于描述：

P1 P2

repeat repeat

k:=k×2; ① print k; ③ k:=k+1; ② k:=0; ④ until false; until false;

1) K的初值为5，故P1执行两个循环后，K=23。 2) 语句并发执行有以下情况：

①、②、③、④，这时的打印值为：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( ) /*进入管程代码，保证互斥

《操作系统教程》（第三版）CH3应用题参考答案

{

P(mutex); }

void leave-monitor-normally( ) /*不发信号退出管程 {

V(mutex); }

void leave-with-signal(c) /*在条件c上发信号并退出管程，释放一个等待c条件的进程。{ 注意这时没有开放管程，因为刚刚被释放的进程已在管程中。 V(c); }

void wait(c) /*等待条件c，开放管程 {

V(mutex); P(c); }

（2）用管程实现信号量。 TYPE semaphore=monitor VAR S;condition; C:integer; DEFINE P,V;

USE check,wait,signal,release; procedure P begin

check(IM); C:=C-1:

if C<0 then wait(S,IM); release(IM); end

procedure V begin

check(IM); C:=C+1;

if C≤0 then signal(S,IM); release(IM); end begin

C:=初值; end.

12 证明消息传递与管程的功能是等价的：

(1) 用消息传递实现管程； (2) 用管程实现消息传递。

《操作系统教程》（第三版）CH3应用题参考答案

答：(1) 用消息传递实现管程；

用消息传递可以实现信号量(见13(2))，用信号量可以实现管程(见11(1))，那么，把两种方法结合起来，就可以用用消息传递实现管程。

(2) 用管程实现消息传递。 TYPE mailbox=monitor VAR r,k,count:integer;

buffer:array[0?n-1] of message; full,empty:condition; DEFINE add,get;

USE check,wait,signal,release; procedure add(r); begin

check(IM);

if count=n then wait(full,IM); buffer[r]:=message; r:=(r+1) mod n count:=count+1;

if count=1 then sighal(empty,IM); release(IM); end

procedure get(m); begin

check(IM);

if count=0 then wait(empty,IM); m:=buffer[k]; count:=count-1;

if count=n-1 then signal(full,IM); release(IM); end begin

r:=0;k:=0;count:=0; end

13 证明信号量与消息传递是等价的：

（1）用信号量实现消息传递；（2）用消息传递实现信号量。答：(1) 用信号量实现消息传递；

1) 把消息队列组织成一个共享队列，用一个互斥信号量管理对该队列的入队操作和出队操

作。

2) 发送消息是一个入队操作，当队列存储区满时，设计一个同步信号量阻塞send操作。 3) 接收消息是一个出队操作，当队列存储区空时，设计另一个同步信号量阻塞receive操

作。

(2) 用消息传递实现信号量。

《操作系统教程》（第三版）CH3应用题参考答案

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 forki :array[0..4] of semaphore; forki := 1; cobegin {

process Pi /* i=0,1,2,3 */ begin L1: 思考； P(fork[i])； /*i=4,P(fork[0])*/ P(fork[i+1] mod5) /*i=4,P(fork[4])*/ 吃通心面； V(fork[i])； V(fork([i+ 1] mod 5)； goto L1; end; }

coend;

16 Dijkstra临界区软件算法描述如下： var flag:array[0?n] of (idle,want-in,in_cs);

turn:integer;tune:0 or 1 or?or,n-1; process Pi(i=0,1,?,n-1) var j;integer; begin repeat

repeat

flag[i]:=want_in;

《操作系统教程》（第三版）CH3应用题参考答案

while turn≠i do

if flag[turn]==idle then turn:=i; flag[i]:=in_cs; j:=0;

while (j

critical section; flag[i]:=idle; ?

until false; end.

试说明该算法满足临界区原则。

答：为方便描述，把Dijkstra程序的语句进行编号：

repeat

flag[i]:=want_in; ① while turn≠i do ② if flag[turn]==idle then turn:=i; ③ flag[i]:=in_cs; ④ j:=0;

while (j

critical section;

flag[i]:=idle; ⑦ ?

(1) 满足互斥条件

当所有的Pj都不在临界区中，满足flag[j]≠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，且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个进程处于in_cs状态，但不要忘了仅有一个进程能成功执行语句④，将turn置为自己的值。

假设{P1,P2,?Pm}是一个已将flag[i]置为in_cs(i=1,2,?,m)(m≤n-1)的进程集合，并且已经假设当前turn=k(1≤k≤m)，则Pk必将在有限时间内首先进入临界区。因为集合中除了Pk之外的所有其他进程终将从它们执行的语句⑤(第二个while循环语句)退出，且

《操作系统教程》（第三版）CH3应用题参考答案

这时的j值必小于n，故内嵌until起作用，返回到起始语句①重新执行，再次置

flag[i]=want_in，继续第二轮循环，这时的情况不同了，flag[turn]=flag[k]必定≠idle(而为in_cs)。而进程Pk发现最终除自身外的所有进程Pj的flag[j]≠in_cs，并据此可进入其临界区。

17 另一个经典同步问题：吸烟者问题(patil，1971)。三个吸烟者在一个房间内，还有一个

香烟供应者。为了制造并抽掉香烟，每个吸烟者需要三样东西：烟草、纸和火柴，供应者有丰富货物提供。三个吸烟者中，第一个有自己的烟草，第二个有自己的纸和第三个有自己的火柴。供应者随机地将两样东西放在桌子上，允许一个吸烟者进行对健康不利的吸烟。当吸烟者完成吸烟后唤醒供应者，供应者再把两样东西放在桌子上，唤醒另一个吸烟者。试采用：(1)信号量和P、V操作，(2)管程编写他们同步工作的程序。答：(1)用信号量和P、V操作。 var S,S1,S2,S3;semaphore; S:=1;S1:=S2:=S3:=0; flag1,flag2,flag3:Boolean; flag1:=flag2:=flag3:=true; cobegin {

process 供应者

begin

repeat P(S);

取两样香烟原料放桌上，由flagi标记; /*flage1、flage2、flage3代表烟草、纸、火柴

if flag2&flag3 then V(S1); /*供纸和火柴 else if flag1&flag3 then V(S2); /*供烟草和火柴 else V(S3); /*供烟草和纸 untile false; end

process 吸烟者1

begin

repeat P(S1); 取原料; 做香烟; V(S); 吸香烟; untile false; process 吸烟者2

begin

repeat P(S2); 取原料; 做香烟;

《操作系统教程》（第三版）CH3应用题参考答案

V(S);

吸香烟; untile false; process 吸烟者3

begin

repeat P(S3); 取原料; 做香烟; V(S); 吸香烟; untile false; }

coend.

(3) 用管程。

TYPE mskesmoke=monitor VAR S,S1,S2,S3:condition;

flag1,flag2,flag3:boolean

DEFINE give, take1, take2, take3; USE check,wait,signal,release; procedure give

begin

check(IM); 准备香烟原料;

if 桌上有香烟原料 then wait(S,IM); 把准备的香烟原料放桌上;

if flag2&flag3 then signal(S1,IM); if flag1&flag3 then signal(S2,IM); else signal(S3,IM); release(IM); end

procedure take1

begin

check(IM):

if 桌上没有香烟原料 then wait(S1,IM); else 取原料; signal(S,IM); release(IM); end

procedure take2

begin

check(IM):

if 桌上没有香烟原料 then wait(S2,IM); else 取原料;

《操作系统教程》（第三版）CH3应用题参考答案

signal(S,IM);

release(IM); end

procedure take3

begin

check(IM):

if 桌上没有香烟原料 then wait(S3,IM); else 取原料; signal(S,IM); release(IM); end begin

flag1:=flag2:=flag3:=true; end. cobegin {

process 供应者

begin repeat

Call makesmoke.give(); ?

until false; end

process 吸烟者1

begin repeat

Call makesmoke.take1(); 做香烟，吸香烟; until false; end

process 吸烟者2

begin repeat

Call makesmoke.take2(); 做香烟，吸香烟; until false; end

process 吸烟者3

begin repeat

Call makesmoke.take3(); 做香烟，吸香烟; until false; end

《操作系统教程》（第三版）CH3应用题参考答案

}

coend.

18 如图所示，四个进程Pi（i=0?3）和四个信箱Mj（j=0?3），进程间借助相邻信箱传递消息，

即Pi每次从Mi中取一条消息，经加工后送入M(i+1)mod4，其中M0、M1、M2、M3分别可存放3、3、2、2个消息。初始状态下，M0装了三条消息，其余为空。试以P、V操作为工具，写出Pi（i=0?3）的同步工作算法。

M1 P0 P1 M2 P2 M3 P3 M0

答：

var mutex1,mutex2,mutex3,mutex0:semaphore;

mutex1:=mutex2:=mutex3:=mutex0:=1; empty0,empty1,empty2,empty3:semaphore; empty:=0;empty1:=3;empty:=2:=empty3:=2; full0,full1,full2,full3:semaphore; full0:=3;full1:=full2:=full3:=0;

in0,in1,in2,in3,out0,out1,out2,out3;integer; in0:=in1:=in2:=in3:=out0:=out1:=out2:=out3:=0; cobegin { process P0

begin repeat P(full0); P(mutex0);

从M0[out0]取一条消息; out0:=(out0+1) mod 3; V(mutex0); V(empty0); 加工消息; P(empty1); P(mutex1); 消息已M1[in1]; in1:=(in1+1) mod 3; V(mutex1); V(full1); untile false; end process P1

begin repeat P(full1); P(mutex1);

从M1[out1]取一条消息; out1:=(out1+1) mod 3; V(mutex1); V(empty1); 加工消息; P(empty2); P(mutex2); 消息已M2[in2]; in2:=(in2+1) mod 2; V(mutex2); V(full2); untile false; end process P2

begin repeat P(full2); P(mutex2);

从M2[out2]取一条消息; out2:=(out2+1) mod 2; V(mutex2); V(empty2); 加工消息; P(empty3); P(mutex3); 消息已M3[in3]; in3:=(in3+1) mod 2; V(mutex3); V(full3); untile false; end process P3

begin repeat P(full3); P(mutex3);

从M3[out3]取一条消息; out3:=(out3+1) mod 2; V(mutex3); V(empty3);

《操作系统教程》（第三版）CH3应用题参考答案

加工消息; P(empty0); P(mutex0); 消息已M0[in0]; in0:=(in0+1) mod 3; V(mutex0); V(full0); untile false; end } coend.

19 设有三组进程Pi、Qj、Rk，其中Pi、Qj构成一对生产者和消费者，共享一个由M1个缓

冲区构成的循环缓冲池buf1。Qj、Rk构成另一对生产者和消费者，共享一个由M2个缓

冲区构成的循环缓冲池buf2。如果Pi每次生产一个产品投入buf1，Qj每次从中取两个产品组装成一个后并投入buf2，Rk每次从中取三个产品包装出厂。试用信号量和P、V操作写出它们同步工作的程序。

答：

var mutex1，mutex2，mutex3:semaphore; empty1，empty2，full1，full2;semaphore;

in1，in2，out1，out2:integer; counter1,counter2:integer; buffer1:arrar[0..M1-1] of item;buffer2:array[0..M2-1] of item; empty1:=M1;empty:=M2;

in1:=in2:=out1:=out2:=0; counter1:=counter2:=0; full1:=full2:=0;mutex1:=mutex2:=mutex3:=1; cobegin {

process Pi

begin L1:

P(empty1); P(mutex1);

put an item into buffer[in1]; in1:=(in1+1) mod M1; counter++;

if counter1=2 then {counter1:=0;V(full1);} V(mutex); goto L1; end

process Qj

begin L2:

P(full1); P(mutex1);

take an item from buffer1[out1]; out1:=(out1+1) mod M1;

take an item from buffer1[out1]; out1:=(out1+1) mod M1; V(mutex1);

V(empty1); V(empty1);

《操作系统教程》（第三版）CH3应用题参考答案

Process the products;

P(empty2); P(mutex2);

put an item into buffer2[in2]; in2:=(in2+1) mod M2; counter2++;

if counter2=3 then {counter2:=0; V(full2);} V(mutex2); goto L2; end process Rk

begin L3:

P(full2); P(mutex2);

take an item from buffer2[out2]; out2:=(out2+1) mod M2;

take an item from buffer2[out2]; out2:=(out2+1) mod M2; V(mutex2);

V(empty2); V(empty2); V(empty2);

packet the products; goto L3; end } coend

20 在一个实时系统中，有两个进程P和Q，它们循环工作。P每隔1秒由脉冲寄存器获得

输入，并把它累计到整型变量W上，同时清除脉冲寄存器。Q每隔1小时输出这个整型变量的内容并将它复位。系统提供了标准例程INPUT和OUTPUT供I/O，提供了延时系统调用Delay（seconds）。试写出两个并发进程循环工作的算法。答：

var W，V:integer;

mutex:semaphore; W:=0;V:=0;mutex:1;

cobegin {

process P

begin repeat P(mutex); delay(1)； V:=INPUT； W:=W+V; 清除脉冲寄存器; V(mutex); untile false;

《操作系统教程》（第三版）CH3应用题参考答案

end process Q

begin repeat P(mutex); delay(60); OUTPUT(W); W:=0; V(mutex); untile false; } coend.

21 系统有同类资源m个，被n个进程共享，问：当m＞n和m≤n时，每个进程最多可以

请求多少个这类资源时，使系统一定不会发生死锁? 答：当m≤n时，每个进程最多请求1个这类资源时，系统一定不会发生死锁。当m>n时，如果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(1)+┅+alloc(n))

另一方面所有进程将陷入无限等待状态。可以推出 need(1)+ ┅+need(n)

上式表示死锁发生后，n个进程还需要的资源量之和小于n，这意味着此刻至少存在一个进程i,need(i)=0,即它已获得了所需要的全部资源。既然该进程已获得了它所需要的全部资源，那么它就能执行完成并释放它占有的资源，这与前面的假设矛盾，从而证明在这个系统中不可能发生死锁。

23 一条公路两次横跨运河，两个运河桥相距100米，均带有闸门，以供船只通过运河桥。

运河和公路的交通均是单方向的。运河上的运输由驳船担负。在一驳船接近吊桥A时就拉汽笛警告，若桥上无车辆，吊桥就吊起，直到驳船尾P通过此桥为止。对吊桥B也按同样次序处理。一般典型的驳船长度为200米，当它在河上航行时是否会产生死锁?若会，说明理由，请提出一个防止死锁的办法，并用信号量来实现驳船的同步。答：当汽车或驳船未同时到达桥A时，以任何次序前进不会产生死锁。但假设汽车驶过了桥A，它在继续前进，并且在驶过桥B之前，此时有驳船并快速地通过了桥A，驳船头到达桥B，这时会发生死锁。因为若吊起吊桥B让驳船通过，则汽车无法通过桥B；若不吊起吊桥B让汽车通过，则驳船无法通过桥B。可用两个信号量同步车、船通过两座桥的动作。

var Sa,Sb:semaphore;

《操作系统教程》（第三版）CH3应用题参考答案

Sa:=Sb:=1; cobegin {

process 驳船 begin P(Sa); P(Sb); 船过桥A、B; V(Sa); V(Sb); end process 汽车 begin P(Sa); P(Sb); 车过桥A、B; V(Sa); V(Sb); end } coend

24 Jurassic公园有一个恐龙博物馆和一个花园，有m个旅客和n辆车，每辆车仅能乘一个

旅客。旅客在博物馆逛了一会，然后，排队乘坐旅行车，当一辆车可用时，它载入一个旅客，再绕花园行驶任意长的时间。若n辆车都已被旅客乘坐游玩，则想坐车的旅客需要等待。如果一辆车已经空闲，但没有游玩的旅客了，那么，车辆要等待。试用信号量和P、V操作同步m个旅客和n辆车子。答：这是一个汇合机制，有两类进程：顾客进程和车辆进程，需要进行汇合、即顾客要坐进车辆后才能游玩，开始时让车辆进程进入等待状态。

var scl,sck,sc,kx,xc,mutex:semaphore; sck := kx:= sc:= xc:=0; sc1:=n;mutex:=1;

sharearea:一个登记车辆\\被服务乘客信息的共享区; cobegin

process 顾客i(i=1,2,?) begin

P(scl); /*车辆最大数量信号量 P(mutex); /*封锁共享区，互斥操作

在共享区sharearea登记被服务的顾客的信息：起始和到达地点，行驶时间 V(sck); /*释放一辆车，即顾客找到一辆空车 P(kx); /*车辆要配备驾驶员，顾客等待被载，上车；

V(sc); /*顾客进程已汇合到车辆进程，即顾客坐进车里 P(xc); /*待游玩结束后后，顾客等待下车

《操作系统教程》（第三版）CH3应用题参考答案

V(scl); /*空车辆数加1 end

Process 车辆j(j=1,2,?) begin

L: P(sck); /*车辆等待有硕客来使用

在共享区sharearea登记那一辆车被使用，并与顾客进程汇合； V(mutex); /*这时可开放共享区，让另一顾客雇车 V(kx); /*允许顾客用此车辆 P(sc);

/*车辆等待顾客上车

车辆载着顾客开行到目的地； v(xc); /*允许顾客下车 goto L; end coend

25 今有k个进程，它们的标号依次为1、2、…、k，如果允许它们同时读文件file，但必须

满足条件：参加同时读文件的进程的标号之和需小于K，请使用：1)信号量与P、V操作，2)管程，编写出协调多进程读文件的程序。答：1) 使用信号量与P、V操作

var waits,mutex:semaphore; numbersum:integer:=0; wait:=0;mutex:=1; cobegin {

process readeri(var number:integer;) begin P(mutex);

L: if numbersum+number≥K then {P(waits); goto L;} then numbersum:=numbersum+number; V(mutex); Read file; P(mutex);

numbersub:=numbersum-number; V(waits); V(mutex); }

2) 使用管程：

TYPE sharefile =MONITOR VAR numbersum,n:integer; SF:codition; DEFINE startread,endread; USE wait,signal,check,release;

procedure startread(var number:integer:);

《操作系统教程》（第三版）CH3应用题参考答案

begin

check(IM);

L: if (number+numbersum)≥K then {wait(SF,IM); goto L;} numbersum:=numbersum+number; release(IM); end

procedure endread(var number:integer;); begin

check(IM);

numbersum:=numbersum-number; signal(SF,IM); release(IM);

end begin

numbersum:=0; end. main() {cobegin process-i(); coend } process-i()

var number:integer; begin

number:=进程读文件编号; startread(number); read F; endread(number); end

26 设当前的系统状态如下，系统此时Available=(1，1，2)：

Claim Allocation 进程, R1 R2 R3 R1 R2 R3 P1 3 2 2 1 0 0 P2 6 1 3 5 1 1 P3 3 1 4 2 1 1 P4 4 2 2 0 0 2

(1) 计算各个进程还需要的资源数Cki-Aki? (2) 系统是否处于安全状态，为什么?

(3) P2发出请求向量request1(1，0，1)，系统能把资源分给它吗？

《操作系统教程》（第三版）CH3应用题参考答案

(4) 若在P2申请资源后，若P1发出请求向量request0(1，0，1)，系统能把资源分给它

吗？

(5) 若在P1申请资源后，若P3发出请求向量request0(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种资源，在某时刻进程P0、P1、P2、P3和P4对资源的占有

和需求情况如表，试解答下列问题：

Allocation A B C D 0 0 3 2 1 0 0 0 1 3 5 4 0 3 3 2 0 0 1 4 Claim A B C D 0 0 4 4 2 7 5 0 3 6 10 10 0 9 8 4 0 6 6 10 Available A B C D 1 6 2 2 Process P0 P1 P2 P3 P4

(1) 系统此时处于安全状态吗？

(2) 若此时P2发出request1(1、2、2、2)，系统能分配资源给它吗？为什么？答：(1)系统处于安全状态，存在安全序列：P0，P3，P4，P1，P2。 (2)不能分配，否则系统会处于不安全状态。

28 把死锁检测算法用于下面的数据，并请问：

Available=(1，0，2，0)

Need= 3 Allocation= 0 1 0 1 1 1 1 0 0 1 0 0 1 0 0 0 3 1 1 1 2 0 0 1 0 1 0 1 1 0 0 0 0 2 1 1 1 0 0 (1) 此时系统此时处于安全状态吗？

(2) 若第二个进程提出资源请求request2(0，0，1，0)，系统能分配资源给它吗？ (3) 若第五个进程提出资源请求request5(0，0，1，0)，系统能分配资源给它吗？答：(1)此时可以找出进程安全序列：P4，P1，P5，P2，P3。故系统处于安全状态。

(2)可以分配，存在安全序列：P4，P1，P5，P2，P3。 (3)不可分配，系统进入不安全状态。

29 考虑一个共有150个存储单元的系统，如下分配给三个进程，P1最大需求70,己占有25；

P2最大需求60,己占有40；P3最大需求60,己占有45。使用银行家算法，以确定下面的

《操作系统教程》（第三版）CH3应用题参考答案

任何一个请求是否安全。(1)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个单元)任何一个执行。安全序列为：

P1，P2，P3，P4，P3，P1，P2，P4 P1，P2，P3，P4，P3，P1，P4，P2 P1，P2，P3，P4，P3，P2，P1，P4 P1，P2，P3，P4，P3，P2，P4，P1 P1，P2，P3，P4，P3，P4，P1，P2 P1，P2，P3，P4，P3，P4，P2，P1

(2) P4进程到达，P4最大需求60,最初请求35。如果把35个单元分给P4，系统还余5

个单元，不再能满足任何一个进程的需求，系统进入不安全状态。

30 有一个仓库，可存放X、Y两种产品，仓库的存储空间足够大，但要求：(1) 每次只能

存入一种产品X或Y， (2) 满足-N

－N＜X产品数量－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－1个。

当往库中存放入一个X产品时，则允许存入Y产品的数量也增加1，故信号量sy应加1；当往库中存放入一个Y产品时，则允许存入X产品的数量也增加1，故信号量sx应加1。 var mutex：semaphore=1;/*互斥信号量*/

sx，sy：semaphore； sx=M-1; sy=N-1; cobegin {

process X { repeat P(sx); P(mutex); 将X产品入库； V(mutex); V(sy);

《操作系统教程》（第三版）CH3应用题参考答案

until false } process Y { repeat P(sy); P(mutex); 将Y产品入库； V(mutex); V(px); until false

} } coend.

31 有一个仓库可存放A、B两种零件，最大库容量各为m个。生产车间不断地取A和B

进行装配，每次各取一个。为避免零件锈蚀，按先入库者先出库的原则。有两组供应商分别不断地供应A和B，每次一个。为保证配套和合理库存，当某种零件比另一种零件超过n(n

var empty1，empty2，full1，full2：semaphore；

mutex，sa，sb：semaphore； in1，in2，out1，out2：integer；

buffer1，buffer2 ：array [0..m-1] of item； empty1：=empty2：=m； sa：=sb：=n；

in1：=in2：=out1：=out2：=0； cobegin {

process producerA

{ repeat P(empty1)； P(sa)； P(mutex)；

buffer1[in1] ：=A零件； in1：=(in1+1) mod m； V(mutex)； V(sb)； V(full1)； untile false； }

《操作系统教程》（第三版）CH3应用题参考答案

process producerB

{ repeat P(empty2)； P(sb)； P(mutex)；

Buffer2[in2] ：=B零件； in2：=(in2+1) mod m； V(mutex)； V(sa)； V(full2)； untile false； } process take { repeat

P(full1)； P(full2)； P(mutex)；

Take from buffer1[out1] and buffer2[out2]中的A、B零件； out1：=(out1+1) mod m； out2：=(out2+1) mod m； V(mutex)； V(empty1)； V(empty1)；

把A和B装配成产品； until false } } coend.

32 进程A1、A2、?、An1通过m个缓冲区向进程B1、B2、?、Bn2不断地发送消息。

发送和接收工作符合以下规则：

(1) 每个发送进程每次发送一个消息，写进一个缓冲区，缓冲区大小与消息长度相等； (2) 对每个消息，B1、B2、?、Bn2都需接收一次，并读入各自的数据区内；

(3) 当M个缓冲区都满时，则发送进程等待，当没有消息可读时，接收进程等待。试用信号量和PV操作编制正确控制消息的发送和接收的程序。

答：本题是生产者－消费者问题的一个变形，一组生产者A1，A2，…An1和一组消费者B1，B2，…Bn2共用m个缓冲区，每个缓冲区只要写一次，但需要读n2次。因此，可以把这一组缓冲区看成n2组缓冲区，每个发送者需要同时写n2组缓冲区中相应的n2个缓冲区，而每一个接收者只需读它自己对应的那组缓冲区中的对应单元。

应设置一个信号量mutex实现诸进程对缓冲区的互斥访问；两个信号量数组empty[n2]和full[n2]描述n2组缓冲区的使用情况。其同步关系描述如下：

var mutex,empty[n2],full[n2]：semaphore;

i:integer;mutex=1; for(i=0;i<=n2-1;i++)

《操作系统教程》（第三版）CH3应用题参考答案

{

empty[i]=m; full[i]=0; } main () { cobegin A1( ); A2( ); ┋ An1 (); B1 (); B2 (); ┋ Bn2( ); coend }

send ( ) /*进程Ai发送消息*/ { int i;

for (i=0;i<=n2-1;i++) p(empty[i]); p(mutex);

将消息放入缓冲区； V（mutex）; for(i=0;i<=n2-1;i++) V(full[i]); }

receive(i) /*进程Bi接收消息*/ {

p(full[i]); p(mutex);

将消息从缓冲区取出； V(mutex); V(emtpy[i]); }

Ai ( ) /*发送进程A1,A2,…An1的程序类似，这里给出进程Ai的描述*/ { while (1) { ┋ send ( );

《操作系统教程》（第三版）CH3应用题参考答案

┋ } }

Bi ( ) /*接收进程B1,B2,…Bn2的程序类似，这里给出进程Bi描述*/ { while (1) { ┋ receive(i); ┋ } }

33 某系统有R1设备3台，R2设备4台，它们被P1、P2、P3和P4进程共享，且已知这4

个进程均按以下顺序使用设备：

→申请R1→申请R2→申请R1→释放R1→释放R2→释放R1

(1) 系统运行中可能产生死锁吗？为什么？

(2) 若可能的话，请举出一种情况，并画出表示该死锁状态的进程—资源图。答：(1)系统四个进程需要使用的资源数为R1各2台，R2各1台。可见资源数不足，同时各进程申请资源在先，有可能产生死锁发生的四个条件，故系统可能产生死锁。

(2) 当三个进程执行完申请资源R1，开始执行申请资源R2时，第四个进程会因没有资

源R1而被阻塞。当三个进程执行完申请资源R2后，系统还剩1个R2资源。而这三个进程因执行申请第二个资源R1而全部被阻塞，系统进入死锁。

P1 P2 ● ● ● ●●●● P3

P4 34 如图所示，左右两队杂技演员过独木桥，为了保证安全，请用PV操作和信号量来解决

过独木桥问题。只要桥上无人，则允许一方的人过桥，待一方的人全部过完后，另一方的人才允许过桥。

《操作系统教程》（第三版）CH3应用题参考答案

答：

var wait,mutex1,mutex2,bridge1,bridge2:semaphore; mutex1:=mutex2:=bridge1:=bridge2:=1;wait:=0; counter1,counter2:integer; cobegin {

process P左 process P右

begin begin

P(mutex1); P(mutex2); count1++; count2++;

if count1=1 then P(wait); if count2=1 then P(wait); V(mutex1); V(mutex2); P(bridge1); P(bridge2); 过独木桥; 过独木桥;

V(bridge1); V(bridge2); P(mutex1); P(mutex2);

Count1-- count2--; if count1=0 then V(wait); if count2=0 then P(wait); V(mutex1); V(mutex2); end end }coend

35 修改读者-写者的同步算法，使它对写者优先，即一旦有写者到达，后续的读者必须等待，

而无论是否有读者在读文件。(1)用信号量和P、V操作实现；(2)用管程实现。答：(1) 用信号量和P、V操作实现。

为了提高写者的优先级，增加一个信号量s，用于在写进程到达后封锁后续的读者。其控制流程如下：

var rmutex，wmutex，S：semaphore； rmutex=1;wmutex=1; S=1; count:integer:=0; main ( ) { cobegin reader ( ); writer ( ); coend } reader ( ) begin

while (1) { P(S); P(rmutex);

if (count==0) p(wmutex);

《操作系统教程》（第三版）CH3应用题参考答案

count++; V(rmutex); V(S); 读文件； p(rmutex); count--;

if (count==0) v(wmutex); V(rmutex); } end writer( ) begin while(1) { P(S); P(wmutex); 写文件； V(wmutex); V(S); } end.

(2)用管程实现。

TYPE read-write=monitor VAR rc, wc : integer; R, W : condition;

DEFINE start-read, end-read, start-writer, end-writer; USE wait,signal,check,release; procedure start-read; begin

check(IM);

if wc>0 then wait(R,IM); rc := rc + 1; signal(R, IM); release(IM); end;

procedure end-read; begin

check(IM); rc := rc - 1;

if rc=0 then signal(W,IM); release(IM); end;

procedure start-write; begin

check(IM); wc := wc + 1;

《操作系统教程》（第三版）CH3应用题参考答案

if rc>0 or wc>1 then wait(W,IM);

release(IM); end;

procedure end-write; begin

check(IM); wc := wc - 1;

if wc>0 then signal(W,IM); else signal(R, IM); release(IM); end; begin

rc := 0; wc := 0; R := 0; W := 0; end.

Cobegin {

process P1

begin ……

call read-writer.start-read; …… read; ……

call read-writer.end-read; ……

end;

process P2

begin ……

call read-writer.start-write; …… write; ……

call rear-writer.end-write; …… end; } coend.

36 假定某计算机系统有R1和R2两类可再使用资源（其中R1有两个单位，R2有一个单

位），它们被进程P1，P2所共享，且已知两个进程均以下列顺序使用两类资源。 →申请R1→申请R2→申请R1→释放R1→释放R2→释放R1→

试求出系统运行过程中可能到达的死锁点，并画出死锁点的资源分配图（或称进程－资源图）。答：当两个进程都执行完第一步(都占用R1) 时，系统进入不安全状态。这时无论哪个进程执行完第二步，死锁都会发生。可能到达的死锁点：进程P1占有一个R1和一个R2，而进程P2占有一个R1。或者相反。这时己形成死锁。进程---资源图为：

《操作系统教程》（第三版）CH3应用题参考答案

P1 P1 ．． P1

P1 37 某工厂有两个生产车间和一个装配车间，两个生产车间分别生产A、B两种零件，装配

车间的任务是把A、B两种零件组装成产品。两个生产车间每生产一个零件后都要分别把它们送到装配车间的货架F1、F2上，F1存放零件A，F2存放零件B，F1和F2的容量均为可以存放10个零件。装配工人每次从货架上取一个A零件和一个B零件，然后组装成产品。请用：(1)信号量和P、V操作进行正确管理，(2)管程进行正确管理。答：(1) 信号量和P、V操作进行正确管理。

var F1,F2:ARRAY[0..9] of item; SP1,SP2,SI1,SI2:semaphore; in1,in2,out1,out2:integer; in1:=0;in2:=0;out1:=0;out2:=0; SP1:=10;SP2:=10;SI1:=0;SI2:=0; main() {cobegin producer1( ); producer2( ); installer( ) coend }

process producer1() begin while (true) {

produce A 零件; P(SP1); F1[in1]:=A;

in1:=(in1+1) MOD 10 V(SI1); } end

process producer2() begin

while (true)

{

produce B 零件; P(SP2); F2[in2]:=B;

in2:=(in2+1) MOD 10 V(SI2); } end

process installer() var product:item; begin while (true) { P(SI1);

product1:=F1[out1]; out1:=(out1+1) MOD 10; V(SP1); P(SI2);

product2:=F2[out2]; out2:=(out2+1) MOD 10; V(SP2); 组装产品;

} end

(2) 管程进行正确管理。

TYPE produceprodut=monitor

VAR F1,F2:ARRAY[0..9] of item; SP1,SP2,SG1,SG2:condition;

in1,in2,out1,out2:integer; inc1,inc2: integer;

DEFINE put1, put2, get; USE wait,signal,check,release; procedure put1(A); begin

check(IM);

if inc1=10 then wait(SP1,IM); inc1:=inc1+1;

F1[in1]:=A;

in1:=(in1+1) MOD 10

signal(SG1, IM); release(IM); end;

procedure put2(B); begin

check(IM);

《操作系统教程》（第三版）CH3应用题参考答案

if inc2=10 then wait(SP2,IM);

inc2:=inc2+1;

F2[in2]:=B;

in2:=(in2+1) MOD 10

signal(SG2, IM); release(IM); end;

procedure get(A,B); begin

check(IM);

if inc1=0 then wait(SG1,IM); if inc2=0 then wait(SG2,IM); inc1:=inc1-1; inc2:=inc2-1;

A:=F1[out1];

out1:=(out1+1) MOD 10 B:=F2[out2];

Out2:=(out2+1) MOD 10

signal(SP1, IM); signal(SP2, IM); release(IM); end;

begin

in1:=0;in2:=0;out1:=0;out2:=0;inc1:=0;inc2:=0; SP1:=0;SP2:=0;SG1:=0;SG2:=0;

end.

cobegin {

process Produce1

begin

while (true) {

produce A 零件;

call produceprodut.put1(A);

}

end;

process Produce2

begin

while (true) {

produce B零件;

call produceprodut.put2(B);

}

end;

process consume

《操作系统教程》（第三版）CH3应用题参考答案

begin

while (true) {

call produceprodut.get(A,B);

组装产品; }

end;

} coend.

38 桌上有一只盘子，最多可以容纳两个水果，每次仅能放入或取出一个水果。爸爸向盘子

中放苹果(apple)，妈妈向盘子中放桔子(orange)，两个儿子专等吃盘子中的桔子，两个女儿专等吃盘子中的苹果。试用：(1)信号量和P、V操作，(2)管程，来实现爸爸、妈妈、儿子、女儿间的同步与互斥关系。答：(1)用信号量和P、V操作。类似于课文中的答案，扩充如下：1) 同步信号量初值为2；2) 要引进一个互斥信号量mutex，用于对盘子进行互斥；3)盘子中每一项用橘子、苹果2个枚举值。

var

plate ARRAY[0,1] of (apple, orange);

flag0,flag1:boolean; mutex:semaphore;

sp:semaphore; /* 盘子里可以放几个水果 */ sg1，sg2:semaphore; /* 盘子里有桔子，有苹果?*/ sp := 2; /* 盘子里允许放入二个水果*/ sg1:=sg2:= 0; /* 盘子里没有桔子，没有苹果 */ flag0:=flag1:=false;mutex:=1; cobegin process son process father begin begin L3: P(sg1); L1: 削一个苹果; P(mutex); P(sp); if (flag0 & plate[0]= =桔子) then P(mutex); { x := plate[0];flag0:=false;} if (flag0==false) then else { x:= plate[1]; flag1:=false;} {plate [0]:=苹果; flag0:=true;} V(mutex); else { plate[1]:=苹果; flag1:=true; } V(sp); V(mutex); 吃桔子; V(sg2); goto L3; goto L1; end; end; process daughter process mother begin begin L4: P(sg2); L2: 剥一个桔子; P(mutex); P(sp); if (flag0 & plate[0]= =苹果) then P(mutex); { x := plate[0];flag0:=false;} if (flag0==false) then else { x:= plate[1]; flag1:=false;}

《操作系统教程》（第三版）CH3应用题参考答案

{plate [0]:=桔子; flag0:=true;}

else { plate[1]:=桔子; flag1:=true; }

V(mutex); V(sg1); goto L2; end; V(mutex); V(sp); 吃苹果; goto L4; end; coend.

(2)用管程。

TYPE FMSD = MONITOR

VAR plate ARRAY[0,1] of (apple, orange); count:integer; flag0,flag1:boolean; SP, SS, SD : codition; DEFINE put, get;

USE wait, signal, check, release； procedure put(var fruit:(apple, orange)); begin check(IM);

if (count==2) then wait(SP,IM)； else {if (flag0==false) then

{plate [0]:= fruit; flag0:=true;} else {plate[1]:=fruit; flag1:=true; } count:=count+1;

if (fruit==orange) then signal(SS,IM)； else signal(SD,IM); } release(IM); end;

procedure get(varfruit:(apple,orange),x:plate); begin check(IM);

if (count= =0) or plate<>fruit then begin

if (fruit= =orange) then wait(SS,IM)； else wait(SD,IM)； end; count:=count-1;

if (flag0 & plate[0]= =fruit) then { x := plate[0];flag0:=false;} else { x:= plate[1]; flag1:=false;} signal(SP, IM); release(IM); end; begin

count:=0;flag0:=false;flag1:=false; SP := 0; SS := 0; plate[0]:=plate[1]:=null;

SD := 0；《操作系统教程》（第三版）CH3应用题参考答案

end; main() {cobegin process father begin while (1) {

准备好苹果; call FMSD.put(apple); …… } end; process mother begin while (1) { 准备好桔子;

call FMSD.put(orange); …… } end; process son begin while (1)

{ call FMSD.get(orange,x); 吃取到的桔子; …… } end;

process daughter begin while (1)

{ call FMSD.get(apple,x); 吃取到的苹果; …… } end; } coend

39 一组生产者进程和一组消费者进程共享九个缓冲区，每个缓冲区可以存放一个整数。生

产者进程每次一次性向3个缓冲区写入整数，消费者进程每次从缓冲区取出一个整数。请用：(1)信号量和P、V操作，(2)管程，写出能够正确执行的程序。答：(1)信号量和P、V操作。

var buf:ARRAY [0..8] of integer; count,getptr,putptr:integer; count:=0;getptr:=0;putptr:=0; S1,S2,SPUT,SGET;semaphore; S1:=1;S2:=1;SPUT:=1;SGET:=0; main() { cobegin

producer-i(); consumer-j(); coend }

process producer-i begin

L1:生产3个整数; P(SPUT); P(S1);

buf[putptr]:=整数1; putptr:=(putptr+1) MOD 9; buf[putptr]:=整数2; putptr:=(putptr+1) MOD 9; buf[putptr]:=整数3; putptr:=(putptr+1) MOD 9; V(SGET); V(SGET); V(SGET): V(S1); goto L1 end

process consumer-j var y:integer; begin L2:P(SGET); P(S2); y:=buf[getptr];

getptr:=(getptr+1) MOD 9; count:=count+1; if count = 3 then begin count:=0; V(SPUT); end V(S2);

consume the 整数y; goto L2;

《操作系统教程》（第三版）CH3应用题参考答案

end

(2) 管程。

TYPE get-put = MONITOR VAR buf ARRAY[0..8] of integer; count,getptr,putptr:integer; SP,SG;codition; DEFINE put, get;

USE wait, signal, check, release； procedure put(var a1,a2,a3:integer;); begin check(IM);

if (count>6) then wait(SP,IM)； count:=count+3; buf[putptr]:=a1;

putptr:=(putptr+1) MOD 9; buf[putptr]:=a2;

putptr:=(putptr+1) MOD 9; buf[putptr]:=a3;

putptr:=(putptr+1) MOD 9; signal(SG,IM); release(IM); end;

procedure get(b); begin check(IM);

if (count= =0) then wait(SG,IM)； b:=buf[getptr];

getptr:=(getptr+1) MOD 9; count:=count+1;

if count < 7 then signal(SP, IM); else if count > 0 then signal(SG,IM); release(IM); end; begin

count:=0;getptr:=0;putptr:=0; SP:=0;SG:=0; end; cobegin {

process producer-i begin

L1:生产3个整数;

Call get-put.put(a1,a2,a3);

《操作系统教程》（第三版）CH3应用题参考答案

goto L1 end

process consumer-j var y:integer; begin

L2: call get-put.get(b) consume the 整数b; goto L2; end } coend

40 设有三个进程P、Q、R共享一个缓冲区，P进程负责循环地从磁带机读入一批数据并放

入缓冲区，Q进程负责循环地从缓冲区取出P进程放入的数据进行加工处理并把结果放入缓冲区，R进程负责循环地从缓冲区读出Q进程放入的数据并在打印机上打出。请用：(1)信号量和P、V操作，(2)管程，写出能够正确执行的程序。答：(1)信号量和P、V操作

var Sp,Sq,Sr:semaphore;

buf:integer; Sp:=1;Sq:=Sr:=0; cobegin {

process P

begin repeat

从磁带读入数据； P(Sp); buf:=data; V(Sq); until false; end process Q

begin repeat P(Sq); data:=buf; 加工处理data; buf:=data; V(Sr); until false; end process R

begin repeat

P(Sr); data:=buf; V(Sp); 打印数据 until false; end } coend.

(2) 管程。

TYPE PQR=MONITOR VAR buf:integer; SP,SQ,SR:codition;

turn:{p,q,r};

DEFINE PPUT,QGET,QPUT,RGET; USE wait,signal,check,release; procedure PPUT(var data:integer;); begin check(IM);

if turn !=p then wait(SP,IM); turn:=q; buf:=data; signal(SQ,IM); release(IM); end

procedure QGET(var data:integer;); begin check(IM);

if turn !=q tnen wait(SQ,IM) data:=buf release(IM); end

procedure QPUT(var data:integer;); begin

check(IM); turn:=r; buf:=data; signal(SR,IM); release(IM); end

procedure RGET(var data:integer;); begin check(IM);

if turn !=r tnen wait(SR,IM);

《操作系统教程》（第三版）CH3应用题参考答案

turn:=p; data:=buf signal(SP,IM); release(IM); end begin

SP:=0;SQ:=0;SR:=0;turn:=p; end main() { cobegin process P x:=integer; begin

LP:从文件读入一个数据到x; PPUT(x); goto LP; end process Q

x:=integer; begin

LQ:QGET(x); 加工处理x; QPUT(x); goto LQ; end process R

x:=integer; begin

LR:RGET(x); 打印x; goto LR; end } coend

41 下述流程是解决两进程互斥访问临界区问题的一种方法。试从“互斥”(mutual

exclusion)、“空闲让进”(progress)、“有限等待”(bounded waiting)等三方面讨论它的正确性。如果它是正确的，则证明之；如果它不正确，请说明理由。

program attemp; var c1,c2:integer;

procedure p1; (/* 对第一个进程p1 */) begin

repeat

Remain Section 1;

《操作系统教程》（第三版）CH3应用题参考答案

repeat c1:=1-c2 until c2<>0;

Critical Section; (/* 临界区 */) c1:=1

一

until false end;

procedure p2; (/* 对另一个进程p2 */) begin

repeat

Remain Section 2;

repeat c2:=1-c1 until c1<>0;

Critical Section; (/* 临界区 */) c2:=1

until false end;

begin (/* 主程序 */)

c1:=1; c2:=1; cobegin

p1;p2 (/* 两进程p1, p2开始执行 */) coend

end.

答：(1)互斥

己知c1和c2的初值为1，若进程P1执行到c1:=1-c2时，进程P2也同时执行c2:=1-c1。这样一来，

c1和c2的值都变为0，接着再各自执行repeat ---untile循环语句c1:=1-c2和c2:=1-c1时，c1和c2就又都变回了1。于是，P1和P2会同时进入临界区，不满足互斥条件。

(2) 有空让进

设开始无进程在临界区中，进程P1执行了c1:=1-c2，由于c2的初值为1，这使得c1的值变为0但c2仍为1，从而保证了P1进入临界区。当P1退出临界区时，执行了c1:=1，使得P2就可进入临界区。进程P2先执行的情况相似，能保证有空让进的原则。

(3) 有限等待

假定进程P1在临界区执行，进程P2申请进入临界区，则因进程P1会在有限时间内执行完并退出临界区，然后，将执行c1:=1，这使得进程P2因c1值为1而立即可进入临界区。因而，能满足有限等待的原则。

42 分析下列算法是否正确，为什么?

repeat

《操作系统教程》（第三版）CH3应用题参考答案

key：=true； repeat

swap(lock，key)； until key=false；

Critical Section; (/* 临界区 */)

lock：=false；

other code； until false；

答：由于lock的初值未定，如果它的值false，则可通过swap实现上锁操作。但如果lock的初

值为true，那么，进程会永远等待而进不了临界区。

以下并发执行的程序，仅当数据装入寄存器后才能加1。 const n=50；

var tally ：integer； procedure total( ) var count：integer； begin

for count：=1 to n do tally：=tally+1 end；

begin (/*main program*/) tally：=0； cobegin

total()；total() coend；

writeln(tally)； end．

给出该并发程序输出的tally值的上限和下限。答：tally值的上限和下限为100和50。

44 举例说明下列算法不能解决互斥问题。 var balocked：array[0．．1] of boolean； turn：0．．1；

procedure P[id：integer]； begin

repeat

blocked[id]：=true； while turn≠id do begin

while blocked[1-id] do skip； turn：=id； end；

{critical section}

《操作系统教程》（第三版）CH3应用题参考答案

blocked[id]：=false；

{remainder} until false end； begin

blocked[0]：=blocked[1]：=false； turn：=0； cobegin

P[0]；P[1] coend； end．

答：为方便描述，把程序语句进行编号：

blocked[id]：=true； ① while turn≠id do ② begin

while blocked[1-id] do skip； ③ turn：=id； ④ end；

假设id=0，则1-id=1，并且turn=1。当进程P[id]先执行①置blocked[id]=true；接着执行②

时，因为turn≠id而进入到③执行。此时，因blocked[1-id]为false(初值)，故在③上不做空操作而打算去做④。麻烦的事情发生了，如果在P[id]执行④之前，系统又调度执行P[1-id]，而P[1-id]在执行了①置blocked[1-id]=true之后，在执行②时，因发现turn=1-id，故退出了while，直接进入临界区。而这时P[id]继续执行④，虽然置turn=id但已无法挡住P[1-id]先己进入了临界区的事实，此后，P[id]也进入临界区。

所以，该算法不能解决互斥问题，它会让两个进程同时进入临界区。

45 现有三个生产者P1、P2、P3，他们都要生产桔子水，每个生产者都已分别购得两种不

同原料，待购得第三种原料后就可配制成桔子水，装瓶出售。有一供应商能源源不断地供应糖、水、桔子精，但每次只拿出一种原料放入容器中供给生产者。当容器中有原料时需要该原料的生产者可取走，当容器空时供应商又可放入一种原料。假定：生产者P1已购得糖和水；生产者P2已购得水和桔子精；生产者P3已购得糖和桔子精；

试用：1)管程，2)信号量与P、V操作，写出供应商和三个生产者之间能正确同步的程序。答：1)管程。

TYPE makedrink=monitor VAR S,S1,S2,S3:condition;

container:item;

DEFINE give，produce1，produce2，produce3; USE check,wait,signal,release; procedure give

begin

《操作系统教程》（第三版）CH3应用题参考答案

Check(IM);

take raw material;

if container≠null then wait(S,IM); else container:= raw material;

if (container)= 桔子精 then signal(S1,IM); else if (container)=糖 then signal(S2,IM); else signal(S3,IM); release(IM); end

procrdure produce1

begin

check(IM);

if (container)≠ 桔子精 then wait(S1,IM);

else { take the桔子精 from container; 做桔子水;} signal(S,IM); release(IM); end

procrdure produce2

begin

check(IM);

if (container)≠糖 then wait(S2,IM);

else { take the糖from container; 做桔子水;} signal(S,IM); release(IM); end

procrdure produce3

begin

check(IM);

if (container)≠水 then wait(S3,IM);

else { take the水from container; 做桔子水;} signal(S,IM); release(IM); end begin

container{糖,水,桔子精}; end cobegin {

process供应商 begin

repeat ?

Call makedrink.give(); ?

《操作系统教程》（第三版）CH3应用题参考答案

until false;

end.

Process P1

begin

repeat ?

Call makedrink.produce1(); ?

until false; end.

Process P2

begin

repeat ?

Call makedrink.produce2(); ?

until false; end.

Process P3

begin

repeat ?

Call makedrink.produce3(); ?

until false; end. }

coend.

2) 信号量与P、V操作

var S,S1,S2,S3:=semaphore;

S:=1;S1:=S2:=S3:=0; container{糖,水,桔子精}; cobegin

{ process 供应商

begin

repeat P(S);

take raw material into container;

if (container)= 桔子精 then V(S1); else if (container)=糖 then V(S2); else V(S3); untile false;

《操作系统教程》（第三版）CH3应用题参考答案

end

process P1

begin

repeat P(S1);

take the桔子精 from container; V(S);

做桔子水; untile false; end process P2

begin

repeat P(S2);

take the糖from container; V(S);

做桔子水; untile false; end process P3

begin

repeat P(S3);

take the 水 from container; V(S);

做桔子水; untile false; end }

coend.

46 有一材料保管员，他保管纸和笔若干。有A、B两组学生，A组学生每人都备有纸，B

组学生每人都备有笔。任一学生只要能得到其他一种材料就可以写信。有一个可以放一张纸或一支笔的小盒，当小盒中无物品时，保管员就可任意放一张纸或一支笔供学生取用，每次允许一个学生从中取出自己所需的材料，当学生从盒中取走材料后允许保管员再存放一件材料，请用：1)信号量与P、V操作，2)管程，写出他们并发执行时能正确工作的程序。答：1)信号量与P、V操作。

var S,Sa,Sb,mutexa,mutexb:semaphore;

S:=mutexa:=mutexb:=1;Sa:=Sb:=0; box:(paper,pen); cobegin {

process 保管员

begin

repeat P(S);

take a material into box;

if (box)=paper then V(Sa); else V(Sb); untile false; end

process A组学生

begin repeat P(Sa); P(mutexa);

take the pen from box; V(mutexa); V(S);

write a letter; untile false; end

process B组学生