第五章同步與互斥

第五章同步和互斥

5.2同步機(jī)構(gòu)

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

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

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

5.2同步機(jī)構(gòu)

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

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

5.2同步機(jī)構(gòu)

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

5.2同步機(jī)構(gòu)

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

第五章同步和互斥

5.2同步機(jī)構(gòu)

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

第五章同步和互斥

5.2同步機(jī)構(gòu)

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

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

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

第五章同步和互斥

5.2同步機(jī)構(gòu)

邏輯時(shí)鐘在先發(fā)生關(guān)系的時(shí)空?qǐng)D

水平方向代表空間，垂直方向代表時(shí)間，圓點(diǎn)代表事件，豎線代表進(jìn)程，進(jìn)程之間帶箭頭的線代表報(bào)文。

第五章同步和互斥

5.2同步機(jī)構(gòu)

邏輯時(shí)鐘邏輯時(shí)鐘

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

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

5.2同步機(jī)構(gòu)

邏輯時(shí)鐘邏輯時(shí)鐘

標(biāo)量邏輯時(shí)鐘

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

5.2同步機(jī)構(gòu)

邏輯時(shí)鐘邏輯時(shí)鐘

標(biāo)量邏輯時(shí)鐘

第五章同步和互斥

5.2同步機(jī)構(gòu)

邏輯時(shí)鐘邏輯時(shí)鐘

向量邏輯時(shí)鐘

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

5.2同步機(jī)構(gòu)

邏輯時(shí)鐘邏輯時(shí)鐘

向量邏輯時(shí)鐘

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

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

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

5.2同步機(jī)構(gòu)

邏輯時(shí)鐘邏輯時(shí)鐘

向量邏輯時(shí)鐘

第五章同步和互斥

5.4互斥算法

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

5.4互斥算法

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

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

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

5.4互斥算法

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

5.4互斥算法

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

第五章同步和互斥

5.4互斥算法

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

5.4互斥算法

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

5.4互斥算法

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

5.4互斥算法

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

5.4互斥算法

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

5.4互斥算法

Maekawa互斥算法請(qǐng)求子集的例子：考慮一個(gè)七個(gè)進(jìn)程的例子，每個(gè)進(jìn)程的請(qǐng)求子集如下：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算法的兩個(gè)極端情況：(1)退化為集中式互斥算法。Pc(c∈{1，2，…，n})作為協(xié)調(diào)者，對(duì)所有進(jìn)程Pi，有：Ri：{Pc}，1≤i≤n(2)完全分布式的互斥算法。對(duì)所有進(jìn)程Pi，有：Ri：{P1，P2，…，Pn}，1≤i≤n第五章同步和互斥

5.4互斥算法

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

5.4互斥算法

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

第五章同步和互斥

5.4互斥算法

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

5.4互斥算法

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

5.4互斥算法

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

5.4互斥算法

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

5.4互斥算法

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

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

5.4互斥算法

選舉算法Bully選舉算法實(shí)例：

第五章同步和互斥

5.4互斥算法

選舉算法Bully選舉算法實(shí)例：

第五章同步和互斥

5.4互斥算法

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

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