云計算環境下基于馬氏距離的任務調度策略研究

李 慧，雷麗暉

(陜西師范大學 計算機科學學院，陜西 西安 710119)

云計算環境下基于馬氏距離的任務調度策略研究

李 慧，雷麗暉

(陜西師范大學 計算機科學學院，陜西 西安 710119)

針對現有的云計算環境下的任務調度策略缺乏考慮用戶任務偏好從而導致虛擬機資源利用不充分、用戶對服務質量滿意度不高等問題，提出了云計算環境下基于馬氏距離的任務調度策略。該策略利用任務偏好指數與資源性能評分兩個概念；任務調度器依據任務偏好指數與資源性能評分之間的馬氏距離，為任務選擇馬氏距離最小的虛擬機資源進行映射。仿真實驗結果表明，該策略是有效的，滿足了根據任務的偏好差異分配不同特性的虛擬機資源的需求，使得不同偏好的用戶同時擁有高質量的服務。

云計算；任務調度；馬氏距離；CloudSim

0 引 言

云計算環境下用戶任務調度策略的目標之一在于保證用戶所用服務的質量,提高用戶服務的滿意度，同時盡可能提高云計算環境下資源的利用率[1]。大量事實表明，用戶任務調度策略會直接影響到用戶任務的執行效率及云計算環境中的資源的利用率。因此,文中提出一種基于馬氏距離的任務調度策略。該策略首先根據用戶任務的基本信息計算得到用戶任務的偏好指數；接著根據虛擬機資源性能情況計算得到資源性能評分；最后計算用戶任務偏好指數與資源性能評分之間的馬氏距離，為任務選擇距離最小的虛擬機資源進行映射，從而有效地建立用戶任務和虛擬機資源之間的合理映射關系，完成任務調度。通過在云計算仿真平臺CloudSim上仿真模擬該調度策略，驗證了其有效性，同時有效地提高了任務執行效率和用戶對服務質量的滿意度。

1 相關研究

目前已有較多的云計算環境下的用戶任務調度策略，主要包括：啟發式智能調度策略[2]、基于信任模型的調度策略[3]、基于反饋機制的調度策略[4]、基于服務商利潤的調度策略[5]以及基于QoS任務分類的調度策略[6]。

(1)啟發式智能調度策略。

啟發式智能調度策略主要是一些基于啟發式算法的策略，算法包括蟻群算法、遺傳算法、粒子群算法。

(2)基于信任模型的調度策略。

這種策略在云計算環境中加入信任的描述，有效建立任務與資源間的信任映射關系，進而保證了用戶任務的服務質量。

(3)基于反饋機制的調度策略。

該類策略主要采用負反饋機制來使虛擬機資源達到動態負載均衡。

(4)基于服務商利潤的調度策略。

該類策略是以提高提供云計算環境的服務商的利潤為目標，在滿足用戶基本需求的同時，降低資源和能量的消耗。

(5)基于QoS任務分類的調度策略。該類調度策略重在滿足不同用戶的不同任務需求。

顯然，現有的云計算環境下的任務調度策略缺乏對用戶任務偏好的考慮。

因此，文中提出了一個兼顧用戶任務偏好的云計算環境下的用戶任務調度策略，通過計算任務的偏好指數以及資源的性能評分之間的馬氏距離，合理有效地建立兩者之間的映射關系，有效地提高了任務的執行效率及用戶對服務的滿意度。

2 基于馬氏距離的任務調度算法

定義1(云計算環境下任務模型)：云計算環境下的任務集。

C={c0,c1,…,cn-1}

(1)

ci={cID,cLenth,cFileSize,cOutputSize,cPref}

(2)

ciPref={cComPref,cStoPref,cBwPref}

(3)

其中，ci為第i(0≤i≤n-1)個元任務(元任務之間無依賴關系)；cID為任務ID號；cLenth為任務計算量；cFileSize為任務存儲數據量；cOutputSize為任務輸出數據量；cPref為任務偏好指數；cComPref為計算偏好值；cStoPref為存儲偏好值；cBwPref為帶寬偏好值。

定義2(云計算環境下資源模型)：云計算資源環境模型。

VM={vm0,vm1,…,vmm-1}

(4)

vmi={vmID,vmUser,vmMipss,vmStoreSize,vmBw,vmScore}

(5)

vmiScore={vmComScore,vmStoScore,vmBwScore}

(6)

其中，vmi為第i(0≤i≤m-1)個虛擬機資源；vmID為虛擬機ID號；vmUser為虛擬機當前擁有者；vmMipss為虛擬機的指令執行數；vmStoreSize為虛擬機存儲容量；vmBw為虛擬機帶寬大小；vmScore為虛擬機資源評分；vmComScore為虛擬機資源計算評分；vmStoScore為虛擬機資源存儲評分；vmBwScore為虛擬機資源帶寬評分。

