Exact quantification of the sub-optimality of uniprocessor fixed priority pre-emptive scheduling
Exact quantification of the sub-optimality of uniprocessor fixed priority pre-emptive scheduling
复制标题
单处理器固定优先级抢占式调度次优性的精确量化
作者：
Robert I. Davis;T. Rothvoss;Sanjoy Baruah;A. Burns
本文研究了单处理器系统中固定优先级抢占式调度与最优算法（如 "最早截止日期优先"（EDF））相比的相对有效性。比较中使用的定量指标是处理器加速因子，相当于处理器速度需要提高多少才能确保根据最优调度算法可调度的任何任务集都能使用固定优先级抢占式调度进行调度（假设优先级分配策略为最优）。对于所有任务截止日期都小于或等于其周期的受限截止日期任务集，处理器加速因子的最大值为 1/Ω≈1.76322（其中 Ω 是由超越方程 ln (1/Ω)=Ω 定义的数学常数，因此 Ω≈0.567143）。此外，对于隐式截止日期任务集（所有任务的截止日期都等于其周期），处理器加速因子的最大值为 1/ln (2)≈1.44270 。后一结果的推导为著名的刘和雷兰结果提供了另一种证明。
This paper examines the relative effectiveness of fixed priority pre-emptive scheduling in a uniprocessor system, compared to an optimal algorithm such as Earliest Deadline First (EDF).The quantitative metric used in this comparison is the processor speedup factor, equivalent to the factor by which processor speed needs to increase to ensure that any taskset that is schedulable according to an optimal scheduling algorithm can be scheduled using fixed priority pre-emptive scheduling, assuming an optimal priority assignment policy.For constrained-deadline tasksets where all task deadlines are less than or equal to their periods, the maximum value for the processor speedup factor is shown to be 1/Ω≈1.76322 (where Ω is the mathematical constant defined by the transcendental equation ln (1/Ω)=Ω, hence, Ω≈0.567143). Further, for implicit-deadline tasksets where all task deadlines are equal to their periods, the maximum value for the processor speedup factor is shown to be 1/ln (2)≈1.44270. The derivation of this latter result provides an alternative proof of the well-known Liu and Layland result.