分布式系統(tǒng)中的死鎖課件

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

2、式系統(tǒng)中的死鎖 6.1 6.1 死鎖問題死鎖問題 v死鎖的圖論模型死鎖的圖論模型 可以用圖模型來表示死鎖，表示死鎖的圖模型有兩種，一種是等待圖，另一種是資源分配圖。 在等待圖中，節(jié)點代表進程，當且僅當進程Pi等待一個被進程Pj所占用的資源時，邊(Pi,Pj)存在于等待圖中，圖中的邊是有向的。 資源分配圖中的節(jié)點有兩種：一種是進程節(jié)點，另一種是資源節(jié)點。每個邊是一個有序?qū)?Pi,Rj)或(Rj,Pi)，其中P代表進程，R代表一個資源類型。邊(Pi,Rj)表示進程Pi請求類型為Rj的一個資源，并且正在等待這個資源，一個資源類型中可能有多個資源。邊(Rj,Pi)表示類型為Rj的一個資源已經(jīng)分配給進程

3、Pi。由于等待圖假定一個資源類型中只有一個資源，所以資源分配圖是一個比等待圖更加有力的工具。 分布式系統(tǒng)中的死鎖第六章第六章 分布式系統(tǒng)中的死鎖分布式系統(tǒng)中的死鎖 6.1 6.1 死鎖問題死鎖問題 v死鎖的圖論模型死鎖的圖論模型 資源分配圖實例： P1 P2 P3 P1 P2 P3 (a) 不處于死鎖狀態(tài) (b) 處于死鎖狀態(tài) R1 R2 R1 R2 分布式系統(tǒng)中的死鎖第六章第六章 分布式系統(tǒng)中的死鎖分布式系統(tǒng)中的死鎖 6.1 6.1 死鎖問題死鎖問題 v死鎖的圖論模型死鎖的圖論模型 資源分配圖到等待圖的轉(zhuǎn)化：(1)在資源分配圖中找到一個未被處理的資源R。如果所有的資源都已經(jīng)處理，轉(zhuǎn)向步驟3。

4、(2)從這個資源R的每個輸入進程節(jié)點到每個輸出進程節(jié)點之間加一條有向邊。一個資源的輸入進程節(jié)點是等待這個資源的進程節(jié)點，一個資源的輸出進程節(jié)點是占有這個資源的進程節(jié)點。轉(zhuǎn)向步驟1。(3)刪除所有的資源節(jié)點以及相應(yīng)的邊。分布式系統(tǒng)中的死鎖第六章第六章 分布式系統(tǒng)中的死鎖分布式系統(tǒng)中的死鎖 6.1 6.1 死鎖問題死鎖問題 v死鎖的圖論模型死鎖的圖論模型 資源分配圖到等待圖的轉(zhuǎn)化實例： P4 P3 P2 P1 P5 R5 R4 R3 R2 R1 P4 P3 P2 P1 P5 (a) 資源分配圖 (b) 等待圖 分布式系統(tǒng)中的死鎖第六章第六章 分布式系統(tǒng)中的死鎖分布式系統(tǒng)中的死鎖 6.1 6.1 死

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

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

7、K中的任何節(jié)點a，a能到達K中的所有節(jié)點，并且只能到達K中的節(jié)點。 分布式系統(tǒng)中的死鎖第六章第六章 分布式系統(tǒng)中的死鎖分布式系統(tǒng)中的死鎖 6.1 6.1 死鎖問題死鎖問題 v死鎖的死鎖的ANDAND條件和條件和OROR條件條件 OR條件死鎖圖例： P1 P2 P3 P4 P5 (a) 無死鎖 P1 P2 P3 P4 P5 (b) 有死鎖 分布式系統(tǒng)中的死鎖第六章第六章 分布式系統(tǒng)中的死鎖分布式系統(tǒng)中的死鎖 6.2 6.2 死鎖的預(yù)防死鎖的預(yù)防 v預(yù)防死鎖的一般方法預(yù)防死鎖的一般方法死鎖預(yù)防算法是通過限制進程的資源請求來達到預(yù)防死鎖的目的，都是通過打破四個死鎖條件中的一個條件來實現(xiàn)的。 進程在開

