云计算任务调度算法研究

黄 少 荣

(广东司法警官职业学院 信息管理系, 广州 510520)



云计算任务调度算法研究

黄 少 荣

(广东司法警官职业学院 信息管理系, 广州 510520)

云计算是一种新型的商业计算模式,应用大规模的虚拟化资源通过计算机网络向用户提供不同服务。云计算面对的用户众多,系统要处理的任务量与数据量十分巨大,并且云计算系统结构复杂,对大量任务进行高效调度是云计算中一个必须解决的难题。云计算任务调度算法决定了用户任务的执行效率和系统资源的使用效率,直接关系到云计算系统的整体稳定性和整体效果。在对云计算任务调度算法的相关研究现状进行深入分析和研究的基础上,从模型高效和算法高效2个层面上指出未来云计算任务调度算法的发展趋势,提出构建基于多目标优化的云计算任务调度模型。

云计算; 任务调度; 启发式算法; 多目标优化; 群智能

0 引 言

云计算是下一代计算机网络与应用的新技术,是网络计算、分布式计算、并行计算、效用计算、网络存储、虚拟化和负载均衡等传统计算机技术和网络技术的发展和延伸。云计算的核心思想是把计算任务分配给一个由大量计算机器组成的资源池,使用户能够按需获得云中的计算能力、存储空间以及信息服务[1]。云计算包含了基础设施即服务(IaaS)、平台即服务(PaaS)以及软件即服务(SaaS)这3个层次的服务,这些服务都存在任务与资源之间的调度问题,即云计算需要同时处理大量的计算任务,对用户提交的各种任务快速分配所需的计算资源。高效的任务调度策略决定了云计算的工作效率,是保证云计算服务质量的关键[2]。

1 云计算任务调度模型

云计算任务调度主要研究如何为用户提交的任务分配资源,也就是将多个相互独立的多样化任务分配到云中规模宠大的虚拟资源上,满足用户QoS要求、总任务的完成时间最小,负载均衡最高等目标,其调度模型如图1所示[3]。

云计算任务调度工作于云任务和虚拟机之间,即图1中左边虚线圈所示的众多箭头所在之处。任务执行所需要的成本、耗费的时间、负载均衡、系统稳定性、用户需求以及对系统的满意度等都是由任务调度策略决定的。因此,云计算任务调度算法决定了用户任务的执行效率和系统资源的使用效率,影响了整个云计算系统的工作性能。

2 云计算任务调度算法

目前的云计算任务调度机制还未形成统一的标准和规范,各大云计算服务供应商都是自己搭建云平台,并根据云平台的特点采用不同的任务调度策略,所用算法大致分为以下几种:

图1 云计算任务调度模型

2.1 传统任务调度算法

分布式计算是云计算技术的一种,分布式任务调度与云计算任务调度具有一定的相似性,一些用于分布式环境下的传统调度算法经过适当改进也可用于云计算任务调度问题。典型的有:

1) Min-min算法[4]。Min-min算法的设计思想是尽可能将任务指派给最早可用并且执行速度最快的计算资源,通过获取任务执行的2个最小值(最早执行开始时间和最快执行速度)完成选择。该算法属于贪婪算法的一种,通过先易后难的策略,任务集中在计算能力较强的节点上,而性能较低节点没有充分利用,容易造成负载不均衡。

2) Max-min算法。Max-min算法与Min-min算法类似,也是贪婪算法的一种,但采用的是先难后易的策略,分配任务时,按任务执行的难度考虑,选择最大最早完成时间的任务映射到具有最早执行时间的资源上执行。Min-min算法是先完成执行时间短的任务,而Max-min算法则先完成执行时间长的任务。在异构计算环境中,当短的任务数量远远多于长任务数量时,该算法具有一定的优势。

3) Sufferage算法[5]。Sufferage算法也是贪婪算法的一种,任务的Shfferage值就是该任务的最早完成时间与次早完成时间之间的差,该值代表某个任务如果不分配到完成时间最早的资源上将造成的损失。在任务间发生竞争时,比较各任务的执行损失,将损失最大的任务优先分配给计算资源。

