第2章進(jìn)程同步演示

1、22 進(jìn)程間通信221 競(jìng)爭(zhēng)條件 并發(fā)進(jìn)程的相關(guān)性 資源共享方式：a)內(nèi)存，CPU，設(shè)備，文件，系統(tǒng)分配和協(xié)調(diào)；b)小量軟資源，共享隊(duì)列，通過(guò)手段協(xié)調(diào)。 進(jìn)程合作。1間接相互制約方式2直接相互制約方式這些關(guān)系可以歸結(jié)為兩種關(guān)系:互斥和同步?；コ猓╩utual exclusion）-共享某資源的各進(jìn)程不能同時(shí)進(jìn)行同一操作。競(jìng)爭(zhēng)條件-(race condition,書(shū)P24)即兩個(gè)或多個(gè)進(jìn)程讀寫(xiě)某些數(shù)據(jù),而最后的結(jié)果取決于進(jìn)程運(yùn)行的精確時(shí)序,就稱為競(jìng)爭(zhēng)條件。這就是為什么會(huì)產(chǎn)生與時(shí)間有關(guān)的錯(cuò)誤的原因。同步（synchronization）-關(guān)于進(jìn)程間合作時(shí)操作的時(shí)間順序的限制?；コ夂屯降膮^(qū)別:一個(gè)

2、只要不同時(shí)發(fā)生就行，誰(shuí)先誰(shuí)后看排隊(duì)、優(yōu)先級(jí);一個(gè)是動(dòng)作要有嚴(yán)格的時(shí)間順序。下面我們先討論互斥的問(wèn)題222 臨界區(qū)(Critical Section)我們把一次僅允許一個(gè)進(jìn)程使用的資源稱為臨界資源(Critical Resource)。如打印機(jī)，繪圖儀，磁帶機(jī)等，公共變量，公用表格，公用隊(duì)列等。訪問(wèn)臨界資源的那段程序稱為臨界區(qū)。它能夠從概念上分離出來(lái)，而，或叫臨界段(互斥段)。例1:有兩個(gè)進(jìn)程共享一個(gè)變量count。P1:R1:=COUNT;| R1:=R1+1;| COUNT:=R1;|P2:R2:=COUNT;| R2:=R2+1;| COUNT:=R2;此時(shí)兩個(gè)進(jìn)程各自對(duì)count作了加操

3、作，而count增加了2。如果執(zhí)行是另一種順序。P1:R1:=COUNT;| 發(fā)生時(shí)鐘中斷P2:R2:=COUNT;|P2:R2:=R2+1;|COUNT:=R2;|P1:R1:=R1+1;|COUNT:=R1;雖然兩個(gè)進(jìn)程也各自對(duì)count作了加一操作，但count卻只增加了一。例2:兩個(gè)進(jìn)程在系統(tǒng)中共用一個(gè)緩沖隊(duì)列。如果程序順序是p1:return ptr1:=ptr;獲得第一個(gè)緩沖區(qū)的PTR ptr:=tail(ptr);指針指向下一個(gè)p2:reture ptr2:=ptr;獲得第二個(gè)緩沖區(qū)的PTRptr:=tail(ptr);指針指向第三個(gè)但如果程序順序是：p1:return ptr1

4、:=ptr;獲得第一個(gè)緩沖區(qū)的PTR發(fā)生時(shí)鐘中斷：p2:reture ptr2:=ptr;也獲得第一個(gè)緩沖區(qū)的PTRp1:ptr:=tail(ptr);指針指向第二個(gè)PTRp2:ptr:=tail(ptr);指針指向第三個(gè)PTR執(zhí)行結(jié)果造成p1，p2共得一個(gè)緩沖區(qū)，第二個(gè)緩沖區(qū)丟失，第三個(gè)緩沖區(qū)成為首部。設(shè)置準(zhǔn)則:P24 任何兩個(gè)進(jìn)程不能同時(shí)處于臨界區(qū)。 不應(yīng)對(duì)CPU的速度和數(shù)目作任何假設(shè)。 臨界區(qū)外的進(jìn)程不得阻塞其它進(jìn)程。 不得使進(jìn)程在臨界區(qū)外無(wú)休止地等待。223 忙等待的互斥2231 關(guān)閉中斷2332 設(shè)置鎖變量在測(cè)試與設(shè)置方法中，設(shè)置個(gè)變量w來(lái)代表某種臨界資源的狀態(tài)，因此w又成為鎖或鎖位

