同步與互斥實例

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

取產(chǎn)品直到取為空

放產(chǎn)品；直到為滿；

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

GotoL1;GotoL2;

end;

end;

coend

2.實例

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

R受C的約束；C受R、P的約束；P受C的約束。設(shè)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ā)的顧客數(shù)*/CHAIRS:integer;/*為顧客準(zhǔn)備的椅子數(shù)*/customers,barbers，mutex:semaphore;customers:=0;barbers:=0;waiting:=0;mutex:=1;Processbarber;beginwhile(TRUE);/*理完一人,還有顧客嗎?*/

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

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

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

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

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

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

(1)

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

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

申請打印機(jī)申請打印機(jī)申請打印機(jī)使用打印機(jī)使用打印機(jī)使用打印機(jī)

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

進(jìn)入口處，取一只籃子；

V(mutex1);

選購商品; P(mutex2);

結(jié)賬，并歸還籃子；

V(mutex2); V(S);

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

揀黑子；

V(S2);untilfalse;

endprocessB:beginrepeat P(S2);

揀白子；

V(S1);untilfalse

end某寺廟有小、老和尚若干，有一水缸，由小和尚提水入缸供老和尚飲用。水缸可以容納10桶水，水取自同一井水。水井狹窄，每次只能容一個桶取水。水桶總數(shù)為3個。每次入、出水缸僅一桶，且不可同時進(jìn)行。試給出有關(guān)取水、入水的算法描述。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習(xí)題1.司機(jī)和售票員問題問題描述：在公共汽車上，司機(jī)和售票員的活動分別是：司機(jī)的活動：啟動車輛正常運(yùn)行到站停車售票員的活動：關(guān)車門售票開車門在汽車不斷的到站，停車，行駛過程中，這兩個活動有什么同步關(guān)系？用信號量和Ｐ，Ｖ操作實現(xiàn)．2.吸煙者問題三個吸煙者在一間房間內(nèi)，還有一個香煙供應(yīng)者。為了制造并抽掉香煙，每個吸煙者需要三樣?xùn)|西：煙草、紙和火柴。供應(yīng)者有豐富的貨物提供。三個吸煙者中，第一個有自己的煙草，第二個有自己的紙，第三個有自己的火柴。供應(yīng)者將