第五章同步與互斥

第五章同步和互斥

5.2同步機構(gòu)

分布式系統(tǒng)中同步機構(gòu)的作用

同步點：為了達到合作，各個進程在執(zhí)行的過程中必須存在若干點，超過這些點時，一個進程在另一個進程執(zhí)行完某一活動前不能繼續(xù)執(zhí)行，這些點稱為這兩個進程之間的同步點。

分布計算系統(tǒng)中共享資源的兩類：一類是各進程可以同時訪問的，如中央處理機(允許多個進程交疊使用一個處理機)、只讀文件和不允許修改的存放子程序和數(shù)據(jù)的主存區(qū)域等；另一類是不允許多個進程同時訪問的，每次只允許一個進程使用，如大多數(shù)外部設(shè)備(如打印機)、可寫的文件以及主存中可修改的區(qū)域等。同步機構(gòu)在互斥控制中的作用是對活動的執(zhí)行進行排序。第五章同步和互斥

5.2同步機構(gòu)

分布式系統(tǒng)中同步機構(gòu)的作用

一致狀態(tài)：一個計算系統(tǒng)應(yīng)該在所有時間內(nèi)滿足一定的外部規(guī)定或約束，如果一個計算系統(tǒng)確實在所有時間內(nèi)滿足了一定的外部規(guī)定或約束，這時我們稱系統(tǒng)狀態(tài)是一致的。同步機構(gòu)的目的就是給進程提供某種手段，使系統(tǒng)保持一致狀態(tài)。分布計算系統(tǒng)的計算方式分成三種：完全復(fù)制的計算。任何操作所激發(fā)的每個活動必須由所有的消費者共同處理，要求所有的活動均應(yīng)完成。這時同步機構(gòu)的目的是保證消費者處理活動的次序必須相同。第五章同步和互斥

5.2同步機構(gòu)

分布計算系統(tǒng)的計算方式分成三種：完全分割的計算。一個操作所激發(fā)的不同活動由不同的消費者分別獨自處理。在這種情況下，同步機構(gòu)的目的是保證所有相互干擾的活動成為有序的，使得該操作保持原子性(要么完成操作，要么干脆不發(fā)生)。分割和部分復(fù)制的計算。一個操作所激發(fā)的活動中，某些是由不同的消費者獨自處理的，某些操作是由一些消費者共同處理。它兼有前面兩種計算形式的特點。對于不同的計算方式，同步機構(gòu)的目的和要求也是不同的。第五章同步和互斥

5.2同步機構(gòu)

評價同步機構(gòu)的標準：響應(yīng)時間和吞吐量。各種機構(gòu)應(yīng)盡量利用系統(tǒng)的并行性質(zhì)，以提高吞吐量和縮短響應(yīng)時間?；謴?fù)能力。同步機構(gòu)應(yīng)能使系統(tǒng)從故障中恢復(fù)過來。開銷。指使用同步機構(gòu)的代價，包括額外增加的報文長度、數(shù)量和對它們的處理時間，以及用于存放同步信息所需的額外存儲空間。公平性。操作發(fā)生沖突時，同步機構(gòu)應(yīng)能避免生產(chǎn)者餓死，各生產(chǎn)者具有平等的權(quán)利。

第五章同步和互斥

5.2同步機構(gòu)

評價同步機構(gòu)的標準：可擴充性。系統(tǒng)擴充新的處理機時同步機構(gòu)應(yīng)不影響其正常運行。連接方式。使用某些同步機構(gòu)要求生產(chǎn)者在邏輯上全部互連，這樣所產(chǎn)生的開銷可能很大；有些同步機構(gòu)只要求一個生產(chǎn)者知道其鄰居的情況，開銷也較少。初始化。使用同步機構(gòu)要求系統(tǒng)應(yīng)容易進行初始化，知道進程何時可以進行生產(chǎn)和消費活動。排序方法。當生產(chǎn)者對一序列操作進行某種指定排序時，必須交換報文，各種同步機構(gòu)實現(xiàn)效率可能大不相同。

第五章同步和互斥

5.2同步機構(gòu)

