一种基于动态决策路径的网格任务调度算法  

A New Scheduling Algorithm in Grid Based on Dynamic Decisive Path

作　　者：林剑柠[1] 吴慧中[2] 

机构地区：[1]中国电子科技集团第28研究所国防C4ISR重点实验室,南京210007 [2]南京理工大学计算机科学与技术学院,南京210094

出　　处：《计算机研究与发展》2008年第5期841-847,共7页Journal of Computer Research and Development

摘　　要：网格下的任务调度是一个NP问题.一些迭代算法例如遗传算法可以较有效地解决,但是迭代次数过多时间复杂度高.传统的启发式策略则往往会造成资源空闲时刻过多,反而延误整个程序的完成时间.采用一种"先调度、后优化"的思想,首先采用普通的启发式算法得到调度方案,然后根据得到的甘特图重新生成DAG图,生成决策任务和决策路径,采用启发式算法将决策任务尽可能提前调度到资源的空闲时段提前运行,达到缩短整个任务收敛时间的目的,同时给出任务之间的死锁判定方法.实验证明,新算法优于其他启发式算法.Grid environment is an open, dynamic and changeful application environment, in which task scheduling is a hot topic of grid environment research in recent years. Task scheduling in grid environment is a NP problem. How to choose effective resource to run the tasks is an important problem. Although some iterative methods, such as GA, can solve it effectively. However it will spend too much time scheduling too many tasks. And some custom heuristic algorithms often cause the spare time slots in the resource. So in this paper a new heuristic algorithm is addressed based on the idea which is scheduling the tasks first, and then optimizing them. First it uses the common heuristic algorithm to schedule the tasks, and then a new DAG can be rebuilt and the decisive tasks and decisive path can be constructed. After that the decisive tasks will be re-scheduled to the new resource which includes the fit spare time slots in order to advance the decisive task and its child tasks. Also adopted in this paper is a new method to judge the deadlock between tasks in the DAG so that the tasks could be completed normally. Simulation tests prove that the heuristic algorithm can tackle the NP problem in a simple and efficient way.

关 键 词：决策任务 网格计算 启发式 调度 死锁 

分 类 号：TP312[自动化与计算机技术—计算机软件与理论]