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

大连理工大学本科毕业设计（论文）云环境中DAG调度算法的设计与实现DesignandImplementationofDAGSchedulingAlgorithmsinCloudEnvironment学院（系）：计算机科学与技术学院专业：计算机科学与技术学生姓名：xxx学号：xxxxxxxx指导教师：xxx评阅教师：完成日期：大连理工大学DalianUniversityofTechnology云环境中DAG调度算法的设计与实现-I-摘要近年来随着网格、云计算工作流等异构分布式计算技术的发展，关于多DAG共享异构分布式资源的调度问题逐渐成为备受关注的研究热点。目前，尽管有关多DAG共享异构分布式资源调度的研究取得了一定进展，但仍有很多问题亟待进一步研究和解决。本文围绕多DAG共享异构分布式资源调度的若干问题展开了研究，这些问题包括：具有多优先级的多DAG调度和具有期限约束的多DAG调度吞吐量最大化、费用优化以及费用优化的公平性等。对这些问题的解决将有利于提高网格、云计算工作流等异构分布式计算系统的资源利用率、合理处理多个DAG应用之间的调度关系和有效降低用户DAG应用的费用，因此有着重要的理论意义和应用价值。关于DAG共享异构分布式资源调度的研究主要是关于DAG调度算法的研究。本文使用Java语言实现了经典DAG静态调度算法HEFT、CPOP和LBP，还实现了侧重公平性的E-Fairness算法，最后实现了混合调度算法MMHS。在实现这些算法的基础上，还测试这些算法的相关性能，如调度时间和公平性等。同时实现了DAG调度仿真器，在仿真器基础上，可以方便地进行各种算法的研究，而且方便做算法性能的实验测试。关键词：多DAG调度;多优先级;公平性;仿真器云环境中DAG调度算法的设计与实现-II-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云环境中DAG调度算法的设计与实现-III-目录摘要.....................................................................................................................................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实验与分析............................................................................