云计算环境下基于时间期限和预算的调度算法

刘亚秋，邢乐乐，景维鹏

(东北林业大学信息与计算机工程学院，哈尔滨 150040)

1 概述

随着网格计算和并行计算的发展，云计算应运而生，这宣告低成本、高性能计算时代的到来。它将计算作为一种服务提供给用户，实际上是计算能力的商品化，用户根据自己的需求使用云计算服务。在现有的云计算研究中，作业调度作为其运行枢纽，一直是研究的热点技术之一，除了影响作业响应能力和执行效率外，还直接关系到整个平台的系统性能、吞吐量和资源利用率。

目前，在已有的云计算调度研究中鲜有考虑云计算动态环境下用户实际需求对调度影响的算法，其中，对时间期限和最高预算的研究，较早是在网格计算环境中。如文献[1-2]分别提出一种网格环境下的考虑时间期限或者预算的作业调度，但满足的是单一用户需求，达到资源的时间最优或者预算最优，这样很容易将任务集中分配到某一个资源上，造成负载不平衡。文献[3]在上述算法基础上同时考虑时间期限和预算问题，计算网格环境下所有资源在时间和预算上的均衡度，依此为任务分配合适的资源，以达到优化的目的，但该算法在调度时忽略了数据传输时间和网格环境的变化，且算法复杂度较高。而文献[4]算法侧重于判断网格中资源的在时间和预算上不同的效益值，仅以此动态选择时间最优或者代价最优，没有明确考虑时间和预算效益值相同时调度的情况，且忽略了作业优先级与用户需求的关系。

已有的云计算调度问题研究除自带算法外，如文献[5]将该路由领域的加权轮询思想应用于作业调度中，提出了基于优先级的加权轮转调度算法，算法中优先级和权值的计算仅以作业大小来判断，既没有考虑用户要求，也不能适应动态的云环境。文献[6-7]仅考虑了动态云的特点，前者提出滑动窗口的设计，通过调节窗口的大小来平衡云计算集群的负载，后者在原有 DLS算法的基础上，加入Bayesian认知模型和社会学信任模型，提出Cloud-DLS算法。但上述 2种算法均没有考虑用户对作业的实际需求。文献[8]也提出一种动态均衡调度，通过调整优先级为作业提供不同的服务，但是也无法保证在特定时间期限下作业是否能被执行。文献[9]对作业的评价和最优化进行研究，侧重于最优化一组作业的总执行时间，对其中的某一作业无法保证响应时间。为更合理地分配计算资源，提高集群的作业容量，文献[10]提出一种最后期限评价模型，由模型获得作业所需的最小资源数，即最小map槽数和最小reduce槽数，以此保证作业完成时间，并尽可能地提高集群作业数。但是此模型是静态的，最小资源数一旦确定便不再改变，而无法适应动态变化的集群网络环境，且没有考虑预算问题。

本文提出一种基于时间期限和预算双重约束的云计算调度改进算法(DBS)。根据用户在时间期限和预算上的实际需求，设置不同优先级的队列，通过权值计算模型得到作业权值，并作为优先级进行作业排序，结合时间和预算评价模型，依次调度作业分配集群计算资源，并且更新作业和集群信息，以适应云环境的动态变化，形成完整的调度策略。

2 基本模型

针对云计算环境下网络负载及任务数动态变化的特点，同时考虑到用户对时间期限和预算的实际需求，以及可能在时间期限和预算要求程度上的不同倾向，本文设计权值计算模型、最高预算评价模型和权值更新模型。

模型1 权值计算模型

根据作业的时间影响因子、最后截止时间和最高预算来计算权值，表达式如下：

其中，tasksNum表示作业的大小；D表示用户设定的作业的最迟截止时间；B表示作业的最高预算；V表示资源在某一时刻的处理能力(考虑资源的当前负载)；c表示资源处理任务时每秒的收费；∂表示用户对作业完成时间要求的影响因子。

模型2 最高预算评价模型

二是拓宽思维视野。思维可以是工作发展的最大动力，也可以是最大的阻力。历史上任何一次变革，都是首先从拓展思维视野、变革思想观念开始的。军民融合参与主体多元、涉及领域宽广、利益交织重叠，必须倡导对思想的解放与更新，强化融合共赢理念，坚持优长互促、兼容互补、资源互投、效益互享，破除自成体系、自我封闭的陈旧观念，在更广范围、更高层次、更深程度上，凝聚军民融合发展合力，提升军民融合发展效能。

