李 慧，雷麗暉

(陜西師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院，陜西 西安 710119)

云計(jì)算環(huán)境下基于馬氏距離的任務(wù)調(diào)度策略研究

李 慧，雷麗暉

(陜西師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院，陜西 西安 710119)

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

云計(jì)算；任務(wù)調(diào)度；馬氏距離；CloudSim

0 引 言

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

1 相關(guān)研究

目前已有較多的云計(jì)算環(huán)境下的用戶任務(wù)調(diào)度策略，主要包括：?jiǎn)l(fā)式智能調(diào)度策略[2]、基于信任模型的調(diào)度策略[3]、基于反饋機(jī)制的調(diào)度策略[4]、基于服務(wù)商利潤(rùn)的調(diào)度策略[5]以及基于QoS任務(wù)分類的調(diào)度策略[6]。

(1)啟發(fā)式智能調(diào)度策略。

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

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

這種策略在云計(jì)算環(huán)境中加入信任的描述，有效建立任務(wù)與資源間的信任映射關(guān)系，進(jìn)而保證了用戶任務(wù)的服務(wù)質(zhì)量。

(3)基于反饋機(jī)制的調(diào)度策略。

該類策略主要采用負(fù)反饋機(jī)制來(lái)使虛擬機(jī)資源達(dá)到動(dòng)態(tài)負(fù)載均衡。

(4)基于服務(wù)商利潤(rùn)的調(diào)度策略。

該類策略是以提高提供云計(jì)算環(huán)境的服務(wù)商的利潤(rùn)為目標(biāo)，在滿足用戶基本需求的同時(shí)，降低資源和能量的消耗。

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

顯然，現(xiàn)有的云計(jì)算環(huán)境下的任務(wù)調(diào)度策略缺乏對(duì)用戶任務(wù)偏好的考慮。

因此，文中提出了一個(gè)兼顧用戶任務(wù)偏好的云計(jì)算環(huán)境下的用戶任務(wù)調(diào)度策略，通過(guò)計(jì)算任務(wù)的偏好指數(shù)以及資源的性能評(píng)分之間的馬氏距離，合理有效地建立兩者之間的映射關(guān)系，有效地提高了任務(wù)的執(zhí)行效率及用戶對(duì)服務(wù)的滿意度。

2 基于馬氏距離的任務(wù)調(diào)度算法

定義1(云計(jì)算環(huán)境下任務(wù)模型)：云計(jì)算環(huán)境下的任務(wù)集。

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

(1)

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

(2)

ciPref={cComPref,cStoPref,cBwPref}

(3)

其中，ci為第i(0≤i≤n-1)個(gè)元任務(wù)(元任務(wù)之間無(wú)依賴關(guān)系)；cID為任務(wù)ID號(hào)；cLenth為任務(wù)計(jì)算量；cFileSize為任務(wù)存儲(chǔ)數(shù)據(jù)量；cOutputSize為任務(wù)輸出數(shù)據(jù)量；cPref為任務(wù)偏好指數(shù)；cComPref為計(jì)算偏好值；cStoPref為存儲(chǔ)偏好值；cBwPref為帶寬偏好值。

定義2(云計(jì)算環(huán)境下資源模型)：云計(jì)算資源環(huán)境模型。

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)個(gè)虛擬機(jī)資源；vmID為虛擬機(jī)ID號(hào)；vmUser為虛擬機(jī)當(dāng)前擁有者；vmMipss為虛擬機(jī)的指令執(zhí)行數(shù)；vmStoreSize為虛擬機(jī)存儲(chǔ)容量；vmBw為虛擬機(jī)帶寬大??；vmScore為虛擬機(jī)資源評(píng)分；vmComScore為虛擬機(jī)資源計(jì)算評(píng)分；vmStoScore為虛擬機(jī)資源存儲(chǔ)評(píng)分；vmBwScore為虛擬機(jī)資源帶寬評(píng)分。

