分布式系統(tǒng)幾種典型一致性算法概述

1、對(duì)三種典型分布式任務(wù)分配算法的分析在分布式系統(tǒng)中非同居模塊間的數(shù)據(jù)傳遞產(chǎn)生處理機(jī)間的通信這種機(jī)間通信可能使得 增加處理機(jī)數(shù)目反而會(huì)引起系統(tǒng)吞吐量的降彳氐即產(chǎn)生“飽和效應(yīng)”。為降低飽和效應(yīng)，人 們傾向于把模塊分配到盡可能少的處理機(jī)上 但這又導(dǎo)致系統(tǒng)負(fù)載不平衡，從而降低了系統(tǒng)的 吞吐量。顯然，這是任務(wù)分配中相互沖突的兩個(gè)方面 不同的任務(wù)分配算法試圖用不同的策 略來(lái)平衡這兩個(gè)方面。傳統(tǒng)的分布式任務(wù)分配算法大致可分為三類(lèi)：基于圖論的分配算法，整數(shù)規(guī)劃方法和試 探法。這三類(lèi)算法并非互斥的，一類(lèi)算法中往往可以借鑒其它方法中的某些技術(shù)。下面，我 們先對(duì)這三類(lèi)典型算法進(jìn)行分析和比較然后給出一種試探法的改進(jìn)算法

2、。在討論中，我們假定提交的任務(wù)已分解成一組模塊并使模塊間的通信量盡可能小。還假定分配模式為：一任務(wù)被分解成m個(gè)模塊T= t1, t2,，tm,系統(tǒng)中有n個(gè)可利用的處理機(jī) P= 牛p2,，pn。任務(wù)分配的目的就是將這m個(gè)模塊分配到門(mén)個(gè)處理機(jī)上 使預(yù)期的性 能目標(biāo)函數(shù)值最小。1對(duì)三種典型算法的分析1基于圖論的分配算法基本思想是給定矩陣C表示模塊間的通信開(kāi)銷(xiāo)：mxmC= q .11W iW m& 1W jW m& q .為弓與t.間的通信量給定矩陣。訕表示模塊的執(zhí)行開(kāi)銷(xiāo);Q= qi .11W iW m& 1 W jW n& qi .為弓在p.上的執(zhí)行開(kāi)銷(xiāo)將模塊t1,七“，tm作為圖中結(jié)點(diǎn)，若兩模塊間

3、有數(shù)據(jù)傳遞,則相應(yīng)結(jié)點(diǎn)間有一條無(wú)向邊1996-04-26收稿*軟件工程國(guó)家重點(diǎn)實(shí)驗(yàn)室開(kāi)放基金部分資助。何炎祥，教授，研究方向：分布式OS與分布信息處理，并行程序設(shè)計(jì)與編譯系統(tǒng)。羅先林、吳思，研究生，研究方向：分布式OS與分布信息處理。邊上的權(quán)Wj .= ci .;處理機(jī)p1, p2，pn也作為圖中結(jié)點(diǎn)，若qj k8 ,則在ti與pk間有一 條邊，定義該邊上的權(quán)為Wj. k=1 n- 1Xqi. jn-2n- 1ci kO于是，可將該圖視為一個(gè)網(wǎng)絡(luò)，并定義n度割集為將網(wǎng)絡(luò)中各個(gè)結(jié)點(diǎn)分割成n個(gè)不相交的子集，使得每個(gè)子集中有且僅有一個(gè)處 理機(jī)結(jié)點(diǎn)?？梢宰C明，每個(gè)切口的開(kāi)銷(xiāo)正好是執(zhí)行開(kāi)銷(xiāo)和通信開(kāi)銷(xiāo)之和

4、，因此，在圖上執(zhí)行 MaxFlow /MinCut算法就可得到任務(wù)的最優(yōu)分配方案 。在現(xiàn)階段，僅有多項(xiàng)式復(fù)雜度n= 2的MaxFlow /MinCut算法，因此 基于圖論的分配算法僅限于在處理機(jī)數(shù)目小于3的環(huán)境 中使用，因而局限性較大。Lo在1 中提出了一種改進(jìn)算法。該算法分為迭代、匯總和貪心三個(gè)階段。在第一階段的每一輪迭代中，依次考慮每個(gè)結(jié)點(diǎn)P1, p2.，pn，把區(qū)和p.=P- p.作為兩個(gè)獨(dú)立的結(jié)點(diǎn)，并將所有到P- p.的邊用一個(gè)到p.的邊代替，該邊上的權(quán)為所有到P- pj的邊上的權(quán)之和。利用Max Flow /MinCut算法，可得到分配給R的模塊的一個(gè)子集。刪去在此輪迭代中已 分配給

