操作系統(tǒng)習(xí)習(xí)題答案第 (3)

1、CH3 應(yīng)用題參考答案1、 有三個(gè)并發(fā)進(jìn)程：R 負(fù)責(zé)從輸入設(shè)備讀入信息塊，M 負(fù)責(zé)對(duì)信息塊加工處理；P 負(fù)責(zé)打印輸出信息塊。今提供；l ）一個(gè)緩沖區(qū)，可放置K 個(gè)信息塊；2 ）二個(gè)緩沖區(qū)，每個(gè)可放置K 個(gè)信息塊；試用信號(hào)量和P 、V 操作寫出三個(gè)進(jìn)程正確工作的流程。答：1 ) var B : array 0 , k-1 of item ; sread : semaPhore : = k ; smanage : semaPhore : = 0 ; swrite : semaphore : = 0 ; rptr : integer : = O ; mptr : integer : = O ; wp

2、tr ：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 mess

3、age 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

4、：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

5、) 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 設(shè)有n 個(gè)進(jìn)程共享一個(gè)互斥段，如果：( 1 ）每次只允許一個(gè)進(jìn)程進(jìn)入互斥段；( 2 ）每次最多允許m 個(gè)進(jìn)程（m 簇n ）同時(shí)進(jìn)入互斥段。試問(wèn)：所采用的信號(hào)量初值是否相同信號(hào)量值的變化范圍如何？答：所采用的互斥信號(hào)量初值不同。1 ）互斥信號(hào)量初值為1 ，變化范圍為

6、-nl , 1 。當(dāng)沒(méi)有進(jìn)程進(jìn)入互斥段時(shí)，信號(hào)量值為1 ；當(dāng)有1 個(gè)進(jìn)程進(jìn)入互斥段但沒(méi)有進(jìn)程等待進(jìn)入互斥段時(shí)，信號(hào)量值為O ；當(dāng)有1 個(gè)進(jìn)程進(jìn)入互斥段且有一個(gè)進(jìn)程等待進(jìn)入互斥段時(shí)，信號(hào)量值為-1 ；最多可能有n -1 個(gè)進(jìn)程等待進(jìn)入互斥段，故此時(shí)信號(hào)量的值應(yīng)為-（n - 1 ）也就是-n+1 。2 ）互斥信號(hào)量初值為m ，變化范圍為-nm , m 。當(dāng)沒(méi)有進(jìn)程進(jìn)入互斥段時(shí)，信號(hào)量值為m ；當(dāng)有1 個(gè)進(jìn)程進(jìn)入互斥段但沒(méi)有進(jìn)程等待進(jìn)入互斥段時(shí)，信號(hào)量值為m - 1 ：當(dāng)有m 個(gè)進(jìn)程進(jìn)入互斥段且沒(méi)有一個(gè)進(jìn)程等待進(jìn)入互斥段時(shí)，信號(hào)量值為0 ：當(dāng)有m 個(gè)進(jìn)程進(jìn)入互斥段且有一個(gè)進(jìn)程等待進(jìn)入互斥段時(shí)，信號(hào)量

7、值為一l ；最多可能有n - m 個(gè)進(jìn)程等待進(jìn)入互斥段，故此時(shí)信號(hào)量的值應(yīng)為-(n-m)也就是-n+m.3 有兩個(gè)優(yōu)先級(jí)相同的進(jìn)程P1和P2，各自執(zhí)行的操作如下，信號(hào)量S1和S2初值均為0。試問(wèn)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)對(duì)進(jìn)程語(yǔ)句進(jìn)行編號(hào)，以方便描述P1 : P2 : begin begin y : = 1 ； x :=1 ; y :=y+3 ；

8、x ：x+5 ; V(S1); P(S1); Z:Y+1 ； x ：XY ;P(s2); V(S2);Y:=z+y; z：=Z+X； End end 、 、 和 是不相交語(yǔ)句，可以任何次序交錯(cuò)執(zhí)行，而結(jié)果是唯一的。接著無(wú)論系統(tǒng)如何調(diào)度進(jìn)程并發(fā)執(zhí)行，當(dāng)執(zhí)行到語(yǔ)句 時(shí)，可以得到x = 10 , y = 4 。按Bernstein 條件，語(yǔ)句 的執(zhí)行結(jié)果不受語(yǔ)句 的影響，故語(yǔ)句 執(zhí)行后得到z = 5 。最后，語(yǔ)句 和 并發(fā)執(zhí)行，這時(shí)得到了兩種結(jié)果為：語(yǔ)句 先執(zhí)行：x =10 , y =9 , z= 150 語(yǔ)句 先執(zhí)行：x =10 , y =19 , z =15此外，還有第三種情況，語(yǔ)句 被推遲，直

9、至語(yǔ)句 后再執(zhí)行，于是依次執(zhí)行以下三個(gè)語(yǔ)句：7 ：二z + X : z : = y + 1 ; y : Z十y ; 這時(shí)z 的值只可能是y 1=5 ，故y =ZY=5 + 4=9，而x = 10 。第三種情況為：x = 10 ，Y=9 , Z = 5 。4 有一閱覽室，讀者進(jìn)入時(shí)必須先在一張登記表上登記，該表為每一座位列出一個(gè)表目，包括座號(hào)、姓名，讀者離開(kāi)時(shí)要注銷登記信息；假如閱覽室共有100 個(gè)座位。試用：l ）信號(hào)量和P 、V 操作；2 ）管程，來(lái)實(shí)現(xiàn)用戶進(jìn)程的同步算法。答：1 ）使用信號(hào)量和P 、v 操作：var name ：array l 100of A ; A = record nu

10、mber ：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 t

11、hen A i .name：readername；reader get the seat number=i；/*AI.numberV ( mutex ) 進(jìn)入閱覽室，座位號(hào)i ，座下讀書；P ( mutex ) ; Ainame：null ; V （mutex ) ; V(seatcount);離開(kāi)閱覽室；coend2 ）使用管程操作：TYPE readbook=monitor VAR R: condition ; I,seatcount ：integer;name：array l:100 of string ; DEFINE rcadercome, readerleave ; USE che

12、ck , 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 ch

13、eck ( 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. 在一個(gè)盒子里，混

14、裝了數(shù)量相等的黑白圍棋子· 現(xiàn)在用自動(dòng)分揀系統(tǒng)把黑子、白子分開(kāi)，設(shè)分揀系統(tǒng)有二個(gè)進(jìn)程P1 和P2 ，其中P1 揀白子；P2 揀黑子。規(guī)定每個(gè)進(jìn)程每次揀一子；當(dāng)一個(gè)進(jìn)程在揀時(shí)，不允許另一個(gè)進(jìn)程去揀；當(dāng)一個(gè)進(jìn)程揀了一子時(shí)，必須讓另一個(gè)進(jìn)程去揀試寫出兩進(jìn)程P1 和P2 能并發(fā)正確執(zhí)行的程序。答1 ：實(shí)質(zhì)上是兩個(gè)進(jìn)程的同步問(wèn)題，設(shè)信號(hào)量s1 和s2 分別表示可揀白子和黑子，不失一般性，若令先揀白子。var S1 , S2 : semaphore; S1 : = l; S2 ：=0;cobegin process P1 begin repeat P( S1 ) ; 揀白子V ( S2 ) ;

15、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

16、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

17、 ( ) ; process -W ( ) ; coend process-B ( ) begin ( ) ;other ; end process-W ( ) begin ( ) ;other ; end 6 管程的同步機(jī)制使用條件變量和wait 及signal ，嘗試為管程設(shè)計(jì)一種僅僅使用一個(gè)原語(yǔ)操作的同步機(jī)制。答：可以采用形如waituntil 條件表達(dá)式的同步原語(yǔ)。如waituntil ( numbersum + number < K ) 表示進(jìn)程由于條件不滿足而應(yīng)等待，當(dāng)進(jìn)程號(hào)累加和小于K 時(shí)，系統(tǒng)應(yīng)喚醒該進(jìn)程工作7 設(shè)公共汽車上，司機(jī)和售票員的活動(dòng)分別如下：司機(jī)的活動(dòng)：?jiǎn)?dòng)車

18、輛：正常行車；到站停車。售票員的活動(dòng)：關(guān)車門；售票；開(kāi)車門。在汽車不斷地到站、停車、行駛過(guò)程中，這兩個(gè)活動(dòng)有什么同步關(guān)系用信號(hào)量和P 、V 操作實(shí)現(xiàn)它們的同步。答：在汽車行駛過(guò)程中，司機(jī)活動(dòng)與售票員活動(dòng)之間的同步關(guān)系為：售票員關(guān)車門后，向司機(jī)發(fā)開(kāi)車信號(hào)，司機(jī)接到開(kāi)車信號(hào)后啟動(dòng)車輛，在汽車正常行駛過(guò)程中售票員售票，到站時(shí)司機(jī)停車，售票員在車停后開(kāi)門讓乘客上下車。因此，司機(jī)啟動(dòng)車輛的動(dòng)作必須與售票員關(guān)車門的動(dòng)作取得同步；售票員開(kāi)車門的動(dòng)作也必須與司機(jī)停車取得同步。應(yīng)設(shè)置兩個(gè)信號(hào)量：S1 、S2 ;S1 表示是否允許司機(jī)啟動(dòng)汽車（其初值為0 ) ;S2 表示是否允許售票員開(kāi)門（其初值為0 ）。用P

19、、v 原語(yǔ)描述如下：var S1 , S2 : semaphore ; S1=0；S2=0；cobegin driver ( ) ; busman ( ) ; coend driver ( ) begin while ( 1 ) P ( S1 ) 啟動(dòng)車輛；正常行車；到站停車；V ( S2 ) ; end busman ( ) begin while ( 1 ) 關(guān)車門； V ( 51 ) 售票;P ( S2 ) 開(kāi)車門；上下乘客； end 8、一個(gè)快餐廳有4 類職員：( l ）領(lǐng)班：接受顧客點(diǎn)菜；( 2 ）廚師：準(zhǔn)備顧客的飯菜；( 3 ) 包工：將做好的飯菜打包；( 4 ）出納員：收款并提交

20、食品。每個(gè)職員可被看作一個(gè)進(jìn)程，試用一種同步機(jī)制寫出能讓四類職員正確并發(fā)運(yùn)行的程序。答：典型的進(jìn)程同步問(wèn)題，可設(shè)四個(gè)信號(hào)量51 、S2 、S3 和S4 來(lái)協(xié)調(diào)進(jìn)程工作。var S1 , S2 ,S3 , S4 : semaphore ; S1 : = 1 ;S2 ：=S3 : = S4 : = 0 ; cobegin process P1 begin repeat 有顧客到來(lái)； P ( S1 )； 接受顧客點(diǎn)菜； V ( 52 )； untile false； end process P2 begin repeat P (S2 ) ; 準(zhǔn)備顧客的飯菜；v ( S3 ) ; untile fal

21、se ; 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、在信號(hào)量S上作P 、v 操作時(shí)，S的值發(fā)生變化，當(dāng)S> 0、S=0、S< 0 時(shí)，它們的的物理意義是什么？答：S 的值表示它代表的物理資源的使用狀態(tài)：S > 0 表示還有共享資源可供使用。S 閱表示共享資源正被進(jìn)程使用但沒(méi)有進(jìn)程等待使用資源。S <

22、; 0 表示資源已被分配完，還有進(jìn)程等待使用資源。10 ( 1 ）兩個(gè)并發(fā)進(jìn)程并發(fā)執(zhí)行，其中，A 、B 、C 、D 、E 是原語(yǔ)，試給出可能的并發(fā)執(zhí)行路徑。Process P Process Q begin begin A ; D ; B ; E ; C ; end : end ; ( 2 ）兩個(gè)并發(fā)進(jìn)程P1 和P2 并發(fā)執(zhí)行，它們的程序分別如下：P 1 P2 repeat repeat k:=k×2 ; print k ; k:=k+1 ; k:=0 ; until false ; until false ; 若令k 的初值為5 ，讓P1 先執(zhí)行兩個(gè)循環(huán)，然后，P1 和P2 又并發(fā)

23、執(zhí)行了一個(gè)循環(huán)，寫出可能的打印值，指出與時(shí)間有關(guān)的錯(cuò)誤。答：( 1 ）共有10 種交錯(cuò)執(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 ）把語(yǔ)句編號(hào)，以便于描述：P1 P2 repeat repeat k:=k×2 ； printk ； k:=k+l ； k:=0 ； until false ; until fa

24、lse ; l ) K 的初值為5 ，故P1 執(zhí)行兩個(gè)循環(huán)后，K = 23 。2 ）語(yǔ)句并發(fā)執(zhí)行有以下情況： 、 、 、 ，這時(shí)的打印值為：47 、 、 、 ，這時(shí)的打印值為：23 、 、 、 ，這時(shí)的打印值為：46 、 、 、 ，這時(shí)的打印值為：46 、 、 、 ，這時(shí)的打印值為：23 、 、 、 ，這時(shí)的打印值為：23 由于進(jìn)程P1和P2 并發(fā)執(zhí)行，共享了變量K ，故產(chǎn)生了結(jié)果不唯一。11 證明信號(hào)量與管程的功能是等價(jià)的：( l ）用信號(hào)量實(shí)現(xiàn)管程；( 2 ）用管程實(shí)現(xiàn)信號(hào)量。答：( 1 ）用信號(hào)量實(shí)現(xiàn)管程；Hoare 是用信號(hào)量實(shí)現(xiàn)管程的一個(gè)例子，詳見(jiàn)課文內(nèi)容。下面介紹另一種簡(jiǎn)單方法：每

25、一個(gè)管程都對(duì)應(yīng)一個(gè)mutex ，其初值為1 ，用來(lái)控制進(jìn)程互斥調(diào)用管程。再設(shè)一個(gè)初值為0 的信號(hào)量，用來(lái)阻塞等待資源的進(jìn)程。相應(yīng)的用信號(hào)量實(shí)現(xiàn)的管程庫(kù)過(guò)程為：Var mutex,c:semaphore ; mutex:=1 ; c:=0 ; void enter-monitor ( ) /*進(jìn)入管程代碼，保證互斥P ( mutex ) ; void leave-monitor-normally ( )/*不發(fā)信號(hào)退出管程 V ( mutex ) ; void leave-with-sigal(c) /*在條件c 上發(fā)信號(hào)并退出管程，釋放一個(gè)等待c 條件的進(jìn)程。注意這時(shí)沒(méi)有開(kāi)放管程，因?yàn)閯倓偙会?/p>

26、放的進(jìn)程己在管程中。V ( c ) ; void wait(c) /*等待條件c ，開(kāi)放管程 V ( mutex ) ; P (c) ; ( 2 ）用管程實(shí)現(xiàn)信號(hào)量。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

27、begin check ( IM ) : C : = C + 1 ; if C0 then signal ( S,IM ) ; release ( IM ) ; end begin C:=初值;End.12 證明消息傳遞與管程的功能是等價(jià)的：( 1 ）用消息傳遞實(shí)現(xiàn)管程；( 2 ）用管程實(shí)現(xiàn)消息傳遞。答：( 1 ）用消息傳遞實(shí)現(xiàn)管程；用消息傳遞可以實(shí)現(xiàn)信號(hào)量（見(jiàn)13 ( 2 ) ) ，用信號(hào)量可以實(shí)現(xiàn)管程（見(jiàn)11 (1 ) ) ，那么，把兩種方法結(jié)合起來(lái)，就可以用用消息傳遞實(shí)現(xiàn)管程。( 2 ）用管程實(shí)現(xiàn)消息傳遞。TYPE mailbox=monitor VAR r , k , count:in

28、teger ; 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 ) ; releas

29、e ( 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 證明信號(hào)量與消息傳遞是等價(jià)的：( 1 ）用信號(hào)量實(shí)現(xiàn)消息傳遞；( 2 ）用消息傳遞實(shí)現(xiàn)信號(hào)量。答：( l ）用信號(hào)量實(shí)現(xiàn)消息傳遞；1

30、）把消息隊(duì)列組織成一個(gè)共享隊(duì)列，用一個(gè)互斥信號(hào)量管理對(duì)該隊(duì)列的入隊(duì)操作和出隊(duì)操作.2 ）發(fā)送消息是一個(gè)入隊(duì)操作，當(dāng)隊(duì)列存儲(chǔ)區(qū)滿時(shí)，設(shè)計(jì)一個(gè)同步信號(hào)量阻塞send 操作。3 ）接收消息是一個(gè)出隊(duì)操作，當(dāng)隊(duì)列存儲(chǔ)區(qū)空時(shí)，設(shè)計(jì)另一個(gè)同步信號(hào)量阻塞receive 操作。( 2 ）用消息傳遞實(shí)現(xiàn)信號(hào)量。l ）為每一個(gè)信號(hào)量建立一個(gè)同步管理進(jìn)程，它包含了一個(gè)計(jì)數(shù)器，記錄信號(hào)量值；還為此信號(hào)量設(shè)立一個(gè)等待進(jìn)程隊(duì)列2 ）應(yīng)用進(jìn)程執(zhí)行P 或V操作時(shí)，將會(huì)調(diào)用相應(yīng)P 、V庫(kù)過(guò)程。庫(kù)過(guò)程的功能是：把應(yīng)用進(jìn)程封鎖起來(lái)，所執(zhí)行的P 、V 操作的信息組織成消息，執(zhí)行send 發(fā)送給與信號(hào)量對(duì)應(yīng)的同步管理進(jìn)程，之后，再執(zhí)行

31、receive 操作以接收同步管理進(jìn)程的應(yīng)答。3 ）當(dāng)消息到達(dá)后，同步管理進(jìn)程計(jì)數(shù)并查看信號(hào)量狀態(tài)。如果信號(hào)量的值為負(fù)的話，執(zhí)行P 操作的應(yīng)用進(jìn)程被阻塞，掛到等待進(jìn)程隊(duì)列，所以，不再要送回答消息。此后，當(dāng)V 操作執(zhí)行完后，同步管理進(jìn)程將從信號(hào)量相應(yīng)隊(duì)列中選取一個(gè)進(jìn)程喚醒，并回送一個(gè)應(yīng)答消息。正常情況下，同步管理進(jìn)程回送一個(gè)空應(yīng)答消息，然后，解鎖執(zhí)行P 、V 操作的應(yīng)用程序。14 使用（1）消息傳遞，( 2 ）管程，實(shí)現(xiàn)生產(chǎn)者和消費(fèi)者問(wèn)題。答：( 1 ）見(jiàn)課文ch3 3.5.4 節(jié)。（2 ）見(jiàn)課文Ch3 節(jié)。15 試?yán)糜涗浶托盘?hào)量和P 、V 操作寫出一個(gè)不會(huì)出現(xiàn)死鎖的五個(gè)哲學(xué)家進(jìn)餐問(wèn)題的算法。

32、答：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_

33、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

34、; until false ; end . 試說(shuō)明該算法滿足臨界區(qū)原則。答：為方便描述，把Dijkstra 程序的語(yǔ)句進(jìn)行編號(hào)：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 ）滿足互斥條件當(dāng)所有的巧都不在臨界區(qū)中，滿足flagjin_cs

35、（對(duì)于所有j , ji ）條件時(shí)，Pi 才能進(jìn)入它的臨界區(qū)，而且進(jìn)程Pi 不會(huì)改變除自己外的其他進(jìn)程所對(duì)應(yīng)的flagj的值。另外，進(jìn)程Pi 總是先置自己的flagj為in_cs后，才去判別Pj進(jìn)程的flagj的值是否等于in_cs 所以，此算法能保證n 個(gè)進(jìn)程互斥地進(jìn)入臨界區(qū)。( 2 ）不會(huì)發(fā)生無(wú)休止等待進(jìn)入臨界區(qū) 由于任何一個(gè)進(jìn)程Pi 在執(zhí)行進(jìn)入臨界區(qū)代碼時(shí)先執(zhí)行語(yǔ)句 ，其相應(yīng)的flagi的值不會(huì)是idle 。注意到flagiin_cs 并不意味著turn的值一定等于i 。我們來(lái)看以下情況，不失一般性，令turn 的初值為0，且P0不工作，所以，flagturn=flag0=idle。但是若

36、干個(gè)其他進(jìn)程是可能同時(shí)交替執(zhí)行的，假設(shè)讓進(jìn)程Pj(j=l , 2 , n-l）交錯(cuò)執(zhí)行語(yǔ)句 后（這時(shí)flagj=want_in），再做語(yǔ)句 （第一個(gè)while 語(yǔ)句），來(lái)查詢flagturn的狀態(tài)。顯然，都滿足turni ，所以，都可以執(zhí)行語(yǔ)句 ，讓自己的turn 為j 。但turn僅有一個(gè)值，該值為最后一個(gè)執(zhí)行此賦值語(yǔ)句的進(jìn)程號(hào)，設(shè)為k 、即turn=k (1kn -1 ）。接著，進(jìn)程Pj(j=1,2,n-l ) 交錯(cuò)執(zhí)行語(yǔ)句 ，于是最多同時(shí)可能有n-1 個(gè)進(jìn)程處于in_cs 狀態(tài)，但不要忘了僅有一個(gè)進(jìn)程能成功執(zhí)行語(yǔ)句 ，將加m 置為自己的值。 假設(shè)P1 , P2 ， Pm 是一個(gè)己將fla

37、gi 置為in_cs ( i =1,2,m ) ( m n -1）的進(jìn)程集合，并且已經(jīng)假設(shè)當(dāng)前turn=k ( 1km ) ，則Pk 必將在有限時(shí)間內(nèi)首先進(jìn)入臨界區(qū)。因?yàn)榧现谐薖k 之外的所有其他進(jìn)程終將從它們執(zhí)行的語(yǔ)句 （第二個(gè)while 循環(huán)語(yǔ)句）退出，且這時(shí)的j 值必小于n ，故內(nèi)嵌until 起作用，返回到起始語(yǔ)句 重新執(zhí)行，再次置flag i = want_in ，繼續(xù)第二輪循環(huán)，這時(shí)的情況不同了，flagturn =flag k 必定idle （而為in_cs ）。而進(jìn)程Pk 發(fā)現(xiàn)最終除自身外的所有進(jìn)程Pj 的flagjin_cs ，并據(jù)此可進(jìn)入其臨界區(qū)。17 另一個(gè)經(jīng)典同步問(wèn)

38、題：吸煙者問(wèn)題(patil , 1971 ）。三個(gè)吸煙者在一個(gè)房間內(nèi)，還有一個(gè)香煙供應(yīng)者。為了制造并抽掉香煙，每個(gè)吸煙者需要三樣?xùn)|西：煙草、紙和火柴，供應(yīng)者有豐富貨物提供。三個(gè)吸煙者中，第一個(gè)有自己的煙草，第二個(gè)有自己的紙和第三個(gè)有自己的火柴。供應(yīng)者隨機(jī)地將兩樣?xùn)|西放在桌子上，允許一個(gè)吸煙者進(jìn)行對(duì)健康不利的吸煙。當(dāng)吸煙者完成吸煙后喚醒供應(yīng)者，供應(yīng)者再把兩樣?xùn)|西放在桌子上，喚醒另一個(gè)吸煙者。試采用：( 1 ）信號(hào)量和P 、v 操作，( 2 ）管程編寫他們同步工作的程序。答：( 1 ）用信號(hào)量和P 、v 操作。vars , S1 ,S2 , S3 ; semaphore ; S:=1 ; S1:=

39、S2:=S3:=0 ; fiag1 , flag2 , fiag3 : Boolean ; fiag1:=flag2:=flag3:=true;cobegin process 供應(yīng)者 begin repeat P(S) ; 取兩樣香煙原料放桌上，由flagi標(biāo)記； / * nago1 、nage2 、nage3 代表煙草、紙、火柴 if flag2 & flag3 then V(S1) ; / 供紙和火柴 else if flag1 & fiag3 then V(S2 ) ; / 供煙草和火柴 else V(S3) ; / 供煙草和紙untile false ; end pro

40、cess 吸煙者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 :

41、 boolean DEFINE give , take1 , take2 , take3 ; USE check , wait , signal , release ; procedure give begin check ( IM ) ; 準(zhǔn)備香煙原料；if 桌上有香煙原料then wait( S , IM ) ; 把準(zhǔn)備的香煙原料放桌上；if fiag2 & flag3 then signal ( S1 ,IM）;if flag1 & flag3 then signal ( S2 ,IM ) ; else signal (S3 , IM ) ; release ( IM )

42、 ; end procedure take1 begin check(IM):if 桌上沒(méi)有香煙原料then wait ( S1 ,IM）; else 取原料；signal ( S , IM ) ; release ( IM ) ; end procedure take2 begin check ( IM ) : if 桌上沒(méi)有香煙原料 then wait(S2,IM);else 取原料；signal ( S , IM ) ; release （IM）; end procedure take3 begin check ( IM ) : if 桌上沒(méi)有香煙原料then wait(S3,IM);e

43、lse 取原料 signal ( S ,IM ) ; release ( IM ) ; end begin flag1:=flag2:=flag3:=true;end.cobegin process 供應(yīng)者 begin repeat Call (); until false ; end process 吸煙者1 beginrepeat Call () ;做香煙，吸香煙；until false ; end process 吸煙者2 begin repeat Call () ; 做香煙，吸香煙；until false ; end process 吸煙者3 begin repeat Call ();

44、 做香煙，吸香煙；until false ; end coend . 18、 如圖所示，四個(gè)進(jìn)程Pi （i=0 3 ）和四個(gè)信箱Mj (j=0 3 ) ，進(jìn)程間借助相鄰信箱傳遞消息，即Pi 每次從Mi中取一條消息，經(jīng)加工后送入M(i + 1) mod4 ，其中M0 、M1 、M2 、M3 ;可存放3 、3 、2 、2 個(gè)消息。初始狀態(tài)下，MO 裝了三條消息，其余為空。試以P 、V 為操作工具，寫出Pi（i=03）的同步工作算法答：var mutexl , mutexZ , mutex3 ，mutex0 :semaphore; Mutex1nutex2:=mutex3:=mutex0:=1;Em

45、pty0,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取一

46、條消息；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;In

47、2:=(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(full

48、3) ; 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、有三組進(jìn)程Pi 、Qj、Rk ，其中Pi 、Qj構(gòu)成一對(duì)生產(chǎn)者和消費(fèi)者，共享一個(gè)由M1個(gè)緩區(qū)構(gòu)成的循環(huán)緩沖池buf1 。Qj、Rk凡構(gòu)成另一對(duì)生產(chǎn)者和消費(fèi)者，共享一個(gè)由M2 個(gè)緩沖區(qū)構(gòu)成的循環(huán)緩沖池buf2 。如果P

49、i每次生產(chǎn)一個(gè)產(chǎn)品投入buf1,Qj每次從中取兩個(gè)產(chǎn)品組裝成一個(gè)后并投入buf2，Rk每次從中取三個(gè)產(chǎn)品包裝出廠. 試用信號(hào)量和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 ; in