李美安，陳志黨，王春申

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

基于請求集的分布式互斥算法作為Maekawa算法[1]的推廣，近年來得到了人們的廣泛關(guān)注，人們提出了許多各具特色的算法來構(gòu)建請求集，以降低分布式互斥算法的消息復(fù)雜度或者提高分布式互斥算法在其他方面的性能，例如李美安通過循環(huán)編碼產(chǎn)生請求集的方式，得出一種消息復(fù)雜度較低、容錯性能高且同步時間短的對稱分布式互斥算法[2]，但由于該算法的初始化節(jié)點數(shù)較少，因此算法的時間復(fù)雜度還是比較高。為了改善請求集生成算法的性能，陳志黨在該算法的基礎(chǔ)上，提出了一種通過提高請求集初始化節(jié)點的數(shù)量的方式來改善請求集生成算法，即折半循環(huán)編碼算法[3]，從而更快、更優(yōu)地產(chǎn)生請求集，使算法的時間復(fù)雜度大幅度降低。

1 系統(tǒng)模型

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

1.1 對稱請求集產(chǎn)生的條件

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

MAEKAWA M提出了對稱請求集應(yīng)滿足的四個條件，即：

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

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

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

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

滿足條件A1～A4的請求集稱為對稱請求集，能夠生成對稱請求集的算法稱為對稱請求集生成算法，利用對稱請求集實現(xiàn)分布式互斥的算法稱為對稱分布式互斥算法。

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

為了減少在生成請求集過程中的循環(huán)次數(shù)，本文提出了松弛循環(huán)差集的定義、貪心算法定義以及循環(huán)請求集與松弛差集等價的定理。

定義(貪心策略)：貪心策略是指從問題的初始狀態(tài)出發(fā)，通過若干次的貪心選擇而得出最優(yōu)值(或較優(yōu)解)的一種解題方法。

定理 循環(huán)請求集與松弛差集等價。

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

1.3 貪心策略理論

1.3.1貪心選擇性質(zhì)

貪心選擇性質(zhì)是指應(yīng)用同一規(guī)則f，將原問題變?yōu)橐粋€相似的、但規(guī)模更小的子問題，此后的每一步都是當前看似最佳的選擇。這種選擇依賴于已做出的選擇，但不依賴于未做出的選擇。從全局來看，運用貪心策略解決的問題在程序的運行過程中無回溯過程。

1.3.2局部最優(yōu)解

貪心策略通常是自頂向下進行的。第一步為一個貪心選擇，將原問題變成一個相似的、但規(guī)模更小的問題，而后的每一步都是當前看似最佳的選擇。這種選擇可能依賴于已作出的所有選擇，但不依賴有待于做的選擇或子問題的解。

從求解的全過程來看，每一次貪心選擇都將當前問題歸納為更小的相似子問題，而每一個選擇都僅做一次，無重復(fù)回溯過程。因此，貪心法有較高的時間效率。

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

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

設(shè)系統(tǒng)的節(jié)點數(shù)為N，系統(tǒng)請求集方陣AN是N×N的方陣，其行列編號均為0～N-1，AN第 i行表示系統(tǒng)的第i個節(jié)點的請求集碼字，用 ai表示，aij表示AN的第 i行第j列元素，它的值表示節(jié)點j在第i個節(jié)點的請求集碼字中是否被選中，aij為1表示選中，為0表示沒被選中。

為了判斷是否產(chǎn)生請求集，引進標記數(shù)組 TN，它具有N個分量，每個分量對應(yīng)AN的一行，該分量為1表示AN對應(yīng)行和第0行有交點((a0&ai)！=0)，反之，則說明沒有交點。

表示狀態(tài)數(shù)組T：長度為N的數(shù)組。T[i]=1用來表示差集i在請求集中已被表示，T[i]=0表示差集i在請求集中沒被表示。

最小重復(fù)記錄字 count：用來表示第 j行(1≤j＜「N/2?)和第0行第一次出現(xiàn)沒有交點。

2.2 請求集生成算法描述

(1)令 2k≤?N/2」，求出k，將系統(tǒng)第 0 個節(jié)點的碼字a0中 20-1，21-1，…，2k-1(1≤k＜N)位初始 化為 1，并令T[0]=1。

(2)對第 0 行向右進行循環(huán)右移 i位(0≤i＜「N/2?)得到第i行，判斷第0行和第i行是否有交點，如果有交點，令 T[i]=1，i++，轉(zhuǎn)(2)，否則轉(zhuǎn)(3)。

(3)若第 0行和第 i行沒有交點，則 count=i，遍歷第0行中 a[0][j]=0(j|0≤j＜N)的所有情況，在第 0行中置 a[0][j]=1，并令 T[i]=1，求以上各種情況下 count的最大值，并在count取最大值時，在第一行所對應(yīng)的節(jié)點j處，令 a[0][j]=1為插入節(jié)點，轉(zhuǎn)(2)。

(4)直到 T 前「N/2?行都為 1 或者 count＞「N/2?時，算法結(jié)束。

2.3 請求集產(chǎn)生算法的實例實現(xiàn)

以請求集個數(shù)N=13為例，圖1～圖 4描述了各節(jié)點請求集的求取過程。

由于 22＜「13/2?＜23，所 以 a[0][0]=1，a[0][1]=1，a[0][3]=1，T[0]=1。

圖1 初始化

圖2 第一步令a[0][2]=1，count=4

圖3 第三步令a[5][4]=1，count=5

圖4 第六步 算法結(jié)束

首先初始化，利用循環(huán)右移的方法，當?shù)降谒男械臅r候和第一行沒有節(jié)點，如圖 1，則遍歷第 0行令 a[0][2]=0，并令 T[2]=1，繼續(xù)利用循環(huán)右移，得到 count=4，如圖2所示。依次類推，當a[0][9]=1時，count=7，由于前T「N/2?行都為 1，如圖 4所示，則算法結(jié)束。

3 性能分析

分布式互斥請求集生成算法的性能度量主要有三個指標：請求集長度、時間復(fù)雜度和空間復(fù)雜度。本文將分別分析這些指標。

3.1 請求集長度說的

表1比較了幾種典型分布式互斥算法所產(chǎn)生的請求集長度，其中Bin-cyclic代表折半循環(huán)編碼算法。

表1 幾種分布式互斥算法的請求集大小的比較

3.2 時間復(fù)雜度

3.3 空間復(fù)雜度

由于折半循環(huán)算法引入了對稱請求集的概念，只計算前「N/2?行和第0行有交點即可。空間復(fù)雜度為O(N2/2)，而本算法只是在貪心策略的基礎(chǔ)上，依據(jù)貪心策略對可納入節(jié)點通過局部求最優(yōu)的方式來生成請求集，所以，空間復(fù)雜度與折半循環(huán)算法一樣。

[1]MAEKAWA M.A Nalgorithm formutualexclusion in decentralized systems[J].ACM Transactions on Computer Systems， 1985，3(2)：145-159.

[2]李美安，劉心松，王征.一種基于松弛循環(huán)差集的高性能分布式互斥算法[J].電子學(xué)報，2007，35(1)：58-63.

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

[4]申二威，李美安.一種改進的高效分布式互斥請求集生成算法[J].微計算機信息，2010(8-24)：201-20.