基于改进蚁群算法的云计算任务调度模型

魏 赟,陈元元

(上海理工大学光电信息与计算机工程学院,上海200093)

基于改进蚁群算法的云计算任务调度模型

魏 赟,陈元元

(上海理工大学光电信息与计算机工程学院,上海200093)

为解决云环境下的资源调度问题,提出一种能改善任务并行性与兼顾任务串行关系的调度模型,将用户提交的动态任务分割成具有制约关系的子任务,按运行次序放到具有不同优先级的调度队列中。针对同一调度队列中的子任务,采用基于最短任务延迟时间的改进蚁群算法(DSFACO)进行调度,在兼顾调度公平性与效率的前提下,最大化缩短任务延迟时间,从而提高用户满意度。实验结果表明,与任务调度增强蚁群算法相比,DSFACO算法在任务延迟时间、调度公平性及效率方面性能更好,能实现云计算环境下任务的最优调度。

云计算;蚁群算法;任务调度;公平性;任务延迟时间

1 概述

云计算采用服务的方式为用户提供动态虚拟化资源池[1],可以将用户提交的任务分配给分布式计算机资源池进行合理调度。在云环境下采用何种任务管理和调度算法,使任务延迟时间最短、用户满意度最高,将会直接影响云平台的效率与性能。云环境下的任务按照任务间有无输入输出关系分为2种:串行任务和并行任务。对于串行任务的调度,必须按照任务间的输入输出关系进行有序调度,文献[2]提出一种基于路径优先级的任务调度算法,文献[3]提出一种抢占式多有向无环图(DAG)工作流动态调度策略来保证调度的公平性,但是它们都没有对算法效率问题进行考虑。为提高云平台上任务调度的效率,越来越多的智能优化算法被应用到并行任务的调度,蚁群优化(Ant Colony Optimization, ACO)算法是一种动态的随机搜索算法[4],特别是在动态环境中,可以表现出高灵活性和健壮性,用于解决许多系统组合优化问题,因此,ACO算法非常适合于解决云环境下具有并行关系的任务调度问题。近年来很多学者用ACO算法来解决NP hard问题,如:旅行商问题,任务调度问题[5-6]和车辆路径问题等。文献[7]在云环境下提出基于Qos的作业调度算法,文献[8]提出云环境下的最优调度策略,文献[9]提出云环境下实现最优资源分配的方法,文献[10]在云环境下提出基于改进蚁群算法的调度算法,文献[11]在云环境下提出基于改进遗传算法的调度算法,文献[12]提出云环境下满足Multi-QoS需求的调度算法,但是上述算法均没有兼顾完成时间最短和用户公平性问题。

本文基于云计算平台和任务类型的特点,针对云环境下并行任务调度模型,将计算任务分割成小粒度子任务,对于有串行制约关系的任务,将其放入不同优先级别的调度队列中等待调度;对于可以并行运行的子任务,提出一种基于最短任务延迟时间的改进蚁群算法(Delay Time Shortest and Fairness Ant Colony Optimization,DSFACO)。

2 云环境下的并行调度模型

目前,云环境下的任务调度大多采用Google提出的MapReduce分布式计算编程模型,如文献[13]中在云环境下提出一种改进型MapReduce模型。将用户所提交的任务划分成多个Map任务和多个Reduce任务并行处理,大致分为2个阶段:Map阶段和Reduce阶段。在Map阶段,把用户所提交的任务分成M片,并将其分给多个计算节点并行执行,然后将处理后的文件输出。在Reduce阶段,对Map阶段输出的结果进一步汇总处理,输出最后的处理结果并提交给用户。因为云环境中任务具有大规模性和动态性等特点,任务和计算资源的数量是非常大的,系统每时每刻都要对海量用户所提交的任务进行处理,所以在MapReduce分布式计算编程模型下,如何对大量任务进行合理高效调度是决定云计算效率的重点和难点,不恰当的任务调度方法将会增加任务执行时间,降低整个云的性能和用户满意度。

2.1 模型定义

在云环境中,当用户所提交申请计算资源的任务非常紧急,而云计算资源管理平台不能尽快向其分配计算资源,逐渐将会导致云计算资源利用率降低、用户满意度下降,因此本文主要研究对用户所提交的紧急任务划分和调度。

