分布式系統(tǒng)中的死鎖.ppt

1、第六章 分布式系統(tǒng)中的死鎖 6.1 死鎖問題,死鎖發(fā)生的條件,(1) 互斥。正如我們第五章所討論的，互斥是一種資源分配方式，保證同一個資源在同一時刻最多只能被一個進(jìn)程占用，它用于防止多個進(jìn)程同時共享訪問不可同時共享訪問的資源。 (2) 不可剝奪的資源分配。系統(tǒng)將一個資源的訪問權(quán)分配給某一個進(jìn)程后，系統(tǒng)不能強(qiáng)迫該進(jìn)程放棄對該資源的控制權(quán)。 (3) 占有并等待。必然有一個進(jìn)程占用了至少一個資源，同時在等待獲取被其他進(jìn)程占用的資源。 (4) 循環(huán)等待。在等待圖中有一個循環(huán)路徑。,第六章 分布式系統(tǒng)中的死鎖 6.1 死鎖問題,死鎖的圖論模型,可以用圖模型來表示死鎖，表示死鎖的圖模型有兩種，一種是等待圖

2、，另一種是資源分配圖。,在等待圖中，節(jié)點代表進(jìn)程，當(dāng)且僅當(dāng)進(jìn)程Pi等待一個被進(jìn)程Pj所占用的資源時，邊(Pi,Pj)存在于等待圖中，圖中的邊是有向的。 資源分配圖中的節(jié)點有兩種：一種是進(jìn)程節(jié)點，另一種是資源節(jié)點。每個邊是一個有序?qū)?Pi,Rj)或(Rj,Pi)，其中P代表進(jìn)程，R代表一個資源類型。邊(Pi,Rj)表示進(jìn)程Pi請求類型為Rj的一個資源，并且正在等待這個資源，一個資源類型中可能有多個資源。邊(Rj,Pi)表示類型為Rj的一個資源已經(jīng)分配給進(jìn)程Pi。由于等待圖假定一個資源類型中只有一個資源，所以資源分配圖是一個比等待圖更加有力的工具。,第六章 分布式系統(tǒng)中的死鎖 6.1 死鎖問題,死

3、鎖的圖論模型,資源分配圖實例：,第六章 分布式系統(tǒng)中的死鎖 6.1 死鎖問題,死鎖的圖論模型,資源分配圖到等待圖的轉(zhuǎn)化： (1)在資源分配圖中找到一個未被處理的資源R。如果所有的資源都已經(jīng)處理，轉(zhuǎn)向步驟3。 (2)從這個資源R的每個輸入進(jìn)程節(jié)點到每個輸出進(jìn)程節(jié)點之間加一條有向邊。一個資源的輸入進(jìn)程節(jié)點是等待這個資源的進(jìn)程節(jié)點，一個資源的輸出進(jìn)程節(jié)點是占有這個資源的進(jìn)程節(jié)點。轉(zhuǎn)向步驟1。 (3)刪除所有的資源節(jié)點以及相應(yīng)的邊。,第六章 分布式系統(tǒng)中的死鎖 6.1 死鎖問題,死鎖的圖論模型,資源分配圖到等待圖的轉(zhuǎn)化實例：,第六章 分布式系統(tǒng)中的死鎖 6.1 死鎖問題,處理死鎖的策略死鎖,可以使用P

4、AID來概括死鎖處理的各種方法：預(yù)防(Prevent)、避免(Avoid)、忽略(Ignore)和檢測(Detect) 。 預(yù)防死鎖。通過限制請求，保證四個死鎖條件中至少有一個不能發(fā)生，從而預(yù)防死鎖。 避免死鎖。如果資源分配會導(dǎo)致一個安全的結(jié)果狀態(tài)，就將資源動態(tài)地分配給進(jìn)程。如果至少有一個執(zhí)行序列使所有的進(jìn)程都能完成運行，那么這個狀態(tài)就是安全的。 忽略死鎖。忽略死鎖是UNIX常采用的一種方法，這種方法只是簡單地忽略死鎖問題。 檢測死鎖和從死鎖中恢復(fù)。允許死鎖發(fā)生，然后發(fā)現(xiàn)并解除死鎖。,第六章 分布式系統(tǒng)中的死鎖 6.1 死鎖問題,死鎖的AND條件和OR條件,資源死鎖和通信死鎖：在通信死鎖中，進(jìn)

