分布式數(shù)據(jù)庫(kù)中常見(jiàn)死鎖檢測(cè)算法分析課件

1、分布式數(shù)據(jù)庫(kù)中常見(jiàn)死鎖檢測(cè)算法分析主要內(nèi)容死鎖的形成 1分布式系統(tǒng)中常見(jiàn)的死鎖檢測(cè)方法2死鎖檢測(cè)的實(shí)例3關(guān)于死鎖檢測(cè)和恢復(fù)的研究方向4一 死鎖的形成產(chǎn)生死鎖的原因： 由于系統(tǒng)提供的資源數(shù)比多個(gè)進(jìn)程所需的資源數(shù)少，并且系統(tǒng)的資源分配策略和進(jìn)程并發(fā)執(zhí)行的速度不當(dāng)。 死鎖問(wèn)題如果處理不當(dāng)，將嚴(yán)重影響系統(tǒng)的效率和可靠性。產(chǎn)生死鎖的必要條件是： 互斥使用資源，占有且等待資源，非搶奪式分配，循環(huán)等待資源。二 分布式系統(tǒng)中常見(jiàn)的死鎖檢測(cè)方法死鎖的檢測(cè)： 基于事先避免死鎖的一些方法通常會(huì)增加系統(tǒng)開銷，降低資源的利用率，因此并不太常用，特別是在分布式系統(tǒng)中更少用。為了降低系統(tǒng)開銷，在分配資源時(shí)不加限制，只要有剩

2、余資源，總是把資源分配給申請(qǐng)者。當(dāng)然，這樣可能會(huì)出現(xiàn)死鎖。這種系統(tǒng)采用定時(shí)運(yùn)行一個(gè)“死鎖檢測(cè)”程序的方法，當(dāng)檢測(cè)到死鎖時(shí)再設(shè)法將其排除。這種方法在分布式系統(tǒng)中最為常用。1 超時(shí)法超時(shí)法就是一個(gè)事務(wù)的等待時(shí)間如果超過(guò)了規(guī)定的時(shí)限,就認(rèn)為發(fā)生了死鎖。在該算法中，每個(gè)事務(wù)在發(fā)出一個(gè)新的操作請(qǐng)求前設(shè)置一個(gè)超時(shí)。如果在超時(shí)結(jié)束以前，沒(méi)有收到請(qǐng)求的操作已經(jīng)成功執(zhí)行的確認(rèn)信息，事務(wù)則認(rèn)為它自己已經(jīng)處于死鎖同時(shí)夭折自己。1 超時(shí)法優(yōu)點(diǎn)缺點(diǎn)該算法簡(jiǎn)單，實(shí)現(xiàn)方便，而且不會(huì)由于死鎖檢測(cè)而引起任何網(wǎng)絡(luò)傳輸問(wèn)題。由于該算法判斷死鎖的標(biāo)準(zhǔn)與資源請(qǐng)求模型無(wú)關(guān)，因此它可以適用于任何類型的資源請(qǐng)求模型中。1.該方法的主要缺點(diǎn)是

3、夭折了過(guò)多的事務(wù)。夭折的事務(wù)可能并沒(méi)有死鎖，造成了不必要的事務(wù)夭折與重啟。2.另一個(gè)缺點(diǎn)是超時(shí)間隔難以把握。如果時(shí)間間隔太短，則會(huì)使更多的事務(wù)發(fā)生不必要的夭折，如果太長(zhǎng)，則會(huì)延長(zhǎng)死鎖在系統(tǒng)中的持續(xù)時(shí)間，進(jìn)而降低系統(tǒng)性能。由于系統(tǒng)中的各種應(yīng)用存在相當(dāng)大的差異，所以通常超時(shí)間隔不得不設(shè)置為比一個(gè)事務(wù)的平均執(zhí)行時(shí)間更長(zhǎng)。2 集中式檢測(cè)方法在分布式系統(tǒng)中，每個(gè)站點(diǎn)都有一個(gè)本地死鎖檢測(cè)程序，其任務(wù)是判斷在其站點(diǎn)所有潛在的全局死鎖；其方法是：在站點(diǎn)的輸入端口開始，沿本地等待圖反向搜索，如果最終會(huì)搜索到輸出端口，就說(shuō)明具有潛在的全局死鎖。在集中式死鎖檢測(cè)方法中，利用所有的局部資源分配圖(或等待圖)建立一個(gè)全

