操作系统 - - - - 课后答案(1) 下载本文

《操作系统教程》(第三版)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