邏輯時鐘邏輯時鐘可以給分布計算系統(tǒng)中的事件一個唯一的排序。邏輯時鐘的本質(zhì)是基于Lamport定義的“在先發(fā)生關(guān)系”。在先發(fā)生關(guān)系

如果a和b均是同一進程中的兩個事件，并且a在b之前出現(xiàn)，則a→b；若a代表“一個進程發(fā)送一個報文”這個事件，b代表“另一個進程接收這個報文”這個事件，則a→b；如果a→b，且b→c，則a→c。

兩個不同的事件a和b，如果a→b，或b→a，則事件a和b是因果關(guān)聯(lián)的。如果a→b和b→a均不成立，則稱事件a和b是并發(fā)的。

第五章同步和互斥

5.2同步機構(gòu)

邏輯時鐘在先發(fā)生關(guān)系的時空圖

水平方向代表空間，垂直方向代表時間，圓點代表事件，豎線代表進程，進程之間帶箭頭的線代表報文。

第五章同步和互斥

5.2同步機構(gòu)

邏輯時鐘邏輯時鐘

設(shè)Ci代表進程i的邏輯時鐘，該邏輯時鐘就是一個函數(shù)，它給進程i中的事件a分配一個正整數(shù)值Ci(a)。

時鐘條件： 對任何事件a和b，如果a→b，則C(a)<C(b)。但相反的結(jié)論不能成立。若a和b是同一進程Pi中的兩個時間，并且a→b，則Ci(a)<Ci(b)；若a代表“一個Pi進程發(fā)送一個報文”這個事件，b代表“另一個進程Pj接收這個報文”這個事件，Ci(a)<Cj(b)。第五章同步和互斥

5.2同步機構(gòu)

邏輯時鐘邏輯時鐘

標量邏輯時鐘

每個進程Pi有一個邏輯時鐘LCi，LCi被初始化為init(init≥0)并且它是一個非減的整數(shù)序列。進程Pi發(fā)送的每個報文m都被標上LCi的當前值和進程的標號i，從而形成一個三元組(m,LCi,i)。任何一個邏輯時鐘LCi基于以下兩條規(guī)則更新它的邏輯時鐘值：當發(fā)生一個事件(一個外部發(fā)送或內(nèi)部事件)之前，我們更新LCi：LCi:=LCi+d (d>0)當收到一個帶時間戳的報文(m,LCj,j)時，我們更新LCi：LCi:=max(LCi,LCj)+d (d>0)第五章同步和互斥

5.2同步機構(gòu)

邏輯時鐘邏輯時鐘

標量邏輯時鐘

第五章同步和互斥

5.2同步機構(gòu)

邏輯時鐘邏輯時鐘

向量邏輯時鐘

在向量邏輯時鐘中，每個進程Pi和一個時間向量LCi[1,…,n]相關(guān)聯(lián)，其中向量元素LCi[i]描述了進程Pi的邏輯時間進展情況，即自身的邏輯時間進展情況；向量元素LCi[j]表示進程Pi所知的關(guān)于進程Pj的邏輯時間進展情況；向量LCi[1,…,n]組成進程Pi對于邏輯全局時間的局部視圖。第五章同步和互斥

5.2同步機構(gòu)

邏輯時鐘邏輯時鐘

向量邏輯時鐘

任何一個邏輯時鐘LCi基于以下兩條規(guī)則更新它的邏輯時鐘值：當發(fā)生一個事件(一個外部發(fā)送或內(nèi)部事件)之前，Pi更新LCi[i]：

LCi[i]:=LCi[i]+d (d>0)每個報文捎帶發(fā)送方在發(fā)送時的時鐘向量，當收到一個帶時間戳的報文(m,LCj,j)時，Pi更新LCi：

LCi[k]:=max(LCi[k],LCj[k]) 1≤k≤n LCi[i]:=LCi[i]+d (d>0)第五章同步和互斥

5.2同步機構(gòu)

邏輯時鐘邏輯時鐘

向量邏輯時鐘

第五章同步和互斥

5.4互斥算法