5、的那些模塊結(jié)點(diǎn)，并定義未刪除的模塊tj與處理機(jī)pk間的權(quán)為qi, k= qi, j+ 2 tj為已分配給p的某個(gè)處理機(jī)的模塊ci, j若所有的模塊結(jié)點(diǎn)已分配完，或在最后一輪迭代中沒(méi)有模塊分配給某個(gè)處理機(jī) 則迭代階段 結(jié)束。Lo證明了迭代的終止性及若此時(shí)模塊分配完則將獲得最優(yōu)解。在匯總階段，首先計(jì)算一個(gè)優(yōu)化的n度割集的下界L =圣tjE Tmink(qi k) + minj 乂 rC( pj, p其中,C( ppr)為任意選擇的處理機(jī)間最小切口的開(kāi)銷(xiāo),T為所有第一階段中沒(méi)有分配的模 塊的集合:然后，檢查將剩余模塊指派到某個(gè)處理機(jī)上是否更合適若是，則算法結(jié)束，也得 到一個(gè)最優(yōu)解。否則進(jìn)入貪心階段。

6、將相互通信開(kāi)銷(xiāo)大的模塊匯集成簇同一簇中的模塊分 配到同一個(gè)處理機(jī)上，這樣得到的結(jié)果是次最優(yōu)的。這個(gè)改進(jìn)算法解決了基本算法在處理機(jī)數(shù)目上的限制。為使此算法更能反映真實(shí)情況，Lo還考慮了每個(gè)處理機(jī)上可利用資源的限制和同居模塊間的通信開(kāi)銷(xiāo) 并引入了沖突開(kāi)銷(xiāo) 的因素。此外,Lo提出了一種限制各處理機(jī)上模塊數(shù)的方法，其基本思想是：若m 2n,則 先進(jìn)行合一，并保證合一后的簇中模塊數(shù)目不超過(guò)B /2 ( B為一處理機(jī)上最大允許的模塊數(shù))。 重復(fù)這種合一過(guò)程，直至模塊簇?cái)?shù)目mW 2n,然后再用適當(dāng)算法將m個(gè)模塊簇按最小 執(zhí)行開(kāi)銷(xiāo)分配到n個(gè)處理機(jī)上。這個(gè)改進(jìn)算法利用了試探法中對(duì)模塊進(jìn)行合一的思想并直接利用了現(xiàn)

7、有的網(wǎng)絡(luò)算法，因此實(shí)現(xiàn)較簡(jiǎn)單，但算法開(kāi)銷(xiāo)大，因?yàn)镸ax Flow /MinCut算法的時(shí)間復(fù)雜度為O( a2log2+ a /n b),其中a , b分別為邊數(shù)和結(jié)點(diǎn)數(shù)。每次迭代中，每獲得分配給一個(gè)處理機(jī)的模塊子集的復(fù) 雜度為O( m4log2m)(設(shè)系統(tǒng)為全互連的),這樣，每次迭代的開(kāi)銷(xiāo)為O( nm4log2m),而最壞迭 代次數(shù)為m。因此，最壞情況下的復(fù)雜度為O( nm5log2m)。此外，該算法沒(méi)有明確反映實(shí)時(shí)性 和存儲(chǔ)方面的限制，沒(méi)有提供保護(hù)模塊優(yōu)先關(guān)系的機(jī)制，也不能衡量排隊(duì)延遲對(duì)吞吐量的影 響。1.2整數(shù)規(guī)劃方法基本思想是仍用前面定義的Q矩陣表示執(zhí)行開(kāi)銷(xiāo)，但用Vmxm表示模塊間的通信

8、開(kāi)銷(xiāo)：V= vi J1W iW m& 1W jW m&Vj ,ti 向 傳遞的數(shù)據(jù)量1997年2小型微型計(jì)算機(jī)系統(tǒng)同時(shí)引進(jìn)一個(gè)距離矩陣D :nxnD= di ,I1 W iW n& 1 W jW n& di ,pi 與p.間的距離模塊分配函數(shù)用矩陣X 來(lái)定義mxmX= xi .Il W i W m& 1 W j W n&xi .= 1 表示弓分配到p.上x(chóng)； j= 0 否則該分配方法的目標(biāo)函數(shù)定義為：T（ X） = k qi, kxi, k+kj iW Vi, jdk, rXi, kXj, r其中，常數(shù)w用來(lái)調(diào)節(jié)通信開(kāi)銷(xiāo)和執(zhí)行開(kāi)銷(xiāo)間的差異。此時(shí)任務(wù)分配即要找使T最小的那個(gè)X的指派。因此，這種方