5、。w=0 表示資源空閑(可用)w=1 表示資源已被使用關(guān)鎖原語(yǔ): lock(w)；關(guān)中斷L:if w=1 then goto L else w:=1開(kāi)中斷開(kāi)鎖原語(yǔ): unlock(w)；w:=0；大家注意:由于原語(yǔ)執(zhí)行時(shí)不能中斷?？紤]三個(gè)進(jìn)程P1：P2：P3：lock(w);lock(w);lock(w);執(zhí)行臨界段1；執(zhí)行臨界段2；執(zhí)行臨界段3；unlock(w);unlock(w);unlock(w);2233 嚴(yán)格輪換法（書(shū)P25）2234 Peterson解決方案（書(shū)P26）2235 TSL指令例1:IBM360/370采用匯編實(shí)現(xiàn)LOCK(X)TSX 測(cè)鎖位并置1，送PSW(條件碼)

6、BNZ -4 不為0，往回跳4字節(jié)，繼續(xù)執(zhí)行TSX。UNLOCK(X)MOI X，00例2:Intel 8086/8088 匯編指令也能實(shí)現(xiàn)鎖原語(yǔ)。LOCK PROC FAR匯編語(yǔ)言的過(guò)程保留字MOV AL，1;將1送入AL寄存器AGAIN:XCHG AL，F(xiàn)LAG ;交換指令，狀態(tài)進(jìn)入AL，F(xiàn)LAG=1關(guān)鎖TEST AL，AL;測(cè)試AL，看狀態(tài)是什么JNZ AGAIN;AL=1時(shí)回跳(FLAG=1)RET;返回主程序UNLOCK PROC FAR;開(kāi)鎖MOV FLAG ，0;FLAG=0RET;修改后的關(guān)鎖和開(kāi)鎖原語(yǔ)為:lock w:begin if w=1 then begin block

7、(n); insert(wL，n); scheduler end else w:=1end;unlock w:begin if wn then begin remove(wL，q); states(q):=readya; insert(RL，q) end; w:=0end;225 信號(hào)量(semaphores machini)一、信號(hào)量信號(hào)量是表示資源的物理實(shí)體，是一個(gè)與隊(duì)列有關(guān)的整型變量。在類pascal中，將它表示為一個(gè)記錄。type semaphore=record val:integer;值域 L:pointer;指針域end;信號(hào)量實(shí)際是一個(gè)計(jì)數(shù)鎖(廣義鎖)，它的值只能由P、V操作來(lái)

8、改變。二、P、V操作(計(jì)數(shù)信號(hào)量機(jī)制)procedure p(s)；var s:semphore;beginLock out interrupt;關(guān)中斷 s.value=s.value-1; if s.value0 then beginstates(q):=blockeda;活動(dòng)阻塞insert(wL，q);插入等待隊(duì)列unlock interrupt;開(kāi)中斷scheduler; 重新分配CPUend else unlock interrupt;開(kāi)中斷end；procedure v(s)var s:semaphore;begin lock out interrupt;關(guān)中斷 s.value:=

9、s.value+1; if s.value=0等待隊(duì)列不空 then beginremove(wl，r);從wl隊(duì)中摘下rstates(r):=readya;活動(dòng)就緒insert(rl，r);插入就緒隊(duì)列l(wèi)ength(rl):=length(rl)+1endl; unlock interrupt開(kāi)中斷end;P、V操作必須是原語(yǔ)，執(zhí)行期間不可分割。P、V操作的物理意義：P操作:信號(hào)量s可以看成一個(gè)資源量。例如有幾臺(tái)打印機(jī)，即信號(hào)量 s.value初值=n，如果有進(jìn)程對(duì)s進(jìn)行P操作就是申請(qǐng)?jiān)撡Y源的一個(gè)單位(申請(qǐng)一臺(tái)打印機(jī))，所以進(jìn)行一次P操作，s.value要減1(減少一個(gè)資源)。進(jìn)行到最后S分

