周水清1,2，陈雯1,2，龚仕林1,2

　　（1.数字化纺织服装技术教育部工程研究中心，上海 201620; 2.东华大学 信息科学与技术学院，上海 201620）

　摘要：近年来，基于互联网技术的云计算的应用日趋成熟，诸多开源的云平台不断出现。异构分布式环境中，在面对不同情况时，如何保障负载均衡已经成为云计算研究中的重要研究方向。本文提出了一种基于DAG(Directed Acyclic Graph)的异构分布式系统的任务调度策略。该算法通过资源效益度的竞争，从筛选后的资源池中选择恰当的资源节点进行任务分配，以此提高系统的负载均衡能力。通过实验表明，该任务调度算法可以有效降低通信开销，提高资源利用率，提升负载均衡能力，为整个系统提供高效的性能。

关键词：云计算；资源调度；负载均衡；DAG

0引言

　　随着近几年互联网的迅猛发展，网络上的数据量呈现了爆发式的增长。面对如此庞大的数据量，搭建一个云计算资源管理平台用于管理这些数据就显得非常有必要［12］。

　　在平台中，任务调度算法是提高平台工作效率的关键之一。云计算任务调度的目标就是将相互独立的N项任务分配到M种异构可用的资源上，使得任务的完成总时间最小且资源得到充分利用。在实际应用中则是将不同的任务分配给不同的虚拟机执行，以使得网络带宽占用率最小，得到最佳的任务执行时间［3］。

　　目前，关于云计算平台的任务调度算法逐渐成为研究热点。Silvio Luiz Stanzani等人提出了MCAHEFT（MultiCluster AllocationHEFT）算法［4］，证明了多集群调度平行任务的可能性，不过没有充分考虑到数据传输时造成的网络负担。Nitish Chopra等人提出了在公私混合云中进行调度的算法［5］，它着重考虑了任务调度运行中的用户花费问题。通过多次调度，从公有云中借用资源达到了在规定时间内降低使用费用的目的。但是其缺点是从公有云中借用资源的步骤过于繁琐复杂。O.M.Elzeki等人对最大最小任务调度算法进行了优化［6］。它克服原来最大最小算法的不足，当有大量较小任务的时候，最大最小任务调度算法的任务执行时间会显著降低。但是，其缺点是没有充分考虑到资源节点的可用性和稳定性。田国忠提出了基于异构资源的多DAG任务调度的BackFill算法，并且研究了用户使用费用的优化问题［7］。

　　尽管有很多分布式任务调度的研究取得了一定进展，但是在以下几方面仍然有进一步研究和优化的空间：

　　（1）只考虑了网络情况良好、数据传输效率较高的情况；

　　（2）不同任务会对任务执行节点有不同的要求，需要引入一个灵活的变量用以量化任务执行节点；

　　（3）可以将DAG的概念引入算法。

1算法模型

　　本文提出的算法在优化后的MaxMin算法的基础上［8］进行了以下的改进和优化：

　　（1）引入了DAG任务的概念；

　　（2）引入了资源效益度，将资源的性能进行量化，从而便于任务执行节点的筛选；

　　（3）把任务直接分配到数据所在的资源节点上，而不是将数据和任务分配到筛选出的节点上，降低了网络负载。

　　资源效益度（满足程度）［9］：指的是在任务调度的过程中，资源对于任务所要求的条件满足程度，对于第Ri个资源，其资源的效益程度用E(Ri)表示。

　　资源效益度不只是与任务完成时间、资源的负载有关，同时还与资源能耗、数据本地性有关。资源效益度值越高，则选择该资源节点来完成任务的可能性也越高。

　　资源节点的效益度是由资源的特征参数构成的，这些特征参数可以使用一个集合来表示：C={c1,c2,c3,c4,c5,…}，集合中的每一个元素表示资源的一个特征量。常见的特征量如表1所示。此外，根据不同情况的需要，还可以灵活选择特征量。表1特征量表类型参数CPUCPU数量CPU处理速率CPU利用率内存空闲物理内存空闲虚拟内存硬盘磁盘利用率磁盘转速I/O访问速度其他Flag标识在计算资源效益度时，首先要对特征参量进行量化和归一化处理，从而使得Ci∈［0,1］。 然后根据归一化之后的特征量计算资源的效益度。

　　在特征量集中，由于有些特征量对于任务的执行影响占据主导地位，有的则相对较弱，所以有必要对每个特征量取其权值。改变不同的权值用以应对不同的情况。

　　此外，在效益度中，设置了变量Flag，它是一个布尔值。当资源空闲、没有任务需要处理时，将其置为1。如果有任务正在处理时，则将其置为0。因此，将效益度的公式修改为：

　　另一方面，在实际的生产中，经常出现的一种情况就是，所需要完成的任务的输入值是其他任务完成之后的输出值。在DAG中，任务之间具有关联性，即必须在完成一个任务之后才能继续执行后续任务。基于这种特征，本文使用DAG用以模拟此情况［10］。DAG的示例如图1所示。

