负载均衡优先的改进优先级表调度算法*

葛维春， 叶 波

(1. 辽宁省电力公司 科技信通部， 沈阳 110006； 2. 东北电力大学 信息工程学院， 吉林 吉林 132012)

电气工程

负载均衡优先的改进优先级表调度算法*

葛维春1， 叶 波2

(1. 辽宁省电力公司 科技信通部， 沈阳 110006； 2. 东北电力大学 信息工程学院， 吉林 吉林 132012)

针对当前云计算环境下DAG任务调度时存在的负载失衡、任务调度效率不高的问题，提出了一种负载均衡优先的改进优先级表调度算法(LS-IPLB).算法将云计算集群中虚拟机的状态参数变化抽象成空间中的参数向量变化，给出实时衡量云计算集群的负载均衡性方法，并作为虚拟机选择权值的重要参数.同时以任务执行代价、任务的出度和任务间的通信代价作为参数计算任务优先级，并在任务调度时采用任务复制策略进一步优化调度过程.结果表明，LS-IPLB算法能有效缩短DAG任务图的完成时间，并实现了良好的负载均衡性.

云计算； DAG任务调度； 负载均衡； 执行代价； 出度； 通信代价； 任务优先级； 任务复制

当前云计算集群对于独立任务的调度已有成熟的理论与方法，并在实际中广泛应用.但是关于DAG任务的调度问题仍处于起步研究阶段，近年来已引起国内外研究者的广泛关注，已有多种关于DAG任务调度方法被提出，并且所采用的调度策略和解决问题的角度各有不同.其中，优先级表调度算法因其算法的高效性和易于实现而得到广泛应用[1-3].

文献[4]提出的HEFT算法和文献[5]提出的CPOP算法是当前公认的调度效率较高的算法.HEFT算法中任务优先级别由ranku(从任务节点到出口节点的关键路径长度)值确定，任务调度时将任务分配到具有最小执行时间的虚拟机上；而CPOP算法将ranku与rankd(从入口节点到任务的关键路径长度)的和作为权值来计算任务优先级.HEFT和CPOP算法分别以任务的向前和向后关键路径作为优先级计算权值，获得了较好的全局调度效果，提升了任务执行效率.单独以ranku或者rankd作为权值计算任务优先级容易陷入局部最优，并且这两种算法未采用任务复制策略，难以获得更短调度时间的机会.

文献[6]提出了关键任务优先调度算法，算法在每一步都赋予关键路径节点最高优先级，但该算法未对非关键路径上任务进行有效调度，一旦非关键任务调度失当，势必会影响算法调度性能；文献[7]提出了改进列表任务调度算法(HIPLTS)，赋予关键路径上任务最高优先级，但是优先级计算未考虑通信代价影响，也未考虑系统负载均衡性.

图1 LS-IPLB算法原理图

算法提出了云计算系统负载均衡性量度，以兼顾调度过程中系统的负载均衡性；在确定任务优先级时未单独采用ranku或者rankd作为参考量，而是重点考虑了任务的执行代价、任务间的通信代价对任务优先级的影响，使计算出的优先级能够较准确地反映出特定DAG任务图的内在关系；在处理器选择阶段，提出一种根据当前状态计算权值、选择虚拟机的策略；在任务分配过程中，运用前驱任务复制技术，达到减少任务通信代价、提高处理器利用率的目的.

1 系统负载均衡度定义

1.1 计算节点数学模型

对于云计算集群的虚拟机节点，其工作状态可用一个参数向量来表示，如具有k个状态参数的虚拟机，其参数向量可表示为a=(∂1，∂2，…，∂k)，k个状态参数构成k维的参数向量空间.当节点接收任务进行处理时，其各个参数值将会发生变化，此时参数变化值即反映了虚拟机当前工作状态的变化.假设云计算集群中虚拟机个数为M，任务调度时根据虚拟机各个参数的状态进行合理任务分配.假设各个参数在当前系统中进行调度时的权重分别为a1，a2，…，ak，令a1+a2+…+ak=1，则虚拟机状态参数集合为

0≤xi2≤a2，…，0≤xik≤ak}

(1)

