云计算环境下任务调度研究综述

申倩等

摘 要：云计算是一种新的商业计算模型。它将计算任务分布在大量计算机构成的资源池上，使各种应用系统能够根据需要获取计算资源、数据资源、存储资源和应用服务资源等。大数据时代，云计算的另一个特点是它将处理大规模的任务。如何实现在满足用户QoS的前提条件下，对海量任务进行高效调度并对大量云资源进行合理的分配，使得云任务占用尽量少的云资源是云计算领域的一个研究热点。主要论述了云计算环境下任务调度的目标和新特性，分析总结了云计算任务调度的研究现状并以调度目标为侧重点归纳总结了四类调度策略，即侧重性能的调度、侧重服务质量的调度、侧重经济原则的调度和侧重能耗优化的调度，给出了云任务调度的研究展望，为下一步更深入的研究指出方向。

关键词：云计算；任务调度；能耗优化；用户行为

中图分类号：TP3 文献标识号：A 文章编号：2095-2163（2014）06-

Abstract： Cloud computing is a new business computing model. It distributed computing tasks in a large resource pool consisting of many computers， make a variety of applications can obtain computing resources， data resources， storage resources and application services and other resources as needed. Big Data era， another characteristic of cloud computing is that it will deal with a massive task. How to achieve massive task for efficient scheduling and rational allocation of cloud resources under the precondition user QoS， making the task of occupying as little cloud computing resources is a research hotspot. The paper discusses the objectives and new features of task scheduling under the cloud computing environment ，analyzes and summarizes the research status of cloud computing task scheduling and summarizes four scheduling policy according to schedule objectives. Simultaneously， the paper gives prospect of cloud task scheduling for the next direction of more in-depth study noted.

Key words： Cloud Computing； Task Scheduling； Energy Optimization； User Behavior

0 引 言

云计算是近年来广受关注的研究热点之一。云计算是一个较为抽象的概念，最初起源于电话通讯行业。20世纪，电话已经普及、并演变为一种公共事业，借助公共电话网，两个电话可以实现直接通讯。但是若要在两个用户之间建立一条私密的、专用通道，则必须架设一条新的物理专线，这将导致昂贵的费用开销。90年代，VPN（虚拟专用网络）技术出现，凭其即可通过公用网络随时为两个用户建立专线连接，这就大大节省了通讯的开支。为了描述这种可以为个人提供专用资源，而且又可以随时使用的网络服务，“云”概念应运而生了。“计算”，指的是计算机的计算能力，其速度取决于计算机的硬件配置。1963年，斯坦福大学的约翰·麦卡锡教授就预见说“计算的能力，有一天会被组织起来，成为一种公共资源和公共事业。”[1]；也就是说，将计算的能力放在网络上，而不是个人电脑上。所有的硬件计算能力、

存储能力、软件执行能力，全部都由互联网来提供。1997年，南加州大学的一位印度裔教授切诺柏将“云”

与“计算”组合成一个新单词，从而正式提出了“云计算”概念。

云的运营商把计算能力作为一种资源，集中在一起组成资源池，再通过网络，配送给有需要的客户。而且，服务商的供应量将随客户的需求量高低而进行调整与变动。客户购买预制服务后就不需要再购买昂贵的软件和硬件。这对于小型创业公司而言，在相当程度上减少了因购买服务器和软件带来的开销，只要通过租用就可以获得在网上超高强配置的软硬件能力。也就是说，正如自来水管道供水、电力网供电一样，云计算亦将计算从有形的产品变成了无形的服务。

云计算提供的资源服务从具体应用角度可分为三个层次，具体来说就是基础设施即服务（IaaS）、平台即服务（PaaS）和软件即服务（SaaS）。这三个层次各自侧重于不同的应用，但是却包含着相同的问题，即资源、任务调度问题。调度问题直接关系到云服务的稳定性、用户的满意度、资源的利用率以及运营成本等。因此，对云计算的调度问题展开研究具有非常重要的现实意义及理论价值。

1云计算环境下的任务调度

1.1 云环境下用户获取服务的流程

云计算系统是由海量的商用机和高性能服务器组成，其中的数据中心向用户分配虚拟机来运行其所提交的任务，而任务调度则决定虚拟机的分配数量及任务执行次序，如图1所示。

1.2 云环境下任务调度的新特性

云计算是在网格计算、并行计算、集群计算的基础上发展起来的，因此他们的任务调度策略具有很大的相似性。但是，与网格计算等相比，云计算还表现了一些新的专有特性，可具体描述为：

（1） 云资源的差异较大，云环境下的资源可能是高性能的服务器、普通PC机，或者是各种硬件设备上的虚拟环境。这就使得资源的计算能力和存储能力必然具有明显差异。

（2） 用户对云资源的需求具有多样性和偏好性，因此需要考虑更加复杂的QoS约束，最大限度地满足用户的QoS要求。

（3） 云计算环境下的有效调度需要保证云计算服务商提供的云资源能够得到充分利用并获得最大收益。传统的调度策略往往却只是考虑如何满足各用户的QoS要求，而很少考虑资源服务商的经济效益。

