基于差集的高效能分布式請(qǐng)求集生成算法

陳志黨，李美安，王春申，林 嵐

（內(nèi)蒙古農(nóng)業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，內(nèi)蒙古 呼和浩特 010018）

基于差集的高效能分布式請(qǐng)求集生成算法

陳志黨，李美安，王春申，林 嵐

（內(nèi)蒙古農(nóng)業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，內(nèi)蒙古 呼和浩特 010018）

松弛正向差集；請(qǐng)求集;折半循環(huán)編碼算法

基于請(qǐng)求集的分布式互斥算法作為Maekawa算法[1]的推廣，近年來得到了人們的廣泛關(guān)注，人們提出了許多各具特色的算法[2-5]來構(gòu)建請(qǐng)求集以降低分布式互斥算法的消息復(fù)雜度或者提高分布式互斥算法在其他方面的性能。但在通常情況下，分布式互斥請(qǐng)求集生成算法的性能直接影響分布式互斥算法的性能。例如，請(qǐng)求集生成算法的對(duì)稱性將影響分布式互斥算法的對(duì)稱性，請(qǐng)求集生成算法所生成請(qǐng)求集的長(zhǎng)度直接影響基于其上的分布式互斥算法的消息復(fù)雜度。而目前已經(jīng)存在的分布式互斥請(qǐng)求集生成算法在請(qǐng)求集長(zhǎng)度、時(shí)間復(fù)雜性等方面都不能讓人滿意。李美安[6]介紹了一種用循環(huán)編碼產(chǎn)生請(qǐng)求集的互斥算法，它通過循環(huán)編碼產(chǎn)生請(qǐng)求集的方式得出一種消息復(fù)雜度較低、容錯(cuò)性能高且同步時(shí)間短的對(duì)稱分布式互斥算法。但由于李氏循環(huán)編碼互斥算法的初始化節(jié)點(diǎn)數(shù)較少，因此算法的時(shí)間復(fù)雜度還是較高。

1 系統(tǒng)模型

設(shè)系統(tǒng)的節(jié)點(diǎn)數(shù)為 N，并從 0～N-1對(duì)節(jié)點(diǎn)編號(hào)，第i個(gè)節(jié)點(diǎn)的ID號(hào)為i-1，假定系統(tǒng)的節(jié)點(diǎn)與通信均可靠，各節(jié)點(diǎn)沒有共享存儲(chǔ)器和共同的物理時(shí)鐘，節(jié)點(diǎn)間依靠消息進(jìn)行異步通信，并且消息通信時(shí)間延遲無法預(yù)知。

1.1 對(duì)稱請(qǐng)求集產(chǎn)生的條件

用SN表示包含N個(gè)節(jié)點(diǎn)的分布式系統(tǒng)，Si表示系統(tǒng)中 ID號(hào)為 i的節(jié)點(diǎn)，Ri表示節(jié)點(diǎn) Si的請(qǐng)求集，k、n等為常數(shù)。

Maekawa提出了對(duì)稱請(qǐng)求集應(yīng)滿足的4個(gè)條件，即：

A1：?i，j∈[0，N-1]，Ri∩Rj≠?。 即任意兩個(gè)節(jié)點(diǎn)的請(qǐng)求集交集不為空。

A2：?i∈[0，N-1]，Si∈Ri。 即任意節(jié)點(diǎn)的 請(qǐng) 求集 包含該節(jié)點(diǎn)本身。

A3：?i，j∈[0，N-1]，i≠j，|Ri|=|Rj|=k。 即每個(gè)節(jié)點(diǎn)的請(qǐng)求集長(zhǎng)度相同，都包含k個(gè)節(jié)點(diǎn)。

A4：?i∈[0，N-1]，|{Rj|Si∈Rj，j∈[0，N-1]}|=k。 即任一節(jié)點(diǎn)都屬于k個(gè)請(qǐng)求集。

滿足A1～A4的請(qǐng)求集稱為對(duì)稱請(qǐng)求集。能夠生成對(duì)稱請(qǐng)求集的算法稱為對(duì)稱請(qǐng)求集生成算法。利用對(duì)稱請(qǐng)求集實(shí)現(xiàn)分布式互斥的算法稱為對(duì)稱分布式互斥算法。

1.2 請(qǐng)求集產(chǎn)生算法的相關(guān)概念