8、始執(zhí)行之前同時獲得所有所需資源。這種方法打破了占有并等待的條件。 所有的資源都要被賦予一個唯一的數(shù)字編號。一個進程可以請求一個有唯一編號i的資源，條件是該進程沒有占用編號小于或等于i的資源。這樣，就打破了循環(huán)等待的條件。 每個進程被賦予一個唯一的優(yōu)先級標識。優(yōu)先級標識決定了進程Pi是否應(yīng)該等待進程Pj，從而打破了不可剝奪的條件。 分布式系統(tǒng)中的死鎖第六章第六章 分布式系統(tǒng)中的死鎖分布式系統(tǒng)中的死鎖 6.2 6.2 死鎖的預(yù)防死鎖的預(yù)防 v基于時間戳的預(yù)防死鎖方法基于時間戳的預(yù)防死鎖方法包括兩種死鎖預(yù)防方案。這兩種方案相互補充，這種方法常用于分布式數(shù)據(jù)庫系統(tǒng)中。 等待死亡方案(wait-die

9、scheme)。該方案是基于非剝奪方法。當進程Pi請求的資源正被進程Pj占有時，只有當Pi的時間戳比進程Pj的時間戳小時，即Pi比Pj老時，Pi才能等待。否則Pi被卷回(roll-back)，即死亡。 傷害等待方案(wound-wait scheme)。它是一種基于剝奪的方法。當進程Pi請求的資源正被進程Pj占有時，只有當進程Pi的時間戳比進程Pj的時間戳大時，即Pi比Pj年輕時，Pi才能等待。否則Pj被卷回(roll-back)，即死亡。 分布式系統(tǒng)中的死鎖第六章第六章 分布式系統(tǒng)中的死鎖分布式系統(tǒng)中的死鎖 6.2 6.2 死鎖的預(yù)防死鎖的預(yù)防 v基于時間戳的預(yù)防死鎖方法基于時間戳的預(yù)防死鎖

10、方法圖例說明： P1 P2 R1 R2 (a) 年輕者請求年長者 占有的資源 P1 P2 R1 R2 (b) 年長者請求年輕者 占有的資源 P1 P2 R1 R2 (c) 年輕者請求年長者占有的資源， 同時， 年長者請求年輕者占有的資源 分布式系統(tǒng)中的死鎖第六章第六章 分布式系統(tǒng)中的死鎖分布式系統(tǒng)中的死鎖 6.3 6.3 死鎖的檢測死鎖的檢測v集中式死鎖檢測集中式死鎖檢測在集中式死鎖檢測方法中，利用所有的局部資源分配圖(或等待圖)建立一個全局資源分配圖(或等待圖)。任何一個機器為它自己的進程和資源維持一個局部的資源分配圖。整個系統(tǒng)只有一個協(xié)調(diào)者，它維持全局的資源分配圖，全局的資源分配圖是由局部

11、資源分配圖組合而成的。 分布式系統(tǒng)中的死鎖第六章第六章 分布式系統(tǒng)中的死鎖分布式系統(tǒng)中的死鎖 6.3 6.3 死鎖的檢測死鎖的檢測v集中式死鎖檢測集中式死鎖檢測全局資源分配圖(或等待圖)的獲得方法：當在局部圖中有邊被加入或刪除時，向協(xié)調(diào)者發(fā)送一個報文，協(xié)調(diào)者根據(jù)報文信息對全局圖進行更新。 定期地更新，每個機器定期地向協(xié)調(diào)者發(fā)送自上次更新以來所有添加的邊和刪除的邊，協(xié)調(diào)者根據(jù)報文信息對全局圖進行更新。當協(xié)調(diào)者認為需要運行回路檢測算法時，它要求所有的機器向它發(fā)送局部圖的更新信息，協(xié)調(diào)者對全局圖進行更新。當開始死鎖檢測時，協(xié)調(diào)者便查找全局等待圖。如果發(fā)現(xiàn)回路，一個進程就會被卷回，從而打破循環(huán)等待。

12、1) 缺點：容易產(chǎn)生假死鎖的情況 。 分布式系統(tǒng)中的死鎖第六章第六章 分布式系統(tǒng)中的死鎖分布式系統(tǒng)中的死鎖 6.3 6.3 死鎖的檢測死鎖的檢測v集中式死鎖檢測集中式死鎖檢測產(chǎn)生假死鎖的圖例說明： A S R B (a)機器 0 C S T (b)機器 1 C S A R B T (c)協(xié)調(diào)者 A S R B (d)機器 0 T 分布式系統(tǒng)中的死鎖第六章第六章 分布式系統(tǒng)中的死鎖分布式系統(tǒng)中的死鎖 6.3 6.3 死鎖的檢測死鎖的檢測v集中式死鎖檢測集中式死鎖檢測產(chǎn)生假死鎖的圖例說明： C S T (e)機器 1 C S A R B T (g)協(xié)調(diào)者：假死鎖 B A S C T R B (f)

