信號量的PV操作例題

1、？信號量的PV操作是如何定義的？試說明信號量的PV操作的物理意義。參考答案：P（S）：將信號量S減1，若結(jié)果大于或等于0，則該進程繼續(xù)執(zhí)行；若結(jié)果小于0，則該進程被阻塞，并將其插入到該信號量的等待隊列中，然后轉(zhuǎn)去調(diào)度另一進程。V（S）：將信號量S加1，若結(jié)果大于0，則該進程繼續(xù)執(zhí)行；若結(jié)果小于或等于0，則從該信號量的等待隊列中移出一個進程，使其從阻塞狀態(tài)變?yōu)榫途w狀態(tài)，并插入到就緒隊列中，然后返回當(dāng)前進程繼續(xù)執(zhí)行。PV操作的物理含義：信號量S值的大小表示某類資源的數(shù)量。當(dāng)S>0時，其值表示當(dāng)前可供分配的資源數(shù)目；當(dāng)S<0時，其絕對值表示S信號量的等待隊列中的進程數(shù)目。每執(zhí)行一次P操作

2、，S值減1，表示請求分配一個資源，若S0，表示可以為進程分配資源，即允許進程進入其臨界區(qū)；若S<0，表示已沒有資源可供分配，申請資源的進程被阻塞，并插入S的等待隊列中，S的絕對值表示等待隊列中進程的數(shù)目，此時CPU將重新進行調(diào)度。每執(zhí)行一次V操作，S值加1，表示釋放一個資源，若S>0，表示等待隊列為空；若S0，則表示等待隊列中有因申請不到相應(yīng)資源而被阻塞的進程，于是喚醒其中一個進程，并將其插入就緒隊列。無論以上哪種情況，執(zhí)行V操作的進程都可繼續(xù)運行。1、 設(shè)公共汽車上，司機和售票員的活動分別是：司機的活動：啟動車輛； 正常行車； 到站停車；售票員的活動： 關(guān)車門； 售票； 開車門；

3、 在汽車不斷地到站、停車、行駛過程中，這兩個活動有什么同步關(guān)系？用P、V操作實現(xiàn)它們的同步。 設(shè)兩個信號量S和C，初值為S0；C0；司機： L1： 正常行車 售票員： L2： 售票到站停車 P（S）V（S） 開車門P（C） 關(guān)車門啟動開車 V（C）GO TO L1 GO TO L22、請用PV操作實現(xiàn)他們之間的同步關(guān)系： （1）桌上一個盤子，只能放一只水果。爸爸放蘋果，媽媽放桔子，兒子只吃桔子，女兒只吃蘋果。（2）桌上一個盤子，只能放一只水果。爸爸放蘋果，媽媽放桔子，兒子吃桔子、蘋果。參考答案：第一步：確定進程4個進程Father（爸爸）、Mother（媽媽）、Son（兒子）、Daughter

4、（女兒）Father進程：l 將蘋果放入盤中Mother進程：l 將桔子放入盤中Son進程：l 從盤中取出桔子l 吃桔子Daughter進程：l 從盤中取出蘋果l 吃蘋果第二步：確定進程的同步、互斥關(guān)系l 同步：Father當(dāng)盤中無水果時，才可以將蘋果放入盤中l(wèi) 同步：Mother當(dāng)盤中無水果時，才可以將桔子放入盤中l(wèi) 同步：Son當(dāng)盤中有桔子時，才可以從盤中取出桔子l 同步：Daughter當(dāng)盤中有蘋果時，才可以從盤中取出蘋果第三步：設(shè)置信號量l 盤中無水果，Sp，初值1l 盤中有桔子，So，初值0l 盤中有蘋果，Sa，初值0第四步：用偽代碼描述begin Sp,So,Sa：semaphor