这些算法都是为了提高用户任务的执行效率而设计的,但由于云计算中的任务资源的动态性、异构性和差异性,因此云计算的计算模式比传统的计算模式更加复杂,这些传统算法必须经过适当改进才能用于云计算任务调度问题。

2.2 Hadoop中的任务调度算法

大多的云计算环境是基于开源云计算框架----Hadoop架构的,针对云系统用户任务调度中不同的QoS目标约束要求,Hadoop实现了3种不同的调度算法:

1) 先进先出调度算法。FIFO算法(First In First Out,FIFO)根据用户提交任务的时间先后和优先级的高低来进行调度执行,当系统中有空闲的Worker请求任务时,Master会选择一个最早提交并且优先级最高的任务分配给该Worker节点。该算法简单,容易实现,但由于不对用户任务进行区分,并且云中用户任务调度的优先级和QoS要求各不相同,很难同时满足不同用户的QoS要求。

2) 公平调度算法[6]。公平调度算法(Fair Scheduling, FS)保证任务一个提交作业的用户在一定时间内得到响应,有很好的公平性和效率。按照该算法,当只有一个作业提交到系统后,整个系统的所有计算资源都会被这个作业独占。当有新作业提交时,原作业所占资源中已经完成任务的Worker会被释放,供那些新提交的作业使用。

3) 计算能力调度算法[7]。计算能力调度算法(Capacity Scheduling, CS)通过建立作业队列来管理和维护作业。该算法的核心思想是按照各个队列不同的需求将相应的资源分配出去,保证各个作业都能占用各自需要的资源。

这3种算法较为简单,但性能不佳,存在QoS(Quality of Service)差、频繁调度、资源碎片多、不够灵活等弊端,而且任务队伍和资源池配额受人为设置影响。

2.3 启发式任务调度算法

云计算任务调度本质上是一种组合优化类的NP-Hard问题,很难在多项式时间复杂度内求得全局最优解。随着资源和任务的急剧增加,传统的任务调度算法已经难以很好地满足实际应用的需求。针对此问题,很多研究者提出了不同的改进算法,这些算法中除了改进一些经典调度算法外,也逐渐被引入启发式优化算法。启发式算法能在一个较短的时间内得到一个满意的调度方案,在短时间内将大量用户任务分别映射到合适的计算资源上,其中表现比较优异的是遗传算法和群智能算法中的蚁群算法和粒子群算法,这3种算法的工作原理以及在云计算任务调度中的应用如下:

1) 遗传算法[8]

遗传算法(Genetic Algorithm, GA)是一种借鉴生物进化过程中的优胜劣汰机制而提出的一种随机搜索算法。GA随机生成一个固定数目的初始群体,群体中每个个体代表问题的一个解,该群体通过选择、交叉和变异等操作,根据适者生存的原则不断迭代进化,进化到一定代数的末代群体中的最优个体即代表问题的近似最优解。

GA的并行计算方式适合大规模运算和对复杂系统进行优化,算法具有全局收敛性,能较快地收敛到全局近似最优解,已经在云计算任务调度问题中展现出优越性能。Joanna等[9]在充分考虑云环境中的资源安全和信任机制问题等要素的基础上,利用遗传算法对云环境下的的资源进行调度。张水平等[10]对遗传算法进行改进,避免算法陷入局部最优,并利用改进的元胞自动机遗传算法对云环境下的资源进行合理调度。Sean Marston等[11]提出一种简单高效的遗传算法,对云环境下的资源进行分层排序,并根据资源利用属性提供访问顺序。该算法在资源离散分布时容易出现资源搜索困难。刘愉等[12]在充分考虑云计算环境的动态异构性和大规模任务处理特性的基础上,提出了一种基于染色体编码方式和适应度函数的改进遗传算法(IGA)对任务进行调度。

2) 蚁群算法[13]