13、協(xié)調(diào)者 分布式系統(tǒng)中的死鎖第六章第六章 分布式系統(tǒng)中的死鎖分布式系統(tǒng)中的死鎖 6.3 6.3 死鎖的檢測死鎖的檢測v分布式死鎖檢測分布式死鎖檢測Knapp將分布式死鎖檢測算法分為以下四類：路徑推動算法(path-pushing algorithm)。先在每個機器上建立形式簡單的全局等待圖。每當進行死鎖檢測時，各個機器就將等待圖的拷貝送往一定數(shù)量的鄰居節(jié)點。局部拷貝更新后又被傳播下去。這一過程重復(fù)進行直到某個節(jié)點獲得了足夠的信息來構(gòu)造一個等待圖以便做出是否存在死鎖的結(jié)論。1) 邊跟蹤算法(edge-chasing algorithm)。分布式網(wǎng)絡(luò)結(jié)構(gòu)圖中的回路可以通過沿圖的邊傳播一種叫探測器的特

14、殊信息來檢測。當一個發(fā)起者得到一個與自己發(fā)送的探測器相匹配的探測器時，它就知道它在圖中的一個回路里。 分布式系統(tǒng)中的死鎖第六章第六章 分布式系統(tǒng)中的死鎖分布式系統(tǒng)中的死鎖 6.3 6.3 死鎖的檢測死鎖的檢測v分布式死鎖檢測分布式死鎖檢測Knapp將分布式死鎖檢測算法分為以下四類：擴散計算(diffusing computation)。懷疑有死鎖發(fā)生時，事務(wù)管理器通過向依賴于它的進程發(fā)送查詢啟動一個擴散進程。這里不會生成全局等待圖。發(fā)送查詢信息時，擴散計算就增長；接收回答后，擴散計算就縮減。根據(jù)所得信息，發(fā)起者會檢測到死鎖的發(fā)生。 3) 全局狀態(tài)檢測(global state detectio

15、n)。這個方法基于Chandy和Lamport 的快照方法?？梢酝ㄟ^建立一個一致的全局狀態(tài)而無需暫停當前的計算來生成一個一致的全局等待圖。 分布式系統(tǒng)中的死鎖第六章第六章 分布式系統(tǒng)中的死鎖分布式系統(tǒng)中的死鎖 6.3 6.3 死鎖的檢測死鎖的檢測v層級式死鎖檢測層級式死鎖檢測在層級式死鎖檢測算法中，站點被分層地放在一個樹中。一個站點的死鎖檢測只涉及到它的下一級站點。例如，設(shè)A、B和C是控制器，而C是A和B的最低的公共祖先。假定節(jié)點Pi出現(xiàn)在控制器A和B的局部等待圖中，那么節(jié)點Pi也必定出現(xiàn)在如下控制器的等待圖中： (1) C控制器；(2) 所有位于從C到A的路徑上的控制器；(3) 所有位于從C

16、到B的路徑上的控制器。 而且，如果Pi和Pj出現(xiàn)在控制器D的等待圖中，并且在D的一個下一級控制器(子控制器)的等待圖中有一條從Pi到Pj的路徑，那么邊(Pi,Pj)一定存在于D的等待圖中。 分布式系統(tǒng)中的死鎖第六章第六章 分布式系統(tǒng)中的死鎖分布式系統(tǒng)中的死鎖 6.3 6.3 死鎖的檢測死鎖的檢測v關(guān)于死鎖檢測和恢復(fù)的研究方向：關(guān)于死鎖檢測和恢復(fù)的研究方向：算法正確性。嚴格證明死鎖檢測算法的正確性是困難的，由于報文的傳輸延遲是不可預(yù)料的，所以得到一致的全局狀態(tài)是很困難的。 算法性能。需要在信息流量(監(jiān)測和恢復(fù)算法的復(fù)雜性)和死鎖持續(xù)時間(監(jiān)測和恢復(fù)的速度)之間達成妥協(xié)。 死鎖解決。一個好而快的死