　　在任务调度的过程中，按照任务层对任务进行归类。在每一层中，得到任务所要处理数据的元数据（metadata）。和资源的特征量类似，元数据也是一个集合，其内部常用的元素如表2所示。

元数据对算法非常重要，比如数据能否在本地、数据的大小、数据的权限等。它无法像资源的效益度一样进行确切的量化分析，只能根据不同的情况在恰当的地方调用适合的元数据。

2优化算法

　　在系统的整体调度策略中，其策略核心是根据任务的元数据和资源的效益度执行任务调度。本文所提出的DAG任务应用分布式异构系统的调度策略，其大致思想如下：

　　首先，选择需要处理的任务。在一个DAG任务中，先对第一层任务进行调度分配，即从DAG的入口开始。根据元数据，获得需要处理数据的大小。需要处理数据量最大的任务拥有最高的优先处理权。

　　在分布式系统中，同一份数据会在不同的资源上拥有备份，因此根据元数据获取需要处理的任务数据的路径。

　　此外，判断数据是否在本地资源上的变量是一个布尔值，记为L。为此，有必要把效益度公式再次修改为：

　　拥有任务所需要数据的资源的集合，称为资源候选池。从上式可以知道，当本地资源没有所需要的数据，或者当资源正在处理其他任务时，资源的效益度会设为0，也就是最低。这样这个资源在资源候选池中就没有了竞争力，这样任务就会分配到其他候选资源上。

　　在对资源进行筛选后，剩下的资源会继续通过效益度竞争，并且仍然由效益度较高的资源获得任务执行权。在获得执行权后，将资源节点的Flag置为0，并在任务执行完毕之后将Flag重新置1，以此迭代，完成一层DAG任务。

　　在DAG任务的第一层执行完毕后，执行第二层的任务集合。处理方法与第一层任务执行程序一样。原则是将需要处理的最大数据分配给处于空闲状态并且效益度最高的拥有本地数据的资源上，依次迭代。当最后一层的任务完成之后，到达DAG的出口，整个DAG任务则完成。算法流程图如图2所示。

　　从流程图中可以看出，算法会首先考虑当前DAG层是否还有任务需要执行。如果有尚未完成的任务，则获取任务的元数据。通过元数据比较该层全部任务所拥有的优先级，选择优先级最高的任务，通过效益度计算公式选择效益度最高的资源节点，使用该节点执行任务。在完成任务之后，继续考虑当前层有无任务需要执行，依次迭代，最后完成整个DAG层。在所有的DAG层都完成以后，该DAG任务完成。下面给出算法的伪代码。

　　while (layer.size() != 0){//判断是否还有DAG层

　　while (task.size() != 0){//判断该层是否还有任务

　　for all submitted tasks in layer of DAG;//遍历所有需要执行的任务

　　for all metadata in tasks;

　　//确认执行任务的元数据

　　search task T which has maximum data

　　//找到数据量最大的任务，设为T

　　for all resource;

　　assign Ti to the resource Rj which has maximum performance with local data in leisure;

　　set Flag of resource Rj to busy;

　　//将运行任务的资源设定为busy状态

　　}

　　}

3实验与结果分析

　　3.1实验相关条件

　　实验使用的仿真平台是CloudSim。它是一款由澳大利亚墨尔本大学的实验室与Gridbus项目所宣布推出的云计算仿真软件。

　　CloudSim的功能可以分为两大类：第一类是虚拟化引擎，其目的是在数据中建立和管理独立的、协同的、多重的虚拟化服务。第二类是虚拟化服务分配处理核心，使其可以在时间共享和空间共享之间灵活地进行切换。

　　实验中搭建了一个数据中心用以模拟云计算集群。该集群拥有五台虚拟机作为资源节点，分别称之为Vm0，Vm1，Vm2，Vm3，Vm4。详细数据如表3所示。因为集群中每台计算机的性能指标复杂繁多，所以本次实验中仅仅考虑与任务处理速度相关的两个主要性能指标：MIPS（Million Instructions Per Second）和Ram。这两项指标是任务处理中的关键指标。此外，所有的虚拟机都假定是单核处理器。在CloudSim中的具体实现则是从CondorVM类中分别实例化5个Vm，在实例化的过程中指定相应的性能参数。

　　任务的输入是DAG任务，有50个任务，分为9层。每层的任务数量如表4所示。

　　在CloudSim中，DAG任务是通过一个xml文件引入的。利用Java的File类对文件进行解析，从而实现任务的输入。

　　另外，在比较资源效益度方面，因为CondorVM类继承自VM类，所以可以使用VM类中的方法getCloudletMips()和getCloudletRAM()获得本次试验所需的资源节点的性能指标。每次分配任务时，算法都会自动刷新这些指标，把得到的最新性能指标代入上文所推出的节点效益度公式(4)，从而实时地为算法提供每个节点的效益度指标。