為了減少在生成請(qǐng)求集過程中的循環(huán)次數(shù)，本文提出了松弛循環(huán)差集的定義以及循環(huán)請(qǐng)求集與松弛差集等價(jià)的定理，即：

定義 1（松弛正向差集）：設(shè) SUB={xi|i∈[1，n]}為有限集合D的一個(gè)子集，且|D|=N，|SUB|=k。如果?x∈D，至少存在一個(gè)有序數(shù)對(duì)（xj，xi），xi，xj∈SUB，使得 x=（xj-xi）mod（N）（j＞i），則稱 SUB為 D的松弛正向差集。

定理：循環(huán)請(qǐng)求集與松弛正向差集等價(jià)。

循環(huán)編碼算法中已經(jīng)證明，循環(huán)編碼所產(chǎn)生的請(qǐng)求集滿足Maekawa所提出的4個(gè)條件，其產(chǎn)生的請(qǐng)求集是對(duì)稱請(qǐng)求集，而在松弛差集算法中證明了循環(huán)請(qǐng)求集與松弛差集等價(jià)的定理，因此松弛循環(huán)差集所產(chǎn)生的請(qǐng)求集也是對(duì)稱請(qǐng)求集。而本算法是在松弛差集算法的基礎(chǔ)上進(jìn)行的改進(jìn)，即通過增加初始化請(qǐng)求集的長(zhǎng)度，來縮短算法的時(shí)間復(fù)雜度，以求更快地找到所求請(qǐng)求集，因此本算法所產(chǎn)生的請(qǐng)求集也是對(duì)稱請(qǐng)求集。

1.3 請(qǐng)求集初始化理論

根據(jù)Maekawa在參考文獻(xiàn)[1]中提出的請(qǐng)求集應(yīng)滿足的條件可知，系統(tǒng)的節(jié)點(diǎn)數(shù)（N）最少需要用長(zhǎng)度為m的請(qǐng)求集表示（N＜m（m-1）+1），那么基于循環(huán)編碼的請(qǐng)求集生成算法的請(qǐng)求集方陣中每行至少有一個(gè)1，并且每個(gè)1與碼字的第0位的距離不相同。

依據(jù)此條件考慮到2的冪之間的差的互異性，本算法在折半循環(huán)編碼算法中再以2i+1-2i為間距對(duì)請(qǐng)求集方陣第0行請(qǐng)求集碼字進(jìn)行初始化。為了更好地優(yōu)化循環(huán)基，令 2k≤N/2，因?yàn)橹挥?2k≤N/2時(shí)才能保證初始化節(jié)點(diǎn)的任意兩點(diǎn)間的距離不等。比如對(duì)于10個(gè)節(jié)點(diǎn)的請(qǐng)求集為1101000100，由于第3個(gè)節(jié)點(diǎn)和第0個(gè)節(jié)點(diǎn)之間的距離與第7個(gè)節(jié)點(diǎn)和第0個(gè)節(jié)點(diǎn)之間的距離相同，為了使循環(huán)基也變成單向的，應(yīng)使 2k≤N/2，從而（2j-2i）mod N（i≠j且 i，j∈k）之間的距離不等。為了減少循環(huán)編碼的次數(shù)，本算法在折半循環(huán)編碼算法的基礎(chǔ)上引入松弛正向差集，即當(dāng)（xj-xi）mod（N）（j＞i）在小于 N/2中的所有節(jié)點(diǎn)都可以表示時(shí)，此時(shí)的請(qǐng)求集即為所求的請(qǐng)求集。

綜上所述，通過松弛正向差集的優(yōu)化能更好地提高本算法的時(shí)間復(fù)雜度。

2 請(qǐng)求集產(chǎn)生的算法的描述與實(shí)現(xiàn)

2.1 數(shù)據(jù)結(jié)構(gòu)

（1）請(qǐng)求基向量 IN。IN是一個(gè)集合，包含已納入請(qǐng)求集的節(jié)點(diǎn)，其下標(biāo)從0開始。

（2）標(biāo)志向量 TN。TN含有 N個(gè)分量，分量 TN[i-1]標(biāo)記系統(tǒng)SN的對(duì)應(yīng)節(jié)點(diǎn)Si的狀態(tài)。TN[i-1]=1表明Si已被請(qǐng)求基IN中已有元素的模N差表示，TN[i-1]=0表明請(qǐng)求基IN中已有元素的模N差還不能表示節(jié)點(diǎn)Si。

