操作系统习题问题详解第 (3)

文档CH3 应用题参考答案1、 有三个并发进程：R 负责从输入设备读入信息块，M 负责对信息块加工处理；P 负责打印输出信息块。今提供；l 一个缓冲区，可放置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 : = O ; mptr : integer : = O ; wptr ：integer : = 0 ; x : item cobegin process reader ; process manager ; process writer ; begin begin begin LI : read a message intox ; L2 : P ( smanage ) ; L3 : P ( swnte ) ; P ( sread ) ; x:=Bmptr; x:=Bswrite;Brptr:=x; mptr:=(mptr+1) mod k; wptr:=(wptr+1) mod k;Rptr:=(rptr+1) mod k; manage the message in x; V(sread);V(smanage); Bmptr:=x; print the message in x;Goto L1; V(swrite); goto L3;End; goto L2; end;End;coend2 ) var A , B :array 0 , k -l of item ; sPut1 : semaphore:=k; SPut2: semaPhore:=k; sget1 : semaPhore : = 0 ; sget2 : semaphore : = 0 ; put1 ：integer ：=O ; put2：integer : = 0 ; get1 ：integer ：=O ; get2 : integer : = O ; cobegin process reader ; processn manager; process Writer ; begin begin begin Ll : read a message into x ; L2 : P ( sgetl ) ; L3 : P ( sgetZ ) ; P ( SPut1 ) ; x : = A get1 ; x : = B get2; A put1:=x ; get1 ：(get1+1 ) mod k ; get2:=get2 + l ) mod k ;Put1:=(put1+1) mod k; V(sput1); V(sput2);V(sget1); manage the message into x; print the message in x;Goto L1; P(sput2); goto L3; Put2:=(put2+1) mod k; V(sget2); Goto L2; End;Coend2 设有n 个进程共享一个互斥段，如果：( 1 每次只允许一个进程进入互斥段；( 2 每次最多允许m 个进程m 簇n 同时进入互斥段。试问：所采用的信号量初值是否一样？信号量值的变化围如何？答：所采用的互斥信号量初值不同。1 互斥信号量初值为1 ，变化围为-nl , 1 。当没有进程进入互斥段时，信号量值为1 ；当有1 个进程进入互斥段但没有进程等待进入互斥段时，信号量值为O ；当有1 个进程进入互斥段且有一个进程等待进入互斥段时，信号量值为-1 ；最多可能有n -1 个进程等待进入互斥段，故此时信号量的值应为-n - 1 也就是-n+1 。2 互斥信号量初值为m ，变化围为-nm , m 。当没有进程进入互斥段时，信号量值为m ；当有1 个进程进入互斥段但没有进程等待进入互斥段时，信号量值为m - 1 ：当有m 个进程进入互斥段且没有一个进程等待进入互斥段时，信号量值为0 ：当有m 个进程进入互斥段且有一个进程等待进入互斥段时，信号量值为一l ；最多可能有n - m 个进程等待进入互斥段，故此时信号量的值应为-(n-m)也就是-n+m.3 有两个优先级一样的进程P1和P2，各自执行的操作如下，信号量S1和S2初值均为0。试问Pl 、P2 并发执行后，x 、y 、z 的值各为多少？ P1: P2:Begin beginY:=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 ：XY ;P(s2); V(S2);Y:=z+y; z：=Z+X； End end 、 、 和 是不相交语句，可以任何次序交织执行，而结果是唯一的。接着无论系统如何调度进程并发执行，当执行到语句 时，可以得到x = 10 , y = 4 。按Bernstein 条件，语句 的执行结果不受语句 的影响，故语句 执行后得到z = 5 。最后，语句 和 并发执行，这时得到了两种结果为：语句 先执行：x =10 , y =9 , z= 150 语句 先执行：x =10 , y =19 , z =15此外，还有第三种情况，语句 被推迟，直至语句 后再执行，于是依次执行以下三个语句：7 ：二z + X : z : = y + 1 ; y : Z十y ; 这时z 的值只可能是y 1=5 ，故y =ZY=5 + 4=9，而x = 10 。第三种情况为：x = 10 ，Y=9 , Z = 5 。4 有一阅览室，读者进入时必须先在一登记表上登记，该表为每一座位列出一个表目，包括座号、，读者离开时要注销登记信息；假设阅览室共有100 个座位。试用：l 信号量和P 、V 操作；2 管程，来实现用户进程的同步算法。答：1 使用信号量和P 、v 操作：var name ：array l 100of 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 : = l ; seatcount : = 100 ; cobegin process readeri ( var readename：string ) i=1 , 2 ) P ( seatcount ) ; P mutex ) ; for i : = 1 to 100 do i+if A i .namenull then A i .name：readername；reader get the seat number=i；/*AI.numberV ( mutex ) 进入阅览室，座位号i ，座下读书；P ( mutex ) ; Ainame：null ; V mutex ) ; V(seatcount);离开阅览室；coend2 使用管程操作：TYPE readbook=monitor VAR R: condition ; I,seatcount ：integer;name：array l:100 of string ; DEFINE rcadere, readerleave ; USE check , wait , signal , release ; Procedure readere ( readername ) begin check ( IM ) ; if seatcount100 wait ( R,IM ) seatcount : = seatcount + 1 ; for i=1 to 100 do i+if namei =null then namei:= readername; get the seat number = i ; release ( IM ) ; end procedure readerleave ( readername ) begin check ( IM ) ; seatcount-; for i = 1 to 1 00 do i+if namei readername then namei:null;release ( IM ) ; end begin seatcount : = 1OO ; name:null ; end cobegin process readeri ( i = 1 , 2 begin readere ( readername; read the book ; readerleave ( readername; leave the readroom;end coend.5. 在一个盒子里，混装了数量相等的黑白围棋子 现在用自动分拣系统把黑子、白子分开，设分拣系统有二个进程P1 和P2 ，其中P1 拣白子；P2 拣黑子。规定每个进程每次拣一子；当一个进程在拣时，不允许另一个进程去拣；当一个进程拣了一子时，必须让另一个进程去拣试写出两进程P1 和P2 能并发正确执行的程序。答1 ：实质上是两个进程的同步问题，设信号量s1 和s2 分别表示可拣白子和黑子，不失一般性，假设令先拣白子。var S1 , S2 : semaphore; S1 : = l; 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 . 答2 : TYPE pickup-chess = MONITOR VAR flag : boolean ; S-black , s-white : codition ;DEFINE pickup-black , pickup-white ;USE wait,signal , check , release ; procedure pickup-black ; begin check(IM ) ; if flag then wait(s-black,IM ) ;flag : true;pickup a black;signal(S-white,IM); release ( IM ) ; 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 0、S=0、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:=k2 ; 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:=k2 ； 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 C0 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 ：array0n-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 countn-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 04 of semaphore ; forki:=1 ; cobegin process Pi /* i = 0 , 1 , 2 , 3 */begin L1 : 思考：P(forki) ; / * i =4,P(fork 0) * / P(forki+1 mod 5) / * i =4Pfork 4* / 吃通心面；V (forki ; V (fork(i+1 mod 5 ) ; goto L1 ; end ; coend ; 16 Dijkstra 临界区软件算法描述如下：var flag ：array0n 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 turn1 do if flagturn=idle then turn:=i ; flagi:= ip_cs ; j:=0 ; while (j n ) & (j=1 or flagj in_cs ) do j:=j + 1 ; until jn : critical section ; flag i:=idle ; until false ; end . 试说明该算法满足临界区原如此。答：为方便描述，把Dijkstra 程序的语句进展编号：repeat flagi:=want_in ； while turni do if flagtrun=idle then turn:=i ； flagi: = in_cs ； j:= O ; while(j n ) & (j=1 or flagj in_cs do j:=j + 1 ; until jn ; critical section ; flagi :=idle ；( l 满足互斥条件当所有的巧都不在临界区中，满足flagjin_cs对于所有j , ji 条件时，Pi 才能进入它的临界区，而且进程Pi 不会改变除自己外的其他进程所对应的flagj的值。另外，进程Pi 总是先置自己的flagj为in_cs后，才去判别Pj进程的flagj的值是否等于in_cs 所以，此算法能保证n 个进程互斥地进入临界区。( 2 不会发生无休止等待进入临界区 由于任何一个进程Pi 在执行进入临界区代码时先执行语句 ，其相应的flagi的值不会是idle 。注意到flagiin_cs 并不意味着turn的值一定等于i 。我们来看以下情况，不失一般性，令turn 的初值为0，且P0不工作，所以，flagturn=flag0=idle。但是假设干个其他进程是可能同时交替执行的，假设让进程Pj(j=l , 2 , n-l交织执行语句 后这时flagj=want_in，再做语句 第一个while 语句，来查询flagturn的状态。显然，都满足turni ，所以，都可以执行语句 ，让自己的turn 为j 。但turn仅有一个值，该值为最后一个执行此赋值语句的进程号，设为k 、即turn=k (1kn -1 。接着，进程Pj(j=1,2,n-l ) 交织执行语句 ，于是最多同时可能有n-1 个进程处于in_cs 状态，但不要忘了仅有一个进程能成功执行语句 ，将加m 置为自己的值。 假设P1 , P2 ， Pm 是一个己将flagi 置为in_cs ( i =1,2,m ) ( m n -1的进程集合，并且已经假设当前turn=k ( 1km ) ，如此Pk 必将在有限时间首先进入临界区。因为集合中除了Pk 之外的所有其他进程终将从它们执行的语句 第二个while 循环语句退出，且这时的j 值必小于n ，故嵌until 起作用，返回到起始语句 重新执行，再次置flag i = want_in ，继续第二轮循环，这时的情况不同了，flagturn =flag k 必定idle 而为in_cs 。而进程Pk 发现最终除自身外的所有进程Pj 的flagjin_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 begin repeat P (S2 ) ; 取原料；做香烟；V(S) ; 吸香烟；untile false ;process 吸烟者3 begin repeat P (S3 ) ; 取原料；做香烟；V ( S ) ; 吸香烟；untile false ; coend .( 3 用管程。TYPE mskesmoke=moonitor VAR S, S1 ,S2 ,S3 : condition ; flag1 , flag2, flag3 : boolean DEFINE give , take1 , take2 , take3 ; USE check , wait , signal , release ; procedure give begin check ( IM ) ; 准备香烟原料；if 桌上有香烟原料then wait( S , IM ) ; 把准备的香烟原料放桌上；if fiag2 & flag3 then signal ( S1 ,IM;if flag1 & flag3 then signal ( S2 ,IM ) ; else signal (S3 , IM ) ; release ( IM ) ; end procedure take1 begin check(IM):if 桌上没有香烟原料then wait ( S1 ,IM; else 取原料；signal ( S , IM ) ; release ( IM ) ; end procedure take2 begin check ( IM ) : if 桌上没有香烟原料 then wait(S2,IM);else 取原料；signal ( S , IM ) ; release IM; end procedure take3 begin check ( IM ) : if 桌上没有香烟原料then wait(S3,IM);else 取原料 signal ( S ,IM ) ; release ( IM ) ; end begin flag1:=flag2:=flag3:=true;end.cobegin process 供应者 begin repeat Call makesmoke.give(); until false ; end process 吸烟者1 beginrepeat Call makesmoke.take1() ;做香烟，吸香烟；until false ; end process 吸烟者2 begin repeat Call makesmoke.take2() ; 做香烟，吸香烟；until false ; end process 吸烟者3 begin repeat Call makesmke.take3(); 做香烟，吸香烟；until false ; end coend . 18、 如如下图，四个进程Pi i=0 3 和四个信箱Mj (j=0 3 ) ，进程间借助相邻信箱传递消息，即Pi 每次从Mi中取一条消息，经加工后送入M(i + 1) mod4 ，其中M0 、M1 、M2 、M3 ;可存放3 、3 、2 、2 个消息。初始状态下，MO 装了三条消息，其余为空。试以P 、V 为操作工具，写出Pii=03的同步工作算法答：var mutexl , mutexZ , mutex3 ，mutex0 :semaphore; Mutex1nutex2:=mutex3:=mutex0:=1;Empty0,empty1,empty2, empty3; semaphore;empty:=0 ; empty1:=3 ; empty:=2:=empty3:=2;full0 , full1 , full2 , full3:semphore ; full0:=3;full1:=full2:=full3:=0;in0,in1,in2,in3,out0 ,out2,out3,;intger;in0:=in1:in2:in3:=out0:=out1:=out2:=out3:=0;cobegin process P0 begin repeat P(full0); P(mutex0); 从M0out0取一条消息；out0:=(out0+1) mod 3 ; V(mutex0); V(empty0) ; 加工消息；P(empty1) ; P(mutex1) ; 消息已M1in1;In1:=(in1+1) mod 3;V(mutex1) ; V(full1 ) ; untile false ; end process P1 begin repeat P ( full1 ) ; P ( mutex1 ) ; 从M1out1取一条消息；Out1:=(out1+1) mod 3 ;V(mutex1); V(empty1); 加工消息;P(empty2); P(mutex2 ) ; 消息己M2in2;In2:=(in2+1) mod 2;V(mutex2 ) ; v ( full2 ) ; untile false ; end process P2begin repeat P(full2) ; P(mutex2 ) ; 从M2out2取一条消息；out2:=(out2 + l ) mod 2;V(mutex2) ; V(empty2) ; 加工消息；P(empty3) ; P(mutex3) ; 消息己M3in3;in3:=(in3+1) mod 2 ;V(mutex3) ; V(full3) ; untile false ; endprocess P3 begin repeat P(full3) ; P(mutex3) ; 从M3out3 取一条消息;out3:=(out3+1)mod 2;V (mutex3) ; V (empty3) ; 加工消息；P ( empty0 ) ; P ( mutex0 ) ; 消息己MOin0;In0:=(in0+1) mod 3 ;V(mutex0) ; V(full0) ; untile false ; end coend 19、有三组进程Pi 、Qj、Rk ，其中Pi 、Qj构成一对生产者和消费者，共享一个由M1个缓区构成的循环缓冲池buf1 。Qj、Rk凡构成另一对生产者和消费者，共享一个由M2 个缓冲区构成的循环缓冲池buf2 。如果Pi每次生产一个产品投入buf1,Qj每次从中取两个产品组装成一个后并投入buf2，Rk每次从中取三个产品包装出厂. 试用信号量和P 、V操作写出它们同步工作的程序。答：var mutex1 , mutex2 , mutex3 : semaphore; empty1 , empty2 , full1 , full2 ; semaphore ; in1 , in2 , out1 , out2 : integer ; counter1 , counter2:integer ; buffer1:array0M1-1 of item ; buffer2:array0M2-1of item ;empty1:=M1 ; empty:=M2; in1 : = in2 :=out1:=out2:=0 ; counter1:=counter2:=0 ;fun1:=full2:mutex1:=mutex2:=mutex3:=1;cobegin process Pi begin L1: P(empty1) ; P(mutex1 ) ; put an item into buffer in1 ; in1:=(in1+1) mod M1 ; counter+;if counter1 = 2 then counter1:=0;V(full1); V(mutex) ; goto L1; end process Qjbegin L2:P ( full2) ; P ( mutex1 ) ; take an item from buffer1out1;out1:=(out1+1) mod M1; take an item from buffer1out1 ;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