云环境中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多DAGBackfill算法实现 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分配”关键步骤，也就是用不一样方法将整个DAGDeadline分配到各任务（或任务区间）上，然后依据任务所分配时间窗口尽可能选择较廉价（所以速度也较慢）资源进行费用优化。多年来，相关单个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中DAGW（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.1DAG调度仿真器。图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.1DAG，得到调度长度为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（任务TiT-LEVEL是指从入口任务到Ti一条最长路径长度）和B-LEVEL（任务TiB-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争用同一组机器，所以aMakespan（从提交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是全部DAGSlowdown平均值。Unfairness（S）是能够用来衡量一个多DAG调度算法S调度不公平程度关键指标。4.2多DAG公平调度E-Fairness改善算法如前所述，ZhaoFairness算法不能处理不一样时间抵达多个DAG，也不适适用于多优先级多个DAG应用情况。为了能够将任何时间抵达新DAG和已经全部预分配资源且部分任务已经实施DAG同时公平地进行调度，改善Fairness算法被提出。以下将经过图4.3来讨论改善方法。假如系统在0时刻只有图4.2（a）中DAG-A抵达请求调度，利用TopcuogluHEFT算法对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调度举例另外，ZhaoFairness算法中首先要对每个DAGSlowdown值初始化为0，全部DAG调度初始次序为各个DAG单独调度时Makespan大小降序排列。只有DAG被调度1次，DAGSlowdown值发生改变后，才能实现多个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多DAGBackfill算法实现在图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占用后，将会被分成两个更小时隙。4.4含有多优先级多DAG混合调度策略MMHS正如上述算法E-Fairness和Backfill中所提到，这两种算法在多优先级多DAG调度中适适用于不一样情况：E-Fairness适合于确定相同优先级DAG之间调度关系，而Backfill适合确定不一样优先级DAG间调度关系。适适用于多优先级多DAG调度在不一样时间抵达系统混合调度策略MMHS以下：混合调度策略MMHS1：While(DAGnew)do/*当新DAG抵达*/2：计算DAGnew中全部任务向上权值Rank；3：If(Pnew≥max{Pscheduling})/*Pscheduling表示集合Uscheduling中元素优先级集合(Uscheduling是正在调度运行DAG集合，并根据优先级从大到小排序)，Pnew表示新达成DAG优先级)*/4：依据新DAG抵达时间修改相关时隙；5：撤销Qw-mi中全部任务；/*正在运行DAG全部任务包含对应于机器MiQw-mi中未被调度任务、已经实施完成任务和正在Mi上实施任务*/6：If(Pnew>max{Pscheduling})7：依据HEFT算法调度DAGnew任务，并将DAGnew任务依次放入Qw-mi；8：While(Uscheduling)do：9：计算和修改全部机器上时隙链表SMi；10：apeer从Uscheduling选择优先级最高DAG(注：最高级可能有多个)；11：If(apeer中DAGCO-DAG)12：apeer中多个同级DAG间调度关系采取E-Fairness算法，并采取HEFT方法Backfill算法将这些任务匹配到SMi，并将任务依次放入Qw-mi13：Else14：apeer中多个同级DAG间调度关系采取E-Fairness算法，并采取LE方法Backfill算法将这些任务匹配到SMi，并将任务依次放入Qw-mi；15：Uscheduling=Uschedulingapeer；16：Endwhile17：Else18：If(Pnew=max{Pscheduling})19：apeer依次从Uscheduling选择优先级最高DAG(注：最高级可能有多个)；20：apeer中多个同级DAG间调度关系采取E-Fairness算法21：While(Uscheduling)do22：计算和修改对应于每个机器时隙链表：SMi23：apeer依次从Uscheduling选择优先级最高DAG；24：If(apeer中DAGCO-DAG)25：apeer中多个同级DAG间调度关系采取E-Fairness算法，并采取HEFT方法Backfill算法将这些任务匹配到SMi，同时将任务依次放入Q26：Else27：apeer中多个同级DAG间调度关系采取E-Fairness算法，并采取LE方法Backfill算法将这些任务匹配到SMi，同时将任务依次放入Qw-mi；28：Uscheduling=Uschedulingapeer29：Endwhile30：Else31：If(Pnew<max{Pscheduling})32：仅撤销Qw-mi中优先级小于或等于新抵达DAG优先级DAG中任务；保留全部优先级大于新DAGDAG中任务调度方案，并将这些DAG从Uscheduling中删除；33：While(Uscheduling)do34：计算和修改全部时隙链表SMi；35：apeer在Uscheduling中选择优先级和新DAG相同DAG和新达成DAG；36：If(apeer中DAGCO-DAG)37：apeer中多个同级DAG间调度关系采取E-Fairness算法，并采取HEFTBackfill算法将这些任务匹配到SMi，同时将任务依次放入Qw-mi；38：Else39：apeer中多个同级DAG间调度关系采取E-Fairness算法，并采取LE方法Backfill算法将这些任务匹配到SMi，同时将任务依次放入Qw-mi；40：Uscheduling=Uschedulingapeer41：Endwhile42：Endwhile4.5试验和分析本节经过大量试验数据，着重从资源利用率UR、DAGMakespan和不公平程度Unfairness这3项指标将MMHS策略和相关算法（E-Fairness，Backfill）进行性能比较。因为针对两个DAG调度，MMHS调度策略只需要在E-Fairness和Backfill之间进行选择，所以只需对E-Fairness，Backfill这2种算法在不一样条件下作性能比较即可。4.5.1相关两个DAG调度试验假设B优先级小于A优先级，依据混合调度策略MMHS，保留那些优先级大于新抵达DAG全部DAG任务分配方案。那么，当B抵达时，MMHS将保留A中全部任务在0时刻分配方案，而将B匹配到各个机器时隙上。在下文图4.6和图4.7中显示了在DAG-B不一样抵达时间上，分别在2个和5个机器上2种调度算法相关性能指标情况。我们比较了2种算法MakespanA，图4.6和图4.7所表示，采取Backfill算法，DAG-AMakespanA能够避免受到B影响，很好地确保了DAG-A用户对实施期限较为严格限制。能够看出，在公平性指标上，Backfill算法比E-Fairness算法相对要差。所以