以时间期限评价模型[10]为模板，推导出预算评价模型，为使推导简化，本文做出以下假设：(1)集群中节点对 map任务和reduce任务的处理时间是相等的；(2)输入数据的块大小在HDFS中已经配置好；(3)每个reduce节点得到同等比例的reduce数据。

为评价作业 J的执行时间T，考虑 map完成时间，reduce完成时间和数据传输时间如下：

其中，Tm表示处理一个 map任务所需的时间；Tr表示处理一个reduce任务所需的时间；Td表示map和reduce任务传输一单位数据所需的时间；δ表示job输入数据；fδ表示reduce任务的输入数据；nm表示map任务的槽数；nr表示reduce任务的槽数。

当给出时间期限D和最高预算B时，表达式为：

其中，t表示job提交的时间；Sm表示第一个map任务开始的时间。从预算角度考虑，reduce任务最晚开始时间为：

时间期限D和最高预算B满足：

因此，从预算角度考虑，作业Job需求的最小map槽数和最小reduce槽数分别为：

模型3 权值更新模型

系统设置为每隔500 ms更新一次作业最小槽数和作业权值。根据当前集群的作业运行情况，重新计算得出作业的最小槽数，然后和已得到的槽数进行比较，如果已得到的槽数比应得的槽数少，则适量地增加作业权值，如果已得到的槽数比应得的槽数多，则适量地减少作业权值。

然后比较当前作业的权值和平均值，如果作业权值小于平均值，则：

如果作业权值大于平均值，说明作业在其所在的队列中已经处于优势，等待500 ms，在下次更新时，若作业依然无法满足最小槽数，则提交到上一级队列，以增加获得资源和调度的机会。

同理，当作业得到的槽数多于最小槽数，且作业权值大于其所在队列的平均值时，更新作业权值：

若500 ms后依然获得过多的资源，则调到下一级队列。

3 算法设计

本文在云计算环境下加入时间期限和预算的双重约束，结合评价模型提出了DBS算法，为Hadoop集群设置3 个队列：HightimeQueue，MidtimeQueue，LowtimeQueue，在配置文件中设置不同的计算资源比例和收费标准：(1)HightimeQueue拥有最多的调度机会和计算资源，尽可能地保证对时间要求高的用户作业的需求，但是相应的费用比其他2个队列要高。(2)LowtimeQueue里的作业虽然对时间要求比较低，但是也为它配置一定的计算资源，尽可能避免高时间要求的作业独占资源，低时间作业迟迟得不到响应的情况，进而可以使集群负载维持在一个较合理的水平。(3)MidtimeQueue的优先级在上述两者之间，针对的是用户对时间期限和预算要求相同的作业，保证了该类作业也可以得到一定的调度机会。

当JobClient提交作业后，会进入一个等待队列，经过预处理，根据式(1)，计算出作业的权值，更新作业信息。然后根据用户提交的时间影响因子，放入合适的队列，为降低算法的复杂度，时间影响因子取值 0.0、0.5、1.0，分别对应 LowtimeQueue、MidtimeQueue和 HightimeQueue。分类结束之后，分别对队列中的作业根据权值和提交时间进行排序，完成之后，等待Tasktracker发送心跳请求分配任务。

TaskTracker自主检测当前节点的状态，若发现存在空闲资源，则主动向 JobTracker发送信息，请求任务，JobTracker接收到信息后，启动作业调度器，选择作业进行分配。算法的伪代码如下：

其中，m为集群总的资源数；n为集群中的作业数。算法的时间复杂度为 O (3n)，空间复杂度为 O( m n)。

4 实验与结果分析

4.1 实验环境

为了检测DBS算法的性能，在实验条件有限的情况下，搭建由6个节点构成的虚拟hadoop集群，其中每个节点内存为4 GB，CPU配置为双核2.4 GHz，操作系统为Linux Ubuntu 10.0，Hadoop版本为Hadoop0.20.2。使用HDFS进行数据存储，每一个文件块大小为64 MB，并有3个副本。其中，一个节点设置为JobTracker和NameNode，其他节点为TaskTracker和DataNode。

4.2 结果分析

为比较调度算法对不同用户需求作业的影响，实验将作业分为2组，用Hadoop自带的FIFO算法进行比较。

实验1 相同大小作业不同时间影响因子

在相同大小作业不同时间影响因子的情况下，相关作业的参数设定以及集群不同调度算法对作业的响应时间如表1所示。

表1 DBS与FIFO调度算法结果比较1

