陳彬玫, 徐 虹

(成都信息工程學(xué)院計算機學(xué)院,四川成都610225)

0 引言

進(jìn)程遷移是實現(xiàn)負(fù)載平衡的基礎(chǔ),包括遷移機制和遷移策略兩個部分。遷移機制是指進(jìn)程遷移的具體實現(xiàn),遷移策略是前期的準(zhǔn)備,包括負(fù)載向量管理和分布式調(diào)度兩部分內(nèi)容。傳統(tǒng)的進(jìn)程遷移研究大多集中于進(jìn)程的遷移機制,對進(jìn)程的遷移策略關(guān)注較少[1-4]。進(jìn)程遷移是系統(tǒng)動態(tài)適應(yīng)負(fù)載變化的最佳機制[1],但實現(xiàn)這個過程是有代價的[5-6]。例如,進(jìn)程遷移開銷會加重已經(jīng)過載的服務(wù)器;遷移后的進(jìn)程可能離開本身具有親和性的緩存和資源;負(fù)載的瞬時變化和負(fù)載延遲擴散會造成進(jìn)程遷移顛簸[6-7];短期進(jìn)程[5]或者churn服務(wù)器不應(yīng)作為遷移的選擇目標(biāo)等。因而需要實現(xiàn)高效、穩(wěn)定的遷移策略。

進(jìn)程遷移策略的研究主要集中在負(fù)載平衡的信息、調(diào)度、位置、選擇、接受和決定等策略[1,6-8]。其中,信息策略是其他策略的依據(jù),是整個進(jìn)程遷移策略的核心和基礎(chǔ)。關(guān)于信息策略,已有成果主要關(guān)注于負(fù)載向量(Load Vector)的表示、收集、傳播等,很少重視信息策略中負(fù)載向量的可靠性問題,特別是對瞬時變化和采集噪聲的考量。例如,文獻(xiàn)[10]在負(fù)載收集過程中使用自適應(yīng)雙閾值策略,有效降低了系統(tǒng)通信開銷。文獻(xiàn)[6]在遷移權(quán)衡中使用負(fù)載閾值作為進(jìn)程是否需要遷移的指標(biāo),文獻(xiàn)[9]提出閾值和閾長結(jié)合的動態(tài)反饋調(diào)整自適應(yīng)算法,但閾值策略只能對遷移決定作出有限平衡。文獻(xiàn)[5]使用進(jìn)程剩余生命時間作為負(fù)載向量表示,由于不能反映進(jìn)程的外部資源依賴,使用范圍有限。

負(fù)載信息的可靠性和準(zhǔn)確性會嚴(yán)重影響進(jìn)程遷移系統(tǒng)的適應(yīng)性和穩(wěn)定性[1,6-8]。已有系統(tǒng)實現(xiàn)在使用負(fù)載向量時大多采用延遲響應(yīng)和加權(quán)負(fù)載的經(jīng)驗性折中策略,例如文獻(xiàn)[5]使用1分鐘時間內(nèi)的平均負(fù)載,文獻(xiàn)[8]使用當(dāng)前時刻系統(tǒng)負(fù)載和前一時刻的系統(tǒng)負(fù)載的加權(quán)求和,文獻(xiàn)[11]使用連續(xù)兩次的負(fù)載值確定負(fù)載是否突變。而這些策略都不能很好的跟蹤系統(tǒng)的負(fù)載變化情況,特別是負(fù)載瞬時值在較大的峰谷之間顛簸的情況。因此,針對進(jìn)程遷移策略中的負(fù)載計算問題,提出了一種自適應(yīng)的動態(tài)負(fù)載平衡(Adaptive Dynamic Load Balancing,ADLB)算法,通過等比計算緩存負(fù)載分量的歷史實現(xiàn)均值平滑,通過平均偏差實現(xiàn)峰谷平滑,通過源負(fù)載曲線和目標(biāo)負(fù)載曲線的平滑確定遷移關(guān)系,為遷移決策提供更準(zhǔn)確的依據(jù),從而實現(xiàn)運行時自適應(yīng)智能調(diào)度。

