云计算环境下基于马氏距离的任务调度策略研究

李 慧，雷丽晖

(陕西师范大学 计算机科学学院，陕西 西安 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所示。总体上能源感知任务调度算法的执行效率优于其他两种。

用户对某一项云计算任务的满意度由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