第7章死鎖的預(yù)防避免和檢測

1、死鎖問題 系統(tǒng)中有進程處于相互的無限等待狀態(tài)（被阻塞） 資源死鎖和通信死鎖 等待圖：將系統(tǒng)中進程對資源的占用與需求共享情況用有向圖表示 進程集合P0, P1 , Pn為節(jié)點集，當(dāng)且僅當(dāng)進程Pi等待一個被進程Pj占用的資源時，邊(Pi, Pj)存在于圖中。資源(resources)分類 根據(jù)資源性質(zhì)：可剝奪資源(搶占)和不可剝奪資源可搶占資源：指資源占有進程雖然需要使用該資源，但另一個進程卻強行把資源從占有者進程處搶來。不可搶占資源：指只有占用者進程不再需要使用該資源而主動釋放資源外，其它進程不得在占有者進程使用資源過程中強行搶占。 可搶占資源如：CPU、主存、硬盤，該類資源可為多個進程共享（可

2、搶占） 不可搶占資源如：打印機、讀卡機，磁帶驅(qū)動器，該類資源可為某個進程獨享（不可搶占）資源分類 根據(jù)使用方式：共享資源和獨享資源 根據(jù)使用期限：永久資源和臨時性資源永久資源是可順序重復(fù)使用的資源臨時性資源是由一個進程產(chǎn)生，被另外一個進程使用短暫時間之后便無用的資源。產(chǎn)生死鎖的原因 競爭資源。當(dāng)系統(tǒng)中供多個進程所共享的資源 ，不足以同時滿足它們的需要時，引起它們對資源的競爭而產(chǎn)生死鎖。 進程推進的順序不當(dāng)。進程在運行過程中，請求和釋放資源的順序不當(dāng)，導(dǎo)致進程的死鎖。競爭資源 競爭非剝奪性資源 競爭臨時性資源打印機R1磁帶機R2P1P2S1，S2，S3是臨時資源P1:Release(S1);Re

3、quest(S3)P2:Release(S2);Request(S1)P3:Release(S3);Request(S2)不可能發(fā)生死鎖P1:Request(S3) ; Release(S1)P2:Request(S1) ; Release(S2)P3:Request(S2) ; Release(S3)可能發(fā)生死鎖死鎖問題一實例：哲學(xué)家問題哲學(xué)家筷子盤子哲學(xué)家1號哲學(xué)家5號哲學(xué)家4號哲學(xué)家2號哲學(xué)家3號15324未就餐時示意圖未就餐時示意圖哲學(xué)家1號哲學(xué)家4號哲學(xué)家2號哲學(xué)家3號15324哲學(xué)家5號先拿左,拿到后再拿右,成功后進餐.吃完后先放左再放右.雖可保證不會有相鄰的同時進餐,但可能死鎖,

4、如動畫所示.此時沒有一個哲學(xué)家可以完成進餐.哲學(xué)家1號哲學(xué)家4號哲學(xué)家2號哲學(xué)家3號15324哲學(xué)家5號此時5號哲學(xué)家被禁止拿筷子.1號哲學(xué)家拿起他右邊即5號哲學(xué)家左邊的筷子.1號哲學(xué)家開始進餐,完成后放下筷子,其它哲學(xué)家開始進餐哲學(xué)家1號哲學(xué)家4號哲學(xué)家2號哲學(xué)家3號哲學(xué)家5號設(shè)1號進餐,則3,4兩位哲學(xué)家可以拿筷子1號進餐完畢,放下筷子,先左后右.1號放下左邊筷子的同時,3號可拿起右邊筷子3號開始進餐,同時1號放下右邊的筷子此時4號條件不再滿足,放下筷子.此時5號條件滿足,可在下一時鐘周期拿左筷子哲學(xué)家4號哲學(xué)家1號哲學(xué)家2號哲學(xué)家3號1524哲學(xué)家5號這種方法將出現(xiàn)1,2號哲學(xué)家單鍵1號

