Muntz and Coffman give a level algorithm that constructs optimal preemptive schedules on identical processors when the task system is a tree or when there are only two processors. A variation of their algorithm is adapted for processors of different speeds. The algorithm is shown to be optimal on two processors for arbitrary task systems, but not on three or more processors even for trees. Taking the algorithm as a heuristic on m processors and using the ratio of the lengths of the constructed and optimal schedules as a measure, we show that, on identical processors, its performance is bounded by 2 - 2/m. Moreover 2 - 2/m is a best bound in that there exist task systems for which this ratio is approached arbitrarily closely. On processors of different speeds, we derive an upper bound of its performance in terms of the speeds of the given processor system and show that @@@@1.5m is an upper bound over all processor systems. We also give an example of a system for which the bound @@@@m/2 @@@@2 canbe approached asymptotically, thus establishing that the @@@@1.5m bound can at most be improved by a constant factor.
Muntz和Coffman提供了一种级别算法,当任务系统是一棵树或只有两个处理器时,该算法可在相同的处理器上构造最佳的抢先式计划。他们算法的一种变体适用于不同速度的处理器。对于任意任务系统,该算法在两个处理器上显示最佳,即使对于树,在三个或更多处理器上也不是最佳算法。以该算法作为对m个处理器的启发式算法,并使用所构造和最佳调度的长度之比作为度量,我们表明,在相同的处理器上,其性能受2-2 / m的限制。此外,2-2 / m是最佳界限,因为存在一些任务比率可以任意接近的任务系统。在不同速度的处理器上,我们根据给定处理器系统的速度得出其性能的上限,并表明@@@@ 1.5m是所有处理器系统的上限。我们还给出了一个系统的示例,对于该系统,可以渐近逼近@@@@ m / 2 @@@@ 2的边界,因此可以确定@@@@ 1.5m的边界最多可以提高一个常数。 / P>
机译:具有偏移量的固定优先级抢占式调度的可调度性分析和优先级分配的高效算法
机译:两台均匀机器上带排斥的先占和非先占在线算法
机译:基于抢占式硬件调度程序引擎和不同调度算法的nMPRA CPU体系结构的实现
机译:先发制人的行为分析与优先调度算法的改进
机译:公平最短的作业优先:用于软实时系统的抢先式调度算法。
机译:使用同步综合从非抢占式调度到抢占式调度
机译:具有优先级和延迟约束的实时系统的非抢占式调度算法和可调度性条件
机译:非抢占式时间扭曲调度算法。