1 進(jìn)程遷移策略

區(qū)分機制和策略是一種重要的設(shè)計模式,遷移機制和遷移策略的關(guān)系如圖1所示。

進(jìn)程遷移策略是遷移機制的前提和依據(jù),包括負(fù)載向量管理和分布式調(diào)度兩部分內(nèi)容[1]。負(fù)載向量管理通過對整個系統(tǒng)中資源進(jìn)行抽象,篩選系統(tǒng)需要的負(fù)載向量,通過一定機制收集、計算和分發(fā),實現(xiàn)全系統(tǒng)共享,為系統(tǒng)管理以及策略制定提供服務(wù)。分布式調(diào)度策略根據(jù)負(fù)載向量管理模塊通告的負(fù)載信息考慮什么時候(when)遷移哪個進(jìn)程(which)到哪臺機器(where)。所以調(diào)度過程是通過兩次協(xié)調(diào)實現(xiàn):首先是負(fù)載向量共享確定when、which和where的遷移關(guān)系,繼而通過發(fā)起者和接收者的協(xié)商實施遷移。遷移機制是進(jìn)程遷移的具體實現(xiàn),接受調(diào)度策略的指令,實施遷移。遷移過程依賴于具體的操作系統(tǒng)環(huán)境,需要應(yīng)用程序和內(nèi)核的配合、修改內(nèi)核數(shù)據(jù)結(jié)構(gòu)和增加系統(tǒng)調(diào)用,實現(xiàn)難度較大。

從圖1可以看出,在以進(jìn)程遷移為目標(biāo)的系統(tǒng)平臺上,負(fù)載向量的表示、收集和計算是進(jìn)程遷移的起點,進(jìn)程遷移策略是進(jìn)程遷移的指令發(fā)出者,決定整個系統(tǒng)的適應(yīng)性和穩(wěn)定性[1,6-8]。適應(yīng)性關(guān)注遷移策略對系統(tǒng)的影響。由于進(jìn)程遷移本身就是對系統(tǒng)負(fù)載變化的適應(yīng),調(diào)度算法需要適應(yīng)不同主機負(fù)載、網(wǎng)絡(luò)負(fù)載和權(quán)重參數(shù)的變化。適應(yīng)性本質(zhì)上是要求遷移策略對負(fù)載變化感知的靈敏性。穩(wěn)定性關(guān)注系統(tǒng)是否具備預(yù)測下一步行動效果的能力。在分布式系統(tǒng)中,不穩(wěn)定是絕對的,穩(wěn)定是相對的。但是,不穩(wěn)定性必須限制在盡量小的程度內(nèi)或者穩(wěn)定程度盡可能達(dá)到折中。例如進(jìn)程遷移的顛簸反而對

系統(tǒng)的穩(wěn)定性帶來負(fù)面影響;在負(fù)載很高的系統(tǒng)中最好的辦法是無為而治。穩(wěn)定性本質(zhì)上是要求遷移策略對負(fù)載變化感知的遲鈍性。

總之,進(jìn)程遷移策略關(guān)注進(jìn)程遷移動作的實施是否有效[7]。最佳的解決方案是很難實現(xiàn)的,常用的策略是用一個子集來逼近整個搜索空間或利用啟發(fā)式達(dá)到次優(yōu)的解決方案。

圖1 遷移機制和遷移策略關(guān)系圖

2 ADLB算法與實現(xiàn)

2.1 基本思想

獲得可靠負(fù)載的有效方法是對系統(tǒng)一定時段的歷史負(fù)載和當(dāng)前負(fù)載進(jìn)行加權(quán)計算。根據(jù)負(fù)載信息產(chǎn)生特點,時間歷史越久的負(fù)載越?jīng)]有參考意義,所占權(quán)重應(yīng)該較少。當(dāng)前負(fù)載是需要均衡的負(fù)載,要重點考慮,同時也要考慮瞬時的負(fù)載噪聲。在這個負(fù)載的蹺板上,歷史負(fù)載影響太重,系統(tǒng)響應(yīng)遲鈍,當(dāng)前負(fù)載影響太重,系統(tǒng)反應(yīng)靈敏,但決策可能盲目。因此,ADLB算法通過兩個步驟獲得更為可靠的負(fù)載計算結(jié)果。

