基于时间和费用约束的网格任务调度算法研究及仿真

摘要

网格计算是继Internet和Web之后最重要的信息技术，并且也是随着Internet技术迅速发展起来的。集群(Cluster)、P2P(Peer-to-Peer)和网格是下一代并行和分布式计算的一种流行模式，其中集群和P2P中的资源是同构的，并且大多数采用集中控制，他们的资源是很容易管理的，任务计算也是容易调度的。但是，随着科技的发展，科学、工程和商业领域中大规模性的计算问题的出现，使得单一的环境(P2P)、单一的技术(集群计算)变得力不从心，必须寻求一种价格低廉、处理能力超强的高性能计算环境，网格计算就是这样应运而生的。 网格是一个异构的、分布式的、动态的和多管理性领域的环境。在这样一个环境中进行资源管理，并且充分利用这些资源进行任务计算，即网格任务调度，都是目前网格计算中比较热门的研究方向。一般来说，提交到网格中的任务都有一定的QoS(Quality of Service)约束条件，网格任务调度的核心问题就是设计合适的调度算法去满足网格任务的QoS约束条件。 本文主要研究了时间和费用两种QoS约束条件，并提出了一种保障任务完成的最优调度算法，该调度算法既能优化网格任务执行代价(时间和费用)，又能保障网格任务完成。主要的研究工作以及创新性体现在以下几个方面： 1) 通过模拟市场经济下的商品价值规律，提出了一个考虑子任务重要性和时间紧迫性的调度算法模型，该调度模型通过模拟市场经济下的商品价值规律，根据网格子任务的特点(重要性和时间紧迫性)有针对性的选择资源，使得选择的资源能够完成用户任务。 2) 建立了一个网格任务调度的性能模型。该模型使任务和资源之间一一映射，并且能够找到其最佳映射方式，使得任务处理代价最优。 3) 改进了一种网格任务代理和资源代理之间的议价算法。该改进算法是基于决策和对策理论，通过将双方的决策赢得函数构造成一个零和矩阵，求其稳定解或次稳定解。在该解下，双方的赢得较大而损失较小，从而达到一个平衡状态。这种议价算法适用于大多数网格任务调度中的议价过程。 4) 设计了一种具有保障性的时间和费用约束的网格任务调度算法(DBOG)。该调度算法是建立在网格任务和网格资源之间一一映射的基础上，通过代理选择具有一定条件的资源，保障网格任务完成。并且该算法符合本文提出的网格任务调度的性能模型条件，因此它在时间和费用上最优。将DBOG调度算法在GridSim仿真工具上进行了仿真研究，从实验研究的角度验证了该算法理论的正确性和可行性；并将该调度算法执行的结果与其他的调度算法进行了比较，结果表明该算法不但在时间和预算上最优，而且能保障任务顺利完成。本文得到了国家自然科学基金(批准号：60773211，60402028)和湖北省武汉市青年晨光计划项目(批准号：20045006071-15)的资助。

目录

文摘

英文文摘

声明

第1章 绪论

1.1本课题来源及研究意义

1.2网格研究现状

1.3本文主要研究工作

1.4本文的结构

第2章网格基本概念

2.1网格的特点

2.2网格体系结构：五层沙漏结构

2.3网格计算工具包及其框架结构

2.3.1 Globus

2.3.2 Legion

2.3.3 Condor-G

2.3.4 Nimrod

2.4网格应用

2.4.1调度程序

2.4.2资源代理

2.4.3负载均衡

2.4.4网格门户

2.5本章小结

第3章一种基于市场经济下商品价值规律模型的网格调度算法

3.1经济模型网格

3.1.1经济模型网格的产生

3.1.2经济模型网格中的经济学原理

3.1.3一种基于Agent的网格经济模型

3.2 Nimrod-G代理的网格任务调度过程

3.2.1 Nimrod-G逻辑结构

3.2.2 Nimrod-G代理的任务调度过程

3.3典型网格任务调度算法

3.3.1极小极小算法(Min-Min)

3.3.2极大极小算法(Max-Min)

3.3.3快速贪婪算法(Fast-Greedyl)

3.4一种基于市场经济下商品价值规律的网格调度算法

3.4.1网格对象描述

3.4.2网格任务调度算法

3.4.3算法执行流程图

3.4.4网格任务调度算法分析

3.4.5算法总结

3.5本章小结

第4章一种具有保障性的时间和费用约束的网格任务调度算法

4.1一种基于博弈论的网格议价改进算法

4.2一种任务调度的性能模型

4.3网格对象描述

4.3.1用户任务描述

4.3.2网格资源描述

4.3.3网格任务调度的数学描述

4.4算法保障性分析

4.5算法保障性证明

4.6算法描述

4.7算法分析

4.8算法总结

4.9数据实例

4.10本章小结

第5章基于GridSim平台的仿真研究

5.1 GridSim仿真器

5.1.1 GridSim仿真器概述

5.1.2 GridSim仿真的特点

5.1.3 GridSim内部体系结构

5.1.4 GridSim仿真过程

5.2具有保障性的时间和费用约束的网格任务调度算法仿真

5.2.1仿真步骤

5.2.2实验结果

5.2.3实验结果分析

5.3本章小结

第6章总结与展望

6.1总结

6.2展望

参考文献

致谢

攻读硕士学位期间发表的论文和参加科研项目情况