普適分布式互斥算法及應(yīng)用.pdf

1、在分布式系統(tǒng)中，很多進(jìn)程能夠在微觀上并行執(zhí)行。但由于共享資源的有限性，以及全局?jǐn)?shù)據(jù)要求的一致性，一些臨界資源的訪問需要以互斥的方式實現(xiàn)同步。實現(xiàn)分布式互斥的算法一般分為基于令牌的分布式互斥算法和基于競爭的分布式互斥算法?；诹钆频姆植际交コ馑惴ň哂休^小的消息復(fù)雜度，但其同步時間較長，基于競爭的分布式互斥算法具有較大的消息復(fù)雜度，但其同步時間較短。同時，基于競爭的分布式互斥算法由于具有良好的對稱性在全分布系統(tǒng)中得到了廣泛的應(yīng)用。本文著重研

2、究了基于競爭的分布式互斥算法。特別是基于請求集的適用于任意規(guī)模分布式系統(tǒng)的普適分布式互斥算法。 基于競爭的分布式互斥算法主要分為兩類：全局互斥和局部互斥。全局互斥以Lamport和R＆A算法為代表；局部互斥以Makawa算法為代表。雖然全局互斥具有十分優(yōu)良的對稱性和極高的避免死鎖的能力，但其極大的消息復(fù)雜度(D(N))使得系統(tǒng)的規(guī)模受到了較大的限制。局部互斥雖然對稱性不如全局互斥，同步延遲也較大(一般為2T)，但Makawa算法

3、提出了請求集(Quorum)的概念，使得局部互斥的消息復(fù)雜度降為O(平方根N)。因此，局部互斥在系統(tǒng)規(guī)模的限制方面的性能比全局互斥要好得多。局部互斥在打破全局互斥對系統(tǒng)規(guī)模的限制的同時，由于請求集的生成需要時間和存儲空間，以及同步延遲的增加，因此使得互斥算法的實際性能受到很大影響。 局部互斥算法的運(yùn)行過程分為兩部分。一部分是請求集生成算法；另一部分是基于請求集的互斥算法。請求集生成算法決定了整個互斥算法的消息復(fù)雜度和對稱性，并對

4、算法運(yùn)行的實際時間消耗具有重要影響?；コ馑惴▽φ埱蠹慕M織及通信容錯處理形式?jīng)Q定了分布式互斥算法的對稱性，同步延遲，死鎖避免能力，節(jié)點與通信的失效容錯能力，并對消息復(fù)雜度具有重要影響。因此，尋求對任意規(guī)模系統(tǒng)都能生成對稱請求集的請求集生成算法(普適請求集生成算法)，降低請求集算法的時間復(fù)雜度和空間復(fù)雜度以降低由于生成請求集所耗費的時間與空間給互斥算法性能帶來的額外影響的問題是本文研究的一個重要內(nèi)容。在此基礎(chǔ)上提出消息復(fù)雜度低，同步延遲短

5、，失效容錯能力強(qiáng)的沒有死鎖的適用于任意規(guī)模分布式系統(tǒng)的普適對稱分布式互斥算法也是本文研究的主要內(nèi)容之一。 首先本文對適用于任意規(guī)模分布式系統(tǒng)的普適分布式互斥請求集生成算法進(jìn)行了研究。其目的在于尋找請求集長度、時間復(fù)雜度與空間復(fù)雜度都較低的對稱請求集生成算法。為降低算法的復(fù)雜性，同時根據(jù)循環(huán)請求集的優(yōu)良特性，本文提出的對稱請求集生成算法都是循環(huán)請求集生成算法。本文提出了基于循環(huán)編碼的對稱循環(huán)請求集生成算法，基于循環(huán)松弛差集的對稱請

6、求集生成算法以及基于循環(huán)請求集性質(zhì)的對稱請求集生成算法。其次本文對普適分布式互斥算法進(jìn)行了研究。以往的互斥算法多數(shù)是對Makawa算法的某一方面性能進(jìn)行改進(jìn)。它們多數(shù)需要犧牲互斥算法的一方面性能以提高其另一方面性能。如對容錯能力，死鎖檢測能力或者同步時間的改進(jìn)一般會以提高分布式互斥算法的消息復(fù)雜度為代價。本文將基于競爭的互斥算法的低同步延遲與基于令牌的互斥算法的低消息復(fù)雜度結(jié)合起來提出了新的互斥算法，這種算法能同時具有令牌算法和競爭算法

7、的優(yōu)點，克服上述二種算法的缺點。另一方面本文基于網(wǎng)絡(luò)系統(tǒng)的自組織特性，將分布式網(wǎng)絡(luò)劃分成一定數(shù)量的子網(wǎng)，在子網(wǎng)內(nèi)采用令牌算法，在由子網(wǎng)組成的上層采用競爭算法以確定各節(jié)點的請求時序與權(quán)限轉(zhuǎn)移，提出了分層結(jié)構(gòu)的分布式互斥算法，對降低分布式互斥算法的消息復(fù)雜度具有很大作用。 本文還對非穩(wěn)定環(huán)境下互斥算法的平均消息復(fù)雜度進(jìn)行研究并提出了相應(yīng)的復(fù)合算法。實際上，以前的所有分布式互斥算法，都是以假設(shè)系統(tǒng)的節(jié)點與通信都可靠作為算法運(yùn)行的前提的

8、。但實際系統(tǒng)中，節(jié)點與通信并不總是可靠的。因此，在實際應(yīng)用中，對節(jié)點與通信容錯的處理對分布式互斥的平均消息復(fù)雜度影響很大。通過對互斥算法的容錯處理方式進(jìn)行研究，并對不同容錯處理方式下，互斥算法的平均消息復(fù)雜度進(jìn)行分析，提出了在實際應(yīng)用中采取有效的容錯處理方式以提高互斥算法的性能的復(fù)合容錯算法。 本文還對分布式互斥算法的應(yīng)用范圍進(jìn)行了擴(kuò)展，對其在現(xiàn)場總線控制和數(shù)據(jù)交換機(jī)的性能改進(jìn)領(lǐng)域的應(yīng)用進(jìn)行了研究。提高了算法的理論層次和應(yīng)用范圍