P、V操作習(xí)題答案

1、信號(hào)量應(yīng)用問題：1 寫出程序描述下列前趨關(guān)系。 S1-S2, S1-S3, S2-S4, S2-S5 , S3-S6, S4-S7, S5-S7, S6-S7Var s1,s2, s3,s4:semaphore:=0, 0, 0, 0;Begin Parbegin P1: begin .; V(s1); V(s1); End; P2: begin P(s1); ; V(s2); V(s2); End; P3: begin P(s1) V(s3) End; P4: begin P(s2); V(s4); P5: begin P(s2); .; V(s4);End; P6: begin P(s3)

2、 . V(s4) End; P7:begin P(s4); P(s4); P(s4); End; Parend end 2. 請(qǐng)用信號(hào)量實(shí)現(xiàn)4100（4人，每人100米）接力賽的同步過程。提示：前趨圖同步問題，可設(shè)4個(gè)進(jìn)程，三個(gè)信號(hào)量，進(jìn)程1只設(shè)V操作，進(jìn)程4只設(shè)P操作，其余進(jìn)程先做P操作再做V操作。Var s1,s2,s3:semaphore:=0, 0, 0;Begin Parbegin Athlete1: begin Run 100m; V(s1); End;Athlete2: begin P(s1) Run 100m; V(s2); End;Athlete3: begin P(s2)

3、; Run 100m; V(s3); End;Athlete4: begin P(s3); Run 100m; End; Parendend3設(shè)公共汽車上，司機(jī)和售票員的活動(dòng)分別是： 司機(jī)： 售票員： 啟動(dòng)車輛 上乘客 正常行車 關(guān)車門 到站停車 售票 開車門 下乘客 在汽車不斷地到站、停車、行駛過程中，這兩個(gè)活動(dòng)有什么同步關(guān)系？請(qǐng)用信號(hào)量機(jī)制實(shí)現(xiàn)他們的同步。/-假定初始狀態(tài)為停車狀態(tài)，引入信號(hào)量Stop和Run： BEGIN semaphore Stop,Run; Stop:=Run:=0; CoBegin Driver: BEGIN Repeat Wait(Run); 啟動(dòng)車輛； 正常行駛

4、； 到站停車； Signal(Stop); Until False; END; Conductor:BEGIN Repeat 上乘客； 關(guān)車門； Signal(Run); 售票； Wait(Stop); 開車門； 下乘客； Until False; END; CoEnd; END;生產(chǎn)者消費(fèi)者問題：1 桌上有一個(gè)可以容納兩個(gè)水果的盤子，每次只能放或取一個(gè)水果。爸爸放蘋果媽媽放橘子，兩個(gè)兒子吃蘋果，兩個(gè)女兒吃橘子。試用信號(hào)量和P、V操作，編寫實(shí)現(xiàn)爸爸、媽媽、兒子和女兒的并發(fā)工作程序。Mutex實(shí)現(xiàn)互斥放或取水果。empty盤子可放水果數(shù)Apple 盤子中放的蘋果數(shù)Orange 盤子中放的橘子數(shù)S

5、emaphore mutex=1;Semaphore empty=2;Semahpore apple=0;Semahpore orange=0;Main()Cobegin Father();Mother();Son();Daughter();Coend)Father()While(true) p(empty) P(mutex)放蘋果V(mutex)V(apple)Mother()While(true) p(empty) P(mutex) 放橘子 V(mutex) V(orange)Son()While(true) p(apple) P(mutex) 取蘋果 V(mutex) V(empty)D

6、aughter()While(true) p(orange) P(mutex) 取橘子 V(mutex)V(empty)2、有一個(gè)倉(cāng)庫(kù)存放兩種零件A和B，最大庫(kù)容量各為m個(gè)。有一車間不斷地取A和B進(jìn)行裝配，每次各取一個(gè)。為了避免零件銹蝕，遵循線入庫(kù)者先出庫(kù)的原則。有兩組供應(yīng)商分別不斷地供應(yīng)A和B（每次一個(gè)），為保證齊套和合理庫(kù)存，當(dāng)某種零件的數(shù)量比另一種數(shù)量超過n（nm）個(gè)時(shí)，暫停對(duì)數(shù)量大的零件的進(jìn)貨，集中補(bǔ)充數(shù)量少的零件。試用P、V操作正確實(shí)現(xiàn)之。 semaphore mutex=1, emptya=emptyb=m, fulla=fullb=0, sa=sb=n; main() CoBeg