互斥問題互斥問題就是定義一些基本的操作來解決共享資源的多個并發(fā)進程的沖突問題。互斥算法的主要目標是保證在任一個時刻只能有一個進程訪問臨界區(qū)。一個正確的互斥算法必須避免沖突(死鎖和餓死)和保證公平性。為此，算法應(yīng)滿足以下三個條件：已獲得資源的進程必須先釋放資源之后，另一個進程才能得到資源；不同的請求應(yīng)該按照這些請求的產(chǎn)生順序獲得滿足，請求應(yīng)該按照某種規(guī)則進行排序，例如使用邏輯時鐘確定請求的順序；若獲得資源的每個進程最終都釋放資源，則每個請求最終都能滿足。第五章同步和互斥

5.4互斥算法

互斥問題衡量互斥算法性能的參數(shù)：

完成一次互斥操作所需的報文數(shù)目；同步延遲，即從一個進程離開臨界區(qū)之后到下一個進程進入臨界區(qū)之前的時間間隔；

響應(yīng)時間，即從一個進程發(fā)出請求到該進程離開該臨界區(qū)之間的時間間隔。第五章同步和互斥

5.4互斥算法

集中式互斥算法第五章同步和互斥

5.4互斥算法

Lamport時間戳互斥算法Lamport時間戳互斥算法由以下5條規(guī)則組成：一個進程Pi如果為了申請資源，它向其它各個進程發(fā)送具有時間戳Tm:Pi的申請資源的報文，并把此報文也放到自己的申請隊列中；一個進程Pj如果收到具有時間戳Tm:Pi的申請資源的報文，它把此報文放到自己的申請隊列中，并將向Pi發(fā)送一個帶有時間戳的承認報文。如果Pj正在臨界區(qū)或正在發(fā)送自己的申請報文，則此承認報文要等到Pj從臨界區(qū)中退出之后或Pj發(fā)送完自己的申請報文之后再發(fā)送，否則立即發(fā)送；一個進程Pi如果想釋放資源，它先從自己的申請隊列中刪除對應(yīng)的Tm:Pi申請報文，并向所有其他進程發(fā)送具有時間戳的Pi釋放資源的報文；

第五章同步和互斥

5.4互斥算法

Lamport時間戳互斥算法Lamport時間戳互斥算法由以下5條規(guī)則組成：一個進程Pj如果收到Pi釋放資源的報文，它從自己的申請隊列中刪除Tm:Pi申請報文；當滿足下述兩個條件時，申請資源的進程Pi獲得資源：Pi的申請隊列中有Tm:Pi申請報文，并且根據(jù)時間戳它排在所有其它進程發(fā)來的申請報文前面；Pi收到所有其它進程的承認報文，其上面的時間戳值大于Tm。第五章同步和互斥

5.4互斥算法

Lamport時間戳互斥算法Lamport時間戳互斥算法實例：第五章同步和互斥

5.4互斥算法

Ricart-Agrawala互斥算法一個進程申請資源時向所有其他進程發(fā)出申請報文；其它進程收到申請報文后若不在臨界區(qū)并且自己未申請進入臨界區(qū)，或者自己雖然發(fā)出了申請報文，但自己的報文排在收到的申請報文之后，則回答表示同意；申請資源的進程僅在收到所有進程的回答報文后才進入臨界區(qū)使用資源；一個進程使用完資源后，它向所有未給回答的其它申請發(fā)送回答報文。第五章同步和互斥

5.4互斥算法

Ricart-Agrawala互斥算法Ricart-Agrawala互斥算法實例：第五章同步和互斥

5.4互斥算法

Maekawa互斥算法請求子集：在Maekawa互斥算法中，一個進程P在發(fā)出申請報文后，不用得到所有其他進程的回答，而只須得到一個進程子集S中的所有進程的回答即可進入臨界區(qū)。稱S是P的請求子集。假設(shè)Ri和Rj分別是進程Pi和Pj的請求子集，要求Ri∩Rj≠NULL。當進程Pi請求進入臨界區(qū)時，它只向Ri中的進程發(fā)送請求報文。當進程Pj收到一個請求報文時，如果它自上一次臨界區(qū)釋放后還沒有發(fā)出過回答報文給任何進程，且自己的請求隊列中無任何請求，它就給該請求報文一個回答。否則，請求報文被放入請求隊列中。進程Pi只有收到Ri中的所有進程的回答后，才能進入臨界區(qū)。在釋放臨界區(qū)時，進程Pi只給Ri中的所有進程發(fā)送釋放報文。第五章同步和互斥