10、配完畢(s.value=0)，再有進(jìn)程申請(qǐng)資源(進(jìn)行P(s)，使s.value0 其值為剩余(尚有)資源s.value=0 無(wú)資源，無(wú)等待進(jìn)程s.value0 s.value的絕對(duì)值即為等待該資源的進(jìn)程數(shù)。V操作:表示釋放資源，s.value=s.value+1。如果s.value=1 then x:=x-1; write(x); V(mutex)end;procedure t2(x); var x:integer; begin P(mutex);read(x);if x=1 then x:=x-1;write(x);V(mutex);end;Hansen提出并行PASCAL語(yǔ)言之前，Dijk

11、stra提出： COBEGIN S1;S2;S3；;Sn COENDP、V操作在這里起到了lock和unlock的作用，實(shí)現(xiàn)了互斥。2利用信號(hào)量實(shí)現(xiàn)進(jìn)程同步例1:有一個(gè)緩沖區(qū)，有計(jì)算進(jìn)程和打印進(jìn)程同時(shí)并行工作，計(jì)算進(jìn)程將結(jié)果放在緩沖區(qū)，放之前要申請(qǐng)緩沖區(qū)空，打印進(jìn)程負(fù)責(zé)把結(jié)果打印出來(lái)，做之前要申請(qǐng)緩沖區(qū)滿，這是一個(gè)同步問(wèn)題，初始，一定要計(jì)算進(jìn)程先動(dòng)作，先緩沖區(qū)寫(xiě)入，然后再打印進(jìn)程工作。在緩沖區(qū)滿時(shí)，計(jì)算進(jìn)程不能寫(xiě)。在緩沖區(qū)空時(shí)，打印進(jìn)程不能讀。打印進(jìn)程計(jì)算進(jìn)程 緩沖區(qū)我們可以設(shè)空、滿信號(hào)量 empty:=1； full:=0；P計(jì)算：P打?。篟epeatRepeatP(empty);P(ful

12、l); 寫(xiě)入數(shù)據(jù)；輸出數(shù)據(jù)；V(full);V(empty);Until false;Until false;用P、V操作，實(shí)現(xiàn)了題意要求*生產(chǎn)者-消費(fèi)者問(wèn)題(producer-consumer problems)生產(chǎn)者和消費(fèi)者問(wèn)題，是從操作系統(tǒng)中許多實(shí)際同步問(wèn)題中抽象出來(lái)的具有代表性的問(wèn)題。它反映了操作系統(tǒng)中典型的同步例子。生產(chǎn)者進(jìn)程生產(chǎn)信息，例如它可以是計(jì)算進(jìn)程;消費(fèi)者進(jìn)程使用信息，它可以是輸出打印進(jìn)程。由于生產(chǎn)者和消費(fèi)者進(jìn)程彼此獨(dú)立，且運(yùn)行速度不確定，可能出現(xiàn)生產(chǎn)者已生產(chǎn)了信息，而消費(fèi)者卻沒(méi)有來(lái)得及接受的情況，為此引入了一個(gè)或若干個(gè)存儲(chǔ)單元組成的臨時(shí)存儲(chǔ)區(qū)，以便存放生產(chǎn)者所產(chǎn)生的信息，以

13、平滑進(jìn)程間由于速度不確定所帶來(lái)的問(wèn)題。這個(gè)臨時(shí)存儲(chǔ)區(qū)叫做緩沖區(qū)，通常用一維數(shù)組來(lái)抽象。例2：如果圖變成如下 S TGETCOPYPUTGET、COPY、PUT三進(jìn)程共用兩個(gè)緩沖區(qū)S、T(其大小為每次存放一個(gè)記錄)。GET進(jìn)程負(fù)責(zé)不斷把輸入記錄送入緩沖區(qū)S中，COPY進(jìn)程負(fù)責(zé)從緩沖區(qū)S中取出記錄復(fù)制到緩沖區(qū)T中，PUT進(jìn)程負(fù)責(zé)把記錄從緩沖區(qū)T中取出打印，試用P、V操作實(shí)現(xiàn)這三個(gè)進(jìn)程之間的同步。例3：有窮緩沖區(qū)生產(chǎn)者和消費(fèi)者問(wèn)題（P30-圖2-11）設(shè)有多個(gè)生產(chǎn)者和消費(fèi)者，他們共享一個(gè)具有n個(gè)存儲(chǔ)單元的有窮緩沖區(qū)0n-1。inout滿空指針in指出空緩沖區(qū)頭，out指出滿緩沖區(qū)頭，每當(dāng)有生產(chǎn)者要求

14、一個(gè)空緩沖區(qū)，則分給其指針in指出的空緩沖區(qū)，同時(shí)指針in按箭頭方向移動(dòng)一個(gè)位置，消費(fèi)者要求滿緩沖區(qū)操作，也類似移動(dòng)out指針，分一個(gè)滿緩沖區(qū)。為使生產(chǎn)者進(jìn)程和消費(fèi)者進(jìn)程協(xié)調(diào)合作，它們應(yīng)遵循以下規(guī)則:1)只要緩沖區(qū)有空閑單元，生產(chǎn)者都可存放信息，當(dāng)緩沖區(qū)滿時(shí)，任一生產(chǎn)者提出要求時(shí)，都必須等待。2)只要緩沖區(qū)中有信息可取，消費(fèi)者都可以從緩沖區(qū)中取用信息，當(dāng)緩沖區(qū)空時(shí)，任一消費(fèi)者取用信息都必須等待。3)生產(chǎn)者們和消費(fèi)者們不能同時(shí)讀寫(xiě)緩沖區(qū)。設(shè)緩沖區(qū)編號(hào)為0n-1，設(shè)三個(gè)信號(hào)量。var mutex，empty，full:semphore:=1，n，0;buffer:array 0.n-1of mas