7、in Provider_A(); /零件A供應(yīng)商 Provider_B(); /零件B供應(yīng)商 Assembling_Shop(); /裝配車間 CoEnd Provider_A() while(true) p(emptya); p(sa); p(mutex); 將零件A放入倉(cāng)庫(kù); v(mutex); v(fulla); v(sb); Provider_B() while(true) p(emptyb); p(sb); p(mutex); 將零件B放入倉(cāng)庫(kù); v(mutex); v(fullb); v(sa); Assembling_Shop() while(true) p(fulla); p(

8、fullb); p(mutex); 裝配零件; v(mutex); v(emptya); v(emptyb); 3、有一個(gè)倉(cāng)庫(kù)，可以存放A和B兩種產(chǎn)品，倉(cāng)庫(kù)的存儲(chǔ)空間足夠大，但要求： 每次只能存入一種產(chǎn)品（X或Y）； -NA產(chǎn)品數(shù)量-B產(chǎn)品數(shù)量M。 其中，N和M時(shí)正整數(shù)。 試用“存放A”、“存放B”和P、V操作描述產(chǎn)品A與產(chǎn)品B的入庫(kù)過程。A-BM說明：如果只放A不放B，則A最多可放M-1個(gè)，如果多放一個(gè)B，則可以多放一個(gè)A。B-AN說明：如果只放B不放A，則B最多可放N-1個(gè)，如果多放一個(gè)A，則可以多放一個(gè)B。/2-BEGIN Mutex,SA,SB:semaphore; Mutex:=1;

9、 SA:=M-1; SB:=N-1; parBegin process PA Beginloop: P(SA); P(Mutex); 存放A; V(Mutex); V(SB);Goto loop; End; process PB Begin loop: P(SB); P(Mutex); 存放B; V(Mutex); V(SA);Goto loop; End; parEnd; END;/北大91讀者寫者問題：1、多個(gè)進(jìn)程共享一個(gè)文件，其中只讀文件的程值為讀者，其余只寫文件的稱為寫者。讀者可以同時(shí)讀，但寫者只能獨(dú)立地寫。 說明進(jìn)程間的相互制約關(guān)系，應(yīng)設(shè)置哪些信號(hào)量？ 用P、V操作寫出其同步算法；

10、修改上述算法，使得它對(duì)寫者優(yōu)先，即一旦有寫者到達(dá)，后續(xù)的讀者都必須等待，而無論是否有讀者在讀文件。（該問題的又一提法：在一個(gè)飛機(jī)訂票系統(tǒng)中，多個(gè)用戶共享一個(gè)數(shù)據(jù)庫(kù)。多用戶同時(shí)查詢是可以接受的，但若一個(gè)用戶要訂票需更新數(shù)據(jù)庫(kù)時(shí)，其余所有用戶都不可以訪問數(shù)據(jù)庫(kù)。請(qǐng)畫出用戶查詢與訂票的邏輯框圖(等價(jià)于同步進(jìn)程的描述的圖式表示)。為了提高寫者的優(yōu)先級(jí)，增加一個(gè)信號(hào)量S，用于在寫進(jìn)程到達(dá)后封鎖后續(xù)的讀者Semaphore mutex=1;Semaphore write=1;Semahpore s=1;Int count =0;Main() Cobegin Reader();Writer();Coend；

11、 Reader() while(true) P(s);P(mutex);If(count=0) p(write);Count+;V(s);讀文件；P(mutex)Count-;If(count=0) v(write);V(mutex);Writer() While(true) p(s);P(write); 寫文件；V(write);V(s);2某一橋只有一車道，載重為4輛車，用P、V操作實(shí)現(xiàn)兩方向的車過橋。本題本質(zhì)上可以認(rèn)為是讀者寫者問題，往同一個(gè)方向的車可以認(rèn)為是讀者，往相反方向的車可以認(rèn)為是寫者。但是由于橋的重量有限，增加了讀者之間的互斥。本題的臨界資源顯然是單通道的橋，首先如果橋上有向東

12、方向的車，那么向西方向的車一定不能過，如果超過4輛，同一方向的車也不能過，需要互斥。設(shè)信號(hào)量mutex，實(shí)現(xiàn)雙向車子互斥通行；信號(hào)量sew，swe表示由西向東與由東向西的負(fù)荷數(shù)，初值為4；整數(shù)型iew,iwe表示各方向的車子數(shù)，初值為0；siew,siwe實(shí)現(xiàn)對(duì)iew,iwe的互斥訪問，初值為1；Process 由東向西的車子；Begin P(sew);P(siew);Iew:=iew+1;If iew=1 then p(mutex);V(siew);過橋；P(siew);Iew:=iew-1;If iew=0 then v(mutex);V(siew);V(sew)EndPorcess 由西