5、e; Sp :=1; So :=0; Sa :=0;cobeginFather ( );Mother ( );Son ( );Daughter ( );coend;end;process Father ( ) begin L1: P（Sp）; 將蘋果放入盤中； V（Sa）; goto L1; end;process Mother ( ) begin L2: P（Sp）; 將桔子放入盤中； V（So）; goto L2; end;process Son ( ) begin L3: P（So）; 從盤中取出桔子； V（Sp） 吃桔子； goto L3； end;process Daughter (

6、 ) begin L4: P（Sa）; 從盤中取出蘋果； V（Sp） 吃蘋果； goto L4； end;（2）第一步：確定進程3個進程Father（爸爸）、Mother（媽媽）、Son（兒子）Father進程：l 將蘋果放入盤中Mother進程：l 將桔子放入盤中Son進程：l 從盤中取出水果（桔子或蘋果）l 吃水果（桔子或蘋果）第二步：確定進程的同步、互斥關(guān)系l 同步：Father當(dāng)盤中無水果時，才可以將蘋果放入盤中l(wèi) 同步：Mother當(dāng)盤中無水果時，才可以將桔子放入盤中l(wèi) 同步：Son當(dāng)盤中有水果（桔子或蘋果）時，才可以從盤中取出水果第三步：設(shè)置信號量l 盤中無水果，empty，初值1

7、l 盤中有水果（桔子或蘋果），full，初值0第四步：用偽代碼描述begin empty, full：semaphore; empty:=1; full :=0;cobeginFather ( );Mother ( );Son ( );coend;end;process Father ( ) begin L1: P（empty）; 將蘋果放入盤中； V（full）; goto L1; end;process Mother ( ) begin L2: P（empty）; 將桔子放入盤中； V（full）; goto L2; end;process Son ( ) begin L3: P（full

8、）; 從盤中取出水果; V（empty）; 吃水果; goto L3； end;3. 某工廠有一個可以存放設(shè)備的倉庫，總共可以存放10臺設(shè)備。生產(chǎn)的每一臺設(shè)備都必須入庫，銷售部門可從倉庫提出設(shè)備供應(yīng)客戶。設(shè)備的入庫和出庫都必須借助運輸工具。現(xiàn)只有一臺運輸工具，每次只能運輸一臺設(shè)備。請設(shè)計一個能協(xié)調(diào)工作的自動調(diào)度管理系統(tǒng)。參考答案：第一步：確定進程可以為入庫（Pin）和出庫（Pout）各設(shè)置一個進程Pin進程：l 生產(chǎn)了一臺設(shè)備l 使用運輸工具入庫Pout進程：l 使用運輸工具出庫l 提出設(shè)備供應(yīng)客戶第二步：確定進程的同步、互斥關(guān)系l 同步：當(dāng)倉庫中有空余位置存放設(shè)備時，設(shè)備才可以入庫l 同步：

9、當(dāng)倉庫中有存放的設(shè)備時，設(shè)備才可以出庫l 互斥：運輸工具是臨界資源，要互斥訪問第三步：設(shè)置信號量l 倉庫中有空余位置數(shù)量，empty，初值10l 倉庫中有存放的設(shè)備數(shù)量，full，初值 0l 為運輸工具設(shè)置互斥信號量S，初值 1，表示當(dāng)前可用第四步：用偽代碼描述begin empty, full, S：semaphore; empty := 10;full := 0;S := 1;cobeginPin ();Pout ();coend;end;process Pin ( ) begin L1: 生產(chǎn)了一臺設(shè)備 ;P（empty）; P (S);使用運輸工具入庫;V （S）; V（full）;

10、goto L1; end;process Pout ( ) beginL2: P（full）;P (S);使用運輸工具出庫;V （S）;V（empty）;提出設(shè)備供應(yīng)客戶; goto L2; end;4、寫者優(yōu)先的“讀者寫者”問題：1）共享讀2）互斥寫、讀寫互斥3）寫者優(yōu)先于讀者（一旦有寫者，則后續(xù)讀者必須等待，喚醒時優(yōu)先考慮寫者）wmutex:semaphore=1 /讀者與寫者之間、寫者與寫者之間互斥使用共享數(shù)據(jù)S：semaphore=1 /當(dāng)至少有一個寫者準備訪問共享數(shù)據(jù)時，它可使后續(xù)的讀者等待寫完成S2：semaphor1 /阻塞第二個以后的等待讀者readcount,writecou

