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

1、1、CH3應(yīng)用題參考答案有三個并發(fā)進(jìn)程：R 負(fù)責(zé)從輸入設(shè)備讀入信息塊，M 負(fù)責(zé)對信息塊加工處理；P 負(fù)責(zé)打印輸出信息塊。今提供;l ）一個緩沖區(qū)，可放置K 個信息塊；2 ）二個緩沖區(qū)，每個可放置K 個信息塊；試用信號量和P答：、 V 操作寫出三個進(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 ;wptrx

2、: itemcobegin process reader ; writer ;begininteger : = 0 ;process manager ;processbeginLI : read a message intox ;( swnte ) ;P ( sread );x:=Bswrite;Brptr:=x;wptr:=(wptr+1) mod k;beginL2 : P ( smanage ) ;L3 : Px:=Bmptr;mptr:=(mptr+1) mod k;Rptr:=(rptr+1)mod k;manage the message in x;V(sread);V(smana

3、ge);print the message in x;Goto L1;goto L3;End;end;Bmptr:=x;V(swrite);goto L2;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 : =

4、O ;cobeginprocess reader ;process Writer ;begin beginLl : read a message into x ; L2P ( sgetZ ) ;P ( SPut1 ) ;x= B get2;A put1:=x;get2:= ( get2 + l ) mod k ;Put1:=(put1+1) mod k;V(sput2);V(sget1);print the message in x;Goto L1;goto L3;Put2:=(put2+1) mod k;V(sget2);Goto L2;End;Coendprocessnmanager;be

5、ginP ( sgetl ) ;L3: = A get1 ;xget1 ：(get1+1)mod k ;V(sput1);manage the message into x;P(sput2);2 設(shè)有 n 個進(jìn)程共享一個互斥段，如果：( 1 )每次只允許一個進(jìn)程進(jìn)入互斥段；( 2 )每次最多允許m 個進(jìn)程( m 簇 n )同時進(jìn)入互斥段。試問：所采用的信號量初值是否相同？信號量值的變化范圍如何？答：所采用的互斥信號量初值不同。1 )互斥信號量初值為1 ，變化范圍為-n l , 1。當(dāng)沒有進(jìn)程進(jìn)入互斥段時，信號量值為1 ；當(dāng)有 1 個進(jìn)程進(jìn)入互斥段但沒有進(jìn)程等待進(jìn)入互斥段時，信號量值為O ；當(dāng)有

6、 1 個進(jìn)程進(jìn)入互斥段且有一個進(jìn)程等待進(jìn)入互斥段時，信號量值為-1 ；最多可能有n -1 個進(jìn)程等待進(jìn)入互斥段，故此時信號量的值應(yīng)為- ( n - 1 )也就是 -n+1 。2 )互斥信號量初值為m ，變化范圍為-n m , m 。當(dāng)沒有進(jìn)程進(jìn)入互斥段時，信號量值為m ；當(dāng)有1 個進(jìn)程進(jìn)入互斥段但沒有進(jìn)程等待進(jìn)入互斥段時，信號量值為m - 1 ：當(dāng)有 m 個進(jìn)程進(jìn)入互斥段且沒有一個進(jìn)程等待進(jìn)入互斥段時，信號量值為0 ：當(dāng)有m 個進(jìn)程進(jìn)入互斥段且有一個進(jìn)程等待進(jìn)入互斥段時，信號量值為一l ；最多可能有n - m 個進(jìn)程等待進(jìn)入互斥段，故此時信號量的值應(yīng)為-(n-m) 也就是 -n+m.3有兩個優(yōu)

7、先級相同的進(jìn)程P1和P2,各自執(zhí)行的操彳如下，信號量 S1和S2初 值均為0。試問Pl 、 P2 并發(fā)執(zhí)行后，x 、 y 、 z 的值各為多少？P2:beginP1: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;Endend答：現(xiàn)對進(jìn)程語句進(jìn)行編號，以方便描述號，以方便描述.P1 :P2 :beginx :=1 ;xP(S1);x： x+5 ; ： X Y ; V(S2);z: =Z+X;endbeginy : = 1；y :=y+3 ；V(S1);Z:Y+1 ；P(s2);Y:=