5、程等待的資源就是報文。資源死鎖和通信死鎖的真正區(qū)別在于資源死鎖通常使用AND條件，而通信死鎖通常使用OR條件。 所謂AND條件就是當(dāng)進(jìn)程取得所有所需資源時，它才能繼續(xù)執(zhí)行；所謂OR條件就是當(dāng)進(jìn)程得到至少一個所需資源，它就能繼續(xù)執(zhí)行。 在使用AND條件的系統(tǒng)中，死鎖條件是在等待圖中存在回路。但是在使用OR條件的系統(tǒng)中，等待圖中的回路未必會引發(fā)死鎖。在使用OR條件的系統(tǒng)中，死鎖條件是存在結(jié)(knot)。一個結(jié)K是一個節(jié)點集合，對于K中的任何節(jié)點a，a能到達(dá)K中的所有節(jié)點，并且只能到達(dá)K中的節(jié)點。,第六章 分布式系統(tǒng)中的死鎖 6.1 死鎖問題,死鎖的AND條件和OR條件,OR條件死鎖圖例：,第六章

6、分布式系統(tǒng)中的死鎖 6.2 死鎖的預(yù)防,預(yù)防死鎖的一般方法,死鎖預(yù)防算法是通過限制進(jìn)程的資源請求來達(dá)到預(yù)防死鎖的目的，都是通過打破四個死鎖條件中的一個條件來實現(xiàn)的。,進(jìn)程在開始執(zhí)行之前同時獲得所有所需資源。這種方法打破了占有并等待的條件。 所有的資源都要被賦予一個唯一的數(shù)字編號。一個進(jìn)程可以請求一個有唯一編號i的資源，條件是該進(jìn)程沒有占用編號小于或等于i的資源。這樣，就打破了循環(huán)等待的條件。 每個進(jìn)程被賦予一個唯一的優(yōu)先級標(biāo)識。優(yōu)先級標(biāo)識決定了進(jìn)程Pi是否應(yīng)該等待進(jìn)程Pj，從而打破了不可剝奪的條件。,第六章 分布式系統(tǒng)中的死鎖 6.2 死鎖的預(yù)防,基于時間戳的預(yù)防死鎖方法,包括兩種死鎖預(yù)防方案

7、。這兩種方案相互補(bǔ)充，這種方法常用于分布式數(shù)據(jù)庫系統(tǒng)中。,等待死亡方案(wait-die scheme)。該方案是基于非剝奪方法。當(dāng)進(jìn)程Pi請求的資源正被進(jìn)程Pj占有時，只有當(dāng)Pi的時間戳比進(jìn)程Pj的時間戳小時，即Pi比Pj老時，Pi才能等待。否則Pi被卷回(roll-back)，即死亡。 傷害等待方案(wound-wait scheme)。它是一種基于剝奪的方法。當(dāng)進(jìn)程Pi請求的資源正被進(jìn)程Pj占有時，只有當(dāng)進(jìn)程Pi的時間戳比進(jìn)程Pj的時間戳大時，即Pi比Pj年輕時，Pi才能等待。否則Pj被卷回(roll-back)，即死亡。,第六章 分布式系統(tǒng)中的死鎖 6.2 死鎖的預(yù)防,基于時間戳的預(yù)防

8、死鎖方法,圖例說明：,第六章 分布式系統(tǒng)中的死鎖 6.3 死鎖的檢測,集中式死鎖檢測,在集中式死鎖檢測方法中，利用所有的局部資源分配圖(或等待圖)建立一個全局資源分配圖(或等待圖)。任何一個機(jī)器為它自己的進(jìn)程和資源維持一個局部的資源分配圖。整個系統(tǒng)只有一個協(xié)調(diào)者，它維持全局的資源分配圖，全局的資源分配圖是由局部資源分配圖組合而成的。,第六章 分布式系統(tǒng)中的死鎖 6.3 死鎖的檢測,集中式死鎖檢測,全局資源分配圖(或等待圖)的獲得方法： 當(dāng)在局部圖中有邊被加入或刪除時，向協(xié)調(diào)者發(fā)送一個報文，協(xié)調(diào)者根據(jù)報文信息對全局圖進(jìn)行更新。 定期地更新，每個機(jī)器定期地向協(xié)調(diào)者發(fā)送自上次更新以來所有添加的邊和刪