（3）向量狀態(tài)字S。S可取0或者 1，S=1表示算法運(yùn)行結(jié)束。

2.2 請(qǐng)求集生成算法描述

（1）令 2k≤?N/2」求出 k，將系統(tǒng)第 0個(gè)節(jié)點(diǎn)的碼字 I0中 20-1，21-1，……2k+1-1 （1≤k＜N）位初始化為 1，并令TN在對(duì)應(yīng)位=1，向量狀態(tài)字S的初始值為S[0]=0。

（2）對(duì)IN所得到的初始化節(jié)點(diǎn)進(jìn)行松弛正向差集：即（（2j-1）-（2i-1））mod（N）（N-1＞j＞i＞0），對(duì)沒有初始化的節(jié)點(diǎn)進(jìn)行初始化，并對(duì)其所對(duì)應(yīng)的標(biāo)志數(shù)組置1，如果有令 TN[i]=1，否則 TN[i]=0；并且 S遍歷 TN中前 2k+1-1位，如全部為 1，則 S[0]=1；否則轉(zhuǎn) S[0]=0。

（3）若 TN的前 2k+1-1位還存在 TN[i]=0，則令最大位置處為 1，并令 TN對(duì)應(yīng)位置處為1，轉(zhuǎn)（2）。

1）“蜜月溫泉之旅”冬季舉辦婚禮的較多，可以抓住這個(gè)機(jī)遇進(jìn)行以“蜜月溫泉之旅”為主題的產(chǎn)品設(shè)計(jì)，在西海瑤池中結(jié)合其自身的溫泉場(chǎng)所特點(diǎn)，進(jìn)行一些改進(jìn)設(shè)計(jì)出專供情侶使用的浴池和套房。并給予多種產(chǎn)品方案和優(yōu)惠方案，供不同情侶游客選擇。

（4）直到向量狀態(tài)字S[0]=1，算法結(jié)束。

2.3 請(qǐng)求集產(chǎn)生算法的實(shí)例實(shí)現(xiàn)

為驗(yàn)證算法的正確性與有效性，以請(qǐng)求集個(gè)數(shù)N=48為例，描述了各節(jié)點(diǎn)請(qǐng)求集的求取過程。

因?yàn)?24＜48/2＜25，所以：I[0]=1，I[1]=1，I[3]=1，I[7]=1，I[15]=1，I[31]=1。

（1）初始化：

請(qǐng)求基向量 （IN）：[1101000100 0000010000 0000000000 0100000000 00000000]

標(biāo) 志 向 量 （TN）：[1101000100 0000010000 0000000000 0100000000 00000000]

向量狀態(tài)（S）：[0]

請(qǐng)求基向量 （IN）：[1111101110 0010111000 0000100010 1100000000 00000000]

標(biāo) 志 向 量 （TN）：[1111101110 0010111000 0000100010 1100000000 00000000]

向量狀態(tài)（S）：[0]

（3）從TN的前2k+1-1位往前找第1個(gè)不為0的節(jié)點(diǎn)，令 IN[29]=1，并對(duì) TN、S做相應(yīng)的變化。

請(qǐng)求基向量（IN）：[1111111110 0011111100 0111111111 1100000000 00000000]

標(biāo) 志 向 量 （TN）：[1111111110 0011111100 0111111111 1100000000 00000000]

向量狀態(tài)（S）：[0]

（4）向量狀態(tài)字 S=1，算法結(jié)束。

請(qǐng)求基向量（IN）：[1111111111 1111111111 1111111111 1100000000 00000000]

標(biāo) 志 向 量 （TN）：[111111111 1111111111 1111111111 1100000000 00000000]]

向量狀態(tài)（S）：[1]

從以上的計(jì)算過程可知，本算法最終生成的請(qǐng)求集長(zhǎng)度為9，與在折半循環(huán)編碼算法中得到的的請(qǐng)求集個(gè)數(shù)相同，請(qǐng)求集為[1101000100010001000010000000010100000000000000000]。但是在算法的比較次數(shù)上，本算法的比較次數(shù)為29次，遍歷5次，而在折半循環(huán)編碼算法中的比較次數(shù)為（48×48）/2=1 152次，遍歷216次。可見本算法顯著提高了CPU的工作效率，計(jì)算量顯著減少。