17、鎖檢測算法可能并不能提供足夠的信息用于解決死鎖。 假死鎖。一個檢測程序不僅要滿足前進要求，即必須在有限的時間內(nèi)發(fā)現(xiàn)死鎖，還要滿足安全要求。如果一個死鎖被發(fā)現(xiàn)，那么這個死鎖應(yīng)該是確實存在的。 死鎖概率。檢測和恢復(fù)算法的設(shè)計依賴于給定系統(tǒng)中死鎖發(fā)生的概率。 分布式系統(tǒng)中的死鎖第六章第六章 分布式系統(tǒng)中的死鎖分布式系統(tǒng)中的死鎖 6.3 6.3 死鎖的檢測死鎖的檢測v死鎖檢測的實例死鎖檢測的實例 ANDAND模型下的模型下的Chandy-Misra-HassChandy-Misra-Hass算法算法 在Chandy-Misra-Hass算法中，分布式死鎖檢測算法使用一個特殊的報文，在等待圖中該報文從一

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

19、andy-Misra-Hass算法圖例說明：算法圖例說明： P1 P2 P3 P4 P5 P6 P7 站點 A 站點 B 站點 C (1,2,3) (1,3,7) (1,5,6) (1,6,1) (1,1,2) (1,3,4) (1,4,5) 分布式系統(tǒng)中的死鎖第六章第六章 分布式系統(tǒng)中的死鎖分布式系統(tǒng)中的死鎖 6.3 6.3 死鎖的檢測死鎖的檢測v死鎖檢測的實例死鎖檢測的實例 ANDAND模型下的模型下的Chandy-Misra-HassChandy-Misra-Hass算法中打破死鎖方法：算法中打破死鎖方法： 一種方法是由探測報文的發(fā)起者殺死自己，但是，當有多個進程同時檢測到同一個死鎖時，

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

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

22、型下的模型下的Mitchell-MerrittMitchell-Merritt算法算法Mitchell-Merritt算法圖例說明： P5 P1 P2 P3 P4 P5 P1 P2 P3 P4 (a) 等待圖 (b) 反向等待圖 分布式系統(tǒng)中的死鎖第六章第六章 分布式系統(tǒng)中的死鎖分布式系統(tǒng)中的死鎖 6.3 6.3 死鎖的檢測死鎖的檢測v死鎖檢測的實例死鎖檢測的實例 ANDAND模型下的模型下的Mitchell-MerrittMitchell-Merritt算法算法為什么每個進程每次只能請求一個資源？在每個進程每次只能請求一個資源的情況下，等待圖中的一個循環(huán)中的每個節(jié)點都等待環(huán)內(nèi)的節(jié)點，所以只有

23、進入環(huán)內(nèi)的邊。其反向等待圖中則沒有進入環(huán)內(nèi)的邊，就不會有大標識符的進程產(chǎn)生的探測報文進入回路，而不能檢測出死鎖。 分布式系統(tǒng)中的死鎖第六章第六章 分布式系統(tǒng)中的死鎖分布式系統(tǒng)中的死鎖 6.3 6.3 死鎖的檢測死鎖的檢測v死鎖檢測的實例死鎖檢測的實例OROR模型下的模型下的Chandy-Misra-HassChandy-Misra-Hass算法算法 使用兩類報文：(query,i,j,k)和(reply,i,j,k)，表示這些報文屬于由進程Pi發(fā)起的并由Pj送往Pk的擴散計算。 一個進程的依賴集合包括所有它在等待以便獲得報文的進程。如果接收進程Pk是活動的，它會忽略所有的查詢和回答報文。如果它

24、被阻塞，它會向它的依賴集合中的進程發(fā)送查詢。 一旦收集到回答報文，接收進程將向發(fā)起者發(fā)送一個回答報文。發(fā)起者以及每個中間進程用一個計數(shù)器記錄查詢和回答的數(shù)目。如果這兩個數(shù)字相同，即發(fā)起者的每個查詢都得到了回答，就表明發(fā)起者處于死鎖狀態(tài)。 分布式系統(tǒng)中的死鎖第六章第六章 分布式系統(tǒng)中的死鎖分布式系統(tǒng)中的死鎖 6.3 6.3 死鎖的檢測死鎖的檢測v死鎖檢測的實例死鎖檢測的實例OROR模型下的模型下的Chandy-Misra-HassChandy-Misra-Hass算法算法 當接收進程Pk處于阻塞狀態(tài)時，會有幾種可能： 如果這是Pi發(fā)起的第一個來自Pj的報文(這個報文的發(fā)送者Pj叫做Pk關(guān)于Pi的結(jié)合者)，它將向它的依賴集合中的所有進程發(fā)送這個查詢，并且將查詢數(shù)目存儲在一個局部變量num(i)中。令局部變量wait(i)表示這一進程從它接收到它的第一個由Pi發(fā)起的查詢起一直被阻塞這一事實。 如果這個查詢是Pi發(fā)起的但不是第一個來自Pj的報文，即當wait(i)仍然成立時，Pk將馬