大连理工大学本科毕业设计（论文）云环境中DAG调度算法的设计与实现Design and Implementation of DAG Scheduling Algorithmsin Cloud Environment学 院（系）： 计算机科学与技术学院 专 业： 计算机科学与技术 学 生 姓 名： xxx 学 号： xxxxxxxx 指 导 教 师： xxx 评 阅 教 师： 完 成 日 期： 大连理工大学Dalian University of Technology差距大，市场体系不完善，缺乏集聚效应等问题，同时充分考虑到该地周围已形成成熟建材商圈的商业价值，因地制宜的进行家居建材广场的建设。通过合理布局、优化环境、提升服务，该项目必将切实发挥商业区在引导消费、拉动经济增长方面的作用，促进该县经济和社会又好又快发展。云环境中DAG调度算法的设计与实现摘 要近年来随着网格、云计算工作流等异构分布式计算技术的发展，关于多DAG共享异构分布式资源的调度问题逐渐成为备受关注的研究热点。目前，尽管有关多DAG共享异构分布式资源调度的研究取得了一定进展，但仍有很多问题亟待进一步研究和解决。本文围绕多DAG共享异构分布式资源调度的若干问题展开了研究，这些问题包括：具有多优先级的多DAG调度和具有期限约束的多DAG调度吞吐量最大化、费用优化以及费用优化的公平性等。对这些问题的解决将有利于提高网格、云计算工作流等异构分布式计算系统的资源利用率、合理处理多个DAG应用之间的调度关系和有效降低用户DAG应用的费用，因此有着重要的理论意义和应用价值。关于DAG共享异构分布式资源调度的研究主要是关于DAG调度算法的研究。本文使用Java语言实现了经典DAG静态调度算法HEFT、CPOP和LBP，还实现了侧重公平性的E-Fairness算法，最后实现了混合调度算法MMHS。在实现这些算法的基础上，还测试这些算法的相关性能，如调度时间和公平性等。同时实现了DAG调度仿真器，在仿真器基础上，可以方便地进行各种算法的研究，而且方便做算法性能的实验测试。关键词：多DAG调度;多优先级;公平性;仿真器- I -云环境中DAG调度算法的设计与实现Design and Implementation of DAG Scheduling Algorithmsin Cloud EnvironmentAbstractIn recent years, with the grid, cloud computing workflows and other heterogeneous distributed computing technology, scheduling of multiple DAGs sharing on heterogeneous distributed resources is becoming a hot topic of concern. At present, despite about multiple DAGs sharing on Heterogeneous Distributed Resource Scheduler has made some progress, but there are still many problems to be further studied and resolved.This paper focuses on a number of issues more DAG sharing on Heterogeneous Distributed Resource Scheduling. These issues include: a multi-priority DAG scheduling and deadline constraints have multiple DAGs scheduling to maximize throughput, cost optimization and cost optimization of the fair and so on. Solving these problems will help improve grid, cloud computing resource utilization, workflow and other heterogeneous distributed computing systems, rational treatment of multiple DAGs scheduling relationship between applications and reduce user DAG application fee, so there are theoretical significance and application value.Research on the DAG share in Heterogeneous Distributed Resource Scheduling is research on DAG scheduling algorithm. This article uses the Java language to achieve a classic DAG static scheduling algorithm HEFT, CPOP and LBP, but also to implement a focused equity E-Fairness algorithm, and finally realize the hybrid scheduling algorithm MMHS.On the basis of these algorithms, but also test the relative performance of these algorithms, such as the scheduled time and equity. While achieving the DAG scheduling simulator, a simulator based on, it can easily study various algorithms, and easy to do experiments to test the algorithm performance.Key Words：multi DAGs scheduling;multi priority;fairness- III -目 录摘 要IAbstractII引 言11 绪论21.1 研究背景21.2 研究现状32 相关定义及理论82.1 DAG任务调度模型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 静态调度算法HEFT153.3 静态调度算法CPOP163.4 基于表调度的任务调度算法LBP183.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混合调度策略MMHS274.5 实验与分析294.5.1 相关的两个DAG的调度实验294.5.2 多个随机DAG的调度实验结果分析31结 论33参 考 文 献34附录A MMHS算法核心代码36致 谢39云环境中DAG调度算法的设计与实现引 言近年来，随着一些异构分布式计算环境工作流系统技术的发展（如网格、云计算或混合云计算工作流系统），作为这些工作流管理系统的关键技术之一的多个DAG任务共享异构分布式资源的调度问题引起了研究者们的关注。很多的工作流任务及任务间的依赖约束关系都可由有向无环图DAG（Direct Acyclic Graph）来表示1。目前有关多个DAG任务共享资源调度的研究在执行时间最小化（Makespan Minimization）、公平性最大化（Fairness Maximization）、吞吐量最大化（Throughput Maximization）以及资源分配优化（Resource Allocation Optimization）等方面已经取得了一些进展。在网格、云计算或混合云计算等平台的工作流的研究领域中，关于有最晚完成期限约束的DAG调度问题也引起了研究者们的关注。在这些新型异构分布式应用环境下，由于资源提供者往往会根据所提供的资源类型、服务质量QoS（Quality of Service）和用户使用（或租用）资源的总时长进行计费，用户考虑到经济费用等因素，往往会根据应用的需求为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 研究背景任务调度问题是分布式计算领域中的基本问题。根据被调度的任务之间是否存在相关依赖关系，任务调度可分为独立的任务调度和相关的任务调度（有时也被称为依赖任务调度）。其中相关的任务是由一组既有前后数据传递约束关系，又有并行关系的多个任务