云环境下基于失效感知的工作流调度算法研究

摘要

近年来，由于云计算的快速发展，大规模的云计算数据中心在全球各地被广泛建立。随着对云计算关注度的提高，云计算的功能(functionality)和复杂度(complexity)被研究人员广泛研究。在云环境中，为了在满足服务质量的前提下，尽可能的降低服务成本，实现用户和服务提供商双方最大化收益问题而引入了“云工作流”。通过将工作流技术与云计算相结合，一方面其可以将原先复杂的应用需求按照业务逻辑进行抽象定义和分解，对任务和资源进行再次整理和灵活配置，从而提高服务质量;另一方面其可以实现任务自动调度、任务监控和资源分配的优化与管理，因此可以大幅提高任务的执行效率，能有效地提高云计算服务的质量，减少执行任务的费用开销。
　　针对云工作流的调度问题，不同的研究人员从完工时间最小化、执行成本最低化、任务完成率最大化等多方面展开研究。虽然当前存在很多云工作流的调度方法，但都没有针对云计算资源失效而建立调度模型，从而有效的规避和减少失效事件对云环境下工作流任务调度结果的影响。而在云计算环境中，资源失效是不可避免的。由于资源失效将直接带来系统性能降低、程序执行提前终止甚至数据丢失等问题，最终导致更多的任务不能在截止期内完成、违约率增高，严重影响到云计算的可靠性和稳定性，大大降低了服务质量（Quality of Service，QoS）。同时由于工作流的各个任务之间存在时序约束和数据依赖。因此在工作流执行的过程当中，一旦某一个资源节点出现失效情况，不但导致此任务需要重新执行，有可能整个工作流任务都需要重新执行，严重影响到云计算的效率，浪费大量的计算资源。
　　基于当前云计算环境下失效预测机制的国内、外研究现状和发展趋势，结合云计算调度优化特点，本文首先提出了基于失效感知的工作流调度模型，在调度过程中引入了失效预测机制和任务再调度策略，调度在满足截止期要求的基础上以最大化任务的完成率为目标。在任务调度过程中，为工作流的每一个任务生成子截止时间。根据资源失效预测模型，当所选的资源节点在任务的子截止期前发生失效时，提前把任务迁移到另一个可以顺利完成该任务的节点上，从而有效地规避资源失效对任务执行带来的影响，且在任务迁移过程中尽量把关键路径任务分配到同一个性能较高的虚拟机上以减少任务之间数据传输的开销，缩短完工时间，提高任务的完成率。然后对失效感知的工作流调度模型中的各个模块功能进行了详细说明，在此基础上对失效预测机制、工作流模型和资源模型进行定义，最后对模型进行具体实现，给出了基于失效感知的工作流调度算法(BFGA)。该算法基于遗传算法进行改进，算法中提出了新颖的三元组编码方式，在种群初始化过程中，采用随机生成和使用已经证明是有效的算法相结合的方式生成个体，以达到兼顾种群多样性的目的。同时设计了符合工作流特点的交叉和变异方法，在个体进行交叉变异之后又引入了调整算子对部分结果进行局部微调，以避免陷入局部最优，有效提高了收敛的速度。
　　通过CloudSim云计算仿真平台对提出的模型和算法进行仿真实验，实验借助不同类型工作流应用和改变仿真环境参数的方法进行。通过与GA算法进行对比，验证了算法的有效性。实验证明BFGA算法相对一般的GA算法由于采用三元组的编码方式，初始化种群采用了多种生成个体的方法，丰富了种群个体的多样性，且在种群进化过程中增加了调整算子，使其具有更好的收敛速度。其次，从失效预测准确率、工作流任务数量、失效节点比率三个方面来验证BFGA算法与GA算法、First-fit算法、Pessimistic Best-fit算法以及不考虑失效的普通算法对任务调度的影响。实验证明当失效预测准确率大于50％时，BFGA算法相比其他算法具有较高的作业完成率和不可靠节点利用率。当失效预测准确率为75％，工作流任务数大于600时五种算法的任务完成率均有下降，但是BFGA算法下降较为缓慢且一直高于其他四种算法。通过实验有效地证明BFGA算法能够降低资源失效给工作流任务调度带来的影响，很好的解决了基于失效感知的工作流调度问题。

目录

摘要

第1章 绪论

1．1 研究背景及意义

1．2 国内外研究现状

1．3 本文的主要工作及创新点

1．4 本文的组织结构

1．5 本章小结

第2章 云计算与工作流相关介绍

2．1 云计算概述

2．1．1 云计算简介

2．1．2 云计算特点

2．1．3 云计算服务质量

2．2 工作流技术

2．2．1 工作流定义

2．2．2 云工作流体系架构

2．3 云资源的稳定性

2．4 失效预测机制

2．5 本章小结

第3章 云环境下的工作流任务调度

3．1 工作流任务模型

3．2 工作流任务调度的定义

3．3 工作流任务调度的目标

3．4 工作流任务调度的流程

3．5 遗传算法

3．6 本章小结

第4章 基于失效感知的工作流调度模型

4．1 基于失效预测机制的任务调度架构

4．2 失效预测模型

4．3 云资源管理

4．4 问题描述

4．5 本章小结

第5章 基于失效感知的工作流调度算法

5．1 BFGA算法流程

5．2 BFGA算法实现

5．2．1 三元组编码方式设计

5．2．2 初始化种群

5．2．3 交叉算子设计

5．2．4 变异算子设计

5．2．5 调整算子的原则

5．3 本章小结

第6章 仿真实验与结果分析

6．1 CloudSim仿真框架简介

6．2 模拟方法及参数选择

6．2．1 IaaS参数设置

6．2．2 工作流的选取

6．3 实验模拟与结果分析

6．3．1 BFGA算法有效性

6．3．2 失效预测准确性对任务调度的影响

6．3．3 工作流任务数量对任务调度的影响

6．3．4 失效节点比率对任务调度的影响

6．4 本章小结

第7章 总结与展望

参考文献

致谢

声明