分布式數(shù)據(jù)庫中常見死鎖檢測(cè)算法分析

分布式數(shù)據(jù)庫中常見死鎖檢測(cè)算法分析主要內(nèi)容死鎖的形成1分布式系統(tǒng)中常見的死鎖檢測(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)。死鎖問題如果處理不當(dāng)，將嚴(yán)重影響系統(tǒng)的效率和可靠性。產(chǎn)生死鎖的必要條件是：互斥使用資源，占有且等待資源，非搶奪式分配，循環(huán)等待資源。一死鎖的形成在左圖中，T1封鎖X后T2又封鎖Y，而它們又要到提交后才撤去各自的鎖，調(diào)度Hl不能通過AEF所包圍的封鎖區(qū)，最后落入E點(diǎn)陷入死鎖，在這種情況下，只能借助于死鎖檢測(cè)器中止并重發(fā)。T2使調(diào)度轉(zhuǎn)變?yōu)榇械?。由上可知，形成死鎖至少要有兩對(duì)沖突操作，死鎖是沖突不能解決的結(jié)果。二分布式系統(tǒng)中常見的死鎖檢測(cè)方法死鎖的檢測(cè)：基于事先避免死鎖的一些方法通常會(huì)增加系統(tǒng)開銷，降低資源的利用率，因此并不太常用，特別是在分布式系統(tǒng)中更少用。為了降低系統(tǒng)開銷，在分配資源時(shí)不加限制，只要有剩余資源，總是把資源分配給申請(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ī)定的時(shí)限,就認(rèn)為發(fā)生了死鎖。在該算法中，每個(gè)事務(wù)在發(fā)出一個(gè)新的操作請(qǐng)求前設(shè)置一個(gè)超時(shí)。如果在超時(shí)結(jié)束以前，沒有收到請(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ò)傳輸問題。由于該算法判斷死鎖的標(biāo)準(zhǔn)與資源請(qǐng)求模型無關(guān)，因此它可以適用于任何類型的資源請(qǐng)求模型中。1.該方法的主要缺點(diǎn)是夭折了過多的事務(wù)。夭折的事務(wù)可能并沒有死鎖，造成了不必要的事務(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ì)搜索到輸出端口，就說明具有潛在的全局死鎖。在集中式死鎖檢測(cè)方法中，利用所有的局部資源分配圖(或等待圖)建立一個(gè)全局資源分配圖(或等待圖)。任何一個(gè)機(jī)器為它自己的進(jìn)程和資源維持一個(gè)局部的資源分配圖。整個(gè)系統(tǒng)只有一個(gè)協(xié)調(diào)者，它維持全局的資源分配圖，全局的資源分配圖是由局部資源分配圖組合而成的。