任务集合和调度集合定义如下:用户提交的任务集合记为T={T1,T2,…,TM},调度等待队列集合记为Q={Q1,Q2,…,QN},对任务进行MapReduce处理后,子任务定义为tijk,其中,i为任务编号,1≤i≤M;j为调度队列编号,1≤j≤N;k为可并行子任务编号,k=1,2,…。对于调度次序为ti1的调度优先级高于ti2,对于同一个调度队列中的任务tij1,tij2,…,tijk可并行调度。

2.2 调度模型基本原理

调度步骤具体如下:

Step 1将用户提交的任务运用MapReduce模型划分为更小的子任务,将具有制约或并行关系的子任务放入具有不同优先级的调度队列中,如图1所示。

图1 调度次序划分

Step 2从优先级最高的调度队列开始调度,当队列中所有子任务调度完毕后,依次调度后续任务队列,以保证子任务之间的制约关系。对于同一队列中的子任务,按本文所设计的DSFACO算法选择调度对象。

Step 3任务的所有子任务全部调度完毕后,结束该任务并将结果返回给用户。

由于相同调度队列中的子任务相互独立,且云计算资源可采用相同的调度算法对每个队列进行调度,因此本文以任务延迟时间最短为目标,对ACO算法进行改进,主要研究如何对调度等待队列中的子任务进行高效调度,最大限度提高云平台效率及用户的满意度。

3 基于改进蚁群优化算法的子任务调度

标准蚁群优化算法是受生物进化的启发,对自然界真实蚁群进行模拟后所提出的一种仿生优化算法,具有并行性、鲁棒性和正反馈性等优点,但该算法的随机性很大,在解决大规模优化问题时很容易陷入局部最优,导致算法效率很低。因此,考虑到实际应用中的效率与公平问题对ACO算法进行如下改进:以任务延迟时间最短为目标建立数学函数来解决效率问题;将向计算资源提出请求的用户参数作为公平因子引入到ACO算法中来解决任务分配公平性问题,并对任务被选择概率进行改进。

3.1 改进蚁群算法的设计

为便于计算,重新对调度等待队列Qk中的子任务进行标记Qk={q1,q2,…,qm},云计算资源集合表示为A={a1,a2,…,an},任务qi的预开始处理时间和实际开始处理时间分别记为EDT(qi),ADT(qi),任务调度时间窗为st。

(1)目标函数建立

为实现调度队列中的子任务高效调度,使得任务延迟时间最短,建立以下目标函数:

(2)启发式因子设置

将任务处理时间与任务完成时间作为2个启发式因子。

(3)客户公平因子的引入

将向计算资源提出请求的用户参数引入到ACO算法中,用N(ci)表示用户ci的待处理任务数量;η3(qi)表示任务qi的公平因子;F(ci)表示任务qi所属用户ci的公平因子;β3表示启发函数η3(qi)相对重要性的期望启发式因子,β3越大,公平因子对任务被选中概率的影响越大。

其中,K1为一固定常数,用于调节客户公平因子的大小。

(4)任务启发式因子更新

当任务qi被选择安排计算资源后,该任务所属用户ci的任务启发式因子更新为:

(5)任务被选择的概率

在本次迭代中若任务qi所属用户已经被分配计算资源,则此用户ci其他任务的公平因子应该按比例降低,这样可以对其他用户的任务进行分配计算资源:

其中,x表示调度队列中任务的被调度次序;τix为表示信息素的参数;allowed表示目前尚未分配处理的任务集合中与计算资源类型匹配的所有任务。

(6)信息素更新

式(7)表示任务在本次调度中剩余的信息素,K2为信息素增强系数,式(8)表示每次qi更新信息素时的积累方式。

3.2 改进蚁群算法的实现步骤

改进蚁群算法的具体步骤如下:

Step 1变量初始化:对输入参数进行初始化,云计算资源集合A,调度等待队列Qk,最大迭代次数NI_MAX,信息启发式因子α,期望启发式因子β1,β2,信息素的挥发系数ρ,信息素的增强系数Q,时间窗的长度st。

Step 2单次迭代外层循环:次序x累加,当x＞s时,结束本层循环,表示已全部将所有计算资源的可用时间分配给各项任务,执行Step6;否则执行Step3。

Step 3单次迭代内层循环:计算资源aj→aj+1依次执行,每个计算资源依次处理满足条件的各类任务,当j＞l1+l2+…+ln时,执行Step2;否则执行Step4。

Step 4根据式(6)计算任务被选择的概率。