云計算環境中的資源以虛擬機資源形式呈現給用戶，虛擬機資源VM中包含所有虛擬機。文中假設所有任務ci為元任務，視為互不依賴任務進行調度[7]。在同一個虛擬機vmi上執行的任務ci遵循FCFS原則，且為非搶占式。用戶任務偏好指數cPref對應著虛擬機資源性能評分vmScore。

定義3(用戶任務偏好指數)。

對于任務偏好指數cPref的計算，首先根據式(7)～(9)計算平均偏好值；

(7)

(8)

(9)

其中，avgComValue為計算平均偏好值；avgStoValue為存儲平均偏好值；avgBwValue為帶寬平均偏好值。

再根據式(10)～(12)計算出當前任務ci的各項偏好指數；

(10)

(11)

(12)

當前任務ci的任務計算量ciLength、任務存儲數據量ciFileSize、任務輸出數據量ciOutputSize三項數值中，高于其對應的avgComValue、avgStoValue、avgBwValue的任務平均偏好值越多，即其偏離程度正向越高，說明任務ci對該項偏好越明顯；反之如果與任務平均偏好值的偏差越小或為負值，說明對某一項偏好的要求較低或小于平均值。

定義4(虛擬機資源性能評分)。

需要通過該虛擬機資源的信息計算資源的評分值。利用式(13)～(15)計算出虛擬機vmi的性能評分。當一項性能評分正值越大時，說明該虛擬機資源性能高于平均水平越顯著；反之，一項性能評分負值越大時，說明該虛擬機資源性能低于平均水平顯著。

(13)

(14)

(15)

定義5(用戶滿意度)。

dij為第i個云任務的偏好指數ciPref與第j個虛擬機的性能評分vmjScore的馬氏距離。

dij=

(i∈[1,n];j∈[1,m])

(16)

其中，S為ciPref與vmjScore的協方差矩陣。

(17)

Sks=[(ciPref(k)-avg(k))*(ciPref(s)-avg(s))+(vmjScore(k)-avg(k)) *vmjScore(s)-avg(s))]/ 2(k∈[1,3],s∈[1,3])

(18)

avg(1)=(ciComPref+vmjComScore)/2

(19)

avg(2)=(ciStoPref+vmjStoScore)/2

(20)

avg(3)=(ciBwPref+vmjBwScore)/2

(21)

建立任務與虛擬機資源的映射關系時，用戶滿意度uSat定義為：

uSatij=dij

(22)

3 仿真實驗及結果分析

2009年4月，云計算仿真平臺CloudSim由澳大利亞墨爾本大學網格實驗室和Gridbus項目聯合推出[8-10]。

文中使用的仿真實驗的硬件環境為：IntelCore3.10GHzCPU，2GB內存，2G硬盤；軟件環境為：Windows7操作系統，Eclipse4.4.1和Java1.7語言開發工具，及CloudSim3.0仿真器[11]。

3.1 仿真算法

文中提出的基于馬氏距離的任務調度算法的偽代碼如下：

public void EnergyAwaredbindCloudletToVm(){

//計算云任務的數量

int cloudletNum=cloudletList.size();

//計算虛擬機的數量

int vmNum=vmList.size();

//計算用戶任務平均偏好值

AvgComValue

for(int i=0;i

cloudletList.get(i).cComPref=getComValue(cloudletList.get(i));

cloudletList.get(i).cStoPref=getStoValue(cloudletList.get(i));

cloudletList.get(i).cBwPref=getBwValue (cloudletList.get(i));

}

//計算虛擬機資源的性能評分vmComScore、vmStoScore、vmBwScore

for(int i=0;i

vmList.get(i).vmComScore=getvmComScore(vmList.get(i));

vmList.get(i).vmStoScore=getvmStoScore(vmList.get(i));

vmList.get(i).vmBwScore=getvmBwScore(vmList.get(i));

}

//計算用戶任務偏好指數與虛擬機資源性能評分之間的馬氏距離

for(int i=0;i

for(int j=0;j

dist[i][j]=MaDist

(cloudletList.get(i),vmList.get(j));

cloudletList.get(i).

MaDistList.

add(dist[i][j]);

}

}

//將每個任務與資源的馬氏距離進行升序排序,并記錄最優映射

for(int i=0;i

minIndex[i]=getMinIndex

(cloudletList.get(i).MaDisList)；

Collections.sort(cloudletList.get(i).MaDisList,

newVmComComparator());

minDist[i]=cloudletList.get(i).

MaDisList.get(0);

}

//按照最優映射關系進行資源匹配

for(int i=0;i

cloudletList.get(i).setVmId

(minIndex[i]));

}

3.2 實驗結果與分析

與提出的調度算法進行比較的調度算法包括帶負載均衡的貪心策略算法和FCFS任務調度算法。對實驗結果進行對比分析，任務完成時間對比顯示如圖1所示?？傮w上能源感知任務調度算法的執行效率優于其他兩種。

