操作系統(tǒng)習題答案第.doc

CH3 應用題參考答案1、 有三個并發(fā)進程：R 負責從輸入設備讀入信息塊，M 負責對信息塊加工處理；P 負責打印輸出信息塊。今提供；l ）一個緩沖區(qū)，可放置K 個信息塊；2 ）二個緩沖區(qū)，每個可放置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 有兩個優(yōu)先級相同的進程P1和P2，各自執(zhí)行的操作如下，信號量S1和S2初值均為0。試問Pl 、P2 并發(fā)執(zhí)行后，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 答：現(xiàn)對進程語句進行編號，以方便描述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 、 、 和 是不相交語句，可以任何次序交錯執(zhí)行，而結果是唯一的。接著無論系統(tǒng)如何調度進程并發(fā)執(zhí)行，當執(zhí)行到語句 時，可以得到x = 10 , y = 4 。按Bernstein 條件，語句 的執(zhí)行結果不受語句 的影響，故語句 執(zhí)行后得到z = 5 。最后，語句 和 并發(fā)執(zhí)行，這時得到了兩種結果為：語句 先執(zhí)行：x =10 , y =9 , z= 150 語句 先執(zhí)行：x =10 , y =19 , z =15此外，還有第三種情況，語句 被推遲，直至語句 后再執(zhí)行，于是依次執(zhí)行以下三個語句：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 ）管程，來實現(xiàn)用戶進程的同步算法。答：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 rcadercome, readerleave ; USE check , wait , signal , release ; Procedure readercome ( 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 readercome ( readername）; read the book ; readerleave ( readername）; leave the readroom;end coend.5. 在一個盒子里，混裝了數(shù)量相等的黑白圍棋子 現(xiàn)在用自動分揀系統(tǒng)把黑子、白子分開，設分揀系統(tǒng)有二個進程P1 和P2 ，其中P1 揀白子；P2 揀黑子。規(guī)定每個進程每次揀一子；當一個進程在揀時，不允許另一個進程去揀；當一個進程揀了一子時，必須讓另一個進程去揀試寫出兩進程P1 和P2 能并發(fā)正確執(zhí)行的程序。答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 ）兩個并發(fā)進程并發(fā)執(zhí)行，其中，A 、B 、C 、D 、E 是原語，試給出可能的并發(fā)執(zhí)行路徑。Process P Process Q begin begin A ; D ; B ; E ; C ; end : end ; ( 2 ）兩個并發(fā)進程P1 和P2 并發(fā)執(zhí)行，它們的程序分別如下：P 1 P2 repeat repeat k:=k2 ; print k ; k:=k+1 ; k:=0 ; until false ; until false ; 若令k 的初值為5 ，讓P1 先執(zhí)行兩個循環(huán)，然后，P1 和P2 又并發(fā)執(zhí)行了一個循環(huán)，寫出可能的打印值，指出與時間有關的錯誤。答：( 1 ）共有10 種交錯執(zhí)行的路徑：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 執(zhí)行兩個循環(huán)后，K = 23 。2 ）語句并發(fā)執(zhí)行有以下情況： 、 、 、 ，這時的打印值為：47 、 、 、 ，這時的打印值為：23 、 、 、 ，這時的打印值為：46 、 、 、 ，這時的打印值為：46 、 、 、 ，這時的打印值為：23 、 、 、 ，這時的打印值為：23 由于進程P1和P2 并發(fā)執(zhí)行，共享了變量K ，故產生了結果不唯一。11 證明信號量與管程的功能是等價的：( l ）用信號量實現(xiàn)管程；( 2 ）用管程實現(xiàn)信號量。答：( 1 ）用信號量實現(xiàn)管程；Hoare 是用信號量實現(xiàn)管程的一個例子，詳見課文內容。下面介紹另一種簡單方法：每一個管程都對應一個mutex ，其初值為1 ，用來控制進程互斥調用管程。再設一個初值為0 的信號量，用來阻塞等待資源的進程。相應的用信號量實現(xiàn)的管程庫過程為：Var mutex,c:semaphore ; mutex:=1 ; c:=0 ; void enter-monitor ( ) /*進入管程代碼，保證互斥P ( mutex ) ; void leave-monitor-normally ( )/*不發(fā)信號退出管程 V ( mutex ) ; void leave-with-sigal(c) /*在條件c 上發(fā)信號并退出管程，釋放一個等待c 條件的進程。注意這時沒有開放管程，因為剛剛被釋放的進程己在管程中。V ( c ) ; void wait(c) /*等待條件c ，開放管程 V ( mutex ) ; P (c) ; ( 2 ）用管程實現(xiàn)信號量。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 ）用消息傳遞實現(xiàn)管程；( 2 ）用管程實現(xiàn)消息傳遞。答：( 1 ）用消息傳遞實現(xiàn)管程；用消息傳遞可以實現(xiàn)信號量（見13 ( 2 ) ) ，用信號量可以實現(xiàn)管程（見11 (1 ) ) ，那么，把兩種方法結合起來，就可以用用消息傳遞實現(xiàn)管程。( 2 ）用管程實現(xiàn)消息傳遞。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 ）用信號量實現(xiàn)消息傳遞；( 2 ）用消息傳遞實現(xiàn)信號量。答：( l ）用信號量實現(xiàn)消息傳遞；1 ）把消息隊列組織成一個共享隊列，用一個互斥信號量管理對該隊列的入隊操作和出隊操作.2 ）發(fā)送消息是一個入隊操作，當隊列存儲區(qū)滿時，設計一個同步信號量阻塞send 操作。3 ）接收消息是一個出隊操作，當隊列存儲區(qū)空時，設計另一個同步信號量阻塞receive 操作。( 2 ）用消息傳遞實現(xiàn)信號量。l ）為每一個信號量建立一個同步管理進程，它包含了一個計數(shù)器，記錄信號量值；還為此信號量設立一個等待進程隊列2 ）應用進程執(zhí)行P 或V操作時，將會調用相應P 、V庫過程。庫過程的功能是：把應用進程封鎖起來，所執(zhí)行的P 、V 操作的信息組織成消息，執(zhí)行send 發(fā)送給與信號量對應的同步管理進程，之后，再執(zhí)行receive 操作以接收同步管理進程的應答。3 ）當消息到達后，同步管理進程計數(shù)并查看信號量狀態(tài)。如果信號量的值為負的話，執(zhí)行P 操作的應用進程被阻塞，掛到等待進程隊列，所以，不再要送回答消息。此后，當V 操作執(zhí)行完后，同步管理進程將從信號量相應隊列中選取一個進程喚醒，并回送一個應答消息。正常情況下，同步管理進程回送一個空應答消息，然后，解鎖執(zhí)行P 、V 操作的應用程序。14 使用（1）消息傳遞，( 2 ）管程，實現(xiàn)生產者和消費者問題。答：( 1 ）見課文ch3 3.5.4 節(jié)。（2 ）見課文Ch3 3.4.3 節(jié)。15 試利用記錄型信號量和P 、V 操作寫出一個不會出現(xiàn)死鎖的五個哲學家進餐問題的算法。答：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 =4P（fork 4）* / 吃通心面；V (forki ; V (fork(i+1 mod 5 ) ; goto L1 ; end ; coend ; 16 Dijkstra 臨界區(qū)軟件算法描述如下：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 . 試說明該算法滿足臨界區(qū)原則。答：為方便描述，把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 ）滿足互斥條件當所有的巧都不在臨界區(qū)中，滿足flagjin_cs（對于所有j , ji ）條件時，Pi 才能進入它的臨界區(qū)，而且進程Pi 不會改變除自己外的其他進程所對應的flagj的值。另外，進程Pi 總是先置自己的flagj為in_cs后，才去判別Pj進程的flagj的值是否等于in_cs 所以，此算法能保證n 個進程互斥地進入臨界區(qū)。( 2 ）不會發(fā)生無休止等待進入臨界區(qū) 由于任何一個進程Pi 在執(zhí)行進入臨界區(qū)代碼時先執(zhí)行語句 ，其相應的flagi的值不會是idle 。注意到flagiin_cs 并不意味著turn的值一定等于i 。我們來看以下情況，不失一般性，令turn 的初值為0，且P0不工作，所以，flagturn=flag0=idle。但是若干個其他進程是可能同時交替執(zhí)行的，假設讓進程Pj(j=l , 2 , n-l）交錯執(zhí)行語句 后（這時flagj=want_in），再做語句 （第一個while 語句），來查詢flagturn的狀態(tài)。顯然，都滿足turni ，所以，都可以執(zhí)行語句 ，讓自己的turn 為j 。但turn僅有一個值，該值為最后一個執(zhí)行此賦值語句的進程號，設為k 、即turn=k (1kn -1 ）。接著，進程Pj(j=1,2,n-l ) 交錯執(zhí)行語句 ，于是最多同時可能有n-1 個進程處于in_cs 狀態(tài)，但不要忘了僅有一個進程能成功執(zhí)行語句 ，將加m 置為自己的值。 假設P1 , P2 ， Pm 是一個己將flagi 置為in_cs ( i =1,2,m ) ( m n -1）的進程集合，并且已經假設當前turn=k ( 1km ) ，則Pk 必將在有限時間內首先進入臨界區(qū)。因為集合中除了Pk 之外的所有其他進程終將從它們執(zhí)行的語句 （第二個while 循環(huán)語句）退出，且這時的j 值必小于n ，故內嵌until 起作用，返回到起始語句 重新執(zhí)行，再次置flag i = want_in ，繼續(xù)第二輪循環(huán)，這時的情況不同了，flagturn =flag k 必定idle （而為in_cs ）。而進程Pk 發(fā)現(xiàn)最終除自身外的所有進程Pj 的flagjin_cs ，并據(jù)此可進入其臨界區(qū)。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 個消息。初始狀態(tài)下，MO 裝了三條消息，其余為空。試以P 、V 為操作工具，寫出Pi（i=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) ; 從M3o