一种加权欧氏距离负载均衡云任务调度算法

2013-07-13刘广亮

河南科技大学学报(自然科学版) 2013年3期

李英，李亚，刘广亮

(南阳师范学院软件学院，河南南阳473061)

0 引言

云计算是在并行计算、分布式计算、集群计算、网格计算的基础上发展起来的一种新兴计算模式[1］，其基本思想是通过构建数据中心，并采用成熟的虚拟化技术给用户提供服务[2］。然而，不同的用户对服务的需求是不同的，这就要求云计算平台能够通过任务调度为不同的用户提供不同类型的服务，并保证用户能够获得较好的服务质量。

任务调度是云计算的关键技术之一。云任务调度的目的就是按照某种策略，将任务合理地分配到处理单元，以达到完成时间最短、成本最小以及提高系统利用率等目的[3］。

目前，云计算的任务调度算法具有较好的完成时间，但是并不符合云计算按需分配的特性，不能满足用户的需求。为此，本文提出了基于加权欧氏距离的负载平衡的云计算任务调度算法(简称EDW-LB算法)。EDW-LB算法针对云计算平台中任务执行时的动态特征，提出使用加权欧式距离来计算任务和资源的相关程度，使云计算任务能够分配到合适的资源中，更好的满足用户对完成时间以及带宽等多方面的需求。通过仿真和分析，表明该算法是可行的，并将本算法与目前比较常用的最优时间调度算法进行对比，证明了在用户满意度和资源利用率方面取得了较好的效果。

1 问题描述

云环境中使用成熟的虚拟机技术，将物理层上的硬件映射到虚拟机层上，用户的任务是通过虚拟机来执行的[4］。任务调度相应于完成把n个任务通过某种策略合理的分配到虚拟机上执行。

服务质量(QoS)是衡量用户使用云计算服务满意度的标准。QoS衡量参数大致可以分为:完成时间、费用、带宽和可靠性[4］。本文通过QoS参数对任务进行划分。

1.1 任务描述

云任务集合用T={T1，T2，…，Tn}表示，每个任务的属性集合表示为:

其中，IDi为云任务的编号;TYPEi为云任务的类型;Li为任务的总长度;INi为任务的输入大小;OUTi为任务的输出大小;Ei为用户对任务的期待值;Ji为用户对任务的满意度。

任务的类型是根据QoS参数对进行划分，每一类任务都对资源有着不同的需求指标。例如，计算型任务要求任务完成时间较短，而有些任务对带宽有着较高的要求。文献[2］提出给每类任务设定一般期待向量:

设第i类任务的一般期待向量为[2］:

其中，ei1、ei2、ei3、ei4、ei5分别表示对虚拟机的CPU数量、内存大小、带宽、任务执行的费用以及虚拟机的故障率的期待值。

1.2 资源描述

虚拟机集合用V={V1，V2，…，Vm}表示，每个虚拟机的性能参数集合表示为:

其中，IDi为虚拟机的编号;PENi为虚拟机中包含的处理机或者CPU个数;RAM为虚拟机的内存;BWi为虚拟机的带宽;FRi为虚拟机的故障率;PPUi为虚拟机单位时间内的使用价格。

2 WED_GA_LB任务调度算法

2.1 相关计算

2.1.1 归一化

将虚拟机的 5 个性能参数进行归一化，令集合Xij={X1j，X2j，…，Xij}，i∈[1，m］，j∈[1，5］，Xij表示第i个虚拟机的第j个属性(不包括虚拟机ID)，归一化值为:

其中，GXij为第i个虚拟机的第j个性能参数归一化后的值;curXij、minXij、maxXij分别为性能当前值、最小值和最大值。

2.1.2 欧氏距离的计算

任务的一般期待向量可以体现每种不同类别任务对资源性能的不同需求，因此，可以通过计算任务的一般期待向量与归一化后的资源性能参数的欧氏距离，获得最适合用户需求的资源。假设某任务的一般期待向量为[e1，e2，e3，e4，e5］，某虚拟机性能参数归一化后为[GXi1，GXi2，GXi3，GXi4，GXi5］，则该云任务与第i个虚拟机的欧式距离表示为[5-6］:

式(4)在计算任务与虚拟机的距离时，将各个性能所起的作用看成是一样的，然而对于不同类别的任务对虚拟机性能的要求是不一样的，所以这样显然是不合理的。文中提出加权的欧式距离，使计算距离时根据任务分类不同，虚拟机性能参数所起的作用也不同。加权欧式距离定义如下:

2.1.3 虚拟机负载计算

本文通过对虚拟机的性能参数归一化后的值GXij来计算虚拟机的负载能力，具体操作为:首先，计算每个虚拟机的综合性能指标为第i个虚拟机的第j个性能参数归一化后的值。再将GSi/min(GSi)，得到虚拟机负载能力向量 gs= [gs1，gs2，gs3，gs4，gs5］。

定义1 虚拟机当前负载状态[7］指在当前分配到该虚拟机上的所有任务的长度之和(长度单位为字节)。第i个虚拟机的当前负载状态表示为:

其中，m为虚拟机的个数。

通过以上描述可知:第i个虚拟机的当前负载状态Loadi＞gsi×SLoad时，则该虚拟机负载较重。此时，需要将任务转移到其他虚拟机上。文中采用的转移方法是根据欧氏距离来转移。

2.1.4 任务的满意度J值

任务执行完后，需要计算任务的满意度J的值。任务i的满意度可以表示为:

其中，m为当前分配到该节点的任务数;Lk为第k个任务的长度(长度单位为字节)。

由式(6)可得当前系统中总负载量SLoad为:

其中，Texpt为任务的期待执行时间;Tact为任务实际的执行时间;BWact为任务实际获得的带宽;BWexpt任务期待的带宽;COSTexpt为任务期待的成本;COSTact为任务实际成本;Psucces为任务期待的可靠完成率;P为机器的故障率。

Ji=0说明该任务获得的资源与期待的资源一致;Ji＞0表示该任务获得的资源的性能高于期待的资源;Ji＜0表示该任务获得的资源没有达到期待值。

2.2 EDW-LB算法流程

根据前面的描述得知任务与资源之间的欧式距离越小，资源的性能也就越符合任务的期待值。这里需要考虑一个问题，同一类型的任务很有可能会被分配到同一个资源上，这样就会造成某个或某些资源的负载过重，从而导致任务的完成时间过长。因此，本文提出的EDW-LB算法不仅考虑欧氏距离，而且还需要考虑资源的负载情况。该算法的伪代码如下:

EDW-LB-bindCloudletToVM(cloudletList，vmList)

Foreach t in T

//计算任务t与各个资源加权欧式距离

eucliddis[］=ComputeWEuclidDis(vmList，t)

//根据加权欧式距离的值对资源进行排序(升序)，

并记录资源的编号

vmOS[］=SortVmByED(eucliddis[］)

Foreach i in vmOS[］

//暂时第i个任务分配给欧式距离最小的资源

Allocate t to vmOS[i］

//考察编号为vmOS[i］资源的状态

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

//如果该资源负载较重，

根据欧式距离将任务分配给下一个资源

Allocate t to vmOS[i+1］

EndIF

EndFor

endFor

3 仿真实验

使用云计算仿真平台Cloudsim[8-10］来验证提出的基于加权欧式距离的负载均衡任务调度算法的可行性与算法性能，并与顺序任务调度算法、最优完成时间调度算法进行了仿真比较。

3.1 实验设置

[2］将所有任务分成两类，第1类属于计算型任务，对完成时间要求较高;第2类对带宽要求较高。这两类的任务的一般期待向量分别为[0.6，0.1，0.3］，[0.3，0.2，0.5］。

模拟的云环境包括4个虚拟机，虚拟机的性能参数如表1所示，10个任务(其中5个为第1类，5个为第2类)。仿真实验主要考察的3个方面是用户任务的完成时间，用户满意度和各个资源的负载情况。

表1 虚拟机列表

3.2 实验结果及分析

图1为任务完成时间对比图，从图1中可以看出顺序调度、最优完成时间以及EDW-LB这3种算法的对比情况，对于完成时间有较高要求的任务(任务1～5)而言，文中提出的EDW-LB算法的完成时间比顺序调度算法以及最优完成时间算法要短，而对于要求带宽的任务(任务6～10)，EDW-LB算法的完成时间却不是最短的，这是因为EDW-LB算法需要在满足任务的带宽需求的情况下，对任务进行调度。

图2体现了3种算法的用户满意度对比情况，由图2可以看出:EDW-LB调度算法的用户满意度比顺序调度算法以及最优完成时间算法优越，也就是说EDW-LB调度算法可以使任务获得符合其需求的资源。

图1 任务完成时间对比图

图2 用户满意度对比图

考察虚拟机的负载状态，随机生成长度在区间[10 000，50 000］的100个任务，虚拟机性能参数如表1所示，进行仿真实验。

表2是采用3种不同算法时虚拟机的负载状态，从表2中很容易看出采用顺序调度算法各个虚拟机的负载情况，3号虚拟机上的任务长度(指令数)大于1、2、4号虚拟机，然而实验中所创建的虚拟机综合性能1号＞2号＞3号＞4号。也就是说，1号虚拟机的性能最好，负载的指令数却并不是很多。WED-LB调度算法能够根据虚拟机的性能，控制虚拟机的负载情况。