Quantifying the Exact Sub-Optimality of Non-Preemptive Scheduling

Robert Ian Davis, Abhilash Thekkilakattil, Oliver Gettings, Radu Dobrin, Sasikumar Punnekkat

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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. schedulablability 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),
which since it matches a recently published upper bound gives
the exact sub-optimality for EDF-NP.
It is known that neither preemptive, nor non-preemptive
fixed priority scheduling dominates the other, i.e., 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 upper and lower bounds on
the speed-up factor required to guarantee FP-P feasibility of
any FP-NP feasible task set. Empirical evidence suggests that
the lower bound may be tight, and hence equate to the exact
speed-up factor in this case.
Original languageEnglish
Title of host publicationReal-Time Systems Symposium (RTSS)
Publication statusAccepted/In press - Dec 2015


  • EDF
  • fixed priority
  • uniprocessor
  • resource augmentation
  • real-time
  • speedup factor
  • sub-optimality
  • non-preemptive scheduling
  • preemptive scheduling

Cite this