云计算环境下任务调度技术的研究进展

□李陶深，李明丽，张希翔

（1. 广西大学 计算机与电子信息学院，广西 南宁 530004；2.湖南大学 信息科学与技术学院，湖南 长沙 4100075）

1 前言

云计算是近年来受到国内外广泛关注的研究热点之一.云计算由一系列动态变化的资源组成，这些资源通过虚拟化技术提供给云计算用户，用户可以通过网络按需租赁云计算资源，从而减少用户终端的处理负担，并能享受云端强大的计算能力.云计算是分布式计算、集群计算、网格计算及并行计算的发展，它作为一种新颖、灵活、便捷、新崛起的商业计算模型，将计算任务分布在海量计算机构成的集群上，用户可以按需获取计算能力、存储容量和信息服务[1].

云计算对现代人类世界的改变正如发电厂对19世纪的人类用电方式的改变一样.在没有发电厂和电网的19世纪70年代，几乎每个工厂甚至住户都需要配备一台发电机以供应自身电力的需要，这样的自发电机制无疑是低效而且昂贵.随着电力需求的增加，人们提出了建立电力生产中心的思想，电能通过电网输送到工厂、住所，人们不再需要购买自己的发电机，转向购买发电厂通过电网输送的电力资源.云计算的本质和发电厂一致，庞大的计算中心或数据中心通过犹如电网一样无所不在的互联网，将计算资源输送给千家万户，而用户只需通过简单的设备根据需求访问计算机与存储系统.

云计算的商业化特性使其必须具有通用性设计，并能便捷的为用户动态需求提供多样化的服务，这样的制约条件下，使得云计算的作业调度具有较高的复杂性.尤其云计算是一种商业实现，更为注重用户每次使用云计算的体验和评价.因此，云计算服务提供商如何通过恰当的调度策略高效地运营云计算资源显得尤为重要[2].

任务调度就是以优化为目的在一定的规则限制下将任务与资源做映射[3].任务调度是在所有计算机系统中都是影响系统性能的关键所在，它也是云计算系统中的关键问题.在云计算概念提出之前，在并行计算、网格计算和分布式计算中已经存在着许多经典的任务调度算法，例如：遗传算法[4]、模拟退火算法[5]、Min-Min算法[6]、Min-Max算法[]和蚁群算法[7]等.这些算法经过为适应云计算的新特征做相应改进以后，都可以应用于云计算系统的任务调度.但是在云计算环境下，作业调度系统需充分考虑制约用户作业的各种因素，负责为用户作业选取“云”或者网格中最适合的资源.

本文对云计算环境下任务调度的新特性、任务调度算法的研究现状和相关研究成果进行归纳和总结，探讨和分析一些尚待解决的问题或尚未很好解决的问题，讨论未来可以开展研究的工作方向.

2 云计算环境下任务调度的新特性

如前所述，云计算是网格计算、集群计算、并行计算的发展，因此在一定程度上，网格计算、集群计算和并行计算的作业调度策略对云计算具有相似性和借鉴性.但是，云计算不同于网格计算、集群计算和并行计算，它所采用的商业理念、形式、成熟的虚拟化技术以及非标准化的规范，使得云计算环境下的任务调度需要充分考虑按需提供虚拟化资源、付费服务、用户群体大、任务差异大等各种制约用户作业的因素，调度中面临许多新问题.

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

图1 云计算系统用户获取服务示意图

从云计算资源使用者角度来说，用户通常考虑哪个云计算资源能满足他们作业计算的QoS要求（例如作业类型、预期完成时间、计算时间等），及他们需要为云计算资源所支付的费用.因此，在云计算任务调度中，需要满足云计算用户的作业QoS要求、性价比要求，使之以一种经济方式高效地利用云资源.从云服务提供商角度来说，系统是通过用户所租用的资源(虚拟机数量、带宽、内存等)和时长进行收费，因此在在云计算任务调度中，需要任务调度机制高效、及时地处理用户任务请求，保持处理机负载均衡，以保障在满足用户服务质量的前提下，提高云系统的吞吐量和整体用户数量，进而使云计算资源的使用获得最大的收益.

假设有用户向数据中心提交一个任务，可以分解为5个子任务，并根据子任务之间的依赖关系和先后关系生成有向无环图(Directed Acyclic Graph，DAG)，如图2所示.在传统的任务调度中，一般只是从用户的角度来考虑任务如何高效地完成.具体做法是：假设数据中心分配给该用户三个虚拟机，定义预期执行时间(Expected Execution Time)子任务ni在主机mj上 执行的时间可用矩阵元素EETij表示，即：