　3.2实验结果

　　经过多次试验，并对结果进行统计后，将其与FCFS（First Come First Server）算法以及Maxmin算法进行比较。FCFS算法是一种对DAG任务中的每一个任务逐个依次进行执行的经典算法。得到的试验结果如下：

　　（1）在网络负载使用方面，因为优化后的算法是把任务分配到资源上，所以其对网络环境的要求较低。而另外两个算法则是把任务需要的数据传输到任务节点上，因此当网络环境恶劣或者需要传输数据量非常大的时候，这两个算法的性能会大幅下降，所以两者对网络环境的要求较高。

　　（2）由图3可以看出，优化后的算法平均任务完成时间为217.35 ms，MaxMin算法为205.21 ms， FCFS算法为210.04 ms。新算法的完成时间比Maxmin算法的完成时间延长了5.91%。这是因为新算法相比原本的算法增加了限制条件，从而造成任务完成时间的延长。不过，任务完成时间的增量在可以接受的范围之内。如果处理的任务量不是非常大，那么可以近似认为新算法和Maxmin算法的完成时间相同。

　　（3）在负载均衡能力方面，由于处理的DAG任务大多分布于第3层，所以主要从第3层分析算法的负载均衡能力。负载均衡能力主要观察是否每个节点都被平均地分配到了任务。如果各个节点之间所获得的任务数量相近，那么就可以认为算法的负载均衡能力较好。

　　如图4所示，在所有28个任务中，原来的Maxmin算法主要是把任务分配到了运算能力较为强大的Vm3和Vm4上，Vm0和Vm1所分配到的任务个数显然偏少，算法的负载均衡能力不好。

　　对于FCFS算法，它将大量的任务分配到了运算能力低下的节点Vm0和Vm1上。而能力相对强大的Vm3和Vm4的几个节点相对而言几乎没有分配到任务，因此，该算法的负载均衡能力也不好。

　　最后，对于本文提出的新算法，各节点获得的任务数量较为平均，相对于另外两个算法，负载均衡能力明显有了提升。这是因为优化后的算法采用的策略是将任务放在本地数据上进行处理，即把任务分配到了数据所在资源上，而不是把数据传输到效益度较高的资源上进行处理。

4总结

　　本文提出了资源效益度概念，用于量化系统中各个资源节点，以此作为选择任务分配时的重要依据。对于资源效益度，用户可以根据不同的任务情况，随时改变它的量化标准，从而灵活调整任务分配的策略。文章通过DAG模拟了日常生产中所遇到的输入任务情况，并提出了基于DAG任务的调度算法。通过加入效益度函数对原有算法进行了优化。

　　实验结果表明，新算法可以显著降低网络负载，并且在输入DAG任务规模不太大的时候，通过牺牲部分任务完成时间显著提高了云计算系统的任务负载均衡能力。为云计算环境下DAG任务调度策略的研究提出了新的解决思路。

参考文献

　　［1］ ARMBRUST M, FOX O, GRIFFITH R, et al. Above the clouds: a view of cloud computing［J］. Eecs Department University of California Berkeley, 2009, 53(4):5058.

　　［2］ 梁钢, 茅秋吟. 云计算IaaS平台的信息安全和运维服务设计［J］. 电子技术应用, 2013, 39(7):6364.

　　［3］ 徐忠胜,沈苏彬.一种云计算资源的多目标优化的调度方法［J］.微型机与应用,2015,34(13):1720.

　　［4］ STANZANI S L, SATO L M, NETTO M A S. Scheduling workflows in multicluster environments［C］.Advanced Information Networking and Applications Workshops (WAINA), 2013 27th International Conference on. IEEE, 2013: 560565.

　　［5］ CHOPRA N, SINGH S. HEFT based workflow scheduling algorithm for cost optimization within deadline in hybrid clouds［C］.2013 Fourth International Conference on Computing, Communications and Networking Technologies (ICCCNT). IEEE, 2013: 16.

　　［6］ ELZEKI O M, RESHAD M Z, ELSOUD M A. Improved maxmin algorithm in cloud computing［J］. International Journal of Computer Applications, 2012, 50(12): 2227.

　　［7］ 田国忠. 多 DAG 共享资源调度的若干问题研究［D］. 北京: 北京工业大学, 2014.

　　［8］ KOKILAVANI T, GEORGE AMALARETHNAM D I. Load balanced MinMin algorithm for static Metatask scheduling in grid computing［J］. International Journal of Computer Applications, 2011,20(2):4349.

　　［9］ 程春玲, 张登银, 徐玉,等. 一种面向云计算的分态式自适应负载均衡策略［J］. 南京邮电大学学报：自然科学版, 2012(4):5358.

　　［10］ 唐一韬, 黄晶, 肖球. 一种基于DAG的MapReduce任务调度算法［J］. 计算机科学, 2014, 41(S1):4246.