全局資源分配圖(或等待圖)的獲得方法當(dāng)協(xié)調(diào)者認(rèn)為需要運(yùn)行回路檢測(cè)算法時(shí)，它要求所有的機(jī)器向它發(fā)送局部圖的更新信息，協(xié)調(diào)者對(duì)全局圖進(jìn)行更新。定期地更新，每個(gè)機(jī)器定期地向協(xié)調(diào)者發(fā)送自上次更新以來所有添加的邊和刪除的邊，協(xié)調(diào)者根據(jù)報(bào)文信息對(duì)全局圖進(jìn)行更新。當(dāng)在局部圖中有邊被加入或刪除時(shí)，向協(xié)調(diào)者發(fā)送一個(gè)報(bào)文，協(xié)調(diào)者根據(jù)報(bào)文信息對(duì)全局圖進(jìn)行更新。2集中式檢測(cè)方法當(dāng)開始死鎖檢測(cè)時(shí)，協(xié)調(diào)者便查找全局等待圖。如果發(fā)現(xiàn)回路，一個(gè)進(jìn)程就會(huì)被卷回，從而打破循環(huán)等待。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)生假死鎖的圖例說明：3分布式死鎖檢測(cè)方法123路徑推動(dòng)算法:先在每個(gè)機(jī)器上建立形式簡(jiǎn)單的全局等待圖。每當(dāng)進(jìn)行死鎖檢測(cè)時(shí)，各個(gè)機(jī)器就將等待圖的拷貝送往一定數(shù)量的鄰居節(jié)點(diǎn)。局部拷貝更新后又被傳播下去。這一過程重復(fù)進(jìn)行直到某個(gè)節(jié)點(diǎn)獲得了足夠的信息來構(gòu)造一個(gè)等待圖以便做出是否存在死鎖的結(jié)論。邊跟蹤算法:分布式網(wǎng)絡(luò)結(jié)構(gòu)圖中的回路可以通過沿圖的邊傳播一種叫探測(cè)器的特殊信息來檢測(cè)。當(dāng)一個(gè)發(fā)起者得到一個(gè)與自己發(fā)送的探測(cè)器相匹配的探測(cè)器時(shí)，它就知道它在圖中的一個(gè)回路里。擴(kuò)散計(jì)算：懷疑有死鎖發(fā)生時(shí)，事務(wù)管理器通過向依賴于它的進(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的快照方法?？梢酝ㄟ^建立一個(gè)一致的全局狀態(tài)而無需暫停當(dāng)前的計(jì)算來生成一個(gè)一致的全局等待圖。Knapp將分布式死鎖檢測(cè)算法分為以下四類：3分布式死鎖檢測(cè)方法321在集中式方案中全部潛在的死鎖循環(huán)都發(fā)送給某個(gè)指定的站點(diǎn)，而在分布式檢測(cè)方案中則沒有這種站點(diǎn)。分布式死鎖檢測(cè)機(jī)構(gòu)中沒有本地和非本地死鎖檢測(cè)程序的任何區(qū)別，每個(gè)站點(diǎn)具有同樣的責(zé)任。在分布式方案中，死鎖檢測(cè)程序需要一種規(guī)則來決定應(yīng)該把潛在的死鎖循環(huán)發(fā)送給哪個(gè)站點(diǎn)，這種規(guī)則必須保證能最終檢測(cè)到全局死鎖，并且必須盡量減小傳送的信息量。分布式死鎖檢測(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è)需要解決的重要問題。死鎖的解決方法有多種，不同的系統(tǒng)應(yīng)根據(jù)實(shí)際情況采用不同的解決方法。在實(shí)際應(yīng)用中，不僅要解決死鎖問題，還要注意盡可能地提高資源利用率。死鎖的檢測(cè)與解除構(gòu)成了數(shù)據(jù)庫管理系統(tǒng)的主要內(nèi)容。死鎖檢測(cè)對(duì)應(yīng)于在等待圖中確定一個(gè)循環(huán)。在分布式數(shù)據(jù)庫中死鎖檢測(cè)問題比在集中式數(shù)據(jù)庫的死鎖檢測(cè)問題更困難，這是因?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è)進(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è)來自Pj的報(bào)文(這個(gè)報(bào)文的發(fā)送者Pj叫做Pk關(guān)于Pi的結(jié)合者)，它將向它的依賴集合中的所有進(jìn)程發(fā)送這個(gè)查詢，并且將查詢數(shù)目存儲(chǔ)在一個(gè)局部變量num(i)中。令局部變量wait(i)表示這一進(jìn)程從它接收到它的第一個(gè)由Pi發(fā)起的查詢起一直被阻塞這一事實(shí)。如果這個(gè)查詢是Pi發(fā)起的但不是第一個(gè)來自Pj的報(bào)文，即當(dāng)wait(i)仍然成立時(shí)，Pk將馬上回答。如果從wait(i)變?yōu)榧俚哪且粫r(shí)刻Pk運(yùn)行過，那么這個(gè)查詢就被丟棄。OR模型下的Chandy-Misra-Hass算法圖例說明：OR模型下的Chandy-Misra-Hass算法圖例說明：四關(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é)。死鎖解決。一個(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ù)庫系統(tǒng)及其應(yīng)用.北京:科學(xué)出版社,20002.劉鍵，《分布式計(jì)算機(jī)系統(tǒng)》，人民郵電出版社，1990年.3.KnappE.Deadlockdetectionindistributeddatabases.ACMComputSurv,1987,19(4):303-3284.GligorVD,ShattuckSH.Ondeadlockdetectionindistributedsystems.IEEETransSoftwareEng,1980,6(5):435–4405.RoeslerM,BurkhardWA,CooperKB.Efficientdeadlockresolutionforlock-basedconcurrencycontrolschemes.In:Proceedingsofthe8thInternationalonferenceonDistributedComputingSystems,SanJose,California,June13–17,1988.IEEE-CSPress,1988,224-233

參考文獻(xiàn)6.ChoudharyAN,KohlerWH,StankovicJA,TowsleyD.Amodifiedpriority-basedprobealgorithmfordistributeddeadlockdetectionandresolution.IEEETransSoftwareEng,1989,15(1):10-177.KshemkalyaniAD,SinghalM.Invariant-based