Broad Angle for Technology技术广角
云计算环境中任务调度策略
王海涛1 张焕青1 肖世平2 张学平1 闫 力1
1 中国人民解放军理工大学 南京 2100072 西安通信学院指挥控制系统系 西安 710100
摘 要 在满足用户QoS 的前提条件下，对海量任务进行高效调度并对云资源进行合理分配是云计算领域的一个研究热点。文章论述云计算环境下任务调度的概念、特点和目标，归纳了云计算任务调度的研究现状，并对传统任务调度算法、Hadoop 中的任务调度算法、智能化的任务调度算法的实现机制和性能指标等进行了分析与比较。分析结果表明智能化任务调度算法性能优良且适应性强，是今后的研究重点。关键词 大数据；云计算；任务调度；调度算法
云计算提供的服务面向的用户群是庞大的，“云”中的任务数量也是巨大的，系统每时每刻都需要处理海量的任务[1]。要实现这一目标，云计算系统需要使Internet 上的资源像水和电一样在网络上按需分配，并能够根据请求任务的复杂性和数据集合的大小合理动态调整，这就提出了云计算环境中任务调度的问题。云计算的任务调度就是在一个特定的云环境中，根据一定的资源使用规则，将资源在不同的使用者之间进行调整的过程。因此，考虑如何合理地分配和利用云环境中的资源、有效地调度用户提交的海量任务且保证云系统的负载均衡成为云计算研究的重点之一。近年来，许多学者已提出不少良好而有现实应用价值的任务调度策略，但到目前为止，还没有形成一个统一、通用并有效的任务调度策略体系。云计算任务调度策略不仅直接对任务执行时间产生作用，还会对整个云的性能产生影响。
用户提交的某项任务直接交与云计算系统处理；而是在收到用户提交的任务之后，将任务拆分为许多子任务；并查询目前状态下云计算系统内部可用资源状况，按照一定的调度策略将子任务与计算资源建立映射关系。一般情况下子任务无法细分，一个子任务对应一个计算资源，一个计算资源可对应多个子任务。在所有计算资源完成任务执行并进行汇总后，将结果返回至提交任务的用户。
在云计算中，任务调度策略对用户应用任务的服务质量和云计算系统的运行效率产生直接影响。好的任务调度策略能够有效降低任务完成时间，满足用户对于便捷、安全、人性化的要求，同时任务调度也将平衡云计算系统负载，提高资源利用率，降低能耗和运营成本，促进云计算的良好发展[2]。
1.2 云计算任务调度模型
云计算中的任务调度概况如图1所示[3]。
任务集合T={t 1，t 2，…，t n }，表示当前任务队列有n 个相互独立的任务，并且每个任务只能在一个虚拟机上运行。虚拟机资源集合为VM=γ1，γ2，…，γm ，表示云计算数据中心现可利用的m 个虚拟机资源，虚拟机性能用MIPS 表示。
1 云计算中的任务调度
1.1 云计算任务调度概念
在云计算中，由于用户数量多、应用任务种类繁杂，且云计算资源池规模庞大且异构，通常无法直接将
基金项目：国家自然科学基金资助项目(61072043)
57
技术广角 Broad Angle for Technology
䌘⑤ㅵ⧚
许多相似性，包括调度都将任务与资源建立有效的映射关系，以期实现任务的顺利执行；将降低任务执行时
间、系统能耗作为共同目标等。但是云计算环境中的任务调度比传统计算模式下的任务调度涉及面更为广泛，
也更为复杂，其区别在于：首先，云计算环境中的资源不是集中式部署，任务调度策略也必须适应分布式部署
的资源模式；其次，云计算资源同时执行多方任务，任务调度不能够影响到云计算系统中其他正在执行任务的资源，以免造成多方任务因抢占资源造成的节点失效问
图1 云计算中任务调度
另外，定义任务传输矩阵tom={t ij |t ij ≥0，1≤i ≤n ，1≤j ≤m}，t ij 表示将任务t i 传输到虚拟机γj 所用时间；定义任务计算矩阵exe={e ij |e ij ≥0，1≤i ≤n ，1≤j ≤m}，e ij 表示任务t i 在虚拟机γj 上计算所用时间。
t ij = outputsizei /bandwidth j e ij = lengthi /Mips j
(1)(2)
题；最重要的一点是，作为一种商业服务模式，云计算任务调度必须同时考虑终端用户、云计算服务商、网络提供商等多方面的利益，满足用户QoS 协议的前提下，为云系统创建良好的任务执行环境，才能保证云系统正常运行。云计算环境中任务调度策略具体的评价标准包括：完成时间(Task Makespan)、经济原则(Economic Principles) 、通信成本(Communication Cost)、安全程度(Degree of Safety)、负载状况(Load Condition)等[4]。
1）完成时间。指从终端用户向云计算系统提交应用任务开始到收到结果为止的时间段，包括任务传输、拆分、调度、执行等多项时间综合，其中任务执行时间占比最大。一般情况下，任务完成时间是用户最为关心的指标，也是反映云计算系统性能最直接的指标。目前大部分任务调度策略都以完成时间作为主要研究内容。
2）经济原则。云计算系统之所以区别于传统的计
其中，outputsize i 表示任务t i 的数据量，length i 表示任务t i 计算量；bandwidth j 表示虚拟机γj 的通信带宽，Mips j 表示虚拟机γj 的计算能力。
n 个任务在m 个虚拟资源上的预测执行时间ETC(Expected Time to Compute)是一个n ×m 的矩阵。ETC ij 表示t i 在虚拟机γj 运行所需时间，ETC ij =t ij +e ij ，则虚拟机执行分配任务集合时间可表示为E j 。由于任务分配到各个虚拟机资源上是并发执行的，所以所有任务完成所需的执行时间是数组E 中的最大值，用E total 表示。
E j =∑ie T ask j +∑ie T ask j t ij
其中， Task j 为在虚拟机γj 上执行的任务集合。任务t i 在处理节点γj 上执行的费用可以表示为：cost j =ETC ij ×q j (4)其中，q j 表示在虚拟机j 上单位时间内的计算成本。云计算任务调度的总目标往往以上述公式为基本条件，寻求任务执行时间、经济效益、资源利用率等方面的利益最大化。
(3)
算模式，原因在于能够将多方资源整合并面向大众，在整个利益链中有网络营运商、云服务提供商、基础设备维护商等，他们利用良好的任务调度策略，降低整体运营成本，可促进云计算的可持续发展。
3）通信成本。由于用户向云计算数据中心提交的应用任务种类繁多且数量巨大，因此任务需要进行切分规划，递交至不同计算资源处理执行。而子任务间往往存在处理的优先级，或形成工作流性质的子任务。不同计算资源在处理任务时需要进行通信协调，如何降低数据中心内部通信成本，提高数据文件有效访问率，对任务顺利执行影响较大。
1.3 云计算任务调度评价标准
云计算任务调度与传统计算模式下任务调度存在
58
Broad Angle for Technology技术广角
4）安全程度。目前，云计算部署方式包括公有云、私有云、社区云和混合云多种形态，不同部署方式面向不同的终端用户。公有云、混合云是最为广泛的部署方式，由于其开放性，用户准入门槛较低，云系统内部数据隔离措施不完善、数据安全往往无法得到保证。在这种条件下，如何规范子任务与计算资源的映射方式，保证用户提交任务中的敏感数据在执行过程中不被干扰、泄露，而形成安全隐患，成为云计算环境中任务调度日渐关注的问题之一。
5）负载状况。由于云计算资源池内部的各类资源分布式部署且性能差异较大，其处理任务能力也会有明显不同，如果将任务集中于某一些性能优良的计算资源可能会造成任务队列过长而影响任务正常执行，任务过多分配至性能较差资源则会降低执行效率。系统内部的负载状况不均会影响用户与云计算服务商多方利益。因此，必须通过任务调度策略实现系统负载平衡，降低系统运行成本，提高任务执行效率。
种，对于云计算数据中心的可用计算资源，每次都选取具有最快执行速度和能将某一任务最先完成的计算资源，是一种典型的先易后难策略。该算法一般用于任务负载轻，且用户对服务质量要求不高的情况。当云计算规模扩大、任务增多时，利用该调度算法容易造成优质资源上的任务累积过多，而其他资源长期处于空闲状态，不利于提高整体资源利用率。
当不同子任务在调度过程中发生资源的抢占或竞争时，则根据比较Sufferage 值的大小进行具体的 调度。
3 Hadoop中的任务调度算法
为方便大规模分布式部署的集群系统计算运行，Google 公司最先提出Map/Reduce计算模式[7]。因其计算模式简练易移植，且计算效率高，现已被广泛借鉴应用在众多云计算平台中。Map/Reduce计算模式的基本思想为：将一个大型任务首先通过Map 步骤进行规划、拆分成子任务，子任务进而分配至分布式部署的计算资源中进行具体的Reduce 步骤，在所有计算资源执行完毕后，将计算结果汇总输出，以完成任务的总体处理(见图2) 。
2.2 Max-min算法
Max-min 算法也属于贪心算法的一种，其在算法难度上与Min-m i n 算法保持一致。不同的是，Max-min 在获取到云计算数据中心可最早执行的计算资源后，总是将计算量最大，也就是完成时间最晚的任务分配至该计算资源。Max-min 算法改善了利用Min-min 算法时容易导致的负载严重不均的问题，能够在一定程度上提高云计算系统内部资源利用率，但该算法不具有自适应性和拓展性，应用空间依旧较小。
3. 1 先进先出的调度算法(FIFO)
FIFO 算法即对任务实行先进先出的调度策略，根据用户提交应用任务的优先级别和到达时间来判断与计算资源的映射关系。在云计算系统中，计算资源一旦出现空闲状态，系统就在任务队列中选择最早提交并且优先级高于其他的任务，分配至该计算资源进行执行。
云计算利用FIFO 算法可以减少任务调度开销，且算法简单、易于应用，但其缺点也比较明显：一方面当计算量大、任务优先级高的任
2.3 Sufferage算法
Sufferage 算法[6]与Min-min 和Max-min 两种调度算法同属于贪心
2 传统的任务调度算法
由于云计算与网格结算的部分相似性，早期研究中主要将网格环境中的任务调度策略移植到云计算环境中，其主要包括以下几种。
算法，但不同的是，Sufferage 算法中将次小任务完成时间与最小任务完成时间的差定义为任务执行损失，称为Sufferage 值。在任务调度过程中，总是将任务分配至具有最大Sufferage 值的计算节点，
2.1 Min-min算法
Min-min [5]算法是贪心算法的一
59
技术广角 Broad Angle for Technology
䕧 ӊ0DS䰊↉
Ё䯈 ӊ
5HGXFH䰊↉
˄ ˅
图2 Map/Reduce具体执行过程
䕧 ӊ
务处于执行状态时，小型任务可能长时间得不到云系统相应；另一方面该算法灵活性差，不支持资源抢占等特殊要求。但可以把该算法调度框架进行修改，得到适合具体应用的任务调度策略。
内等待分配，在任务池中系统负责对任务进行管理与维护，池内的任务可以平分可用资源，不同任务池的任务则对计算资源进行抢占。这种任务调度策略在一定程度上保证了任务调度的公平性，避免部分用户得不到体验性较好的服务，提高了云计算服务的整体质量。
队列中任务不需要配备的计算资源时，该队列所属的资源就会被其他队列利用，当该队列内又出现任务需要执行时，原来被配备的计算资源重新用于执行该队列内的任务。通过这种措施，提高了计算资源的利用率，避免资源负载不均和某些资源闲置的情况发生。
但是计算能力调度算法不支持资源抢占，当一个计算资源开始执行某项任务后，必须要等到任务执行完毕后才会执行同队列或其他队列的任务。另外，当某些用户长期使用了超过其限制比的资源后，系统将不再为其分配另外的计算资源，以避免影响系统服务的公平性。
3.2 公平调度算法(Fair Scheduling)
最初由Facebook 提出，初衷为让Hadoop 实现更为公平的作业处理。其基本思想为最大程度地把系统中资源平均分配给用户提交的任务，尽可能满足不同需求的用户能够有平等的机会使用系统资源[8]。
以上云计算任务调度策略，只重视资源池内计算资源的选择，未执行的任务在任务队列中处于等待状态，而资源无法主动选择队列中的任务。在公平调度算法中，建立与资源池结构类似的任务池，将不同优先级的任务分配至不同任务池
3.3 计算能力调度算法(Capacity Scheduling)
计算能力调度算法最先由Yahoo 提出并应用在其分布式计算集群中，其调度策略内容为：数据中心根据内部可用资源的性能参数，在系统接收到用户发出服务请求并提交应用任务后，数据中心通过多个JobQueue 队列管理任务，并给每个JobQueue 队列一定的资源参数配比，用于执行在该队列内的任务[9]。一旦出现某个JobQueue
4 智能化的任务调度算法
在云计算环境中，任务调
60
Broad Angle for Technology技术广角
度是一种组合优化类的N P 完全问题，之前所述的传统调度策略和Hadoop 中调度策略大都存在不足之处，近年来许多学者根据启发式智能算法加以改进，在解决云计算任务调度问题时，取得了较好的 效果。
传、变异和交叉等操作，在已有解的基础上不断进化，实现向更优解的进化，在经过多次迭代后，将最优个体的基因解码即可得到问题的解，遗传算法现已在不同的领域得到广泛应用，并取得良好的解决效果[14]。
黄璐[15]等人提出的任务调度改进遗传算法中将遗传算法与模拟退火算法相结合，通过模拟退火算法中的Metropolis 准则，确立新个体的准入机制，在不丢失遗传特性的前提下，保证有足够数量的新个体加入，使遗传算法的种群实现逐步进化，搜索最优任务调度方案。段卫军[16]等人提出基于遗传算法和蚁群算法融合的QoS 约束任务调度策略，利用任务的预测完成时间和成本耗费定义适应度函数，通过遗传算子全局搜索最优解，融合蚁群算子提高解的精确度。李建锋[17]等人在提出利用遗传算法的任务调度策略中，为保证用户群的总体服务质量与满意度，综合考虑全部任务的执行时间和子任务平均完成时间两项标准，建立双象适应度函数，从而提升云计算任务调度的任务执行效率，降低总体任务执行时间，并缩短子任务的平均完成时间。
4.1 蚁群算法
蚁群算法(Ant Colony Optimization, A C O ) 最早由意大利学者M.Dorigo 、V.Mniezzo 和A.Colorni 于20世纪90年代初提出。根据自然环境中蚁类觅食过程中依据信息素的方式搜寻最短路径，在工程应用的多个领域取得了良好的解决效果[10]。
针对当前蚁群算法中重要参数大都根据大量重复实验来确定，所得参数组合可能不是最优，而且不能适应云计算任务调度的动态性，胡伟华等人[11]提出了用粒子群优化算法来求解蚁群算法参数最优组合的改进算法。该算法能够灵活根据任务和计算资源属性确定蚁群算法参数配置，从而能够在云计算系统中保持良好系统负载均衡，并满足用户的服务要求，符合用户服务等级协议。张雨[12]提出在云计算环境的任务调度策略中将蚁群算法与遗传算法相结合，由于蚁群算法在初期求解速度慢，而遗传算法可以弥补这方面不足。任务调度初期利用遗传算法将任务与资源编码，并以任务平均完成时间作为适应度函数评判标准。根据遗传算法的解进行蚁群算法的初始化，可以较为迅速的求得任务调度方案。王登科[13]等人提出一种基于粒子群优化和蚁群优化的任务调度算法，该算法首先利用粒子群优化算法迅速求得初始解，然后根据该调度结果生成蚁群算法的初始信息素分布，最后利用蚁群算法得到任务调度的最优解。实验表明，该算法具有较好的实时性和寻优能力，是一种有效的调度算法。
4.3 粒子群算法
粒子群算法(Particle Swarm Optimization，PSO) 是由Kennedy 和Eberhart 最先提出，因受到自然界中群体性物种(如鸟群、鱼群) 的聚集、迁徙等行为的启发，而用于全局搜索的一种启发式优化算法，并在工程研究与应用领域取得良好的解决效果[18]。粒子群算法采用速度—位置搜索模型，每个粒子代表解空间的一个候选解，解的优劣程度由适应度函数决定。该算法保留了种群的全局搜索策略，但其采用的速度—位置模型操作简单，避免了复杂的遗传操作，它特有的记忆使其可以跟踪当前整个种群的最优粒子。传统PSO 算法在求解云计算任务调度这个大规模的、实时的问题上有着天然的优势。
封良良[19]等人根据经典粒子群算法提出改进方案解决云计算任务调度问题，采用双适应度函数的方案，综合考虑全部任务的执行时间和子任务平均完成时间两
4.2 遗传算法
遗传算法(Genetic Algorithm)模仿自然界生物以遗传和变异为两项重要方式不断演化，提出一种启发式智能化算法。在计算模型中建立仿照基因的模型，通过遗
61
技术广角 Broad Angle for Technology
项标准，以提升算法复杂性为代价提升云计算任务调度的任务执行效率，降低总体任务执行时间，并缩短子任务的平均完成时间。沈恺涛[20]等人提出一种改进粒子群编码方式的任务调度策略，在原有粒子算法的基础上对局部粒子群和全局粒子群采用自然数编码，将局部最优解与全局最优解有效结合，使整个粒子群高效地搜寻任务调度最佳方案，实验证明该算法在实际应用中能够取得较好的任务调度效果。李静梅[21]等人提出一种粒子群优化的异构多处理器任务调度算法，可同时适用于云计算、分布式计算、网格计算等多种异构多处理器的计算模式中，该算法将模拟退火算法与粒子群算法相结合，避免因粒子群算法收敛过快而陷入局部最优解，能够在迭代过程中保持对最优解的逐步稳定递进。同时利用整数矩阵对种群粒子编码，重新定义粒子更新模式，提高异构处理器任务执行的效率和整体服务质量，具有较好的借鉴意义。
[9]
计算机系,2013
[5] Braun TD, Siegel HJ, Beck N. A comparison of eleven
static heristics for mapping a class of independent tasks onto heterogenous distributed computing systems[J]. Journal of Parallel and Distributed Computing. 2001,61(1): 810-837
[6] 郑爱卿. 基于执行时间方差的元任务网格调度算法研究[D].
北京:北京交通大学计算机学院,2008
[7] 史恒亮. 云计算任务调度研究[D].南京:南京理工大学计算
机系,2012
[8] Isard M, Prabhakaran V, Currey J. Fair scheduling for
distributed computing clusters[C]//Proceedings of the 22nd ACMSIGOPS Symposium on Operating Systems Principles, New York, 2009:261-276
鸣. 云计算下计算能力调度算法的研究和改进[D].太原:太原理工大学计算机系,2012
[10] Dorigo M, Caro G. Ant colony optimization: a new
metaheutistic[C]//The 1999 Congress on Evolutionary Computation. Washington: IEEE Press,1999:1470-1477[11] 胡伟华. 基于改进蚁群算法的云计算任务调度策略研究[D].
5 结束语
本文对云计算环境中的任务调度的概念、特点和调度策略评价标准进行分析与论述，总结当前云计算任务调度策略的研究成果与应用现状，并对多种任务调度算法的实现机制和性能表现进行分析与比较。由于云计算需要考虑用户、网络性能、资源池计算能力等多方面因素，其目标也不仅仅需解决一方面问题；因此，云计算任务调度还有许多工作需进一步深入研究。
杭州:杭州电子科技大学,2013:21-35
[12] 张雨, 李芳, 周涛. 云计算环境下基于遗传蚁群算法的任务调
度研究[J].计算机工程与应用,2014(6):51-55
[13] 王登科. 基于粒子群优化与蚁群优化的云计算任务调度算
法[J].计算机应用与软件,2013,30(1):290-293
[14] 王小平, 曹立明. 遗传算法:理论、应用于软件实现[M].西安:
西安交通大学出版社,2002:10-50.
[15] 黄璐. 基于遗传算法的云计算任务调度算法研究[D].厦门:
厦门大学,2014:21-30
[16] 段卫军, 付学良, 王芳. 云计算环境下融合遗传算法和蚁群算
法QoS 约束任务调度[J].计算机应用,2014,34(S2):66－69
参考文献
[1] Wikipedia. Utility computing.[EB/OL].(2010-07-12)
[2015-08-12].http: //en.Wikipedia.org/wiki/Utility_computing
[2] 刘鹏. 云计算[M].北京:电子工业出版社,2007:34-35[3] Solanki SV, Gour BMA, Mahajan R. An overview of
different job scheduling heuristics strategies for cloud computing environment [C]//Proceedings of ICETT, 2011:7-11
[4] 吴皓. 云环境下任务调度算法研究[D].南京:南京邮电大学
[17] 李建锋, 彭舰. 云计算环境下基于改进遗传算法的任务调度
算法[J].计算机应用,2013,31(1):184-186
[18] Bratton D, Kenndey J. Defining a standard for particle
swarm optimization[C]//IEEE Swarm Intelligence Symposium. Honolulu,2007:35-46
[19] 封良良, 张陶, 贾振红. 云计算环境下基于粒子群的任务调度
算法研究[J].计算机工程,2013,39(5):183-186
[20] 沈恺涛, 胡德敏. 基于云计算和改进离散粒子群的任务调度
研究[J].计算机测量与控制,2012,20(11):3070-3072 [21] 李静梅, 张博. 一种粒子群优化的异构多处理器任务调度算
法[J].小型微型计算机系统,2013,34(5):1154-1157
62
Broad Angle for Technology技术广角
作者简历
王海涛
博士，副教授，主要研究方向为无线自组织网络、网络管理与QoS 保障。
张焕青
硕士研究生，主要研究方向为计算机网络、云计算。
肖世平
西安通信学院指挥控制系副主任，主要研究方向为指挥信息系统。
张学平
博士，教授，主要研究方向为计算机网络信息管理。
闫力
硕士研究生，主要研究方向为计算机网络、情景感知技术。
Scheduling Strategy Based on Cloud Computing
Wang Haitao1
Zhang Huanqing1
1 PLA University of Science and Technology, Nanjing 210007,China
Xiao Shiping2
2 Xi’an Communication College, Xi’an 710006, China
Zhang Xueping1Yan Li1
Abstract It is a research hotspot to occupy as little cloud resource as possible to achieve massive task for efficient scheduling and rational allocation of cloud resources under the precondition for user QoS. This paper discusses the concept, features and objectives of task scheduling in the cloud computing environment and summarizes its research status. It analyzes and compares the realizaiton mechanisms and performance index of traditional tasks scheduling algorithm, task scheduling algorithm of Hadoop and intelligent scheduling algorithm. The analysis result shows that intelligent scheduling algorithms have better adaptability and performance, so they should be studied extensively in the future.Keywords Big Data; Cloud Computing; Task Scheduling; Scheduling Algorithm63