普適分布式互斥算法及應用.pdf

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

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

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

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

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

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

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

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