一種貪心策略的更高效的請求集生成算法＊

李美安，陳志黨，王春申

(內蒙古農業大學 計算機科學與技術學院，內蒙古 呼和浩特 010018)

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

1 系統模型

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

1.1 對稱請求集產生的條件

用SN表示包含N個節點的分布式系統，Si表示系統中 ID號為 i的節點，Ri表示節點 Si的請求集，k、n等為常數。

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

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

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

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

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

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

1.2 請求集產生算法的相關概念

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

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

定理 循環請求集與松弛差集等價。

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

1.3 貪心策略理論

1.3.1貪心選擇性質

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

1.3.2局部最優解

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

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

2 請求集產生的算法的描述與實現

2.1 數據結構

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

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

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

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

2.2 請求集生成算法描述

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

(2)對第 0 行向右進行循環右移 i位(0≤i＜「N/2?)得到第i行，判斷第0行和第i行是否有交點，如果有交點，令 T[i]=1，i++，轉(2)，否則轉(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取最大值時，在第一行所對應的節點j處，令 a[0][j]=1為插入節點，轉(2)。

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

2.3 請求集產生算法的實例實現

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

由于 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 第六步 算法結束

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

3 性能分析

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

3.1 請求集長度說的

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

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

3.2 時間復雜度

3.3 空間復雜度

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

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

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

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

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