云环境中DAG调度算法的设计与实现

年4月19日云环境中DAG调度算法的设计与实现文档仅供参考大连理工大学本科毕业设计（论文）云环境中DAG调度算法的设计与实现DesignandImplementationofDAGSchedulingAlgorithmsinCloudEnvironment学院（系）：计算机科学与技术学院专业：计算机科学与技术学生姓名：xxx学号：xxxxxxxx指导教师：xxx评阅教师：完成日期：大连理工大学DalianUniversityofTechnology摘要近年来随着网格、云计算工作流等异构分布式计算技术的发展，关于多DAG共享异构分布式资源的调度问题逐渐成为备受关注的研究热点。当前，尽管有关多DAG共享异构分布式资源调度的研究取得了一定进展，但仍有很多问题亟待进一步研究和解决。本文围绕多DAG共享异构分布式资源调度的若干问题展开了研究，这些问题包括：具有多优先级的多DAG调度和具有期限约束的多DAG调度吞吐量最大化、费用优化以及费用优化的公平性等。对这些问题的解决将有利于提高网格、云计算工作流等异构分布式计算系统的资源利用率、合理处理多个DAG应用之间的调度关系和有效降低用户DAG应用的费用，因此有着重要的理论意义和应用价值。关于DAG共享异构分布式资源调度的研究主要是关于DAG调度算法的研究。本文使用Java语言实现了经典DAG静态调度算法HEFT、CPOP和LBP，还实现了侧重公平性的E-Fairness算法，最后实现了混合调度算法MMHS。在实现这些算法的基础上，还测试这些算法的相关性能，如调度时间和公平性等。同时实现了DAG调度仿真器，在仿真器基础上，能够方便地进行各种算法的研究，而且方便做算法性能的实验测试。关键词：多DAG调度;多优先级;公平性;仿真器DesignandImplementationofDAGSchedulingAlgorithmsinCloudEnvironmentAbstractInrecentyears,withthegrid,cloudcomputingworkflowsandotherheterogeneousdistributedcomputingtechnology,schedulingofmultipleDAGssharingonheterogeneousdistributedresourcesisbecomingahottopicofconcern.Atpresent,despiteaboutmultipleDAGssharingonHeterogeneousDistributedResourceSchedulerhasmadesomeprogress,buttherearestillmanyproblemstobefurtherstudiedandresolved.ThispaperfocusesonanumberofissuesmoreDAGsharingonHeterogeneousDistributedResourceScheduling.Theseissuesinclude:amulti-priorityDAGschedulinganddeadlineconstraintshavemultipleDAGsschedulingtomaximizethroughput,costoptimizationandcostoptimizationofthefairandsoon.Solvingtheseproblemswillhelpimprovegrid,cloudcomputingresourceutilization,workflowandotherheterogeneousdistributedcomputingsystems,rationaltreatmentofmultipleDAGsschedulingrelationshipbetweenapplicationsandreduceuserDAGapplicationfee,sotherearetheoreticalsignificanceandapplicationvalue.ResearchontheDAGshareinHeterogeneousDistributedResourceSchedulingisresearchonDAGschedulingalgorithm.ThisarticleusestheJavalanguagetoachieveaclassicDAGstaticschedulingalgorithmHEFT,CPOPandLBP,butalsotoimplementafocusedequityE-Fairnessalgorithm,andfinallyrealizethehybridschedulingalgorithmMMHS.Onthebasisofthesealgorithms,butalsotesttherelativeperformanceofthesealgorithms,suchasthescheduledtimeandequity.WhileachievingtheDAGschedulingsimulator,asimulatorbasedon,itcaneasilystudyvariousalgorithms,andeasytodoexperimentstotestthealgorithmperformance.KeyWords：multiDAGsscheduling;multipriority;fairness目录摘要 IAbstract II引言 11绪论 21.1研究背景 21.2研究现状 32相关定义及理论 82.1DAG任务调度模型 82.2计算环境的异构性 92.3云环境下任务调度算法概述 92.3.1云环境下任务调度技术综述 102.3.2云环境下任务调度过程 102.3.3云环境下任务调度系统 112.3.4云环境下任务调度特点 122.3.5云环境下任务调度算法 123静态DAG任务调度算法 153.1实验环境简介 153.2静态调度算法HEFT 153.3静态调度算法CPOP 163.4基于表调度的任务调度算法LBP 183.5算法的时间复杂度和调度性能比较 193.5.1时间复杂度 193.5.2调度性能 203.6实验与分析 204具有多优先级的多DAG混合调度 214.1具有多优先级的多DAG调度系统模型 214.2多DAG公平调度E-Fairness改进算法 234.3多DAG的Backfill算法的实现 264.4具有多优先级的多DAG混合调度策略MMHS 274.5实验与分析 294.5.1相关的两个DAG的调度实验 294.5.2多个随机DAG的调度实验结果分析 31结论 33参考文献 34附录AMMHS算法核心代码 36致谢 39引言近年来，随着一些异构分布式计算环境工作流系统技术的发展（如网格、云计算或混合云计算工作流系统），作为这些工作流管理系统的关键技术之一的多个DAG任务共享异构分布式资源的调度问题引起了研究者们的关注。很多的工作流任务及任务间的依赖约束关系都可由有向无环图DAG（DirectAcyclicGraph）来表示[1]。当前有关多个DAG任务共享资源调度的研究在执行时间最小化（MakespanMinimization）、公平性最大化（FairnessMaximization）、吞吐量最大化（ThroughputMaximization）以及资源分配优化（ResourceAllocationOptimization）等方面已经取得了一些进展。在网格、云计算或混合云计算等平台的工作流的研究领域中，关于有最晚完成期限约束的DAG调度问题也引起了研究者们的关注。在这些新型异构分布式应用环境下，由于资源提供者往往会根据所提供的资源类型、服务质量QoS（QualityofService）和用户使用（或租用）资源的总时长进行计费，用户考虑到经济费用等因素，往往会根据应用的需求为DAG应用指定一个最晚完成期限Deadline，而并不要求DAG在最短时间内完成，这样就需要工作流调度系统能够根据用户指定的最晚完成期限尽可能为用户的DAG任务选择经济费用最低的资源。针对有期限约束的DAG任务调度及其费用优化，相关研究提出了一些算法和解决方案。这些关于有Deadline约束的DAG调度算法大多都有一个“Deadline分配”的重要步骤，也就是用不同的方法将整个DAG的Deadline分配到各任务（或任务区间）上，然后根据任务所分配的时间窗口尽可能选择较便宜（因而速度也较慢）的资源进行费用优化。近年来，关于单个DAG在异构分布式环境下的调度研究已经取得了很大进展[2-9]，但这些算法不能直接运用于多DAG的调度，针对多个DAG工作流调度的研究还处于探索阶段。现有相关的多DAG调度模型与算法尽管提出和解决了一些重要的问题，但对更为复杂情况下的多DAG调度，如多个用户可能会在不同时间提交DAG，且用户对DAG执行时间的要求可能差异较大，如何处理好已被部分调度执行的DAG和新到达DAG中各任务之间的关系，以更好地兼顾多个DAG之间调度的公平性和资源利用率的改进等问题，还没有得到较好的解决。适用于异构分布式环境下多个不同DAG随机提交的多优先级DAG调度模型和算法被提出。正是在这样的研究背景下，本文围绕异构分布式计算环境下具有不同QoS需求类型的多个DAG共享资源的调度问题、具有期限约束的多DAG共享资源调度的吞吐量最大化问题、总费用优化问题和费用优化的公平性问题等四个方面的内容展开了我们的研究工作。1绪论1.1研究背景任务调度问题是分布式计算领域中的基本问题。根据被调度的任务之间是否存在相关依赖关系，任务调度可分为独立的任务调度和相关的任务调度（有时也被称为依赖任务调度）。其中相关的任务是由一组既有前后数据传递约束关系，又有并行关系的多个任务组成，一般可由有向无环图任务图来表示。为了提高系统效率，这些DAG类型的任务中的子结点任务往往需要在多个处理单元或多个计算机所组成的资源系统上协同完成。近些年来，随着网络和科学技术的发展，特别是一些大型的科学计算、应用及信息处理如果仅依靠一台计算机不容易解决，就需要利用多个计算机资源来共同完成。比如要统计过去1年间9000篇（或者更多）科技论文中的高频词，以便分析近期研究热点。如果只有1台计算机运行这项工作任务，只能将所有论文按某种顺序遍历一遍进行统计或者编制多线程程序来并行执行以提高遍历效率。然而，如果有N台运算能力可能互不相同的经过网络互联的计算机能同时为这项工作任务服务，这9000篇论文就能够分解成N份，让这N台计算机并行遍历统计，效率和速度将大大提高。在这一过程中，这项工作能够分解为以下一些子任务：在其中某台计算机上进行“所有论文遍历任务的分发”、每台计算机被分配的“遍历统计”和某台计算机的最后“汇总统计”，那么这些子任务结点及其数据传递关系就构成了一个DAG任务图。在这个图中，多个任务的执行有一定的先后约束和数据传递的关系，如某台计算机被分配的“遍历统计任务”必须要在“论文遍历任务的分发任务”结束，并将必要的数据送达该机器后才能开始执行就是这种约束关系的体现。类似地，在物理、天文、生物、工程等很多领域的一些大型科学计算问题也能够转化为相应的DAG任务，而且这些领域的计算规模日益增大，计算流程日益复杂，更需要多计算机资源的并行执行和协同工作来解决有关问题。近年来，随着网格和云计算的应用和发展，为这种大型科学计算应用需要提供了良好平台。这些平台都能经过网络为这类需要多计算机资源协同工作的应用系统提供由大量高性能的异构分布式资源所构成的资源池，使应用系统能够根据应用需要获取计算力、存储空间和各种软件服务。特别是当前研究和发展中的网格工作流或云计算工作流系统，不但能够对这些大型计算的DAG任务进行构建、调度执行、监控管理，还能够利用和管理网格和云计算所提供的大量计算资源，并在一些科学计算领域实现了对这类DAG任务计算的自动化运行。然而，实现这些系统服务和服务效率的高低很大程度上取决于DAG任务调度方法的好坏。要将DAG中的多个子结点任务调度映射到多个计算机资源上，不但要考虑不同计算机的处理能力不同，而且计算机资源间的网络通信速率也可能不同，因此是个复杂的问题。如何为这些DAG任务选择合适的资源，将这些DAG任务分配映射到网络中的多个计算资源上，以达到DAG任务的完成时间最小化等调度目标，即可归结DAG任务在异构分布式计算系统上的调度问题。关于DAG任务的调度，近年来引起了国内外研究者们的广泛关注。当前很多关于DAG任务调度方法被提出，而且所采用的调度技术和解决问题的角度各有不同。其中有一些已成功应用于实际的网格或云计算等工作流调度系统中，如H.Topcuoglu于提出的异构分布式计算系统DAG任务调度模型及其著名的HEFT调度算法已被实际应用在了ASKALON网格工作流系统中。然而，由于网格、云计算或混合云计算等异构分布式计算系统应用的发展及其追求更低成本和提高资源利用率的需要，必然会要涉及到处理来自多个不同用（租）户的DAG应用任务共享同一组资源的调度问题，而且这些应用的DAG结构类型、服务质量QoS要求（一般包括完成时间、经济花费、可靠性和安全性等几方面）也会多种多样，这必将会产生多个DAG对系统资源的争用、完成时间的最小化、调度的公平性、费用优化和资源利用的提高等问题。针对多个DAG应用任务共享一组资源调度的这些问题，近几年一些研究者们提出了一些相关的解决办法，但由于这类调度问题研究才起步，有很多新问题亟待进一步研究和解决。对这些问题的研究和解决，将会对网格、云计算或混合云计算等异构分布式计算环境下的多用（租）户DAG应用发展起到积极推动作用，不但具有理论研究价值，也有现实的应用价值。正是在这样的研究背景下，本文围绕异构分布式计算环境下具有不同QoS需求类型的多个DAG共享资源的调度问题、具有期限约束的多DAG共享资源调度的吞吐量最大化问题、总费用优化问题和费用优化的公平性问题等四个方面的内容展开了我们的研究工作。1.2研究现状各种类型的DAG任务在多个处理单元上的调度已被证明是NP（Non-deterministicPolynomial）完全难题，即完全多项式非确定性问题。早在70年代开始就有学者针对各种类型的DAG任务模型在各种资源环境模型下调度的有关问题进行展开了研究。当前尽管对DAG调度已经有了很多研究成果，但国内外学者仍在继续不断地对其进行深入探索和研究。这些相关的研究成果，无论是从被调度对象的DAG任务类型、目标资源环境和调度目标等几方面的模型来看，还是从解决问题所采用的技术方法或数学模型上来看，都有很多的分类。首先从被调度对象的DAG类型、资源环境和调度目标等方面能够做以下一些归类：（1）从用户对DAG应用的起始和结束时间是否有限制来看，一般可分为无期限约束的DAG调度和具有期限约束的DAG调度。如前所述，在ASKALON网格工作流系统的工作流定义工具AGWL中，作为可选项，用户可根据应用的需要来指定工作流的最晚完成时间等服务质量（QoS）。那么这种带有确定的最晚完成时间期限约束的DAG则属于有期限约束类型的DAG。（2）从调度目标环境的可用资源数目是否固定来说，可分为数目固定和不固定两类。针对资源数目不固定类型的DAG调度方法和技术适用于资源数量可随DAG调度应用需要动态扩展的分布式系统。比如针对云计算环境的动态弹性资源管理模式，以减少任务间数据传递的聚簇方法或以减少资源数量为目标的调度算法可归为这一类。（3）从DAG图中的每个结点任务是否能够继续被分割而且能并行在任意数目机器上执行来看，DAG任务模型又可分为Moldable和Unmoldable两种类型。一般来说，数据集的处理、Web访问日志分析等作业任务能够将任务根据并行处理资源结点数量被分为若干等分，可归为Moldable类型的DAG任务。很多著名的算法，如DSC、HEFT算法所针正确是Unmoldable类型的DAG。然而，两种类型DAG的调度相比，Unmoldable类型DAG的调度方法是基础，多数现有针对Moldable类型问题的方法和技术都是在Unmoldable类型DAG调度方法的基础上进行改进和扩展而来。实际上由于现实资源数量的有限性和结点任务粒度大小的相对性，Moldable类型的DAG调度最终仍可归为Unmoldable类型DAG的调度问题。（4）从任务的调度映射方案是否在DAG执行开始前就已确定来看，有动态调度和静态调度两类算法。静态调度算法是指在DAG执行前依据当前有效的可用计算资源和任务的相关信息，依据一定的方法确定好调度方案和映射关系的方法。这类算法有很多，常见的列表启发式类算法均属静态类。而动态算法则是指系统运行过程中动态地为DAG任务进行调度和资源分配的方法。（5）根据DAG任务是否包含必要和非必要计算成分，可分为精确计算DAG和非精确计算DAG任务的调度算法。一般来说，在实时的视频和声音等信息处理中常见这类非精确计算DAG任务。（6）依据DAG任务本身大小是否具有随机性，可分为随机DAG调度和非随机DAG调度，而与随机DAG调度算法密切相关的调度目标之一则是对算法鲁棒性（Robustness）的评价。对随机DAG调度的鲁棒性分析或旨在改进调度鲁棒性算法认为：DAG中的任务本身由于输入条件不同或程序类型等不同（如随机搜索类的遗传算法程序），在执行前是无法确定DAG的形状、结构或运算量，或者由于资源在不同时间执行同一任务所需时间的不确定等因素，进而造成DAG任务大小的随机性，因此需要根据任务的随机分布或资源状态的分布函数来优化DAG任务调度。（7）从系统资源管理方面来看，能够分为根据计算环境中资源的可靠性而展开的资源分配、调度算法的研究和考虑资源负载平衡而展开的调度优化的研究。（8）根据多个DAG应用是否为共享资源，可分为单DAG和多DAG调度。为了追求更低的成本和资源共享的需要，其中有关多用（租）户的多DAG共享资源的调度成为近几年来的热点研究问题。DAG应用任务不同于独立的任务调度，DAG的任务结点之间的数据传递依赖关系和网络传递的时延会造成任务在各分布式资源上留下很多的空闲时隙，如果多个DAG共享资源混合调度，则这些空闲时隙能被多个DAG相互利用，将大大提高资源的利用效率。其次，从所采用的技术方法或数学模型角度来看，主要有以下几类：（1）Markov决策过程方法。主要用于解决具有期限约束的单个DAG调度及其费用优化的问题。主要思想是用Markov决策过程方法将整个DAG划分为若干任务区间，如果能保证每一个任务区间在各自的限制时间段内完成，则工作流即可在约束的期限之前完成，进而可求出最小费用的任务资源映射方案。（2）列表启发式方法。列表启发式方法的主要步骤是在DAG中所有的任务被赋予属性并按照属性优先级的大小降序放在任务表中，一旦任务要求被处理，高优先级的任务首先被调度。很多文献等所提出的算法都属于这类方法，其中包括H.Topcuoglu所提出的著名HEFT算法。其主要思想分为两个阶段，第一阶段是根据任务的执行时间以及与后继任务的数据传输时间计算得到这个任务的Ranku值（该任务结点到出口结点之间的最大距离，在有些文献中也被记为B-level），将其作为调度优先级，然后根据ranku值对DAG中的任务进行倒序排序。第二个阶段是根据第一个阶段得到的任务排序，选取未被调度的任务中优先级最高的任务，然后遍历所有可用资源，查找到能够最早完成处理该任务的计算资源，并将该任务分配到资源上相应的空闲时隙中。（3）遗传、进化等随机搜索类方法。遗传算法是当前广泛使用的解决优化组合的算法之一。它借鉴了生物学中遗传过程中“适者生存”的概念。遗传算法首先假定潜在的资源分配或任务映射匹配解决方案能够表示为遗传参数的组合，成为染色体。能够任意选择一定数量的染色体，然后所有染色体基于她们的值排队，一般使用轮转法选择合适的染色体，这能保证最合适的个体得到保留并作为父本。两个被选中的染色体能够进行交叉配对复制产生后代。染色体复制会发生突变从而产生新个体。经过上述过程的多次重复，产生新的染色体会逐渐接近最优解。另外，应用于DAG调度的其它随机搜索类的方法还有进化算法、蚁群、粒子群等算法。虽然随机搜索类算法适用范围广，但一般来说时间复杂度较高。（4）任务复制方法类。任务的复制减少数据传输的时间，利用计算资源的空闲时间复制前驱任务，以避免某些前驱任务的数据传输时间过长，从而减小计算资源等待的空闲时隙。（5）排队论方法类。利用排队论的有关模型来解决DAG调度中资源优化或资源预定的相关问题。针对有时间限制网格工作流的DAG任务调度，提出了利用“M/M/1/N/∞排队论模型”和“Little公式”计算DAG中每个任务结点在每个资源上执行时间超过期限约束的概率大小，然后进行资源优化，最终确定任务和资源的映射调度方案。（6）模糊理论及模糊聚类方法。模糊理论一般用于随机DAG调度问题。针对任务执行时间不确定的随机DAG调度问题展开研究，利用模糊集扩展原理推算出DAG的关键路径长度可能性的分布和可能的关键任务组合，并在调度和监控中，对那些尽管不是关键路径任务，但其隶属程度高的任务与关键路径任务一起给予同等重要的考虑。而模糊聚类方法常见于根据DAG调度目标环境中的计算资源相关非功能属性进行聚类并进行资源优化处理。（7）随机过程模型方法类。利用离散时间Markov随机过程的遍历性或平稳分布的方法进行DAG吞吐量的优化，或者利用有限状态连续时间的Markov随机过程模型的有关方法对DAG中的关键区间任务进行资源状态预测和资源可靠性的优化。（8）调度回溯方法类。该类方法一般用于解决DAG调度的费用优化问题。核心思想是，在对DAG中每个任务进行资源映射的过程中，如果对某任务分配了速度较慢而且花费便宜的资源后，需要计算整个DAG的完成时间是否超出了时间限制。如果超出，则取消该任务在这较慢资源上的分配，直到选择到合适的资源为止。以上为现有DAG调度问题研究中常见的一些技术和方法。随着网格、云计算和混合云计算等新型异构分布式系统研究和应用的发展，根据系统的资源结构、资源管理模式、商业计费模式、资源可靠性等方面所呈现出的不同特点，现有这些解决DAG调度问题的研究基本上又以以下其中一个或若干个为调度目标：调度长度最小化、吞吐量最大化、资源利用率最大化、费用最低化、资源负载平衡、可靠性最大化、公平性最大化、达到较好的鲁棒性或满足用户指定的期限约束要求等。随着新技术的不断出现和研究的进一步发展，新的调度目标也将会不断地出现，而且很多调度目标往往会相互冲突，需要根据具体应用任务的需要和资源环境模型来确定或者进行一定的平衡。当前现有DAG任务调度的研究绝大多数是针对一个DAG在多个资源上调度问题。这些研究针对不同类型的DAG应用、不同的目标资源系统和不同的调度目标，以不同的技术方法解决了单DAG应用任务调度中各方面的问题，已基本趋于成熟。然而，随着异构分布式计算环境下的各种应用深入和发展，特别是随着网格和云计算工作流等应用系统追求更低成本和资源共享的需要，必然会涉及到处理来自多用（租）户的多DAG共享一组异构分布式计算资源的调度问题。如中科院计算所的韩艳波研究员在关于互联网分布式系统的XaaS（一切皆服务）模式第三方运营与优化的论著中指出：同一个物理平台或应用要服务尽可能多的租户，计算、存储和带宽资源在多个应用程序间进行共享和优化调度，并进一步提出了多个租户共享同一个工作流引擎，但每个租户都能够定义不相同工作流的多工作流共享资源的应用模式。另外，PeterKacsuk也将工作流管理平台分为两大类：如果多用户同时以协作的方式监控、控制和执行同一个任务图，则称为MC类型；如果所管理运行的多用户之间不同的多个工作流DAG任务图互相独立，则称为MI类型，即多DAG工作流系统。因此研究和解决多DAG共享资源调度问题对异构（或互联网）分布式计算系统未来的发展具有重要的意义。尽管很多现有的解决单DAG调度问题的技术方法能够用于多DAG的调度，如处理多DAG调度的一个最直接简单的办法是，利用传统单个DAG调度算法将这多个DAG逐次按顺序调度完毕，或者是对新到达的DAG应用执行需求，经过采取申请新资源的办法来进行调度，如Mao等针对云计算工作流的多个DAG应用的调度执行问题，就采取了这种方式。然而，由于DAG任务与多个独立任务调度的最大区别在于每个DAG内部的任务之间有前后约束关系，而且任务间有数据传递关系。在一些异构分布式系统中，比如效用网格或公有云计算系统，资源提供商往往采用基于租赁的销售模式以及基于使用量和性能指标的计费模式对用户DAG应用执行所提供的计算服务进行计费。因此，针对网格或者云计算等分布式计算系统下单个具有期限约束的DAG应用或工作流调度问题，相关研究的主要调度目标之一就是费用最小化。同样，当多个DAG共享一组资源进行混合调度时，也会存在在满足期限内完成条件下所有DAG总费用最小化问题，然而当前也未见对这一问题展开研究和讨论的报导。当具有期限约束的多个DAG在共享的资源组上进行混合调度时，显然DAG吞吐量越大，DAG任务的费用优化空间越小。换句话说，DAG的吞吐量调度目标与DAG费用优化的目标是相矛盾的，存在根据具体系统或应用需要对两个调度目标进行平衡的问题。然而从系统管理的角度来看，吞吐量最大化是一个重要的目标，因此在DAG吞吐量最大化基础上降低所有DAG任务的费用是需要研究和解决的重要问题之一。不论选取何种DAG调度算法，由于这种数据传递关系，总会在资源上出现空闲时隙，那么便会降低DAG调度的任务吞吐量和资源利用率。如果将多个DAG共享资源进行混合调度，一个DAG的任务会利用其它DAG任务所留下的空闲时隙，将大大提高资源的利用率和任务吞吐量。因此，近年来多DAG共享资源的调度问题成为了研究热点。

