第六講進(jìn)程的同步(續(xù))

1、操操作作系系統(tǒng)統(tǒng)第第 六六 講講進(jìn)進(jìn) 程程 的的 同同 步（續(xù)）步（續(xù)）操操作作系系統(tǒng)統(tǒng)例例3 3：哲學(xué)家吃通心面問題：哲學(xué)家吃通心面問題有五個(gè)哲學(xué)家圍一圓桌旁，桌中央有一盤通心面，有五個(gè)哲學(xué)家圍一圓桌旁，桌中央有一盤通心面，每人面前有一只空盤于，每兩人之間放一把叉子。每人面前有一只空盤于，每兩人之間放一把叉子。每個(gè)哲學(xué)家思考、饑餓、然后吃通心面。為了吃每個(gè)哲學(xué)家思考、饑餓、然后吃通心面。為了吃面，每個(gè)哲學(xué)家必須獲得兩把叉子，且每人只能面，每個(gè)哲學(xué)家必須獲得兩把叉子，且每人只能直接從自己左邊或右邊去取叉子直接從自己左邊或右邊去取叉子 操操作作系系統(tǒng)統(tǒng)操操作作系系統(tǒng)統(tǒng)VarVar chopsti

2、ck:array0.4 of semaphore; chopstick:array0.4 of semaphore; chopsticki chopsticki := 1; := 1;cobegincobegin process Pi / i=0,1,2,3,4, process Pi / i=0,1,2,3,4, begin begin思考；思考；P(chopstickiP(chopsticki)； P(chopstickP(chopstick (i+1)mod 5) (i+1)mod 5)； 吃通心面；吃通心面；V(chopstickiV(chopsticki)；V(chopstick(i

3、+1)mod 5)V(chopstick(i+1)mod 5)； end;end;coendcoend; ;操操作作系系統(tǒng)統(tǒng)上述解法可能出現(xiàn)永遠(yuǎn)等待，有若干辦法可避免死鎖上述解法可能出現(xiàn)永遠(yuǎn)等待，有若干辦法可避免死鎖： 至多允許四個(gè)哲學(xué)家同時(shí)拿左邊筷子；至多允許四個(gè)哲學(xué)家同時(shí)拿左邊筷子； 奇數(shù)號(hào)先取左邊的叉子，偶數(shù)號(hào)先取右邊的叉子；奇數(shù)號(hào)先取左邊的叉子，偶數(shù)號(hào)先取右邊的叉子； 每個(gè)哲學(xué)家取到手邊的兩把叉子才吃，否則一把叉每個(gè)哲學(xué)家取到手邊的兩把叉子才吃，否則一把叉 子也不取。子也不取。操操作作系系統(tǒng)統(tǒng)例例4 4：讀者寫者問題：讀者寫者問題有兩組并發(fā)進(jìn)程：讀者和寫者，共享一個(gè)文件有兩組并發(fā)進(jìn)程：

4、讀者和寫者，共享一個(gè)文件F F，要求：要求： 允許多個(gè)讀者同時(shí)執(zhí)行讀操作允許多個(gè)讀者同時(shí)執(zhí)行讀操作; ; 任一寫者在完成寫操作之前不允許其它讀者或?qū)懻呷我粚懻咴谕瓿蓪懖僮髦安辉试S其它讀者或?qū)懻?工作工作; ; 寫者執(zhí)行寫操作前，應(yīng)讓已有的寫者和讀者全部退寫者執(zhí)行寫操作前，應(yīng)讓已有的寫者和讀者全部退 出。出。操操作作系系統(tǒng)統(tǒng)為實(shí)現(xiàn)為實(shí)現(xiàn)ReaderReader與與WriterWriter進(jìn)程間在讀或?qū)憰r(shí)的互斥而設(shè)進(jìn)程間在讀或?qū)憰r(shí)的互斥而設(shè)置了一個(gè)互斥信號(hào)量置了一個(gè)互斥信號(hào)量WmutexWmutex。另外，再設(shè)置一個(gè)整型。另外，再設(shè)置一個(gè)整型變量變量ReadcountReadcount表示正在讀