运用传统的Min-Min算法来进行任务调度，最后求得的运行时间为100，子任务执行顺序与虚拟机资源分配如图3所示.

图2 子任务DAG图

图3 Min-Min算法甘特图

从图3的调度结果可知，在整个任务执行过程中，虚拟机m1从未被分配子任务执行.从云服务提供商的角度来说，本来可以分配给其他用户的m1被闲置了，这造成了机会成本的浪费；而从用户的角度来说，如果租借不必要的虚拟机m1，就需要支出额外的费用.

在本例中，虽然传统的任务调度算法能够满足任务执行时间最小的要求，但是未能达到用户与服务提供商的利益最大化.文献[8]提出了一种预先调度的算法，该算法应用博弈论中纳什均衡的思想来预先决定任务分解后所需的虚拟机数量，然后再进行虚拟机的分配.这一算法减少了虚拟机的闲置时间，并达到了最小化执行时间的目的.但是，为了降低兄弟节点的最早开始时间，该算法需要对其父节点进行复制，这无形中会增加需执行任务的数量并增加了通信开销.文献[9]从另外一个角度来避免虚拟机资源的浪费，提出了一种云计算下适应用户任务动态变更的调度算法，针对用户因个人因素撤销任务的情形，对每个撤销任务根据其依赖关系撤销关联任务，更新DAG图，然后再使用Min-Min算法进行调度.这个算法提高了调度效率和云资源的利用率，保障了云服务提供商的利益.

与传统系统的任务调度机制相比，云计算任务调度呈现出一些新的特性要求[2]：

(1)用户对云计算资源需求具有多样性与偏好性，因此需要考虑更复杂的QoS约束，最大限度地保障用户QoS要求.对于这个特点，可以利用基于行为成本方法、基于工作流的方法、启发式算法等求解组合优化问题.

(2)调度时保证云计算服务提供商有效地利用云计算资源和获得最大收益.云计算或网格中传统的调度策略往往只考虑如何满足各用户的QoS要求，却很少考虑资源提供商的最大收益.针对这个特点，可利用队列模型方法、博弈论等解决任务调度问题.

3 云计算中任务调度技术的现状分析

由于云计算技术比较新颖，目前有关云计算下任务调度的研究还比较少.一些学者根据云计算的特点，对云计算下的任务调度做了相关研究，取得了一些研究进展.

3.1 经典任务调度算法的改进运用

传统的分布式计算和网格计算中有许多经典的任务调度算法，这些算法经过恰当地改进，可以适用于云计算环境中.下面是一些可用于云计算的经典任务调度算法：

(1)机会负载均衡算法(OLB)：它将每一个任务，以任意顺序，分配到下一个空闲的虚拟机中.这个算法非常简单，目的就是使所有虚拟机都运转效率.

(2)最小执行时间算法(MCT)：它将任务以任意顺序分配到虚拟机中的对该任务具有最小执行时间的那台.最小执行时间算法把每一个任务映射到对该任务而言的最佳虚拟机上，但是，它忽视了该虚拟机的机会成本，该算法损害了虚拟机的负载均衡性.

(3)最早完成时间算法(MCT)：将每一个任务以任意顺序映射到对该任务而言具有最小最早完成时间的虚拟主机上.在该算法中，不能保证每一个任务都可以在最小执行时间完成.

(4)Min-Min算法：从一个未分配任何虚拟机的任务集合开始，分为三个阶段.第一阶段：计算集合中每个任务的最小期望完成时间，并找出相对应的机器.第二阶段：找出所有最小期望完成时间集合里的最小值，并将该任务映射到相应的虚拟机上.第三阶段：指派完成后，更新机器期望就绪时间并将已映射的任务从任务集合中删除.重复上面三个阶段，直至所有的任务被映射到处理机中.

(5)Max-Min算法：Max-Min算法与Min-Min算法思想基本一致.不同的是Max-Min算法首先调度大任务.因此，在第二阶段中，Max-Min算法找出所有最小期望完成时间集合里的最大值，并将该任务映射到相应的虚拟机上.其余阶段与Min-Min算法完全相同.

3.2 启发式任务调度算法

研究表明[10]：在云计算环境中，任务调度是一个NP完全问题.因此，启发式算法经常被视为解决该类问题的最佳选择.启发式算法可以划分为静态的和动态的.静态启发式算法应用于所要执行的任务数量是已知的状况，动态启发式算法适用于任务动态地达到系统的情形[11].

