Exact Speedup Factors and Sub-Optimality for Non-Preemptive Scheduling

Robert Ian Davis, Abhilash Thekkilakattil, Oliver Gettings, Radu Dobrin, Sasikumar Punnekkat, Jian-Jia Chen

Research output: Contribution to journalArticlepeer-review


Fixed priority scheduling is used in many real-time systems; however, both preemptive and non-preemptive variants (FP-P and FP-NP) are known to be sub-optimal when compared to an optimal uniprocessor scheduling algorithm such as preemptive earliest deadline first (EDF-P). In this paper, we investigate the sub-optimality of fixed priority non-preemptive scheduling. Specifically, we derive the exact processor speed-up factor required to guarantee the feasibility under FP-NP (i.e. schedulability assuming an optimal priority assignment) of any task set that is feasible under EDF-P. As a consequence of this work, we also derive a lower bound on the sub-optimality of non-preemptive EDF (EDF-NP). As this lower bound matches a recently published upper bound for the same quantity, it closes the exact sub-optimality for EDF-NP. It is known that neither preemptive, nor non-preemptive fixed priority scheduling dominates the other, in other words, there are task sets that are feasible on a processor of unit speed under FP-P that are not feasible under FP-NP and vice-versa. Hence comparing these two algorithms, there are non-trivial speedup factors in both directions. We derive the exact speed-up factor required to guarantee the FP-NP feasibility of any FP-P feasible task set. Further, we derive the exact speed-up factor required to guarantee FP-P feasibility of any constrained-deadline FP-NP feasible task set.
Original languageEnglish
Pages (from-to)1-39
Number of pages39
JournalReal-Time Systems
Publication statusPublished - 28 Oct 2017

Bibliographical note

© The Author(s) 2017.


  • Real-time
  • Uniprocessor
  • Resource augmentation
  • Speedup factor
  • Sub-optimality
  • Non-preemptive scheduling
  • Preemptive scheduling
  • EDF
  • Fixed priority

Cite this