8、z+y; End、 和 是不相交語句，可以任何次序交錯執(zhí)行，而結(jié)果是唯一的。接著無論系統(tǒng)如何調(diào)度進(jìn)程并發(fā)執(zhí)行，當(dāng)執(zhí)行到語句 時，可以得到x = 10 , y = 4 。按Bernstein條件，語句 的執(zhí)行結(jié)果不受語句 的影響，故語句 執(zhí)行后得到z = 5。最后，語句和并發(fā)執(zhí)行，這時得到了兩種結(jié)果為： 語句先執(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

9、，故 y =Z Y=5 + 4=9 ，而 x = 10 。第三種情況為：x = 10 ， Y=9 , Z = 5。4 有一閱覽室，讀者進(jìn)入時必須先在一張登記表上登記，該表為每一座位列出一個表目， 包括座號、姓名， 讀者離開時要注銷登記信息；假如閱覽室共有100 個座位。試用：l )信號量和P 、 V 操作； 2 )管程，來實現(xiàn)用戶進(jìn)程的同步算法。答： 1 )使用信號量和P 、 v 操作：var name ： array l , 100of A ;A = recordnumber ： integer ;name： string ;endfor i : = 1 to 100 do A i .num

10、ber： i ； A i .name :null;mutex , seatcount : semaphore ;i : integer ； mutex : = l ; seatcount : = 100 ;cobeginprocess readeri ( var readename ： string )( i=1 , 2, )P ( seatcount ) ;P ( mutex ) ;for i : = 1 to 100 do i+ if A i .name = null then A i .name : readername；reader get the seat number=i ； /*

11、AI.numberV ( mutex )進(jìn)入閱覽室，座位號i ，座下讀書；P ( mutex ) ;Ainame ： null ;V ( mutex ) ;V(seatcount);離開閱覽室；coend 2 )使用管程操作：TYPE readbook=monitorVAR R: condition ;I,seatcount ： integer;name： array l:100 of string ;DEFINE rcadercome, readerleave ;USE check , wait , signal , release ;Procedure readercome ( reade

12、rname ) begincheck ( IM ) ;if seatcount > 100 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 ) ;endprocedure readerleave ( readername )begincheck ( IM ) ;seatcount-;for i = 1 to 1 00 do i+if name i readern

13、ame then name i :null;release ( IM ) ;endbeginseatcount : = 1OO ; name:= null ;endcobeginprocess readeri ( i = 1 , 2,)beginreadercome ( readername ) ;read the book ;readerleave ( readername ) ;leave the readroom;endcoend.5.在一個盒子里，混裝了數(shù)量相等的黑白圍棋子現(xiàn)在用自動分揀系統(tǒng)把黑子、白子分開，設(shè)分揀系統(tǒng)有二個進(jìn)程P1 和 P2 ，其中 P1 揀白子； P2 揀黑子。規(guī)定

14、每個進(jìn)程每次揀一子；當(dāng)一個進(jìn)程在揀時，不允許另一個進(jìn)程去揀；當(dāng)一個進(jìn)程揀了一子時，必須讓另一個進(jìn)程去揀試寫出兩進(jìn)程P1 和 P2 能并發(fā)正確執(zhí) 行的程序。答 1 ：實質(zhì)上是兩個進(jìn)程的同步問題，設(shè)信號量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 ) ; unti

15、l false ; end coend .答 2 :TYPE pickup-chess = MONITORVAR flag : boolean ;S-black , s-white : codition ;DEFINE pickup-black , pickup-white ;USE wait,signal , check , release ; procedure pickup-black ;begincheck(IM ) ;if flag then wait(s-black,IM ) ;flag :=true;pickup a black;signal(S-white,IM);releas

16、e ( IM ) ;endprocedure pickup-white ;begincheck ( IM ) ;if not flag then wait(S-white,IM );flag :=false ;pickup a white ;signal ( S-black,IM ) ;release ( IM ) ;endbeginflag:=true ;end main ( ) cobeginprocess -B ( ) ;process -W ( ) ;coendprocess-B ( )beginpickup-chess.pickup-black ( ) ;other ;endproc

17、ess-W ( )beginpickup-chess.pickup-white( ) ;other ;end種僅僅6 管程的同步機(jī)制使用條件變量和wait 及 signal ，嘗試為管程設(shè)計一種僅僅使用一個原語操作的同步機(jī)制。答：可以采用形如 waituntil(條件表達(dá)式>的同步原語。如 waituntil( numbersum + number < K ) 表示進(jìn)程由于條件不滿足而應(yīng)等待，當(dāng)進(jìn)程號累加和小于K 時，系統(tǒng)應(yīng)喚醒該進(jìn)程工作7 設(shè)公共汽車上，司機(jī)和售票員的活動分別如下：司機(jī)的活動：啟動車輛：正常行車；到站停車。售票員的活動：關(guān)車門；售票；開車門。在汽車不斷地到站、停車

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

19、 ;S1=0； S2=0；cobegindriver ( ) ;busman ( ) ;coenddriver ( )beginwhile ( 1 ) P ( S1 )啟動車輛；正常行車；到站停車；V ( S2 ) ;endbusman ( )beginwhile ( 1 ) 關(guān)車門；V ( 51 )售票 ;P ( S2 )開車門；上下乘客；end8、一個快餐廳有4 類職員： ( l )領(lǐng)班：接受顧客點菜；( 2 )廚師：準(zhǔn)備顧客的飯菜；( 3 ) 包工：將做好的飯菜打包；( 4 )出納員：收款并提交食品。每個職員可被看作一個進(jìn)程，試用一種同步機(jī)制寫出能讓四類職員正確并發(fā)運行的程序。答：典型的

20、進(jìn)程同步問題，可設(shè)四個信號量51 、 S2 、 S3 和 S4 來協(xié)調(diào)進(jìn)程工作。var S1 , S2 ,S3 , S4 : semaphore ;S1 : = 1 ;S2： =S3 : = S4 : = 0 ;cobegin process P1beginrepeat有顧客到來；P ( S1 )；接受顧客點菜；V ( 52 )；untile false ；endprocess P2 begin repeat P (S2 ) ;準(zhǔn)備顧客的飯菜；v ( S3 ) ; untile false ; endprocess P3 begin repeatP (S3 ) ;將做好的飯菜打包；V ( S4

21、 ) ; untile false ;endprocess P4beginrepeatP( 54 ) ;收款并提交食品；V ( 51 ) ;ufltile false ;endcoend .9、在信號量S上作P、v操作時，S的值發(fā)生變化，當(dāng)S> 0、S=R S< 0時，它們的的物理意義是什么？答： S 的值表示它代表的物理資源的使用狀態(tài)：S > 0 表示還有共享資源可供使用。 S 閱表示共享資源正被進(jìn)程使用但沒有進(jìn)程等待使用資源。S < 0 表示資源已被分配完，還有進(jìn)程等待使用資源。10 ( 1 )兩個并發(fā)進(jìn)程并發(fā)執(zhí)行，其中，A 、 B 、 C 、 D 、 E 是原語，

22、試給出可能的并發(fā)執(zhí)行路徑。Process P Process QbeginbeginA ;D ;B ;E ;C ;end :end ;( 2 )兩個并發(fā)進(jìn)程P1 和 P2 并發(fā)執(zhí)行，它們的程序分別如下：P 1P2repeatrepeatk:=k x 2 ; print k ;k:=k+1 ;k:=0 ;until false ;until false ;若令 k 的初值為5 ，讓 P1 先執(zhí)行兩個循環(huán)，然后，P1 和 P2 又并發(fā)執(zhí)行了一個循環(huán)，寫出可能的打印值，指出與時間有關(guān)的錯誤。( 1 )共有 10 種交錯執(zhí)行的路徑：A 、B 、C 、D、E;A、B、D、E、C;A、B、D、C、E;A

23、、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 )把語句編號，以便于描述：P1P2repeatrepeatk:=k x 2 ； 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由于進(jìn)程P

24、1 和 P2 并發(fā)執(zhí)行，共享了變量K ，故產(chǎn)生了結(jié)果不唯一。11 證明信號量與管程的功能是等價的：( l )用信號量實現(xiàn)管程；( 2 )用管程實現(xiàn)信號量。答： ( 1 )用信號量實現(xiàn)管程；Hoare 是用信號量實現(xiàn)管程的一個例子，詳見課文內(nèi)容。下面介紹另一種簡單方法： 每一個管程都對應(yīng)一個mutex ， 其初值為1 ， 用來控制進(jìn)程互斥調(diào)用管程。再設(shè)一個初值為0 的信號量，用來阻塞等待資源的進(jìn)程。相應(yīng)的用信號量實現(xiàn)的管程庫過程為：Var mutex,c:semaphore ; mutex:=1 ; c:=0 ;進(jìn)入管程代碼，保證互斥void enter-monitor ( ) /*P ( mu

25、tex ) ;void leave-monitor-normally ( )/* 不發(fā)信號退出管程V ( mutex ) ;void leave-with-sigal(c) /* 在條件 c 上發(fā)信號并退出管程，釋放一個等待c條件的進(jìn)程。注意這時沒有開放管程，因為剛剛被釋放的進(jìn)程己在管程 中。V ( c ) ;void wait(c) /* 等待條件c ，開放管程V ( mutex ) ;P (c) ;( 2 )用管程實現(xiàn)信號量。TYPE semaphore=monitorVAR S ; condition ;C:integer ;DEFINE P , V ;USE check , wait

26、, signal , release ;procedure Pbegincheck ( IM ) ;C:= C-1 :if C < 0 then wait ( S,IM ) ;release ( IM ) ;end procedure Vbegincheck ( IM ) :C : = C + 1 ;if C <0 then signal ( S,IM );release ( IM ) ;end beginC：=初值;End.12 證明消息傳遞與管程的功能是等價的：( 1 )用消息傳遞實現(xiàn)管程；( 2 )用管程實現(xiàn)消息傳遞。答： ( 1 )用消息傳遞實現(xiàn)管程；用消息傳遞可以實現(xiàn)信號

27、量(見13 ( 2 ) ) ，用信號量可以實現(xiàn)管程(見11(1 ) ) ，那么，把兩種方法結(jié)合起來，就可以用用消息傳遞實現(xiàn)管程。( 2 )用管程實現(xiàn)消息傳遞。TYPE mailbox=monitorVAR r , k , count:integer ;bufferarray0 , n-1 of message ;full , empty:condition ;DEFINE add , get ;USE check , wait , signal , release ; procedure add ( r ) ;begincheck ( IM ) ;if count=n then wait (

28、full,IM ) ;buffer r:=message ;r:=(r+1) mod ncount:=count + 1 ;if count = 1 then sighal ( empty , IM ) ; release ( IM ) ;end procedure get ( m ) ;begincheck ( IM ) ;if count = 0 then wait ( empty , IM ) ;m:=buffer k；count : = count-1 ;if count = n-1 then signal ( full , IM ); release ( IM ) ;endbegin

29、r:= 0 ; k:= 0 ; count:=0 ;end13 證明信號量與消息傳遞是等價的：( 1 )用信號量實現(xiàn)消息傳遞；( 2 )用消息傳遞實現(xiàn)信號量。答： ( l )用信號量實現(xiàn)消息傳遞；1 ) 把消息隊列組織成一個共享隊列，用一個互斥信號量管理對該隊列的入隊操作和出隊操作.2 )發(fā)送消息是一個入隊操作，當(dāng)隊列存儲區(qū)滿時，設(shè)計一個同步信號量阻塞send 操作。3 ) 接收消息是一個出隊操作，當(dāng)隊列存儲區(qū)空時，設(shè)計另一個同步信號量阻塞receive 操作。( 2 )用消息傳遞實現(xiàn)信號量。l ) 為每一個信號量建立一個同步管理進(jìn)程，它包含了一個計數(shù)器，記錄信號量值；還為此信號量設(shè)立一個等待

30、進(jìn)程隊列2 )應(yīng)用進(jìn)程執(zhí)行P或V操作時，將會調(diào)用相應(yīng)P、V庫過程。庫過程的功能是： 把應(yīng)用進(jìn)程封鎖起來，所執(zhí)行的P 、 V 操作的信息組織成消息，執(zhí)行 send 發(fā)送給與信號量對應(yīng)的同步管理進(jìn)程，之后，再執(zhí)行receive 操作以接收同步管理進(jìn)程的應(yīng)答。3 ) 當(dāng)消息到達(dá)后，同步管理進(jìn)程計數(shù)并查看信號量狀態(tài)。如果信號量的值為負(fù)的話，執(zhí)行P 操作的應(yīng)用進(jìn)程被阻塞，掛到等待進(jìn)程隊列，所以，不再要送回答消息。此后，當(dāng)V 操作執(zhí)行完后，同步管理進(jìn)程將從信號量相應(yīng)隊列中選取一個進(jìn)程喚醒，并回送一個應(yīng)答消息。正常情況下，同步管理進(jìn)程回送一個空應(yīng)答消息，然后，解鎖執(zhí)行P 、 V 操作的應(yīng)用程序。14 使用(

31、 1)消息傳遞，( 2 )管程，實現(xiàn)生產(chǎn)者和消費者問題。答：( 1 )見課文 ch3 3.5.4 節(jié)。(2 )見課文Ch3 3.4.3 節(jié)。15 試?yán)糜涗浶托盘柫亢蚉 、 V 操作寫出一個不會出現(xiàn)死鎖的五個哲學(xué)家進(jìn)餐問題的算法。答：var forki:array 0, 4 of semaphore ;forki:=1 ;cobeginprocess Pi /* i = 0 , 1 , 2 , 3 */ beginL1 :思考：P(forki) ;/ * i =4,P(fork 0) * /P(forki+1 mod 5) / * i =4P( fork 4 ) * /吃通心面；V (fork

32、i ;V (fork(i+1 mod 5 ) ;goto L1 ;end ;coend ;16 Dijkstra 臨界區(qū)軟件算法描述如下：var flag ： array0 , 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 ;beginrepeatrepeatflag i :want_in ;while turn* 1 doif flagturn=idle then turn:=i ;flagi:= ip_cs ;j:=0

33、;while (j < n ) & (j=1 or flagj* in_cs )do j:=j + 1 ;until j >n :critical section ;flag i:=idle ;until false ;end .試說明該算法滿足臨界區(qū)原則。答：為方便描述，把Dijkstra 程序的語句進(jìn)行編號：repeat flagi:=want_in ； while turn wi do if flagtrun=idle then turn:=i； flagi: = in_cs ； j:= O ;while(j < n ) & (j=1 or flagj豐

34、 in_cs ) do j:=j + 1 ; until j >n ;critical section ;flagi :=idle ；( l )滿足互斥條件當(dāng)所有的巧都不在臨界區(qū)中，滿足flagj win_cs (對于所有j , j為)條件時， Pi 才能進(jìn)入它的臨界區(qū)，而且進(jìn)程Pi 不會改變除自己外的其他進(jìn)程所對應(yīng)的 flagj 的值。另外，進(jìn)程Pi 總是先置自己的flagj 為 in_cs 后，才去判別 Pj 進(jìn)程的 flagj 的值是否等于in_cs 所以， 此算法能保證n 個進(jìn)程互斥地進(jìn)入臨界區(qū)。( 2 )不會發(fā)生無休止等待進(jìn)入臨界區(qū)由于任何一個進(jìn)程Pi 在執(zhí)行進(jìn)入臨界區(qū)代碼時先

35、執(zhí)行語句，其相應(yīng)的flagi 的值不會是idle 。注意到flagi = in_cs并不意味著turn的值一定 等于i。我們來看以下情況，不失一般性，令turn的初值為0,且P0不工作， 所以， flagturn=flag0=idle 。 但是若干個其他進(jìn)程是可能同時交替執(zhí)行的，假設(shè)讓進(jìn)程Pj(j=l , 2 , , n-l ) 交錯執(zhí)行語句后 (這時 flagj=want_in ) ，再做語句(第一個while 語句)，來查詢flagturn 的狀態(tài)。顯然，都滿足turn wi ,所以，都可以執(zhí)行語句，讓自己的turn為j。但turn僅有一個值，該值為最后一個執(zhí)行此賦值語句的進(jìn)程號，設(shè)為 k

36、、即turn=k (1 <k<n-1 )。接著，進(jìn)程Pj(j=1,2, , n-l ) 交錯執(zhí)行語句，于是最多同時可能有n-1個進(jìn)程處于in_cs狀態(tài)，但不要忘了僅有一個進(jìn)程能成功執(zhí)行語句，將加 m 置為自己的值。假設(shè) P1 , P2 , , Pm 是一個己將 flagi 置為 in_cs ( i =1,2, , ,m ) (m < n -1 )的進(jìn)程集合，并且已經(jīng)假設(shè)當(dāng)前 turn=k ( 1 < k< m )，則Pk必 將在有限時間內(nèi)首先進(jìn)入臨界區(qū)。因為集合中除了Pk 之外的所有其他進(jìn)程終將從它們執(zhí)行的語句(第二個while 循環(huán)語句)退出， 且這時的j 值必

37、小于n ，故內(nèi)嵌until起作用，返回到起始語句重新執(zhí)行，再次置flag i =want_in ，繼續(xù)第二輪循環(huán)，這時的情況不同了，flagturn =flag k 必定idle (而為in_cs )。而進(jìn)程Pk發(fā)現(xiàn)最終除自身外的所有進(jìn)程 Pj的flagj win_cs ,并據(jù)及可進(jìn)入其臨界區(qū)。17 另一個經(jīng)典同步問題：吸煙者問題(patil , 1971 )。三個吸煙者在一個房間內(nèi)，還有一個香煙供應(yīng)者。為了制造并抽掉香煙，每個吸煙者需要三樣?xùn)|西：煙草、 紙和火柴，供應(yīng)者有豐富貨物提供。三個吸煙者中，第一個有自己的煙草，第二個有自己的紙和第三個有自己的火柴。供應(yīng)者隨機(jī)地將兩樣?xùn)|西放在桌子上，允