蚁群算法(Ant Colony Algorithm, ACA)是模拟自然界中蚂蚁的群体协作觅食过程而提出的一种基于群智能的启发式仿生算法。该算法最早被应用于解决TSP问题,充分利用蚁群之间的信息传递,采用分布式正反馈机制在解路径图中搜索从蚁穴到食物间的最短路径。

ACA具有全局搜索和快速收敛等优点,并且容易与其他方法结合,鲁棒性强,已经在云计算任务调度问题上取得一定成绩。刘永等[14]在Google公司的Map/Reduce框架上提出了2个基于蚁群优化的资源调度策略,并在这两个资源调度策略中引入双向蚂蚁机制。张春艳等[15]将蚁群分为搜索蚁、侦察蚁和工蚁,提出一种多态蚁群算法对云环境下的任务进行调度,优化目标是最小化任务的平均完成时间。李坤[16]在考虑节点计算能力、网络带宽和任务难度等因素的基础上,利用改进蚁群算法对云环境下的任务进行调度,以任务执行时间和负载均衡为优化目标。查英华等[17]提出了一种增强蚁群算法对云环境下的任务进行调度,在优化任务完成时间同时兼顾了负载均衡。

3) 粒子群算法[18]

粒子群优化算法(Particle Swarm Optimization, PSO)是模拟鸟群觅食过程而提出的一种基于群智能的随机优化算法。PSO是一种基于迭代的优化工具,系统初始化为一组随机解,通过更新速度和位置来不断进化到全局最优解。

PSO具有简单通用、可调参数少、优化性能高等优点,是目前计算智能领域的一个研究热点,并且已经被应用于很多领域的优化问题中,也成功应用于云计算任务调度问题。Suraj等[19]在考虑任务之间的依赖关系的基础上,利用粒子群算法对云计算环境中的资源进行调度。刘万军等[20]在粒子群优化算法中引入变异粒子逆向飞行思想和动态多群体协作以提高全局搜索能力,提出一种改进粒子群算法对云计算资源进行调度。王登科等[21]提出一种基于粒子群优化和蚁群优化的任务调度算法,以总任务完成时间最小为优化目标。李依桐等[22]提出一种混合粒子群优化算法用于云任务调度,以最小化工作流费用为优化目标。算法中引入遗传算法的交叉和变异思想,并结合随迭代次数变化的变异指数,保证种群进化初期具有较高的全局搜索能力,避免陷入局部最优。

4) 其他智能算法

差分演化算法(Differential Evolution, DE)是一种新兴的基于群体进化的计算技术,通过模拟生物进化过程中个体间的合作与竞争来实现对复杂优化问题的求解,是一种具有保优思想的贪婪遗传算法。该算法实现简单、全局优化能力强,但不能直接用于离散问题[23]。朱宇航根据云计算任务调度问题的特点,对基本差分演化算法进行离散化改进,并将改进的离散差分演化算法(TC-MDDE)应用于满足用户QoS需求的云计算任务调度问题[3]。

人工峰群算法(Artificial Bee Colony, ABC)是一种模仿蜜蜂行为的群智能优化算法,通过蜂群觅食过程中不同分工的蜜蜂之间的信息共享和交流而实现问题空间的寻优[24]。ABC具有计算简单、参数少、容易实现等优点,成为云计算任务调度问题的一种新工具。卓涛等提出一种基于改进人工蜂群算法(IABC)对云计算资源调度模型进行求解,将个体当前最优值及随机向量引入到蜂群搜索过程中以加快搜索速度。该算法提高了云计算资源利用率,并且减少了任务的执行时间[25]。

人工鱼群算法(Artificial Fish-warm Algorithm, AFA)是一种基于动物自治体的优化方法,根据水域中鱼生存数目最多的地方就是本水域中富含营养物质最多的地方这一特点来模拟鱼群的觅食行为而实现寻优。AFA不需要了解问题的特殊信息,只需要对问题进行优劣的人工鱼个体的局部寻优行为,达到全局最优值在群体中突现出来的目的,收敛速度快[26]。孙文等提出了一种基于郭涛思想的AFA对云计算环境下的任务实现调度,该算法主要优化总任务的完成时间,同时也把任务平均完成时间作为一个必要的参考量[27]。

