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

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

　滿足條件A1～A4的請求集稱為對稱請求集，能夠生成對稱請求集的算法稱為對稱請求集生成算法，利用對稱請求集實(shí)現(xiàn)分布式互斥的算法稱為對稱分布式互斥算法。
1.2 請求集產(chǎn)生算法的相關(guān)概念
　為了減少在生成請求集過程中的循環(huán)次數(shù)，本文提出了松弛循環(huán)差集的定義、貪心算法定義以及循環(huán)請求集與松弛差集等價(jià)的定理。
　定義(貪心策略)：貪心策略是指從問題的初始狀態(tài)出發(fā)，通過若干次的貪心選擇而得出最優(yōu)值(或較優(yōu)解)的一種解題方法。
　定理 循環(huán)請求集與松弛差集等價(jià)。
　在循環(huán)編碼算法中已經(jīng)證明，循環(huán)編碼所產(chǎn)生的請求集滿足MAEKAWA M所提出的四個條件，其產(chǎn)生的請求集是對稱請求集，而松弛差集算法中證明了循環(huán)請求集與松弛差集等價(jià)的定理，因此，松弛循環(huán)差集所產(chǎn)生的請求集也是對稱請求集。而本算法是在松弛差集算法的基礎(chǔ)上進(jìn)行的改進(jìn)，即通過增加初始化請求集的長度來縮短算法的時間復(fù)雜度，以求更快地找到所求請求集，因此，本算法所產(chǎn)生的請求集也是對稱請求集。

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

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