Exact comparison of fixed priority and EDF scheduling based on speedup factors for both pre-emptive and non-pre-emptive paradigms

Robert Ian Davis, Alan Burns, Sanjoy Baruah, Thomas Rothvoss, Laurent George, Oliver Gettings

Research output: Contribution to journalArticlepeer-review

Abstract

This paper investigates the relative effectiveness of fixed priority (FP) scheduling in a uniprocessor system compared to Earliest Deadline First (EDF) scheduling. The quantitative metric used in this comparison is the processor speedup factor, defined as the factor by which processor speed needs to increase to ensure that any task set that is schedulable according to EDF can be scheduled using fixed priorities. In the pre-emptive case, exact speedup factors are known for sporadic task sets with implicit or constrained deadlines. In this paper, we derive exact speedup factors for both pre-emptive and non-pre-emptive fixed priority scheduling of arbitrary deadline sporadic task sets. We also show that the exact speedup factor for the preemptive case holds when tasks share resources according to the Stack Resource Policy / Deadline Floor Protocol.
Original languageEnglish
Pages (from-to)566-601
JournalReal-Time Systems
Volume51
Issue number5
DOIs
Publication statusPublished - Sept 2015

Keywords

  • REAL-TIME
  • speedup factor
  • uniprocessor
  • EDF
  • fixed priority
  • scheduling

Cite this