第一個步驟獲得當(dāng)前時刻以前的負(fù)載狀況的加權(quán)均值。算法并不在內(nèi)存中保留進(jìn)程運行以來的所有歷史負(fù)載記錄,而是通過等比級數(shù)作為權(quán)重對系統(tǒng)運行以來所有負(fù)載值按照時間逆序加權(quán)求和作為當(dāng)前負(fù)載值。加權(quán)采用等比級數(shù)方法是為了有效利用2進(jìn)制數(shù)的優(yōu)點。例如,歷史負(fù)載的權(quán)重為:當(dāng)前負(fù)載的權(quán)重為:其中m∈N,1≤n≤2m,且可以根據(jù)系統(tǒng)實現(xiàn)需求進(jìn)行調(diào)整。由此,用 Ai表示時間線上各點采集到的當(dāng)前負(fù)載信息,Ti表示時間線上各點加權(quán)求和后的平滑負(fù)載值,m取3,n取1,則各個時間點的負(fù)載計算過程形成如下序列:由序列可見,加權(quán)計算存在3個關(guān)鍵:(1)負(fù)載值的影響按照時間線前進(jìn)的反方向等比下降;(2)當(dāng)m值確定時,n值越小,當(dāng)前負(fù)載值的權(quán)重越小,歷史的權(quán)重越大,反之相反;(3)m、n可以根據(jù)需要采用不同的值。

第二個步驟仍然采用如上加權(quán)均值的方法,但計算的對象是當(dāng)前采集到的瞬時負(fù)載值偏離第一步驟獲得的加權(quán)均值的程度。這需要引入負(fù)載序列的標(biāo)準(zhǔn)差和平均偏差。在工程應(yīng)用上,都認(rèn)為平均偏差是對標(biāo)準(zhǔn)差的一種好的逼近,并且避免了標(biāo)準(zhǔn)差的開方操作。例如,RTCP協(xié)議中抖動值的計算和TCP協(xié)議中超時重傳機制的實現(xiàn)都使用了平均偏差。文獻(xiàn)[12]也給出平均偏差(d)和標(biāo)準(zhǔn)偏差(σ)存在如下關(guān)系:σ≥d≥0,因而可以使用平均偏差代替標(biāo)準(zhǔn)偏差。標(biāo)準(zhǔn)差和平均偏差的計算公式分別為:

上述兩個步驟獲得的負(fù)載值之和即是決策依據(jù)負(fù)載。兩個步驟都是必要的,僅通過第一個步驟獲得負(fù)載值作為遷移依據(jù),無法準(zhǔn)確跟蹤負(fù)載當(dāng)前的瞬時變化,失去負(fù)載感知的靈敏性。在第一步驟的均值中強調(diào) n取較小的值以最大可能考慮歷史,最后的負(fù)載值使用第一步驟的均值和第二步驟的標(biāo)準(zhǔn)差之和,可以削弱瞬時高負(fù)載,補償瞬時低負(fù)載,有效保證負(fù)載統(tǒng)計的穩(wěn)定性。

2.2 算法實現(xiàn)

2.2.1 歷史負(fù)載平滑

取g為影響歷史負(fù)載權(quán)重的因子,A為經(jīng)過平滑的負(fù)載值,M是實際測到的負(fù)載值。計算公式為:

為了編碼實現(xiàn)方便,g采用2的乘方,這樣計算時只需要移位操作而不需要乘除運算。從(1)式可以看出,歷史負(fù)載值隨著時間的流逝,通過等比的關(guān)系逐漸減小,對負(fù)載平衡時總負(fù)載的計算的影響也逐漸減小。

2.2.2 峰谷負(fù)載平滑

上一步操作中,A的效果相當(dāng)于平均值,M-A就是負(fù)載瞬時值的峰谷范圍。計算公式為:

