分布式系统中处理机的任务调度算法研究——智能算法在网格任务调度中的研究

摘要

网格作为典型的分布式应用系统，由大量分布共享的异构资源组成，这些资源协同提供了巨大的计算能力。由于网格计算中资源具有在广域上分布、自主管理、本质上异构、负载动态变化等特性，使得网格环境下的任务调度所面临的问题比传统分布式环境要复杂得多，是一个NP完全问题(除极少数特殊情况外)。调度技术一直为计算机学者们研究的焦点，是网格的核心技术，它可以描述为合理解决计算任务在地理分布的各种资源之间的动态调度。总的来说，一个好的任务调度算法其关键的技术参数是在最短的时间内实现最优分配策略，从而提高系统资源的利用率以及保持系统较好的系统负载均衡。 本文通过对智能算法--蚁群与遗传算法的深入研究，将它们引入到网格任务调度中，提出了基于改进型蚁群算法的网格任务调度技术与基于蚁群与遗传混合算法的网格任务调度技术。 基于改进型蚁群算法的网格任务调度技术，主要针对现有网格任务调度算法负载均衡、资源利用率、跨度等方面的不足而提出。该算法的关键问题就是如何确定负载，使各个结点的负载基本趋于均衡，以达到网格系统任务调度要求总的执行时间最小以及系统的利用率最高。蚁群算法的正反馈特性容易导致搜索结果过早的陷入局部最优，改进型蚁群算法针对这一现象做出一系列改进：增加信息素权值、增加挥发平衡因子、引入前辈们提出的转移概率准则以及对信息素总量进行限制。 蚁群算法基于随机搜索的特性，在算法的初期按启发信息进行求解，收敛速度缓慢。通过对遗传算法的研究，本文针对具有快速响应要求的网格任务调度提出了以仿真时间为优先目标的蚁群与遗传混合算法，该调度算法将蚁群与遗传算法混合应用于网格任务调度中，取两种算法之所长，去其所短，优势互补，从而在时间效率上优于蚁群算法。新算法在满足调度的限定条件之前采用遗传算法，充分利用遗传算法的群体性、快速搜索等优势生成初始解(即产生有关问题的初始信息素分布)，随后采用本文提出的基于奖励因子的蚁群算法，在有一定初始信息素分布的情况下，最大限度地利用蚁群算法的正反馈性来快速求解任务的最优解。 通过使用基于SimJava的网格资源调度模拟工具包GridSim仿真验证了如上算法，取得了令人满意的效果。

目录

文摘

英文文摘

声明

第一章绪论

1.1课题研究背景

1.2网格概述

1.2.1网格的概念

1.2.2网格的特点

1.2.3网格计算的发展与关键技术

1.3网格体系结构

1.3.1五层沙漏结构

1.3.2开放网格服务体系结构

1.4网格应用领域

1.5网格的研究现状

1.6论文的主要工作

1.7论文的组织结构

第二章网格任务调度研究

2.1网格任务调度概述

2.2网格任务调度特点与目标

2.2.1网格任务调度特点

2.2.2网格任务调度目标

2.3网格任务调度模型

2.4网格任务调度过程

2.5目前常见的任务调度算法

2.5.1传统型任务调度算法

2.5.2智能化任务调度算法

2.6本章小结

第三章蚁群算法基本原理

3.1蚁群算法概述

3.1.1真实蚁群的觅食现象

3.1.2人工蚁群与真实蚁群的联系

3.2蚁群算法基本原理

3.3蚁群系统模型

3.4蚁群算法的应用领域

3.5蚁群算法的研究进展

3.6用蚁群算法进行网格任务调度的思路

3.7本章小结

第四章基于改进型蚁群算法的网格任务调度研究

4.1算法改进

4.2仿真试验及分析

4.2.1网格模拟器的选择

4.2.2 GridSim模拟器介绍

4.2.3仿真试验

4.2.4结论与分析

4.3本章小结

第五章基于蚁群与遗传混合算法的网格任务调度研究

5.1遗传算法简介

5.1.1遗传算法的主要步骤

5.1.2遗传算法的基本构成

5.2基于遗传与蚁群的混合算法

5.2.1遗传算法部分

5.2.2蚁群算法部分

5.2.3混合算法过程

5.3仿真试验及分析

5.3.1仿真试验

5.3.2结论与分析

5.4本章小结

第六章结论和未来的工作

6.1工作总结

6.2下一步工作展望

致谢

参考文献

附录： 作者在攻读硕士学位期间发表的论文