5、的進(jìn)程數(shù)目。由于只要有一表示正在讀的進(jìn)程數(shù)目。由于只要有一個(gè)個(gè)ReaderReader進(jìn)程在讀，便不允許進(jìn)程在讀，便不允許WriterWriter進(jìn)程去寫。進(jìn)程去寫。因?yàn)橐驗(yàn)镽eadcount是一個(gè)可被多個(gè)是一個(gè)可被多個(gè)Reader進(jìn)程訪問的臨界進(jìn)程訪問的臨界資源，因此，應(yīng)該為它設(shè)置一個(gè)互斥信號(hào)量資源，因此，應(yīng)該為它設(shè)置一個(gè)互斥信號(hào)量rmutex。操操作作系系統(tǒng)統(tǒng) 因此，當(dāng)因此，當(dāng)Readcount=0, 表示尚無表示尚無Reader進(jìn)程在讀時(shí)，進(jìn)程在讀時(shí)，Reader進(jìn)程才需要執(zhí)行進(jìn)程才需要執(zhí)行wait(Wmutex)操作。若操作。若wait(Wmutex)操作成功，操作成功，Reader進(jìn)

6、程便可去讀，相應(yīng)進(jìn)程便可去讀，相應(yīng)地，做地，做Readcount+1操作。操作。 同理，僅當(dāng)同理，僅當(dāng)ReaderReader進(jìn)程在執(zhí)行了進(jìn)程在執(zhí)行了ReadcountReadcount減減1 1操作后操作后其值為其值為0 0時(shí)，才須執(zhí)行時(shí)，才須執(zhí)行signal(Wmutexsignal(Wmutex) )操作，以便讓操作，以便讓W(xué)riterWriter進(jìn)程寫。進(jìn)程寫。 操操作作系系統(tǒng)統(tǒng)var Readcountvar Readcount : integer:=0; : integer:=0; Wmutex Wmutex，RmutexRmutex: semaphore;: semaphore;

7、 Readcount Readcount := 0; / := 0; /* * 讀進(jìn)程計(jì)數(shù)讀進(jìn)程計(jì)數(shù) * */ / Wmutex Wmutex := 1; := 1; Rmutex Rmutex := 1; := 1; 操操作作系系統(tǒng)統(tǒng)procedure read; procedure write;procedure read; procedure write;begin beginbegin begin P(Rmutex); P(Wmutex P(Rmutex); P(Wmutex);); if Readcount =0 then P(Wmutex if Readcount =0 then

8、P(Wmutex) )； 寫文件寫文件; ; / /是第一個(gè)讀者是第一個(gè)讀者 V(WmutexV(Wmutex);); Readcount := Readcount Readcount := Readcount + 1; end; + 1; end; V(Rmutex V(Rmutex);/);/允許下一讀者進(jìn)入允許下一讀者進(jìn)入 讀文件；讀文件； P(RmutexP(Rmutex);); Readcount := Readcount Readcount := Readcount - 1; - 1; if Readcount = 0 then V(Wmutex if Readcount = 0

9、then V(Wmutex) )； /沒有讀者了沒有讀者了 V(RmutexV(Rmutex););end;end;操操作作系系統(tǒng)統(tǒng)2.5 2.5 進(jìn)程的通信進(jìn)程的通信一、進(jìn)程通信的概念一、進(jìn)程通信的概念 進(jìn)程通信的定義：進(jìn)程間的信息交換。進(jìn)程通信的定義：進(jìn)程間的信息交換。 信號(hào)量及信號(hào)量及PVPV操作可實(shí)現(xiàn)進(jìn)程互斥和同步，但缺乏傳輸大操作可實(shí)現(xiàn)進(jìn)程互斥和同步，但缺乏傳輸大量消息的能力。這是一種低級的、間接的通信方式。量消息的能力。這是一種低級的、間接的通信方式。進(jìn)程通信是指進(jìn)程之間可直接以較高的效率傳遞較多數(shù)。進(jìn)程通信是指進(jìn)程之間可直接以較高的效率傳遞較多數(shù)據(jù)的信息交換方式。這種方式中采用的