3 性能分析

分布式互斥請(qǐng)求集生成算法的性能度量主要有3個(gè)指標(biāo)：請(qǐng)求集長(zhǎng)度、時(shí)間復(fù)雜度和空間復(fù)雜度。

3.1 請(qǐng)求集長(zhǎng)度

表1 幾種典型算法的請(qǐng)求集長(zhǎng)度的比較

3.2 時(shí)間復(fù)雜度

依據(jù)程序的執(zhí)行過程，當(dāng)節(jié)點(diǎn)數(shù)N比較大時(shí)，本文算法的時(shí)間復(fù)雜度計(jì)算過程如下：

（1）初始化請(qǐng)求基向量 IN，生成系統(tǒng)標(biāo)志向量IN。若節(jié)點(diǎn)數(shù)為 N，則初始化請(qǐng)求集長(zhǎng)度為：n=log2?N/2」，生成對(duì)應(yīng)的 AN需要計(jì)算n×（n-1）/2次。

不同節(jié)點(diǎn)數(shù)下算法復(fù)雜度比較如表2所示，由表2可知，本文的算法的時(shí)間復(fù)雜度為O（N），而折半循環(huán)編碼算法的時(shí)間復(fù)雜度為O（N2/2），由此可見，在節(jié)點(diǎn)數(shù)N相對(duì)較大時(shí)，本算法的效率就遠(yuǎn)大于折半循環(huán)編碼算法，能以更短的時(shí)間生成所需請(qǐng)求集，易于實(shí)際應(yīng)用。

表2 兩種算法的關(guān)鍵節(jié)點(diǎn)比較次數(shù)

3.3 空間復(fù)雜度

本文在折半循環(huán)編碼算法基礎(chǔ)上，在提高循環(huán)編碼初始化節(jié)點(diǎn)的數(shù)量和引進(jìn)松弛正向差集的概念兩方面進(jìn)行合理的改進(jìn)，使空間復(fù)雜度由O（N2/2）下降到 O（N），時(shí)間復(fù)雜度由O（N2/2）降到現(xiàn)在的 O（N/2），因此本算法易于實(shí)際應(yīng)用。

[2]AGRAWAL D,ABBADI A E.An efficient and fault-tolerant solution for distributed mutual exclusion[J].ACM Transactions on Computer Systems，1991，9（1）：158-167.

[3]CHEUNG S Y，AMMAR M H.AHAMAD M.The grid protocol： a high performance scheme for maintaining replicated data[J].IEEE Transactions on Knowledge and Data Eng，1992，12（6）：42-53.

[4]KUMAR A.Hierarchical quorum consensus：a new algorithm formanaging replicated data[J].IEEE Transactions on Computer Systems，1991，9（6）：996-1004.

[5]HARADA T，YAMASHITA M.Transversal merge operation：a no dominated coterie construction method for distributed mutualexclusion[J].IEEE Transactionson Paralleland Distributed Systems，2005，2（2）：183-192.

[6]LI Meian.A high performance distributed mutual exclusion algorithm base on cyclic coding[J].Acta Electronica Sinica on 2005，33（8）：1397-1402.

[7]陳志黨，李美安.一種新的分布式互斥請(qǐng)求集生成算法[J].微計(jì)算機(jī)信息，2010（3-9）：211-212.

[8]LUK Waishing.Two new quorum based algorithmsfor distributed mutual exclusion[C].Proceeding of the 17th International Conference on Distributed Computing Systems，IEEE，1997：100-106.

High-performance distributed request set generation algorithm based on difference sets

Chen Zhidang，Li Meian，Wang Chunshen，Lin Lan

（College of Computer and Information Engineering，Inner Mongolia Agricultural University，Huhehaote 010018，China）

relaxed positive difference set；quorum;binary cyclic coding

TP393

A

1674-7720（2011）03-0046-03

2010-10-08）

陳志黨，男，1985年生，碩士研究生，主要研究方向：分布式計(jì)算，分布式操作系統(tǒng)，寬帶網(wǎng)絡(luò)與通信。

李美安，男，1973年生，教授，碩士生導(dǎo)師，主要研究方向：分布式計(jì)算，分布式操作系統(tǒng)，寬帶網(wǎng)絡(luò)與通信。

王春申，女，1985年生，碩士研究生，主要研究方向：圖像處理，圖像復(fù)原。