3.2.1 静态调度

当以下两种情形同时出现时，可用静态策略进行调度：

(1)所有任务在同一时刻到达；

(2)当每一个任务被调度后，都立即更新虚拟机可用时间.

可用于静态启发式调度算法有遗传算法(GA)和模拟退火算法(SA).文献[12]对传统的遗传算法进行了改进，提出了一种双适应度的改进型遗传算法，同时考虑了总任务完成时间的个体适应度和任务平均所用时间的个体的适应度，较好地避免了潜在优良基因的丢失、陷入局部收敛.在双适应度遗传算法和传统遗传算法得出的总任务完成时间相差不大的情况下，双适应度遗传算法得出的任务平均完成时间要明显少于传统遗传算法，从而降低了能耗，达到节能的目的.但是，该算法需要进化到一定的代数才能体现其优越性，其收敛速度比一般的遗传算法要慢.文献[13]采用统计技术预测任务执行时间，然后再用模糊控制理论设置遗传算法的参数(收敛速度，适应度)，最后使用遗传算法进行迭代，获得任务调度方案.该算法是一种在线模式动态调度算法，符合云计算的特性，并且可以均衡虚拟机的负载.但是其实现比较复杂，性能依赖于概率统计中预测执行时间的准确性.

3.2.2 动态调度

在动态任务调度中，任务不是同时到达的，而是在一段时间里以一定的概率到达.在这种任务到达的模式下，任务集中的任务数量是变化的，可分配的虚拟机数量也随着变化.动态启发式算法可以分成两种类型：批模式与在线模式.批模式中，任务到达后被分配到一个集合中，在集合中做预调度.在线模式中，一旦任务到达，就立即给它分配虚拟机，每个任务只能被调度一次.

3.2.2.1 批模式动态调度

批模式动态调度算法有：

（1）痛苦算法：该算法将机器分配给痛苦值最大的任务.在每次调度事件中，痛苦值被重新计算，它等于最早完成时间和次早完成时间的差值.对于任务Ti，若在最早完成时间计划里的机器Mk未被映射，则将Mk映射到Ti.否则，假设Mk已映射到Tj，算法比较任务Ti和Tj的痛苦值，若Ti的痛苦值较大，则取消对Tj的映射，将Tj放回任务集合.任务集中的每一个任务只被考虑一次.

（2）优先权变化的轮询调度算法：该算法基于任务的期限完成时间进行优先权的确定，具有越早期限完成时间的任务，其优先权越高.算法每进行一轮调度，都要对优先权进行重新分配，然后基于优先权重新映射虚拟机.优先权高的任务可以优先选择性能优良的虚拟机，极端情况下甚至可以独享虚拟机.

3.2.2.2 在线模式动态调度

在线模式动态调度算法有：

（1）交换算法(SA)：它结合了MCT和MET这两种启发式算法的思想.在最短执行时间算法(MET)中，可能会将过多的任务分配到同一个性能优异的虚拟机中，从而造成负载不均衡.而最短完成时间算法(MCT)可以均衡负载，但不能确保每个任务都可以分配至最短执行时间的机器上.交换算法将两个结合起来，可以只付出一定量额外时间的同时，均衡系统负载.

（2）K百分比最佳算法(KPB)：该算法在调度任务时，只考虑虚拟机集合里的一个子集.该子集由任务执行时间最优的前百分之K比例的虚拟机组成.该算法将任务映射到性能优异的虚拟机子集中，使其与最短执行时间算法相比，获得更好的负载均衡；与最短完成时间相比，又能获得更短的执行时间.

3.3 构建新的任务调度算法模型

一些研究人员根据云计算的技术特性，提出构建新的适应云计算需求的任务调度算法模型.

文献[14]将网络中虚拟机使用费用按性能从高到低设置，用户提交的任务具有截止时间.使算法在满足截止时间限制的同时，完成任务的花费最低，满足了用户的QoS和性价比最优要求.文章所设计的算法只考虑了独立型任务，没有考虑依赖型任务，这是不符合云计算中任务之间的实际联系的.

文献[15]采用了社会学领域中关于分配性正义的伯格模型，对云环境下的任务调度建立双重公平行约束.从用户角度，以一般期待完成时间来约束不同QoS的偏好分类；云服务方面，以资源分配的评判函数进行系统公平性的约束.与社会学领域的普遍结论一致，达到公平的同时，却损失了一定的效率.

