云计算环境下任务调度算法的研究

李菡薏,陈家琪

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

云计算环境下任务调度算法的研究

李菡薏,陈家琪

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

在云计算环境中存在庞大的任务数,为了能更加高效地完成任务请求,如何进行有效地任务调度是云计算环境下实现按需分配资源的关键。针对调度问题提出了一种基于蚁群优化的任务调度算法,该算法能适应云计算环境下的动态特性,且集成了蚁群算法在处理NP-Hard问题时的优点。该算法旨在减少任务调度完成时间。通过在CloudSim平台进行仿真实验,实验结果表明,改进后的算法能减少任务平均完成时间、并能在云计算环境下有效提高调度效率。

云计算;任务调度;蚁群算法

如今,越来越多的计算任务和服务都被引入进了云端,云计算也变得越来越受欢迎。云计算是分布式计算、并行计算、网格计算、效用计算、虚拟化、网络存储等传统计算机和网络技术发展融合的商业实现。云计算可以对共享可配置的计算资源进行方便的按需访问,并且根据实际情况来进行按需分配,同时管理这些资源只需要通过极小的代价来进行管理,是一种基于互联网的新型计算服务模式。而云计算平台的核心技术之一便是调度,目前关于调度问题的研究尚处于初级阶段,而现有的调度算法均存在着一些不足之处。而在云计算环境中,任务调度是一个NP完全问题[1],蚁群算法作为智能优化算法,适合于求解NP类问题。但就目前业界内的研究成果来看,蚁群算法虽然在解决云计算调度问题时取得了较好的效果,但仍存在不足。比如蚁群算法虽具有较好的寻优能力,但由于初始阶段信息素匾乏,初期收敛速度较慢。因此,本文从最小化完成时间的角度优化云计算环境的任务调度问题,通过对现有的蚁群算法进行优化,以建立一个较优的任务调度策略。

1 问题描述

1.1 云计算调度的概念

迄今为止,针对云计算的任务调度问题仍属于一个比较前沿的课题。云计算的核心思想是将计算任务分布在大量由计算机组成的资源池上,使用户能够按需获取计算能力、存储空间和信息服务,但云中拥有的资源与要处理的任务均是海量的,因此如何充分利用云中资源对任务进行高效调度是云计算中的重点与难点。

云计算的核心服务通常可分为以下3个子层:

(1)IaaS(Infrastructure as a Service)层。该层是云计算的基础,IaaS层通过建立大规模数据中心为上层的云计算服务提供大量的硬件资源。同时,IaaS层可在虚拟化技术的支持下,提供个性化的基础设施服务来实现硬件资源的按需配置。

(2)PaaS(Platform as a Service)层。该层作为3层核心服务的中间层,作为平台即服务层既可为上层应用提供简单、可靠的分布式编程框架,但由于底层系统具有一定的复杂性,所以又需要基于底层的资源信息来管理数据、调度作业。随着数据密集型应用的普及和数据规模的日益庞大,PaaS层需要具备存储与处理海量数据的能力。

(3)SaaS(Software as a Service)层。该层面向的是云计算终端用户,作为软件即服务层其提供基于互联网的软件应用服务。随着Web服务、HTML5、Ajax、Mashup 等技术的成熟与标准化,SaaS应用近年来发展迅速。

虽然这3个云计算的核心服务层分别侧重于不同的应用,但其仍存在着资源、任务调度问题。调度问题是云计算中的一个重要问题,直接影响到资源的使用效率、云服务的稳定性、运营成本和用户的满意程度。因此云计算的研究一直侧重于调度方面,无论是从理论技术还是实际应用方面都具有重要的研究价值[2]。

1.2 蚁群算法