5.4互斥算法

Maekawa互斥算法請求子集的例子：考慮一個七個進程的例子，每個進程的請求子集如下：R1：{P1，P3，P4}；R2：{P2，P4，P5}；R3：{P3，P5，P6}；R4：{P4，P6，P7}；R5：{P5，P7，P1}；R6：{P6，P1，P2}；R7：{P7，P2，P3}。第五章同步和互斥

5.4互斥算法

Maekawa互斥算法Maekawa算法的兩個極端情況：(1)退化為集中式互斥算法。Pc(c∈{1，2，…，n})作為協(xié)調(diào)者，對所有進程Pi，有：Ri：{Pc}，1≤i≤n(2)完全分布式的互斥算法。對所有進程Pi，有：Ri：{P1，P2，…，Pn}，1≤i≤n第五章同步和互斥

5.4互斥算法

簡單令牌環(huán)互斥算法在有n個進程的系統(tǒng)中，將這n個進程組成一個首尾相連的邏輯環(huán)。每個進程在環(huán)中有一個指定的位置，位置可以按網(wǎng)絡(luò)地址進行排列，當然也可以采用任何其他可行的方式排列，但每個進程必須知道在環(huán)中哪個進程是它后面的進程。一個進程擁有令牌時就可以進入臨界區(qū)，令牌可在所有的進程間傳遞。如果得到令牌的進程不打算進入臨界區(qū)，它只是簡單地將令牌傳送給它后面的進程。第五章同步和互斥

5.4互斥算法

簡單令牌環(huán)互斥算法問題：如果令牌丟失，需要重新產(chǎn)生一個令牌，但檢測令牌是否丟失是比較困難的。另外一個問題是進程的崩潰，但進程的崩潰比較容易檢測。這個算法在高負載的情況下工作得很好。然而，它在輕負載的情況下工作得很差，出現(xiàn)很多不必要的報文傳遞。

第五章同步和互斥

5.4互斥算法

Ricart-Agrawala令牌環(huán)互斥算法初始時，令牌被賦予給任何一個進程。請求進入臨界區(qū)的進程Pj不知道哪個進程擁有令牌，所以它向所有其它進程發(fā)送一個帶時間戳的請求報文，請求得到令牌。每個進程有一個請求隊列記錄有所有進程的請求，令牌中記錄有每個進程最后一個持有令牌的時間。如果當前擁有令牌的進程Pi不再需要令牌，它就按照i+1，i+2，…，n，1，2，…，i-1的順序?qū)ふ业谝粋€符合條件的進程Pj，并將令牌傳遞給進程Pj。說明：雖然該算法不是按照每個請求的時間順序來滿足的，但是，由于令牌是按一個方向繞環(huán)傳遞的，所以不會有餓死現(xiàn)象發(fā)生。第五章同步和互斥

5.4互斥算法

基于時間戳的令牌互斥算法每個進程保持一張進程狀態(tài)表，記錄它所知的進程狀態(tài)，進程狀態(tài)包括該進程是否為請求進程，以及得到該狀態(tài)的時間。令牌是一個特殊的報文，該報文中包含了發(fā)送該令牌的進程的進程狀態(tài)表。初始化時，每個進程的狀態(tài)表中各個進程均為非請求狀態(tài)，時鐘值為0，并任意指定一個進程為令牌的持有者。請求時，一個進程請求進入臨界區(qū)時，如果它持有令牌，它不發(fā)送任何請求報文，將自己的進程狀態(tài)表中相應(yīng)于自己一欄的狀態(tài)改為請求態(tài)，并記錄該狀態(tài)的時鐘值，直接進入臨界區(qū)。如果它不持有令牌，則它向所有其它進程發(fā)送帶有時間戳的請求報文。發(fā)出請求報文后，將自己的進程狀態(tài)表中相應(yīng)于自己一欄的狀態(tài)改為請求態(tài)，并記錄該狀態(tài)的時鐘值。第五章同步和互斥

