计算机理论论文网格环境中流水线虚拟服务调度算法的设计与实现.doc
网格环境中流水线虚拟服务调度算法的设计与实现 网格环境中流水线虚拟服务调度算法的设计与实现 Design and Implementation of the Pipeline Virtual Service Scheduling Algorithm in Grid Environment 【中文摘要】 具有DAG(有向无环图)结构的任务调度是网格环境下一个经典但具有挑战性的问题。基于面向服务的体系结构(SOA),本文将其抽象为流水线虚拟服务(Pipeline Virtual Service,PVS),并以HSDC系统天文数据处理为例,研究在网格环境下,流水线虚拟服务调度算法的设计和实现。通过对HSDC应用特点以及网格环境的分析,本文提出了PVS两阶段预调度模型(SOD算法实现)以及“三维金字塔”调度模型(TPS算法实现)。前者将调度策略产生和调度策略执行分离开来并行执行,利用网格中的闲散资源产生调度策略,并将其时间隐藏于调度策略执行中。后者考虑更加通用的网格调度情况,不再拘泥于以往调度时的二维匹配(任务和资源),而是对于影响调度的因素进行详细分类,根据PVS不同的结构找寻调度因素之间的多维匹配关系,从而产生更多更优的调度候选方案。实验分析说明,这两种算法模型和实现很好地适应了网格的开放性、动态性,在平衡调度开销和调度精度,减少调度时间,提高整体资源利用率方面都有着明显的优势。同时,HSDC原型系统的设计和实现也说明了本文所提的调度模型算法在网格环境下的实用性和有效性。【英文摘要】 The scheduling of tasks with DAG-structure is a classic but challenging problem in Grid environment. Based on SOA, this thesis abstracts the DAG tasks as Pipeline Virtual Service (PVS). Taking HSDC telescope data process as the application example, this thesis pays main attention on design and implementation of the Pipeline Virtual Service scheduling algorithm.By analyzing the application characterizations and Grid environment, a PVS pre-scheduling model with the relevant SOD algorithm and the Triangular Pyramid Scheduling (TPS) model with TPS algorithm are provided in this thesis. In the first model, scheduling policies generation and execution are separated and run in parallel. It can utilize the free computing abilities in Grid and hide the time of scheduling policies generation. The second model solves the scheduling problem by considering more general Grid characters. Rather than being limited in the two-dimension matching relationship (task-resource), it classifies the factors which affect the scheduling in details and establishes the new match relationship according to different structures of different PVSs. Therefore, it can find more and better scheduling solutions. The analytic simulation results show that two scheduling models and algorithms match the open and dynamic Grid environment. They have the advantages in balancing the scheduling cost and scheduling precision, saving the scheduling time and improving the resource utility. Moreover, the design and implementation of HSDC prototype also shows the practicability and efficiency of scheduling models and algorithms discussed in this thesis.【中文关键词】 网格; 有向无环图; 任务调度; SOA 【英文关键词】 Grid; DAG; task scheduling; SOA 【毕业论文目录】摘要 3-4 Abstract 4 第1章 引言 8-10 第2章 网格技术 10-19 2.1 引言 10 2.2 网格概念及发展 10-11 2.3 网格体系结构和基础工具 11-13 2.4 SOA 技术 13-17 2.4.1 SOA 的概念及特点 13-14 2.4.2 SOA 的产生发展及优势 14-15 2.4.3 SOA 应用体系结构 15-16 2.4.4 SOA 应用 16-17 2.5 SOA 与网格技术的结合 17-19 第3章 DAG 任务调度研究 19-34 3.1 引言 19 3.2 DAG 任务调度综述 19-21 3.2.1 DAG 任务调度模型 19-20 3.2.2 DAG 任务调度目标 20-21 3.3 网格环境下DAG 调度算法分类研究 21-29 3.3.1 随机算法 22-23 3.3.2 启发式算法 23-27 3.3.3 由自然法则得到的算法 27-29 3.4 网格项目中DAG 调度算法应用 29-31 3.5 存在的问题及发展方向 31-34 第4章 HSDC 问题分析及建模 34-38 4.1 引言 34 4.2 问题分析 34-35 4.3 流水线虚拟服务（PVS）模型 35-38 第5章 PVS 两阶段预调度模型及算法设计 38-50 5.1 引言 38 5.2 问题分析 38-39 5.3 PVS 两阶段预调度模型 39-40 5.4 基于PVS 两阶段预调度模型的算法设计 40-45 5.4.1 算法描述 40-42 5.4.2 算法分析 42-45 5.5 实验模拟 45-48 5.5.1 实验环境 45-46 5.5.2 实验结果及分析 46-48 5.6 小结 48-50 第6章 “三维金字塔”调度模型及算法设计 50-65 6.1 引言 50 6.2 问题分析 50 6.3 “三维金字塔”调度模型 50-53 6.3.1 “三维金字塔”调度模型 50-52 6.3.2 相关建模参数及问题抽象 52-53 6.4 TPS（Triangular Pyramid Scheduling）算法 53-59 6.4.1 TPS_Preparing 53-54 6.4.2 TPS_Scheduling 54-59 6.5 实验及分析 59-64 6.6 小结 64-65 第7章 原型系统设计 65-72 7.1 引言 65 7.2 原型系统设计及开发 65-70 7.3 原型系统实验 70-72 第8章 结论及展望 72-76 8.1 引言 72 8.2 本文主要贡献 72-74 8.2.1 任务建模 72 8.2.2 调度模型和算法实现 72-74 8.2.3 系统应用 74 8.3 后续研究工作 74-75 8.4 小结 75-76 参考文献 76-85 致谢 85-86 个人简历、在学期间发表的学术论文与研究成果 86-87