5、筷子,3,4號哲學(xué)家競爭3號筷子的情況.而5號沒有人與他競爭,得到左邊的筷子若4號在與3號的競爭中得到筷子,則與5號競爭4號筷子.無論無論4號號5號誰號誰得到得到4號筷子號筷子,都都有一個可以進餐有一個可以進餐若4號在與3號的競爭中沒有得到筷子,則5號得到4號筷子,進餐死鎖問題一條件 死鎖發(fā)生的充要條件 互斥：一個資源在同一時刻不能被共享； 占有并等待：必然有一個進程占用了至少一個資源，同時在等待獲得被其它進程占用的資源； 不可剝奪：已占用的資源不能被剝奪 循環(huán)等待：等待圖中有一個回路 死鎖的形式 AND條件：當(dāng)進程獲得所有所需的資源后才能繼續(xù)執(zhí)行 OR條件：當(dāng)進程至少獲得一個所需的資源后才能

6、繼續(xù)執(zhí)行 P-out-of-Q：進程同時請求Q個資源但至少獲得P個之后才能繼續(xù)執(zhí)行處理死鎖的策略死鎖的避免 動態(tài)檢查資源的分配情況，只有在結(jié)果狀態(tài)是安全的情況下，才將資源分配給進程；在分布式系統(tǒng)中實現(xiàn)的開銷較大 銀行家算法：至少總可以滿足一個客戶的要求 銀行共有資金800萬：A的余額是600萬，B的余額是400萬，C的余額是500萬；A要求一次提走300萬，B要求一次提走200萬，C要求一次提走100萬，假設(shè)客戶在存款后會立即重新全額存入。 當(dāng)以上提款要求被滿足后，銀行當(dāng)前存款余額還剩200萬。這時，A、B和C均要求提取剩余款，則服務(wù)次序BCA是安全的，其他的服務(wù)順序或上述條件的違反都可能導(dǎo)致

7、不安全的結(jié)果狀態(tài)。死鎖避免的方法 死鎖避免，即動態(tài)檢查資源狀態(tài)，以保證沒有循環(huán)等待發(fā)生。 在集中式系統(tǒng)中，銀行家算法是死鎖避免的一個經(jīng)典算法。 基于Petri網(wǎng)的死鎖避免方法適合應(yīng)用在分布式系統(tǒng)中。基于Petri網(wǎng)的死鎖避免方法步驟1)給出描述特定系統(tǒng)的模型2)得到相應(yīng)的Petri網(wǎng)的可達樹3)由可達樹確定死鎖狀態(tài)4)根據(jù)死鎖狀態(tài)，找到所有的臨界狀態(tài)和它們的抑制變遷。Petri網(wǎng)描述的狀態(tài) 安全狀態(tài)：包括臨界狀態(tài)和非臨界狀態(tài) 不安全狀態(tài)：包括死鎖狀態(tài)和死鎖邊界狀態(tài) 臨界狀態(tài)：如果一個狀態(tài)接近死鎖狀態(tài)但是仍可以到達其他不導(dǎo)致死鎖的狀態(tài)。 非臨界狀態(tài)：如果在某個狀態(tài)下總不會到達死鎖狀態(tài)，則稱該狀態(tài)

8、為非臨界狀態(tài)。 死鎖狀態(tài)：導(dǎo)致死鎖的不安全狀態(tài)稱為死鎖狀態(tài) 死鎖邊界狀態(tài)：可能導(dǎo)致死鎖的不安全狀態(tài)稱為死鎖邊界狀態(tài)。 死鎖的圖論模型死鎖的圖論模型 可以用圖模型來表示死鎖，表示死鎖的圖模型有兩種，一種是等待圖，另一種是資源分配圖。 在等待圖中，節(jié)點代表進程，當(dāng)且僅當(dāng)進程Pi等待一個被進程Pj所占用的資源時，邊(Pi,Pj)存在于等待圖中，圖中的邊是有向的。 資源分配圖中的節(jié)點有兩種：一種是進程節(jié)點，另一種是資源節(jié)點。每個邊是一個有序?qū)?Pi,Rj)或(Rj,Pi)，其中P代表進程，R代表一個資源類型。邊(Pi,Rj)表示進程Pi請求類型為Rj的一個資源，并且正在等待這個資源，一個資源類型中可能

