面向環(huán)和結的分布式死鎖檢測算法研究.pdf

1、在分布式系統中，如果資源的分配與需求產生沖突，系統中可能發(fā)生死鎖，這是一種無限阻塞狀態(tài)：發(fā)生死鎖的進程集合中的已經持有部分資源的進程在發(fā)出新的資源申請時，發(fā)現被申請的資源正在被這個集合中的其它進程所占據，這個集合中的進程都將無限期地相互等待資源被釋放，從而導致系統運行陷入停滯。
　　死鎖可以在分布式系統設計之初就采取措施加以避免，但這樣一來或者需要系統擁有足夠多的資源，或者需要對進程的資源請求做出嚴格的限制，以運行時間的延長來換取

2、不被鎖住。所以避免方法要預知系統可能出現的各種運行狀態(tài)，適用于進程的并發(fā)時間和規(guī)模相對固定的分布式系統，如機場的實時控制系統。而大多數分布式系統中的進程對資源的需求時間和規(guī)模是不確定的，避免算法無法應對所有的可能情況，此時可行的死鎖處理方法是死鎖的檢測和解決。
　　對分布式死鎖檢測算法的研究由來已久，根據進程對資源的需求條件不同，分布式計算可以被分為單資源模型、AND模型、OR模型以及AND-OR模型，這些模型的通用性逐漸增強，它

3、們在系統等待圖中所產生的死鎖拓撲結構相應地表示單環(huán)、多環(huán)和結（后兩種模型都為結），學者們對各種算法的研究過程也是按著這個拓撲結構的順序展開的。對每一種模型下發(fā)生的死鎖，在算法研究中都出現了一些經典的死鎖檢測方法，如Mitchell和Merritt提出的單環(huán)檢測算法，Chandy和Misra提出的環(huán)檢測算法，Lee提出的結檢測算法和Manivannan提出的通用檢測算法等等。在我們看來，在已提出的算法中，為單環(huán)和多環(huán)檢測所設計的算法可被歸

4、納為資源管理節(jié)點相關(RD)和資源管理節(jié)點無關(RI)兩類，而為結檢測設計的算法可被歸納為起始點歸約(IR)和中間結點歸約(NR)兩類。在對這些算法的分析中我們發(fā)現資源管理節(jié)點相關和資源管理節(jié)點無關類算法存在著檢測效率不高，不能克服交疊環(huán)等缺陷，而起始點歸約和中間節(jié)點歸約類算法存在著算法過于復雜，不能適用于動態(tài)環(huán)境等缺陷。此外，已有算法的共性問題還包括不能容錯，不能并發(fā)執(zhí)行等缺陷，而這些缺陷或者在非形式化證明中被忽略，或者在性能模擬中被

5、掩蓋。
　　本文所作的工作就是在分析已有算法不足的基礎上，對現有的分布式死鎖檢測算法進行改進和創(chuàng)新。這些工作分為四個部分：1)在原有的資源管理節(jié)點相關和資源管理節(jié)點無關類算法的基礎上，將單環(huán)死鎖檢測算法改進為僅與資源管理節(jié)點相關(RDO)的檢測方法，將原來的算法的執(zhí)行載體由進程管理節(jié)點或/和資源管理節(jié)點改為全部為資源管理節(jié)點，這樣就大大化簡了檢測的執(zhí)行步驟并提高了算法的可靠性；2)為環(huán)死鎖檢測提出一種快速的雙邊發(fā)送死鎖檢測算法。這

6、種算法與原有的資源管理節(jié)點相關和資源管理節(jié)點無關算法的區(qū)別在于資源管理節(jié)點同時向自己的所有請求者發(fā)送等待和被等待消息，而不是先前的只發(fā)送二者之一，此外算法還增加了一個前處理過程以期在不發(fā)送探針的情況下在當地發(fā)現潛在的二元死鎖；3)從環(huán)是結的必要條件出發(fā)，改進了結檢測算法，算法在結中尋找環(huán)，找到后即執(zhí)行死鎖解決動作，而不需要尋找結的全部成員，從而迅速解決死鎖。這種尋找可以用對等待圖的前向或逆向搜索實現，本文中我們采用了逆向搜索方法；4)為

7、不可靠的分布式系統提出一種基于動態(tài)等待圖的容錯的死鎖檢測算法。這也是一種結檢測算法，算法通過將系統中發(fā)生阻塞的進程的生成和退出，處理器、進程或通信通道出現故障等情況映射成為死鎖拓撲結構的動態(tài)變化，將原有用于表達死鎖拓撲的靜態(tài)等待圖轉化為動態(tài)等待圖，并在此基礎上將圖中節(jié)點的被動退出設置為死鎖檢測強制終止條件，使并發(fā)執(zhí)行的算法能夠全部終止，從而使算法擁有容錯功能。
　　正確性和算法性能是死鎖檢測算法研究的核心問題，除比較簡單的單環(huán)檢測