15、sege;in，out:0.n-1;begin cobeginproducer:begin repeat produce a new message m;p(empty);p(mutex);buffer(in):=m;in:=(in+1)mod n;v(mutex);v(full); until falseend;consumer:begin repeatp(full);p(mutex);in:=buffer(out);out:=(out+1)mod n;v(mutex);v(empty);consume message m until falseend; coendend.環(huán)型緩沖區(qū)機(jī)構(gòu)適用

16、于實(shí)現(xiàn)操作系統(tǒng)中的假脫機(jī)控制，經(jīng)常使用的是spooling系統(tǒng)。生產(chǎn)者實(shí)際是假脫機(jī)入口進(jìn)程，緩沖區(qū)大小要使入口進(jìn)程和出口進(jìn)程速度匹配。私用信號(hào)量（Private Semaphore）。一個(gè)進(jìn)程的私用信號(hào)量是從制約它的進(jìn)程發(fā)送來(lái)的、使它能繼續(xù)執(zhí)行條件所需的消息。與私用信號(hào)量相對(duì)應(yīng)，我們稱互斥信號(hào)量為公用信號(hào)量。例4：利用信號(hào)量描述前驅(qū)關(guān)系為了實(shí)現(xiàn)這種前驅(qū)關(guān)系，我們只需為進(jìn)程P1，P2，P6各設(shè)置一個(gè)私用信號(hào)量a，b，c，d，e，作為同步信號(hào)，賦初值為0。S1S2S3S4S5S6begin cobeginp1:begin S1;v(s1);v(s1); end;p2:begin p(s1); S2

17、; v(s2);v(s2); end;p3:begin p(s1); S3; v(s3); end;p4:begin p(s2); S4; v(s4); end;p5:begin p(s2); S5; v(s5); end;p6:begin p(s4); p(s5); p(s3); S6; end;在考慮進(jìn)程同步問(wèn)題時(shí)，要注意到幾個(gè)問(wèn)題: 分析有幾個(gè)臨界區(qū)，是否需要公用互斥信號(hào)量，初值是多少（資源量）。 考慮幾個(gè)進(jìn)程如何同步，如何通過(guò)信號(hào)量互通消息，初值是多少。如何用信號(hào)量作為進(jìn)程阻塞和喚醒的機(jī)構(gòu)。a）在資源分配和釋放情況中，進(jìn)程所等待的事件是其所要求的資源被其它進(jìn)程釋放出來(lái)成為可用。這時(shí)信號(hào)

