1、信號量應用問題：1 寫出程序描述下列前趨關系。 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. 請用信號量實現4100（4人，每人100米）接力賽的同步過程。提示：前趨圖同步問題，可設4個進程，三個信號量，進程1只設V操作，進程4只設P操作，其余進程先做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設公共汽車上，司機和售票員的活動分別是： 司機： 售票員： 啟動車輛 上乘客 正常行車 關車門 到站停車 售票 開車門 下乘客 在汽車不斷地到站、停車、行駛過程中，這兩個活動有什么同步關系？請用信號量機制實現他們的同步。/-假定初始狀態為停車狀態，引入信號量Stop和Run： BEGIN semaphore Stop,Run; Stop:=Run:=0; CoBegin Driver: BEGIN Repeat Wait(Run); 啟動車輛； 正常行駛

4、； 到站停車； Signal(Stop); Until False; END; Conductor:BEGIN Repeat 上乘客； 關車門； Signal(Run); 售票； Wait(Stop); 開車門； 下乘客； Until False; END; CoEnd; END;生產者消費者問題：1 桌上有一個可以容納兩個水果的盤子，每次只能放或取一個水果。爸爸放蘋果媽媽放橘子，兩個兒子吃蘋果，兩個女兒吃橘子。試用信號量和P、V操作，編寫實現爸爸、媽媽、兒子和女兒的并發工作程序。Mutex實現互斥放或取水果。empty盤子可放水果數Apple 盤子中放的蘋果數Orange 盤子中放的橘子數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、有一個倉庫存放兩種零件A和B，最大庫容量各為m個。有一車間不斷地取A和B進行裝配，每次各取一個。為了避免零件銹蝕，遵循線入庫者先出庫的原則。有兩組供應商分別不斷地供應A和B（每次一個），為保證齊套和合理庫存，當某種零件的數量比另一種數量超過n（nm）個時，暫停對數量大的零件的進貨，集中補充數量少的零件。試用P、V操作正確實現之。 semaphore mutex=1, emptya=emptyb=m, fulla=fullb=0, sa=sb=n; main() CoBeg

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

8、fullb); p(mutex); 裝配零件; v(mutex); v(emptya); v(emptyb); 3、有一個倉庫，可以存放A和B兩種產品，倉庫的存儲空間足夠大，但要求： 每次只能存入一種產品（X或Y）； -NA產品數量-B產品數量M。 其中，N和M時正整數。 試用“存放A”、“存放B”和P、V操作描述產品A與產品B的入庫過程。A-BM說明：如果只放A不放B，則A最多可放M-1個，如果多放一個B，則可以多放一個A。B-AN說明：如果只放B不放A，則B最多可放N-1個，如果多放一個A，則可以多放一個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、多個進程共享一個文件，其中只讀文件的程值為讀者，其余只寫文件的稱為寫者。讀者可以同時讀，但寫者只能獨立地寫。 說明進程間的相互制約關系，應設置哪些信號量？ 用P、V操作寫出其同步算法；

10、修改上述算法，使得它對寫者優先，即一旦有寫者到達，后續的讀者都必須等待，而無論是否有讀者在讀文件。（該問題的又一提法：在一個飛機訂票系統中，多個用戶共享一個數據庫。多用戶同時查詢是可以接受的，但若一個用戶要訂票需更新數據庫時，其余所有用戶都不可以訪問數據庫。請畫出用戶查詢與訂票的邏輯框圖(等價于同步進程的描述的圖式表示)。為了提高寫者的優先級，增加一個信號量S，用于在寫進程到達后封鎖后續的讀者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操作實現兩方向的車過橋。本題本質上可以認為是讀者寫者問題，往同一個方向的車可以認為是讀者，往相反方向的車可以認為是寫者。但是由于橋的重量有限，增加了讀者之間的互斥。本題的臨界資源顯然是單通道的橋，首先如果橋上有向東

12、方向的車，那么向西方向的車一定不能過，如果超過4輛，同一方向的車也不能過，需要互斥。設信號量mutex，實現雙向車子互斥通行；信號量sew，swe表示由西向東與由東向西的負荷數，初值為4；整數型iew,iwe表示各方向的車子數，初值為0；siew,siwe實現對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;理發師睡覺問題：1（睡眠的理發師問題）理發店有一個等候室（其中有N把椅子）和一個理發室（一把理發椅組成）。如果沒有顧客來理發，理發時就在理發椅上睡覺，如果一個走進理發店，發現等候室的椅子都坐滿就離開理發店；如果理發師正忙于理發，那么該顧客就坐在一把空椅子上等待；若理發師正在睡覺，則顧客就喚醒他。用P、V操作寫出工作流程。 考點： 用PV原語

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

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

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

17、員的狀態，只能取1或0；Waiting 表示正在等待的顧客數；Mutex實現對waiting的互斥訪問customers, operator,mutex: semaphore;waiting: inteter;customers=0;operator=0;mutex=1;process operatorbegin loop: p(customers); 復??；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理發師問題：一個理發店有一個入口和一個出口。理發店內有一個可站5 位顧客的站席 區、4 個單人沙發、3 個理發師及其專用理發工具、一個收銀臺。新來的顧客坐在沙發上等 待；沒有空沙發時，可在站席區等待；站席區滿時，只能在入口外等待。理發師可從事理 發、收銀和休息三種活動。理發店的活動滿足下列條件： 1）休息的理發師是坐地自己專用的理發椅上，不會占用顧客的沙發； 2）處理休息狀態的理發師可為在沙發上等待時間最長的顧客理發； 3）理發

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

20、的顧客離開沙發（釋放信號量sofa）。坐到理發椅上，釋放 準備好的信號（customer_ready），獲得該理發師的編號（01 的數字）。等待理發師理 發結束（finishedbarber_number）。在離開理發椅之前付款（payment），等待收據 (receipt)，離開理發椅（leave_barberchair）。最后離開理發店。 這里需要注意幾點： a) 首先是幾個需要進行互斥處理的地方，主要包括:進入站席區、進入沙發、進入理發椅 和付款幾個地方。 b) 通過barber_chair 保證一個理發椅上最多只有一名顧客。但這也不夠，因為單憑 baber_chair 無法保證一名顧客

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

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

23、rberchair）（期間去收銀臺進行收款活動），釋放理發椅空閑信 號(barber_chair)，等待下一位顧客坐上來。 (3)cash（收銀臺）進程 等待顧客付款(payment),執行收款操作，收款操作結束，給付收據（receipt）。 信號量總表： 信號量 wait signal stand_capacity 顧客等待進入理發店 顧客離開站席區 sofa 顧客等待坐到沙發 顧客離開沙發 barber_chair 顧客等待空理發椅 理發師釋放空理發椅 customer_ready 理發師等待，直到一個顧客坐 到理發椅 顧客坐到理發椅上，給理發師 發出信號 mutex 等待理發師空閑，執行

24、理發或 收款操作 理發師執行理發或收款結束， 進入空閑狀態 mutex1 執行入隊或出隊等待 入隊或出隊結束，釋放信號 finished 顧客等待對應編號理發師理 發結束 理發師理發結束，釋放信號 leave_barberchair 理發師等待顧客離開理發椅 顧客付款完畢得到收據，離開 理發椅釋放信號 payment 收銀員等待顧客付款 顧客付款，發出信號 receipt 顧客等待收銀員收、開具收據收銀員收款結束、開具收據， 釋放信號 偽碼： 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); /等待進入理發店 enter_room(); /進入理發店 wait(sofa); /等待沙發 leave_stand_section(); /離開站席區 si

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