10、是通信機(jī)構(gòu)。據(jù)的信息交換方式。這種方式中采用的是通信機(jī)構(gòu)。操操作作系系統(tǒng)統(tǒng) 所謂信件是指進(jìn)程之間相互傳遞的賴以發(fā)生交互所謂信件是指進(jìn)程之間相互傳遞的賴以發(fā)生交互作用的有結(jié)構(gòu)的數(shù)據(jù)。作用的有結(jié)構(gòu)的數(shù)據(jù)。 通信機(jī)構(gòu)將緊密地與進(jìn)程的阻塞和釋放相聯(lián)系。通信機(jī)構(gòu)將緊密地與進(jìn)程的阻塞和釋放相聯(lián)系。 這樣，進(jìn)程間的通信就進(jìn)一步擴(kuò)充了并發(fā)進(jìn)程這樣，進(jìn)程間的通信就進(jìn)一步擴(kuò)充了并發(fā)進(jìn)程 間對數(shù)據(jù)的共享。間對數(shù)據(jù)的共享。操操作作系系統(tǒng)統(tǒng)二、進(jìn)程通信的類型二、進(jìn)程通信的類型1 1、進(jìn)程的通信方式有：共享存儲(chǔ)器方式、消息傳遞方式。、進(jìn)程的通信方式有：共享存儲(chǔ)器方式、消息傳遞方式。共享存儲(chǔ)器方式分為共享數(shù)據(jù)結(jié)構(gòu)方式和共享

11、存儲(chǔ)區(qū)共享存儲(chǔ)器方式分為共享數(shù)據(jù)結(jié)構(gòu)方式和共享存儲(chǔ)區(qū)方式方式 共享數(shù)據(jù)結(jié)構(gòu)方式比如臨界區(qū)，該數(shù)據(jù)類型的設(shè)置共享數(shù)據(jù)結(jié)構(gòu)方式比如臨界區(qū)，該數(shù)據(jù)類型的設(shè)置及管理必須由程序員完成，因此不常用及管理必須由程序員完成，因此不常用, ,是低效的是低效的 共享存儲(chǔ)區(qū)方式即信箱通信共享存儲(chǔ)區(qū)方式即信箱通信 進(jìn)程通過對共享存儲(chǔ)區(qū)中數(shù)據(jù)的讀寫來實(shí)現(xiàn)通信進(jìn)程通過對共享存儲(chǔ)區(qū)中數(shù)據(jù)的讀寫來實(shí)現(xiàn)通信操操作作系系統(tǒng)統(tǒng)消息傳遞方式消息傳遞方式 messagemessage為傳遞單位為傳遞單位, ,也稱報(bào)文也稱報(bào)文 程序員通過系統(tǒng)提供的通信原語進(jìn)行通信程序員通過系統(tǒng)提供的通信原語進(jìn)行通信, ,操作系操作系統(tǒng)隱藏了通信的細(xì)節(jié)統(tǒng)

12、隱藏了通信的細(xì)節(jié) 有直接和間接兩種方式有直接和間接兩種方式操操作作系系統(tǒng)統(tǒng)三、消息傳遞系統(tǒng)的實(shí)現(xiàn)三、消息傳遞系統(tǒng)的實(shí)現(xiàn)1 1、消息傳遞方式有直接和間接兩種。、消息傳遞方式有直接和間接兩種。2 2、直接通信方式、直接通信方式 使用原語使用原語 Send(Receiver,messageSend(Receiver,message) )：發(fā)送一個(gè)消息給接收方，：發(fā)送一個(gè)消息給接收方， Receive(Sender,messageReceive(Sender,message) )：接收：接收sendersender發(fā)來的消息發(fā)來的消息 接收進(jìn)程可與多個(gè)發(fā)送進(jìn)程通信，接收原語中的源進(jìn)接收進(jìn)程可與多個(gè)發(fā)送

13、進(jìn)程通信，接收原語中的源進(jìn) 程參數(shù)，可靈活設(shè)置程參數(shù)，可靈活設(shè)置 操操作作系系統(tǒng)統(tǒng)3 3、間接通信方式、間接通信方式 建立在共享數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)上實(shí)現(xiàn)通信建立在共享數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)上實(shí)現(xiàn)通信 信件信件 信件內(nèi)容包括發(fā)送者名信息（或信息存放地址和信件內(nèi)容包括發(fā)送者名信息（或信息存放地址和 長度）長度）和等和等/ /不等回信；回信存放地址。不等回信；回信存放地址。 利用信箱實(shí)現(xiàn)通信利用信箱實(shí)現(xiàn)通信操操作作系系統(tǒng)統(tǒng) 信箱信箱 若干個(gè)進(jìn)程都可向一個(gè)進(jìn)程發(fā)送信件，接收的進(jìn)程設(shè)立若干個(gè)進(jìn)程都可向一個(gè)進(jìn)程發(fā)送信件，接收的進(jìn)程設(shè)立一個(gè)信箱。信箱大小決定了可以容納的信件數(shù)。一個(gè)信箱。信箱大小決定了可以容納的信件數(shù)。