18、量代表該資源的數(shù)量，而信號(hào)量上的P、V操作可以成為資源分配和釋放的機(jī)構(gòu)。b）在進(jìn)程間相互協(xié)同情況下，使進(jìn)程等待某事件來(lái)控制其執(zhí)行順序，此時(shí)進(jìn)程所等待的事件主要是等待相關(guān)的協(xié)作進(jìn)程完成某個(gè)操作，當(dāng)進(jìn)程在等待這類事件時(shí)，最好將它自己阻塞，以等待該事件的發(fā)生或完成。當(dāng)一個(gè)相關(guān)的協(xié)同進(jìn)程完成了它的操作后，要喚醒等待它的進(jìn)程。于是它可以用V操作作為喚醒工具。例:兩個(gè)協(xié)同進(jìn)程A和B，進(jìn)程A要等待進(jìn)程B的計(jì)算結(jié)果，則這兩個(gè)進(jìn)程的執(zhí)行如下:進(jìn)程A:進(jìn)行計(jì)算P(Bi);阻塞自己等B的結(jié)果繼續(xù)計(jì)算進(jìn)程B:進(jìn)行計(jì)算;V(Bi);喚醒Ac) 在進(jìn)程同步中，V操作次序無(wú)關(guān)緊要，而P操作順序不能顛倒，它會(huì)引起死鎖（死鎖時(shí)

19、會(huì)分析）。d) P、V必須配對(duì)。若多一個(gè)P操作，必然會(huì)有進(jìn)程總在阻塞隊(duì)列中等待，永遠(yuǎn)得不到喚醒；若多一個(gè)V操作，就會(huì)兩個(gè)進(jìn)程同時(shí)進(jìn)入臨界區(qū)的可能，資源已用完，而某個(gè)進(jìn)程仍進(jìn)一步獲得資源而出錯(cuò)。對(duì)信號(hào)量及P、V操作的評(píng)述：從以上例舉的幾個(gè)例子中可見(jiàn)，信號(hào)量可用來(lái)實(shí)現(xiàn)同步和互斥。(1)用信號(hào)量實(shí)現(xiàn)互斥時(shí)，各進(jìn)程中使用臨界資源的那段程序代碼(臨界區(qū))的開(kāi)始和末尾，分別用P(s)和V(s)括起來(lái)，格式為Pi:p(s); Pj: p(s); Csi; csj; v(s) ; v(s); (2)當(dāng)信號(hào)量用來(lái)實(shí)現(xiàn)同步時(shí)，伙伴進(jìn)程間要通過(guò)緩沖區(qū)來(lái)存放要交換的信息，消費(fèi)者在使用信息之前，通過(guò)p(s)詢問(wèn)緩沖區(qū)中

20、是否有信息可取用，若無(wú)則阻塞在相應(yīng)隊(duì)列中等待。而生產(chǎn)者生產(chǎn)出信息后，要通過(guò)V(s)通知消費(fèi)者來(lái)取信息。因此在協(xié)作進(jìn)程間p(s)，v(s)通常按如下方式安排：生產(chǎn)者： 生產(chǎn)信息 V（S）消費(fèi)者： P（S） 消費(fèi)信息發(fā)消息 (3)并行系統(tǒng)中的進(jìn)程相互依賴、相互制約關(guān)系，表現(xiàn)為進(jìn)程間的互斥與同步關(guān)系。為了實(shí)現(xiàn)互斥與同步，進(jìn)程間不僅要傳遞信息，而且為了傳遞信息還要通過(guò)公共變量s進(jìn)行通訊聯(lián)系。因此通常也把同步與互斥叫做進(jìn)程通訊。 (4)P、V存在許多不足之處： 必須配對(duì)，p次序不能顛倒 P、V分散在共享同一資源的各進(jìn)程中，增加程序復(fù)雜性，各進(jìn)程互相依賴，獨(dú)立性差。容易死鎖。227 管程(monitor)

21、-P32一、管程定義Hansen為管程所下的定義是：一個(gè)管程定義了一個(gè)數(shù)據(jù)結(jié)構(gòu)和能為并發(fā)進(jìn)程所執(zhí)行（在該數(shù)據(jù)結(jié)構(gòu)上）的一組操作，這組操作能同步進(jìn)程和改變管程中的數(shù)據(jù)。管程由4部分組成1管程名 monitor monitor-name2數(shù)據(jù)說(shuō)明部分:描述共享資源的數(shù)據(jù)結(jié)構(gòu)。它們是局部于該管程的局部變量。3若干過(guò)程:管程中的過(guò)程是為了分配或使用共享資源，并在相應(yīng)數(shù)據(jù)結(jié)構(gòu)上進(jìn)行操作所必須的程序代碼。procedure (，形參，)begin過(guò)程體end;4對(duì)變量賦初值的語(yǔ)句。管程能使并發(fā)進(jìn)程同步，并在它們之間傳送數(shù)據(jù)。管程也能控制競(jìng)爭(zhēng)，使共享物理資源的各個(gè)進(jìn)程遵循所應(yīng)的次序。二、實(shí)現(xiàn)管程的基本原則。