9、法實(shí)質(zhì)上是帶有某些限制條件的隱式枚舉算法，其時(shí)間復(fù)雜度隨問(wèn)題規(guī)模成指數(shù)增長(zhǎng)。這顯然限制了算法的實(shí)用性。這種方法的優(yōu)點(diǎn)是很容易加入適當(dāng)?shù)南拗茥l件，以滿(mǎn)足實(shí)際環(huán)境的需要。2 提出了一種分支界限法，它用一棵搜索樹(shù)來(lái)表示分配問(wèn)題每個(gè)葉子結(jié)點(diǎn)處表示一 個(gè)分配方案。除了存儲(chǔ)限制和實(shí)時(shí)限制外，它還引入了以下限制條件：模塊優(yōu)先矩陣P*mxnpi j= 1表示tj不能分配給p.;pi, j= 0 否則J模塊互斥矩陣Emxm j= 1表示弓和匕不能分配給同一處理機(jī)；e； j= 0否則并允許一個(gè)任務(wù)（模塊）的多份拷貝，以提高系統(tǒng)的可靠性。該算法在每個(gè)分支處檢查P*, E關(guān)系和存儲(chǔ)及實(shí)時(shí)限制條件，若不滿(mǎn)足，則剪枝；若

10、滿(mǎn)足，則檢查這次分配后的部分開(kāi)銷(xiāo)是否超過(guò)已得到的最小全部開(kāi)銷(xiāo)若超過(guò)，則剪枝；否則 就分配，并選擇下一擴(kuò)充結(jié)點(diǎn)。若全部可能的路徑都被探查完，或規(guī)定的執(zhí)行時(shí)間已到，則算法結(jié)束。該算法的空間復(fù)雜度較小，只需記錄當(dāng)前最小開(kāi)銷(xiāo)的分配方案和此開(kāi)銷(xiāo)即可約為O（mn）。但時(shí)間復(fù)雜度仍可能是指數(shù)級(jí)的而且沒(méi)有保護(hù)模塊優(yōu)先規(guī)定的機(jī)制和實(shí)施負(fù)載平衡 的機(jī)制。對(duì)該算法，還可以進(jìn)行如下改進(jìn)：輸入模塊間的優(yōu)先規(guī)定，利用拓?fù)渑判蛩惴▽?duì)模塊進(jìn)行拓?fù)渑判虿⒁源隧樞蜃鳛閿U(kuò) 充下一結(jié)點(diǎn)的次序。在探查tj的氣分枝時(shí)，若弓有優(yōu)先模塊，則將它在pk上的執(zhí)行時(shí)間作如下調(diào)整：q i, k= qi, k+ max 0,氣，廣 q，k其中,為分配

11、在pr（ x k）上的耳的優(yōu)先模塊,a，為分配在氣上的t的優(yōu)先模塊。這樣，就 可J有效地實(shí)現(xiàn)模塊間的優(yōu)先級(jí)的規(guī)定。還可以利用試探法的合一算法,將提交的模塊合一成n個(gè)模塊簇，這樣搜索空間可降為n。1. 3試探法試探法3 4 與前兩種方法不同，它以次最優(yōu)解為目標(biāo)，其基本思想是先選擇具有最大通 信開(kāi)銷(xiāo)的一對(duì)模塊，若有一處理機(jī)能按一定的實(shí)時(shí)限制和存儲(chǔ)限制處理這對(duì)模塊則將它們 合一（形成模塊簇，以準(zhǔn)備進(jìn)入下一輪迭代）;否則選擇下一對(duì)具有最大通信量的模塊重復(fù) 上述過(guò)程，直至再無(wú)可合一的模塊對(duì)，迭代過(guò)程結(jié)束，將同一模塊簇中的模塊指派給同一處 理機(jī)。這種算法的特點(diǎn)是執(zhí)行開(kāi)銷(xiāo)小，其最壞情況下的時(shí)間復(fù)雜度為O（

