云环境下基于QoS约束的工作流任务调度算法研究与实现

论文摘要

云计算是目前国内外各机构的研究热点之一,是并行计算(Parallel Computing)、分布式计算(Distributed Computing)和网格计算(Grid Computing)的发展,是新兴的一种商业计算模式。其采用了较为成熟的虚拟化技术将位于数据中心内的资源打包,向互联网上用户按需提供服务。任务调度和资源分配是云计算中两个关键的技术,云计算的商业特性使其关注向用户提供服务的服务质量,所使用的虚拟化技术使得其资源分配和任务调度有别于以往的并行分布式计算。云计算以用户为中心、面向服务、商业性等特征,使得目前主要的工作流调度算法是基于QoS的调度算法,而且很多是借鉴原来网格环境下的调度策略。由于云环境下工作流还有着自身的特点,原有的调度策略在一些场合的执行效率上存在问题。本文研究了云环境下的工作流调度策略,首先介绍了目前已有的各种工作流调度算法,并重点研究了基于QoS约束的工作流调度,分析了各算法应用于云环境下调度实例密集型工作流时存在的缺陷。在此基础上,介绍云环境下的工作流调度体系结构,对云工作流业务流程进行分析,采用DAG进行建模,对建模以后所生成的子任务间的逻辑关系进行了说明。并以此为基础,针对工作流调度策略在云环境下调度实例密集型工作流时效率不高的问题,提出了一种基于QoS约束的调度算法,在满足总的最后期限的前提下最小化总的执行成本,区别于以往的工作流调度算法注重单个复杂的科技工作流实例。然后,对云计算仿真平台CloudSim进行了扩展,通过模拟一个DAG数据库,随机产生实例,重载关键类等方法使该平台能够支持云环境下工作流调度的仿真。最后,在扩展后的平台上实现了工作流调度的仿真程序,对所提出的算法进行模拟验证与对比分析,实验结果显示在调度实例密集型云工作流时,该算法具有更好的性能。

论文目录

• 中文摘要
• 英文摘要
• 1 引言
• 1.1 研究背景
• 1.1.1 云
• 1.1.2 云工作流
• 1.1.3 云QoS
• 1.2 本文的主要内容和创新
• 2 工作流调度研究
• 2.1 基于最大努力的调度算法
• 2.1.1 混合启发式
• 2.1.2 TANH
• 2.1.3 网格动态关键路径（DCP-G）
• 2.1.4 快速关键路径（FCP）算法
• 2.1.5 自适应广义调度（AGS）
• 2.1.6 工作流映射机制（WMM）
• 2.1.7 自适应工作流分裂（AWS）算法
• 2.1.8 自适应调度算法（ASA）
• 2.1.9 异构最早完成时间算法（HEFT）
• 2.1.10 贪婪随机自适应搜索过程（GRASP）
• 2.1.11 模拟退火（SA）算法
• 2.1.12 遗传算法（GA）
• 2.1.13 近视算法
• 2.1.14 Min-Min, Max-Min 和 Sufferage 启发式
• 2.2 基于QoS 约束的调度算法
• 2.2.1 基于回溯算法的调度算法
• 2.2.2 丢失与获取方法
• 2.2.3 基于遗传算法的调度算法
• 2.2.4 基于改进的遗传算法的调度算法
• 2.2.5 基于蚁群算法的调度算法
• 2.2.6 最后期限分配算法
• 2.3 各算法比较分析
• 2.4 本章小结
• 3 基于 QoS 约束的云工作流调度算法
• 3.1 工作流参考模型
• 3.2 云工作流调度体系结构
• 3.2.1 服务云
• 3.2.2 云工作流执行代理（EA）
• 3.2.3 云服务目录
• 3.3 云工作流业务流程分析
• 3.3.1 一具体云工作流DAG 模型分析
• 3.4 MCUD 调度算法
• 3.4.1 工作流任务调度描述
• 3.4.2 工作流任务最后期限分配原则
• 3.4.3 MCUD 算法流程
• 3.5 小结
• 4 CloudSim 仿真平台扩展与实验
• 4.1 CloudSim 介绍
• 4.2 配置及仿真流程
• 4.2.1 CloudSim 环境配置
• 4.2.2 仿真流程
• 4.3 工作流调度平台实现
• 4.3.1 CloudSim 平台的扩展
• 4.3.2 CloudSim 平台重新编译
• 4.4 调度算法仿真
• 4.4.1 实验数据
• 4.4.2 仿真核心代码
• 4.5 实验结果与分析
• 4.6 本章小结
• 5 结论与展望
• 5.1 工作总结
• 5.2 展望
• 致谢
• 参考文献
• 附录