2相关定义及理论2.1DAG任务调度模型一个并行程序能够抽象为一个带偏序的任务集，该任务集合可完全由一个有向无环图DAG来表示，定义为：G＝（T，E）。其中，T＝{Ti│i=1，2，…，n}，表示n个任务节点的集合，|T|＝n；E＝{Eij=（Ti，Tj）|Ti，Tj∈T，i<j}，表示拥有e条边的有向边集合，|E|＝e。DAG中每个节点表示并行程序的一个任务，它一般是程序中的一段代码或指令，是调度中的最小单位，假设它是不能被抢占的。节点Ti的权重称为计算成本，记作W（Ti）；DAG中的任意一条边，记作Eij或（Ti，Tj），表示节点Ti和Tj之间存在时间上的先后关系和通信关系，每条边的权重称为通信成本，记作C（Eij）或C（Ti，Tj）。一条边的源节点称为父节点，而其终点节点称为子节点。在DAG中，没有父节点的节点称为入口节点，而没有子节点的节点称为出口节点。如果在一个DAG中，不止一个入口节点，那么我们虚构一个零计算成本的入口节点，所有真正的入口节点经过一条权值为零的虚边与其相连；同样，如果不止一个出口节点，就虚构一个零计算成本的出口节点，所有真正的出口节点都与它经过权值为零的虚边相连。因此，任何一个DAG，都可看作只有一个入口节点和一个出口节点。显而易见，增加虚拟节点和虚拟边并不影响对DAG的调度。图2.1是一个普通的DAG，图中圆圈表示节点，圆圈中符号表示任务节点编号，圆圈外左边方框中数字表示该节点的计算成本；图中带箭头的边表示通信边，边上的数字表示两个节点之间的计算成本。节点T1为入口节点，节点T10为出口节点。图2.1一个普通的DAG图2.2计算环境的异构性一个异构的并行计算系统定义[10-11]为：由一组异构的计算节点和异构的互联网络形成的计算环境。计算节点的异构性指其资源各方面的差异性，包括处理器处理能力的差异、内存大小及访问的差异、I/O访问速度的差异以及操作系统的不同等等，本文讨论的调度问题范围仅限于处理器资源的调度。异构网络指连接计算节点之间的互联网络由不同类型的网络组成，例如能够是以太网或者是Myrinet等等。类似于并行程序能够表示为DAG，一个异构的计算系统也能够表示为一个无向图。其定义为：R＝（P，L）。其中，P＝{Pk│k=1，2，…，m}，表示m个处理器集合，其中，Pk是异构计算系统中任一处理器，|P|=m；L＝{Lij=（Pi，Pj）|Pi，Pj∈P，i≠j}，表示计算节点之间通信连接边的集合，其中，Lij或（Pi，Pj）表示计算节点Pi和Pj之间的物理通信连接。如何量化地表示处理器处理能力的差异性。有两种方法：第一种是以处理器的主频作为度量处理器计算能力的唯一标准，对任何类型的任务来说，处理器的物理速度越快，其处理任务的时间越短；另一种方法是处理器与计算的任务结合起来考虑，即处理器对任务的计算时间并不与处理器的主频呈固定的比例，一些处理器更适合计算某种类型的任务而不适合计算另一类任务，适合与否并不以其物理速度为准。第二种方法与实际情况更符合，也更复杂，因此我们采用第二种方法。因此，处理器计算能力的差异性度量值记作：W（Ti：Pk），表示任务Ti在处理器Pk上的计算时间，表2.1列出了图2.1中DAG中任务节点在三个处理器组成的处理器组中的W（Ti：Pk）。表2.1图2.1中DAG的W（Ti：Pk）Ti12345678910P1141311131213751821P2161913813161511127P3918197109111420162.3云环境下任务调度算法概述由于云环境下资源的分布性、异构性和动态性，以及用户的数量、用户应用程序对资源的需求等都在不断变化，使得任务调度变得极其重要、极其复杂，因此需要动态调度任务、动态划分或释放不同的物理和虚拟资源来适应动态变化的环境。对此，国内外己做了大量的研究工作，先后提出了各种调度算法。本节首先概述性的介绍了云环境下的任务调度。其次对云环境下的任务调度过程、任务调度系统、任务调度特点及一些经典的关于单DAG、多DAG工作流的调度算法进行了讨论。2.3.1云环境下任务调度技术综述云环境下任务调度系统一般由三个部分组成[12]：（1）资源筛选：在所有可用的空闲资源中找出满足用户需求的资源；（2）任务-资源映射：从满足要求的资源中选择一个合适的资源分配给相应的任务，实现任务和资源一一对应的关系；（3）任务执行：把任务调度到映射的资源上去执行。云环境下的作业调度分本地调度和网格调度两个阶段。本地调度又称为低级调度，当收到用户提交的DAG工作流时，优先选择本地的资源对其进行调度执行。网格调度又称为高级调度，网格调度器并不直接控制系统中的各个资源[13]，而是动态的根据任务对资源的具体需求，为其选择最适合的计算资源，这样，能够使资源的使用不受所属区域的限制，提高资源的利用率，充分利用不同地域资源的优势，最大限度的实现各地资源的协同工作。2.3.2云环境下任务调度过程在云环境下，用户提交的DAG工作流一般由一个工作流管理系统统一进行管理和调度。从系统管理方面来看，工作流管理系统负责处理用户工作流的提交、资源管理和分配、数据移动和工作流的调度，而且尽可能地提高资源的利用率和工作流任务的吞吐量。当前的通用模式是将大型的应用任务分解为多个相关的子任务，其中每个子任务都有独特的资源需求，然后将子任务提交到调度系统进行调度。根据任务之间是否存在数据依赖关系，可将任务分为两种类型：（1）依赖任务：即任务之间存在依赖和先后时序的关系，一般见DAG图来描述任务之间的这种依赖关系，而且采用各种启发式思想对映射问题进行简化[14-15]。（2）元任务（MetaTask）[16]：即相互之间独立的任务，任务之间不存在数据依赖关系，任务的调度执行相互之间不受影响。图2.2对云环境下任务调度的过程进行了描述。其中资源监控与发现服务MDS（MonitoringandDiscoveryService）的作用是收集和发布系统中的资源状态信息。图2.2云环境下任务调度流程图2.3.3云环境下任务调度系统当前，云技术在诸多领域都得到了广泛应用，针对各种不同的云应用，提出了许多有效的云环境下任务调度模型和算法。下面将对几个比较流行的任务调度系统进行简单的介绍：Globus：此项目是由美国Argonne实验室等进行研发的，Globus对信息安全、信息服务、资源管理、数据管理以及开发环境等关键理论和技术进行了深入研究，并开发了软件包，能够在多种平台上运行。Globus的资源描述与访问采用可扩展式模型、分布式基于查询的发现、层次命名空间、软QoS、LDAP网络目录存储、周期性推送分发；资源管理体系结构采用典型的层次模型等。Nimrod/G：由澳大利亚的Monash大学开发，它采用Globus中间件作为网格接口，基于经济模型提供一系列计算资源。它遵循层次的、分布式的调度模型，并采用由预算和截止期限所驱动的应用级任务调度策略等，但Nimrod/G不能进行有效的资源计费。P-GRADE平台：P-GRADE平台支持多个DAG工作流在执行过程中所用的资源之间具有互操作性，而且支持多个不同的用户以协作的方式来完成各自的DAG工作流。该平台具备以下功能：（1）分类并定义具体的云环境；（2）创立并修改工作流的应用；（3）管理云环境的相关证书；（4）控制工作流在云资源中的运行过程；（5）监督并实时观察工作流及其子任务的执行进展。另外还存在GHS、E-Science、DataGrid、Webflow、AppLeS等多种调度系统，在此不再作介绍。2.3.4云环境下任务调度特点云环境下任务调度具有以下几个特点：（1）任务调度是在异构的平台上进行的。云系统是由分布在广域网上的各种类型的个人计算机、工作站、大型的机群、大型存储设备、服务器或其它精密的仪器等组成的，可运行在UNIX，Windows等各种操作系统下，因此云系统中的任务调度必须考虑平台的异构性。（2）任务调度能够动态自适应。云中的资源不但是异构的，而且云的系统结构总是在不断地变化，随时有新的资源加入系统、退出系统、有资源出现故障等，且用户对资源的需求也是动态变化的，因此任务调度必须能够满足这种动态特性，从而为用户提供更好的服务。（3）任务调度是分布式的。云系统的分布式特性，使其很难实现全局的统一集中的资源管理以及任务调度管理，因此，任务调度必须是分布式的，从而避免造成系统瓶颈。（4）任务调度必须满足系统不断扩展的要求。随着资源共享的程度越来越高，云系统的规模必将不断扩大，因此，在资源数量和用户的应用不断增长的情况下，云系统的任务调度必须具有可扩展性。2.3.5云环境下任务调度算法早期的任务调度算法主要考虑网格资源的分布性与异构性，称为异构环境下的独立任务调度算法，包括OLB（OpportunisticLoadBalancing）、Round-RobinAlgorithm、MET（MinimumExecutionTime）、SA（SwitchingA1gorithm）、KPB（K-PercentBest）、Max-Min、Min-Min等等。这些算法一般仅仅优化了任务的某一方面，如执行时间跨度、负载平衡或任务吞吐量等。在异构环境中，启发式算法一般是用来解决元任务调度问题的有效方法之一，根据任务和资源的对应关系是否能够实时、动态的调整，将这些启发式任务调度算法划分为静态调度算法和动态调度算法两大类。静态调度算法是指任务和资源的对应关系在执行任务之前就已经全部确定，在整个执行任务的过程中不再做任何调整。常见的有Min-min、Max-min、P-timePetri网模型算法、任务截止时间限制下的MapReduce算法等静态调度算法。（1）Min-min：首先，计算每个任务在每个资源上的期望完成时间，根据计算结果可知每个任务的最早完成时间及其对应的资源；然后，将具有最小完成时间的任务分配给能够最早完成该任务的资源，同时，将已分配的任务从初始任务集合中删除；最后，每分配完一个任务就立即更新资源就绪时间。如此重复，直到全部任务分配完毕。（2）Max-min：Max-min算法与Min-min算法的思想基本相同，区别是Max-min算法优先考虑执行时间较长的任务，当获得每个任务的最早完成时间及其对应的资源时，不是将具有最小最早完成时间的任务进行分配，而是对具有最大最早完成时间的任务进行分配。（3）P-timePetri网模型算法：经典Petri网由两种节点（其中圆形节点代表库所，方形节点代表变迁）、有向弧（连接库所和变迁）、以及令牌等元素组成，Token是库所中的动态对象，能够从一个库所移动到另一个库所，两个库所或两个变迁之间不允许有弧，库所能够拥有任意数量的令牌。（4）任务截止时间限制下的MapReduce算法：任务截止时间限制下的MapReduce算法是在Hadoop平台上实现的。该算法允许用户对任务限定一个最晚完成截止时间，经过计算资源节点的计算能力，对所有的资源进行分类，形成异构环境下不同计算能力、不同层次的资源组合，该算法能够优先利用本地数据资源，提高资源系统的吞吐量，而且该算法能够经过计算任务合成和任务分解之间的时隙，来选择合适的任务进行调度。接下来对动态调度算法进行简单的描述。动态调度算法是指，部分机器-任务映射策略在执行任务调度期间根据实际情况进行确定。现有的动态调度算法能够分为两类：在线模式和批模式（Batchmode）。在线模式的启发式动态任务调度算法，是指任务一经到达立即给它分配可用的资源。这类算法的环境适应性好、算法灵活、能有效的利用资源、避免先到达的任务必须等待一段时间、具有实时性的特点，典型的在线模式动态调度有OLB、MET、轮盘算法等。（1）OLB（OpportunisticLoadBalancing）算法：机会负载均衡算法是最简单的一种算法。该算法不考虑任务的预测执行时间，随机地将任务集合中的任意一个任务分配给机器资源集合中任一个可用的机器资源，充分的利用所有可用的机器资源，算法的实现比较简单；但该算法未考虑任务的预测执行时间，如果某个任务在某台机器上的执行时间过长，则会使整个任务的完成时间增加。（2）MET算法（MinimumExecutionTime）：MET算法是先计算出每个任务在每个机器资源上的执行时间；其次，找出每个任务所对应的具有最小预测执行时间的机器；最后以任意的顺序将各个任务分配给选定机器，MET算法的主要目的是把每个任务尽可能地分配给能够最快完成该任务的机器。（3）轮盘算法（Round-RobinAlgorithm）：轮盘算法是把到达的DAG工作流，经过添加一个入口节点和一个出口节点合并成一个新的DAG工作流，其中，入口节点与它的所有直接后继节点、出口节点与它的所有直接前驱节点之间的通信代价都为零。该算法在调度过程中，如果正在执行的任务属于某个DAG工作流，则在该时刻DAG工作流中的其它任务将不会被执行，即同一个DAG工作流中的任务不会同时被执行。该算法不适合处理对实时性要求比较高的DAG工作流调度。批模式的启发式动态任务调度算法是当任务集合中的任务数量达到一定的数量，或达到一个预定的时间间隔之后，才进行任务和资源的匹配。原则上，静态调度算法都能够用作批模式的算法。批模式算法最大的优点是实时性、高效性。典型的批模式调度算法有快速贪吃算法、最大时间跨度算法、令牌控制算法等。（1）快速贪吃算法（Fast-Greedy）：快速贪吃算法的基本思想是根据到达任务集合的顺序，计算出某个任务相对于所有机器的预测完成时间的最小值，以及具有最小值的机器编号，将该任务匹配给对应的机器。但由于该算法是按照任务到达的先后顺序进行资源分配的，可能会使后到达的任务因为长时间的等待而无法分配给真正能够使其完成时间最小的机器。（2）最大时间跨度算法（MaximumIntervalheuristic，Max-Int）：Max-Int算法计算每个任务的最小最早完成时间和对应的机器，以及该任务的次小最早完成时间和对应的机器，同时计算次小最早完成时间和最小最早完成时间的差，即时间跨度，根据时间跨度的大小对所有任务进行排序，将时间跨度最大的任务分配到获得最小最早完成时间的机器上。直到全部任务分配完毕。（3）令牌控制算法（TokenPlayerAlgorithm）：令牌控制算法在工作流的执行过程中能够检测出不正常现象，并经过诊断功能查找出现不正常现象的原因。当令牌可用时，判定是否支持变迁，若变迁不在系统冲突中，则初始化令牌，并产生一个新操作；若变迁在系统冲突中，则隔离该系统冲突，并判断能否取消该变迁。如果冲突解决机制在保证令牌可用的前提下，允许撤销变迁，则撤销该变迁，同时向系统发送一个初始化操作的新消息。3静态DAG任务调度算法3.1实验环境简介本文实现的算法均使用Java语言在Eclipse集成开发环境下完成。为了更好地实现算法性能的比较，需要一款界面友好的DAG调度仿真软件作为支撑，经过GUI界面的帮助能够更加高效地进行算法性能的比较。为此，我们开发了如图3.1的DAG调度仿真器。图3.1DAG调度仿真器该仿真器能实现多个DAG的随机生成，也支持XML格式的DAG文件的读入。然后DAG经过各个算法的处理，生成开销和时间等性能数据，再以文本和图表的格式显示出来。这样大大提高了算法的正确性验证和性能之间的横向比较。3.2静态调度算法HEFT算法HEFT[2]是一个处理器数目受限的异构处理器调度算法，算法分为两个主要的步骤：一是任务优先级别的确定，即计算所有任务的优先级别并根据优先级别排序；另一个是处理器的选择，即根据任务的优先级顺序把每个选择的任务调度到最适合的处理器上。HEFT调度算法步骤如图3.2所示。图3.2HEFT调度算法任务优先级别的确定：主要根据任务的Ranku值来确定任务的优先级别，任务的Ranku值是基于任务的平均计算成本和通信成本的，任务表是按照任务的Ranku值降序排列，即Ranku值最大的任务排在表头。如果有两个或两个以上的任务具有相同的Ranku值，那么采用随机选择的方式。从Ranku的定义来看，这种根据降序排列的方式满足了DAG中任务之间的优先关系。处理器的选择：处理器的选择最基本的原则就是把需调度的任务分配给能使任务完成时间最早的处理器。对于大多数任务调度算法来说，处理器P的最早可用时刻是处理器P完成了分配给它的最后一个任务的时刻。然而，算法HEFT不同的是它采用一个额外的插入策略，即可能在已经调度到同一个处理器上的两个任务之间插入当前调度任务，当然，在两个已经调度任务中间的时间空隙调度当前任务的原则是必须满足任务之间的优先关系。算法HEFT的时间复杂度为O（e×m），其中e是DAG中通信边的数目，而m是处理器数目。对于一个密集的任务图来说，通信边的数目是与成正比的（n是DAG中任务节点的数目），因此时间复杂度也等于O（×）。从一个典型例子的角度来看，算法HEFT应用于图2.1的DAG，得到的调度长度为80。算法HEFT对任务的调度顺序为：T1，T3，T4，T2，T5，T6，T9，T7，T8，T10。3.3静态调度算法CPOP同HEFT一样，算法CPOP[2]由确定任务优先级和处理器选择两个步骤组成。但确定任务优先级的方法和选择处理器的策略都与HEFT不同。CPOP调度算法如图3.3所示。图3.3CPOP调度算法任务优先级的确定：先计算任务的BLh和TLh值，两者之和作为任务的优先级值。如果任务的优先级值等于DAG的关键路径长度CP，那么该任务称为关键路径任务。毫无疑问，入口任务Tentry的优先级值等于关键路径长度CP，它是关键路径任务。在调度过程的任一时刻，任务优先级队列中包含所有就绪任务，采用了二元树结构来改进优先级队列的操作，因此在该优先级队列中插入和删除一个任务的时间是O（logn），而寻找最大值的时间是O（1）。处理器的选择：对关键路径任务和非关键路径任务采用不同的策略，关键路径任务只能被调度到关键路径处理器，而非关键路径任务能够调度到所有的处理器上。所谓关键路径处理器是指所有关键路径任务在其上执行时，计算成本之和最小的处理器。在对优先级队列中的任务调度时，如果选择的任务是关键路径任务，则把它分配给关键路径处理器；如果选择的任务不是关键路径任务，则按照HEFT算法的原则选择处理器，即选择使任务的完成时间最早的处理器。在调度关键路径任务和非关键路径任务时，都考虑与HEFT算法相同的插入策略。算法CPOP的时间复杂度也为O（e×m），证明从略。相对于图2.1的例子，采用CPOP算法的调度长度是86，关键路径任务是T1，T2，T9，T10，如果所有的关键路径任务分别调度到处理器P1，P2和P3上，则计算成本之和分别为66，54和63。因此P2被选为关键路径处理器。根据算法CPOP，图2.1中DAG的调度顺序为：T1，T2，T3，T7，T4，T5，T9，T6，T8，T10。3.4基于表调度的任务调度算法LBP绝大多数静态启发式的任务调度算法基于古典的表调度思想，其基本内容能够概括为两个独立的步骤。第一步：把任务图中的所有任务按照某种优先级的高低顺序排列成调度表。第二步：从调度表中依次取出各个任务，将任务分配到使它的完成时间最早的处理器上。HEFT算法就是典型的静态表调度算法。分析表调度算法的基本思想，我们认为在步骤一最关键的因素是如何选择任务的优先级别。决定任务优先级别时采用的两个最基本属性是T-LEVEL（任务Ti的T-LEVEL是指从入口任务到Ti的一条最长路径的长度）和B-LEVEL（任务Ti的B-LEVEL是指从任务Ti到出口任务的一条最长路径的长度），T-LEVEL值与任务的最早启动时间有很大的关系，而B-LEVEL值与任务图的关键路径有关。HEFT算法其实是采用B-LEVEL作为其任务的优先级别，只不过考虑到对任务Ti各个处理器的处理时间不同，在计算任务的处理时间时采用了所有处理器处理时间的平均值。对于步骤二来说，大部分算法都无异义，只不过有的算法允许在两个任务处理的时间间隙中插入当前任务，HEFT法即是如此，而有的算法只允许当前任务在所在处理器的最后一个任务后调度。前者调度开销明显比后者高。LBP[19]算法主要在步骤一作出了改进，在选择优先级属性时并不是单纯地采用T-LEVEL或者B-LEVEL。因为它们只是考虑了影响调度性能的一个方面，或者着重于单个任务必须尽早启动，或者着重于关键路径上的任务应尽早调度。但从整体来看，这些考虑都只可能是局部较优而非全局较优。LBP具体确定任务优先级的算法概括如下：第一步计算DAG图中每个任务的层次，某个任务Ti的层次值IL（Ti）为入口任务到Ti之间的边数之和(虚边不计算在内)，入口任务的层次值为零；第二步计算DAG图中每个任务的分支值，某个任务Ti的分支值B（Ti）为任务Ti的所有出口边权值之和；第三步根据任务Ti的层次值IL（Ti）和分支值B（Ti）来决定其优先级。层次值IL（Ti）越小其优先级越高，对具有同样层次值的任务来说，分支值B（Ti）越大其优先级越高。特殊情况（出现可能性较小）下，如果某些任务的层次和分支值都相同的话，则经过计算它们的T-LEVEL值（以Tl（Ti）表示）来决定优先级高低，Tl（Ti）值越小的任务优先级越高。包括决定调度表的优先级在内，整个LBP算法步骤如下：LBP算法1：计算DAG中所有任务Ti（i＝1，2，…，k）的层次值IL（Ti）、分支值B（Ti）T-LEVEL值Tl（Ti）；2：根据IL（Ti）、B（Ti）和Tl（Ti）的大小，依照相应策略计算任务Ti的优先级，然后把任务Ti按照优先级从大到小的顺序放入任务调度表；3：While任务调度表中存在没有被调度的任务Do4：从任务调度表中取出表头的任务Ti准备对其进行调度；5：For空闲主机集合中的每一个处理器Pj（j＝1，2，…，m）Do6：计算任务Ti在处理器Pj上的最早完成时间，在计算最早完成时间时不考虑在任意两个已调度任务的时间间隙中插入当前任务；7：把任务Ti调度到使其具有最小的最早完成时间的处理器上（如果两台或以上处理器具有相同的最小最早完成时间，则把调度到负载最轻的处理器上）；8：Endwhile3.5算法的时间复杂度和调度性能比较3.5.1时间复杂度HEFT和CPOP算法的时间复杂度为O（e×m），其中e为DAG中表示通信的总边数，m为工作处理器的总数。它们算法的时间复杂度主要反映在处理器的选择策略上，由于LBP算法与HEFT算法一样都是采用贪心算法选择处理器，不同之处在于HEFT算法考虑在任意两个已调度任务的时间间隙中插入当前任务，而LBP算法只考虑在所有处理器上的最后一个已调度任务后调度当前任务，因此LBP算法肯定不会比HEFT算法高，因此它的时间复杂度也是O（e×m）。3.5.2调度性能我们以调度长度这一反映调度性能的主要指标来评价LBP算法与HEFT及CPOP算法的好坏。对于同样的DAG（图2.1所示）和同样的工作处理器集合，HEFT的调度顺序是{T1，T3，T4，T2，T5，T6，T9，T7，T8，T10}，CPOP的调度顺序是{T1，T2，T3，T7，T4，T5，T9，T6，T8，T10}，而采用LBP算法调度顺序是{T1，T4，T2，T3，T6，T5，T7，T9，T8，T10}。相应地，HEFT的调度长度为80，CPOP的调度长度为86，而LBP算法调度长度为77。3.6实验与分析我们采用与文献[2]相同的随机任务图进行了仿真实验。这些随机生成的DAG由上十至上百个任务节点组成，节点和边的权重也是随机生成的，但CCR（通信成本与计算成本的比率，即边与节点权重之比）的变化范围控制在0.1～10之间。我们主要从算法的平均运行时间方面对HEFT、CPOP和LBP算法进行了实验比较，从图3.4能够看出，在相同的实验条件下，LBP算法的平均运行时间稍低于HEFT和CPOP算法。图3.4算法的平均运行时间比较

