调度In-Tree图的启发函数构造

在分析了其它同类启发函数的构造机理后,克服"以当前任务具有最早起始执行时刻"贪心方法构造启发函数的缺点,提出了基于任务复制,"以当前任务的直接后继具有最早起始执行时刻"为目标来构造动态启发函数的方案.通过理论证明与模拟实验表明:所构造的启发函数具有较强的启发能力,对In＿Tree图的调度具有较好的效果.这对研究实时分布式计算机系统的任务调度算法具有理论和实际意义.

一种调度In-Tree任务图的算法

In-Tree任务图可用来表示归并、求和等分治算法的很多问题,该文针对这种任务图提出一种分层调度算法,利用队列存放被调度的任务,在同层任务调度中,优先把前驱不为空的任务调度到其一个前驱处理器上执行,只有前驱为空的任务才考虑是否分配新的处理器。实验表明,与以前的算法相比,该算法在调度长度相当的情况下,使用了更少的处理器。