12、m2logm）。由于把m 11期何炎祥等:對(duì)三種典型分布式任務(wù)配算法的分析3個(gè)模塊分配到n個(gè)處理機(jī)上有nm種分配方案，最優(yōu)解通常是很難獲得的但當(dāng)不要求最優(yōu)分 配或不可能實(shí)現(xiàn)最優(yōu)分配時(shí)，這種方法還是很有吸引力的，這種方法的不足之處在于：若合一過(guò)程結(jié)束后，模塊簇的數(shù)目仍大于處理機(jī)的數(shù)目（設(shè)為n+ k）,顯然應(yīng)把這k個(gè)多余的模塊簇分配給各處理機(jī)必要時(shí)，可能還得對(duì)模塊簇進(jìn)行分裂，但該算法并未考慮 這一點(diǎn)。它未考慮模塊互斥以及處理機(jī)性能可能不同等情況因此，難能滿(mǎn)足實(shí)際分配問(wèn)題的W要。該算法開(kāi)銷(xiāo)中的很大一部分用來(lái)尋找通信量最大的模塊對(duì)。Efe 3提出的試探法含兩個(gè)階段：合一和調(diào)整，基本思想是先對(duì)模塊進(jìn)行合

13、一，然后，若 發(fā)現(xiàn)處理機(jī)間負(fù)載不平衡，則改變相應(yīng)參數(shù)后重新進(jìn)行合一。它以模塊為結(jié)點(diǎn)，通信量為邊 將任務(wù)分配問(wèn)題表示成一個(gè)pro cess圖。Efe指出某些模塊可能僅能分配給某一或某幾個(gè)處理機(jī)這類(lèi)模塊稱(chēng)為附屬模塊，合一 過(guò)程此時(shí)改為按附屬模塊形成簇。然后，先把包含僅能分配給某個(gè)處理機(jī)的模塊的模塊簇分 配給該處理機(jī)，再分配包含其它附屬模塊的模塊簇最后分配不包括附屬模塊的模塊簇。每 次分配都以使系統(tǒng)負(fù)載最平衡為目標(biāo)如可用best-fi t方法。模塊分配完后，檢查負(fù)載是否 平衡，若平衡，則算法停止；否則進(jìn)入調(diào)整階段。在調(diào)整階段，先根據(jù)各處理機(jī)的負(fù)載狀況，標(biāo) 記各處理機(jī)為平衡、超載、輕載；將已分配給平衡

14、處理機(jī)的模塊從原process圖中去掉;照抄 分配給超載處理機(jī)的所有模塊；用一個(gè)結(jié)點(diǎn)代表分配給輕載處理機(jī)的模塊并用原來(lái)所有到該 結(jié)點(diǎn)相關(guān)模塊的邊的權(quán)之和作為到該結(jié)點(diǎn)的邊的權(quán)；然后，對(duì)每個(gè)超載處理機(jī)執(zhí)行下面的動(dòng) 作：尋找分配給超載處理機(jī)吼的模塊簇到分配給輕載處理機(jī)虬的模塊簇的邊，設(shè)這樣的邊 的個(gè)數(shù)為氣m，在每條這樣的邊的權(quán)上增加lLk- Lml/nk m，其中上為上的負(fù)載。對(duì)這個(gè)新 形成的process圖重新執(zhí)行合一過(guò)程。顯然這種方法通過(guò)把因某種分配方案引起的負(fù)載不平衡方面的開(kāi)銷(xiāo)轉(zhuǎn)移到通信開(kāi)銷(xiāo)上 并進(jìn)行重新合一來(lái)試圖得到更合理的分配方案 因此，它同時(shí)兼顧了減少通信量和均衡負(fù)載 這兩個(gè)因素。對(duì)這個(gè)