9、除的邊，協(xié)調(diào)者根據(jù)報文信息對全局圖進(jìn)行更新。 當(dāng)協(xié)調(diào)者認(rèn)為需要運行回路檢測算法時，它要求所有的機(jī)器向它發(fā)送局部圖的更新信息，協(xié)調(diào)者對全局圖進(jìn)行更新。 當(dāng)開始死鎖檢測時，協(xié)調(diào)者便查找全局等待圖。如果發(fā)現(xiàn)回路，一個進(jìn)程就會被卷回，從而打破循環(huán)等待。 缺點：容易產(chǎn)生假死鎖的情況 。,第六章 分布式系統(tǒng)中的死鎖 6.3 死鎖的檢測,集中式死鎖檢測,產(chǎn)生假死鎖的圖例說明：,第六章 分布式系統(tǒng)中的死鎖 6.3 死鎖的檢測,集中式死鎖檢測,產(chǎn)生假死鎖的圖例說明：,第六章 分布式系統(tǒng)中的死鎖 6.3 死鎖的檢測,分布式死鎖檢測,Knapp將分布式死鎖檢測算法分為以下四類： 路徑推動算法(path-pushin

10、g algorithm)。先在每個機(jī)器上建立形式簡單的全局等待圖。每當(dāng)進(jìn)行死鎖檢測時，各個機(jī)器就將等待圖的拷貝送往一定數(shù)量的鄰居節(jié)點。局部拷貝更新后又被傳播下去。這一過程重復(fù)進(jìn)行直到某個節(jié)點獲得了足夠的信息來構(gòu)造一個等待圖以便做出是否存在死鎖的結(jié)論。 邊跟蹤算法(edge-chasing algorithm)。分布式網(wǎng)絡(luò)結(jié)構(gòu)圖中的回路可以通過沿圖的邊傳播一種叫探測器的特殊信息來檢測。當(dāng)一個發(fā)起者得到一個與自己發(fā)送的探測器相匹配的探測器時，它就知道它在圖中的一個回路里。,第六章 分布式系統(tǒng)中的死鎖 6.3 死鎖的檢測,分布式死鎖檢測,Knapp將分布式死鎖檢測算法分為以下四類： 擴(kuò)散計算(dif

11、fusing computation)。懷疑有死鎖發(fā)生時，事務(wù)管理器通過向依賴于它的進(jìn)程發(fā)送查詢啟動一個擴(kuò)散進(jìn)程。這里不會生成全局等待圖。發(fā)送查詢信息時，擴(kuò)散計算就增長；接收回答后，擴(kuò)散計算就縮減。根據(jù)所得信息，發(fā)起者會檢測到死鎖的發(fā)生。 全局狀態(tài)檢測(global state detection)。這個方法基于Chandy和Lamport 的快照方法?？梢酝ㄟ^建立一個一致的全局狀態(tài)而無需暫停當(dāng)前的計算來生成一個一致的全局等待圖。,第六章 分布式系統(tǒng)中的死鎖 6.3 死鎖的檢測,層級式死鎖檢測,在層級式死鎖檢測算法中，站點被分層地放在一個樹中。一個站點的死鎖檢測只涉及到它的下一級站點。例如，設(shè)

12、A、B和C是控制器，而C是A和B的最低的公共祖先。假定節(jié)點Pi出現(xiàn)在控制器A和B的局部等待圖中，那么節(jié)點Pi也必定出現(xiàn)在如下控制器的等待圖中： (1) C控制器； (2) 所有位于從C到A的路徑上的控制器； (3) 所有位于從C到B的路徑上的控制器。 而且，如果Pi和Pj出現(xiàn)在控制器D的等待圖中，并且在D的一個下一級控制器(子控制器)的等待圖中有一條從Pi到Pj的路徑，那么邊(Pi,Pj)一定存在于D的等待圖中。,第六章 分布式系統(tǒng)中的死鎖 6.3 死鎖的檢測,關(guān)于死鎖檢測和恢復(fù)的研究方向：,算法正確性。嚴(yán)格證明死鎖檢測算法的正確性是困難的，由于報文的傳輸延遲是不可預(yù)料的，所以得到一致的全局狀

13、態(tài)是很困難的。 算法性能。需要在信息流量(監(jiān)測和恢復(fù)算法的復(fù)雜性)和死鎖持續(xù)時間(監(jiān)測和恢復(fù)的速度)之間達(dá)成妥協(xié)。 死鎖解決。一個好而快的死鎖檢測算法可能并不能提供足夠的信息用于解決死鎖。 假死鎖。一個檢測程序不僅要滿足前進(jìn)要求，即必須在有限的時間內(nèi)發(fā)現(xiàn)死鎖，還要滿足安全要求。如果一個死鎖被發(fā)現(xiàn)，那么這個死鎖應(yīng)該是確實存在的。 死鎖概率。檢測和恢復(fù)算法的設(shè)計依賴于給定系統(tǒng)中死鎖發(fā)生的概率。,第六章 分布式系統(tǒng)中的死鎖 6.3 死鎖的檢測,死鎖檢測的實例,AND模型下的Chandy-Misra-Hass算法,在Chandy-Misra-Hass算法中，分布式死鎖檢測算法使用一個特殊的報文，在等待