11、nt: semaphore = 0,0; /當(dāng)前讀者數(shù)量、寫者數(shù)量mutex1 :semaphore = 1 /多個讀者互斥使用readcountmutex2 :semaphore = 1 /多個寫者互斥使用writecountCobegin: Reader: begin Repeat Wait（S2）； wait(S); wait(mutex1) if readcount=0 then wait(wmutex); readcount+; signal (mutex1); signal(S); signal（S2）； reading wait(mutex1); readcount-; if r

12、eadcount=0 then signal(wmutex); signal(mutex1); until false; begin; writer: begin repeat; wait(mutex2); if writecount=0 then wait(S); writecount+; signal （mutex2）; wait(wmutex); writing signal(wmutex); wait(mutex2); writecount-;if writecount=0 then signal(S); signal （mutex2）; until false; end; coend

13、;5、有一個倉庫，可以存放A、B兩種產(chǎn)品，但要求： 每次只能存入一種產(chǎn)品（A或B）； A產(chǎn)品數(shù)量B產(chǎn)品數(shù)量<M； B產(chǎn)品數(shù)量A產(chǎn)品數(shù)量<N；其中M、N是正整數(shù)，使用P、V操作描述產(chǎn)品A與產(chǎn)品B的入庫過程。Mutex,Sa,Sb: Semaphore;Mutex =1;Sa=M-1;Sb=N-1;CoBegin: Process PA: Begin Loop: P(Sa); P(Mutex); 產(chǎn)品A入庫； V(Mutex); V(Sb); Goto Loop; End; Process PB: Begin Loop: P(Sb); P(Mutex); 產(chǎn)品B入庫； V(Mutex)

14、; V(Sa); Goto Loop; End;CoEnd; 5、進程A1、A2、An1通過m個緩沖區(qū)向進程B1、B2Bn2不斷地發(fā)送消息。發(fā)送和接收工作遵循如下規(guī)則：（1） 每個發(fā)送進程一次發(fā)送一個消息，寫入一個緩沖區(qū)，緩沖區(qū)大小等于消息長度；（2） 對每一個消息，B1，B2，Bn都必須接收一次，讀入各自的數(shù)據(jù)區(qū)內(nèi)；（3）m個緩沖區(qū)都滿時，發(fā)送進程等待；沒有可讀的消息時，接收進程等待。解答：本題是生產(chǎn)者消費者問題的一個變形，一組生產(chǎn)者A1，A2，.An1和一組消費者B1，B2，Bn2公用m個緩沖區(qū)，每個緩沖區(qū)只要寫一次，但需要讀n2次，因此，我們可以把這一組緩沖區(qū)看成n2組緩沖區(qū)，每個發(fā)送者

15、需要同時寫n2組緩沖區(qū)，而每一個接收者只需讀它自己對應(yīng)的那組緩沖區(qū)中的對應(yīng)單元。 Mutex,emptyn2,fulln2:semaphore; Mutex=1; /多進程互斥使用緩沖區(qū)empty0,1,n2=m,m,m;full0,1,.n2=0,0,0;int I;Cobegin: Process Ai Begin: Loop:Int I;For ( I=0; I<n2; I+) P (emptyI);P(Mutex);將消息放入緩沖區(qū)；v(Mutex);for( I=0; I <n2; I+) v(fullI);Goto Loop;End;Process BiBegin:Lo

16、op: P (fullI); P(Mutex); 從消息緩沖區(qū)取出消息； v(Mutex); v(emptyI);Goto Loop;End; CoEnd;6、理發(fā)師問題：一個理發(fā)店有N張沙發(fā)和一張理發(fā)椅，沒有顧客要理發(fā)時，理發(fā)師便去睡覺；當(dāng)一個顧客走進理發(fā)店時，如果所有的沙發(fā)都已被占用，他便離開理發(fā)店；否則，如果理發(fā)師正在為其他顧客理發(fā)，則該顧客就找一張空沙發(fā)坐下等待；如果理發(fā)師因無顧客正在睡覺，則由新到的顧客喚醒理發(fā)師為其理發(fā)。在理發(fā)完成后，顧客必須付費，直到理發(fā)師收費后才能離開理發(fā)店。使用信號量實現(xiàn)這一同步問題。解答：為解決上述問題，需要設(shè)置一個整形變量count用來對理發(fā)店中的顧客進行

