ch3應用題參考答案(完整版)

　　

【正文】 加工消息。 V(full3)。 V(mutex2)。 in2:=(in2+1) mod 2。 從M1[out1]取一條消息。 P(mutex1)。cobegin{process P0begin repeat P(full0)。empty1:=3。 until false。end process 吸煙者1begin repeat Call ()。 release(IM)。 release(IM)。 準備香煙原料。 V(S)。 取原料。 /*供煙草和紙 untile false。 flag1:=flag2:=flag3:=true。當吸煙者完成吸煙后喚醒供應者，供應者再把兩樣東西放在桌子上，喚醒另一個吸煙者。假設{P1,P2,…Pm}是一個已將flag[i]置為in_cs(i=1,2,…,m)(m≤n1)的進程集合，并且已經假設當前turn=k(1≤k≤m)，則Pk必將在有限時間內首先進入臨界區。另外，進程Pi總是先置自己的flag[i]為in_cs后，才去判別Pj進程的flag[j]的值是否等于in_cs，所以，此算法能保證n個進程互斥地進入臨界區。 ③ flag[i]:=in_cs。(j==i or flag[j]≠in_cs) do j:=j+1。tune:0 or 1 or…or,n1。15 試利用記錄型信號量和P、V操作寫出一個不會出現死鎖的五個哲學家進餐問題的算法。庫過程的功能是：把應用進程封鎖起來，所執行的P、V操作的信息組織成消息，執行send發送給與信號量對應的同步管理進程，之后，再執行receive操作以接收同步管理進程的應答。count:=0。 begin check(IM)。procedure add(r)。end.12 證明消息傳遞與管程的功能是等價的：(1) 用消息傳遞實現管程；(2) 用管程實現消息傳遞。procedure P begin check(IM)。}void wait(c) /*等待條件c，開放管程{V(mutex)。相應的用信號量實現的管程庫過程為：var mutex,c:semaphore。 ④ until false。 until false。end}coend.9 在信號量S上作P、V操作時，S的值發生變化，當S＞0、S=0、S0時，它們的物理意義是什么？答：S的值表示它代表的物理資源的使用狀態：S0表示還有共享資源可供使用。 準備顧客的飯菜； V(S3)。var S1,S2,S3,S4:semaphore。應設置兩個信號量：ss2；s1表示是否允許司機啟動汽車(其初值為0)；s2表示是否允許售票員開門(其初值為0)。 end}coend.6 管程的同步機制使用條件變量和Wait及Signal，嘗試為管程設計一種僅僅使用一個原語操作的同步機制。S1:=1。 readerleave(readername)。 endprocedure readerleave(readername) begincheck(IM)。name:array[1..100] of string。 /*A[i].number V(mutex) 進入閱覽室，座位號i，座下讀書。}mutex,seatcount:semaphore。語句⑧先執行：x=10，y=19，z=15。 ③ x:=x+y。 end. end.答：現對進程語句進行編號，以方便描述。 x:=x+5。1） 互斥信號量初值為1，變化范圍為 [n+1 ，1]。 x :=B[get2] 。 P(sput2) 。 Goto L1 。get1 : integer := 0 。end 。end 。process manager。x : itemcobeginprocess reader 。今提供；1） 一個緩沖區，可放置K個信息塊；2） 二個緩沖區，每個可放置K個信息塊；試用信號量和P、V操作寫出三個進程正確工作的流程。rptr : integer := 0 。 V(smanage) 。 B[mptr] := x。 V(sread) 。sget2 : semaphore := 0 。 A[put1] := x 。 get1 :=(get1+1) mod k。 end 。end 。試問PP2并發執行后，x、y、z的值各為多少？P1： P2：begin begin y:=1。 P(S2)。 ⑥ V(S1)。接著無論系統如何調度進程并發執行，當執行到語句⑦時，可以得到x=10，y=4。 name:string。 P(mutex)。 離開閱覽室。 for i=1 to 100 do i++ if name[i]==null then name[i]:=readername。name:=null。試寫出兩進程P1和P2能并發正確執行的程序。 endprocess P2 begin repeat P(S2)。在汽車不斷地到站、停車、行駛過程中，這兩個活動有什么同步關系？用信號量和P、V操作實現它們的同步。} endbusman ( ) begin while(1) { 關車門；， V(s1) 售票； P(s2) 開車門； 上下乘客；} end8 一個快餐廳有4類職員：（1）領班：接受顧客點菜；（2）廚師：準備顧客的飯菜；（3）打包工：將做好的飯菜打包；（4）出納員：收款并提交食品。 接受顧客點菜； V(S2)。endprocess P4begin repeat P(S4)。 print k。 ① print k。答：(1) 用信號量實現管程；Hoare是用信號量實現管程的一個例子，詳見課文內容。}void leavewithsignal(c) /*在條件c上發信號并退出管程，釋放一個等待c條件的進程。 C:integer。 if C≤0 then signal(S,IM)。 full,empty:condition。 if count=1 then sighal(empty,IM)。 release(IM)。 (2) 用消息傳遞實現信號量。14 使用(1)消息傳遞，(2)管程，實現生產者和消費者問題。}coend。 flag[i]:=in_cs。end.試說明該算法滿足臨界區原則。 critical section。顯然，都滿足turn≠i，所以，都可以執行語句③，讓自己的turn為j。為了制造并抽掉香煙，每個吸煙者需要三樣東西：煙草、紙和火柴，供應者有豐富貨物提供。 S:=1。 /*供紙和火柴 else if flag1amp。 吸香煙。process 吸煙者3begin repeat P(S3)。flag1,flag2,flag3:booleanDEFINE give, take1, take2, take3。 if flag1amp。endprocedure take2begin check(IM): if 桌上沒有香煙原料 then wait(S2,IM)。endbegin flag1:=flag2:=flag3:=true。 until false。mutex1:=mutex2:=mutex3:=mutex0:=1。in0,in1,in2,in3,out0,out1,out2,out3。 V(empty0)。 untile false。 P(empty2)。 P(mutex2)。 消息已M3[in3]。 out3:=(out3+1) mod 2。 V(mutex0)。 empty1，empty2，full1，full2。in1:=in2:=out1:=out2:=0。 counter++。 out1:=(out1+1) mod M1。 P(mutex2)。 endprocess Rkbegin L3: P(full2)。 V(mutex2)。Q每隔1小時輸出這個整型變量的內容并將它復位。cobegin{ process Pbegin repeat P(mutex)。 W:=0。既然該進程已獲得了它所需要的全部資源，那么它就能執行完成并釋放它占有的資源，這與前面的假設矛盾，從而證明在這個系統中不可能發生死鎖。但假設汽車駛過了橋A，它在繼續前進，并且在駛過橋B之前，此時有駁船并快速地通過了橋A，駁船頭到達橋B，這時會發生死鎖。 V(Sa)。旅客在博物館逛了一會，然后，排隊乘坐旅行車，當一輛車可用時，它載入一個旅客，再繞花園行駛任意長的時間。mutex:=1。 /*待游玩結束后后，顧客等待下車 V(scl)。答：1) 使用信號量與P、V操作var waits,mutex:semaphore。} then numbersum:=numbersum+number。 SF:codition。 release(IM)。end.main(){cobegin processi()。(7) 不可以分配。使用銀行家算法，以確定下面的任何一個請求是否安全。如果把35個單元分給P4，系統還余5個單元，不再能滿足任何一個進程的需求，系統進入不安全狀態。var mutex：semaphore=1。 P(mutex)。試用信號量與P、V操作正確地實現它們之間的同步關系。因此，可以把這一組緩沖區看成n2組緩沖區，每個發送者需要同時寫n2組緩沖區中相應的n2個緩沖區，而每一個接收者只需讀它自己對應的那組緩沖區中的對應單元。 full[i]=0。for (i=0。}receive(i) /*進程Bi接收消息*/{ p(full[i])?？梢娰Y源數不足，同時各進程申請資源在先，有可能產生死鎖發生的四個條件，故系統可能產生死鎖。wait:=0。 V(mutex1)。 P(mutex1)。(1)用信號量和P、V操作實現；(2)用管程實現。 writer ( )。 count。TYPE readwrite=monitorVAR rc, wc : integer。 signal(R, IM)。end。begin。begin check(IM)。end。DEFINE startread, endread, startwriter, endwriter。 V(rmutex)。 P(rmutex)。為了提高寫者的優先級，增加一個信號量s，用于在寫進程到達后封鎖后續的讀者。 Count1 count2。 P(bridge1)。cobegin{ process P左 process P右 begin begin P(mutex1)。當三個進程執行完申請資源R2后，系統還剩1個R2資源。 將消息從緩沖區取出； V(mutex)。i++) p(empty[i])。 A2( )。其同步關系描述如下：var mutex,empty[n2],full[n2]：semaphore。四個控制關系分別用信號量sa、sb、empty1和empty2實施。 V(px)。 sy=N1。其中，N和M是正整數，試用信號量與P、V操作實現產品X與Y的入庫過程。(2)P4進程到達，P4最大需求60,最初請求35。 (2)不能分配，否則系統會處于不安全狀態。 begin number:=進程讀文件編號。)。USE wait,signal,check,release。 Read file。 wait:=0。