分布式互斥算法的研究與實現(xiàn).pdf

1、分布式互斥是分布式系統(tǒng)設(shè)計的關(guān)鍵問題，它保證了相互沖突的并發(fā)進程可以共享資源。分布式互斥算法被廣泛應(yīng)用于解決副本一致性、領(lǐng)導者選舉等問題。隨著計算機及網(wǎng)絡(luò)技術(shù)的不斷發(fā)展，各種新型的分布式系統(tǒng)不斷涌現(xiàn)；針對這些系統(tǒng)的不同特性，因地制宜的進行分布式互斥算法研究具有相當重要的意義。 本文詳細分析與研究了分布式互斥算法的發(fā)展現(xiàn)狀與未來趨勢。在此基礎(chǔ)上，分析了分布式互斥算法應(yīng)用環(huán)境；詳細探討了分布式互斥對象的特征、特性及行為，并根據(jù)這些特

2、征和特定應(yīng)用環(huán)境提出了對應(yīng)的分布式互斥算法。 本文的創(chuàng)新點及其貢獻在于： 1．本文分析了分布式互斥對象的特性、特征及行為，并提出了一種基于可復制資源的分布式負載均衡策略。分布式系統(tǒng)的異構(gòu)決定了分布式互斥對象的多樣性；傳統(tǒng)分布式互斥模型忽略了這種多樣性，因此制約了分布式互斥算法的研究。針對上述問題，本文分析了不同分布式環(huán)境下的互斥對象的特性，并詳細說明了這些特性對分布式互斥算法的影響，提出了相應(yīng)的優(yōu)化及改進策略。在研究分布

3、式副本對象的過程中，提出了一種分布式負載均衡策略；在傳統(tǒng)負載均衡策略基礎(chǔ)上，本文提出了將節(jié)點的負載分為內(nèi)部、外部和轉(zhuǎn)發(fā)負載，并且分別進行處理的策略；提出了負載的方向性的概念，并且將它應(yīng)用在負載均衡策略中；該策略能夠有效的均衡負載，減小內(nèi)部通信量，同時能夠有效的抑制系統(tǒng)抖動。 2．本文分析了分布式互斥算法所運行的環(huán)境，提出了若干特定拓撲結(jié)構(gòu)下的基于特殊仲裁集(Quorum)構(gòu)建的優(yōu)化分布式互斥算法。分布式系統(tǒng)所處的通信網(wǎng)絡(luò)具有異構(gòu)

4、特征；特定拓撲結(jié)構(gòu)的通信網(wǎng)絡(luò)具有節(jié)點距離可計算性及通信的多跳性；傳統(tǒng)分布式互斥算法通常假設(shè)分布式互斥算法處于全互連的點到點通信網(wǎng)中，從而忽略了上述特性，這種假設(shè)脫離了分布式系統(tǒng)的實際情況，因而嚴重制約了分布式互斥算法的性能。針對上述問題，本文提出了根據(jù)網(wǎng)絡(luò)的特定拓撲結(jié)構(gòu)，優(yōu)化生成分布式互斥算法所需的仲裁集；主要包括四類： (1)線形網(wǎng)絡(luò)的折半仲裁集算法 (2)環(huán)形網(wǎng)絡(luò)的半環(huán)仲裁集分布式互斥算法； (3)樹形網(wǎng)絡(luò)的

5、回溯仲裁集分布式互斥算法； (4)網(wǎng)格網(wǎng)絡(luò)的十字仲裁集分布式互斥算法。這些算法綜合考慮了自身所在網(wǎng)絡(luò)的特性，并利用這些特性減少算法的消息復雜度，縮短響應(yīng)延遲，提高算法的容錯能力。同時，由于P2P系統(tǒng)構(gòu)建于覆蓋網(wǎng)(Overlay)之上，忽略真實的拓撲結(jié)構(gòu)，本文針對這種系統(tǒng)提出了基于分布式哈希表DHT(Distributed Hash Table)的分布式互斥算法。 3．本文提出了自組織網(wǎng)絡(luò)(Ad hoc)分布式系統(tǒng)的互斥算

6、法。Ad hoc網(wǎng)絡(luò)的動態(tài)拓撲結(jié)構(gòu)和節(jié)點自組織特性給分布式互斥算法的實現(xiàn)帶來了諸多困難。針對Ad hoc分布式互斥算法研究滯后的現(xiàn)狀，研究了分布式互斥對象唯一標識在Ad hoc網(wǎng)絡(luò)中的動態(tài)生成問題；提出了應(yīng)用于小規(guī)模Ad hoc網(wǎng)絡(luò)的ADMUTEX算法；進一步，提出了一種用于大規(guī)模網(wǎng)絡(luò)的Ad hoc分布式領(lǐng)導者選舉算法ADLE及該算法在自愈雷場系統(tǒng)中的應(yīng)用實例。ADLE采用Lamport邏輯時戳保證消息的時序性，避免了節(jié)點餓死；通過限制

7、算法執(zhí)行范圍縮小了消息復雜度與同步延遲：而且它采用動態(tài)生成的請求/應(yīng)答隊列，因此不需要節(jié)點了解系統(tǒng)的全局信息，能夠適應(yīng)Ad hoc網(wǎng)絡(luò)的動態(tài)拓撲結(jié)構(gòu)和節(jié)點頻繁出入的情況。較之傳統(tǒng)算法，該算法具有較低的消息復雜度、小響應(yīng)延遲和公平性。 4．本文提出了面向多互斥對象的多目標分布式互斥算法。由于分布式系統(tǒng)中的節(jié)點往往同時需要多個互斥對象來協(xié)同完成特定任務(wù)，或者臨界區(qū)中能夠容納多個節(jié)點進入，這使得多目標分布式互斥算法顯得尤為重要。根據(jù)這