同步與互斥實(shí)例

進(jìn)程同步與互斥實(shí)例同步實(shí)例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/*多個(gè)子進(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í)例

設(shè)某臺(tái)機(jī)掛有兩個(gè)I/O通道：分別掛一臺(tái)輸入機(jī)和一臺(tái)打印機(jī)?？ㄆ瑱C(jī)上有一疊數(shù)據(jù)卡片，現(xiàn)在要把這些數(shù)據(jù)逐一輸入到緩沖區(qū)B1，然后再復(fù)制到緩沖區(qū)B2，并在打印機(jī)上打印出來。問：系統(tǒng)可設(shè)哪些進(jìn)程來完成這個(gè)任務(wù)？用P-V原語寫這些進(jìn)程的同步算法。解：由上圖可見，系統(tǒng)可設(shè)3個(gè)進(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個(gè)信號(hào)量：S1=1，S2=0，S3=1，S4=0

同步算法如下：3.理發(fā)師問題理發(fā)店里有一位理發(fā)師、一把理發(fā)椅和n把供等候理發(fā)的顧客坐的椅子如果沒有顧客，理發(fā)師便在理發(fā)椅上睡覺一個(gè)顧客到來時(shí)，它必須叫醒理發(fā)師如果理發(fā)師正在理發(fā)時(shí)又有顧客來到，則如果有空椅子可坐，就坐下來等待，否則就離開記錄型信號(hào)量解決理發(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ù)少一個(gè)*/V(barbers);/*理發(fā)師去為一個(gè)顧客理發(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();/*一個(gè)顧客坐下等理發(fā)*/end

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

(1)

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

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

申請(qǐng)打印機(jī)申請(qǐng)打印機(jī)申請(qǐng)打印機(jī)使用打印機(jī)使用打印機(jī)使用打印機(jī)

V(mutex)V(mutex)V(mutex)購物問題。某超級(jí)市場(chǎng)，可容納100個(gè)人同時(shí)購物，入口處備有籃子，每個(gè)購物者可持一個(gè)籃子入內(nèi)購物。出口處結(jié)賬，并歸還籃子（出、入口僅容納一人通過）。請(qǐng)用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ī)則過橋。為了保證過橋安全，請(qǐng)用P、V操作分別實(shí)現(xiàn)正確的管理。

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

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

P(mutex);

過橋；

V(mutex);

endprocess(W-E)j:begin

P(mutex);

過橋；

V(mutex);

end.獨(dú)木橋問題。某條河上只有一座獨(dú)木橋，以便行人過河。現(xiàn)在河的兩邊都有人要過橋，按照下面的規(guī)則過橋。為了保證過橋安全，請(qǐng)用P、V操作分別實(shí)現(xiàn)正確的管理。過橋的規(guī)則是：同一方向的可連續(xù)過橋，某方向有人過橋時(shí)另一方向的人要等待。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ù)量的黑棋子和白棋混裝在一個(gè)箱子里，先要用自動(dòng)分揀系統(tǒng)把黑棋子和白棋子分開，該系統(tǒng)由兩個(gè)并發(fā)執(zhí)行的進(jìn)程組成，系統(tǒng)功能如下：(1)進(jìn)程A專門揀黑子，進(jìn)程B專門揀白子；(2)每個(gè)進(jìn)程每次只揀一個(gè)子，當(dāng)一個(gè)進(jìn)程在揀子時(shí)不允許另一進(jìn)程去揀子；(3)當(dāng)一個(gè)進(jìn)程揀了一個(gè)子（黑或白）以后，必讓另一個(gè)進(jìn)程揀一個(gè)子（黑或白）。請(qǐng)用P、V操作管理兩個(gè)并發(fā)進(jìn)程，使其能正確實(shí)現(xiàn)上述功能。VarS1,S2:semaphore:=1,0;processA:beginrepeat P(S1);

揀黑子；

V(S2);untilfalse;

endprocessB:beginrepeat P(S2);

揀白子；

V(S1);untilfalse

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