操作系统第五版费祥林-课后习题答案参考

end

procedure pickup-white ; begin

check ( IM ) ;

if not flag then wait(S-white,IM ); flag :=false ; pickup a white ;

signal ( S-black,IM ) ; release ( IM ) ; end begin

flag:=true ; end

main ( ) { cobegin

process -B ( ) ; process -W ( ) ; coend }

process-B ( ) begin

pickup-chess.pickup-black ( ) ; other ; end

process-W ( ) begin

pickup-chess.pickup-white( ) ; other ; end

6 管程的同步机制使用条件变量和wait 及signal ,尝试为管程设计一种仅仅使用一个原语操作的同步机制。

答:可以采用形如waituntil <条件表达式>的同步原语。如waituntil

( numbersum + number < K ) 表示进程由于条件不满足而应等待,当进程号累加和小于K 时,系统应唤醒该进程工作.

7 设公共汽车上,司机和售票员的活动分别如下: 司机的活动:启动车辆:正常行车;到站停车。 售票员的活动:关车门;售票;开车门。

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

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

机停车取得同步。应设置两个信号量: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 ( 51 ) 售票;

P ( S2 ) 开车门; 上下乘客; } end

8、一个快餐厅有4 类职员:( l )领班:接受顾客点菜;( 2 )厨师:准备顾客的饭菜;( 3 ) 包工:将做好的饭菜打包;( 4 )出纳员:收款并提交食品。每个职员可被看作一个进程,试用一种同步机制写出能让四类职员正确并发运行的程序。

答:典型的进程同步问题,可设四个信号量51 、S2 、S3 和S4 来协调进程工作。 var S1 , S2 ,S3 , S4 : semaphore ; S1 : = 1 ;S2 :=S3 : = S4 : = 0 ; cobegin { process P1 begin repeat

有顾客到来; P ( S1 ); 接受顾客点菜;

V ( 52 );

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( 54 ) ;

收款并提交食品;V ( 51 ) ; ufltile false ; end }

coend .

9、在信号量S上作P 、v 操作时,S的值发生变化,当S> 0、S=0、S< 0 时,它们的的物理意义是什么? 答:S 的值表示它代表的物理资源的使用状态:S > 0 表示还有共享资源可供使用。S 阅表示共享资源正被进程使用但没有进程等待使用资源。S < 0 表示资源已被分配完,还有进程等待使用资源。

10 ( 1 )两个并发进程并发执行,其中,A 、B 、C 、D 、E 是原语,试给出可能的并发执行路径。 Process P Process Q begin begin A ; D ; B ; E ; C ; end : end ;

( 2 )两个并发进程P1 和P2 并发执行,它们的程序分别如下: P 1 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 ;① printk ;③ k:=k+l ;② k:=0 ;④

until false ; until false ;

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

① 、② 、③ 、④ ,这时的打印值为:47 ③ 、④ 、① 、② ,这时的打印值为:23 ① 、③ 、② 、④ ,这时的打印值为:46 ① 、③ 、④ 、② ,这时的打印值为:46 ③ 、① 、② 、④ ,这时的打印值为:23 ③ 、① 、④ 、② ,这时的打印值为:23

由于进程P1和P2 并发执行,共享了变量K ,故产生了‘结果不唯一’。 11 证明信号量与管程的功能是等价的: ( l )用信号量实现管程; ( 2 )用管程实现信号量。 答:( 1 )用信号量实现管程;

Hoare 是用信号量实现管程的一个例子,详见课文内容。下面介绍另一种简单方法:每一个管程都对应一个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 ;

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