然后引入峰谷負(fù)載平滑因子h和平均偏差D,如果要對負(fù)載變化敏感,可以設(shè)置較大的h,將會使得負(fù)載值快速上升。計算公式為:

2.2.3 負(fù)載計算

綜合式(1)和(3),得出的負(fù)載值計算公式如下:

2.2.4 遷移權(quán)衡

系統(tǒng)中遷移源節(jié)點和遷移目標(biāo)節(jié)點之間定義了一對遷移關(guān)系。進(jìn)入遷移臨界窗口的節(jié)點,在遷移窗口內(nèi)變化幅度(絕對值)之和最大的節(jié)點作為一對潛在遷移關(guān)系。為了平滑遷移關(guān)系,源節(jié)點取當(dāng)前負(fù)載值和平滑負(fù)載值的最小值,目標(biāo)節(jié)點取當(dāng)前負(fù)載值和平滑負(fù)載值的最大值。計算公式為:

雖然負(fù)載值已經(jīng)經(jīng)過平滑,但還可以引入遷移臨界窗口規(guī)定系統(tǒng)必須遷移之前處于高負(fù)載的最長時間和系統(tǒng)可以接受遷移進(jìn)程之前處于低負(fù)載的最長時間。當(dāng)然,遷移權(quán)衡要結(jié)合其他策略,例如,節(jié)點和進(jìn)程的生命時間作為權(quán)重是必須考慮的,系統(tǒng)的遷移臨界點可以使用閾值和閾長結(jié)合策略[9]等。

2.3 平滑證明

設(shè)相鄰兩次負(fù)載為:

兩次負(fù)載的比值為:

隨著因子g、h的增大,兩次負(fù)載的比值接近1。

兩次負(fù)載的差值為:

隨著因子g、h的增大,兩次負(fù)載的差值接近0。

綜上,隨著 g、h的增大,負(fù)載曲線趨于直線。

2.4 算法偽代碼描述

(1)float load=0;//表示平滑后的負(fù)載均值

(2)floatmdev=0;//表示平滑后的負(fù)載峰谷

(3)接受新得到的負(fù)載測量值m

(4)If(采樣值m有誤) then

(5)m=1;/*異常處理*/

(6)Endif

(7)If(不是第一個負(fù)載采樣) then

(8)m-=load;

(9)If(m＜0) then

(10)load+=(m ＞＞1);//放大

(11)m=-m;/*m取絕對值*/

(12)Else

(13)load+=(m ＞＞3);//縮小

(14)Endif

(15)m＞＞=2;

(16)mdev-=(mdev＞＞2);

(17)mdev+=m;

(18)Else/*第一個采樣*/

(19)load=m;/*設(shè)置初值*/

(20)mdev=0;

(21)Endif

根據(jù)上述代碼,load與mdev之和即為平滑后的整體負(fù)載。

3 系統(tǒng)模型及性能分析

3.1 系統(tǒng)軟件模塊棧

系統(tǒng)基于linux同構(gòu)集群平臺,采用從下到上分層的棧結(jié)構(gòu)組織進(jìn)程遷移的主要功能模塊,在節(jié)點之間存在3條主要消息通信分別對應(yīng)棧結(jié)構(gòu)的3個主要層次。各個模塊的主要功能如圖2所示。

負(fù)載管理模塊區(qū)分負(fù)載向量的內(nèi)容、權(quán)重和粒度。根據(jù)任務(wù)的性質(zhì),負(fù)載向量的內(nèi)容為3種類型:CPU密集型、內(nèi)存密集型和I/O密集型,I/O類應(yīng)用又分為磁盤I/O和網(wǎng)絡(luò)I/O。磁盤I/O通過分布式文件系統(tǒng)實現(xiàn),包括:文件共享、文件復(fù)制、文件遷移等,采用的負(fù)載分量包括磁盤利用率和磁盤空間大小,文件描述符打開的對象區(qū)分網(wǎng)絡(luò)(NFS)還是磁盤(RAID)等。網(wǎng)絡(luò)I/O以軟中斷為主要指標(biāo),包括消息請求和數(shù)據(jù)傳輸,通過注冊數(shù)據(jù)端口和服務(wù)端口區(qū)分,采用的負(fù)載分量包括網(wǎng)絡(luò)流量、網(wǎng)絡(luò)帶寬和軟中斷頻率等。管理員可以根據(jù)應(yīng)用需求設(shè)定各個應(yīng)用的權(quán)重,也可以通過系統(tǒng)統(tǒng)計負(fù)載歷史感知應(yīng)用主要依賴的資源,還可以預(yù)測進(jìn)程和節(jié)點的剩余生命時間,自適應(yīng)的調(diào)整權(quán)重分配。另外,針對前述負(fù)載分量,系統(tǒng)分別統(tǒng)計節(jié)點和進(jìn)程兩個粒度的負(fù)載信息。