该平均值G(X1，X2，…，Xk)是各虚拟机投影到参数向量空间中的重心位置，它是判断集群整体负载情况的重要参数.通过将服务器节点映射到参数向量空间，可以更直观地研究云计算集群的负载状况.如果节点聚集于重心的周围，则集群负载较为均衡；如果节点投影点在投影空间中的映射分散，则集群负载不均衡，负载均衡状况比较差.

1.2 负载均衡度定义

为评估集群的负载均衡状况，可用各虚拟机投影点与重心距离的标准差归一化值进行衡量，定义该值为集群负载均衡度，用LB表示，即

(2)

负载均衡度LB表示某时刻任务分配到虚拟机上执行时，系统负载均衡度的大小，因此，负载均衡度LB是实时衡量云计算集群负载均衡性的指标.显然，系统负载均衡度的取值范围为[0，1]，负载均衡度越小，表明当前系统的负载均衡状况越好.它将作为虚拟机选择权值参数，以兼顾任务调度时集群的负载均衡性.

2 DAG任务模型

为描述关联任务组，本文构建了关联任务的DAG图.任务由DAG图中的节点表示，执行的先后次序由DAG中的边表示.

G={V，E，W，C}表示一个具有4个元组的关联任务组，各元素表示如下：

3)W为一个N×M的矩阵，表示N个任务在M个虚拟机上的执行代价集合，元素w(vi，pm)表示任务vi在虚拟机pm上的执行代价，任务vi的平均执行代价定义为

(3)

4) 集合C表示任务之间的通信花费集合，当两个具有直接关联关系的任务被分配至同一资源执行时，任务间的通信代价为0.

为了方便描述任务调度问题，还要给出DAG任务图中的入口节点、出口节点、任务的前驱节点集合、任务的后继节点集合、开始执行时间及最早完成时间等变量的定义.

定义1 没有前驱节点的任务为入口节点，没有后继节点的任务为出口节点.如果DAG图中有不止一个入口节点，那么添加一个零计算代价的伪入口节点，并分别用边权值为0的边指向入口节点，出口节点同理.

定义2DAG任务图中，任务vi的直接前驱任务节点集合为vi的父节点集合，记作pred(vi)；任务节点vi的直接后继任务节点集合为vi的子节点集合，记作inhe(vi).

通常任务vi在虚拟机pm上的启动时间受到两个因素的制约，其表述如下：

1) 任务vi在虚拟机pm上的起始可用时间.虚拟机pm上的起始可用时间是指从任务vi分配到虚拟机pm上至要执行任务vi时的时间间隔，用usa(pm)表示.若刚完成被分配任务即执行，则有

usa(pm)=ct(vt，pm)

(4)

式中，ct(vt，pm)为任务vt在pm上的完成时间.

2) 任务vi的直接前驱任务执行结果传递到虚拟机pm的时间.任务vi开始执行的前提是虚拟机pm接收到其所有直接前驱任务的执行结果，由此可计算任务vi在虚拟机pm上开始执行时间，用st(vi，pm)表示，即

C(ei，j))]

(5)

式中，C(ei，j)为执行结果传递到虚拟机的时间.任务vi在虚拟机pm上的完成时间ct(vi，pm)为任务vi在虚拟机pm上开始执行时间与执行时间之和，即

ct(vi，pm)=st(vi，pm)+w(vi，pm)

(6)

图2为一个关联任务组DAG图，该关联任务组有8个任务组成，v1为入口任务，v8为出口任务，任务间的依赖关系由图中有向边给出；任务之间的通信花费由图中数字所示；虚线框中的任务为同级任务，即它们是前级任务的直接后继任务.

图2 关联任务DAG图

3 LS-IPLB算法分析

3.1 任务优先级计算

本文提出的LS-IPLB算法流程图如图3所示.为任务设置优先级能够实现任务调度时的公平和效率，本文修改了表调度算法HEFT的优先级别计算公式，增加了任务的出度值和任务的出口通信值两个关键因子.任务节点vi的出度是指该任务的直接后继任务的数目，用H(vi)表示，分析认为任务出度值越大，对后续任务执行的影响越大，该任务的优先执行能够提高后续任务的并发执行程度.任务节点vi的出口通信值是指该任务所有出口边通信时间之和，用B(vi)表示，即