文献[16]利用经济学领域的博弈论对具有QoS限制的资源分配进行了研究，采用了“两步走”的方法.第一步：每一个任务都独自地进行问题最优化求解，在这一步，不用考虑任务之间资源分配的相互关系.第二步：设计一个进化机制，机制中的博弈算法同时考虑效率和公平，算法考虑任务之间的相互关系，在改变最初的调度策略的时候，以尽可能小的效率损失来提升资源分配公平性.最后证明如果资源分配中有可行解的时候，总是存在着纳什均调度算法结合起来，设计出了一种选择算法.该算法避免了Min-Min算法面临少量长任务和大量短任务时的低效调度和Max-Min算法面临少量短任务和大量长任务时，对短任务实时性需求不能满足的缺陷.选择算法根据最短执行时间对任务进行预处理，然后根据所得到的数据判断该任务集应采用Min-Min算法还是Max-Min算法.实验结果表明，选择算法性能优于Min-Min算法和Max-Min算法，显然，由于加入了预处理和判断函数，选择算法的复杂度有所增加.

除了上述方面以外，专家学者们还从不同的角度对云计算环境下的任务调度进行研究.例如：利用层次分析法进行资源分配[18]、考虑虚拟机之间网络带宽的任务调度[19]、异构多处理器组成的云平台中的任务调度[20]和基于用户预算的任务调度[21].文献[22]根据云计算下用户任务对资源需求存在广泛差异的特点，在考虑资源代价和计算性能的条件下提出一种改进的基于成本的调度算法.文献[23]从用户的区分QoS需求和云服务提供商最大化收益的角度提出一种作业调度方法.

还有很多学者在MapReduce下开展云计算的任务调度研究.MapReduee是云计算平台下的一种编程模型[24]，它作为云计算的开源项目Hadoop的重要组成部分，在企业界和学术界都有着广泛应用.文献[25]在云计算环境中改进MapReduce的调度，把原来任务调度FIFO改为多级反馈队列，既能使高优先级的任务得到响应，又能使短任务迅速完成.文献[26]则采用Triple-Queue调度，把Map阶段分解，设置Map-Shuffle阶段，在任务调度时进行工作负载预处理，分为等待队列，CPU受限队列，I/O受限队列.文献[27]提出在异构型环境中改进MapReduce性能.文献[28]提出一种在异构型环境里自适应的MapReduce调度算法.

4 云计算中任务调度技术的研究展望

就目前云计算中任务调度技术的研究现状和现有研究存在的一些不足，本节给出笔者认为需要进一步研究和解决的问题.

4.1 适应用户任务动态变更的调度策略研究

在数量有限的云资源环境下对数量庞大的用户任务进行调度时，当有用户提交任务后发现作业存在不足需要删除、撤销时，调度系统如何采取一种有效策略与之适应，以避免云资源不必要的浪费是值得关注的问题.这个问题在云计算下用户群越庞大时，越将频繁的出现，特别在私有云下资源较紧缺的情形下，更是需要一种适应用户任务动态变更的调度策略，以达到资源的高效管理和使用.但是在现有的云计算调度研究中，还没有适当的针对海量任务数量的调度算法.为此，可以针对云计算任务调度过程中资源动态变化和用户作业动态变更的情况，研究用户作业动态变更过程中存在着的数据依赖关系，设计相应的任务调度策略.

4.2 启发性技术在云计算任务调度问题中的应用

如前所述，云计算任务调度是一个NP完全问题，为此许多学者都在关注启发性技术在云计算任务调度问题中的使用，将一些经典启发式算法运用于任务调度中，也取得了不错的效果.然而，云计算环境下的作业（任务）往往有较大规模计算量、不同偏好的作业组，以及更多的制约条件，因此在特定的云资源环境选取一个最优的调度策略仍是一个棘手的问题.如何根据云计算的新特性，对传统的启发式任务调度算法进行适当的改进，使之能应用到云计算任务调度中，这还需要做进一步的深入研究.

4.3 以商业的视角研究云计算任务调度