9、有多個資源。邊(Rj,Pi)表示類型為Rj的一個資源已經(jīng)分配給進程Pi。由于等待圖假定一個資源類型中只有一個資源，所以資源分配圖是一個比等待圖更加有力的工具。 死鎖的圖論模型死鎖的圖論模型 資源分配圖實例： P1 P2 P3 P1 P2 P3 (a) 不處于死鎖狀態(tài) (b) 處于死鎖狀態(tài) R1 R2 R1 R2 死鎖的圖論模型死鎖的圖論模型 資源分配圖到等待圖的轉(zhuǎn)化：(1)在資源分配圖中找到一個未被處理的資源R。如果所有的資源都已經(jīng)處理，轉(zhuǎn)向步驟3。(2)從這個資源R的每個輸入進程節(jié)點到每個輸出進程節(jié)點之間加一條有向邊。一個資源的輸入進程節(jié)點是等待這個資源的進程節(jié)點，一個資源的輸出進程節(jié)點是占

10、有這個資源的進程節(jié)點。轉(zhuǎn)向步驟1。(3)刪除所有的資源節(jié)點以及相應(yīng)的邊。 死鎖的圖論模型死鎖的圖論模型 資源分配圖到等待圖的轉(zhuǎn)化實例： P4 P3 P2 P1 P5 R5 R4 R3 R2 R1 P4 P3 P2 P1 P5 (a) 資源分配圖 (b) 等待圖 處理死鎖的策略處理死鎖的策略可以使用PAID來概括死鎖處理的各種方法：預(yù)防(P Prevent)、避免(A Avoid)、忽略(I Ignore)和檢測(D Detect) 。預(yù)防死鎖。通過限制請求，保證四個死鎖條件中至少有一個不能發(fā)生，從而預(yù)防死鎖。避免死鎖。如果資源分配會導(dǎo)致一個安全的結(jié)果狀態(tài)，就將資源動態(tài)地分配給進程。如果至少有一

11、個執(zhí)行序列使所有的進程都能完成運行，那么這個狀態(tài)就是安全的。 忽略死鎖。忽略死鎖是UNIX常采用的一種方法，這種方法只是簡單地忽略死鎖問題。 1) 檢測死鎖和從死鎖中恢復(fù)。允許死鎖發(fā)生，然后發(fā)現(xiàn)并解除死鎖。 分布式系統(tǒng)處理死鎖的策略 基于死鎖預(yù)防的策略 基于死鎖檢測的策略 分布式系統(tǒng)死鎖的特點：由于信息散布在多臺機器上，死鎖難以檢測和處理。分布式系統(tǒng)預(yù)防死鎖的方法要求進程在開始執(zhí)行前就已經(jīng)獲得了所有了所有需要的資源。 所有資源都被唯一編號，進程必須按資源編號單調(diào)申請。 進程具有優(yōu)先級編號，優(yōu)先級低的首先放棄資源。 為了提高公平性，進程的優(yōu)先級可以動態(tài)變化。用預(yù)防策略解決哲學(xué)家問題 基于資源編號

12、：所有哲學(xué)家均要先拿編號大的叉子，再拿編號小的叉子，在沒有獲得大編號的叉子前，即使編號小的叉子沒有被占有，也不允許使用。 基于進程編號：優(yōu)先級高的哲學(xué)家可以等待優(yōu)先級低的哲學(xué)家的叉子，反之不然。即當(dāng)一個哲學(xué)家發(fā)現(xiàn)自己在等待另一個比自己有更高優(yōu)先級的哲學(xué)家的資源時，他必須放棄已經(jīng)控制的叉子。 基于時間戳的死鎖預(yù)防方法基于時間戳的死鎖預(yù)防方法等待死亡方案(wait-die scheme)。該方案是基于非剝奪方法。當(dāng)Pi要使用Pj正在使用的資源時，如果當(dāng)Pi比Pj老，則Pi等待Pj的結(jié)束(舍不得)；否則Pi回卷(不要了)。例如：假定進程p1，p2和p3分別有時間戳5，10和15，若p1申請已由p2占

