同步與互斥實例

進程同步與互斥實例同步實例1.經典的生產者─消費者問題消費者生產者1.經典的生產者─消費者問題varB:integer;empty:semaphore; /*可以使用的空緩沖區(qū)數*/full:semaphore; /*緩沖區(qū)內可以使用的產品數*/empty:=1;/*緩沖區(qū)內允許放入一件產品*/full:=0;/*緩沖區(qū)內沒有產品*/cobegin/*多個子進程并發(fā)執(zhí)行函數*/ProcessproducerprocessconsumerbeginbeginL1:L2: Produceaproduct;P(full); P(empty);

取產品直到取為空

放產品；直到為滿；

V(empty); V(full);Consumeaproduct;

GotoL1;GotoL2;

end;

end;

coend

2.實例

設某臺機掛有兩個I/O通道：分別掛一臺輸入機和一臺打印機?？ㄆ瑱C上有一疊數據卡片，現(xiàn)在要把這些數據逐一輸入到緩沖區(qū)B1，然后再復制到緩沖區(qū)B2，并在打印機上打印出來。問：系統(tǒng)可設哪些進程來完成這個任務？用P-V原語寫這些進程的同步算法。解：由上圖可見，系統(tǒng)可設3個進程：輸入進程、復制進程、打印進程；分別用進程R、進程C、進程P來表示。這些進程之間的相互制約關系：

R受C的約束；C受R、P的約束；P受C的約束。設4個信號量：S1=1，S2=0，S3=1，S4=0

同步算法如下：3.理發(fā)師問題理發(fā)店里有一位理發(fā)師、一把理發(fā)椅和n把供等候理發(fā)的顧客坐的椅子如果沒有顧客，理發(fā)師便在理發(fā)椅上睡覺一個顧客到來時，它必須叫醒理發(fā)師如果理發(fā)師正在理發(fā)時又有顧客來到，則如果有空椅子可坐，就坐下來等待，否則就離開記錄型信號量解決理發(fā)師問題

varwaiting:integer;/*等候理發(fā)的顧客數*/CHAIRS:integer;/*為顧客準備的椅子數*/customers,barbers，mutex:semaphore;customers:=0;barbers:=0;waiting:=0;mutex:=1;Processbarber;beginwhile(TRUE);/*理完一人,還有顧客嗎?*/

P(cutomers);/*若無顧客,理發(fā)師睡眠*/

P(mutex);/*進程互斥*/waiting:=waiting–1;/*等候顧客數少一個*/V(barbers);/*理發(fā)師去為一個顧客理發(fā)*/

V(mutex);/*開放臨界區(qū)*/cut-hair();/*正在理發(fā)*/end;processcustomerbegin

P(mutex);/*進程互斥*/ifwaiting<CHAIRSbegin/*看看有沒有空椅子*/waiting:=waiting+1;/*等候顧客數加1*/V(customers);/*必要的話喚醒理發(fā)師*/

V(mutex);/*開放臨界區(qū)*/P(barbers);/*無理發(fā)師,顧客坐著養(yǎng)神*/get-haircut();/*一個顧客坐下等理發(fā)*/end

V(mutex);/*人滿了,走吧!*/end;互斥實例有三個用戶進程A、B和C，在運行過程中都要使用系統(tǒng)中的一臺打印機輸出計算結果。試說明A、B、C進程之間存在什么樣的制約關系？為保證這三個進程能正確地打印出各自的結果，請用信號量和P、V操作寫出各自的有關申請、使用打印機的代碼。要求給出信號量的含義和初值。

(1)

A、B、C三個進程之間存在互斥的制約關系。因為打印機屬于臨界資源，必須一個進程使用完之后另一個進程才能使用。（2）mutex：用于互斥的信號量，初值為1。各進程的代碼如下：進程A進程B進程C...…......…...

P(mutex)P(mutex)P(mutex)

申請打印機申請打印機申請打印機使用打印機使用打印機使用打印機

V(mutex)V(mutex)V(mutex)購物問題。某超級市場，可容納100個人同時購物，入口處備有籃子，每個購物者可持一個籃子入內購物。出口處結賬，并歸還籃子（出、入口僅容納一人通過）。請用P、V操作完成購物同步算法。VarS,mutex1,mutex2:semaphore;S:=100;mutex1:=1;mutex2:=1processPi:begin P(S); P(mutex1);

