研究云计算调度问题的实际应用价值

云计算是一种以商业为主要推动力的计算模型和服务模式，从计算资源提供的角度来看，它是将计算资源作为一种服务通过网络提供给用户的计算模式，用户以便捷和按需扩展的方式来使用计算资源（包括数据、软件、硬件和网络带宽等），无须了解它提供过程的细节。

云计算提供的资源服务从具体应用角度分为三个层次，即软件即服务（SaaS)、平台即服务（PaaS)和基础设施即服务（IaaS)。这三个层次分别侧重于不同的应用，但是它们包含着相同的问题，即资源、任务调度问题。如Amazon的弹性云需要通过合理的调度保证各虚拟机的利用率；八百客的在线ERP系统更需要合理的任务调度，才能提高用户的满意度和忠诚度。调度问题是云计算中的一个重要问题，直接关系到云服务的稳定性、资源的使用效率、用户的满意程度和运营成本。

因此，对云计算调度问题的研究无论从理论技术本身还是实际应用价值方面都有非常重要的意义。

1云计算调度概述

虽然可以将云计算看成是分布式处理、并行处理和网格计算的发展和商业实现，但是云计算与它们还是有很大的不同，如资源聚合与共享方式、任务提交方式等，故云计算调度也有其自身特点。

1.1云计算调度目标

云计算调度的目标就是对用户提交的任务实现最优调度，并设法提高云计算系统的总体吞吐率。具体的目标包括最优跨度（optimalmakespan)、月艮务质量（qualityofservice，QoS)、负载均衡（loadbalancing)、经济原则（economicprinciples)等。

a)最优跨度。跨度是调度中很重要且常见的目标，用户都希望自己的任务能在最短时间内完成。实现最优跨度是用户和云计算的共同目标。

b)QoS。云计算调度系统必须保障用户的QoS。一方面需要根据应用特征提高资源的发现效率和准确性，保证用户服务的性能QoS；另一方面针对用户的状态变迁，动态进行资源选择和重定向，满足用户的经济QoS，有效地提高用户满意度。因此这一目标是用户的保障也是云计算能长久持续发展的关键。

c)负载均衡。由于云计算平台中的计算机数量非常庞大，组成复杂，加上不同云计算平台的异构性，使得目前云计算中负载均衡的实现成为一个具有挑战性的问题。

d)经济原则。云计算的超大规模及其商业运营模式，使得其经济因素成为要重点考虑的调度指标。市场经济驱动的资源使用者和资源提供者互惠互利，才能使云计算这一面向普适商业应用的计算模式长久地发展下去。

1.2云计算中的资源调度特点

云计算调度与其他计算模式中的调度相比有其自身特点。

a)资源环境。云环境下资源的配置差异较大，可能是高性能集群、性能较高的服务器、普通PC机或是各种硬件资源上的虚拟机环境，所以资源的计算能力、存储能力、带宽等因素具有较大差异。

b)云计算调度是面向异构平台、大规模、非集中式的，因此云计算调度必须面向异构平台，并在这些平台上以分布、并行的方式进行资源任务的管理与调度。

c)约束条件。在传统的分布式计算中，系统性能最优即是最终目标。而在云环境中，云服务商提供资源/服务，用户按需付费。因此，云环境中的调度问题必须考虑成本约束，如任务截止完成时间、用户支付费用及运营商提供成本等因素。

d)优化目标。云环境中不仅注重资源利用率及系统性能的提高，而且要保证用户的QoS需求，尽可能地实现资源供给与消费的双赢局面。

e)可扩展性和动态适应性。在云计算规模不断扩大、应用不断增长的情况下，云调度必须具有可扩展性，才不至于降低云计算系统性能。另外云资源的动态性是很明显的，因此云调度必须适应这种动态性。

2云计算调度问题研究现状

2.1以性能为中心的调度

