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

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

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

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

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

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

7、。這兩種方案相互補充，這種方法常用于分布式數(shù)據(jù)庫系統(tǒng)中。,等待死亡方案(wait-die 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)中的死鎖 6.2 死鎖的預防,基于時間戳的預防

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

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

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

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

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 死鎖的檢測,關于死鎖檢測和恢復的研究方向：,算法正確性。嚴格證明死鎖檢測算法的正確性是困難的，由于報文的傳輸延遲是不可預料的，所以得到一致的全局狀

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

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

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

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

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