22、1一個(gè)管程管理一個(gè)或一組共享資源。2一個(gè)進(jìn)程請(qǐng)求使用資源時(shí)，必須先通過(guò)調(diào)用指定的”管程入口”，才能進(jìn)入管程，然后通過(guò)管程中的過(guò)程使用資源。每一個(gè)管程入口，對(duì)應(yīng)一個(gè)對(duì)臨界資源進(jìn)行操作的過(guò)程。調(diào)用管程入口的格式為monitor-nameprocedure-name （實(shí)參）3互斥： 4、同步:進(jìn)程必須在管程外等待，因此引入了條件變量這個(gè)概念。每個(gè)獨(dú)立的條件變量是和進(jìn)程可能需要等待的不同原因相聯(lián)系。5每一條件變量名就是一個(gè)先進(jìn)先出隊(duì)或一個(gè)排隊(duì)棧。我們可以把一個(gè)緩沖區(qū)定義為一個(gè)管程，它由表示緩沖區(qū)內(nèi)容的一些共享變量組成。它還包括兩個(gè)管程過(guò)程。發(fā)送和接受。開(kāi)始初啟操作將緩沖區(qū)置空。局部于管程內(nèi)的數(shù)據(jù)結(jié)構(gòu)

23、只能被局部于管程內(nèi)的過(guò)程所訪問(wèn)。不能被管程外的過(guò)程對(duì)其進(jìn)行操作。反之，局部于管程內(nèi)的過(guò)程只能訪問(wèn)管程內(nèi)的數(shù)據(jù)結(jié)構(gòu)，因此管程相當(dāng)于圍墻一樣把共享變量(數(shù)據(jù)結(jié)構(gòu))和對(duì)它進(jìn)行的若干操作過(guò)程圍了起來(lái)。進(jìn)程要訪問(wèn)共享資源。(進(jìn)入圍墻使用某操作過(guò)程)就必須經(jīng)過(guò)管程(圍墻的門(mén))才能進(jìn)入。管程每次只允許一個(gè)進(jìn)程進(jìn)入管程內(nèi)，即互斥地訪問(wèn)共享資源。共享數(shù)據(jù)XY過(guò)程（操作）初始化代碼X 為條件變量Y 等待進(jìn)入管程的隊(duì)列例：用管程實(shí)現(xiàn)生產(chǎn)者消費(fèi)者問(wèn)題Type procedure-consumer=monitor;定義管程名var in，out，count:0.n-1;定義變量buffer:array0.n-1 of

24、message;notfull，notempty:condition;條件變量procedure entry-put(in);beginif count=n then notfull.wait;如無(wú)空緩沖區(qū)，調(diào)用wait阻塞自己，插入等候空緩沖區(qū)隊(duì)，同時(shí)以notfull為條件查有要無(wú)進(jìn)管程的消費(fèi)者進(jìn)程。buffer(in):=m;in:=(in+1) mod n;count:=count+1;count=n滿，count=0空if notempty.queue then notempty.signalend;procedure entry-get(m);beginif ountfile即把當(dāng)前

25、目錄中的文件名等信息輸出到文件file中當(dāng)另一進(jìn)程執(zhí)行命令$ws file則把file 中由ls寫(xiě)入的內(nèi)容又輸?shù)絯s中。用pipe機(jī)構(gòu)，直接寫(xiě)$ls | wc利用pipe文件作為管道，把ls命令的輸出作為wc命令的輸入，不用通過(guò)中介文件，管道的作用類似消息緩沖區(qū)通信，但不是用內(nèi)存緩沖區(qū)，而是借助文件進(jìn)行通信。4直接通信的實(shí)例-消息緩沖通信 消息緩沖通信的數(shù)據(jù)結(jié)構(gòu)(p55)所謂消息(message)，通常由消息頭和消息正文構(gòu)成，可用Pascal描述如下type msg=record msgsender 消息發(fā)送者名 msgnext 下一個(gè)消息，鏈指針 msgsize 整個(gè)消息的字節(jié)數(shù) msgte