進入口處，取一只籃子；

V(mutex1);

選購商品; P(mutex2);

結賬，并歸還籃子；

V(mutex2); V(S);

end獨木橋問題。某條河上只有一座獨木橋，以便行人過河。現(xiàn)在河的兩邊都有人要過橋，按照下面的規(guī)則過橋。為了保證過橋安全，請用P、V操作分別實現(xiàn)正確的管理。

過橋的規(guī)則是：每次只有一個人通過橋。Var

mutex:semaphore;process(E-W)i:begin

P(mutex);

過橋；

V(mutex);

endprocess(W-E)j:begin

P(mutex);

過橋；

V(mutex);

end.獨木橋問題。某條河上只有一座獨木橋，以便行人過河?，F(xiàn)在河的兩邊都有人要過橋，按照下面的規(guī)則過橋。為了保證過橋安全，請用P、V操作分別實現(xiàn)正確的管理。過橋的規(guī)則是：同一方向的可連續(xù)過橋，某方向有人過橋時另一方向的人要等待。VarS,S1,S2:semaphore;rc1,rc2:integer;S,S1,S2:=1;rc1,rc2:=0;

process(E-W)i:begin P(S1); rc1:=rc1+1; ifrc1=1thenP(S); V(S1);

過橋；

P(S1); rc1:=rc1-1; ifrc1=0thenV(S); V(S1);

endprocess(W-E)j:begin P(S2); rc2:=rc2+1; ifrc2=1thenP(S); V(S2);

過橋；

P(S2); rc2:=rc2-1; ifrc2=0thenV(S); V(S2);

end揀棋子問題。生產圍棋的工人不小心把相等數量的黑棋子和白棋混裝在一個箱子里，先要用自動分揀系統(tǒng)把黑棋子和白棋子分開，該系統(tǒng)由兩個并發(fā)執(zhí)行的進程組成，系統(tǒng)功能如下：(1)進程A專門揀黑子，進程B專門揀白子；(2)每個進程每次只揀一個子，當一個進程在揀子時不允許另一進程去揀子；(3)當一個進程揀了一個子（黑或白）以后，必讓另一個進程揀一個子（黑或白）。請用P、V操作管理兩個并發(fā)進程，使其能正確實現(xiàn)上述功能。VarS1,S2:semaphore:=1,0;processA:beginrepeat P(S1);

揀黑子；

V(S2);untilfalse;

endprocessB:beginrepeat P(S2);

揀白子；

V(S1);untilfalse

end某寺廟有小、老和尚若干，有一水缸，由小和尚提水入缸供老和尚飲用。水缸可以容納10桶水，水取自同一井水。水井狹窄，每次只能容一個桶取水。水桶總數為3個。每次入、出水缸僅一桶，且不可同時進行。試給出有關取水、入水的算法描述。Varmutex1,mutex2,empty,full,count:semaphore;mutex1:=1;mutex2:=1;empty:=10;full:=0;count:=3;process小和尚:beginrepeat

P(empty);

P(count); P(mutex1);

從井中取水；

V(mutex1); P(mutex2);

送水入水缸；

V(mutex2);

V(count);

V(full);untilfalse;

endprocess老和尚:beginrepeat

P(full);

P(count); P(mutex2);

從缸中取水；

V(mutex2);

V(empty);

V(count);untilfalse;

end習題1.司機和售票員問題問題描述：在公共汽車上，司機和售票員的活動分別是：司機的活動：啟動車輛正常運行到站停車售票員的活動：關車門售票開車門在汽車不斷的到站，停車，行駛過程中，這兩個活動有什么同步關系？用信號量和Ｐ，Ｖ操作實現(xiàn)．2.吸煙者問題三個吸煙者在一間房間內，還有一個香煙供應者。為了制造并抽掉香煙，每個吸煙者需要三樣東西：煙草、紙和火柴。供應者有豐富的貨物提供。三個吸煙者中，第一個有自己的煙草，第二個有自己的紙，第三個有自己的火柴。供應者將