4、局資源分配圖(或等待圖)。任何一個(gè)機(jī)器為它自己的進(jìn)程和資源維持一個(gè)局部的資源分配圖。整個(gè)系統(tǒng)只有一個(gè)協(xié)調(diào)者，它維持全局的資源分配圖，全局的資源分配圖是由局部資源分配圖組合而成的。2 集中式檢測(cè)方法12它易受運(yùn)行集中檢測(cè)程序的站點(diǎn)的故障的影響它可能需要大量的通訊費(fèi)用，因?yàn)榧惺綑z測(cè)程序可能離網(wǎng)絡(luò)中的其他站點(diǎn)很遠(yuǎn)。集中式死鎖檢測(cè)比較簡(jiǎn)單，但它容易產(chǎn)生假死鎖的情況。它有兩個(gè)主要缺點(diǎn)：產(chǎn)生假死鎖的圖例說(shuō)明：3 分布式死鎖檢測(cè)方法123路徑推動(dòng)算法:先在每個(gè)機(jī)器上建立形式簡(jiǎn)單的全局等待圖。每當(dāng)進(jìn)行死鎖檢測(cè)時(shí)，各個(gè)機(jī)器就將等待圖的拷貝送往一定數(shù)量的鄰居節(jié)點(diǎn)。局部拷貝更新后又被傳播下去。這一過(guò)程重復(fù)進(jìn)行直到

5、某個(gè)節(jié)點(diǎn)獲得了足夠的信息來(lái)構(gòu)造一個(gè)等待圖以便做出是否存在死鎖的結(jié)論。邊跟蹤算法:分布式網(wǎng)絡(luò)結(jié)構(gòu)圖中的回路可以通過(guò)沿圖的邊傳播一種叫探測(cè)器的特殊信息來(lái)檢測(cè)。當(dāng)一個(gè)發(fā)起者得到一個(gè)與自己發(fā)送的探測(cè)器相匹配的探測(cè)器時(shí)，它就知道它在圖中的一個(gè)回路里。擴(kuò)散計(jì)算：懷疑有死鎖發(fā)生時(shí)，事務(wù)管理器通過(guò)向依賴于它的進(jìn)程發(fā)送查詢啟動(dòng)一個(gè)擴(kuò)散進(jìn)程。這里不會(huì)生成全局等待圖。發(fā)送查詢信息時(shí)，擴(kuò)散計(jì)算就增長(zhǎng)；接收回答后，擴(kuò)散計(jì)算就縮減。根據(jù)所得信息，發(fā)起者會(huì)檢測(cè)到死鎖的發(fā)生。4全局狀態(tài)檢測(cè):這個(gè)方法基于Chandy和Lamport 的快照方法?？梢酝ㄟ^(guò)建立一個(gè)一致的全局狀態(tài)而無(wú)需暫停當(dāng)前的計(jì)算來(lái)生成一個(gè)一致的全局等待圖。Kn

6、app將分布式死鎖檢測(cè)算法分為以下四類：4 層級(jí)式死鎖檢測(cè)在層級(jí)式死鎖檢測(cè)算法中，站點(diǎn)被分層地放在一個(gè)樹中。一個(gè)站點(diǎn)的死鎖檢測(cè)只涉及到它的下一級(jí)站點(diǎn)。例如，設(shè)A、B和C是控制器，而C是A和B的最低的公共祖先。假定節(jié)點(diǎn)Pi出現(xiàn)在控制器A和B的局部等待圖中，那么節(jié)點(diǎn)Pi也必定出現(xiàn)在如下控制器的等待圖中： (1) C控制器；(2) 所有位于從C到A的路徑上的控制器；(3) 所有位于從C到B的路徑上的控制器。 而且，如果Pi和Pj出現(xiàn)在控制器D的等待圖中，并且在D的一個(gè)下一級(jí)控制器(子控制器)的等待圖中有一條從Pi到Pj的路徑，那么邊(Pi,Pj)一定存在于D的等待圖中。死鎖處理是分布式系統(tǒng)中一個(gè)需要

7、解決的重要問(wèn)題。死鎖的解決方法有多種，不同的系統(tǒng)應(yīng)根據(jù)實(shí)際情況采用不同的解決方法。在實(shí)際應(yīng)用中，不僅要解決死鎖問(wèn)題，還要注意盡可能地提高資源利用率。死鎖的檢測(cè)與解除構(gòu)成了數(shù)據(jù)庫(kù)管理系統(tǒng)的主要內(nèi)容。死鎖檢測(cè)對(duì)應(yīng)于在等待圖中確定一個(gè)循環(huán)。在分布式數(shù)據(jù)庫(kù)中死鎖檢測(cè)問(wèn)題比在集中式數(shù)據(jù)庫(kù)的死鎖檢測(cè)問(wèn)題更困難，這是因?yàn)榇_定一個(gè)死鎖的循環(huán)等待狀態(tài)可能要涉及到多個(gè)場(chǎng)地，而不僅僅是一個(gè)場(chǎng)地。4 層級(jí)式死鎖檢測(cè)三 死鎖檢測(cè)的實(shí)例OR模型下的Chandy-Misra-Hass算法：使用兩類報(bào)文：(query,i,j,k)和(reply,i,j,k)，表示這些報(bào)文屬于由進(jìn)程Pi發(fā)起的并由Pj送往Pk的擴(kuò)散計(jì)算。 一個(gè)