Step 5调度队列的修改:调度队列为n行、s列的矩阵,计算资源每次选择完毕后即对调度队列进行修改,然后执行Step3。

Step 6根据式(7)、式(8)进行信息素更新,更新后继续执行Step7。

Step 7迭代,终止条件:NI→NI+1,当NI＞NI_MAX,且任务完成时间连续60次无变化,跳出循环。

4 仿真实验结果与分析

为评价和分析本文DSFACO算法的性能,在云计算模拟平台CloudSim中,通过改写Datacenter-Broker类中的bindCloudletToVm方法,添加基于DSFACO的调度算法,并且使用Ant工具对平台进行重新编译,从而将基于DSFACO的任务调度算法加入到模拟平台的任务单元调度中,进行模拟实验。同理,对文献[10]中的增强蚁群算法TS-EACO进行相同的环境配置。

根据参数调整原则和大量数据实验,确定DSFACO的参数设置如下:α=10,β1=10,β2=0.5,β3=10,ρ=0.01,NI_MAX=500,st=40 min,计算资源的计算能力和任务数量用Matlab随机产生,且假设子任务编号为0～9之间的随机数,其中,0～2为调度级别1;3～6为调度级别2;7～9为调度级别3。在此实验数据条件下,分别仿真待调度任务数Task=50,100,200 3种情况。最后对DSFACO与TS-EACO算法的调度结果进行对比分析。

当调度任务数为50时,用户被安排调度任务数量如表1所示。

表1 用户调度的任务数量(Task=50)

可以看出,TS-EACO调度结果中,用户d的任务调度数量为0,说明资源管理平台并没有向其分配计算资源,从而其紧急任务无法及时被调度,导致任务调度不公平、用户满意度急剧下降。本文所设计的DSFACO算法的调度任务数量不会出现上述情况,每个用户都相对公平地得到任务处理机会。任务最短延迟时间对比如图2所示,通过TS-EACO计算后,任务的延迟时间约为280 min,迭代次数为25次左右;而DSFACO的任务延迟时间约为250 min,迭代次数50次左右,从结果可知,虽然DSACO的任务延迟时间仅略小于TS-EACO,但DSACO其在保证公平性的前提下在效率方面要好于TS-EACO算法,延迟时间优化了大约30 min。

图2 任务延迟时间(Task=50)

当被调度任务数增多到100时,DSFACO和TSEACO的任务延迟时间对比如图3所示,可以看出TS-EACO算法的收敛速度很快,但是其任务延迟时间比DSFACO算法多了大约50 min,相比于任务数为50的任务延迟时间(30 min)又多了20 min。当被调度任务数量继续增加到200时,从图4可以看出,2种算法所得调度结果的任务延迟时间差距达到110 min。随着被调度数量的增加,本文所设计的DSFACO算法进行的任务调度得到了任务延迟时间更小的调度结果,该算法能充分利用云计算资源进行更加合理的资源调度,获得更高的资源利用率,提高了任务调度的效率。

图3 任务延迟时间(Task=100)

图4 任务延迟时间(Task=200)

通过图5可知,使用DSFACO算法在云环境中对用户提交的任务进行调度,在保证任务调度公平性的前提下,有效缩短了任务延迟时间,提高了用户满意度,而且随着调度任务数量的增加,其综合调度优势越来越明显,任务延迟时间差距越来越大。

图5 算法任务延迟时间对比

从以上实验结果可知,虽然TS-EACO算法的任务延迟时间能达到较短,但本文所设计的DSFACO算法不但能保证任务分配的公平性,而且其任务完成时间、效率、用户满意度等方面都优于TS-EACO算法,进一步验证DSFACO算法能有效解决云环境下的调度问题。

5 结束语

本文提出一种基于改进蚁群算法的并行任务调度模型。将用户提交的动态任务分割成具有相互制约关系的子任务,并将其按运行次序放入具有不同优先级的调度队列中。采用基于最短任务延迟时间和任务分配公平的改进蚁群算法DSFACO,对同一个调度队列中的子任务进行调度。DSFACO算法以缩短任务延迟时间为目标研究子任务的调度问题。通过Cloudsim平台对比分析了DSFACO算法与TSEACO算法,实验结果表明DSFACO算法综合性能优于TS-EACO算法,更加适应云计算环境。下一步工作的重点是在保证DSFACO算法具有最短任务延迟时间的同时降低总计算成本。