17、計數(shù)，再設(shè)置7個信號量：mutex用來實現(xiàn)顧客進程對count變量的互斥訪問，其初值為1；sofa是對應(yīng)于等候室中N張沙發(fā)的資源信號量，其初值為N；empty表示是否有空閑的理發(fā)椅，其初值為1；full表示理發(fā)椅上是否坐有等待理發(fā)的顧客，其初值為0；cut用來等待理發(fā)的完成，其初值為0；payment用來等待付費，其初值為0；receipt用來等待收費，其初值為0。Int count =0;Mutex,sofa,empty,full,cut,payment,receipt: semaphore =1,N,1,0,0,0,0;CoBegin:Process Guest:Begin: P (mut

18、ex); If(count>N) then v(mutex); exit shop; else count +; if ( count >1)then p(sofa); sit on sofa; p(empty); get up from sofa; v(sofa); else /count=1 p(empty); sit on the baber_chair; v(full); p (cut); pay; v(payment); p(receipt); get up from the baber_chair; v(empty); p(mutex) count-; v(mutex)

19、; exit shop; End; Process Barber: Begin Loop: P(full); Cut hair; V(cut); P(payment); Accept payment; V(receipt); Goto Loop; CoEnd;7、一個海底隧道中只有一個車道，規(guī)定同一個方向的可以連續(xù)過隧道；某方向有列車過隧道時，另一個方向的列車就要等待，現(xiàn)在東岸和西岸都有列車要過隧道，如果把每個過隧道的列車看作一個進程，為保證安全，使用P、V操作實現(xiàn)正確管理。8、如果系統(tǒng)中有N個進程， 運行進程最多幾個，最少幾個？ 就緒進程最多幾個，最少幾個？ 等待進程最多幾個，最少幾個？解答

20、： 運行進程最多1個，最少0個； 就緒進程最多N-1個，最少0個； 等待進程最多N個，最少0個；12、假設(shè)有三個并發(fā)進程P，Q，R，其中P負責(zé)從輸入設(shè)備上讀入信息并傳送給Q，Q將信息加工后傳送給R，R則負責(zé)將信息打印輸出。寫出下列條件的并發(fā)程序：（1）進程P、Q共享一個緩沖區(qū)，進程Q、R共享另一個緩沖區(qū)。（2）進程P、Q共享一個由m個緩沖區(qū)組成的緩沖池，進程Q、R共享另一個由n個緩沖區(qū)組成的緩沖池。參考答案：（1）第一步：確定進程3個進程P、Q、RP進程：l 從輸入設(shè)備上讀入信息l 將信息放入緩沖區(qū)1Q進程：l 從緩沖區(qū)1取出信息l 將信息放入緩沖區(qū)2中R進程：l 從緩沖區(qū)2取出信息l 將信息

21、打印輸出第二步：確定進程的同步、互斥關(guān)系l 同步：P當(dāng)緩存區(qū)1無數(shù)據(jù)時，才可以向緩沖區(qū)1寫入信息l 同步：Q當(dāng)緩存區(qū)1有數(shù)據(jù)時，才可以從緩沖區(qū)1讀取信息l 同步：Q當(dāng)緩存區(qū)2無數(shù)據(jù)時，才可以向緩沖區(qū)2寫入信息l 同步：R當(dāng)緩存區(qū)2有數(shù)據(jù)時，才可以從緩沖區(qū)2讀取信息第三步：設(shè)置信號量l 緩存區(qū)1無數(shù)據(jù)，empty1，初值1l 緩存區(qū)1有數(shù)據(jù)，full1，初值0l 緩存區(qū)2無數(shù)據(jù)，empty2，初值1l 緩存區(qū)2有數(shù)據(jù)，full2，初值0第四步：用偽代碼描述begin empty1,empty2,full1,full2：semaphore;empty1 :=1; empty2 :=1; full1

