Quantifying the Exact Sub-Optimality of Non-Preemptive Scheduling

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

Author(s)

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

Department/unit(s)

Publication details

Title of host publicationReal-Time Systems Symposium (RTSS)
DateAccepted/In press - Dec 2015
Original languageEnglish

Abstract

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.

    Research areas

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

Discover related content

Find related publications, people, projects, datasets and more using interactive charts.

View graph of relations