操作系统教程_孙钟秀(第四版)课后习题答案

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

Process the products ; P ( emPty2) ; P ( mutex2 ) ;

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

if counter2 = 3 then { counter2:=0 ;V( full2 ) ; } V ( mutex2) ; goto L2 ; 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 ;

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 小时输出这个整型变量的内容并将它复位。系统提供了标准例程创PUT 和OUT 卫UT 供拍,提供了延时系统调用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 ; 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))

如果在这个系统中发生了死锁,那么一方面m 个资源应该全部分配出去,alloc (1) +?+alloc ( n )=m

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

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

于是有n×( m-1 ) + 1

这说明当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:=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 辆车都己被旅客乘坐游玩,则想坐车的旅客需要等待。如果一辆车己经空闲,但没有游玩的旅客了,那么,车辆要等待。试用信号量和P 、V 操作同步m 个旅客和n 辆车子。 答:这是一个汇合机制,有两类进程:顾客进程和车辆进程,需要进行汇合、即

顾客要坐进车辆后才能游玩,开始时让车辆进程进入等待状态 var sc1 , sck , sc ,Kx,xc ,mutex : semaphore ; sck:=kx:=sc:=xc:=0; sc1:=n ;mutex : = 1 ;

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

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

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

在共享区sharearea 登记被服务的顾客的信息:起始和到达地点,行驶时间 V ( sck ) ; /* 释放一辆车 ,即顾客找到一辆空车 P (Kx); /* 待游玩结束之后,顾客等待下车 V ( sc1 ) ; /*空车辆数加1 End

Process 车辆j(j=1,2,3?) Begin

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

在共享区sharearea登记那一辆车被使用,并与顾客进程汇合; V(mutex); /*这时可开放共享区,让另一顾客雇车 V(kx); /*允许顾客用此车辆 车辆载着顾客开行到目的地; V(xc); /*允许顾客下车 Goto L; End coend

25 今有k 个进程,它们的标号依次为1 、2 、? 、k ,如果允许它们同时读文件file ,但必须满足条件:参加同时读文件的进程的标号之和需小于K ,请使用:1 )信号量与P 、v 操作,2 )管程,编写出协调多进程读文件的程序。 答1 : l )使用信号量与P 、v 操作 var waits , mutex :semphore ; numbersum:integer:=0 ; wait:=0;mutex:=1 ; cobegin {

process readeri ( var number:integer ; ) begin

P(mutex ) ;

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

P(mutex ) ;

numbersum: = 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 : ) ; 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):

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4