14、圖中該報文從一個進(jìn)程傳遞到另一個進(jìn)程，該報文稱為探測報文(probe message)。如果報文回到發(fā)起者，那么就有死鎖存在。探測報文包含一個三元組(i,j,k)，表示該報文是一個由進(jìn)程Pi發(fā)起的死鎖檢測報文，現(xiàn)在由進(jìn)程Pj所在的站點發(fā)往進(jìn)程Pk所在的站點。 當(dāng)一個進(jìn)程接收到一個探測報文時，它首先檢查自己是否等待某個(或某些)進(jìn)程，如果它正在等待某個(或某些)進(jìn)程，它將向所有它等待的進(jìn)程轉(zhuǎn)發(fā)這個探測報文。,第六章 分布式系統(tǒng)中的死鎖 6.3 死鎖的檢測,死鎖檢測的實例,AND模型下的Chandy-Misra-Hass算法圖例說明：,第六章 分布式系統(tǒng)中的死鎖 6.3 死鎖的檢測,死鎖檢測的實例

15、,AND模型下的Chandy-Misra-Hass算法中打破死鎖方法：,一種方法是由探測報文的發(fā)起者殺死自己，但是，當(dāng)有多個進(jìn)程同時檢測到同一個死鎖時，與同一個死鎖有關(guān)的多個進(jìn)程會被殺死，這樣做的效率會很低。 另一種方法是每個收到探測報文的進(jìn)程將自己的標(biāo)識符附加到探測報文的后面，當(dāng)探測報文回到發(fā)起者進(jìn)程時，發(fā)起者進(jìn)程選取一個具有最大標(biāo)識符號碼的進(jìn)程殺死，即使有多個進(jìn)程同時檢測到同一個死鎖，它們也會選擇殺死同一個進(jìn)程。,第六章 分布式系統(tǒng)中的死鎖 6.3 死鎖的檢測,死鎖檢測的實例,AND模型下的Mitchell-Merritt算法,Mitchell-Merritt算法與Chandy-Misra

16、-Hass算法的區(qū)別： 其限制是每個進(jìn)程每次只能請求一個資源。 探測報文在等待圖中，沿等待方向的相反方向傳送，這樣的圖叫反向等待圖(reversed wait-for graph)。 每當(dāng)進(jìn)程收到探測報文時，它將自己的標(biāo)識符和探測報文發(fā)起者的標(biāo)識符相比較，如果自己的標(biāo)識符大于探測報文發(fā)起者的標(biāo)識符，它就用自己的標(biāo)識符取代探測報文發(fā)起者的標(biāo)識符，自己變成探測報文的發(fā)起者。 當(dāng)幾個進(jìn)程同時發(fā)起死鎖檢測時，只有一個進(jìn)程能夠成為唯一的探測者。,第六章 分布式系統(tǒng)中的死鎖 6.3 死鎖的檢測,死鎖檢測的實例,AND模型下的Mitchell-Merritt算法,Mitchell-Merritt算法圖例說明

17、：,第六章 分布式系統(tǒng)中的死鎖 6.3 死鎖的檢測,死鎖檢測的實例,AND模型下的Mitchell-Merritt算法,為什么每個進(jìn)程每次只能請求一個資源？ 在每個進(jìn)程每次只能請求一個資源的情況下，等待圖中的一個循環(huán)中的每個節(jié)點都等待環(huán)內(nèi)的節(jié)點，所以只有進(jìn)入環(huán)內(nèi)的邊。其反向等待圖中則沒有進(jìn)入環(huán)內(nèi)的邊，就不會有大標(biāo)識符的進(jìn)程產(chǎn)生的探測報文進(jìn)入回路，而不能檢測出死鎖。,第六章 分布式系統(tǒng)中的死鎖 6.3 死鎖的檢測,死鎖檢測的實例,OR模型下的Chandy-Misra-Hass算法,使用兩類報文：(query,i,j,k)和(reply,i,j,k)，表示這些報文屬于由進(jìn)程Pi發(fā)起的并由Pj送往Pk的擴(kuò)散計算。 一個進(jìn)程的依賴集合包括所有它在等待以便獲得報文的進(jìn)程。如果接收進(jìn)程Pk是活動的，它會忽略所有的查詢和回答報文。如果它被阻塞，它會向它的依賴集合中的進(jìn)程發(fā)送查詢。 一旦收集到回答報文，接收進(jìn)程將向發(fā)起者發(fā)送一個回答報文。發(fā)起者以及每個中間進(jìn)程用一個計數(shù)器記錄查詢和回答的數(shù)目。如果這兩個數(shù)字相同，即發(fā)起者的每個查詢都得到了回答，就表明發(fā)起者處于死鎖狀態(tài)。,第六章 分布式系統(tǒng)中的死鎖 6.3 死鎖的檢測,死鎖檢測的實例,OR模型下的Chandy-Misra-Hass算法,當(dāng)接收進(jìn)程Pk處于阻塞狀態(tài)時，會有幾種可能： 如果這是Pi發(fā)起的第一個來自Pj的報文(這個報文的發(fā)送者