基于资源动态性度量的网格依赖任务重调度研究

论文摘要

网格是一种能够集成地理上分散资源的基础设施。它能将各种信息资源接成一个整体,向每个用户提供包括计算能力、数据存储能力以及各种应用工具等一体化的透明服务。网格资源是分布在Internet环境中的,资源本身具有异构性、动态性和自治性。网格任务在不同的资源上的性能表现不同,因此对于提高由多个任务构成的网格应用的整体性能而言,需要网格任务调度为应用中的每个任务指派合适的资源。在网格任务调度中,依赖任务调度问题已经引起了广泛的关注。网格依赖任务调度问题,由于对某一任务的资源指派将影响对其他任务的资源指派,因此,为了实现网格应用性能优化的调度目标,需要采取全局的调度策略。该调度策略是基于预知的应用和资源信息,在运行前制定全局调度计划。网格应用的各个任务将按照计划中的时间安排在指派资源上执行。由于网格资源是动态变化的且这种变化会随时发生,因此在应用的运行期间资源可能发生变化,这种变化将影响网格应用的最优性。为此,就需要网格依赖任务重调度,以便在资源发生变化时,对全局调度计划进行调整,以实现应用性能优化的目标。以应用性能优化为目标的网格依赖任务重调度,需要采取全局优化的的重调度策略与资源变化触发的重调度触发方式,而这将面临重调度效率低与触发频繁等困难。为解决上述困难,本文从确定重调度任务范围、减少资源数量、提高备选资源稳定性、减少无用重调度四个方面着手,提出了基于资源动态性度量的网格依赖任务重调度机制。该机制以资源动态性度量模型为基础,以基于视图的资源组织、重调度触发机制以及重调度任务波及域计算为支撑,尽量利用动态性较弱的资源,合理缩小重调度任务范围,并在合适的时机触发网格依赖任务重调度过程,解决了网格依赖任务重调度效率低、触发频繁的问题,从而实现了以应用性能优化为目标的网格依赖任务重调度。本文主要完成了如下的工作：（1）针对网格依赖任务重调度面临的效率低和触发频繁两个问题,本文研究基于资源动态性度量的网格依赖任务重调度机制（G-DERM）,提出资源动态性度量模型。该模型对个体资源及整体资源环境的性能和性能变化周期进行度量。在资源动态性度量的基础,G-DERM通过在合适的时机触发网格依赖任务重调度过程、尽量利用动态性较弱的资源、合理缩小重调度任务范围,能够有效的提高网格依赖任务重调度的效率,降低重调度的触发频繁。（2）针对如何减少备选资源数量和提高备选资源稳定性问题,本文研究基于视图机制的资源组织模型。该模型是一个资源的三层组织结构,是在以应用的资源需求和资源动态性度量结果对网格资源进行双重过滤的基础上构建起来的。该模型能够过滤性能相近的应用可用资源中的强动态性资源,提高重调度备选资源的稳定性,进而提高网格依赖任务重调度的效率并降低重调度触发频率。（3）针对如何减少无用重调度问题,本文研究重调度触发机制,提出重调度的触发规则,建立触发规则的层次结构。该规则在网格资源动态性度量的基础上,分析资源变化对应用性能的影响,判断是否需要触发重调度,并确定重调度触发时刻,延时触发在任务执行时间估计准确性较低情况下的资源变化引发的重调度过程,减少无用重调度次数,降低网格依赖任务重调度触发频率。（4）针对如何确定重调度任务范围问题,本文研究重调度任务波及域及计算算法。在度量资源环境动态性和估计任务完成时间的基础上,通过判断任务完成时间是否在资源环境的变化周期内,重调度过程中将不考虑完成时间不在该周期内的任务,即不考虑对网格应用性能优化支持较弱的任务；并且通过网格应用中任务间所存在的点波及、依赖波及以及连通波及关系计算重调度任务波及域,以在不影响网格应用优化效果的基础上,缩小任务范围,提高重调度的效率。（5）针对重调度任务波及域内网格依赖任务重调度求解效率与优化效果问题,本文研究基于G-DERM的网格依赖任务重调度模型和算法。提出基于DAG的重调度模型及改进HEFT启发式算法,和基于T-RAG优化选取的重调度模型及免疫遗传算法。在保证效率的同时提高网格应用的优化效果。（6）针对如何验证本文所提出的基于资源动态性度量的网格依赖任务重调度机制有效性问题,本文搭建G-DERM模拟实验环境,并进行一系列实验验证所提出的重调度触发机制、波及域计算、资源组织模型对提高网格依赖任务重调度的效率,降低重调度触发频率的支持作用。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 研究背景
• 1.1.1 网格
• 1.1.2 网格计算
• 1.2 网格依赖任务重调度面临的挑战
• 1.3 基于资源动态性度量的网格任务重调度机制的提出
• 1.4 本文主要工作及组织结构
• 第二章 网格任务调度与重调度
• 2.1 网格任务调度
• 2.1.1 网格任务调度执行过程
• 2.1.2 网格任务调度目标与策略
• 2.1.3 网格任务调度算法
• 2.1.4 网格任务调度系统
• 2.2 网格任务重调度
• 2.3 网格依赖任务重调度
• 2.4 小结
• 第三章 基于资源动态性度量的网格依赖任务重调度机制
• 3.1 网格依赖任务重调度存在的问题及解决思路
• 3.1.1 网格依赖任务重调度存在的问题
• 3.1.2 问题解决的基本思路
• 3.2 基于资源动态性度量的网格依赖任务重调度机制
• 3.2.1 基本框架
• 3.2.2 基本过程
• 3.2.3 体系结构
• 3.3 资源动态性度量模型
• 3.4 基于视图机制的资源组织模型
• 3.4.1 资源视图描述
• 3.4.2 资源视图构建及维护方法
• 3.5 小结
• 第四章 重调度触发机制及算法
• 4.1 相关定义
• 4.2 重调度触发机制
• 4.3 重调度触发因素
• 4.4 重调度触发规则
• 4.4.1 重调度任务选取规则及算法
• 4.4.2 重调度延时触发规则及算法
• 4.5 小结
• 第五章 重调度任务波及域及计算
• 5.1 重调度任务波及域
• 5.2 重调度任务波及域计算方法
• 5.2.1 点波及域计算方法
• 5.2.2 依赖波及域计算方法
• 5.2.3 连通波及域计算方法
• 5.2.4 重调度任务波及域计算过程
• 5.3 重调度任务波及域计算算法
• 5.3.1 点波及域计算算法
• 5.3.2 依赖波及域计算算法
• 5.3.3 连通波及域计算算法
• 5.4 小结
• 第六章 基于G-DERM的重调度模型与算法
• 6.1 基于DAG的重调度模型及改进HEFT算法
• 6.1.1 基于DAG的重调度模型
• 6.1.2 改进HEFT算法基本思想
• 6.1.3 算法描述
• 6.1.4 算法实例
• 6.1.5 实验分析
• 6.2 基于T-RAG优化选取的重调度模型及免疫遗传算法
• 6.2.1 基于T-RAG优化选取的重调度模型
• 6.2.2 免疫遗传算法基本思想
• 6.2.3 实验分析
• 6.3 小结
• 第七章 G-DERM模拟实验环境与实验分析
• 7.1 G-DERM模拟实验环境
• 7.2 G-DERM有效性实验设计
• 7.3 G-DERM有效性实验分析
• 7.3.1 G-DERM有效性总体验证实验
• 7.3.2 触发机制有效性验证实验
• 7.3.3 波及域有效性验证实验
• 7.3.4 资源组织有效性验证实验
• 7.4 小结
• 第八章 结论
• 8.1 本文的主要贡献
• 8.2 未来工作展望
• 参考文献
• 致谢
• 攻读博士学位期间的主要成果