蛙跳算法(Shuffled Frog Leaping Algorithm, SFLA)是一种通过启发性搜索来寻找全局最优解的新型群体智能优化算法[28],该算法结合了基于个体所带模因(meme)进化的模因演化算法和粒子群优化算法的优点,先通过子群内部寻优,再通过子群间的混合来交换全局信息实现全局寻优。该算法具有高效的计算性能和优良的全局搜索能力,主要应用于解决多目标优化问题。骆剑平等改进SFLA对云计算资源进行调度,提出了2种不同的编码结构以及相应的更新方程,并根据调度方案的QoS值进行个体间的优胜劣汰,最后得到最佳调度。该调度方案只考虑任务完成时间和带宽资源,没有考虑其他参数[29]。

人工萤火虫算法(Artificial Firefly Algorithm,AFA)是受自然界中的萤火虫通过萤光进行信息交流这种群体行为的启发演变而来的一种新型仿生优化算法,该算法将搜索和优化过程模拟成萤火虫个体的吸引和移动过程,通过求解问题的目标函数量化各个个体位置的优劣。该算法具有参数少、实现简单、计算速度快等优点,在生产调度和路径规划等方面具有广阔的应用前景[30]。刘运等[31]在人工萤火虫算法的基础上,引入高斯变异的概念以提高算法的搜索精度和收敛速度,并将改进后的算法运用到云计算环境下的资源进行调度问题中,解决云计算中资源分配不均的问题。实验证明该算法能有效缩短云计算任务的完成时间。

启发式任务调度算法虽然可以较好地对云环境下的任务进行调度,但优化目标大多是单一地降低任务执行时间、降低成本或改善负载平衡等,没有综合考虑实际应用中更多的复杂因素,比如计算成本、用户多样化需求、网络延迟、故障处理、节能环保等,并且通常存在着收敛性能或全局最优解搜索能力较低的缺点,算法的收敛速度和计算精度有待进一步提高。此外,在启发式任务调度算法中,如果仅仅采用一种优化算法,得到的结果往往不是很理想,因此需要在启发式算法中结合其他优化技术,形成混合算法,以使其对云计算环境下的任务调度在综合性能上达到最优。

3 云计算调度算法的研究展望

目前的云计算任务调度主要存在着优化目标单一和算法性能不高这2方面问题,可以从模型高效和算法高效2个层面出发,综合考虑云计算的时间、成本、成功率、网络故障等约束条件,兼顾云计算用户和运营商双方的利益,构建多目标优化模型,并利用改进的算法对模型进行求解。

3.1 构建适合云环境下的任务调度模型,提出多个目标的优化

云计算任务调度主要采用的性能指标有:最优时间跨度(optimal makespan)、服务质量(quality of service)、负载均衡(load balancing)和经济原则(economic principles)等。从用户角度上考虑的是任务执行时间、可靠性、经济成本等约束条件,并且用户偏好多样,目标约束条件通常会包含多个指标的要求;从服务提供商角度考虑的是降低能耗、减少开销、提高资源利用率等。

针对传统云计算任务调度算法优化目标单一的问题,提出同时将任务执行时间、执行费用以及资源负载均衡等多个因素同时作为调度的优化目标,建立有效灵活的多目标优化模型,保障系统选择最佳的任务调度,最大化地满足用户多样化需求并最大化地提高云服务提供者的资源利用率和经济效益,达到互利共赢。

3.2 改进任务调度策略,提高算法性能

目前对云计算任务调度算法的研究仍处于探索阶段,每一种调度算法都有其应用领域和局限性,还没有一种能适用于所有领域,同时获得最佳调度效果的任务调度算法。