以性能为中心一直是调度研究的重点，这类调度是以调度性能作为最终目标，如任务最早完成时间、最优跨度等。目前研究和使用比较广泛的算法包括Min-Min算法、Max-Min算法、遗传算法（GA)、蚁群算法、贪婪算法和模拟退火算法等。

IBM云计算平台采用的是以性能优先的调度策略0。李建峰等人3基于MapReduce模型，提出了一种具有双适应度的遗传算法（DFGA)，注重作业的平均完成时间；汤小春等人4提出了一种基于元区间的分配决策算法；华夏渝等人5提出一种基于蚁群优化的资源分配算法。

另外虚拟资源的调度是目前云计算调度的研究热点，如Intel公司6研究了虚拟资源间的竞争关系，对虚拟机间由于竞争关系所带来的性能下降进行了建模，并以此为基础提出了预测虚拟资源竞争的模型。国内的学者如Kong等人提出一种在虚拟化的数据中心中基于模糊预测的有效的任务调度方法，该方法以时间和可靠性为目标，建立了以模糊规则为预测的模型，提出基于模糊规则预测的调度算法。孙瑞锋等人提出了一种租借理论与动态多级资源池相结合的调度策略，减少资源空闲时间，提高了资源利用率。而Song等人则提出了一种在虚拟化的数据中心中以多层调度器为核心的调度模型。Freeman等人提出一种方法将VM提供模型集成到现有的资源管理框架中，采用两级调度的方法将对VM的管理集成到批调度器中，向用户提供尽可能多的调度服务，但目前不支持虚拟资源的预定服务。传统的调度器对短期租赁请求调度时，要完成严格的预定资源服务租赁是很困难的。So-tomayor等人提出使用虚拟机的无缝挂起和恢复计算的能力来解决这个问题，即对于可用性要求不太严格的批量计算任务，调度器先挂起当前计算任务，然后去完成具有严格可用性要求的作业，如预定资源的作业。

2.2以服务质量为中心的调度

由于云计算的商业应用，保障用户的QoS是十分必要的，它关系到用户使用云计算的体验，是云计算能否持久发展的关键。因此基于QoS的调度往往不仅要以最小完成时间或最优跨度为目标，还需要考虑到服务质量等问题。

目前已有很多基于QoS的研究，He等人对Min-Min算法进行了改进，根据用户是否有QoS需求进行系统吞吐率的优化。Chanhan等人根据加权平均执行时间进行资源选择，将网带宽作为QoS属性，把任务分为高QoS与低QoS需求两种类别，对于高QoS的任务优先调度，与文献思想相近。Xu等人研究了针对云计算中多个工作流的多QoS调度策略，对于不同的用户考虑不同的QoS需求，提出一种云环境下的多作业流多QoS约束的调度策略。阿尔卡特朗讯贝尔实验室的Hao等人提出了一个网络虚拟化架构，用来实现云服务的动态变化和迁移而不影响服务性能，该机制采用集中控制的分布式架构，使用Openflow组件构建，实现了虚拟机的无缝迁移，提高了云服务质量。孙大为等人提出一种基于免疫克隆的偏好多维QoS云计算调度优化算法，结合免疫克隆算法，对用户应用偏好和多维QoS中的用户效用进行量化，给出了多维QoS优化的目标函数，以满足用户的性能QoS和经济QoS。

2.3以经济原则为中心的调度

云计算的超大规模及其商业运营模式，使得其经济因素成为重点考虑的调度指标。HP云数据中心采用的就是成本优先的策略。