圖2 系統(tǒng)軟件模塊棧

表1 典型負(fù)載變化測試數(shù)據(jù)

負(fù)載向量收集和傳播的方式主要有周期性和事件觸發(fā)兩種,事件包括:進(jìn)程創(chuàng)建、終止、遷移。在設(shè)計的實現(xiàn)方案中,負(fù)載向量傳播內(nèi)容認(rèn)為是固定的數(shù)據(jù)結(jié)構(gòu),傳播策略采用周期加事件觸發(fā)的方式,周期時間較長。為了既能及時在系統(tǒng)的各個節(jié)點之間傳遞信息,又平衡收集開銷,引入負(fù)載更改閾值[10],當(dāng)負(fù)載的變化超過該值時,觸發(fā)負(fù)載推送到各個節(jié)點。當(dāng)負(fù)載的變化不超過該值時,信任已有負(fù)載值,不收集負(fù)載。系統(tǒng)在遷移權(quán)衡時使用兩個主要的閾值,遷移臨界點和遷移臨界窗口。遷移臨界點采用閾值和閾長[9]表示系統(tǒng)需要轉(zhuǎn)移負(fù)載的臨界范圍。遷移臨界窗口則表示系統(tǒng)必須遷移之前處于高負(fù)載的最長時間和系統(tǒng)可以接受遷移進(jìn)程之前處于低負(fù)載的最長時間。另外,系統(tǒng)對進(jìn)程適合遷移以及節(jié)點適合遷出和遷進(jìn)進(jìn)程的最小運行時間也給出了閾值。

遷移協(xié)商采用兩階段的方式,需要遷移雙方對遷移的開始和完成分別作出確認(rèn)。另外啟動策略采用對稱啟動方式,并限制一對節(jié)點運行時只能有一對遷移關(guān)系。為了避免進(jìn)程遷移泛濫和掠奪[8]的群聚效應(yīng)(Herd Effect),在遷移開始之前把確定的遷移關(guān)系傳播給系統(tǒng)內(nèi)其他節(jié)點。

遷移實施主要基于linux環(huán)境下checkpoint-restart實現(xiàn)。

3.2 測試方案

根據(jù)系統(tǒng)實際運行過程中的負(fù)載變化,考慮4種典型的負(fù)載變化趨勢:(1)負(fù)載持續(xù)遞增:模擬了適應(yīng)訪問人數(shù)逐漸增多的互聯(lián)網(wǎng)應(yīng)用;(2)負(fù)載持續(xù)遞減:模擬適應(yīng)訪問人數(shù)逐漸減少的互聯(lián)網(wǎng)應(yīng)用;(3)負(fù)載以類似正弦的方式波動變化:模擬典型的周期運行daemon進(jìn)程負(fù)載變化;(4)負(fù)載隨機變化:模擬系統(tǒng)負(fù)載隨機變化的情況。

分別在上述4種情況下對系統(tǒng)負(fù)載平滑效果進(jìn)行測試,統(tǒng)計實際值和平滑值的情況。測試數(shù)據(jù)如表1所示,上述4種情況分別對應(yīng)表中1、2、3、4項。圖3～6分別直觀的顯示4組數(shù)據(jù)中負(fù)載值的平滑情況。由4種測試結(jié)果可以看出,算法有效的跟蹤了負(fù)載變化,并實現(xiàn)了負(fù)載平滑。進(jìn)程遷移是有開銷的,因此應(yīng)當(dāng)采用盡量不遷移的原則。例如,只有負(fù)載持續(xù)遞增的主機,在遷移關(guān)系的選擇時才會被選中,偶然一次的高負(fù)載并不會引起其上的進(jìn)程遷出。相應(yīng)的,只有負(fù)載持續(xù)遞減的主機,才能成為其他過載主機的遷入目標(biāo)。