云计算调度问题的研究重点就是性能,以调度性能作为最终目标,一般都以最短完成时间、系统效率等作为衡量算法优劣的标准。目前研究和使用较为广泛的算法包括Min-Min算法、Max-Min算法、遗传算法(GA)、蚁群算法、贪婪算法和模拟退火算法等。IBM云计算平台采用的是以性能为中心的调度策略[3]。李建峰等人提出了一种以作业平均完成时间为标准的、基于Map Reduce模型的双适性遗传算法(DFGA)[4],汤小春等人提出了一种基于元区间的分配决策算法[5];华夏渝等人提出一种基于蚁群优化(Ant Colony Optimization)的资源分配算法[6]。

将任务与资源按照一定的原则进行映射就是任务调度。云计算是指通过虚拟化技术将用户的任务通过虚拟机处理,同时将资源以虚拟机的形式体现,这样可简化资源与任务的匹配,从而将分配资源的过程封装为分配虚拟机的过程[7]。一个良好的任务调度算法,应根据环境或任务类型的变化来调整其调度策略[8]。在云计算中,优秀的任务调度算法就是要求使用最少的宽带需求、最小完成时间将任务分配给虚拟机。因此,像蚁群算法(ACO)这种动态的任务调度算法,更加适合解决云计算环境下的动态任务调度问题。ACO算法是一种随机搜索算法[9],该算法使用了一种正反馈机制来模拟自然界蚂蚁寻找食物的方法,当蚂蚁在寻找食物时,每只蚂蚁都会在其经过的路上分泌一种信息素(Pheromone),蚂蚁群体之间通过这种信息素来达到互相进行交流、协作,最终在觅食过程中倾向寻找较短路径。本文从最小化完成时间的角度提出基于蚁群算法的任务调度优化算法JS-ACO,利用蚁群算法的自适应性等特点将其应用到云计算环境的任务调度中,通过为作业寻找最合适的从结点来减少网络宽带的消耗,能提高整个系统的吞吐量,较大程度地提高云计算环境的效率和性能。

2 算法描述

2.1 基于蚁群的作业调度算法

基于蚁群的作业调度算法具体描述如下:

步骤1 信息素参数初始化。将每条路径上的信息素参数根据式(1)初始化

τ0=m×p

(1)

其中,m是虚拟机的个数;p是表示CPU的速度。

步骤2 任务转移规则。为了构造一个完整的解决方案,蚂蚁带着未调度的任务将按照状态转移规则选择下一步移动的位置,从而使一群蚂蚁并行异步地访问邻近虚拟机。在t时刻蚂蚁会根据式(2)和式(3),从当前的虚拟机i选择下一个虚拟机m。

(2)

其中,τim(t)为t时刻从虚拟机i到虚拟机m的信息素强度;q是分布在[0,1]的随机数;q0是一个参数(0≤q0≤1)。avoidk是蚂蚁k的回避列表,S在t时刻根据式(3)状态转移概率选择邻近虚拟机

0,else

(3)

(4)

其中,ETjm(K+1)表示作业j到达虚拟机m的预测执行时间[10];K+1表示作业执行次数;ETjm(K)表示上次执行作业的预测执行时间;RTjm(K)表示上次执行作业的实际执行时间;ξ是一个经验参数(0<ξ<1),表示上次作业的预测执行时间和实际执行时间对下一次预测作业执行的影响度,用来调节在云计算中经验值与预测值的比重

(5)

式中,TTjm表示作业j到达虚拟机m时的预测传输时间,其中Sj表示作业j的大小,bandwidthm表示虚拟机m的可用带宽。

步骤3 局部信息素更新。当蚂蚁k选择了一个虚拟机之后,为衰减被选中路径的信息素浓度,使蚂蚁们对其他路径的选择以扩大搜索范围避免了过早收敛,必须根据式(6)对信息素进行更新

τim=(1-ρ)×τim+ρτ0

(6)

其中,ρ(0<ρ<1)是一个参数,表示信息素蒸发因子。

步骤4 全局信息素更新。当所有蚂蚁都已完成一次遍历,按照式(7)更新本次遍历中最佳路径上的信息素

(7)

2.2 算法流程

基于蚁群优化的云计算任务调度算法JS-ACO如下

ProcedureJS-ACO

Begin

初始化参数

