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

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

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

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

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

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

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

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

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