云計(jì)算環(huán)境中的資源以虛擬機(jī)資源形式呈現(xiàn)給用戶，虛擬機(jī)資源VM中包含所有虛擬機(jī)。文中假設(shè)所有任務(wù)ci為元任務(wù)，視為互不依賴任務(wù)進(jìn)行調(diào)度[7]。在同一個(gè)虛擬機(jī)vmi上執(zhí)行的任務(wù)ci遵循FCFS原則，且為非搶占式。用戶任務(wù)偏好指數(shù)cPref對(duì)應(yīng)著虛擬機(jī)資源性能評(píng)分vmScore。

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

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

(7)

(8)

(9)

其中，avgComValue為計(jì)算平均偏好值；avgStoValue為存儲(chǔ)平均偏好值；avgBwValue為帶寬平均偏好值。

再根據(jù)式(10)～(12)計(jì)算出當(dāng)前任務(wù)ci的各項(xiàng)偏好指數(shù)；

(10)

(11)

(12)

當(dāng)前任務(wù)ci的任務(wù)計(jì)算量ciLength、任務(wù)存儲(chǔ)數(shù)據(jù)量ciFileSize、任務(wù)輸出數(shù)據(jù)量ciOutputSize三項(xiàng)數(shù)值中，高于其對(duì)應(yīng)的avgComValue、avgStoValue、avgBwValue的任務(wù)平均偏好值越多，即其偏離程度正向越高，說(shuō)明任務(wù)ci對(duì)該項(xiàng)偏好越明顯；反之如果與任務(wù)平均偏好值的偏差越小或?yàn)樨?fù)值，說(shuō)明對(duì)某一項(xiàng)偏好的要求較低或小于平均值。

定義4(虛擬機(jī)資源性能評(píng)分)。

需要通過(guò)該虛擬機(jī)資源的信息計(jì)算資源的評(píng)分值。利用式(13)～(15)計(jì)算出虛擬機(jī)vmi的性能評(píng)分。當(dāng)一項(xiàng)性能評(píng)分正值越大時(shí)，說(shuō)明該虛擬機(jī)資源性能高于平均水平越顯著；反之，一項(xiàng)性能評(píng)分負(fù)值越大時(shí)，說(shuō)明該虛擬機(jī)資源性能低于平均水平顯著。

(13)

(14)

(15)

定義5(用戶滿意度)。

dij為第i個(gè)云任務(wù)的偏好指數(shù)ciPref與第j個(gè)虛擬機(jī)的性能評(píng)分vmjScore的馬氏距離。

dij=

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

(16)

其中，S為ciPref與vmjScore的協(xié)方差矩陣。

(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)

建立任務(wù)與虛擬機(jī)資源的映射關(guān)系時(shí)，用戶滿意度uSat定義為：

uSatij=dij

(22)

3 仿真實(shí)驗(yàn)及結(jié)果分析

2009年4月，云計(jì)算仿真平臺(tái)CloudSim由澳大利亞墨爾本大學(xué)網(wǎng)格實(shí)驗(yàn)室和Gridbus項(xiàng)目聯(lián)合推出[8-10]。

文中使用的仿真實(shí)驗(yàn)的硬件環(huán)境為：IntelCore3.10GHzCPU，2GB內(nèi)存，2G硬盤；軟件環(huán)境為：Windows7操作系統(tǒng)，Eclipse4.4.1和Java1.7語(yǔ)言開(kāi)發(fā)工具，及CloudSim3.0仿真器[11]。

3.1 仿真算法

文中提出的基于馬氏距離的任務(wù)調(diào)度算法的偽代碼如下：

public void EnergyAwaredbindCloudletToVm(){

//計(jì)算云任務(wù)的數(shù)量

int cloudletNum=cloudletList.size();

//計(jì)算虛擬機(jī)的數(shù)量

int vmNum=vmList.size();

//計(jì)算用戶任務(wù)平均偏好值

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));

}

//計(jì)算虛擬機(jī)資源的性能評(píng)分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));

}

//計(jì)算用戶任務(wù)偏好指數(shù)與虛擬機(jī)資源性能評(píng)分之間的馬氏距離

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]);

}

}

//將每個(gè)任務(wù)與資源的馬氏距離進(jìn)行升序排序,并記錄最優(yōu)映射

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);

}

//按照最優(yōu)映射關(guān)系進(jìn)行資源匹配

for(int i=0;i

cloudletList.get(i).setVmId

(minIndex[i]));

}

3.2 實(shí)驗(yàn)結(jié)果與分析