22、 :=0; full2 :=0;cobeginP ( );Q ( ); R ( );coend;end;process P ( )begin L1: 從輸入設(shè)備上讀入信息; P（empty1）; 將信息放入緩沖區(qū)1； V（full1）; goto L1 end;process Q ( )begin L2:P（full1）;從緩沖區(qū)1取出信息; V（empty1）; P（empty2）;將信息放入緩沖區(qū)2； V（full2）; goto L2 end;process R ( )begin L3:P（full2）;從緩沖區(qū)2取出信息; V（empty2）;將信息打印輸出 ; goto L3 ; e

23、nd;（2）第一步：確定進程3個進程P、Q、RP進程：l 從輸入設(shè)備上讀入信息l 將信息放入緩沖池1中的一個空緩沖區(qū)中Q進程：l 從緩沖池1中的一個非空緩沖區(qū)中取出信息l 將信息放入緩沖池2中的一個空緩沖區(qū)中R進程：l 從緩沖池2中的一個非空緩沖區(qū)中取出信息l 將信息打印輸出第二步：確定進程的同步、互斥關(guān)系l 同步：P當(dāng)緩沖池1中有空的緩沖區(qū)時，才可以向緩沖池1寫入信息l 同步：Q當(dāng)緩沖池1中有非空的緩沖區(qū)時，才可以從緩沖池1讀取信息l 同步：Q當(dāng)緩沖池2中有空的緩沖區(qū)時，才可以向緩沖池2寫入信息l 同步：R當(dāng)緩沖池2中有非空的緩沖區(qū)時，才可以從緩沖池2讀取信息第三步：設(shè)置信號量l 緩沖池1中

24、的空緩沖區(qū)的數(shù)量，empty1，初值ml 緩沖池1中的非空緩沖區(qū)的數(shù)量，full1，初值0l 緩沖池2中的空緩沖區(qū)的數(shù)量，empty2，初值nl 緩沖池2中的非空緩沖區(qū)的數(shù)量，full2，初值0第四步：用偽代碼描述begin empty1,empty2,full1,full2：semaphore;empty1 :=m; empty2 :=n; full1 :=0; full2 :=0;cobeginP ( );Q ( ); R ( );coend;end;process P ( )begin L1: 從輸入設(shè)備上讀入信息; P（empty1）; 將信息放入緩沖池1中的一個空緩沖區(qū)中； V（fu

25、ll1）; goto L1 end;process Q ( )begin L2:P（full1）;從緩沖池1中的一個非空緩沖區(qū)中取出信息; V（empty1）; P（empty2）;將信息放入緩沖池2中的一個空緩沖區(qū)中； V（full2）; goto L2 end;process R ( )begin L3:P（full2）;從緩沖池2中的一個非空緩沖區(qū)中取出信息; V（empty2）;將信息打印輸出 ; goto L3 ; end;13、有四個并發(fā)進程：R1，R2，W1和W2，它們共享可以存放一個數(shù)的緩沖區(qū)。進程R1每次從磁盤讀入一個數(shù)存放到緩沖區(qū)中，供進程W1打印輸出；進程R2每次從鍵盤讀

26、一個數(shù)存放到緩沖區(qū)中，供進程W2打印輸出。當(dāng)緩沖區(qū)滿時，不允許再向緩沖區(qū)中存放數(shù)據(jù)；當(dāng)緩沖區(qū)空時，不允許再從緩沖區(qū)中取出數(shù)據(jù)打印輸出。試用PV操作實現(xiàn)四個進程的協(xié)調(diào)運行。參考答案：第一步：確定進程4個進程R1、R2、W1、W2R1進程：l 從磁盤上讀入一個數(shù)l 將數(shù)存放到緩沖區(qū)中W1進程：l 將R1進程放進緩沖區(qū)中的數(shù)取出l 打印輸出R2進程：l 從鍵盤讀入一個數(shù)l 將數(shù)存放到緩沖區(qū)中W2進程：l 將R2進程放進緩沖區(qū)中的數(shù)取出l 打印輸出第二步：確定進程的同步、互斥關(guān)系l 同步：R1當(dāng)緩存區(qū)無數(shù)據(jù)時，才可以向緩沖區(qū)寫入數(shù)據(jù)l 同步：R2當(dāng)緩存區(qū)無數(shù)據(jù)時，才可以向緩沖區(qū)寫入數(shù)據(jù)l 同步：W1當(dāng)

