一種加權(quán)歐氏距離負載均衡云任務調(diào)度算法

李 英，李 亞，劉廣亮

(南陽師范學院軟件學院，河南 南陽473061)

0 引言

云計算是在并行計算、分布式計算、集群計算、網(wǎng)格計算的基礎上發(fā)展起來的一種新興計算模式[1］，其基本思想是通過構(gòu)建數(shù)據(jù)中心，并采用成熟的虛擬化技術(shù)給用戶提供服務[2］。然而，不同的用戶對服務的需求是不同的，這就要求云計算平臺能夠通過任務調(diào)度為不同的用戶提供不同類型的服務，并保證用戶能夠獲得較好的服務質(zhì)量。

任務調(diào)度是云計算的關(guān)鍵技術(shù)之一。云任務調(diào)度的目的就是按照某種策略，將任務合理地分配到處理單元，以達到完成時間最短、成本最小以及提高系統(tǒng)利用率等目的[3］。

目前，云計算的任務調(diào)度算法具有較好的完成時間，但是并不符合云計算按需分配的特性，不能滿足用戶的需求。為此，本文提出了基于加權(quán)歐氏距離的負載平衡的云計算任務調(diào)度算法(簡稱EDW-LB算法)。EDW-LB算法針對云計算平臺中任務執(zhí)行時的動態(tài)特征，提出使用加權(quán)歐式距離來計算任務和資源的相關(guān)程度，使云計算任務能夠分配到合適的資源中，更好的滿足用戶對完成時間以及帶寬等多方面的需求。通過仿真和分析，表明該算法是可行的，并將本算法與目前比較常用的最優(yōu)時間調(diào)度算法進行對比，證明了在用戶滿意度和資源利用率方面取得了較好的效果。

1 問題描述

云環(huán)境中使用成熟的虛擬機技術(shù)，將物理層上的硬件映射到虛擬機層上，用戶的任務是通過虛擬機來執(zhí)行的[4］。任務調(diào)度相應于完成把n個任務通過某種策略合理的分配到虛擬機上執(zhí)行。

服務質(zhì)量(QoS)是衡量用戶使用云計算服務滿意度的標準。QoS衡量參數(shù)大致可以分為:完成時間、費用、帶寬和可靠性[4］。本文通過QoS參數(shù)對任務進行劃分。

1.1 任務描述

云任務集合用T={T1，T2，…，Tn}表示，每個任務的屬性集合表示為:

其中，IDi為云任務的編號;TYPEi為云任務的類型;Li為任務的總長度;INi為任務的輸入大小;OUTi為任務的輸出大小;Ei為用戶對任務的期待值;Ji為用戶對任務的滿意度。

任務的類型是根據(jù)QoS參數(shù)對進行劃分，每一類任務都對資源有著不同的需求指標。例如，計算型任務要求任務完成時間較短，而有些任務對帶寬有著較高的要求。文獻[2］提出給每類任務設定一般期待向量:

設第i類任務的一般期待向量為[2］:

其中，ei1、ei2、ei3、ei4、ei5分別表示對虛擬機的CPU數(shù)量、內(nèi)存大小、帶寬、任務執(zhí)行的費用以及虛擬機的故障率的期待值。

1.2 資源描述

虛擬機集合用V={V1，V2，…，Vm}表示，每個虛擬機的性能參數(shù)集合表示為:

其中，IDi為虛擬機的編號;PENi為虛擬機中包含的處理機或者CPU個數(shù);RAM為虛擬機的內(nèi)存;BWi為虛擬機的帶寬;FRi為虛擬機的故障率;PPUi為虛擬機單位時間內(nèi)的使用價格。

2 WED_GA_LB任務調(diào)度算法

2.1 相關(guān)計算

2.1.1 歸一化

將虛擬機的 5 個性能參數(shù)進行歸一化，令集合Xij={X1j，X2j，…，Xij}，i∈[1，m］，j∈[1，5］，Xij表示第i個虛擬機的第j個屬性(不包括虛擬機ID)，歸一化值為:

其中，GXij為第i個虛擬機的第j個性能參數(shù)歸一化后的值;curXij、minXij、maxXij分別為性能當前值、最小值和最大值。

2.1.2 歐氏距離的計算

任務的一般期待向量可以體現(xiàn)每種不同類別任務對資源性能的不同需求，因此，可以通過計算任務的一般期待向量與歸一化后的資源性能參數(shù)的歐氏距離，獲得最適合用戶需求的資源。假設某任務的一般期待向量為[e1，e2，e3，e4，e5］，某虛擬機性能參數(shù)歸一化后為[GXi1，GXi2，GXi3，GXi4，GXi5］，則該云任務與第i個虛擬機的歐式距離表示為[5-6］:

式(4)在計算任務與虛擬機的距離時，將各個性能所起的作用看成是一樣的，然而對于不同類別的任務對虛擬機性能的要求是不一樣的，所以這樣顯然是不合理的。文中提出加權(quán)的歐式距離，使計算距離時根據(jù)任務分類不同，虛擬機性能參數(shù)所起的作用也不同。加權(quán)歐式距離定義如下:

2.1.3 虛擬機負載計算

本文通過對虛擬機的性能參數(shù)歸一化后的值GXij來計算虛擬機的負載能力，具體操作為:首先，計算每個虛擬機的綜合性能指標為第i個虛擬機的第j個性能參數(shù)歸一化后的值。再將GSi/min(GSi)，得到虛擬機負載能力向量 gs= [gs1，gs2，gs3，gs4，gs5］。

定義1 虛擬機當前負載狀態(tài)[7］指在當前分配到該虛擬機上的所有任務的長度之和(長度單位為字節(jié))。第i個虛擬機的當前負載狀態(tài)表示為:

其中，m為虛擬機的個數(shù)。

通過以上描述可知:第i個虛擬機的當前負載狀態(tài)Loadi＞gsi×SLoad時，則該虛擬機負載較重。此時，需要將任務轉(zhuǎn)移到其他虛擬機上。文中采用的轉(zhuǎn)移方法是根據(jù)歐氏距離來轉(zhuǎn)移。

2.1.4 任務的滿意度J值

任務執(zhí)行完后，需要計算任務的滿意度J的值。任務i的滿意度可以表示為:

其中，m為當前分配到該節(jié)點的任務數(shù);Lk為第k個任務的長度(長度單位為字節(jié))。

由式(6)可得當前系統(tǒng)中總負載量SLoad為:

其中，Texpt為任務的期待執(zhí)行時間;Tact為任務實際的執(zhí)行時間;BWact為任務實際獲得的帶寬;BWexpt任務期待的帶寬;COSTexpt為任務期待的成本;COSTact為任務實際成本;Psucces為任務期待的可靠完成率;P為機器的故障率。

Ji=0說明該任務獲得的資源與期待的資源一致;Ji＞0表示該任務獲得的資源的性能高于期待的資源;Ji＜0表示該任務獲得的資源沒有達到期待值。

2.2 EDW-LB算法流程

根據(jù)前面的描述得知任務與資源之間的歐式距離越小，資源的性能也就越符合任務的期待值。這里需要考慮一個問題，同一類型的任務很有可能會被分配到同一個資源上，這樣就會造成某個或某些資源的負載過重，從而導致任務的完成時間過長。因此，本文提出的EDW-LB算法不僅考慮歐氏距離，而且還需要考慮資源的負載情況。該算法的偽代碼如下:

EDW-LB-bindCloudletToVM(cloudletList，vmList)

Foreach t in T

//計算任務t與各個資源加權(quán)歐式距離

eucliddis[］=ComputeWEuclidDis(vmList，t)

//根據(jù)加權(quán)歐式距離的值對資源進行排序(升序)，

并記錄資源的編號

vmOS[］=SortVmByED(eucliddis[］)

Foreach i in vmOS[］

//暫時第i個任務分配給歐式距離最小的資源

Allocate t to vmOS[i］

//考察編號為vmOS[i］資源的狀態(tài)

If(LoadvmOS[i］＞ gsvmOS[i］*SLoad)

//如果該資源負載較重，

根據(jù)歐式距離將任務分配給下一個資源

Allocate t to vmOS[i+1］

EndIF

EndFor

endFor

3 仿真實驗

使用云計算仿真平臺Cloudsim[8-10］來驗證提出的基于加權(quán)歐式距離的負載均衡任務調(diào)度算法的可行性與算法性能，并與順序任務調(diào)度算法、最優(yōu)完成時間調(diào)度算法進行了仿真比較。

3.1 實驗設置

[2］將所有任務分成兩類，第1類屬于計算型任務，對完成時間要求較高;第2類對帶寬要求較高。這兩類的任務的一般期待向量分別為[0.6，0.1，0.3］，[0.3，0.2，0.5］。

模擬的云環(huán)境包括4個虛擬機，虛擬機的性能參數(shù)如表1所示，10個任務(其中5個為第1類，5個為第2類)。仿真實驗主要考察的3個方面是用戶任務的完成時間，用戶滿意度和各個資源的負載情況。

表1 虛擬機列表

3.2 實驗結(jié)果及分析

圖1為任務完成時間對比圖，從圖1中可以看出順序調(diào)度、最優(yōu)完成時間以及EDW-LB這3種算法的對比情況，對于完成時間有較高要求的任務(任務1～5)而言，文中提出的EDW-LB算法的完成時間比順序調(diào)度算法以及最優(yōu)完成時間算法要短，而對于要求帶寬的任務(任務6～10)，EDW-LB算法的完成時間卻不是最短的，這是因為EDW-LB算法需要在滿足任務的帶寬需求的情況下，對任務進行調(diào)度。

圖2體現(xiàn)了3種算法的用戶滿意度對比情況，由圖2可以看出:EDW-LB調(diào)度算法的用戶滿意度比順序調(diào)度算法以及最優(yōu)完成時間算法優(yōu)越，也就是說EDW-LB調(diào)度算法可以使任務獲得符合其需求的資源。

圖1 任務完成時間對比圖

圖2 用戶滿意度對比圖

考察虛擬機的負載狀態(tài)，隨機生成長度在區(qū)間[10 000，50 000］的100個任務，虛擬機性能參數(shù)如表1所示，進行仿真實驗。

表2是采用3種不同算法時虛擬機的負載狀態(tài)，從表2中很容易看出采用順序調(diào)度算法各個虛擬機的負載情況，3號虛擬機上的任務長度(指令數(shù))大于1、2、4號虛擬機，然而實驗中所創(chuàng)建的虛擬機綜合性能1號＞2號＞3號＞4號。也就是說，1號虛擬機的性能最好，負載的指令數(shù)卻并不是很多。WED-LB調(diào)度算法能夠根據(jù)虛擬機的性能，控制虛擬機的負載情況。

表2 虛擬機負載情況 byte

4 結(jié)論

針對云環(huán)境下的任務調(diào)度提出了基于加權(quán)歐氏距離負載均衡的任務調(diào)度算法，該算法使用加權(quán)歐氏距離來計算用戶任務和虛擬機之間的相關(guān)程度，能夠滿足不同需求的用戶，在得到良好的用戶滿意度同時，通過資源的負載平衡策略提高資源的利用率，盡可能的縮短任務的完成時間。

參考文獻:

[1]吳煜祺，曾國蓀，曾媛.云計算環(huán)境下調(diào)度算法的趨勢分析[J］.微電子學與計算機，2012，29(9):103-108.

[2]楊麗，武小年，商可旻.一種基于聚類的云計算任務調(diào)度算法[J］.大眾科技，2012，14(5):37-39.

[3]趙春燕.云環(huán)境下作業(yè)調(diào)度算法研究與實現(xiàn)[D］.北京:北京交通大學，2009.

[4]朱健琛，徐潔，魯珂.一種類歐氏距離-負載平衡的云任務調(diào)度算法[J］.計算機仿真，2012，29(6):159-162.

[5]董旭，魏振軍.一種加權(quán)歐氏距離聚類方法[J］.信息工程大學學報，2005，6(1):23-25.

[6]劉瑞元.加權(quán)歐氏距離及其應用[J］.數(shù)理統(tǒng)計與管理，2002，21(5):17-19.

[7]韓云，于炯，張偉，等.基于負載均衡的任務調(diào)度改進算法[J］.微電子學與計算機，2010，27(8):201-204.

[8]丁陽，顏惠琴.基于改進粒子群算法的云計算任務調(diào)度策略[J］.無錫職業(yè)技術(shù)學院學報，2012，11(3):66-68.

[9]李坤.云環(huán)境下的任務調(diào)度算法研究與實現(xiàn)[D］.長春:吉林大學，2012.

[10]申麗君，劉麗，陸銳，等.基于改進免疫進化算法的云計算任務調(diào)度[J］.計算機工程，2012，38(9):208-210.