15、算法，還存在以下需改進(jìn)處：在合一階段考慮了對(duì)附屬模塊的處理方法，但在調(diào)整階段并未考慮附屬模塊的特殊 性;應(yīng)擴(kuò)充，以允許加入多種限制條件。2 一個(gè)改進(jìn)的試探算法2. 1算法輸入通信開(kāi)銷(xiāo)矩陣Cmxm，執(zhí)行開(kāi)銷(xiāo)矩陣Qmxn，模塊優(yōu)先矩陣P* 每個(gè)處理機(jī)的實(shí)時(shí)限制Rk和Sk。mxn,模塊互斥矩陣E,以及mx m2算法描述及簡(jiǎn)單分析 2. 2. 1 第一階段：for k= 1 to n do將必須指派給pk的模塊分配給pk，這可通過(guò)在矩陣P*中查找Pj,. n中僅有pk k= 0的模4小型微型計(jì)算機(jī)系統(tǒng)1997年塊得到(實(shí)際上，首先搜索P*,將此類(lèi)模塊形成鏈更合適，其復(fù)雜度為0( nm)。將此類(lèi)模塊 標(biāo)

16、記為附屬模塊。根據(jù)處理機(jī)的現(xiàn)有負(fù)載建堆或調(diào)整堆堆頂為負(fù)載最輕的處理機(jī)Pk。若堆不空，則選 Pk；否則第一階段結(jié)束。若所有模塊已分配，則第一階段結(jié)束；否則，若氣不帶有附屬模塊，則在未分配的模 塊中任選一個(gè)為t;否則，選一個(gè)附屬模塊為t。II尋找與tj有最大通信量的未分配的模塊tj(復(fù)雜度為0( m)。若tj的加入仍能滿(mǎn)足以下條件：a )實(shí)時(shí)限制R.和存儲(chǔ)限制S ;kkpj k= 0,即能分配到pk上；不與任何已分配給pk的模塊互斥。則將孔分配到Pk上，否則取下一個(gè)與R通信量最大的模塊為重復(fù)。由于第一階段可能多次執(zhí)行，因此，對(duì)C i, 1m恍排序可以提高動(dòng)態(tài)執(zhí)行的效率。此 階段的復(fù)雜度最壞為0(

17、m),但平均情況下為0(1)。若沒(méi)有tj能分配給pk，則將pk從堆中刪去；否則修改的負(fù)載，返到。不難得知，第一階段的最壞復(fù)雜度不超過(guò)0( m2),因?yàn)?，最多可能循環(huán)m次(這里m為 非附屬模塊的數(shù)目)。2. 2. 2 第二階段若第一階段結(jié)束時(shí)所有模塊已分配完則直接進(jìn)入第三階段否則,說(shuō)明剩余模塊由于模 塊互斥條件和優(yōu)先關(guān)系的限制,以及實(shí)時(shí)和存儲(chǔ)限制，不能分配給任一處理機(jī)。在此，逐個(gè)檢查 這些模塊，設(shè)當(dāng)前的一個(gè)為切并設(shè)耳的一個(gè)優(yōu)先模塊為町它已分配到Pk上則從Pk中取出 町而將與分配給Pk，并尋找可接收的處理機(jī)(這種試探法在實(shí)際情況中可能很有效)。注意，當(dāng)模塊互斥關(guān)系和優(yōu)先關(guān)系比較稀疏時(shí)不會(huì)出現(xiàn)這種情

18、況。這種情況的出現(xiàn)會(huì) 影響算法的效率。2. 2. 3 第三階段設(shè)處理機(jī)p i= 1, 2,，n)的負(fù)載為L(zhǎng)計(jì)算L=k= 1L , Lave= L /n。用q = L /L；v e表示處理機(jī)pk上的負(fù)載狀況。選擇一個(gè)適當(dāng)?shù)某?shù)d并定義:若1- dW qkW 1+ d,標(biāo)記pk為平衡；若qk 1+ d,標(biāo)記pk超載。去掉分配給平衡處理機(jī)的模塊 拷貝超載處理機(jī)上的模塊 用一個(gè)模塊代替輕載處理 機(jī)上的模塊，并用所有到其中原有模塊的邊的權(quán)之和代替到該新模塊的邊的權(quán)：去掉在超載 處理機(jī)上所有附屬模塊到輕載處理機(jī)上模塊的邊去掉超載處理機(jī)上與輕載處理機(jī)中某個(gè)模 塊互斥的模塊到該輕載處理機(jī)模塊的邊。按Efe的方法修改邊上的權(quán)，即在從超載處理機(jī)模塊tk到輕載處理機(jī)模塊、的邊的 權(quán)上加上lLk- Lml/nk m。從第一階段的開(kāi)始重新進(jìn)行分配，此時(shí)已不再包括平衡處理機(jī)及其上的模塊。若此 次重新分配未引起負(fù)載的任何改變則算法終止。此階段的最壞復(fù)雜度也不超過(guò)O( m2)。11期何炎祥等:對(duì)三種典型分布式任務(wù)配算法的分析5與Efe相比，本算法有如下特點(diǎn)：本算法引入了模塊間互斥的限制，以及模塊不能分配到某處理機(jī)的限制，因而更符合 實(shí)際；Efe算法是對(duì)模塊簇執(zhí)行best-fi t算法，而本算法總是把合一后的一對(duì)模塊分配到負(fù) 載最輕的處理機(jī)，本算法第一階段結(jié)束