第7章 死鎖的預防避免和檢測課件

死鎖問題?系統(tǒng)中有進程處于相互的無限等待狀態(tài)（被阻塞）?資源死鎖和通信死鎖?等待圖：將系統(tǒng)中進程對資源的占用與需求共享情況用有向圖表示–進程集合{P0,P1,……,Pn}為節(jié)點集，當且僅當進程Pi等待一個被進程Pj占用的資源時，邊(Pi,Pj)存在于圖中。第7章死鎖的預防避免和檢測資源(resources)分類根據資源性質：可剝奪資源(搶占)和不可剝奪資源可搶占資源：指資源占有進程雖然需要使用該資源，但另一個進程卻強行把資源從占有者進程處搶來。不可搶占資源：指只有占用者進程不再需要使用該資源而主動釋放資源外，其它進程不得在占有者進程使用資源過程中強行搶占。第7章死鎖的預防避免和檢測可搶占資源如：CPU、主存、硬盤，該類資源可為多個進程共享（可搶占）不可搶占資源如：打印機、讀卡機，磁帶驅動器，該類資源可為某個進程獨享（不可搶占）第7章死鎖的預防避免和檢測資源分類根據使用方式：共享資源和獨享資源根據使用期限：永久資源和臨時性資源永久資源是可順序重復使用的資源臨時性資源是由一個進程產生，被另外一個進程使用短暫時間之后便無用的資源。第7章死鎖的預防避免和檢測產生死鎖的原因競爭資源。當系統(tǒng)中供多個進程所共享的資源，不足以同時滿足它們的需要時，引起它們對資源的競爭而產生死鎖。進程推進的順序不當。進程在運行過程中，請求和釋放資源的順序不當，導致進程的死鎖。第7章死鎖的預防避免和檢測競爭資源競爭非剝奪性資源競爭臨時性資源打印機R1磁帶機R2P1P2第7章死鎖的預防避免和檢測S1，S2，S3是臨時資源P1:Release(S1);Request(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ā)生死鎖第7章死鎖的預防避免和檢測死鎖問題一實例：哲學家問題第7章死鎖的預防避免和檢測哲學家筷子盤子哲學家1號哲學家5號哲學家4號哲學家2號哲學家3號15324未就餐時示意圖第7章死鎖的預防避免和檢測哲學家1號哲學家4號哲學家2號哲學家3號15324哲學家5號先拿左,拿到后再拿右,成功后進餐.吃完后先放左再放右.雖可保證不會有相鄰的同時進餐,但可能死鎖,如動畫所示.此時沒有一個哲學家可以完成進餐.第7章死鎖的預防避免和檢測哲學家1號哲學家4號哲學家2號哲學家3號15324哲學家5號此時5號哲學家被禁止拿筷子.1號哲學家拿起他右邊即5號哲學家左邊的筷子.解決方法一:至多只允許四位哲學家同時去拿左邊的筷子1號哲學家開始進餐,完成后放下筷子,其它哲學家開始進餐第7章死鎖的預防避免和檢測哲學家1號哲學家4號哲學家2號哲學家3號哲學家5號解決方法二:僅當哲學家左右兩邊筷子都能用才允許拿筷子設1號進餐,則3,4兩位哲學家可以拿筷子1號進餐完畢,放下筷子,先左后右.1號放下左邊筷子的同時,3號可拿起右邊筷子3號開始進餐,同時1號放下右邊的筷子此時4號條件不再滿足,放下筷子.此時5號條件滿足,可在下一時鐘周期拿左筷子第7章死鎖的預防避免和檢測哲學家4號哲學家1號哲學家2號哲學家3號1524哲學家5號解決方法三:奇數(shù)先拿左邊,偶數(shù)先拿右邊這種方法將出現(xiàn)1,2號哲學家單鍵1號筷子,3,4號哲學家競爭3號筷子的情況.而5號沒有人與他競爭,得到左邊的筷子若4號在與3號的競爭中得到筷子,則與5號競爭4號筷子.無論4號5號誰得到4號筷子,都有一個可以進餐若4號在與3號的競爭中沒有得到筷子,則5號得到4號筷子,進餐第7章死鎖的預防避免和檢測死鎖問題一條件?死鎖發(fā)生的充要條件–互斥：一個資源在同一時刻不能被共享；–占有并等待：必然有一個進程占用了至少一個資源，同時在等待獲得被其它進程占用的資源；–不可剝奪：已占用的資源不能被剝奪–循環(huán)等待：等待圖中有一個回路?死鎖的形式–AND條件：當進程獲得所有所需的資源后才能繼續(xù)執(zhí)行–OR條件：當進程至少獲得一個所需的資源后才能繼續(xù)執(zhí)行–P-out-of-Q：進程同時請求Q個資源但至少獲得P個之后才能繼續(xù)執(zhí)行第7章死鎖的預防避免和檢測處理死鎖的策略—死鎖的避免動態(tài)檢查資源的分配情況，只有在結果狀態(tài)是安全的情況下，才將資源分配給進程；在分布式系統(tǒng)中實現(xiàn)的開銷較大銀行家算法：至少總可以滿足一個客戶的要求銀行共有資金800萬：A的余額是600萬，B的余額是400萬，C的余額是500萬；A要求一次提走300萬，B要求一次提走200萬，C要求一次提走100萬，假設客戶在存款后會立即重新全額存入。當以上提款要求被滿足后，銀行當前存款余額還剩200萬。這時，A、B和C均要求提取剩余款，則服務次序B→C→A是安全的，其他的服務順序或上述條件的違反都可能導致不安全的結果狀態(tài)。第7章死鎖的預防避免和檢測死鎖避免的方法死鎖避免，即動態(tài)檢查資源狀態(tài)，以保證沒有循環(huán)等待發(fā)生。在集中式系統(tǒng)中，銀行家算法是死鎖避免的一個經典算法?；赑etri網的死鎖避免方法適合應用在分布式系統(tǒng)中。第7章死鎖的預防避免和檢測基于Petri網的死鎖避免方法步驟1)給出描述特定系統(tǒng)的模型2)得到相應的Petri網的可達樹3)由可達樹確定死鎖狀態(tài)4)根據死鎖狀態(tài)，找到所有的臨界狀態(tài)和它們的抑制變遷。第7章死鎖的預防避免和檢測Petri網描述的狀態(tài)安全狀態(tài)：包括臨界狀態(tài)和非臨界狀態(tài)不安全狀態(tài)：包括死鎖狀態(tài)和死鎖邊界狀態(tài)臨界狀態(tài)：如果一個狀態(tài)接近死鎖狀態(tài)但是仍可以到達其他不導致死鎖的狀態(tài)。非臨界狀態(tài)：如果在某個狀態(tài)下總不會到達死鎖狀態(tài)，則稱該狀態(tài)為非臨界狀態(tài)。死鎖狀態(tài)：導致死鎖的不安全狀態(tài)稱為死鎖狀態(tài)死鎖邊界狀態(tài)：可能導致死鎖的不安全狀態(tài)稱為死鎖邊界狀態(tài)。第7章死鎖的預防避免和檢測