27、緩存區(qū)中是R1寫的數(shù)據(jù)時，才可以將數(shù)據(jù)從緩沖區(qū)中讀出l 同步：W2當(dāng)緩存區(qū)中是R2寫的數(shù)據(jù)時，才可以將數(shù)據(jù)從緩沖區(qū)中讀出第三步：設(shè)置信號量l 緩存區(qū)無數(shù)據(jù)，empty，初值1l 緩存區(qū)中是R1寫的數(shù)據(jù)，full1，初值0l 緩存區(qū)中是R2寫的數(shù)據(jù)，full2，初值0第四步：用偽代碼描述begin empty, full1,full2：semaphore;empty :=1; full1 :=0; full2 :=0;cobeginR1 ( );R2 ( ); W1 ( );W2 ( );coend;end;process R1 ( )begin L1: 從磁盤上讀入一個數(shù)； P（empty）;

28、 將數(shù)存放到緩沖區(qū)中； V（full1）; goto L1 end;process R2 ( )begin L2: 從鍵盤上讀入一個數(shù)； P（empty）; 將數(shù)存放到緩沖區(qū)中； V（full2）; goto L2 end;process W1 ( )begin L3:P（full1）;將緩沖區(qū)中的數(shù)取出；V（empty）;打印輸出; goto L3 end;process W2 ( )begin L4:P（full2）;將緩沖區(qū)中的數(shù)取出；V（empty）;打印輸出; goto L4 end;15、有一個閱覽室，共有100個座位。讀者進入閱覽室時必須在入口處進行登記；離開閱覽室時必須進行注銷

29、。試用PV操作描述讀者進入/離開閱覽室的同步與互斥關(guān)系。參考答案：第一步：確定進程可以進入閱覽室的讀者可以有很多，這里設(shè)為n，即n個Reader（讀者）進程Reader進程：l 登記l 進入閱覽室l 讀書l 離開閱覽室l 注銷第二步：確定進程的同步、互斥關(guān)系l 同步：當(dāng)教室內(nèi)有空座位時，讀者才可以登記，并進入閱覽室l 互斥：同時只能有一個讀者在入口處進行登記l 互斥：同時只能有一個讀者在出口處進行注銷第三步：設(shè)置信號量l 教室內(nèi)空座位數(shù)量，seat，初值100l 為入口處進行登記設(shè)置互斥信號量Sin，初值 1，表示當(dāng)前可用l 為出口處進行注銷設(shè)置互斥信號量Sout，初值 1，表示當(dāng)前可用第四步

30、：用偽代碼描述begin Sin, Sout, seat：semaphore; seat :=100; Sin := 1; Sout := 1;cobeginprocess Reader-i ( i = 1,2,n );beginP(seat);P(Sin);登記;V(Sin);進入閱覽室;讀書;離開閱覽室;P(Sout);注銷;V(Sout);V（seat）;endcoend;end;17、設(shè)一個機票訂購系統(tǒng)有n個售票處，每個售票處通過網(wǎng)絡(luò)終端訪問系統(tǒng)的公共數(shù)據(jù)區(qū)，假定公共數(shù)據(jù)區(qū)中的一些單元Aj（j1,2,）分別存放各次航班的余票數(shù)，售票時，若某次航班還有余票，則售給乘客，否則，拒絕售票。請用信號量的PV操作實現(xiàn)各售票進程的并發(fā)執(zhí)行。解: 設(shè)Pi（i=1,2,n）表示各售票處的售票處理進程，公共數(shù)據(jù)區(qū)是多個售票進程共享的臨界資源，為其設(shè)置互斥信號量S，初值為1，表示資源可用。算法描述如下：begin S：semaphore; S :=1;cobegin process Pi(i=1,2,n) begin Ri：integer / 表示各進程執(zhí)行