云计算及网格计算中的传统调度系统往往只考虑如何满足各用户的QoS要求，却很少考虑资源提供商的收益最大化问题.实际上，云计算中的任务调度问题不仅要满足云计算用户的作业QoS要求，还需要以一种经济方式高效利用云资源.构建出新的任务调度算法模型应该更多地关注如何去保障用户服务质量和用户与提供商的经济利益.这里不仅需要对服务类型做进一步的细分，综合考虑网络带宽和通信代价等因素，使QoS保障和服务具有较好的性价比，而且还要充分地考虑使服务提供商获得最大化云系统的收益.也就是说，可以从两个方面来考虑：一是从云计算资源使用者角度出发，综合地考虑哪个云计算资源能满足用户作业计算的QoS要求（例如作业完成的预期时间，计算量等），以及用户需要为云计算资源所支付的费用；二是从云计算服务提供商的角度出发，综合考虑在满足用户作业QoS约束的前提下，如何在提供云计算资源时使供应商获得最大的收益.为此，云计算中的任务调度必须以高效、经济的策略来满足用户不同的需求.目前尽管已有研究人员根据资源代价和计算性能、或者根据用户的区分QoS需求和云服务提供商最大化收益提出了一些任务调度算法，但是这些研究还远远不够，需要我们进一步拓展.

4.4 其他学科领域的模型或理论在云计算任务调度中的应用

因为云计算资源由海量高性能计算机和商用计算机混合组成，具有较强的异构性和伸缩性，使得云资源动态多变.另一方面，云用户提交的作业也具有各类偏好，如一些任务偏向于高计算复杂度的科学计算，属于计算型任务；一些任务需要对大型数据进行存储，则需要大量的存储空间，属于存储型任务；一些任务需要高带宽接入、通信数据量大，属于带宽型任务，等等.因此，应该针对用户任务的偏好不同，设计区分服务的调度方法，让有不同类型优势的资源优先分配给相应的任务，可以得到更好的用户评价和反馈，也更符合云计算的商业模式.但是，现有的调度算法并没有很好的对其性能的进行持续评估，资源的选择存在较大的盲目性和局限性，云计算的运营模式也要求云资源分配时更注重用户使用的满意度.因此，如何在动态多变的云资源环境下分配恰当的资源以保证用户任务区分服务的质量是一个值得研究的问题.

可以把一些其他学科领域的模型或理论知识（如经济学中的博弈论，社会学中的伯格模型等）应用到云计算任务调度中，更好地为用户任务分配恰当的虚拟资源，同时又能保证云计算服务提供商有效利用云计算资源和获得最大收益.例如，可以针对云计算资源需求的多样性与偏好性，综合地考虑云计算环境下用户QoS和资源参数更为复杂的依赖关系，研究多态型的演化博弈调度模型，通过任务方和资源方的混合博弈，按照服务类别的划分进行资源分配，依据用户反馈评分或任务执行估计评分不断演化改进虚拟机资源及其所属种群的各项服务评价，达到最后博弈均衡.

5 结束语

云计算具有资源动态多变、按需提供虚拟化资源、付费服务、用户群体大、任务差异大、用户任务偏好多样性等特点，现有的任务调度技术不能很好地适应云计算任务调度的需求.因此，任务调度策略是云计算技术领域的研究热点之一.本文介绍了云计算环境下任务调度技术的特性，对云计算任务调度技术的研究进展进行了较系统的分析和总结，可以看出，尽管国内外在云计算任务调度技术方面的研究取得了一些进展，但是还要许多不足之处，任务调度策略的综合性能还有待于提高，还有许多工作值得我们去探索和研究.

[1]M. Armbrust, A. Fox, R. Griffith et al. Above the Clouds:A Berkeley View of Cloud Computing[R]. University of California, Berkeley: Technical Report(UCB/EECS-2009-28), February 10, 2009

[2]张希翔. 云计算环境下任务调度算法的研究[D].硕士学位论文,南宁：广西大学, 2011

[3]S. Nagadevi, K.Satyapriya and D.Malathy. A Survey on Economic Cloud Schedulers for Optimized Task Scheduling[J].International Journal of Advanced Engineering Technology, 2013, 4(1):58-62

[4]W. Yao, B. Li and J. You.Genetic Scheduling on Minimal Processing Elements in the Grid[M]. Lecture Notes in Computer Sciences 2557, Springer-Verlag Berlin, Berlin,2002. pp.465-476

[5]遆鸣，陈俊杰，强彦.基于模拟退火的Map Reduce调度算法[J].计算机工程, 2012,38(19):45-48

[6]X. He, X. Sun and G..Laszewski. A QoS Guided Min-Min Heuristic for Grid Task Scheduling [J]. Journal of Computer Science and Technology , 2003, 18(4): 442-451

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

[8]M. Abdeyazdan, S. Parsa and A. M. Rahmani. Task Graph Pre-scheduling, Using Nash Equilibrium in Game Theory[J].The Journal of Supercomputing, 2013, 64 (1):177-203

