基于重復數的最短循環(huán)請求集生成算法研究.pdf

1、在分布式系統(tǒng)中，對臨界資源的訪問是需要互斥進行的，所以分布式系統(tǒng)中最先要解決的問題是分布式互斥算法。分布式互斥算法主要分為兩類，分別是基于競爭的和基于令牌的分布式互斥算法?；诟偁幍姆植际交コ馑惴ň哂邢碗s度較大，同步時間短，對稱性比較好的特性，在分布式系統(tǒng)應用廣泛?；诟偁幍姆植际交コ馑惴òㄓ芯植炕コ夂腿只コ?。全局互斥具有對稱性好，但消息復雜度極大，限制了系統(tǒng)規(guī)模。局部互斥降低了消息復雜度，并能適應較大的系統(tǒng)規(guī)模，但增加了請求集

2、生成算法在時間和空間上開銷。局部互斥的運算過程有兩步:第一步是請求集生成算法，第二步是請求集互斥算法。本文研究的方向是請求集生成算法。
　　在基于競爭的分布式互斥算法中，保證算法生成的請求集長度最短、時間復雜度和空間復雜度最低，一直都是分布式互斥請求集生成算法研究者追求的目標。本文通過對基于競爭的分布式互斥算法的研究發(fā)現，當前對特定拓撲結構的分布式互斥算法研究比較充分。這類算法簡單，但僅對特定系統(tǒng)節(jié)點比較適合，并且這些算法生成的請

3、求集大多數為非對稱請求集。因此，適合任意系統(tǒng)規(guī)模的普適請求集生成算法是現在研究重點。在保證請求集生成算法適合任意系統(tǒng)規(guī)模的同時，還能保證請求集結構簡單和對稱性，更是當前研究者追求的目標。循環(huán)請求集是滿足上述兩個條件的請求集。本文主要研究的基于重復數的最短循環(huán)請求集生成算法是一種循環(huán)請求集生成算法。
　　在普適請求集成算法中，大多數算法都能較快的生成請求集，但算法的請求集長度較大。因此，普適請求集生成算法的研究目標是算法的請求集長度

4、越來越短，時間復雜度和空間復雜度也越來也低。然而對請求集長度最短時(即請求集長度為N0.5)，研究這種情況的算法不多，并且這些算法都是用類似窮搜的方法求解。
　　本文提出了一種基于重復數的最短循環(huán)請求集生成算法，該算法目的是在保證請求集長度最短時，降低算法的時間復雜度和空間復雜度。該算法在循環(huán)松弛差集的思想上，以當前請求集中允許的最大重復數作為判斷條件，向請求集中添加元素。通過對算法進一步的研究，本文提出了請求集上限的概念和優(yōu)化方