26、xt 消息正文 end;在直接通訊情況下進(jìn)程可以調(diào)用原語(yǔ)send(p，msg) 向進(jìn)程p發(fā)送一個(gè)消息receive(q，msg) 接受來(lái)自進(jìn)程q的一個(gè)消息這一技術(shù)的基本思想是由系統(tǒng)管理一個(gè)消息緩沖池(許多緩沖區(qū))，緩沖池分成若干個(gè)緩沖區(qū)，每個(gè)緩沖區(qū)可放一個(gè)消息。當(dāng)一進(jìn)程需發(fā)送消息時(shí)，先向系統(tǒng)申請(qǐng)一緩沖區(qū)，寫(xiě)入消息后，連接到接收進(jìn)程PCB指示的消息隊(duì)列上，然后通知接收進(jìn)程。設(shè)置消息隊(duì)列的原因是因?yàn)橐粋€(gè)進(jìn)程可能在一段時(shí)間收到多個(gè)消息，而來(lái)不及處理。消息隊(duì)列的頭由接收進(jìn)程PCB中的隊(duì)列指針給出，PCB就要增加幾項(xiàng)內(nèi)容:mutex:用于消息隊(duì)列互斥訪問(wèn)的信號(hào)量。sm:表示接收消息的計(jì)數(shù)同步信號(hào)量。pm

27、:消息隊(duì)列的隊(duì)首指針mutexSmPmMsgsendmsgsizemsgtextPCB 發(fā)送和接收消息的原語(yǔ)send和read功能如下圖：循環(huán)隊(duì)操作申請(qǐng)一個(gè)消息緩和沖區(qū)發(fā)送區(qū)內(nèi)容復(fù)制到緩沖區(qū)找到到接收進(jìn)程的PCBP(mutex)把消息緩沖區(qū)鏈入接收進(jìn)程的消息鏈尾 V(Sm)V(mutex) P(Sm) P(mutex)取下Pm所指消息鏈?zhǔn)椎木彌_區(qū)，修改鏈?zhǔn)字羔槹丫彌_區(qū)中內(nèi)容全部復(fù)制到接收區(qū)V(mutex)釋放空緩沖區(qū)(a) send(b) receive23 經(jīng)典的IPC問(wèn)題231 哲學(xué)家進(jìn)餐問(wèn)題（P39）一、利用信號(hào)機(jī)制解決哲學(xué)家進(jìn)餐問(wèn)題哲學(xué)家進(jìn)餐問(wèn)題也是一個(gè)經(jīng)典的同步問(wèn)題，它是由Dijks

28、tra1965a提出并解決的。對(duì)上述問(wèn)題的一個(gè)簡(jiǎn)單的解是為每只筷子設(shè)置一個(gè)信號(hào)量，一個(gè)哲學(xué)家通過(guò)在相應(yīng)信號(hào)量上執(zhí)行p操作抓起一只筷子，通過(guò)執(zhí)行v操作放下一只筷子，5個(gè)信號(hào)量構(gòu)成如下的數(shù)組:var chopstick array0.4 of semaphore;每個(gè)信號(hào)量都置初值為1，于是哲學(xué)家們的活動(dòng)可描述如下:repeatp(forki);p(forki+1 mod 5);Eat;v(forki);v(forki+1 mod 5);think;until fale;此解雖然可以保證互斥使用筷子，但有可能產(chǎn)生死鎖，假設(shè)5個(gè)哲學(xué)家同時(shí)抓起各自左邊的筷子，于是5個(gè)信號(hào)量的值都為0，當(dāng)每一個(gè)哲學(xué)家企