Buyya等人提出了面向市场的云计算的概念，以及面向市场的云计算的构架。Deelman等人分析了云计算解决大规模数据处理应用的成本问题，没有考虑启动、停止虚拟机消耗的成本。Assuncao等人分析了使用云计算扩展本地集群的成本问题，考虑了虚拟机启动时消耗的成本，但作了一个假设：云中的资源可以按秒为单位进行申请、配置，测试运行环境的时间和成本不予考虑。代尔夫特理工大学的Yigitbasi等人00设计并实现了C-Meter架构，用来分析云计算的性能。该架构采用了很多评价性能指标，如获取和释放虚拟计算资源的系统开销，以及其他的虚拟化和网络开销等。美国Sandia国家实验室的Brandt等人研究了在云计算环境下实现高性能计算（HPC)的问题，云计算环境中有大规模的资源，可以为高性能计算提供便利条件，并且节省投资。由于HPC对可靠性有着严格的要求，因此需要对云计算资源进行有效的监控和管理。澳大利亚墨尔本大学的Buyya等人提出了基于市场的资源定位的云计算架构，并给出了基于市场的资源管理策略，以支持服务级协商（SLA)的资源定位。葛新等人提出了一种基于计算强度的调度策略，即计算量大的任务往计算能力强的集群调度，计算量小的任务往计算能力弱的集群调度。对于追求经济效益高而对时间需求不敏感的应用，可选择申请计算能力较弱的云环境；有严格时间约束的，可以申请计算能力较强的云资源，以此达到降低成本的目的。尹红军等人[24提出了一种实时满足运营商资源最高效益的动态调度方法，即每次新加入用户时，新加入的用户资源和先前分配的资源一起重新在所有服务器上规划，进行全局虚拟机调度，迁移那些能给系统带来足够效益的部分虚拟机，完成全局最优的虚拟机部署。该方法对云中资源进行了合理的高效益规划，可节约运营商成本，提高云中资源利用率，并降低能耗。

上述分类并非完全囊括所有分类方式，也并非完全正交，如基于负载均衡的调度可归结到以性能为中心的调度，但它也涉及经济原则。而事实上很多研究是满足多目标的，既满足性能需求又考虑用户QoS，同时又兼顾经济指标，如Amazon云计算调度策略结合了成本优先、满足不同用户需求、负载均衡和高可靠性等策略[25]。Prodan等人[26提出的基于CDA(contin?uousdoubleauction)模型的资源调度方法，以达到用户为中心的指标（完成时间、预算花费等）和资源提供商为中心的指标(资源利用率、收益和吞吐量等）的平衡。Mezmaz等人[27提出的多目标混合遗传算法，采用DVS(dynamicvoltagescaling)的方法来减少能量消耗，同时兼顾调度完成时间。

3典型调度方法及系统

目前，云计算调度管理是云服务商及云计算研究的重点和难点。各大云计算厂商根据自己已有架构搭建云平台，并根据自己资源的特点采用不同的调度策略。其中较为着名的是Amazon云计算平台、IBM蓝云平台及Google云计算平台。另外，OpenNebula和Eucalyptus也是比较有影响的云计算平台。

1)Amazon云计算平台Amazon[2是目前公认推广云计算应用最为成功的厂家之一，它成功推出了EC2、SQS、S3和SimpleDB等近十种云服务。它的调度策略基本上结合了经济成本和性能优先的调度方式。首先将其提供的计算资源分为八类，并说明其资源配置及每小时费用，为实现成本优先，采用了不同地域成本不同的收费调度分配策略，供用户选择，而性能方面主要由用户选择预先配置好的虚拟服务器；然后用户根据自己业务需求提出租用请求（资源种类、数量和时间）并在线提交；最后调度算法根据用户特征和使用资源的信息找到合适的资源，并将资源信息反馈给用户，以供用户使用。

2)IBM蓝云专用服务器IBM云计算平台总体采用的是性能优先的策略。采用虚拟机监控代理进行资源分配28。用虚拟机实现计算平台与物理节点的映射，并随着物理节点性能状态的变化进行动态迁移，以满足任务需求或负载均衡。将资源监控和管理以及任务分配和调度策略加入到虚拟机中，能大大简化云调度过程。

IBM云平台的资源分配与任务调度具体采用专用的资源监控代理和作业调度器来管理系统资源调度。如IBM蓝云采用Tivoll系列产品来完成云环境的资源监测、分配、作业调度和系统负载均衡控制。这种方式体现了目前云计算的通用管理模式，即虚拟化技术的支持，能简化调度过程。

3)Google云计算平台的MapReduce调度Google提出的MapReduce编程模式，是一个用于大规模数据处理的分布式计算模型，同时也是一种高效的任务调度模型。

MapReduce主要采用集中式调度模式，因此只有一个主调度器。所有的调度请求都必须提交给主调度器，由主调度器决定如何分配资源、响应用户请求、管理资源等工作。调度模型的整个计算过程由master、worker和user三种线程完成[29]。其中master线程相当于整个集中式系统的中央调度器，完成数据分割、任务调度和均衡控制等；worker线程接收来自master线程的任务，从而进行具体的任务执行工作，如数据处理和运算等，并把数据传送至相应存储位置；user线程是用户线程。

事实上不仅是Google，Yahoo和IBM等很多云平台也都在基础架构上采用了MapReduce的设计思想。

4)Hadoop适用于海量信息处理的Hadoop是一个在集群上运行大型数据库处理应用程序的开放式源代码框架，它支持通过MapReduce来创建并执行应用程序。

Hadoop平台采用的是主从式调度模式，由一个称为Job-packer的主节点控制整个系统的作业调度。主节点采用先来先服务（FIFO)调度算法。其余节点为TaskTracker，在它们空闲时向JobTracker请求分配任务。从节点采用贪婪算法，默认的调度算法总是试图找到距离客户数据最近的从节点以便大的数据量不必通过远距离的网络传输；若从节点忙，任务可被分配至其他节点。