13、向東Begin P(swe);P(siwe); Iwe:=iwe+1;If iwe=1 hten p(mutex);V(siwe);過橋；P(siwe);Iwe:=iwe-1;If iwe=0 then v(mutex);V(siwe);V(swe)End;理發(fā)師睡覺問題：1（睡眠的理發(fā)師問題）理發(fā)店有一個(gè)等候室（其中有N把椅子）和一個(gè)理發(fā)室（一把理發(fā)椅組成）。如果沒有顧客來理發(fā)，理發(fā)時(shí)就在理發(fā)椅上睡覺，如果一個(gè)走進(jìn)理發(fā)店，發(fā)現(xiàn)等候室的椅子都坐滿就離開理發(fā)店；如果理發(fā)師正忙于理發(fā)，那么該顧客就坐在一把空椅子上等待；若理發(fā)師正在睡覺，則顧客就喚醒他。用P、V操作寫出工作流程。 考點(diǎn)： 用PV原語

14、實(shí)現(xiàn)同步Semaphore costomers=0; 等候的顧客數(shù)（不包括正在理發(fā)的）Semaphore barbers=0; 等候顧客的理發(fā)師數(shù)Semaphore mutex=1; Int waiting =0; 等候的顧客數(shù)（還沒有理發(fā)，實(shí)際是customers的備份，為了讀取信號(hào)量的當(dāng)前值）；Void barber(void) while (true) P(customers); P(mutex); waiting = waiting 1 ; V(barbers); V(mutex); cut_hair( );顧客進(jìn)程Void customers(void)P(mutex); if(wa

15、itingchairs) waiting = waiting + 1 ; V(customers); V(mutex); P(barbers); get_hair( ); else V(mutex);提示：考慮一下理發(fā)師（barber）重復(fù)的下列活動(dòng)：（1）睡覺；（2）為顧客理發(fā)；顧客（customers）重復(fù)的下列活動(dòng)：（3）在椅子上等候；（4）理發(fā)；離開；顯然，理發(fā)師在（1）處要考察是否有顧客等候理發(fā)，如果沒有，理發(fā)師睡覺；在（2）處理發(fā)師等待最先進(jìn)入理發(fā)店的顧客喚醒，開始理發(fā)。顧客在（3）處先看是否有座位，沒有則離開；等候理發(fā)的顧客在（4）處被理發(fā)師喚醒（最先理發(fā)的顧客要喚醒理發(fā)師）；理

16、發(fā)結(jié)束后離開。在這兩個(gè)活動(dòng)中，從資源的角度來看，理發(fā)師是顧客爭(zhēng)用的資源，用信號(hào)量barber表示，初值為0；除此以外，顧客還要爭(zhēng)用n張椅子，信號(hào)量customers表示等候理發(fā)的顧客數(shù)，初值為0；最后設(shè)置信號(hào)燈變量mutex用于這兩個(gè)活動(dòng)對(duì)資源barber、customers的互斥，初值為1。2復(fù)印室里有一個(gè)操作員為顧客復(fù)印資料，有5把椅子供顧客休息等待復(fù)印。如果沒有顧客，則操作員休息，當(dāng)顧客來到復(fù)印室時(shí)，如果有空椅子則坐下來，并喚醒復(fù)印操作員；如果沒有空椅子必須離開復(fù)印室。試用信號(hào)量幾P、V操作實(shí)現(xiàn)顧客和操作員活動(dòng)的同步。Customers 表示正在等待復(fù)印的顧客數(shù)Operator 代表操作