14、每個(gè)信箱由每個(gè)信箱由“信箱說明信箱說明”和和“信箱體信箱體”兩個(gè)部分組成。兩個(gè)部分組成。操操作作系系統(tǒng)統(tǒng) 通信原語通信原語 “ “發(fā)送發(fā)送”（SendSend）原語和）原語和“接收接收”(Receive)(Receive)原語。原語。 為避免信件的丟失和錯(cuò)誤地索取信件，通信時(shí)應(yīng)為避免信件的丟失和錯(cuò)誤地索取信件，通信時(shí)應(yīng) 遵循同步規(guī)則。遵循同步規(guī)則。操操作作系系統(tǒng)統(tǒng) 發(fā)送原語：發(fā)送原語： S1S1為信箱滿否信號(hào)量，初值為信箱為信箱滿否信號(hào)量，初值為信箱B B容量容量n n； S2S2為信箱中當(dāng)前信件數(shù)的信號(hào)量，初值為為信箱中當(dāng)前信件數(shù)的信號(hào)量，初值為0 0。 算法算法 Send(B,M)Send

15、(B,M) 輸入：信箱輸入：信箱B B，信件，信件M M 輸出：無輸出：無 根據(jù)信箱根據(jù)信箱B B找到該信箱找到該信箱( (或接收進(jìn)程或接收進(jìn)程) )信號(hào)量信號(hào)量S1;S1; P(S1 P(S1);/);/* *查詢信箱滿否？若滿則阻塞等待查詢信箱滿否？若滿則阻塞等待* */ / BI=M; BI=M; / /* *信件信件M M放入該信箱放入該信箱* */ / I =(I+1) mod n; I =(I+1) mod n;/ /* *調(diào)整存信指針調(diào)整存信指針* */ / V(S2) V(S2)； / /* *與接收進(jìn)程同步與接收進(jìn)程同步, ,若接收者等待則喚醒它若接收者等待則喚醒它* */

16、/ 操操作作系系統(tǒng)統(tǒng) 接收原語：接收原語： S1S1為信箱滿否信號(hào)量，初值為信箱為信箱滿否信號(hào)量，初值為信箱B B容量容量n n； S2S2為信箱中當(dāng)前信件數(shù)的信號(hào)量，初值為為信箱中當(dāng)前信件數(shù)的信號(hào)量，初值為0 0。 算法算法 Receive(B,X)Receive(B,X) 輸入：信箱輸入：信箱B B，接收區(qū)，接收區(qū)X X 輸出：無輸出：無 根據(jù)信箱根據(jù)信箱B B找到該信箱（或接收進(jìn)程）信號(hào)量找到該信箱（或接收進(jìn)程）信號(hào)量S2;S2; P(S2 P(S2);/);/查詢有無信件可取？若無則阻塞等待查詢有無信件可??？若無則阻塞等待 X=BJ; X=BJ; / /* *從信箱中取一封信件從信箱中

17、取一封信件* */ / J=(J+1) mod n; J=(J+1) mod n; / /* *調(diào)整取信指針調(diào)整取信指針* */ / V(S1); V(S1); / /* *與發(fā)送進(jìn)程同步與發(fā)送進(jìn)程同步, ,若它等待則喚醒它若它等待則喚醒它* */ / 操操作作系系統(tǒng)統(tǒng) A A、B B進(jìn)程間的通信過程進(jìn)程間的通信過程A A進(jìn)程調(diào)用進(jìn)程調(diào)用SendSend原語向原語向B B進(jìn)程發(fā)出信件，進(jìn)程發(fā)出信件，B B進(jìn)程調(diào)用進(jìn)程調(diào)用 ReceiveReceive原語就可從信箱中索取來自原語就可從信箱中索取來自A A進(jìn)程的信件，進(jìn)程的信件， 這就完成了一次這就完成了一次A A進(jìn)程和進(jìn)程和B B進(jìn)程的通信過程