相对于传统任务调度算法,启发式算法具有更高的优化效率,特别是群智能算法,其潜在的并行性和分布式的特点为处理海量数据提供了技术保证[32]。在对云计算环境下的多目标任务调度问题的特点进行详细分析的基础上,应该进一步对群智能算法(ACA、PSO、DE、ABC、AFA和SFLA等)进行改进,充分调查群算能算法的参数,对参数做出合理设置,根据群智能算法的优缺点,在群智能中加入其他优化技术,采用相应的混合策略使各算法有效结合,取长补短,不断提高算法的优化性能,并将这些改进后高效的混合群智能算法运用到云环境下多目标优化的任务调度模型中,为用户任务做出合理调度,使任务执行时间短,费用低,能够有效应对资源进入退出、节点失效、资源故障这些突发事件,满足用户多样化需求,提高任务执行成功率。并且能够平衡系统负载,提高资源利用率,节约成本,进而提高云服务提供商的效益,同时满足多个目标的优化。

4 结 语

云计算任务调度算法决定了整个云计算系统的运行效率和工作性能,对云计算任务调度算法进行研究对于提高云计算系统的服务能力具有重要的理论价值和现实意义。本文对云计算环境下的任务调度算法做了分析和比较,重点阐述了启发式算法在云计算任务调度中的应用现状。结合云技术的发展趋势,指出构建多目标优化的云任务调度模型的必要性,针对目前使用的任务调度算法的不足,提出利用改进的混合群智能算法对云环境下的多目标任务调度模型进行优化的思路,使云计算中的任务调度更科学,保证云平台高效率运行。

[ 1 ]刘鹏. 云计算[M]. 2版. 北京:电子工业出版社, 2011:1-15.

[ 2 ]MICHAEL A, ARMANDO F, REAN G, et al. Above the clouds: a Berkeley view of cloud computing[M]. Berkeley: University of California, 2009:1-23.

[ 3 ]朱宇航. 差分进化算法及其在云计算任务调度中的应用研究[D]. 兰州:兰州交通大学, 2013.

[ 4 ]BRAUN T D, SIEGEL H J, BECK N. A comparsion of eleven static heristics for mapping a class of independent tasks onto heterogonous distributed computing systems[J]. Parallel and Distributed Computing, 2001,61(1):810-837.

[ 5 ]郑爱卿. 基于执行时间方差的元任务网格调度算法研究[D]. 北京:北京交通大学, 2008.

[ 6 ]ISARD M, PRABHAKARAN V, CURREY J, et al. Fair scheduling for distributed computing clusters[C]∥Proceedings of the 22nd ACM SIGOPS Symposium on Operating Systems Principles, New York:ACM, 2009:261-276.

[ 7 ]遆鸣. 云计算下计算能力调度算法的研究和改进[D]. 太原:太原理工大学, 2012.

[ 8 ]HOLLAND J H. Adaptation in Nature and Artificial Systems[M]. Boston: MIT Press, 1992.

[ 9 ]JOANNA K, FATOS X, MARCIN B. Secure and task abortion aware GA-based hybridmetaheuristics for grid scheduling[J]. Computer Science, 2010,1:526-535.

[10]张水平,邬海艳. 基于元胞自动机遗传算法的云资源调度[J]. 计算机工程, 2012,38(11):11-13.

[11]SEAN M, ZHI L, SUBBAJYOTI B. Cloud computing-the business perspective[J]. Decision Support Systems, 2011,51(1):176-189.

[12]刘愉,赵志文,李小兰,等. 云计算环境中优化遗传算法的资源调度策略[J]. 北京师范大学学报:自然科学版, 2012,48(4):378-384.

[13]DORIGO M, MANIEZZO V, COLOMI A. Ant system: optimization by a colony of cooperating agents[J]. IEEE Transactions on System, Man and Cybernetics, 1996,26(1):29-41.

[14]刘永,王新华,邢长明,等. 云计算环境下基于蚁群优化算法的资源调度策略[J]. 计算机技术与发展, 2011,21(9):19-27.