5.4互斥算法

基于時間戳的令牌互斥算法收到請求時，當進程A收到進程B的請求報文時，A將B的請求報文中的時間戳同A的進程狀態(tài)表中B的時間值進行比較。若B的請求報文中的時間戳大于A的進程狀態(tài)表中B的時間值，則A修改自己的進程狀態(tài)表。將A的進程狀態(tài)表中對應(yīng)于B的一欄改為請求狀態(tài)，并記錄此狀態(tài)的時間。退出臨界區(qū)時，進程A退出臨界區(qū)后，將自己的進程狀態(tài)表中關(guān)于自己的一欄改為非請求狀態(tài)，時鐘值加1，并將該時鐘值作為該狀態(tài)的時間。然后檢查其進程狀態(tài)表中是否記錄有某個進程處于請求狀態(tài)，若有，則從處于請求狀態(tài)的進程中選取一個請求最早的進程B(具有最小的時間戳)，將令牌傳送給它，并在令牌中附上A的進程狀態(tài)表。第五章同步和互斥

5.4互斥算法

基于時間戳的令牌互斥算法收到令牌時，收到令牌的進程把隨令牌傳來的進程狀態(tài)表和自己的進程狀態(tài)表進行比較。若隨令牌傳來的進程狀態(tài)表中某進程的時間戳大于自己的進程狀態(tài)表中相應(yīng)進程的時間戳，則將自己的進程狀態(tài)表中相應(yīng)進程的狀態(tài)和時間戳該成隨令牌傳來的進程狀態(tài)表中相應(yīng)的狀態(tài)和時間戳。說明：同Ricart-Agrawala令牌環(huán)互斥算法相比，具有更強的公平性，因為它是基于請求的先后順序來滿足的，而Ricart-Agrawala令牌環(huán)互斥算法是基于進程的邏輯環(huán)結(jié)構(gòu)來滿足的。第五章同步和互斥

5.4互斥算法

選舉算法從進程集中選出一個進程執(zhí)行特別的任務(wù)。大部分選舉算法是基于全局優(yōu)先級的，就是說給每個進程預(yù)先分配一個優(yōu)先級，選舉算法選擇一個具有最高優(yōu)先級的進程作為協(xié)調(diào)者。Bully選舉算法

P發(fā)送選舉報文到所有優(yōu)先級比它高的進程。如果在一定時間內(nèi)收不到任何響應(yīng)報文，P贏得選舉成為協(xié)調(diào)者。它向所有比它的優(yōu)先級低的進程發(fā)送通知報文，宣布自己是協(xié)調(diào)者。如果收到一個優(yōu)先級比它高的進程的回答，P的選舉工作結(jié)束。同時啟動一個計時器，等待接收誰是協(xié)調(diào)者的通知報文，如果在規(guī)定時間內(nèi)得不到通知報文，則它重新啟動選舉算法。任何時候，一個進程可能從比它的優(yōu)先級低的進程那兒接收到一個選舉報文，它就給發(fā)送者回答一個響應(yīng)報文，同時啟動如上所述的相同的選舉算法，如果選舉算法已經(jīng)啟動，就不必重新啟動。第五章同步和互斥

5.4互斥算法

選舉算法Bully選舉算法實例：

第五章同步和互斥

5.4互斥算法

選舉算法Bully選舉算法實例：

第五章同步和互斥

5.4互斥算法

選舉算法環(huán)選舉算法：

在環(huán)選舉算法中，所有進程以任意的順序排列在一個單向環(huán)上，每個進程知道環(huán)上的排列情況，任何進程在環(huán)上有一個后繼進程。任何一個進程發(fā)現(xiàn)協(xié)調(diào)者失效時，它創(chuàng)建一個選舉報文，將自己的進程號加入該報文中作為一個候選協(xié)調(diào)者，并把該選舉報文