While(未找到最优解的停止条件)do

每个蚂蚁开始活动

While(当每只蚂蚁都完成构建解时停止)do

For每只蚂蚁do

根据状态转移概率公式选择下个虚拟机;

根据式(6)进行局部信息素更新;

Endfor

记录此次迭代的最优解;

对最优解进行局部搜索;

根据式(7)进行全局信息素更新;

Endwhile

Endwhile

End

3 实验与分析

3.1CloudSim

C1oudSim是墨尔本大学RajkumarBuyya教授领导的网格实验室与Girdbus项目推出的云计算仿真平台,用于云计算基础设施和应用服务的建模、仿真和实验,CloudSim的首要目标是在软件、硬件、服务等云基础设施上,对不同应用和服务模型的调度和分配策略的性能进行量化和比较,最终模拟云计算中资源[11]。在GridSim模型基础上发展而来的C1oudSim能根据云计算的特性,模拟云计算环境下的资源管理和调度模拟。云计算的特点之一是虚拟化技术中资源,将这些资源虚拟化为资源池,打包对外向用户提供服务。C1oudSim能恰好符合这个特点,其提供的扩展部分可对接口进行实现,能提供基于数据中心的虚拟化技术、虚拟化云的建模和仿真功能。在基于CloudSim云计算仿真器中用户能够反复测试自身的程序,在部署服务之前调节性能瓶颈,既能节约大量时间,又可以给开发工作带来较大的便利。

3.2 仿真环境

表1 算法的仿真实验环境

CloudSim采用分层设计特征及体系结构,图1所示为分层的CloudSim体系结构图。

图1 分层的CloudSim体系结构图

CloudSim的顶层是用户代码层,该层提供如主机、用户、虚拟机、应用等一些基本实体,同时提供代理调度策略。通过扩展这些实体可使开发者在用户代码层开发各种应用调度技术,并执行CloudSim支持的云配置的鲁棒性测试。CloudSim的下层是为云计算的虚拟数据中心环境所设置的仿真层、并为仿真提供各种相应的接口。例如:虚拟机分配、CPU分配、内存分配、存储空间分配及宽带分配。下层的仿真层主要用于主机与虚拟机之间资源分配方面的策略研究,并通过扩展核心的虚拟机调度函数实现。

当开始一个仿真时,首先数据中心(DataCenter)创建资源后通过CIS(Cloud Information Service)注册服务,然后CIS提供相关服务的匹配决策,由数据中心代理(DataCenterBroker)管理信息的交互过程。

C1oudSim提供了良好的云计算调度算法仿真平台,C1oudSim中提供的bindCloudletToVm(int cloudletId,int vmId),DataCenterBroker类,通过对该类进行扩展,云应用开发人员可将任务分配到指定的虚拟机上执行,实现自定义的调度策略,完成对自定义的调度算法进行模拟和测试。通过配置特定的环境来进行模拟云计算,最终达到模拟云计算环境下的开发测试目的。

图2 CloudSim的仿真流程

3.3 算法仿真

算法的调度参数列表如表1、表2所示。

表2 调度参数列表

表3 参数列表

在实验中α、β参数值的选取至关重要,参数与蚁群算法的性能是相挂钩的,本次实验设置α的初值为0.1,而β的值设置为2.0。信息素蒸发因子ρ取0.1,ants蚂蚁的数量为20。由于蚁群算法是一个启发式算法,为保证实验结果的公平性,取10次实验结果的平均值来与其他算法相比较,实验结果如图3所示。

图3 任务执行时间比较图

在其他条件不变的情况下,将短任务改为长任务,任务执行时间如图4所示。

图4 任务执行时间比较图

从实验结果中可看出,JS-ACO算法的平均完成时间小于其他两种算法,任务执行的时间比传统的Min-Min算法短,随着任务数量的增加,算法的执行时间差越来越大,优化性能的提升越发明显。究其原因,主要是因为改进后的蚁群算法可动态的跟踪虚拟机的状态。

4 结束语