(7)

图3 LS-IPLB算法流程图

分析认为任务的出口通信值B(vi)越大，对后继任务的影响越大，它的优先执行能够有效减少后继任务等待时间，从而提前后继任务的开始执行时间.综合考虑以上两个重要影响因子，提出了新的优先级计算方法，即

PR(vi)=(αH(vi)+βB(vi))SL(vi)

(8)

(9)

3.2 虚拟机选择

本文采用全职分配原则，以获得全局最小任务完成时间为目标，以负载均衡度与当前时刻任务vi向后关键路径的执行时间为权值，为任务选择权值较小的虚拟机进行调度.任务vi的虚拟机选择权值swi，m定义为

INHE_KEY(vi))LB)

(10)

式中：LB为负载均衡度；INHE_KEY(vi)=HE_KEY(vj)+C(ei，j)+w(vi，pm)；HE_KEY(vi)为vi的关键后继任务集合.

3.3 任务调度及任务复制

调度开始时，深度遍历DAG任务图，得到任务图的关键路径，任务调度时赋予同级任务中关键路径上任务最高优先级，对于非关键任务按照PR(vi)值进行降序排列，对于PR(vi)值相同的任务，则选择后继任务数多的优先调度.

从任务队列中选择优先级最高的，将其调度到swi，m最大的虚拟机上，此时，若存在多个相同swi，m值虚拟机，则选择负载均衡度值较小的虚拟机进行任务调度.

为进一步缩短任务执行时间，提高处理器运行效率，算法采用任务复制技术对调度过程进行优化.任务vi的直接前驱任务按优先级排列的集合为

pred(vi)={vi，1，vi，2，…，vi，n}

(11)

若任务vi，1满足

C(ei，i，y))

则称vi，1为任务vi的关键前驱节任务.将当前任务vi的关键前驱节任务vi，1复制到目标虚拟机pm上，可以提前任务的最早执行时间.定义约束条件为任务vi，1复制到虚拟机pm上的执行时间小于任务vi，1分配到虚拟机px上的执行时间与执行结果传递到虚拟机pm上的时间C(ei，1，i)之和，即

ct(vi，1，pm)

(12)

若约束条件式(12)不满足，则考察任务vi的直接前驱任务层中优先级次大的前驱任务vi，2，可将其调度到任务vi所在虚拟机的空闲时间槽fts(vi，pm)上执行，缩短DAG任务图的完成时间.定义约束条件为任务vi，2在虚拟机pm上的执行代价w(vi，2，pm)小于空闲时间槽fts(vi，pm)的长度，即

fts(vi，pm)>w(vi，2，pm)

(13)

若任务vi有两个以上的前驱任务，则继续考察任务vi，3，此时空闲时间槽更新为

f=fts(vi，pm)-w(vi，2，pm)

(14)

其约束条件为

fts(vi，pm)-w(vi，2，pm)≥w(vi，3，pm)

(15)

继续考察剩下的前驱任务，直到不再满足终止复制约束条件为止，此时虚拟机空闲时间槽小于任何一个待调度前驱任务的执行时间，终止复制约束条件为

(2≤r≤n)

(16)

4 仿真实验结果与分析

为评价LS-IPLB算法的性能，本文在CloudSimToolkit环境中进行模拟实验，通过改写DatacenterBroker类中的bindCloudletToVm方法，添加本文的LS-IPLB调度算法，并且使用Ant工具对平台进行重新编译，将LS-IPLB调度算法加入到模拟平台的任务调度单元中进行实验.在相同的环境配置下，实验选取与本文算法在各方面性能具有可比性的经典表调度算法HEFT、文献[7]改进优先级调度算法(HIPLTS)、文献[9]基于任务复制的调度算法(HNDP)进行比较.实验考查算法的3个影响因素：负载均衡度、DAG任务图中任务个数N及不同任务类型对调度算法的影响，因此设置了2组对比试验，分别测试4种算法的负载均衡性以及不同通信计算比的任务调度长度.

