基于网格计算的调度算法研究

论文摘要

网格计算是以资源共享为主要特征的下一代互联网技术。由于网格中的资源具有动态性、多样性、自治性等特点,网格资源调度问题已经成为网格研究的一个热点和难点问题。网格资源调度的研究主要是针对调度算法的研究。在网格系统中,大量地理上分布的各种资源为不同的组织拥有。这些组织具有不同的使用规则、不同的计费模型、不一样的负荷能力和不同的使用模型。资源拥有者和资源使用者各自具有不同的目标、目的、策略和需求。因此,一些传统的资源管理和调度方式在网格系统中并不适用。而将经济学引入到网格体系中,研究经济学的方法在网格任务调度中的应用,是近年来网格任务调度领域的一个研究热点。本文主要对DAG模型和经济模型的资源调度算法进行了较为深入的研究。在DAG模型中,分析了GS算法和其改进算法,提出了基于有向无环图的成本-时间优化调度算法,在不增加总的完成时间的基础上,减少了费用。在基于计算经济模型的作业截止期限和预算约束DBC（Deadline Budget Constrain）算法的基础上,本文针对网格中资源的特点和用户的实际需求,改进了原有算法,提出了基于效益函数的成本-时间综合优化算法,在系统完成相同数量的网格任务时,消耗相同时间的情况下,该调度算法在代价上优于基于时间优化的调度算法;而花费相同预算的情况下,在时间上优于基于代价优化的调度算法。通过实验表明,本文提出的改进算法是可行的。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 研究背景及意义
• 1.2 国内外研究现状
• 1.2.1 网格的研究现状
• 1.2.2 网格任务调度的研究现状
• 1.3 网格的应用
• 1.4 论文的组织结构
• 第2章 网格中的任务调度
• 2.1 网格计算任务调度的特点和主要目标
• 2.1.1 任务调度的特点
• 2.1.2 任务调度的主要目标
• 2.2 网格调度模型
• 2.2.1 网格资源组织模型
• 2.2.2 调度模型
• 2.2.3 网格应用模型
• 2.3 网格调度过程
• 2.3.1 作业提交
• 2.3.2 收集可用资源静态信息
• 2.3.3 资源预选
• 2.3.4 资源动态信息查询
• 2.3.5 订调度计划，资源预约初始化制
• 2.3.6 作业运行时监控
• 2.4 网格任务调度算法
• 2.4.1 启发式任务调度算法
• 2.4.2 基于Agent的任务调度
• 2.4.3 基于Petri网的任务调度
• 2.4.4 基于有向无环图的任务调度
• 2.4.5 基于经济模型的调度
• 2.5 本章小结
• 第3章 基于DAG模型的改进算法
• 3.1 DAG调度及目标系统
• 3.2 任务调度器的数学模型
• 3.3 分代调度算法（GS）
• 3.4 优化的GS算法（OGS）
• 3.4.1 OGS算法思想
• 3.4.2 OGS算法的具体步骤
• 3.5 对 OGS算法的改进
• 3.5.1 DAG节点入度和出度计算
• 3.5.2 优先级指派算法
• 3.5.3 问题分析
• 3.5.4 改进的基于有向无环图的费用-时间优化算法
• 3.5.5 仿真结果及分析
• 3.6 本章小结
• 第4章 基于经济模型调度的改进算法
• 4.1 基于计算经济模型的调度
• 4.1.1 Nimrod-G网格资源管理系统
• 4.1.2 Nimrod-G资源代理:基于经济学的网格调度程序
• 4.2 调度与计算网格经济体系
• 4.2.1 计算经济模式的体系结构框架
• 4.2.2 基于经济模型的资源调度参数
• 4.3 时间最优化算法
• 4.4 代价最优算法
• 4.5 改进的基于效益函数的成本-时间综合优化算法
• 4.5.1 问题分析
• 时间综合优化算法'>4.5.2 基于效益函数的成本_时间综合优化算法
• 4.5.3 仿真结果及分析
• 4.6 本章小结
• 总结与展望
• 致谢
• 参考文献
• 攻读硕士学位期间发表的论文及科研项目