| 【中文题名】 | 网格计算中启发式任务调度算法的研究 |
| 【英文题名】 | The Research of Heuristic Task Scheduling Algorithm for Grid Computing |
| 【学科专业】 | 计算机应用技术 |
| 【论文级别】 | 硕士论文 |
| 【投稿时间】 | 2007-11-6 |
| 【中关键词】 | 网格计算,任务调度,禁忌,偏差,信任,任务复制 |
| 【英关键词】 | grid computing,tasks scheduling,tabu,deviation,trust,task duplication, |
| 【分类导航】 | 工业技术>自动化技术、计算机技术>计算技术、计算机技术>计算机的应用>计算机网络>一般性问题 |
| 【论文摘要】 |
网格是高性能计算和信息服务的战略性基础设施，而网格技术已成为下一代互联网应用的关键技术。网格可分为多种类型，但不论什么样的网格，网格调度系统都是其发挥潜在性能和优势所共有的核心系统，而任务调度模型及其优化算法则是网格调度系统必须解决的核心基础问题和关键技术。
由于任务调度问题是NP完全问题，因此启发式调度算法得到了学术界的高度重视。针对网格中传统的启发式调度算法，本文主要工作包括以下几部分：
1．首先介绍了网格计算的概念和目的、体系结构、网格计算的关键技术及主要的应用领域并指出任务调度的重要性；然后引入了任务调度的模型，在此基础上详细阐述了网格调度的过程，并对目前调度算法研究现状进行了总结。
2．采用了不同与传统算法设计的思维模式，提出基于禁忌思想的网格调度新算法—Tabu_MaxLoad。该算法通过禁止任务被分配到计算资源上，直到每个任务都只有一个可用资源，仿真结果表明，与经典的优秀算法Min-min、Max-min相比，该算法明显地降低了调度的时间跨度。
3．通过对Min-min算法的分析和研究，针对Min-min算法的缺陷，提出基于最小偏差的网格调度算法(Dev... |
| 【论文题纲】 |
|
摘要 |
5-7 |
|
ABSTRACT |
7-9 |
|
目录 |
9-12 |
|
第一章 绪论 |
12-22 |
|
1.1 研究背景 |
12-19 |
|
1.1.1 网格计算概念和目的 |
12-14 |
|
1.1.2 网格计算体系结构 |
14-17 |
|
1.1.3 网格计算的关键技术 |
17-18 |
|
1.1.4 网格的主要应用领域 |
18-19 |
|
1.2 研究内容 |
19-20 |
|
1.2.1 本文研究重点 |
19 |
|
1.2.2 研究的网格环境 |
19-20 |
|
1.3 论文结构 |
20-21 |
|
1.4 本章小结 |
21-22 |
|
第二章 网格中的任务调度研究 |
22-35 |
|
2.1 网格计算任务调度的特点和主要目标 |
22-24 |
|
2.1.1 任务调度的特点 |
22-23 |
|
2.1.2 任务调度的主要目标 |
23-24 |
|
2.2 网格调度模型 |
24-28 |
|
2.2.1 网格资源组织模型 |
24-27 |
|
2.2.2 调度模型 |
27-28 |
|
2.2.3 网格应用模型 |
28 |
|
2.3 网格调度过程 |
28-30 |
|
2.3.1 作业提交 |
28-29 |
|
2.3.2 收集可用资源静态信息 |
29 |
|
2.3.3 资源预选 |
29 |
|
2.3.4 资源动态信息查询 |
29 |
|
2.3.5 制订调度计划，资源预约初始化 |
29-30 |
|
2.3.6 作业运行时监控 |
30 |
|
2.4 网格任务调度算法的研究 |
30-34 |
|
2.4.1 启发式任务调度算法 |
30-32 |
|
2.4.2 基于Agent的任务调度 |
32-33 |
|
2.4.3 基于Petri网的任务调度模型 |
33 |
|
2.4.4 基于经济模型的网格资源调度算法 |
33-34 |
|
2.5 本章小结 |
34-35 |
|
第三章 基于禁忌思想的网格调度算法 |
35-44 |
|
3.1 问题的提出 |
35-36 |
|
3.1.1 传统算法分析 |
35-36 |
|
3.1.2 禁忌搜索的思想 |
36 |
|
3.1.3 基于禁忌思想的算法提出 |
36 |
|
3.2 基于禁忌思想的算法 |
36-39 |
|
3.2.1 算法思想 |
36-37 |
|
3.2.2 算法描述 |
37-39 |
|
3.3 实验结果与分析 |
39-43 |
|
3.3.1 实验内容与设置 |
39-40 |
|
3.3.2 仿真结果与性能分析 |
40-43 |
|
3.4 本章小结 |
43-44 |
|
第四章 基于最小偏差的网格调度算法 |
44-52 |
|
4.1 均值理论及偏差定义 |
44-45 |
|
4.2 Min-Min算法的缺陷 |
45-47 |
|
4.3 最小偏差算法思想 |
47-48 |
|
4.4 基于最小偏差的算法描述 |
48-49 |
|
4.5 实验结果与分析 |
49-51 |
|
4.6 本章小结 |
51-52 |
|
第五章 基于优先级的信任驱动网格任务调度算法 |
52-63 |
|
5.1 信任关系量化研究 |
52-55 |
|
5.1.1 基本定义 |
52-53 |
|
5.1.2 信任量化方法 |
53-55 |
|
5.2 信任驱动模型与问题描述 |
55-58 |
|
5.2.1 信任驱动模型 |
55-56 |
|
5.2.2 信任效益函数 |
56-58 |
|
5.3 基于优先级的信任驱动调度算法 |
58-62 |
|
5.3.1 算法描述 |
58-59 |
|
5.3.2 实验结果与分析 |
59-62 |
|
5.4 本章小结 |
62-63 |
|
第六章 基于任务复制和费用-时间优化的DAG任务调度算法 |
63-75 |
|
6.1 问题的提出 |
63-65 |
|
6.1.1 经济模型的优点 |
63-64 |
|
6.1.2 基于任务复制的调度 |
64-65 |
|
6.2 算法模型及相关概念 |
65-66 |
|
6.2.1 算法模型 |
65 |
|
6.2.2 相关概念 |
65-66 |
|
6.3 算法介绍 |
66-71 |
|
6.3.1 算法基本思想 |
66-67 |
|
6.3.2 任务映射策略 |
67 |
|
6.3.3 获取任务簇 |
67-69 |
|
6.3.4 优化任务簇 |
69-71 |
|
6.4 实验结果与分析 |
71-73 |
|
6.4.1 算法仿真 |
71 |
|
6.4.2 实验结果分析 |
71-73 |
|
6.5 本章小结 |
73-75 |
|
第七章 总结和展望 |
75-78 |
|
7.1 本文总结 |
75-76 |
|
7.2 展望 |
76-78 |
|
参考文献 |
78-86 |
|
致谢 |
86-87 |
|
作者读研期间参与的科研项目与发表的论文 |
87 |
|
| 【DOI】 | LunWen.ID:2.2008.376526 |
