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

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

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

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

4、特征；特定拓?fù)浣Y(jié)構(gòu)的通信網(wǎng)絡(luò)具有節(jié)點(diǎn)距離可計(jì)算性及通信的多跳性；傳統(tǒng)分布式互斥算法通常假設(shè)分布式互斥算法處于全互連的點(diǎn)到點(diǎn)通信網(wǎng)中，從而忽略了上述特性，這種假設(shè)脫離了分布式系統(tǒng)的實(shí)際情況，因而嚴(yán)重制約了分布式互斥算法的性能。針對(duì)上述問(wèn)題，本文提出了根據(jù)網(wǎng)絡(luò)的特定拓?fù)浣Y(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ò)的特性，并利用這些特性減少算法的消息復(fù)雜度，縮短響應(yīng)延遲，提高算法的容錯(cuò)能力。同時(shí)，由于P2P系統(tǒng)構(gòu)建于覆蓋網(wǎng)(Overlay)之上，忽略真實(shí)的拓?fù)浣Y(jié)構(gòu)，本文針對(duì)這種系統(tǒng)提出了基于分布式哈希表DHT(Distributed Hash Table)的分布式互斥算法。 3．本文提出了自組織網(wǎng)絡(luò)(Ad hoc)分布式系統(tǒng)的互斥算

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

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