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

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

死鎖的圖論模型

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

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

死鎖的圖論模型

資源分配圖實(shí)例：第7章死鎖的預(yù)防避免和檢測

死鎖的圖論模型

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

死鎖的圖論模型

資源分配圖到等待圖的轉(zhuǎn)化實(shí)例：第7章死鎖的預(yù)防避免和檢測

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

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

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

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

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

集中式死鎖檢測產(chǎn)生假死鎖的圖例說明：第7章死鎖的預(yù)防避免和檢測

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

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

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

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