What is the Exact Speedup Factor for Fixed Priority Pre-emptive versus Fixed Priority Non-pre-emptive Scheduling?
Rob Davis, Oliver Gettings, Abhilash Thekkilakattil, Radu Dobrin, Sasikumar Punnekkat · 2015
The performance of real-time scheduling algorithms can be compared in a number of different ways. Empirical techniques typically rely on generating a large number of task sets with parameters chosen from some appropriate distributions. The performance of the scheduling algorithms is then compared by determining task set schedulability according to exact or sometimes sufficient schedulability tests and plotting a graph of the success ratio (i.e. the proportion of task sets that are deemed schedulable) at different utilisation levels. An alternative theoretical method of comparing real-time scheduling algorithms is to determine the resource augmentation bound or speedup factor [6] required. This approach focuses on those task sets that are particularly difficult to schedule using one algorithm but easy to schedule using another. The Speedup Factor), ( BAS comparing two real-time scheduling algorithms A and B is given by the minimum factor by which the speed of the processor needs to be increased to ensure that any task set that is schedulable according to algorithm B is guaranteed to be schedulable by algorithm A. When comparison is made against an optimal algorithm (OPT), then), ( OPTAS is referred to as the sub-optimality of algorithm A. Combining the utilisation bounds for fixed priority pre-emptive (FP-P) and EDF pre-emptive (EDF-P) scheduling from the seminal paper of Liu and Layland [8] shows that the speedup factor S(FP-P, EDF-P) 44270.1)2ln(/1 ≈ = for implicit deadline task sets. Since EDF-P is an optimal uniprocessor scheduling algorithm [4] this result also determines the sub-optimality of FP-P for implicit deadline task sets. In 2009, Davis et al. [1] derived the exact sub-optimality of FP-P for constrained-deadline task sets; S(FP-P, EDF-P) = 76322.1/1 ≈Ω (where Ω is the mathematical constant defined by