與提出的調(diào)度算法進(jìn)行比較的調(diào)度算法包括帶負(fù)載均衡的貪心策略算法和FCFS任務(wù)調(diào)度算法。對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行對(duì)比分析，任務(wù)完成時(shí)間對(duì)比顯示如圖1所示?？傮w上能源感知任務(wù)調(diào)度算法的執(zhí)行效率優(yōu)于其他兩種。

用戶對(duì)某一項(xiàng)云計(jì)算任務(wù)的滿意度由uSat決定。uSat越小，表明任務(wù)調(diào)度算法的用戶滿意度越高，越能夠讓虛擬機(jī)的資源得到合理利用，并更好地滿足用戶需求。用戶滿意度的對(duì)比結(jié)果如圖2所示。能源感知任務(wù)調(diào)度算法的用戶滿意度總體上要遠(yuǎn)遠(yuǎn)優(yōu)于其他兩種算法，其中除任務(wù)5、9以外，其他任務(wù)的用戶滿意度值均小于1。

圖1 任務(wù)完成時(shí)間對(duì)比

圖2 用戶滿意度對(duì)比

4 結(jié)束語(yǔ)

針對(duì)現(xiàn)有云計(jì)算環(huán)境下任務(wù)調(diào)度策略在考慮用戶任務(wù)偏好、虛擬機(jī)資源性能以及用戶滿意度的不足，基于馬氏距離提出了云計(jì)算下的任務(wù)調(diào)度策略，并在云計(jì)算仿真平臺(tái)CloudSim上進(jìn)行了仿真[12-14]。通過(guò)與FCFS調(diào)度算法以及帶有負(fù)載均衡的貪心策略算法進(jìn)行比較，實(shí)驗(yàn)結(jié)果表明：該策略是有效、可行的，可以根據(jù)任務(wù)的偏好差異分配不同特性的虛擬機(jī)資源，確保不同偏好的用戶有更好的服務(wù)質(zhì)量，提高了用戶滿意度。

[1] 劉 鵬．云計(jì)算[M]．北京:電子工業(yè)出版社，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] 朱宗斌，杜中軍．基于改進(jìn)GA的云計(jì)算任務(wù)調(diào)度算法[J]．計(jì)算機(jī)工程與應(yīng)用，2013,49(5)：77-80．

[5] 熊聰聰，馮 龍，陳麗仙,等．云計(jì)算中基于遺傳算法的任務(wù)調(diào)度算法研究[J]．華中科技大學(xué)學(xué)報(bào):自然科學(xué)版，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ì)算任務(wù)調(diào)度研究[J]．計(jì)算技術(shù)與自動(dòng)化，2014，33(1)：73-77．

[8] 劉 永，王新華，邢長(zhǎng)明,等．云計(jì)算環(huán)境下基于蟻群優(yōu)化算法的資源調(diào)度策略[J]．計(jì)算機(jī)技術(shù)與發(fā)展，2011，21(9)：19-23．

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

[10] 蘇淑霞.粒子群算法在云計(jì)算任務(wù)調(diào)度中的應(yīng)用[J].南京師大學(xué)報(bào):自然科學(xué)版,2014,37(4):145-149.

[11] 陳 超.基于預(yù)測(cè)模型的動(dòng)態(tài)多目標(biāo)優(yōu)化算法研究[D].長(zhǎng)沙:湖南大學(xué),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] 王金海,戴少為,史永強(qiáng).一種基于能量感知的云計(jì)算環(huán)境下虛擬機(jī)部署策略[J].新疆職業(yè)大學(xué)學(xué)報(bào),2014,22(1):73-76.

[14] 易星宇,翁楚良.面向云計(jì)算中心效能優(yōu)化的負(fù)載平衡方法[J].計(jì)算機(jī)科學(xué)與探索,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

時(shí)間：2017-01-04

國(guó)家自然科學(xué)基金資助項(xiàng)目(61003061)

李 慧(1989-)，女，碩士研究生，研究方向?yàn)榫W(wǎng)絡(luò)計(jì)算；雷麗暉，博士，副教授，研究方向?yàn)榫W(wǎng)絡(luò)計(jì)算、可靠性軟件理論及技術(shù)。

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