摘要
网格下的任务调度是一个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.
出处
《计算机研究与发展》
EI
CSCD
北大核心
2008年第5期841-847,共7页
Journal of Computer Research and Development
关键词
决策任务
网格计算
启发式
调度
死锁
decisive task
grid computing
heuristic
scheduling
deadlock