用戶對某一項云計算任務的滿意度由uSat決定。uSat越小，表明任務調度算法的用戶滿意度越高，越能夠讓虛擬機的資源得到合理利用，并更好地滿足用戶需求。用戶滿意度的對比結果如圖2所示。能源感知任務調度算法的用戶滿意度總體上要遠遠優于其他兩種算法，其中除任務5、9以外，其他任務的用戶滿意度值均小于1。

圖1 任務完成時間對比

圖2 用戶滿意度對比

4 結束語

針對現有云計算環境下任務調度策略在考慮用戶任務偏好、虛擬機資源性能以及用戶滿意度的不足，基于馬氏距離提出了云計算下的任務調度策略，并在云計算仿真平臺CloudSim上進行了仿真[12-14]。通過與FCFS調度算法以及帶有負載均衡的貪心策略算法進行比較，實驗結果表明：該策略是有效、可行的，可以根據任務的偏好差異分配不同特性的虛擬機資源，確保不同偏好的用戶有更好的服務質量，提高了用戶滿意度。

[1] 劉 鵬．云計算[M]．北京:電子工業出版社，2007:2-3．

[2] Zhang Z H，Zhang X J．A load balancing mechanism based on ant colony and complex network theory in open cloud computing federation[C]//Proc. of 2nd international conference on industrial mechatronics and automation.[s.l.]:[s.n.],2010:240-243．

[3] Zheng Z N，Wang R．An approach for cloud resource scheduling based on parallel genetic algorithm[C]//Proc. of 3rd international conference on computer research and development.[s.l.]:[s.n.],2011：444-447．

[4] 朱宗斌，杜中軍．基于改進GA的云計算任務調度算法[J]．計算機工程與應用，2013,49(5)：77-80．

[5] 熊聰聰，馮 龍，陳麗仙,等．云計算中基于遺傳算法的任務調度算法研究[J]．華中科技大學學報:自然科學版，2012(S1)：1-4．

[6] Xue S J，Wu W．Scheduling workflow in cloud computing ba-sed on hybrid particle swarm algorithm[J]．Telkomnika Indonesian Journal of Electrical Engineering,2012,10(7)：1560-1566．

[7] 李依桐，林 燕．基于混合粒子群算法的云計算任務調度研究[J]．計算技術與自動化，2014，33(1)：73-77．

[8] 劉 永，王新華，邢長明,等．云計算環境下基于蟻群優化算法的資源調度策略[J]．計算機技術與發展，2011，21(9)：19-23．

[9] 趙 莉.基于改進人工免疫算法的云計算任務調度[J].激光雜志,2014,35(11):113-116.

[10] 蘇淑霞.粒子群算法在云計算任務調度中的應用[J].南京師大學報:自然科學版,2014,37(4):145-149.

[11] 陳 超.基于預測模型的動態多目標優化算法研究[D].長沙:湖南大學,2012.

[12] Calheiros R N,Ranjan R,Beloglazov A,et al.CloudSim:a toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms[J].Software Practice and Experience,2011,41(1):23-50.

[13] 王金海,戴少為,史永強.一種基于能量感知的云計算環境下虛擬機部署策略[J].新疆職業大學學報,2014,22(1):73-76.

[14] 易星宇,翁楚良.面向云計算中心效能優化的負載平衡方法[J].計算機科學與探索,2012,6(4):327-332.

Research on Task Scheduling Strategy in Cloud Computing Based on Mahalanobis Distance

LI Hui，LEI Li-hui

(School of Computer Science,Shaanxi Normal University,Xi’an 710119,China)

According to the fact that current scheduling algorithms in cloud computing platform neglect the user task preferences so that virtual resources in the cloud cannot be fully used and users cannot get high quality of services,a new task scheduling strategy based on Mahalanobis Distance is proposed.It makes use of two items like task preferences index and virtual resource performance index,to calculate the Mahalanobis Distance.According to the Mahalanobis Distance,the task scheduler allocates the user tasks to the suitable virtual machines.Simulation results show that this strategy is effective,which not only allocates user tasks to virtual machines with different characteristics according to the different user task preferences,but also ensures that different users can get high quality of services at the same time.

cloud computing;task scheduling;Mahalanobis Distance;CloudSim

2015-02-16

2015-07-16

時間：2017-01-04

國家自然科學基金資助項目(61003061)

李 慧(1989-)，女，碩士研究生，研究方向為網絡計算；雷麗暉，博士，副教授，研究方向為網絡計算、可靠性軟件理論及技術。

http://www.cnki.net/kcms/detail/61.1450.TP.20170104.1017.004.html

TP31

A

1673-629X(2017)01-0053-04

10.3969/j.issn.1673-629X.2017.01.012