8、進(jìn)程的依賴集合包括所有它在等待以便獲得報(bào)文的進(jìn)程。如果接收進(jìn)程Pk是活動(dòng)的，它會(huì)忽略所有的查詢和回答報(bào)文。如果它被阻塞，它會(huì)向它的依賴集合中的進(jìn)程發(fā)送查詢。 一旦收集到回答報(bào)文，接收進(jìn)程將向發(fā)起者發(fā)送一個(gè)回答報(bào)文。發(fā)起者以及每個(gè)中間進(jìn)程用一個(gè)計(jì)數(shù)器記錄查詢和回答的數(shù)目。如果這兩個(gè)數(shù)字相同，即發(fā)起者的每個(gè)查詢都得到了回答，就表明發(fā)起者處于死鎖狀態(tài)。OR模型下的Chandy-Misra-Hass算法：當(dāng)接收進(jìn)程Pk處于阻塞狀態(tài)時(shí)，會(huì)有幾種可能： 如果這是Pi發(fā)起的第一個(gè)來(lái)自Pj的報(bào)文(這個(gè)報(bào)文的發(fā)送者Pj叫做Pk關(guān)于Pi的結(jié)合者)，它將向它的依賴集合中的所有進(jìn)程發(fā)送這個(gè)查詢，并且將查詢數(shù)目存儲(chǔ)在一

9、個(gè)局部變量num(i)中。令局部變量wait(i)表示這一進(jìn)程從它接收到它的第一個(gè)由Pi發(fā)起的查詢起一直被阻塞這一事實(shí)。 如果這個(gè)查詢是Pi發(fā)起的但不是第一個(gè)來(lái)自Pj的報(bào)文，即當(dāng)wait(i)仍然成立時(shí)，Pk將馬上回答。 如果從wait(i)變?yōu)榧俚哪且粫r(shí)刻Pk運(yùn)行過(guò)，那么這個(gè)查詢就被丟棄。 OR模型下的Chandy-Misra-Hass算法圖例說(shuō)明：四 關(guān)于死鎖檢測(cè)和恢復(fù)的研究方向算法正確性。嚴(yán)格證明死鎖檢測(cè)算法的正確性是困難的，由于報(bào)文的傳輸延遲是不可預(yù)料的，所以得到一致的全局狀態(tài)是很困難的。 算法性能。需要在信息流量(監(jiān)測(cè)和恢復(fù)算法的復(fù)雜性)和死鎖持續(xù)時(shí)間(監(jiān)測(cè)和恢復(fù)的速度)之間達(dá)成妥協(xié)

10、。 死鎖解決。一個(gè)好而快的死鎖檢測(cè)算法可能并不能提供足夠的信息用于解決死鎖。 假死鎖。一個(gè)檢測(cè)程序不僅要滿足前進(jìn)要求，即必須在有限的時(shí)間內(nèi)發(fā)現(xiàn)死鎖，還要滿足安全要求。如果一個(gè)死鎖被發(fā)現(xiàn)，那么這個(gè)死鎖應(yīng)該是確實(shí)存在的。 死鎖概率。檢測(cè)和恢復(fù)算法的設(shè)計(jì)依賴于給定系統(tǒng)中死鎖發(fā)生的概率。參考文獻(xiàn)1. 邵佩英著.分布式數(shù)據(jù)庫(kù)系統(tǒng)及其應(yīng)用.北京:科學(xué)出版社, 20002. 劉鍵，分布式計(jì)算機(jī)系統(tǒng)，人民郵電出版社，1990年.3. Knapp E . Deadlock detection in distributed databases.ACM ComputSurv, 1987, 19(4): 303-3284. GligorVD, Shattuck SH . On deadlock detection in distributed systems. IEEE Trans Software Eng, 1980, 6(5): 4354405.RoeslerM, BurkhardWA, CooperKB. Efficient deadlock resolutionfor lock-based concurrency cont