29、圖拿起他右邊的筷子時(shí)，便出現(xiàn)了循環(huán)等待的局面-死鎖。為了防止死鎖的產(chǎn)生，可以有以下措施:l 至多允許4個(gè)哲學(xué)家同時(shí)坐在桌子的周圍l 當(dāng)一個(gè)哲學(xué)家左右的筷子都可用時(shí)，才允許他抓起筷子l 讓所有哲學(xué)家順序編號(hào)，對(duì)于奇數(shù)號(hào)的哲學(xué)家必須首先抓起左邊的筷子，然后抓起右邊的筷子，而對(duì)偶數(shù)的哲學(xué)家則反之。實(shí)際程序見(jiàn)書(shū)P41圖2-20二、用管程解決五個(gè)哲學(xué)家進(jìn)餐問(wèn)題:條件:(1) 相鄰兩哲學(xué)家不能同時(shí)進(jìn)餐(2) 最多只能有兩人進(jìn)餐，即最大并行性為二(3) 為排除隨機(jī)因素，規(guī)定哲學(xué)家進(jìn)餐時(shí)，先拿左筷，后拿右筷，不能同時(shí)拿起兩只筷子，餐后放筷時(shí)，也先左后右同樣順序forks(i)不是叉子狀態(tài)，而是第i位哲學(xué)家可用

30、叉子數(shù)(0，1，2)，當(dāng)fork(i)=2時(shí)才可以吃。否則等待在自己的條件變量上。type forkscontrol=monitor;var forks，right，left:array0.4 of integer; ready:array0.4 of boolean; i:integer;procedure entry pickup(var me:integer);begin if fork(me)2 then wait(ready(me); forks(right(me):=forks(right(me)-1;右叉子減1 forks(left(me):=forks(left(me)-1;左

31、叉子減1end;procedure entry putdown(var me:integer);begin forks(right(me):=forks(right(me)+1; forks(left(me):=forks(left(me)+1; if forks(right(me)=2 右邊符合條件喚醒右邊 then signal(ready(right(me); if forks(left(me)=2左邊符合條件喚醒左邊 then signal(ready(left(me);end；begin for i:=0 to 4 dobegin forks(i):=2;初值是可以吃 right(i

32、):=i+1mod 5;第i位的左、右哲學(xué)家號(hào) left(i):=i+4 mod 5; ready(i):=false;end;運(yùn)行時(shí):cobeginphilosopher 0: process(var HUNGRY:boolean);begin repeat if HUNGRY=true then begin forkscontrol.pickup(0); EATING; forkscontrol.putdown(0);end;THINKING;until false;end;philosopher 2:；philosopher 3:；philosopher 4:；philosopher 5

33、:；coend;232 讀者與寫(xiě)者問(wèn)題(readers-writers problem)一個(gè)數(shù)據(jù)集(如文件或記錄)，被幾個(gè)并發(fā)進(jìn)程共享。通常我們把讀進(jìn)程稱為讀者，而把要求修改數(shù)據(jù)的進(jìn)程稱為寫(xiě)者，顯然幾個(gè)讀者可以同時(shí)讀此數(shù)據(jù)集，不互斥也不會(huì)產(chǎn)生問(wèn)題。例如，設(shè)想一個(gè)飛機(jī)定票系統(tǒng)，大量的訂票者要查詢共享數(shù)據(jù)庫(kù)中有關(guān)飛機(jī)航班的各種信息，而各個(gè)售票臺(tái)卻要試圖讀寫(xiě)其中的數(shù)據(jù)。多個(gè)進(jìn)程同時(shí)讀是可以接受的，但如果一個(gè)進(jìn)程正在更新數(shù)據(jù)庫(kù)，則所有的其他進(jìn)程都不能訪問(wèn)數(shù)據(jù)庫(kù)，即使是讀操作也不行，它們之間必須互斥，否則將破壞此數(shù)據(jù)的完整性。1解決此問(wèn)題的最簡(jiǎn)單的方法:當(dāng)沒(méi)有寫(xiě)者時(shí)，讀者可以進(jìn)入訪問(wèn)，否則等待。var

34、rmutex，wmutex:semaphore; readcount:integer;begin rmutex:=1wmutex:=1;readcount:=0;cobegin reader:begin repeat p(rmutex);對(duì)readcount互斥修改 if readcount=0 then p(wmutex); readcount:=readcount+1; v(rmutex); 作讀操作 p(rmutex);退出讀時(shí)，互斥地將讀者計(jì)數(shù)減1 readcount:=readcount-1; if readcount=0 then v(wmutex);當(dāng)沒(méi)有讀者時(shí)，可寫(xiě) v(rmutex);until false;end;writer:begin repeat p(wmutex);