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

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 := 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 k; rptr := ( rptr+1) mod k; manage the message in x ; V(smanage) ; B[mptr] := x; goto L1 ; V(swrite) ; end ; 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) ; P(sput1) ; x :=A[get1]; A[put1] := x ; get1 :=(get1+1) mod k;

17

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) ; x :=B[get2] ;

get2 :=(get2+1) mod k;

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

put1 := (put1+1) mod k ;

V(sget1) ; Goto L1 ; end ;

V(sput1) ;

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

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

V(sput2) ;

Print the message in x ; Goto L3 ; end ;

coend

2

设有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： 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; ⑥ V(S1); P(S1);

z:=y+1; ③ x:=x+y; ⑦

18

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

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操作：

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.

19

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

5 在一个盒子里，混装了数量相等的黑白围棋子。现在用自动分拣系统把黑子、白子分开，设分拣系统有二个进程P1和P2，其中P1拣白子；P2拣黑子。规定每个进程每次拣一子；当一个进程在拣时，不允许另一个进程去拣；当一个进程拣了一子时，必须让另一个进程去拣。试写出两进程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 设公共汽车上，司机和售票员的活动分别如下：

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

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

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

20