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

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

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

3、們?cè)谙到y(tǒng)等待圖中所產(chǎn)生的死鎖拓?fù)浣Y(jié)構(gòu)相應(yīng)地表示單環(huán)、多環(huán)和結(jié)（后兩種模型都為結(jié)），學(xué)者們對(duì)各種算法的研究過程也是按著這個(gè)拓?fù)浣Y(jié)構(gòu)的順序展開的。對(duì)每一種模型下發(fā)生的死鎖，在算法研究中都出現(xiàn)了一些經(jīng)典的死鎖檢測(cè)方法，如Mitchell和Merritt提出的單環(huán)檢測(cè)算法，Chandy和Misra提出的環(huán)檢測(cè)算法，Lee提出的結(jié)檢測(cè)算法和Manivannan提出的通用檢測(cè)算法等等。在我們看來，在已提出的算法中，為單環(huán)和多環(huán)檢測(cè)所設(shè)計(jì)的算法可被歸

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

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

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

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