4具有多优先级的多DAG混合调度4.1具有多优先级的多DAG调度系统模型具有多优先级的多DAG调度系统模型如图4.1所示，它由3部分组成，分别是：多DAG接收与优先级判别子系统（Receiver&PriorityIdentification）、多DAG调度子系统（Multi-DAGScheduler）和对应于资源Mi的等待执行任务队列组（Qw-mi：QueueofTaskstobeExecutedonMi）。在多租户DAG工作流系统中，不同用户会在不同时间提交DAG。这些DAG到达后，由工作流接收与优先级判别子系统来管理和识别新DAG的优先级，并与较早时间到达的正在被调度执行的DAG优先级进行比较，为多DAG工作流调度子系统调度提供调度信息。然后，由多DAG工作流调度子系统根据混合调度策略将这些多DAG的任务按照执行顺序分配至系统的第3部分，即待执行任务队列组Qw-mi中。每次资源Mi执行完一个任务后，依次从与其相对应的Qw-mi中取下一个任务执行。图4.1多优先级DAG管理系统模型本文关于DAG工作流任务图的表示、定义和向上权值Ranku（ni）等与文献[2][20]的有关定义和方法一致，这里不再重复。在多租户多DAG系统模型中，资源的提供者是根据用户任务的运行时间向用户收取费用的。对CO-DAG类型的用户来说，首要的QoS需求是整个DAG的执行费用最低。如果Pmi表示资源Mj的单位时间的租用价格，则任务ni在资源Mj上所发生的费用为Eij=Pmiwij（wij表示任务结点ni机器资源Mj上的估计运行时间，参见文献[2])。下面经过图4.2的两个工作流实例DAG-A和DAG-B的调度来说明本文介绍的调度方法和策略。这两个DAG的复杂度、结构和各项参数基本与文献[2][20]中的实例一样，机器资源数为3个。假设两个DAG中每项任务在每个机器资源上的执行时间为表4.1，那么计算可得到每个任务的向上权值Ranku(ni)，见表4.2。 (a)DAG-A (b)DAG-B图4.2两个DAG工作流的实例表4.1DAG-A和DAG-B中各任务在机器上的执行时间DAGDAG-ADAG-BniA1A2A3A4A5A6A7A8A9A10B1B2B3B4B5M1,Pmi=1.01413111312137518214918217M2,Pmi=1.28191381316151112751017156M3,Pmi=1.11618191710911142016611161915表4.2两个DAG的任务向上权值表DAGDAG-ADAG-BniA1A2A3A4A5A6A7A8A9A10B1B2B3B4B5Rank107.77780806963.342.735.744.314.742203134.336本文的模型和算法除了要利用以上基本的定义和参数以外，还用到另一个重要定义，即公平性。多DAG调度的一个重要功能是经过一定的方法确定各DAG中各任务的调度和执行顺序，既涉及到同一DAG内前后有依赖关系任务的调度顺序，也涉及到分属不同DAG没有依赖关系任务的调度顺序，这些调度顺序会直接影响各个DAG的执行时间；而后一种调度顺序是否公平，也会直接影响到各个DAG的平均执行时间和调度系统整体性能的好坏。如果调度不考虑公平性，可能往往会因为多个同级DAG之间的结构差异较大而使得任务量小的DAG完成时间比任务量大的完成时间要晚，造成明显的不公平。仅根据任务的权值来确定调度顺序，很可能会造成先到达的DAG部分任务因为后续的DAG任务权值总是很大而得不到调度。因此，除了资源利用率，DAG的执行时间、公平性也是衡量多DAG调度算法性能的重要指标。Zhao和Sakellariou[21]首次提出了衡量这种公平性的方法，基于这种定义方法上的调度算法，能够达到更好的公平性。以下是文献[21]中关于公平性的表述和定义：由于一个DAGa要与其它DAG争用同一组机器，因此a的Makespan（从提交DAGa开始到DAGa的最后一个任务执行完毕所用的时间）很可能比a单独使用这组机器的Makespan要长，那么这两个Makespan可分别被表示为Mmulti（a）和Mown（a）。根据文献[22]的定义：Slowdown（a）=Mown（a）/Mmulti（a），那么某种调度算法S不公平程度Unfairness（S）=|Slowdown(a)-AvgSlowdown|。其中，A为给定的多个DAG的集，AvgSlowdown是所有DAG的Slowdown平均值。Unfairness（S）是能够用来衡量一种多DAG调度算法S调度的不公平程度的重要指标。4.2多DAG公平调度E-Fairness改进算法如前所述，Zhao的Fairness算法不能处理不同时间到达的多个DAG，也不适用于多优先级的多个DAG的应用情况。为了能够将任何时间到达的新DAG与已经全部预分配资源且部分任务已经执行的DAG同时公平地进行调度，改进的Fairness算法被提出。以下将经过图4.3来讨论改进方法。如果系统在0时刻只有图4.2（a）中的DAG-A到达请求调度，利用Topcuoglu的HEFT算法对DAG-A进行调度并执行，且在整个DAG-A调度执行过程中没有任何其它DAG到达，那的调度结果如图4.3（a）示。Mown（DAG-A）=79，Mmulti（DAG-A）=79，Slowdown（DAG-A）=1。可是，如果当DAG-A在调度执行过程中，新的DAG-B到达，假设它的到达时间Bar-t=35，且DAG-B的优先级与DAG-A相同，那么如图4.3（b）所示，DAG-A中的所有任务能够分为3部分：（1）执行完毕的任务组（A1，A3，A4和A5）；（2）Qw-mi中等待执行的任务组（A7，A8，A9和A10）；（3）机器Mi上正在执行的任务组（A2，A6）。由于机器上正在执行的任务具有不可剥夺性，因此在M1和M3上的A2和A6这两个任务不能被撤销，可是在Qw-mi中等待执行还未被执行的任务组（A7，A8，A9和A10）能够被撤销而且能够与新到达的DAG-B一起进行公平调度。考虑到原有DAG-A部分任务的撤销和重新调度可能会导致数据传输问题，因为撤销的未被执行的任务组中的任务有可能重新被调度到一个新的机器资源上，这时已经执行完毕的父母任务结点的数据是否能够及时送达是非常重要的。为了解决这个问题，多DAG系统模型要求：当一个有后继结点的任务完成后，它的执行结果数据必须向每个机器发送。另外，改进的Fairness算法的重要的一个方面就是对新DAG到达后时隙的调整。由于Fairness调度策略基于HEFT方法，在本例中，Bar-t=35，B中的所有任务和A中要重新调度的任务中任何一个任务的执行时间不能早于这个时间，因此在图4.3（b）中，机器M2上的第一个时隙应该调整为新的可用时隙，它的开始时间应被重置为Bar-t。 （a）DAG-A的单独调度结果 （b）DAG-B在35时刻到达时A的任务状态图4.3DAG-A和DAG-B调度举例另外，Zhao的Fairness算法中首先要对每个DAG的Slowdown值初始化为0，所有DAG调度的初始顺序为各个DAG单独调度时Makespan大小的降序排列。只有DAG被调度1次，DAG的Slowdown值发生变化后，才能实现多个DAG之间的公平性调度。对Fairness另一重要调整的步骤是，新到达的DAG必须首先被调度1次。在本例中，Aar-t=0，Bar-t>0，针对所有DAG-A中被撤销的任务和所有DAG-B中的任务，新到达B中向上权值最大的B1任务首先被调度1次。最后一个要调整的步骤是，计算新达到DAG中第i个任务被调度后的Slowdown（）的计算要考虑到新达到DAG的到达时间，最后的调度结果如图4.4和表4.3。图4.4E-Fairness算法调度DAG-A和DAG-B过程表4.32种算法调度DAG-A和DAG-B的结果比较（Bar-t=35s）算法E-Fairness（B优先级=A优先级）Backfill（B优先级<A优先级）两个DAG调度次序A1，A3，A4，A2,A5，A6，B1，A9，B4，B3，B2，B5，A7，A8，A10A1，A3，A4，A2，A5，A6，A9，A7，A8，A10，B1，B4，B3，B2，B5资源利用率0.526320.60760Makspan(A+B)95.0000079.00000Unfairness0.090500.07792MakespanA9579MakespanB42424.3多DAG的Backfill算法的实现在图4.5中，同样地，如果Bar-t=35，但B的优先级不同于A，那么应该采用Backfill算法来确定A和B的调度关系，而不能采用E-Fairness算法，因为优先级高的DAG能够中断先到达的并被正在调度的低优先级DAG，不同优先级DAG之间比较调度顺序上的公平性没有意义。图4.5Backfill算法调度DAG-A和DAG-B的过程当B的优先级高于A时，应该撤销A中未被执行的任务组中的任务，并首先将资源按照HEFT算法将所有机器分配给B，然后将A中的被撤销的任务插入到B所留下的时隙中。如果B的优先级低于A，那么A中的所有任务依然按照在0时刻的调度方案进行调度，并将B中所有任务按照HEFT算法匹配到各个机器Mi上时隙链表SMi（按照时隙的开始时间排列）上，并将这些任务插入到Qw-mi中等待执行。当新DAG-B到达时，正如图4.5所示，相关的时隙应该被修改为可用时隙。在调度过程中，其它一些需要调整时隙的情况举例说明如下：在图4.5中，EST（Bi，M1）表示任务Bi的所有父母任务结果数据的最晚送达到机器M1上的时刻，即任务Bi的最早开始时间。设tm和tn分别是EST（Bi，M1）两个可能的取值，且tm等于时隙的开始时刻，tn是时隙的等分时刻。假设B中某个任务Bi的长度恰好是的1/3，且任务Bi被匹配到时隙队列SM1中的时隙上。那么，当EST（Bi，M1）=tm时，被Bi占用后依然是1个时隙，只是时隙长度缩短了1/3；当EST（Bi，M1）=tn时被Bi占用后，将会被分成两个更