调度作为Hadoop平台的核心技术之一，目前尚处于基础阶段，特别是现有的作业调度算法均存在着一些不足之处。比如FIFO调度算法在一个生产型作业之后，它将长期使用系统资源，在这个作业提交之后的交互型作业由于迟迟得不到系统资源而不能及时处理，从而影响系统的交互能力和用户的使用体验。

5)OpenNebulaOpenNebula3031]是一个开源的虚拟架构引擎，它主要用来在物理资源池上部署、监控和管理虚拟机的运行。它采用层次式调度模式，其中ONED是OpenNebula的核心服务进程，包括虚拟化管理模块和任务调度模块。

芝加哥大学的Sotomayor等人32以OpenNebula为平台，提出了名为Haizea的虚拟资源租约管理器，虚拟资源按照不同的策略以租约的形式提供给用户。OpenNebula利用AmazonEC2接口结合Haizea实现了混合云的调度与管理工作。

6)EucalyptusEucalyptus34355是由美国加利福尼亚大学开发的一个开源软件基础架构。它采用的是层次式调度模式，其中CM(cloudmanager)中的资源服务层主要用于完成资源分配和监控。

对于其资源调度问题，目前是通过监测负载平衡日志和监测响应时间来进行。资源调度算法读取实时的负载平衡器日志，并计算每个虚拟机每60s在集群中的平均响应时间。当监测到虚拟机的平均响应时间超过需要的反应时间，它将开启一个或多个新虚拟机来满足需求，相应地也可在系统负载低时减少虚拟机。

4问题分析与展望

通过以上调研分析发现，与传统调度的研究重点不同，现有关于云调度的研究侧重虚拟资源调度，这是因为云资源是以虚拟资源为核心的。由于云计算的商业应用模式，现在的研究多偏向于以经济原则为中心的调度，如降低成本、减少能耗。同时商业应用模式下云计算用户的使用体验也是十分关键的，因此保障用户QoS也是很多学者关注的。

4.1存在的问题

目前云计算调度方面的研究取得了一些成果，但也存在一些问题。具体如下：

a)现有调度大多忽略了云计算面向服务的特点。云环境将基础物理设施、平台、应用程序及软件都打包成服务的形式向外提供服务，与传统的任务调度、作业调度及工作流调度有一定的区别。云计算要为互联网上的各类用户提供多样化服务，不同用户的需求也不尽相同，如有些用户需要实时性保证，有些用户则希望费用低廉。目前对云平台下调度策略的研究却较少考虑云计算面向服务的特点，且调度策略过于简单，不能很好地满足用户的服务需求并兼顾整体性能和经济成本问题。