13、有的資源，p1就等待；如果p3申請已由p2占有的資源，p3就被撤離。 2）傷害等待方案(wound-wait scheme)。它是一種基于剝奪的方法。當(dāng)Pi要使用Pj正在使用的資源時，如果當(dāng)Pi比Pj新，則Pi等待Pj的結(jié)束；否則Pj回卷(尊老)。 例如：假定進程p1，p2和p3分別有時間戳5，10和15，如果p1申請已由p2占有的資源，那么該資源從p2手中搶占，而且p2被撤離；如果p3申請已由p2占有的資源，則p2就等待。 等待-死亡預(yù)防方案圖示等待-死亡方案例題 例題：根據(jù)表1描述的5個進程的優(yōu)先級及請求時間等信息，用等待-死亡方案畫出時間軸上5個進程執(zhí)行的時間和先后順序。并說明進程之間的

14、等待關(guān)系。進程標(biāo)識優(yōu)先級第一次請求時間/h時間長度/h重試時間/hP12111P211.521P342.122P453.311P534.023P4P2P1P5P3P1P2等待P3殺死P4殺死321451.0 1.52.13.3P54.1P3殺死傷害-等待預(yù)防方案圖示 基于時間戳的預(yù)防死鎖方法基于時間戳的預(yù)防死鎖方法圖例說明：假設(shè)P1的時間戳小于P2的時間戳 P1 P2 R1 R2 (a) 年輕者請求年長者 占有的資源 P1 P2 R1 R2 (b) 年長者請求年輕者 占有的資源 P1 P2 R1 R2 (c) 年輕者請求年長者占有的資源， 同時， 年長者請求年輕者占有的資源 基于時間戳的死鎖預(yù)

15、防方法基于時間戳的死鎖預(yù)防方法 兩種方案的區(qū)別： 在“等待-死亡”方案中，年長的進程必須等待年輕的進程釋放它的資源，因此進程越“年長”，它就越容易引起等待。與此相反，在“因傷等待”方案中，年長的進程決不會等待年輕的進程。 在“等待-死亡”方案中，進程pi可能被撤離若干次。在“傷害-等待”方案中，進程pi撤離的次數(shù)較少。集中式死鎖檢測集中式死鎖檢測 使用一個協(xié)調(diào)者來集中檢測系統(tǒng)狀態(tài)，并消除出現(xiàn)的死鎖 利用各節(jié)點的局部等待圖在協(xié)調(diào)者建立全局等待圖當(dāng)在局部等待圖中有新的邊被加入或刪除時修改全局等待圖協(xié)調(diào)者定期檢查局部等待圖的變化協(xié)調(diào)者認(rèn)為有必要時運行回路檢查算法時缺點：如果不能保證狀態(tài)的一致性，則可