17、員的狀態(tài)，只能取1或0；Waiting 表示正在等待的顧客數(shù)；Mutex實(shí)現(xiàn)對(duì)waiting的互斥訪問customers, operator,mutex: semaphore;waiting: inteter;customers=0;operator=0;mutex=1;process operatorbegin loop: p(customers); 復(fù)??；V(operator);Goto loop;End;Process coutomeriBegin P(mutex); If waiting 5 then Begin Waiting=waiting+1;V(custormers);V(mu

18、tex);P(operator);P(mutex);Waiting=waiting-1;V(mutex);EndElseBegin V(mutex);End;End;4理發(fā)師問題：一個(gè)理發(fā)店有一個(gè)入口和一個(gè)出口。理發(fā)店內(nèi)有一個(gè)可站5 位顧客的站席 區(qū)、4 個(gè)單人沙發(fā)、3 個(gè)理發(fā)師及其專用理發(fā)工具、一個(gè)收銀臺(tái)。新來的顧客坐在沙發(fā)上等 待；沒有空沙發(fā)時(shí)，可在站席區(qū)等待；站席區(qū)滿時(shí)，只能在入口外等待。理發(fā)師可從事理 發(fā)、收銀和休息三種活動(dòng)。理發(fā)店的活動(dòng)滿足下列條件： 1）休息的理發(fā)師是坐地自己專用的理發(fā)椅上，不會(huì)占用顧客的沙發(fā)； 2）處理休息狀態(tài)的理發(fā)師可為在沙發(fā)上等待時(shí)間最長(zhǎng)的顧客理發(fā)； 3）理發(fā)

19、時(shí)間長(zhǎng)短由理發(fā)師決定； 4）在站席區(qū)等待時(shí)間最長(zhǎng)的顧客可坐到空閑的理發(fā)上； 5）任何時(shí)刻最多只能有一個(gè)理發(fā)師在收銀。 試用信號(hào)量機(jī)制或管程機(jī)制實(shí)現(xiàn)理發(fā)師進(jìn)程和顧客進(jìn)程。原理： (1)customer 進(jìn)程： 首先檢查站席區(qū)是否已滿（stand_capacity）,若滿選擇離開，否則進(jìn)入站席區(qū)，即進(jìn)入 理發(fā)店。在站席區(qū)等待沙發(fā)的空位（信號(hào)量sofa），如果沙發(fā)已滿，則進(jìn)入阻塞等待隊(duì)列， 直到出現(xiàn)空位，在站席區(qū)中等待時(shí)間最長(zhǎng)的顧客離開站席區(qū)（stand_capacity）。坐到沙 發(fā)上，等待理發(fā)椅(barber_chair)，如果理發(fā)椅已滿，則進(jìn)入阻塞等待隊(duì)列，直到出現(xiàn) 空位，在沙發(fā)上等待時(shí)間最長(zhǎng)

20、的顧客離開沙發(fā)（釋放信號(hào)量sofa）。坐到理發(fā)椅上，釋放 準(zhǔn)備好的信號(hào)（customer_ready），獲得該理發(fā)師的編號(hào)（01 的數(shù)字）。等待理發(fā)師理 發(fā)結(jié)束（finishedbarber_number）。在離開理發(fā)椅之前付款（payment），等待收據(jù) (receipt)，離開理發(fā)椅（leave_barberchair）。最后離開理發(fā)店。 這里需要注意幾點(diǎn)： a) 首先是幾個(gè)需要進(jìn)行互斥處理的地方，主要包括:進(jìn)入站席區(qū)、進(jìn)入沙發(fā)、進(jìn)入理發(fā)椅 和付款幾個(gè)地方。 b) 通過barber_chair 保證一個(gè)理發(fā)椅上最多只有一名顧客。但這也不夠，因?yàn)閱螒{ baber_chair 無法保證一名顧客

21、離開理發(fā)椅之前，另一位顧客不會(huì)坐到該理發(fā)椅上， 因此增加信號(hào)量leave_barberchair，讓顧客離開理發(fā)椅后，釋放該信號(hào)，而理發(fā) 師接收到該信號(hào)后才釋放barber_chair 等待下一位顧客。 c) 在理發(fā)的過程中，需要保證是自己理發(fā)完畢，才能夠進(jìn)行下面的付款、離開理發(fā)椅的活 動(dòng)。這個(gè)機(jī)制是通過customer 進(jìn)程獲得給他理發(fā)的理發(fā)師編號(hào)來實(shí)現(xiàn)的，這樣，當(dāng) 該編號(hào)的理發(fā)師釋放對(duì)應(yīng)的finished信號(hào)的時(shí)候，該顧客才理發(fā)完畢。 d) 理發(fā)師是通過mutex 信號(hào)量保證他們每個(gè)人同時(shí)只進(jìn)行一項(xiàng)操作（理發(fā)或者收款）。 e) 為了保證該顧客理發(fā)完畢后馬上可以付款離開，就應(yīng)該保證給該顧客理