18、。進(jìn)程的通信過程。B B進(jìn)程進(jìn)程 得到信件后進(jìn)行適當(dāng)處理，然后把處理的結(jié)果組織得到信件后進(jìn)行適當(dāng)處理，然后把處理的結(jié)果組織 成一封回信發(fā)送回成一封回信發(fā)送回A A。進(jìn)程發(fā)出信件后，想要得到對方處理的結(jié)果，也可進(jìn)程發(fā)出信件后，想要得到對方處理的結(jié)果，也可 索取一封回信，實(shí)現(xiàn)了索取一封回信，實(shí)現(xiàn)了B B進(jìn)程和進(jìn)程和A A進(jìn)程的另一次通信進(jìn)程的另一次通信 過程。過程。操操作作系系統(tǒng)統(tǒng)5 5、消息緩沖通信、消息緩沖通信 消息緩沖通訊原理消息緩沖通訊原理BrinchBrinch Hansen Hansen于于19691969年首先提出并實(shí)現(xiàn)，數(shù)據(jù)交年首先提出并實(shí)現(xiàn)，數(shù)據(jù)交換以消息為單位換以消息為單位.

19、.系統(tǒng)統(tǒng)一設(shè)置消息緩沖區(qū)取代信箱，系統(tǒng)統(tǒng)一設(shè)置消息緩沖區(qū)取代信箱，各進(jìn)程不再設(shè)置自己的信箱。各進(jìn)程不再設(shè)置自己的信箱。設(shè)定在通訊源和目的之間存在一條虛擬的通訊鏈設(shè)定在通訊源和目的之間存在一條虛擬的通訊鏈操操作作系系統(tǒng)統(tǒng) 系統(tǒng)設(shè)立消息緩沖區(qū)可以帶來許多好處：系統(tǒng)設(shè)立消息緩沖區(qū)可以帶來許多好處： 無需在接收方準(zhǔn)備好接收緩沖區(qū)之前，發(fā)送無需在接收方準(zhǔn)備好接收緩沖區(qū)之前，發(fā)送 方就可以發(fā)送，消息可以存放于系統(tǒng)的消息方就可以發(fā)送，消息可以存放于系統(tǒng)的消息 緩沖區(qū)中。緩沖區(qū)中。 一旦消息從發(fā)送方消息緩沖區(qū)拷入系統(tǒng)緩沖區(qū)，一旦消息從發(fā)送方消息緩沖區(qū)拷入系統(tǒng)緩沖區(qū)， 發(fā)送方緩沖區(qū)又可被用來存放另一個(gè)要發(fā)送消息

20、。發(fā)送方緩沖區(qū)又可被用來存放另一個(gè)要發(fā)送消息。 這樣可以實(shí)現(xiàn)消息傳遞的流水線操作。這樣可以實(shí)現(xiàn)消息傳遞的流水線操作。操操作作系系統(tǒng)統(tǒng) 消息包括消息頭和消息正文消息包括消息頭和消息正文 進(jìn)程同步方式進(jìn)程同步方式 緊密同步：接收和發(fā)送間無緩沖緊密同步：接收和發(fā)送間無緩沖 發(fā)送不阻塞，接收阻塞發(fā)送不阻塞，接收阻塞 發(fā)送和接收進(jìn)程都不阻塞：中間有一消息隊(duì)列發(fā)送和接收進(jìn)程都不阻塞：中間有一消息隊(duì)列操操作作系系統(tǒng)統(tǒng)進(jìn)程緩沖通訊示例進(jìn)程緩沖通訊示例 系統(tǒng)設(shè)置一個(gè)緩沖池，其中每個(gè)緩沖區(qū)系統(tǒng)設(shè)置一個(gè)緩沖池，其中每個(gè)緩沖區(qū)bufferbuffer可可 存放一條消息。存放一條消息。 發(fā)送消息時(shí)，發(fā)送者先在自己的內(nèi)存空間中設(shè)置發(fā)送消息時(shí)，發(fā)送者先在自己的內(nèi)存空間中設(shè)置 一發(fā)送區(qū)，填寫好消息的信息，再申請一個(gè)可用一發(fā)送區(qū)，填寫好消息的信息，再申請一個(gè)可用 消息緩沖區(qū)，把發(fā)送區(qū)內(nèi)容復(fù)制到消息緩沖區(qū)里，消息緩沖區(qū)，把發(fā)送區(qū)內(nèi)容復(fù)制到消息緩沖區(qū)里， 然后把該緩沖區(qū)連接到接收進(jìn)程的消息隊(duì)列上。然后把該緩沖區(qū)連接到接收進(jìn)程的消息隊(duì)列上。 一個(gè)接收進(jìn)程接收的信件可以很多，所以發(fā)送信一個(gè)接收進(jìn)程接收的信件可以很多，所以發(fā)送信 件時(shí)應(yīng)說明接收進(jìn)程標(biāo)識(shí)、信件長度和正文。件時(shí)應(yīng)