由于任务调度是典型的NP-Hard问题,而蚁群算法成功解决了其他的NP问题,本文旨在优化云计算环境下的任务调度问题,从最小化完成时间出发提出了改进后的ACO算法。该算法利用了蚁群算法的独特性与云环境的特殊性,应用蚁群算法的正反馈机制来求得全局的近似最优解,而不会像其他搜索算法那样容易陷入局部最优解。与此同时,应用信息素的挥发机制,通过更新信息素来指导蚂蚁进行状态转移,对每次迭代产生的最优解再进行局部搜索,最终得到合理的解决方案。实验结果表明:通过改进后的算法可减少完成时间,提高系统效率。本文算法只考虑了任务调度过程中的任务数量,而在实际应用中情况比较复杂,还有更多因素需要考虑,比如对本文提出的蚁群算法进行其他的可能性测试如:任务数量继续增多、数据中心不止一个等,再通过实验结果分析本文实现的蚁群算法是否还存在其他的不足。另外还可考虑与其他算法结合,继续优化蚁群算法的性能。

[1]ThusooA,ShaoZ,AnthonyS,etal.Datawarehousingandanalyticsinfrastructureatfacebook[C].Indianapolis,Indiana:SIGMOD’10,ACM,2010.

[2] 左利云,曹志波.云计算中调度问题研究综述[J].计算机应用研究,2012(11):4023-4027.

[3] 田文洪,赵勇.云计算:资源调度管理[M].北京:国防工业出版社,2011.

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

[5] 汤小春,刘健.基于元区间的云计算基础设施服务的资源分配算法研究[J].计算机工程与应用,2010,46(34):237-241.

[6] 华夏渝,郑骏,胡文心.基于云计算环境的蚁群优化计算资源分配算法[J].华东师范大学学报:自然科学版,2010(1):127-134.

[7]RodrigoNCalheiros,RajivRanjan,CesarAFDeRose,etal.CloudSim:Anovelframeworkformodelingandsimulationofcloudcomputinginfrastructuresandservices[R].Australia:UniversityofMelbourne,2009.

[8]ChangF,RenJ,ViswanathanR.Optimalresourceallocationinclouds[C].WashingtonDC,USA:CLOUD’10,2010.

[9]DorigoM,BlumC.Antcolonyoptimizationtheory:Asurvey[J].TheoreticalComputerScience,2005,344(2-3):243-278.

[10]张晓杰,孟庆春,曲卫芬.基于蚁群优化算法的服务网格的作业调度[J].计算机工程,2006,32(8):216-218.

[11]BuyyaR,RanjanR,CalheirosRN.Modelingandsimulationofscalablecloudcomputingenvironmentsandthecloudsimtoolkit:challengesandopportunities[C].Kochi,India:InternationalConferenceonHighPerformanceComputing&Simulation,2009.

Research on Task Scheduling Algorithm In Cloud Computing Environment

LI Hanyi,CHEN Jiaqi

(School of Optical-Electrical and Computer Engineering,University of Shanghai for Science and Technology,Shanghai 200093,China)

There are large number of tasks in cloud computing environment,and how to conduct effective task scheduling is the key to allocate resources by need in cloud computing environment in order to be more efficient completion of task request.This paper proposes a task scheduling algorithm based on the ant colony optimization which an adapt to the dynamic characteristics of the cloud computing environment coupled with the advantages of ant colony optimization in the treatment of NP-Hard.The algorithm is designed to minimize task completion time during scheduling.Simulation on the CloudSim platform shows that this algorithm can effectively improve the task scheduling time under cloud computing environment.

cloud computing;job scheduling;ant colony optimization

2015- 04- 16

上海市教委科研创新基金资助项目(12zz146)

李菡薏(1991—),女,硕士研究生。研究方向:计算机网络。E-mail:zitengyekuki@163.com。陈家琪(1957—),男,教授。研究方向:网络计算等。

10.16180/j.cnki.issn1007-7820.2015.11.012

TP301.6

A

1007-7820(2015)11-043-05