分布式系統(tǒng)在提供強(qiáng)大服務(wù)能力的同時(shí)也面臨著可靠性、安全性和復(fù)雜性等挑戰(zhàn)。因資源分配與需求產(chǎn)生沖突而產(chǎn)生的死鎖,在分布式系統(tǒng)中是一種較常見(jiàn)的軟件錯(cuò)誤。若不能及時(shí)處理系統(tǒng)中出現(xiàn)的死鎖,則可能出現(xiàn)用戶體驗(yàn)下降、計(jì)算結(jié)果錯(cuò)誤和系統(tǒng)效率下降甚至崩潰等問(wèn)題。常見(jiàn)死鎖處理方式包括:預(yù)防、避免和檢測(cè)解決。相對(duì)于死鎖預(yù)防和死鎖避免,死鎖檢測(cè)和解決不僅簡(jiǎn)單高效而且可行性較高。然而,不同于集中式系統(tǒng),分布式系統(tǒng)具有無(wú)共享內(nèi)存、無(wú)全局時(shí)鐘以及軟硬件失效概率較高等特點(diǎn)。這增加了分布式系統(tǒng)中死鎖處理的復(fù)雜度。同時(shí),作為運(yùn)行在系統(tǒng)中的應(yīng)用進(jìn)程,用于死鎖檢測(cè)和解決的進(jìn)程需要在保證死鎖檢測(cè)和解決結(jié)果正確性的同時(shí)注重效率。通過(guò)對(duì)現(xiàn)有分布式系統(tǒng)中死鎖檢測(cè)算法的研究和分析發(fā)現(xiàn),現(xiàn)有算法多側(cè)重于研究單個(gè)進(jìn)程發(fā)起死鎖檢測(cè)時(shí)的算法正確性和效率問(wèn)題。然而,在真實(shí)分布式系統(tǒng)中,死鎖涉及到的多個(gè)進(jìn)程可能并行發(fā)起死鎖檢測(cè)。當(dāng)多個(gè)進(jìn)程并行檢測(cè)系統(tǒng)中同一個(gè)死鎖時(shí),可能出現(xiàn)諸如死鎖重復(fù)檢測(cè)和解決導(dǎo)致的偽死鎖、非最優(yōu)死鎖解決方案以及算法效率等問(wèn)題。同時(shí),現(xiàn)有算法大多未考慮計(jì)算節(jié)點(diǎn)或進(jìn)程部分或完全失效時(shí)的容錯(cuò)問(wèn)題。再者,諸如移動(dòng)無(wú)線網(wǎng)絡(luò)系統(tǒng)、移動(dòng)代理系統(tǒng)和移動(dòng)邊緣計(jì)算系統(tǒng)等具有移動(dòng)性特點(diǎn)的分布式系統(tǒng)中的死鎖檢測(cè)和解決問(wèn)題還未被充分研究。本文通過(guò)研究和分析現(xiàn)有分布式系統(tǒng)中死鎖檢測(cè)算法存在的不足,針對(duì)現(xiàn)有算法在并行死鎖檢測(cè)情況下的正確性、效率、容錯(cuò)能力和擴(kuò)展性的不足提出了相應(yīng)優(yōu)化方法。本文主要研究成果如下:(1)提出了一種基于優(yōu)先級(jí)的分布式并行死鎖檢測(cè)優(yōu)化算法。在所提出的算法中,高優(yōu)先級(jí)死鎖檢測(cè)進(jìn)程重用低優(yōu)先級(jí)進(jìn)程已收集的死鎖相關(guān)信息,以減少低優(yōu)先級(jí)進(jìn)程重復(fù)轉(zhuǎn)發(fā)探針消息。同時(shí),為減少所傳輸消息中攜帶的數(shù)據(jù)總量,所提出的算法在每個(gè)發(fā)起死鎖檢測(cè)的進(jìn)程正常終止之前不傳輸死鎖相關(guān)信息。最后,通過(guò)改進(jìn)的優(yōu)先級(jí)比較策略,算法可選出唯一的死鎖檢測(cè)進(jìn)程執(zhí)行死鎖相關(guān)信息收集、死鎖檢測(cè)和解決以保證算法正確性。相比已有算法,新算法在保證并行死鎖檢測(cè)結(jié)果正確的同時(shí),也提高了算法效率。(2)提出了一種基于領(lǐng)導(dǎo)人選舉策略的分布式容錯(cuò)并行死鎖檢測(cè)算法。針對(duì)分布式系統(tǒng)中死鎖檢測(cè)時(shí)進(jìn)程間通信失效引起的算法無(wú)法正常運(yùn)行問(wèn)題,提出了一種能夠容忍一定范圍內(nèi)死鎖檢測(cè)進(jìn)程間通信失效的容錯(cuò)算法。在所提出的算法中,死鎖檢測(cè)進(jìn)程通過(guò)維護(hù)進(jìn)程間失效記錄和中央控制進(jìn)程推薦列表,并根據(jù)進(jìn)程優(yōu)先級(jí)推薦新中央控制進(jìn)程控。新算法在單進(jìn)程死鎖檢測(cè)情況下保留了集中式死鎖檢測(cè)算法效率的同時(shí)提供了一定的容錯(cuò)能力。同時(shí),該算法在多進(jìn)程并行死鎖檢測(cè)情況下也具有較高的效率。(3)提出了一種面向移動(dòng)代理系統(tǒng)中單資源模型的分布式并行死鎖檢測(cè)算法。在所提出的算法中,死鎖檢測(cè)代理采用漸進(jìn)式收集死鎖代理相關(guān)信息的方式提升算法效率。通過(guò)基于改進(jìn)的優(yōu)先級(jí)比較策略和延遲回復(fù)策略減少死鎖檢測(cè)代理在系統(tǒng)中的移動(dòng)次數(shù)和代理移動(dòng)時(shí)攜帶的數(shù)據(jù)總量。同時(shí),新算法通過(guò)改進(jìn)的優(yōu)先級(jí)策略保證并行死鎖檢測(cè)和解決結(jié)果的正確性。(4)提出了一種面向移動(dòng)代理系統(tǒng)中一般化資源模型的分布式并行死鎖檢測(cè)算法。所提出的算法利用權(quán)值均分技術(shù)、擴(kuò)散計(jì)算技術(shù)和改進(jìn)的延遲回復(fù)策略以提升算法效率。同時(shí),為保證死鎖檢測(cè)和解決結(jié)果的正確性,新算法也使用了基于優(yōu)先級(jí)的比較策略以避免死鎖重復(fù)檢測(cè)和解決。新算法在保證死鎖檢測(cè)和解決結(jié)果正確性和效率的基礎(chǔ)上擴(kuò)展了算法的適用范圍。本文對(duì)所提出算法的正確性(即算法活性和安全性)進(jìn)行了非形式化證明和基于TLA+(Temporal Logic of Actions)的形式化驗(yàn)證。驗(yàn)證結(jié)果表明,本文所提出的各算法均滿足活性和安全性要求。同時(shí),通過(guò)理論性能分析和仿真實(shí)驗(yàn)對(duì)部分現(xiàn)有死鎖檢測(cè)算法與所提出的算法進(jìn)行了性能比較。比較結(jié)果顯示,本文所提出的算法在整體上具有較高的效率。
【學(xué)位單位】：北京交通大學(xué)
【學(xué)位級(jí)別】：博士
【學(xué)位年份】：2018
【中圖分類(lèi)】：TP338.8
【部分圖文】：