[9]张希翔，李陶深.云计算下适应用户任务动态变更的调度算法[J].华中科技大学学报(自然科学版),2012,(S1):163-169

[10]M. A. Arfeen, K. Pawlikowski and A. Willig. A Framework for Resource Allocation Strategies in Cloud Computing Environment[C]. Proceeding of 2011 IEEE 35th Annual Computer Software and Applications Conference Workshops , Munich , Germany, July 18-22, 2011,pp.261-266

[11]P. Salot. A Survey of Various Scheduling Algorithm in Cloud Computing Environment[J]. International Journal of Research in Engineering and Technology, 2013,2(2):131-135

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

[13]S. Tayal. Tasks Scheduling Optimization for the Cloud Computing Systems[J].International Journal of Advanced Engineering Sciences and Technologies, 2011,5(2):111-115

[14]帅志伟.一种改进型 Min-Min调度算法[D].硕士学位论文，南昌：华东交通大学，2009

[15]赵春燕.云环境下作业调度算法研究与实现[D].硕士学位论文,北京：北京交通大学, 2009

[16]G. Wei, V. Vasilakos, Z. Yao and N. Xiong. A Game-Theoretic Method of Fair Resource Allocation for Cloud Computing Services[J]. The Journal of Supercomputing,2010, 54(2):252-269

[17]K. Etminani and M. Naghibzadeh. A Min-Min Max-Min Selective Algorithm for Grid Task Scheduling [C].Proceedings of The Third IEEE/IFIP International Conference in Central Asia on on Internet, Tashkent ,Uzbekistan, September 26-28,2007, pp.1-7

[18]D. Ergy, G. Kou, Y. Peng, Y. Shi and Y. Shi.The Analytic Hierarchy Process: Task Scheduling and Resource Allocation in Cloud Computing Environment[J].The Journal of Supercomputing, 2013,64(3):835-848

[19]W. Lin, C. Liang, Z. Wang and R. Buyya. Bandwidthaware Divisible Task Scheduling for Cloud Computing[J].Software: Practice and Experiment, 2014, 44(2): 163-174

[20]C.Augonnet, S.Thibault, R.Namyst and PA.Wacrenier.StarPU: A Unified Platform for Task Scheduling on Heterogeneous Multicore Architectures[J].Concurrency and Computation: Practice and Experience, 2011,23(2):187-198

[21]A. M. Oprescu, T. Kielmann and H. Leahu. Budget Estimation and Control for Bag-of-Tasks Scheduling in Clouds [J].Parallel Processing Letters, 2011, 21(2):219-243

[22]S. Selvarani, G. S. Sadhasivam. Improved cost-based algorithm for task scheduling in cloud computing[C].Proceedings of 2010 IEEE International Conference on Computational Intelligence and Computing Research,Coimbatore, India, December 28-29, 2010, pp. 620-624.

[23]L. Li. An Optimistic Differentiated Service Job Scheduling System for Cloud Computing Service Users and Providers[C]. Proceedings of 2009 Third International Conference on Multimedia and Ubiquitous Engineering,Qingdao, China, June 4-6, 2009, pp.295–299.

[24]J. Dean, S. Ghemawat. MapReduce: Simplified Data Processing on Large Clusters[J]. Communications of the ACM, 2008, 51(1): 107-113.

[25]S. Gao, T. Huang, G. Gan. An improved schedule of MapReduce programming environment in cloud computing[C]. Proceedings of Intelligent Computing and Integrated Systems (ICISS), Guilin, China, October 22-24, 2010, pp.665 – 668.

[26]Chao Tian, Haojie Zhou, Yongqiang He, Li Zha. A Dynamic MapReduce Scheduler for Heterogeneous Workloads[C]. Proceedings of 2009 Eighth International Conference on Grid and Cooperative Computing ,Lanzhou, China, August 27-29, 2009, pp.218 – 224.

[27]M. Zaharia, A. Konwinski, A. D. Joseph, R. et al.Improving Mapreduce Performance in Heterogeneous Enviroments[C].Proceedings of the 8th USENIX Symposium on Operating systems design and implementation , San Diego, California, USA, December 8-10,2008, pp.29-42.

[28]Q. Chen, D. Zhang, M. Guo, et al. SAMR: A Selfadaptive MapReduce Scheduling Algorithm in Heterogeneous Environment[C]. Proceedings of 2010 IEEE 10th International Conference on Computer and Information Technology, Bradford, United kingdom, June 29-July 1, 2010, pp.2376-2743.