（4） 用户需求的多样性和应用类型的复杂性使得云计算系统中能源成本成为一个重点关联因素。云计算环境的商业化特点决定了必须引入能耗开销等因素来建立问题模型，并藉此全面研究相应的调度策略。

1.3 云环境下任务调度的目标

云环境下，任务调度的目标就是对用户提交的所有任务实现最优调度，并尽量提高云计算系统的总体吞吐率。具体的目标包括：服务质量（Quality of Service， QoS）、负载均衡、经济原则和节能减排等。具体分析如下：

（1） QoS。云环境下的任务调度系统必须满足用户的QoS。一方面，要根据应用的特征提高资源的发现率和准确性系数，保证用户服务的性能QoS；另一方面，则需针对用户的状态变迁，动态进行资源选择以及重定向，满足用户的经济QoS，有效地提高用户满意度。

（2） 负载均衡。由于云环境下计算资源是由大量计算机节点组成，复杂且异构，这就使得负载均衡的实现具有相当难度。

（3） 经济效益。由于云计算是一种新型的商业模式，其中的经济效益必然成为着重关注的调度指标。该指标的切实完善的真正实现将直接关系着云计算这一面向普适商业应用计算模式的有效运营周期。

（4） 节能减排。云计算是超大规模的计算，每个数据中心的电力消耗均堪称巨大，在提倡绿色计算的背景环境下，云计算也必须将节能减排作为一个重要的追求目标。

2 云环境下任务调度技术研究现状

2.1侧重性能的调度

作为任务调度研究的核心热点，侧重性能的任务调度的最终目标就是性能，例如最优跨度，任务最早完成时间等。目前使用比较广泛的算法包括Min-Min算法、Max-Min算法、遗传算法、贪心算法、蚁群算法和模拟退火算法等。

具体来说，IBM公司的云计算平台采用的就是以性能为中心的调度策略。而且，李建峰等人[2]基于MapReduce模型，提出了一种具有双适应度的遗传算法（DFGA），该算法不仅能够使总任务的完成时间最短还能使任务的平均完成时间较短；汤小春等人[3]则提出了一种基于元区间的最佳分配决策算法，并取得了良好效果；还有，华夏渝等人[4]提出了一种基于蚁群优化的资源分配算法，该算法适应于具有最小响应时间和最好服务质量为其指标要求的任务调度。另外，周文俊等人[5]针对静态资源调度中只考虑任务完成时间最小化问题，提出了一种基于预测的蚁群算法来满足云环境下资源的动态分配。

2.2侧重服务质量的调度

云计算是一种商业模型，其中的用户QoS不仅关系到用户的实际体验，而且将实际影响着云计算的良性发展。因此，基于QoS的任务调度算法研究也获得蓬勃发展。一般情况下，算法研发框架除了要考虑最小完成时间或是最优跨度，还有考虑服务质量等问题。

基于QoS的研究，目前已推出丰硕成果。文献[6]提出了一种基于模糊聚类的云任务调度算法，该算法对资源进行模糊聚类，更好地反映了任务的需求。He等人[7]对Min-Min算法进行了改进，即根据用户是否还有QoS需求而对系统的吞吐率实现了优化。Chanhan等人[8]又根据加权平均执行时间进行资源选择，通过将网络带宽作为QoS属性，而将任务分为高QoS与低QoS需求两类，并且对于高QoS的任务将进行优先调度。再有阿尔卡特朗讯贝尔实验室的Hao等人[9]提出了一个网络虚拟化架构，用来实现云服务的动态需求和迁移，而不影响服务性能，由此提高了云服务质量。另外，孙大为等人[10]则提出一种基于免疫克隆的偏好多维 QoS云计算调度优化算法，结合免疫克隆算法，对客户应用的偏好和多维 QoS中的用户效用进行量化，同时给出了多维 QoS优化的目标函数，以此满足客户的经济 QoS和性能 QoS。

2.3侧重经济原则的调度

除服务质量外，云计算的商业运行模式则使得经济因素也成为任务调度的重要指标之一。惠普的云数据中心采用的就是成本优先调度策略。邓见光等人[11]，在满足QoS的前提条件下，从云服务提供商的角度出发，给出了一种基于成本的云任务调度策略。Buyya等人[12]进而提出了面向市场的云计算以及面向市场的云计算构架。葛新等人[13]再次提出了一种基于计算强度的调度策略，并且具有低成本的特点。该策略的主要思想是将计算量大的任务分配给计算能力强的集群调度，而将计算量小的任务则分配给计算能力弱的集群调度。另外，对于那些经济效益要求高而时间需求相对宽松的应用，即可选择计算能力弱的集群调度；但针对有严格时间要求的应用将可申请计算能力强的集群调度，如此即能达到降低成本的目的。

2.4侧重能耗优化的调度

在提倡绿色计算的浪潮下，已有更多的学者正致力研究侧重于能耗优化的调度算法，并取得了可观的成就。