死鎖的圖論模型

可以用圖模型來表示死鎖，表示死鎖的圖模型有兩種，一種是等待圖，另一種是資源分配圖。

在等待圖中，節(jié)點代表進程，當且僅當進程Pi等待一個被進程Pj所占用的資源時，邊(Pi,Pj)存在于等待圖中，圖中的邊是有向的。資源分配圖中的節(jié)點有兩種：一種是進程節(jié)點，另一種是資源節(jié)點。每個邊是一個有序對(Pi,Rj)或(Rj,Pi)，其中P代表進程，R代表一個資源類型。邊(Pi,Rj)表示進程Pi請求類型為Rj的一個資源，并且正在等待這個資源，一個資源類型中可能有多個資源。邊(Rj,Pi)表示類型為Rj的一個資源已經分配給進程Pi。由于等待圖假定一個資源類型中只有一個資源，所以資源分配圖是一個比等待圖更加有力的工具。第7章死鎖的預防避免和檢測

死鎖的圖論模型

資源分配圖實例：第7章死鎖的預防避免和檢測

死鎖的圖論模型

資源分配圖到等待圖的轉化：(1)在資源分配圖中找到一個未被處理的資源R。如果所有的資源都已經處理，轉向步驟3。(2)從這個資源R的每個輸入進程節(jié)點到每個輸出進程節(jié)點之間加一條有向邊。一個資源的輸入進程節(jié)點是等待這個資源的進程節(jié)點，一個資源的輸出進程節(jié)點是占有這個資源的進程節(jié)點。轉向步驟1。(3)刪除所有的資源節(jié)點以及相應的邊。第7章死鎖的預防避免和檢測

死鎖的圖論模型

資源分配圖到等待圖的轉化實例：第7章死鎖的預防避免和檢測