不僅具有重要科學(xué)研宄價(jià)值也具有較強(qiáng)實(shí)際應(yīng)用價(jià)值。??本文研宄的課題來(lái)源于中國(guó)國(guó)家自然科學(xué)基金面上項(xiàng)目，“資源導(dǎo)向型對(duì)等網(wǎng)??絡(luò)下服務(wù)發(fā)現(xiàn)與服務(wù)組合的研究”（項(xiàng)目編號(hào)６１２７２３５３）和中國(guó)國(guó)家自然科學(xué)基金??海外杰出青年合作項(xiàng)目，“數(shù)據(jù)密集型系統(tǒng)中軟件的錯(cuò)誤檢測(cè)、故障恢復(fù)和優(yōu)化”??（項(xiàng)目編號(hào)６１４２８２０１）。課題的研究目的是為大型對(duì)等網(wǎng)絡(luò)下的Ｗｅｂ服務(wù)應(yīng)用提??供可靠的運(yùn)行環(huán)境。課題的研宄目標(biāo)是：根據(jù)分布式系統(tǒng)應(yīng)用的特點(diǎn)，以提升分布??式系統(tǒng)中錯(cuò)誤檢測(cè)準(zhǔn)確性和效率為前提，提出面向分布式系統(tǒng)的錯(cuò)誤檢測(cè)和故障??容錯(cuò)方法，為構(gòu)建高可靠Ｗｅｂ服務(wù)或相應(yīng)分布式應(yīng)用奠定基礎(chǔ)。??１．２分布式系統(tǒng)架構(gòu)??分布式系統(tǒng)是一組通過(guò)網(wǎng)絡(luò)連接并互相協(xié)作以解決特定任務(wù)的計(jì)算機(jī)以及運(yùn)??行在其上的軟件組成的系統(tǒng)。系統(tǒng)中各計(jì)算機(jī)上應(yīng)用程序之間通過(guò)傳遞消息來(lái)共??享信息和協(xié)調(diào)任務(wù)［１３Ｌ圖１－１給出了分布式系統(tǒng)的整體架構(gòu)示意圖。??Ｃｏｍｐｕｔｅｒ?１?Ｃｏｍｐｕｔｅｒ?２?Ｃｏｍｐｕｔｅｒ?ｉ?Ｃｏｍｐｕｔｅｒ?ｍ?Ｃｏｍｐｕｌｅｒ?ｎ??｜?■?■?｜?｜?■?－ｉ?「■?ｉ?ｒ?Ｉ????