文献[14]中设计了基于动态定价策略的数据中心能耗成本优化方案，为研究基于能耗优化的任务调度提供了基础。该调度算法可以根据动态的服务价格进行调度，达到优化能耗的目的。文献[15]中则提出了两种具有能量感知的任务调度算法，分别利用能耗时间归一及能耗时间来定义适应度函数，实验结果表明，与单独考虑能耗或是时间相比，这两种算法能够有效降低能耗并缩短任务执行时间。曹洁等人[16]也提出了两种满足并行任务截止时间要求和并行任务执行能耗要求的调度方法Ssef和Egsa。实验结果表明，该算法在保证并行任务截止完成时间要求的前提下能够有效降低并行任务的能源消耗，从而降低了云计算系统的能耗开销。

3 云环境下任务调度技术的研究展望

目前，根据云环境任务调度技术的研究进程和现存问题，给出了建议和设想，期望对任务调度的进一步研究提供有益的借鉴。

3.1 基于用户行为特征的调度策略研究

云计算环境中，用户提交的任务数目将是海量，那么如何在资源有限的情况下，对海量任务进行有效调度，同时资源也得到有效利用即已成为研究重点。针对此一问题，可以从用户的行为特征出发，通过统计用户的行为习惯和预期的完成时间，来合理安排任务的科学调度，由此而提高资源利用率和用户满意度。

另一方面，当用户删除、撤销任务时，调度系统将相应地采取一定的调度策略来适应这种变化，从而避免了资源不必要的浪费。

3.2 基于云任务多维属性的节能的任务调度策略

绿色计算提出后，云环境下节能的任务调度的研究随即也成为热点问题。已有的大部分研究均以数据中心的节能为其优化目的，但迄今仍然少有根据任务的多维属性来进行任务调度从而达到节能效果的。云任务是海量的、差异性大的、偏好性强的，针对不同的任务需求给出相应的资源分配方案，将能有效降低任务能耗。

4 结束语

云环境下的资源具有动态多变、按需提供、按量付费、任务差异大、任务偏好性强等特点。现有的调度算法并不能完全满足云任务调度要求。因此，云任务的调度是云计算领域的研究热点之一。本文介绍了云任务调度的新特性及目标，分析了国内外云任务调度的研究现状。尽管这些研究取得了颇丰的进展，但也存在着一定的不足。很多工作仍需进一步展开深度的探讨与研究。

参考文献：

[1]Wikipedia.Utility computing.[2010-07-12].http：//en.wikipedia.org/wiki/Utility_computing.

[2] 李建锋，彭舰.云计算环境下基于改进遗传算法的任务调度算法[J].计算机应用，2011，31（1）：184-186.

[3] 汤小春，刘健.基于元区间的云计算基础设施服务的资源分配算研究[J].计算机工程与应用，2010，46（34）：237-241.

[4] 华夏渝，郑俊，胡文心.基于云计算环境的蚁群优化计算资源分配算法[J].华东师范大学学报：自然科学版，2010，1（1）：127-134.

[5] 周文俊，曹键.基于预测及蚁群算法的云计算资源调度策略.计算机仿真[J].计算机仿真，2012（9）： 239-242+246.

[6] 李文娟，张启飞，平玲娣，潘雪增.基于模糊聚类的云任务调度算法[J].通信学报，2012，33（3）： 146-154.

[7] HE Xiao-shan，SUM Xian-he，Von LASEEWSKI G.QoS guided min-min heuristic for grid task scheduling[J].Journal of Computer Science and Technology ，2003，18（4）：442-451.

[8] CHANHAN S S，JOSHI R C.A heuristic for QoS based independent task scheduling in grid environment[C]//Proc of International Conference on Industrial and Information Systems，2010：102-106.

[9] HAO Fang，LAKSHMAN T V，MUKHERJEE.Enhancing dynamic cloud-based services using network vitualization[J].Computer Communication Review，2010，40（1）：67-74.

[10] 孙大为，常桂然，李凤云.一种基于免疫克隆的偏好多维QoS云资源调度优化算法[J].电子学报，2011，39（8）：1824-1830.

[11] 邓见光，赵跃龙，袁华强，等. 一种成本驱动的云计算任务调度策略[J]. 江苏大学学报： 自然科学版，2014，35（2）：214-219.

[12] BUYYA R，YEO C S，VENUGOPAL S. Market-Oriented Cloud Computing：Vision，Hype，and Reality for Delivering IT Services as Computing Utilities[C]//Proc of the 10th IEEE International Conference on High Performance Computing and Communications.2008：5-13.

[13] 葛新，陈华平，杜冰，等.基于云计算集群扩展中的调度策略研究[J].计算机应用研究，2011，28（3）： 995-997+100.

[14] 王魏，罗军舟，宋爱波.基于动态定价策略的数据中心能耗成本优化[J].计算机学报，2013，36（3）：599-612.

[15] 英昌甜，于炯，杨兴耀.云计算环境下能量感知的任务调度算法[J].微电子学与计算机，2012，29（5）：188-192.

[16] 曹洁，曾国荪.云环境下计算资源动态能耗感知的并行任务调度方法[J].计算机科学，2013，40（10）：39-44.