38、許一個吸煙者進(jìn)行對健康不利的吸煙。當(dāng)吸煙者完成吸煙后喚醒供應(yīng)者，供應(yīng)者再把兩樣?xùn)|西放在桌子上，喚醒另一個吸煙者。試采用：( 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;cobeginprocess 供應(yīng)者beginrepeatP(S) ;取兩樣香煙原料放桌上，由flagi 標(biāo)記； /* nago1 、 n

39、age2 、 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 吸煙者 2begin repeatP (S2 ) ;取原料；做香煙；V(S) ;吸香煙；untile false ;process 吸煙者 3begin repe

40、atP (S3 ) ;取原料；做香煙；V ( S ) ;吸香煙；untile false ;coend .( 3 )用管程。TYPE mskesmoke=moonitorVAR S, S1 ,S2 ,S3 : condition ;flag1 , flag2, flag3 : booleanDEFINE give , take1 , take2 , take3 ;USE check , wait , signal , release ;procedure givebegincheck ( IM ) ;準(zhǔn)備香煙原料；if 桌上有香煙原料then wait( S , IM ) ; 把準(zhǔn)備的香煙原料

41、放桌上；if fiag2 & flag3 then signal ( S1 ,IM) ;if flag1 & flag3 then signal ( S2 ,IM ) ; else signal (S3 , IM ) ;release ( IM ) ;endprocedure take1begincheck(IM):if 桌上沒有香煙原料then wait ( S1 ,IM ) ;else 取原料；signal ( S , IM ) ;release ( IM ) ;endprocedure take2begincheck ( IM ) :if 桌上沒有香煙原料then wai

42、t(S2,IM);else 取原料；signal ( S , IM ) ;release ( IM) ;endprocedure take3begincheck ( IM ) :if 桌上沒有香煙原料then wait(S3,IM);else 取原料signal ( S ,IM ) ;release ( IM ) ;endbeginflag1:=flag2:=flag3:=true;end.cobeginprocess 供應(yīng)者beginrepeatCall makesmoke.give();until false ;endprocess 吸煙者 1beginrepeatCall makesmo

43、ke.take1() ;做香煙，吸香煙；until false ;endprocess 吸煙者 2beginrepeatCall makesmoke.take2() ;做香煙，吸香煙；until false ;endprocess 吸煙者 3beginrepeatCall makesmke.take3();做香煙，吸香煙；until false ;endcoend .18、如圖所示，四個進(jìn)程Pi ( i=0 , 3 )和四個信箱Mj (j=0 , 3 ) ，進(jìn)程間借助相鄰信箱傳遞消息，即Pi 每次從 Mi 中取一條消息，經(jīng)加工后送入M(i +1) mod4,其中M0、M1、M2、M3;可存放3

44、、3、2、2個消息。初始狀態(tài) 下，MO裝了三條消息，其余為空。試以 P、V為操作工具，寫出Pi (i=0, 3) 的同步工作算法答：var mutexl , mutexZ , mutex3 ， mutex0 :semaphore;Mutexl = nutex2:=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:=full

45、3:=0;in0,in1,in2,in3,out0 ,out2,out3,;intger;in0:=in1: = in2: = in3:=out0:=out1:=out2:=out3:=0;cobeginprocess P0beginrepeatP(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 ;endproce

46、ss P1beginrepeatP ( 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 ; endprocess P2beginrepeatP(full2) ;P(mutex2 ) ;從 M2out2 取一條消息；out2:=(out2 + l ) mod 2;V(mutex2) ;V(empty2

47、) ;加工消息；P(empty3) ;P(mutex3) ;消息己 M3in3;in3:=(in3+1) mod 2 ;V(mutex3) ;V(full3) ;untile false ;end process P3beginrepeatP(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 ;en

48、d coend19、有三組進(jìn)程Pi 、 Qj、 Rk ，其中 Pi 、 Qj 構(gòu)成一對生產(chǎn)者和消費者，共享一個由M1個緩區(qū)構(gòu)成的循環(huán)緩沖池bufl。Qj、Rk凡構(gòu)成另一對生產(chǎn)者和消費 者，共享一個由M2個緩沖區(qū)構(gòu)成的循環(huán)緩沖池 buf2 0如果Pi每次生產(chǎn)一個產(chǎn) 品投入buf1,Qj每次從中取兩個產(chǎn)品組裝成一個后并投入buf2 , Rk每次從中取三個產(chǎn)品包裝出廠.試用信號量和P、V操作寫出它們同步工作的程序。var mutex1 , mutex2 , mutex3 : semaphore; empty1 , empty2 , full1 , full2 ; semaphore ;in1 , i

49、n2 , out1 , out2 : integer ; counter1 , counter2:integer ;buffer1:array0 , M1-1 of item ; buffer2:array0 , M2-1of item ;empty1:=M1 ; empty:=M2;in1 : = in2 :=out1:=out2:=0 ; counter1:=counter2:=0 ;fun1:=full2: = mutex1:=mutex2:=mutex3:=1;cobeginprocess PibeginL1:P(empty1) ;P(mutex1 ) ;put an item int

50、o buffer in1 ;in1:=(in1+1) mod M1 ;counter+;if counter1 = 2 then counter1:=0;V(full1);V(mutex) ;goto L1;end process QjbeginL2: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 )

51、 ;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 Rkbegin L3 :P ( full2 ) ;P ( mutex2 ) ;take an item from buffer2 out2;out2: = ( out2 + 1 ) mod M2 ;take

52、 an item from buffer2 out2 ;out2:=( out2 + 1) mod M2 ;take an item from buffer2 out2;out2:=(out2 + 1 ) mod M2 ;v ( mutex2 ) ;V ( empty2 ) ;V ( empty2 ) ;V ( empty2 ) ;packet the products ;goto L3 ;end coend20 在一個實時系統(tǒng)中，有兩個進(jìn)程P 和 Q ，它們循環(huán)工作。P 每隔 1 秒由脈沖寄存器獲得輸入，并把它累計到整型變量W上，同時消除脈沖寄存器。Q每隔 1 小時輸出這個整型變量的內(nèi)容并將它復(fù)位。系統(tǒng)提供了標(biāo)準(zhǔn)例程創(chuàng)PUT 和OUT 衛(wèi) UT 供拍，提供了延時系統(tǒng)調(diào)用Delay ( seconds )。試寫出兩個并發(fā)進(jìn)程循環(huán)工作的算法。Var W ,V:integer;Mutex:semaphore;W:=0 ; V:=0 ;mutex:1;cobegin process PbeginrepeatP(mutex) ;delay (