本仿真实验在戴尔Xeon E5-2609 v3服务器上创建了40个虚拟机作为计算节点，用于50～450个独立任务的调度.虚拟机VM到主机的映射分配由Cloudsim自带的Time-Shared算法实现，虚拟机的属性如表1所示，任务的属性表如表2所示.

表1 虚拟机属性

表2 任务属性

实验1 负载均衡性测试

(17)

显然，系统方差值越小，系统负载均衡性越好.根据式(17)与式(2)得出的实验结果分别如图4、5所示.

图4 期望处理时间方差

图5 负载均衡度

从图4中可以看出，随着任务数的增大，HIPLTS算法、HNDP算法和HEFT算法都出现了较为明显的负载失衡，而本文LS-IPLB算法引入负载均衡度后，算法呈现出良好的负载均衡性，δ值小于其他3种算法；从图5可以看出，其实验结果与图4的结果一致，LS-IPLB算法的负载均衡LB值从开始就小于其余3个算法，且随着任务数的增大，LB值趋于稳定.实验结果表明，LS-IPLB算法具有很好的负载均衡特性，并且适用于当前较大规模云计算集群的任务调度.

实验2 不同类型任务对算法的影响测试

衡量一个任务调度算法的基本评判标准是DAG任务图中全部任务的完成时间，本文采用文献[3]中的调度长度比率作为对调度策略性能的评价指标，其定义为

(18)

式中：max(ct(vk，pm))为DAG任务图的最多完成时间；CPCC为关键路径上的任务计算代价之和.显然，SLR≥1，且SLR越小，说明当前调度策略下DAG任务图完成时间越短，算法性能越好.

实验设置10个性能相异的虚拟机，测试30个不同的DAG任务图.定义DAG任务图中全部任务节点通信代价总和与全部任务节点计算代价总和之比为通信计算比，即

(19)

显然，CER能够反映DAG任务是计算密集型任务还是通信密集型任务.

试验分别设置CER=0.5和CER=10来模拟计算密集型任务与通信密集型任务，图6、7为通过多次重复实验得出的调度长度比率的平均结果.

图7 CER=10时算法调度长度比率

从图6可以看出，随着任务数增加，LS-IPLB算法和HIPLTS算法优于其他2个算法，这是由于CER=0.5时，DAG任务属于计算密集型任务，任务间的通信代价占比较低，冗余复制并不能明显减少任务间的通信代价.但本文改进的任务优先级计算和虚拟机选择策略能更有效地把任务分配到合适的虚拟机上.本文算法在虚拟机选择时加入了负载均衡度参数，使系统中的虚拟机始终处于较好的负载均衡状况，虚拟机计算资源得到了更充分的利用，随着任务数量的增加，优势逐渐显现.

从图7可以看出，当CER=10时，DAG图中任务属于通信密集型任务，LS-IPLB算法和HNDP算法优于其他两种算法，利用冗余复制机制能有效减少任务间通信代价.本文算法在调度时赋予同一级上关键路径任务为最高优先级，并优先复制关键前驱任务，使得算法取得了明显的调度性能.

5 结 论

本文提出了负载均衡优先的改进优先级表调度算法(LS-IPLB)，在改进表调度算法任务调度策略的同时，加入任务负载均衡度理论，得到了较理想的任务调度结果.实验表明，该算法实现了良好的负载均衡特性，尤其适用于较大规模云计算集群的任务调度.算法是在虚拟机之间全互联情况下提出的，没有考虑更复杂的非全互联环境，本文算法的DAG任务与实际关联任务有差别，今后可考虑更为复杂的接近实际云任务的DAG模型，设计更合理的调度算法.

[1]林伟伟，齐德昱.云计算资源调度研究综述 [J].计算机科学，2012，39(10)：1-6.

(LIN Wei-wei，QI De-yu.Survey of resource in cloud computing [J].Computer Science，2012，39(10)：1-6.)

[2]郭力争，赵曙光，姜长远.云计算环境下基于关联量的数据部署与任务调度 [J].计算机工程与科学，2013，35(8)：1-7.

(GUO Li-zheng，ZHAO Shu-guang，JIANG Chang-yuan.Data placement and task scheduling based on associated amount in cloud computing [J].Computer Engineering and Science，2013，35(8)：1-7.)

