基于关键路径的网格任务调度算法研究

摘要

随着网络技术的飞速发展，互联网上充斥着更多可以利用的廉价资源。利用此类资源的网格计算解决规模庞大、复杂问题具有重要的意义。网格资源具有规模庞大、分布异构和动态性等特点。实现高效的网格计算需要解决许多复杂的问题，任务调度问题就是其中的一个关键问题。 网格资源动态性主要反应在资源能力衰减、增强以及新资源的加入和旧资源的退出。以往的很多调度算法主要关注调度方案制定，直接将任务加入到资源节点的待执行任务序列，忽略了方案制定时和方案执行时资源能力的变化。若在方案制定时的资源能力在方案执行时衰减(退出)，使得高权限任务占有了低性能资源，造成任务执行时间增加，有可能增加整个应用的并行完成时间(Makespan)；若在方案制定时的资源能力在方案执行时增强，任务执行时间减小，有可能减小整个应用的Makespan；当新资源加入时，由于已经为任务分配资源，所以不影响任务执行时间和整个应用的Makespan。 为了减小资源能力衰减引起应用Makespan增加的程度，以及增加能力出众的新加入资源对作业Makespan的影响，本算法根据调度执行开始时间(BT)将任务调度分为调度方案制定(TSPF)和调度方案执行(TSPE)两个阶段，定义了网格环境下的调度执行最晚开始时间、调度执行开始时间和任务优先图(DAG)中边的权值，分析了任务图冻结消减和执行消减对任务图结构的影响以及方案制定和方案执行时间的资源能力变化对调度准确性的影响。 基于关键路径的调度算法(CPA)认为，尽量提前任务优先图关键路径中每个任务的完成时间，就能缩短整个作业的Makespan，即关键路径上的任务具有更高的优先权。但是，与基于最早开始时间的调度算法(ETF)比较发现，最早开始时间同样影响着作业Makespan，且在一定条件下ETF算法优于CPA算法。 当前大多数调度算法主要通过预防抢夺解决资源抢夺，即在任何情况下都不允许资源抢夺。本算法在关键路径算法的基础上，根据关键路径长度(CP)定义了任务优先权，并且考虑最早开始时间对作业Makespan的影响，允许未分配资源的任务抢夺已经被任务占有的资源。在此基础上定义了资源抢夺和调度最小图，分析了资源抢夺有可能出现的几种情况，以及对任务图和调度结果的影响，并且针对一种资源抢夺情况，提出了两个启发式原则用以决定是否允许资源抢夺。 最后，提出了基于BT的允许资源抢夺的网格依赖任务调度算法(BTTS)。重点分析了网格模拟平台GridSim，并在此平台上实现ETF算法、CPA算法和BTTS算法，试验结果发现BTTS算法优于其它两种算法，且有效地降低了网格动态性对调度结果的影响。

目录

文摘

英文文摘

论文说明：图表目录

声明

致谢

第一章 绪论

1.1课题来源

1.2本文的目的和意义

1.3网格计算与任务调度研究概况

1.3.1网格计算研究概况

1.3.2网格任务调度研究概况

1.4本文研究内容

1.5本文主要工作及组织结构

第二章 网格与网格任务调度

2.1网格及网格计算

2.2网格体系结构

2.2.1五层沙漏结构

2.2.2开放式网格服务体系结构(OGSA)

2.3网格任务调度

2.3.1网格任务调度原理

2.3.2网格任务调度特点及主要目标

2.3.3网格任务调度算法研究

2.4小结

第三章 网格资源的管理与抢夺

3.1网格资源管理模型

3.1.1分层模型

3.1.2抽象所有者模型

3.1.3计算经济模型

3.2网格资源能力管理

3.3资源抢夺

3.4小结

第四章 基于BT的网格任务调度

4.1任务依赖DAG图

4.2任务调度

4.3任务图削减

4.4基于DAG图的资源抢夺

4.5基于BT网格任务调度算法

4.6小结

第五章 BTTS算法实现以及结果分析

5.1算法仿真平台

5.2 BTTS算法实现

5.3实验结果及分析

5.4小结

第六章 总结与展望

6.1论文总结

6.2进一步工作

参考文献

攻读硕士学位期间发表的论文