可以看出，面对相同大小的作业，FIFO算法对作业无差别处理，平均响应时间为1 175.5 s，平均费用为152.6元，DBS算法平均响应时间为1 154.75 s，平均费用为145.29元，不仅提高了集群的处理能力，而且根据作业不同的需求调整执行次序，尽可能保证时间和预算的约束，更好地体现了作业的公平性。

集群内各个作业的map任务执行情况如图1所示。可以看出，Job1执行速率最快，Job2执行最慢，虽然Job3和Job4的map任务结束时间差不多，但是时间期限为1 300 s的Job3比时间期限为1 200 s的Job4完成时间要早一些，因为2个作业时间影响因子为0.5，综合考虑时间和预算，Job3权值要比Job4高，增加了一些执行的机会。此外，在Job1和Job3已完成，Job4即将完成的情况下，Job2试图分配更多的map任务，体现了算法对集群的动态变化的反应，加快了map任务的执行时间。

图1 DBS算法下作业的map任务数分配执行情况

实验2 不同作业不同时间影响因子

在不同作业不同时间影响因子的情况下，相关作业参数设定以及DBS算法和FIFO算法作业处理结果对比如表2所示。

表2 DBS与FIFO调度算法结果比较2

可以看出，面对不同大小的作业，DBS算法的平均响应时间为1 230 s，平均花费为148.07元，优于FIFO算法76.5 s，节省21.9元。另外从图中可以看到，虽然Job4的执行时间比Deadline多了37 s，这是因为在reduce阶段可能会出现数据不均衡的情况，但是由于Job4的时间影响因子为0.5，Budget没有超出最高预算，所以认为Job4执行成功，响应时间在可接受范围内。

各个作业的map和reduce任务执行情况如图2所示，Job3之所以比Job1结束的快，一方面是为了满足截止时间，另一方面当作业规模比较小时，数据本地性比较好，减少了数据在节点间的复制和传输，任务执行速率加快。同理Job4作业数据比较大，增加了传输时间和处理时间，在reduce阶段执行时间较长，但即使如此，也优于FIFO的作业响应时间。

图2 DBS算法下作业的map和reduce任务分配执行情况

5 结束语

本文提出一种在云计算环境下，根据作业在时间期限和预算上不同需求动态调整分配的调度算法。实验结果表明，该算法能有效地减少作业响应时间，均衡作业的不同需求，且算法复杂度较低，具有较好的稳定性。由于云计算环境面临作业类型的复杂多样，因此下一步将致力于面向数据类型更复杂，且具有多元约束的作业的调度问题，可以从建立一般约束模型，简化约束等方面进行研究。

[1]Abramson D, Buyya R, Giddy J.A Computational Economy for Grid Computing and Its Implementation in the Nimrod-G Resource Broker[J].Future Generation Computer Systems,2002, 18(8): 1061-1074.

[2]Yu Jia, Buyya R, Tham C K.Cost-based Scheduling of A Scientific Workflow Application on Utility Grids[C]//Proc.of the 1st International Conference on e-Science and Grid Computing.Washington D.C., USA: IEEE Press, 2005.

[3]Garg S K, Buyya R, Siegel H J.Time and Cost Trade-off Management for Scheduling Parallel Applications on Utility Grids[J].Future Generation Computer Systems, 2009, 26(1):1344-1355.

[4]李慧敏, 蒋秀凤.基于时间期限和预算效益函数的网格资源调度算法[J].福州大学学报, 2009, 37(6): 803-807.

[5]邓自立.云计算中的网络拓扑设计和Hadoop平台研究[D].合肥: 中国科学技术大学, 2009.

[6]张密密.MapReduce模型在Hadoop实现中的性能分析及改进优化[D].成都: 电子科技大学, 2010.

[7]Wang Wei, Zeng Guosun, Tang Daizhong.Cloud-DLS:Dynamic Trusted Scheduling for Cloud Computing[J].Expert Systems with Applications, 2011, 39(3): 2321- 2329.

[8]Sandholm T, Lai T.Dynamic Proportional Share Scheduling in Hadoop[C]//Proc.of the 15th International Workshop on Job Scheduling Strategies for Parallel Processing.Atlanta, USA:[s.n.], 2010.

[9]Zaharia M, Borthakur D, Sarma J S.Delay Scheduling: A Simple Technique for Achieving Locality and Fairness in Cluster Scheduling[C]//Proc.of the 5th European Conference on Computer Systems.New York, USA: ACM Press, 2010.

[10]Kc K, Anyamwu K.Scheduling Hadoop Jobs to Meet Deadlines[C]//Proc.of Conference on Cloud Computing Technology and Science.Indianapolis, USA: IEEE Press, 2010.