22、發(fā)的理發(fā)師在理 發(fā)完畢后馬上到收銀臺(tái)進(jìn)入收款操作而不是給下一位顧客服務(wù)。在偽碼中由以下機(jī)制實(shí) 現(xiàn)：即顧客在釋放離開理發(fā)椅的信號(hào)前，發(fā)出付款的信號(hào)。這樣該理發(fā)師得不到顧客的 離開理發(fā)椅的信號(hào)，不能進(jìn)入下一個(gè)循環(huán)為下一名顧客服務(wù)，而只能進(jìn)入收款臺(tái)的收款 操作。直到顧客接到收據(jù)后，才釋放離開理發(fā)椅的信號(hào)，離開理發(fā)椅，讓理發(fā)師釋放該 理發(fā)椅的信號(hào)，讓下一位等待的顧客坐到理發(fā)椅上。 (2)barber 進(jìn)程 首先將該理發(fā)師的編號(hào)壓入隊(duì)列，供顧客提取。等待顧客坐到理發(fā)椅坐好(信號(hào)量 customer_ready)，開始理發(fā)，理發(fā)結(jié)束后釋放結(jié)束信號(hào)（finished）。等待顧客 離開理發(fā)椅（leave_ba

23、rberchair）（期間去收銀臺(tái)進(jìn)行收款活動(dòng)），釋放理發(fā)椅空閑信 號(hào)(barber_chair)，等待下一位顧客坐上來。 (3)cash（收銀臺(tái)）進(jìn)程 等待顧客付款(payment),執(zhí)行收款操作，收款操作結(jié)束，給付收據(jù)（receipt）。 信號(hào)量總表： 信號(hào)量 wait signal stand_capacity 顧客等待進(jìn)入理發(fā)店 顧客離開站席區(qū) sofa 顧客等待坐到沙發(fā) 顧客離開沙發(fā) barber_chair 顧客等待空理發(fā)椅 理發(fā)師釋放空理發(fā)椅 customer_ready 理發(fā)師等待，直到一個(gè)顧客坐 到理發(fā)椅 顧客坐到理發(fā)椅上，給理發(fā)師 發(fā)出信號(hào) mutex 等待理發(fā)師空閑，執(zhí)行

24、理發(fā)或 收款操作 理發(fā)師執(zhí)行理發(fā)或收款結(jié)束， 進(jìn)入空閑狀態(tài) mutex1 執(zhí)行入隊(duì)或出隊(duì)等待 入隊(duì)或出隊(duì)結(jié)束，釋放信號(hào) finished 顧客等待對(duì)應(yīng)編號(hào)理發(fā)師理 發(fā)結(jié)束 理發(fā)師理發(fā)結(jié)束，釋放信號(hào) leave_barberchair 理發(fā)師等待顧客離開理發(fā)椅 顧客付款完畢得到收據(jù)，離開 理發(fā)椅釋放信號(hào) payment 收銀員等待顧客付款 顧客付款，發(fā)出信號(hào) receipt 顧客等待收銀員收、開具收據(jù)收銀員收款結(jié)束、開具收據(jù)， 釋放信號(hào) 偽碼： semaphore stand_capacity=5; semaphore sofa=4; semaphore barber_chair=3; sema

25、phore customer_ready=0; semaphore mutex=3; semaphore mutex1=1; semaphore finished3=0,0,0; semaphore leave_barberchair=0; semaphore payment=0; semaphore receipt=0; void customer() int barber_number; wait(stand_capacity); /等待進(jìn)入理發(fā)店 enter_room(); /進(jìn)入理發(fā)店 wait(sofa); /等待沙發(fā) leave_stand_section(); /離開站席區(qū) si

26、gnal(stand_capacity); sit_on_sofa(); /坐在沙發(fā)上 wait(barber_chair); /等待理發(fā)椅 get_up_sofa(); /離開沙發(fā) signal(sofa); wait(mutex1); sit_on_barberchair(); /坐到理發(fā)椅上 signal(customer_ready); barber_number=dequeue(); /得到理發(fā)師編號(hào) signal(mutex1); wait(finishedbarber_number); /等待理發(fā)結(jié)束 pay(); /付款 signal(payment); /付款 wait(receipt); /等待收據(jù) get_up_barberchair(); /離開理發(fā)椅 signal(leave_barberchair); /發(fā)出離開理發(fā)椅信號(hào) exit_shop(); /了離開理發(fā)店 void barber(int i) while(true) wait(mutex1); enqueue(i); /將該理發(fā)師的編號(hào)加入隊(duì)列 signal(mutex1); wait(customer_ready); /等待顧