[15]张春艳,刘清林,孟珂. 基于蚁群算法的云计算任务分配[J]. 计算机应用, 2012,32(5):1418-1420.

[16]李坤. 云环境下的任务调度算法研究与实现[D]. 长春:吉林大学, 2012.

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

[18]KENNEDY J, EBERHART R. C. Particle Swarm Optimization [C]∥Proceedings of the IEEE International Conference on Neural Networks, Piscataway: IEEE,1995:1942-1948.

[19]PANDEY S, WU L, GURU M, et al. A particle swarm optimization-based heuristic for scheduling workflow application in cloud computing environments[C]∥24th IEEE International Conference on Advanced Information Networking and Applications, Piscataway: IEEE, 2010:1109-1119.

[20]刘万军,张孟华,郭文越. 基于MPSO算法的云计算资源调度策略[J]. 计算机工程, 2011,37(11):43-44.

[21]王登科,李忠. 基于粒子群优化与蚁群优化的云计算任务调度算法[J]. 计算机应用与软件, 2013,30(1):290-293.

[22]李依桐,林燕. 基于混合粒子群算法的云计算任务调度研究[J]. 计算技术与自动化, 2014,33(1):73-77.

[23]STORN R, PRICE K. Differential evolution-A simple and efficient heuristic for global optimization over continuous spaces[J]. J Global Optimization, 1997,11(4):341-359.

[24]KARABOGA N. A new design method based on artificial bee colony algorithm for digital IIR Filters [J]. J Franklin Institute, 2009,346(4):328-348.

[25]卓涛,詹颖. 改进人工蜂群算法的云计算资源调度模型[J]. 微电子学与计算机, 2014,31(7):147-150.

[26]李晓磊,邵之江,钱积新. 一种基于动物自治体的寻优模式:鱼群算法[J]. 系统工程理论与实践, 2002,22(11):32-38.

[27]孙文新. 人工鱼群优化在云计算环境中任务调度算法[J]. 安徽农业科学, 2012,40(11):6923-6929.

[28]EUSUFF M M, LANSEY K E. Optimization of water distribution network design using the shuffled frog leaping algorithm[J]. Water Resources Planning and Management, 2003,129(3):210-225.

[29]骆剑平,李霞,陈泯融. 云计算环境中基于混合蛙跳算法的资源调度[J]. 计算机工程与应用, 2012,48(29):67-72.

[30]GROSSMAN R L. The case of cloud computing[J]. IT Professional, 2009,11(2):23-27.

[31]刘运,程家兴,林京. 基于高斯变异的人工萤火虫算法在云计算资源调度中的研究[J]. 计算机应用研究, 2015,32(3):834-837.

[32]CHRISTIAN B, DANIEL M. 群智[M]. 龙飞,译. 北京:国防工业出版社, 2010.

Study of task scheduling algorithm on cloud computing

HUANGShaorong

(Department of Information Management, Guangdong Justice Police Vocational College, Guangzhou 510520, China)

Cloud computing is a new business computing model which uses large-scale virtualized resources to provide services through the computer network. In the cloud computing environment, the users are multitudinous, and the number of tasks and the amounts of data are huge, and the structure of cloud computing system is very complex, and it is a difficult problem to be resolved to schedule tasks efficiently. Task scheduling algorithm determines the execution efficiency of user tasks and use efficiency of system resources, and is directly related to the integral stability and overall effect. After the analysis and comparison of the cloud computing scheduling strategies, based on two aspects of model efficiency and algorithm efficiency, this paper points out the development trend of cloud computing task scheduling algorithm, and proposes cloud computing task scheduling model based on multi-objective optimization.

cloud computing; task scheduling; heuristic algorithm; multi-objective optimization; swarm intelligence

2014-10-10。

广东省科技厅自然科学基金资助项目(101754539192000000)。

黄少荣(1976-),女,广东饶平人,广东司法警官职业学院副教授,硕士。

1673-5862(2015)03-0417-06

TP306.1

A

10.3969/ j.issn.1673-5862.2015.03.022