[1] Armbmst M,Fox A,Griffith R,et al.Above the Clouds: A Berkeley View of Cloud Computing[R].University of California,Berkeley,Technical Report:UCB/EECS-2009-28,2009.

[2] 祝家钰,肖 丹.云环境下基于路径优先级的任务调度算法[J].计算机工程与设计,2013,34(10): 3511-3515.

[3] 孙 月,于 炯,朱建波.云计算中一种多DAG工作流可抢占式调度策略[J].计算机科学,2014,41(3): 145-148.

[4] Dorigo M,Blum C.Ant Colony Optimization Theory:A Survey[J].TheoreticalComputerScience,2005, 344(2/3):243-278.

[5] Gao Y.A Multi-objective Ant Colony System Algorithm for Virtual Machine Placement in Cloud Computing[J]. Journal of Computer and System Sciences,2013,79(8): 1230-1242.

[6] Dorigo M,BirattariM,StutzelT.AntColony Optimization[J].IEEEComputationalIntelligence Magazine,2006,1(4):28-39.

[7] Huang Qiyi,HuangTinglei.AnOptimisticJob Scheduling Strategy Based on QoS for Cloud Computing[C]//Proceedings of 2010 IEEE International Conference on Intelligent Computing and Integrated Systems.[S.l.]:IEEE Press,2010:673-675.

[8] Sanyal M G.Survey and Analysis of Optimal Scheduling Strategies in Cloud Environment[C]//Proceedings of IEEEInternationalConferenceonInformationand Communication Technologies.[S.l.]:IEEE Press, 2012:789-792.

[9] Chang F,Ren J,Viswanathan R.Optimal Resource Allocation in Clouds[C]//Proceedings of the 3rd International Conference on Cloud Computing.[S.l.]: IEEE Press,2010:418-425.

[10] 查华英,杨静丽.改进蚁群算法在云计算任务调度中的应用[J].计算机工程与设计,2013,34(5): 1716-1726.

[11] 李建峰,彭 舰.云计算环境下基于改进遗传算法的任务调度算法[J].计算机应用,2011,31(1):184-186.

[12] Dutta D,Joshi R C.A Genetic:Algorithm Approach to Cost-basedMulti-QoSJobSchedulinginCloud Computing Environment[C]//Proceedings of International Conference and Workshop on Emerging Trends in Technology.Mumbai,India:ACMPress,2011: 422-427.

[13] 李 震,杜中军.云计算环境下的改进型Map-Reduce模型[J].计算机工程,2012,38(11):27-29,37.

编辑 陆燕菲

Cloud Computing Task Scheduling Model Based on Improved Ant Colony Algorithm

WEI Yun,CHEN Yuanyuan
(School of Optical-electrical and Computer Engineering, University of Shanghai for Science and Technology,Shanghai 200093,China)

To solve the problem of resource scheduling problem in cloud computing,a parallel scheduling model is proposed,which can improve the task parallelism while maintaining the serial relationships between tasks.Dynamic tasks submitted by users are divided into sub-tasks in some serial sequences,and it puts into scheduling queue with different priorities according to running order.For these tasks in the same priority scheduling queue,an improved Delay Time Shortest and Fairness Ant Colony Optimization(DSFACO)algorithm is applied to schedule.Considering both fairness and efficiency,DSFACO algorithm applies to subtask scheduling problem to realize shortest delay time,thus improves the user satisfaction.Experimental results show DSFACO algorithm is better than the TS-EACO algorithm in fairness, efficiency and task delay time,and it can realize the optimal scheduling in cloud computing.

cloud computing;ant colony algorithm;task scheduling;fairness;task delay time

魏 赟,陈元元.基于改进蚁群算法的云计算任务调度模型[J].计算机工程,2015,41(2):12-16.

英文引用格式:Wei Yun,Chen Yuanyuan.Cloud Computing Task Scheduling Model Based on Improved Ant Colony Algorithm[J].Computer Engineering,2015,41(2):12-16.

1000-3428(2015)02-0012-05

:A

:TP393

10.3969/j.issn.1000-3428.2015.02.003

国家自然科学基金资助项目(61170277);上海市教委科研创新基金资助项目(12YZ094)。

魏 赟(1976-),女,副教授、博士,主研方向:云计算,智能交通控制,分布式系统;陈元元(通讯作者),硕士。

2014-05-27

:2014-07-26E-mail:chenyuanyuanzhang@163.com