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

法:每一个管程都对应一个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=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 )用管程实现消息传递。

答:( 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 )用消息传递实现信号量。

答:( l )用信号量实现消息传递; 1 )把消息队列组织成一个共享队列,用一个互斥信号量管理对该队列的入队操作和出队操作.

2 )发送消息是一个入队操作,当队列存储区满时,设计一个同步信号量阻塞

send 操作。

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

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

l )为每一个信号量建立一个同步管理进程,它包含了一个计数器,记录信号量值;还为此信号量设立一个等待进程队列

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] mod 5) / * i =4P(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 ; while turn≠1 do

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

while (j < n ) & (j==1 or flag[j] ≠in_cs ) do j:=j + 1 ; until j≥n :

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

until false ; end .

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

答:为方便描述,把Dijkstra 程序的语句进行编号: repeat

flag[i]:=want_in ;① while turn≠i do ②

if flag[trun]==idle then turn:=i ;③ flag[i]: = in_cs ;④ j:= O ;

while(j < n ) & (j==1 or flag[j] ≠in_cs )⑤ do j:=j + 1 ; @ until j≥n ;

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

( l )满足互斥条件

当所有的巧都不在临界区中,满足flag[j]≠in_cs(对于所有j , j≠i )条件时,Pi 才能进入它的临界区,而且进程Pi 不会改变除自己外的其他进程所对应的flag[j]的值。另外,进程Pi 总是先置自己的flag[j]为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=l , 2 , ?n-l)交错执行语句① 后(这时flag[j]=want_in),再做语句② (第一个while 语句),来查询flag[turn]的状态。显然,都满足turn≠i ,所以,都可以执行语句③ ,让自己的turn 为j 。但turn仅有一个值,该值为最后一个执行此赋值语句的进程号,设为k 、即turn=k (1≤k≤n -1 )。接着,进程Pj(j=1,2,?n-l ) 交错执行语句④ ,于是最多同时可能有n-1 个进程处于in_cs 状态,但不要忘了仅有一个进程能成功执行语句④ ,将

加m 置为自己的值。

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

vars , S1 ,S2 , S3 ; semaphore ; S:=1 ; S1:=S2:=S3:=0 ;

fiag1 , flag2 , fiag3 : Boolean ; fiag1:=flag2:=flag3:=true; cobegin {

process 供应者 begin repeat P(S) ;

取两样香烟原料放桌上,由flagi标记; / * nago1 、nage2 、nage3 代表烟草、纸、火柴

if flag2 & flag3 then V(S1) ; / *供纸和火柴

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

process 吸烟者1 begin repeat P(S1) ; 取原料; 做香烟; V(S) ; 吸香烟;

untile false ; process 吸烟者2

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