16、能會得出錯誤結(jié)論（假死鎖） 集中式死鎖檢測集中式死鎖檢測產(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 集中式死鎖檢測集中式死鎖檢測產(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)協(xié)調(diào)者 分布式死鎖檢測 每個節(jié)點獨立進行死鎖檢測 每個節(jié)點維持一個全局等待圖的拷貝 全局等待圖分解到若干個節(jié)點上進行維護，需要時通過消息交換組合起來。 路徑推動算法 在每個節(jié)點建立部分的全局等待圖，當(dāng)需要進行死鎖檢測時，節(jié)點將

17、自己的全局等待圖向鄰接點進行擴散；接到消息的節(jié)點用自己的等待圖信息完善全局等待圖并進行鄰接點擴散操作，直到在某節(jié)點形成最終的全局等待圖并將檢測結(jié)論通知各個節(jié)點。 狀態(tài)比較難一致，可能依據(jù)部分等待圖來判斷分布式死鎖檢測 邊跟蹤算法：各節(jié)點將自己的資源需求作為探測器沿依賴關(guān)系發(fā)送出去，如果某節(jié)點收到自己發(fā)出的探測器，則表明存在資源依賴回路。 擴散計算算法：當(dāng)需要檢測時，進程向它所依賴的進程發(fā)起詢問，并將因此而引發(fā)的各個詢問關(guān)聯(lián)成等待圖，或者通過接收應(yīng)答將圖消解，或者從中發(fā)現(xiàn)死鎖。 全局狀態(tài)檢測：通過建立一致的全局狀態(tài)圖來檢測是否有死鎖發(fā)生。等級式死鎖檢測 死鎖檢測和恢復(fù)的研究方向死鎖檢測和恢復(fù)的研

18、究方向算法正確性。通常由于報文的傳輸延遲是不可預(yù)料的，嚴(yán)格證明死鎖檢測算法的正確性有難度。算法性能。需要在信息流量(監(jiān)測和恢復(fù)算法的復(fù)雜性)和死鎖持續(xù)時間(監(jiān)測和恢復(fù)的速度)之間達成妥協(xié)。 死鎖解決。一個好而快的死鎖檢測算法可能并不能提供足夠的信息用于解決死鎖。 假死鎖。一個檢測程序不僅要滿足前進要求，即必須在有限的時間內(nèi)發(fā)現(xiàn)死鎖，還要滿足安全要求。如果一個死鎖被發(fā)現(xiàn)，那么這個死鎖應(yīng)該是確實存在的。 死鎖概率。檢測和恢復(fù)算法的設(shè)計依賴于給定系統(tǒng)中死鎖發(fā)生的概率。 死鎖檢測算法死鎖檢測算法 ANDAND模型下的模型下的Chandy-Misra-HassChandy-Misra-Hass算法算法

19、基本思想：l在等待圖中，將探測報文(probe message)從一個進程發(fā)送到另一個進程。l如果報文回到發(fā)起者，那么就有死鎖存在。l探測報文包含一個三元組(i,j,k)，表示該報文是一個由進程Pi發(fā)起的死鎖檢測報文，現(xiàn)在由進程Pj所在的站點發(fā)往進程Pk所在的站點。 l當(dāng)一個進程接收到一個探測報文時，如果該進程正在等待某個(或某些)進程，它將向某個(或某些)等待的進程轉(zhuǎn)發(fā)探測報文。 v死鎖檢測的實例死鎖檢測的實例ANDAND模型下的模型下的Chandy-Misra-HassChandy-Misra-Hass算法圖例說明：算法圖例說明： P1 P2 P3 P4 P5 P6 P7 站點 A 站點

20、B 站點 C (1,2,3) (1,3,7) (1,5,6) (1,6,1) (1,1,2) (1,3,4) (1,4,5) v死鎖檢測的實例死鎖檢測的實例ANDAND模型下的模型下的Chandy-Misra-HassChandy-Misra-Hass算法中打破死鎖方法：算法中打破死鎖方法： 如果檢測到死鎖，則由探測報文的發(fā)起者殺死自己。存在問題：當(dāng)有多個進程同時檢測到同一個死鎖時，與同一個死鎖有關(guān)的多個進程會被殺死。解決方法：每個收到探測報文的進程將自己的標(biāo)識符附加到探測報文的后面，當(dāng)探測報文回到發(fā)起者進程時，發(fā)起者進程選取一個具有最大標(biāo)識符號碼的進程殺死，即使有多個進程同時檢測到同一個死鎖，它們也會選擇殺死同一個進程。 v死鎖檢測的實例死鎖檢測的實例OROR模型下的模型下的Chandy-Misra-HassChandy-Misra-Hass算法算法 使用兩類報文：(query,i,j,k)和(reply,i,j,k)，表示這些報文屬于由進程Pi發(fā)起的并由Pj送往Pk的擴散計算。 如果接收進程Pk是活動的，它會忽略所有的查詢和回答報文。如果它被阻塞，它會向它的依賴集合中的進程發(fā)送查詢。 發(fā)起者的每個