[3]张晓磊.云计算独立任务及关联任务调度算法研究 [D].重庆：重庆大学，2014.

(ZHANG Xiao-lei.Study on scheduling slgorithm of the independent and associated for cloud computing [D].Chongqing：Chongqing University，2014.)

[4]Topcuoglu H，Hariri S，Wu M Y.Performance-effective and low-complexity task scheduling for heterogeneous computing [J].IEEE Transactions on Parallel and Distributed Systems，2002，13(3)：260-274.

[5]Buyya R，Yeo C S，Venugopal S，et al.Cloud computing and emerging IT platforms：vision，hype and reality for delivering computing as the 5th utility [J].Future Generation Computer Systems，2009，25(6)：599-616.

[6]Janeĉek T J.A high performance，low complexity algorithm for compile-time task scheduling in heterogeneous systems [J].Parallel Computing，2015，31(7)：653-670.

[7]李静梅，王雪，吴艳霞.一种改进的优先级列表任务调度算法 [J].计算机科学，2014，41(5)：20-23.

(LI Jing-mei，WANG Xue，WU Yan-xia.Improved priority task scheduling algorithm [J].Computer Science，2014，41(5)：20-23.)

[8]王鹏，黄焱，李坤，等.云计算系统相空间分析模型及仿真研究 [J].计算机研究与发展，2013，36(2)：286-296.

(WANG Peng，HUANG Yan，LI Kun，et al.Load ba-lancing degree first algorithm on phase space for cloud computing cluster [J].Journal of Computer Research and Development，2013，36(2)：286-296.)

[9]孟宪福，刘伟伟.基于选择性复制前驱任务的DAG调度算法 [J].计算机辅助设计与图形学学报，2010，22(6)：1056-1062.

(MENG Xian-fu，LIU Wei-wei.A DAG scheduling algorithm based on selected duplication of precedent tasks [J].Journal of Computer-Aided Design and Computer Graphics，2010，22(6)：1056-1062.)

[10]宫华，张彪，许可.并行机生产与成批配送协调调度问题的近似策略 [J].沈阳工业大学学报，2015，37(3)：324-328.

(GONG Hua，ZHANG Biao，XU Ke.Approximation strategy for coordinated Scheduling problem in production and batch delivery of parallel machines [J].Journal of Shenyang University of Technology，2015，37(3)：324-328.)

(责任编辑：景 勇 英文审校：尹淑英)

List scheduling algorithm of improved priority with considering load balance

GE Wei-chun1, YE Bo2

(1. Science and Technology Communication Department, Liaoning Province Electric Power Company, Shenyang 110006, China; 2. College of Information Engineering, Northeast Dianli University, Jilin 132012, China)

Aiming at such problems as the load imbalance and low efficiency of DAG task scheduling in the current cloud computing environment, a list scheduling algorithm of improved priority with considering load balance (LS-IPLB) was proposed. In the algorithm, the state parameter change of virtual machine in the cloud computing cluster was abstracted into the parameter vector variation in the space, and the real-time measurement method for the load balance of cloud computing cluster was given, which was taken as an important parameter to select the weight of virtual machine. At the same time, the task priority was calculated through taking the task execution cost, task output value and communication cost between the tasks as the parameters. In addition, the task duplication strategy was used in the task scheduling to further optimize the scheduling process. The results show that the LS-IPLB algorithm can effectively shorten the completion time of DAG task graph, and can achieve good load balance.

cloud computing; DAG task scheduling; load balance; execution cost; output value; communication cost; task priority; task duplication

2017-03-28.

国家电网公司电力云计算服务试点平台建设项目(0711-140TL21112001).

葛维春(1961-)，男，辽宁沈阳人，教授级高级工程师，博士，主要从事电力系统分析计算及科技管理等方面的研究.

10.7688/j.issn.1000-1646.2017.03.01

TP 391.9

A

1000-1646(2017)03-0241-07

*本文已于2017-05-08 20∶25在中国知网优先数字出版. 网络出版地址： http：∥www.cnki.net/kcms/detail/21.1189.T.20170508.2025.016.html