圖１－２分布式系統(tǒng)中資源請(qǐng)求模型分類(lèi)??Ｆｉｇ．?１－２?Ｃｌａｓｓｉｆｉｃａｔｉｏｎ?ｏｆ?ｒｅｓｏｕｒｃｅ?ｒｅｑｕｅｓｔ?ｍｏｄｅｌｓ?ｉｎ?ｄｉｓｔｒｉｂｕｔｅｄ?ｓｙｓｔｅｍｓ??圖１－２給出了分布式系統(tǒng)中資源請(qǐng)求模型分類(lèi)。根據(jù)引起死鎖的資源類(lèi)型可將??資源請(qǐng)求模型分為：資源模型和通信模型［１８］。根據(jù)應(yīng)用進(jìn)程申請(qǐng)資源的數(shù)量以及??進(jìn)程可以繼續(xù)運(yùn)行時(shí)資源所需邏輯關(guān)系，文獻(xiàn)［１９］將上述兩種資源模型細(xì)分為：??（１）

?ｂ）?ｃ）??圖１－３常用死鎖表示圖，其中，ａ）任務(wù)資源圖；ｂ）二分圖；ｃ）通用資源圖??Ｆｉｇ．?１－３?Ｄｅａｄｌｏｃｋ?ｇｒａｐｈ?ｒｅｐｒｅｓｅｎｔａｔｉｏｎｓ，?ｗｈｅｒｅ，?ａ）?ｔａｓｋ?ｒｅｓｏｕｒｃｅ?ｇｒａｐｈ；?ｂ）?ｂｉｐａｒｔｉｔｅ?ｇｒａｐｈ；?ｃ）?ｇｅｎｅｒａｌ??ｒｅｓｏｕｒｃｅ?ｇｒａｐｈ??圖１－３?ｃ）表示由進(jìn)程程ｐ＃ｐ２及可重用資源ＲＲｊ?＝?｛ｒｒ＾ｒｉ＾，?．．．，ｒｒｘ｝和一組可消??耗資源ＣＲｊ?＝?｛ｃｒｉ，ｃｒ２，ｃｒｙ｝組成的一般化資源等待圖。每個(gè)可重用資源ＲＲＰ其成員??數(shù)為正整數(shù)。每個(gè)可消耗資源ＣＲｐ其生產(chǎn)者是進(jìn)程集Ｐ的非空子集。一般化資源??等待圖中的邊分為三種類(lèi)型：??（１）
【參考文獻(xiàn)】

相關(guān)期刊論文 前2條

1 梅宏;王千祥;張路;王戟;;軟件分析技術(shù)進(jìn)展[J];計(jì)算機(jī)學(xué)報(bào);2009年09期

2 王汝傳,徐小龍,鄭曉燕,孫知信;移動(dòng)代理安全機(jī)制模型的研究[J];計(jì)算機(jī)學(xué)報(bào);2002年12期

相關(guān)博士學(xué)位論文 前1條

1 程欣;面向環(huán)和結(jié)的分布式死鎖檢測(cè)算法研究[D];哈爾濱工業(yè)大學(xué);2006年

相關(guān)碩士學(xué)位論文 前1條

1 陳鵬;分布式數(shù)據(jù)庫(kù)死鎖檢測(cè)算法研究[D];重慶大學(xué);2004年

本文編號(hào)：2873761