b)缺少云计算下的任务模型。云计算中的各种资源调度策略只有经过合适的任务模型的检验才具有更高的实用性。但在当前云环境下，由于缺少云计算方面的任务曰志，大多数研究者仍采用单纯的数学模型或使用已经存在的并行系统下的任务模型进行资源调度策略的评测。由于这些任务模型不是根据具体云环境下运行的任务负载构建出的，得出的实验结果的说服力不足，所以在云环境下构建合适任务模型便成为了—个急需解决的问题。

c)缺少对云资源的动态可用性评估。当前云计算中还没有比较成熟的资源可用性评估系统。目前，分布式系统和网格环境中也有一些资源评估预测系统，这些系统可集成到各种调度系统或资源管理系统中，为调度提供依据。但是由于这些评估模型不是云环境下构建出的，不一定适合云计算环境。云资源工作负载的动态性导致资源可用能力存在较大的不确定性，资源可用度和可用能力信息的掌握对系统选择最佳的资源一任务调度有着直接的指导作用，因此准确掌握资源动态可用能力信息对调度决策的制定起着至关重要的作用。

d)不能很好兼顾云计算用户和运营商双方利益。现有研究多是从保障用户QoS、服务费用和SLA角度，要么从运营商角度降低成本、减少能耗、优化虚拟资源规划。如何能使得市场经济驱动的资源提供与消费双方互惠互利，这是当前云计算调度需要侧重考虑的问题，因为只有这样才能保证云计算长久地发展下去。

4.2展望

尽管云计算调度已经取得了一些研究成果，但是随着云计算的发展，云计算调度仍需要进行深入研究。

a)云计算需要建立有效灵活的模型为调度提供实时性能信息。云资源动态可用性评估模型能在较大程度上保障系统选择最佳的资源一任务调度，构建适合云环境的任务模型能更有效地评估云中提出的各种虚拟资源调度策略的性能。考虑到云计算面向服务的特点，根据不同的应用需求提供灵活的调度机制。

b)云计算中实现虚拟共享资源的动态管理分配。目前大多数云计算平台的数据中心（包括IBM、AmazonEC2等）的资源分配管理还是静态的，即在建立和使用云资源时预先配置一定数量的设备，这样很容易造成过度配置资源或过低配置资源两种极端情况36。因此根据负载情况动态地分配/释放相关资源以达到提高资源利用率和提高服务质量并降低成本的目标将是很有价值的研究。

c)需要考虑云计算用户和运营商双方利益。云计算的商业模式使得这一点成为云计算长久持续发展的必要条件。

d)考虑采用多级和分布式的资源数据中心，设计动态综合调度策略和算法。目前已有一些学者对此进行研究，但多是实验模拟阶段。

综上所述，如果能从模型高效和算法高效两个层面出发，兼顾云计算调度双方（云计算用户和运营商）的利益，并通过任务模型对调度策略进行验证，将会使得云计算中的资源调度更高效，更有利于云计算的健康持久发展。

5结束语

本文阐述了云计算调度的目标和特点，探讨了目前云计算中的调度研究现状，并从以性能为中心、服务质量为中心和经济原则为中心这三个方面进行了总结归纳；特别是对当前主流云计算平台所采用的云计算调度方法进行了深入研究，分析了现有关于云计算调度的研究中存在的一些问题，并针对这些问题提出了改进意见。由于云计算环境下的资源调度是一个NP4iard问题，也是云计算领域的研究热点，要解决它还有很多工作要做。

作者：　左利云\曹志波2(1.广东石油化工学院广东省石化装备故障诊断重点实验室，广东茂名525000；2华南理工大学计算机科学 与工程学院，广州510006）