网格环境下任务调度的研究

论文摘要

伴随网格技术的出现和快速发展,网格技术正处在不断成熟和逐步完善之中,由于网格技术支持分布式资源整合为一个整体,目前有越来越多的资源和虚拟机构参与网格的开发,这些资源数量和种类各部相同,例如有些是计算类型的资源,有些是存储型的资源,还有软件类型资源、信息类型资源、知识类型资源和用户类型资源等等,总之有一定功能的资源都可以整合的网格中发挥自己的作用。然而资源多了面对的问题也就会增加,选择哪些资源去完成某项任务可以使性能更好,更能得到网格用户的满意成为了主要问题。网格的任务调度算法成为了关键,为了是网格用户的满意度达到最大化,我们需要一个更综合性的调度算法,使调度的性能达到用户偏好的要求。这样的算法是要用多目标模型来实现。在网格任务调度中,用户更在乎的指标主要包括任务执行的时间、执行任务需要的开销和任务执行的可靠性,不同用户对这些指标的要求不尽相同,有些用户更在乎执行时间快慢,有些用户则考虑经济更多,面对这样的问题,就要求我们能提供一个有效的算法去满足不同的可能要求。本文提出了一个综合性的多目标网格调度算法模型,该模型基于N-constraint,并把模型转化成为多维选择背包问题,这是个NP问题,所以只能寻求最优解,本文提出了一个多目标启发式算法NVCA （N-Variable Constraints Algorithm）,该算法是基于动态规划,并在求解过程中加入了一个新的求近似解的算法,大大减少了解空间,使求解速度大大提高。本文最后用实现数据证明了与目前存在的调度算法相比NVCA算法的有效性。NVCA算法的有效性本文在第三章能够得到验证,但是实验中NVCA算法而时间数据是我们靠经验随机生成的,没有太多依据,因为一个新任务到来还是很难知道这个运行时间的值,所以本文在第四章单独研究如何预测任务执行时间,借鉴相似度算法思想,基于CBR进入历史任务库匹配,用历史任务的时间来推测新任务的时间,通过实验证明,与现存的一个有效算法进行对比后证实我们的改进效果。

论文目录

• 摘要
• Abstract
• 引言
• 1 绪论
• 1.1 研究背景
• 1.2 相关概念
• 1.2.1 网格的概念
• 1.2.2 网格的发展
• 1.2.3 网格的特点
• 1.3 本文研究的内容和意义
• 1.4 本章小结
• 2 网格调度算法的研究
• 2.1 网格调度
• 2.1.1 网格调度的体系结构
• 2.1.2 网格调度流程
• 2.2 网格调度算法
• 2.2.1 任务间的依靠性
• 2.2.2 Adaptive调度算法
• 2.2.3 元启发式调度算法
• 2.3 调度算法分析
• 2.3.1 各类调度算法的优缺点
• 2.3.2 各类调度算法对网格调度特点的适应性
• 2.4 本章小结
• 3 适合于网格任务调度的NVCA算法
• 3.1 当前可用于网格调度的多目标相关调度算法
• 3.1.1 BDLS算法和BGA算法
• 3.1.2 DCA算法
• 3.2 NVCA算法
• 3.2.1 问题定义
• 3.2.2 问题模型
• 3.2.3 算法描述
• 3.3 NVCA算法分析及问题
• 3.4 NVCA算法求解
• 3.4.1 结合剪枝方法
• 3.4.2 基于网格聚类取近似解
• 3.5 NVCA算法对网格调度的适应性
• 3.5.1 实验环境
• 3.5.2 实验结果和分析
• 3.6 本章小结
• 4 基于相似度的网格任务执行时间预估
• 4.1 任务属性归一原则和效用函数
• 4.2 基于相似度算法的网格任务执行时间预测
• 4.3 实验环境及性能分析
• 4.4 本章小结
• 结论
• 参考文献
• 攻读硕士学位期间发表学术论文情况
• 致谢