圖3 負(fù)載遞增實驗數(shù)據(jù)

圖4 負(fù)載遞減實驗數(shù)據(jù)

圖5 負(fù)載正弦波動實驗數(shù)據(jù)

圖6 負(fù)載隨機變化實驗數(shù)據(jù)

4 總結(jié)

針對進(jìn)程遷移中負(fù)載信息計算的可靠性問題,提出ADLB算法,有效的解決了負(fù)載變化抖動問題。系統(tǒng)在運行時采集并計算平滑負(fù)載,自適應(yīng)系統(tǒng)負(fù)載的變化,并結(jié)合其他權(quán)重因素,動態(tài)遷移進(jìn)程。

負(fù)載向量的管理不是進(jìn)程遷移所特有,也不專用于遷移調(diào)度,幾乎所有實現(xiàn)動態(tài)負(fù)載平衡和任務(wù)調(diào)度的系統(tǒng)中都要涉及。負(fù)載向量的計算方法也可以用于其他計算環(huán)境,并可以根據(jù)不同目標(biāo),收集不同的負(fù)載分量。由于算法的通用性,對于其他平臺也有借鑒意義。

下一步工作是在目前工作的基礎(chǔ)之上研究多目標(biāo)(I/O、MEM、CPU)調(diào)度決策問題。

[1] Dejan S Milojici,Fred Douglis,Yves Paindaveine,et al.Process migration[J].ACM,2000,32(3):241-299.

[2] Balazs Gerofi,Hajime Fujita,Yutaka Ishikawa.An Efficient Process Live Migration Mechanism for Load Balanced Distributed Virtual Environments[C].Cluster 2010;IEEE International Conference on Cluster Computing,2010.

[3] Amirreza Zarrabi.A Generic Process Migration Algorithm[J].International Journal of Distributed and Parallel Systems(IJDPS),2012,5(3):29-37.

[4] Chandu D Vaidya,M B Chandak.Efficient Parallel Process Migration Algorithm Using Statistical Approach[C].Fourth International Conference on Computational Intelligence and Communication Networks,2012.

[5] 張永坤,金海,唐丹.一種基于進(jìn)程剩余運行時間總和的集群動態(tài)負(fù)載平衡算法[J].計算機工程與科學(xué),2005,27(5):63-65.

[6] 蔣江.異構(gòu)集群系統(tǒng)中基于進(jìn)程遷移機制的負(fù)載平衡算法的研究[D].長沙:國防科技大學(xué)研究生院,2002.

[7] 韓海軍.無中心集群下基于進(jìn)程遷移的負(fù)載平衡研究[D].沈陽:沈陽理工大學(xué),2007.

[8] 遲忠惠.基于進(jìn)程遷移的負(fù)載均衡算法的研究[D].青島:中國海洋大學(xué),2005.

[9] 周佳祥,鄭緯民,楊廣文.一種基于進(jìn)程遷移的自適應(yīng)雙閾值動態(tài)負(fù)載平衡系統(tǒng)[J].清華大學(xué)學(xué)報,2000,40(3):121-125.

[10] 胡金柱,徐松.分布式系統(tǒng)中一種負(fù)載平衡的動態(tài)反饋調(diào)整自適應(yīng)算法[J].小型微型計算機系統(tǒng),2003,24(8):1510-1515.

[11] 劉學(xué)偉.基于linux進(jìn)程遷移的設(shè)計與應(yīng)用實踐[D].成都:電子科技大學(xué),2008.

[12] 韓兆洲,楊林濤.極差、平均差和標(biāo)準(zhǔn)差之間測度關(guān)系研究[J].統(tǒng)計與信息論壇,2008,23(4):5-8.