摘 要: 在折半循環(huán)編碼算法的基礎(chǔ)上,依據(jù)貪心策略對(duì)可納入節(jié)點(diǎn)進(jìn)行局部求最優(yōu)的方式來(lái)生成請(qǐng)求集的算法,從而使算法的請(qǐng)求集長(zhǎng)度下降了一個(gè)數(shù)量級(jí),接近。
關(guān)鍵詞: 初始化;折半循環(huán)編碼;局部貪心策略;請(qǐng)求集
基于請(qǐng)求集的分布式互斥算法作為Maekawa算法[1]的推廣,近年來(lái)得到了人們的廣泛關(guān)注,人們提出了許多各具特色的算法來(lái)構(gòu)建請(qǐng)求集,以降低分布式互斥算法的消息復(fù)雜度或者提高分布式互斥算法在其他方面的性能,例如李美安通過(guò)循環(huán)編碼產(chǎn)生請(qǐng)求集的方式,得出一種消息復(fù)雜度較低、容錯(cuò)性能高且同步時(shí)間短的對(duì)稱分布式互斥算法[2],但由于該算法的初始化節(jié)點(diǎn)數(shù)較少,因此算法的時(shí)間復(fù)雜度還是比較高。為了改善請(qǐng)求集生成算法的性能,陳志黨在該算法的基礎(chǔ)上,提出了一種通過(guò)提高請(qǐng)求集初始化節(jié)點(diǎn)的數(shù)量的方式來(lái)改善請(qǐng)求集生成算法,即折半循環(huán)編碼算法[3],從而更快、更優(yōu)地產(chǎn)生請(qǐng)求集,使算法的時(shí)間復(fù)雜度大幅度降低。
由于折半循環(huán)算法只是簡(jiǎn)單地提高了算法的時(shí)間復(fù)雜度和空間復(fù)雜度,算法沒(méi)有對(duì)請(qǐng)求集的長(zhǎng)度有所提高,所生成的請(qǐng)求集長(zhǎng)度仍然保持在之間,因此本文在貪心策略的基礎(chǔ)上,依據(jù)貪心策略對(duì)可納入節(jié)點(diǎn)進(jìn)行局部求最優(yōu)的方式,來(lái)生成請(qǐng)求集的算法,從而更快、更優(yōu)地產(chǎn)生請(qǐng)求集。
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)沒(méi)有共享存儲(chǔ)器和共同的物理時(shí)鐘,節(jié)點(diǎn)間依靠消息進(jìn)行異步通信,并且無(wú)法預(yù)知消息通信時(shí)間延遲。
滿足條件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)求集過(guò)程中的循環(huán)次數(shù),本文提出了松弛循環(huán)差集的定義、貪心算法定義以及循環(huán)請(qǐng)求集與松弛差集等價(jià)的定理。
定義(貪心策略):貪心策略是指從問(wèn)題的初始狀態(tài)出發(fā),通過(guò)若干次的貪心選擇而得出最優(yōu)值(或較優(yōu)解)的一種解題方法。
定理 循環(huán)請(qǐng)求集與松弛差集等價(jià)。
在循環(huán)編碼算法中已經(jīng)證明,循環(huán)編碼所產(chǎn)生的請(qǐng)求集滿足MAEKAWA M所提出的四個(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),即通過(guò)增加初始化請(qǐng)求集的長(zhǎng)度來(lái)縮短算法的時(shí)間復(fù)雜度,以求更快地找到所求請(qǐng)求集,因此,本算法所產(chǎn)生的請(qǐng)求集也是對(duì)稱請(qǐng)求集。
1.3 貪心策略理論
1.3.1 貪心選擇性質(zhì)
貪心選擇性質(zhì)是指應(yīng)用同一規(guī)則f,將原問(wèn)題變?yōu)橐粋€(gè)相似的、但規(guī)模更小的子問(wèn)題,此后的每一步都是當(dāng)前看似最佳的選擇。這種選擇依賴于已做出的選擇,但不依賴于未做出的選擇。從全局來(lái)看,運(yùn)用貪心策略解決的問(wèn)題在程序的運(yùn)行過(guò)程中無(wú)回溯過(guò)程。
1.3.2 局部最優(yōu)解
貪心策略通常是自頂向下進(jìn)行的。第一步為一個(gè)貪心選擇,將原問(wèn)題變成一個(gè)相似的、但規(guī)模更小的問(wèn)題,而后的每一步都是當(dāng)前看似最佳的選擇。這種選擇可能依賴于已作出的所有選擇,但不依賴有待于做的選擇或子問(wèn)題的解。
從求解的全過(guò)程來(lái)看,每一次貪心選擇都將當(dāng)前問(wèn)題歸納為更小的相似子問(wèn)題,而每一個(gè)選擇都僅做一次,無(wú)重復(fù)回溯過(guò)程。因此,貪心法有較高的時(shí)間效率。
2 請(qǐng)求集產(chǎn)生的算法的描述與實(shí)現(xiàn)
2.1 數(shù)據(jù)結(jié)構(gòu)
設(shè)系統(tǒng)的節(jié)點(diǎn)數(shù)為N,系統(tǒng)請(qǐng)求集方陣AN是N×N的方陣,其行列編號(hào)均為0~N-1,AN第i行表示系統(tǒng)的第i個(gè)節(jié)點(diǎn)的請(qǐng)求集碼字,用ai表示,aij表示AN的第i行第j列元素,它的值表示節(jié)點(diǎn)j在第i個(gè)節(jié)點(diǎn)的請(qǐng)求集碼字中是否被選中,aij為1表示選中,為0表示沒(méi)被選中。
為了判斷是否產(chǎn)生請(qǐng)求集,引進(jìn)標(biāo)記數(shù)組TN,它具有N個(gè)分量,每個(gè)分量對(duì)應(yīng)AN的一行,該分量為1表示AN對(duì)應(yīng)行和第0行有交點(diǎn)((a0&ai)!=0),反之,則說(shuō)明沒(méi)有交點(diǎn)。
表示狀態(tài)數(shù)組T:長(zhǎng)度為N的數(shù)組。T[i]=1用來(lái)表示差集i在請(qǐng)求集中已被表示,T[ i]=0表示差集i在請(qǐng)求集中沒(méi)被表示。
最小重復(fù)記錄字count:用來(lái)表示第j行(1≤j<[N/2])和第0行第一次出現(xiàn)沒(méi)有交點(diǎn)。
3.3 空間復(fù)雜度
由于折半循環(huán)算法引入了對(duì)稱請(qǐng)求集的概念,只計(jì)算前「N/2?骎行和第0行有交點(diǎn)即可??臻g復(fù)雜度為O(N2/2),而本算法只是在貪心策略的基礎(chǔ)上,依據(jù)貪心策略對(duì)可納入節(jié)點(diǎn)通過(guò)局部求最優(yōu)的方式來(lái)生成請(qǐng)求集,所以,空間復(fù)雜度與折半循環(huán)算法一樣。
公平、健壯和易于實(shí)現(xiàn)的分布式互斥算法是研究人員追求的最終目標(biāo),本文在陳志黨提出的折半循環(huán)編碼算法的基礎(chǔ)上,依據(jù)貪心策略對(duì)可納入節(jié)點(diǎn)進(jìn)行局部求最優(yōu)的方式來(lái)生成請(qǐng)求集的算法,從而產(chǎn)生更優(yōu)的請(qǐng)求集,使算法的請(qǐng)求集長(zhǎng)度下降到,空間復(fù)雜度可近似為O(N2/2),時(shí)間復(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] 陳志黨,李美安.一種新的分布式互斥請(qǐng)求集生成算法[J].微計(jì)算機(jī)信息,2010(3-9):211-212.
[4] 申二威,李美安.一種改進(jìn)的高效分布式互斥請(qǐng)求集生成算法[J].微計(jì)算機(jī)信息,2010(8-24):201-20.