處理死鎖的策略可以使用PAID來概括死鎖處理的各種方法：預防(Prevent)、避免(Avoid)、忽略(Ignore)和檢測(Detect)。預防死鎖。通過限制請求，保證四個死鎖條件中至少有一個不能發(fā)生，從而預防死鎖。避免死鎖。如果資源分配會導致一個安全的結果狀態(tài)，就將資源動態(tài)地分配給進程。如果至少有一個執(zhí)行序列使所有的進程都能完成運行，那么這個狀態(tài)就是安全的。忽略死鎖。忽略死鎖是UNIX常采用的一種方法，這種方法只是簡單地忽略死鎖問題。檢測死鎖和從死鎖中恢復。允許死鎖發(fā)生，然后發(fā)現(xiàn)并解除死鎖。第7章死鎖的預防避免和檢測分布式系統(tǒng)處理死鎖的策略基于死鎖預防的策略基于死鎖檢測的策略分布式系統(tǒng)死鎖的特點：由于信息散布在多臺機器上，死鎖難以檢測和處理。第7章死鎖的預防避免和檢測分布式系統(tǒng)預防死鎖的方法要求進程在開始執(zhí)行前就已經獲得了所有了所有需要的資源。所有資源都被唯一編號，進程必須按資源編號單調申請。進程具有優(yōu)先級編號，優(yōu)先級低的首先放棄資源。為了提高公平性，進程的優(yōu)先級可以動態(tài)變化。第7章死鎖的預防避免和檢測用預防策略解決哲學家問題基于資源編號：所有哲學家均要先拿編號大的叉子，再拿編號小的叉子，在沒有獲得大編號的叉子前，即使編號小的叉子沒有被占有，也不允許使用?；谶M程編號：優(yōu)先級高的哲學家可以等待優(yōu)先級低的哲學家的叉子，反之不然。即當一個哲學家發(fā)現(xiàn)自己在等待另一個比自己有更高優(yōu)先級的哲學家的資源時，他必須放棄已經控制的叉子。第7章死鎖的預防避免和檢測

基于時間戳的死鎖預防方法等待—死亡方案(wait-diescheme)。該方案是基于非剝奪方法。當Pi要使用Pj正在使用的資源時，如果當Pi比Pj老，則Pi等待Pj的結束(舍不得)；否則Pi回卷(不要了)。例如：假定進程p1，p2和p3分別有時間戳5，10和15，若p1申請已由p2占有的資源，p1就等待；如果p3申請已由p2占有的資源，p3就被撤離。

2）傷害—等待方案(wound-waitscheme)。它是一種基于剝奪的方法。當Pi要使用Pj正在使用的資源時，如果當Pi比Pj新，則Pi等待Pj的結束；否則Pj回卷(尊老)。

例如：假定進程p1，p2和p3分別有時間戳5，10和15，如果p1申請已由p2占有的資源，那么該資源從p2手中搶占，而且p2被撤離；如果p3申請已由p2占有的資源，則p2就等待。第7章死鎖的預防避免和檢測等待-死亡預防方案圖示第7章死鎖的預防避免和檢測等待-死亡方案例題例題：根據表1描述的5個進程的優(yōu)先級及請求時間等信息，用等待-死亡方案畫出時間軸上5個進程執(zhí)行的時間和先后順序。并說明進程之間的等待關系。第7章死鎖的預防避免和檢測進程標識優(yōu)先級第一次請求時間/h時間長度/h重試時間/hP12111P211.521P342.122P453.311P534.023P4P2P1P5P3P1P2等待P3殺死P4殺死321451.01.52.13.3P54.1P3殺死第7章死鎖的預防避免和檢測傷害-等待預防方案圖示第7章死鎖的預防避免和檢測

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

集中式死鎖檢測產生假死鎖的圖例說明：第7章死鎖的預防避免和檢測

集中式死鎖檢測產生假死鎖的圖例說明：第7章死鎖的預防避免和檢測分布式死鎖檢測每個節(jié)點獨立進行死鎖檢測每個節(jié)點維持一個全局等待圖的拷貝全局等待圖分解到若干個節(jié)點上進行維護，需要時通過消息交換組合起來。路徑推動算法在每個節(jié)點建立部分的全局等待圖，當需要進行死鎖檢測時，節(jié)點將自己的全局等待圖向鄰接點進行擴散；接到消息的節(jié)點用自己的等待圖信息完善全局等待圖并進行鄰接點擴散操作，直到在某節(jié)點形成最終的全局等待圖并將檢測結論通知各個節(jié)點。狀態(tài)比較難一致，可能依據部分等待圖來判斷第7章死鎖的預防避免和檢測分布式死鎖檢測邊跟蹤算法：各節(jié)點將自己的資源需求作為探測器沿依賴關系發(fā)送出去，如果某節(jié)點收到自己發(fā)出的探測器，則表明存在資源依賴回路。擴散計算算法：當需要檢測時，進程向它所依賴的進程發(fā)起詢問，并將因此而引發(fā)的各個詢問關聯(lián)成等待圖，或者通過接收應答將圖消解，或者從中發(fā)現(xiàn)死鎖。全局狀態(tài)檢測：通過建立一致的全局狀態(tài)圖來檢測是否有死鎖發(fā)生。第7章死鎖的預防避免和檢測等級式死鎖檢測第7章死鎖的預防避免和檢測

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

死鎖檢測算法AND模型下的Chandy-Misra-Hass算法

基本思想：在等待圖中，將探測報文(probemessage)從一個進程發(fā)送到另一個進程。如果報文回到發(fā)起者，那么就有死鎖存在。探測報文包含一個三元組(i,j,k)，表示該報文是一個由進程Pi發(fā)起的死鎖檢測報文，現(xiàn)在由進程Pj所在的站點發(fā)往進程Pk所在的站點。