摘  要： 在折半循環(huán)編碼算法的基礎上，依據(jù)貪心策略對可納入節(jié)點進行局部求最優(yōu)的方式來生成請求集的算法，從而使算法的請求集長度下降了一個數(shù)量級，接近。
關鍵詞： 初始化；折半循環(huán)編碼；局部貪心策略；請求集

　基于請求集的分布式互斥算法作為Maekawa算法[1]的推廣，近年來得到了人們的廣泛關注，人們提出了許多各具特色的算法來構建請求集，以降低分布式互斥算法的消息復雜度或者提高分布式互斥算法在其他方面的性能，例如李美安通過循環(huán)編碼產(chǎn)生請求集的方式，得出一種消息復雜度較低、容錯性能高且同步時間短的對稱分布式互斥算法[2]，但由于該算法的初始化節(jié)點數(shù)較少，因此算法的時間復雜度還是比較高。為了改善請求集生成算法的性能，陳志黨在該算法的基礎上，提出了一種通過提高請求集初始化節(jié)點的數(shù)量的方式來改善請求集生成算法，即折半循環(huán)編碼算法[3]，從而更快、更優(yōu)地產(chǎn)生請求集，使算法的時間復雜度大幅度降低。
　由于折半循環(huán)算法只是簡單地提高了算法的時間復雜度和空間復雜度，算法沒有對請求集的長度有所提高，所生成的請求集長度仍然保持在之間，因此本文在貪心策略的基礎上，依據(jù)貪心策略對可納入節(jié)點進行局部求最優(yōu)的方式，來生成請求集的算法，從而更快、更優(yōu)地產(chǎn)生請求集。
1 系統(tǒng)模型
　設系統(tǒng)的節(jié)點數(shù)為N，并從0~N-1對節(jié)點編號，第i個節(jié)點的ID號為i-1。假定系統(tǒng)的節(jié)點與通信均可靠，各節(jié)點沒有共享存儲器和共同的物理時鐘，節(jié)點間依靠消息進行異步通信，并且無法預知消息通信時間延遲。

　滿足條件A1～A4的請求集稱為對稱請求集，能夠生成對稱請求集的算法稱為對稱請求集生成算法，利用對稱請求集實現(xiàn)分布式互斥的算法稱為對稱分布式互斥算法。
1.2 請求集產(chǎ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ǎn)生的請求集也是對稱請求集。

1.3 貪心策略理論
1.3.1 貪心選擇性質(zhì)
　貪心選擇性質(zhì)是指應用同一規(guī)則f，將原問題變?yōu)橐粋€相似的、但規(guī)模更小的子問題，此后的每一步都是當前看似最佳的選擇。這種選擇依賴于已做出的選擇，但不依賴于未做出的選擇。從全局來看，運用貪心策略解決的問題在程序的運行過程中無回溯過程。
1.3.2 局部最優(yōu)解
　貪心策略通常是自頂向下進行的。第一步為一個貪心選擇，將原問題變成一個相似的、但規(guī)模更小的問題，而后的每一步都是當前看似最佳的選擇。這種選擇可能依賴于已作出的所有選擇，但不依賴有待于做的選擇或子問題的解。
　從求解的全過程來看，每一次貪心選擇都將當前問題歸納為更小的相似子問題，而每一個選擇都僅做一次，無重復回溯過程。因此，貪心法有較高的時間效率。
2 請求集產(chǎn)生的算法的描述與實現(xiàn)
2.1 數(shù)據(jù)結構
　設系統(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個分量，每個分量對應AN的一行，該分量為1表示AN對應行和第0行有交點((a0&ai)！=0)，反之，則說明沒有交點。
表示狀態(tài)數(shù)組T：長度為N的數(shù)組。T[i]=1用來表示差集i在請求集中已被表示，T[ i]=0表示差集i在請求集中沒被表示。
　最小重復記錄字count：用來表示第j行(1≤j<[N/2])和第0行第一次出現(xiàn)沒有交點。

 
3.3 空間復雜度
    由于折半循環(huán)算法引入了對稱請求集的概念，只計算前「N/2?骎行和第0行有交點即可?？臻g復雜度為O(N2/2)，而本算法只是在貪心策略的基礎上，依據(jù)貪心策略對可納入節(jié)點通過局部求最優(yōu)的方式來生成請求集，所以，空間復雜度與折半循環(huán)算法一樣。
    公平、健壯和易于實現(xiàn)的分布式互斥算法是研究人員追求的最終目標，本文在陳志黨提出的折半循環(huán)編碼算法的基礎上，依據(jù)貪心策略對可納入節(jié)點進行局部求最優(yōu)的方式來生成請求集的算法，從而產(chǎn)生更優(yōu)的請求集，使算法的請求集長度下降到，空間復雜度可近似為O(N2/2)，時間復雜度為O(N/2)，因此本算法易于實際應用。
參考文獻
[1] MAEKAWA M. A Nalgorithm for mutual exclusion in decentralized systems[J]. ACM Transactions on Computer Systems， 1985，3(2)：145-159.
[2] 李美安，劉心松，王征.一種基于松弛循環(huán)差集的高性能分布式互斥算法[J].電子學報，2007，35(1)：58-63.
[3] 陳志黨，李美安.一種新的分布式互斥請求集生成算法[J].微計算機信息，2010(3-9)：211-212.
[4] 申二威，李美安.一種改進的高效分布式互斥請求集生成算法[J].微計算機信息，2010(8-24)：201-20.