Quantifying the Suboptimality of Uniprocessor Fixed Priority Pre-emptive Scheduling for Sporadic Tasksets with Arbitrary Deadlines

R.I. Davis, T. Rothvoss, S. K. Baruah, A. Burns

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

Abstract

This paper examines the relative effectiveness of fixed priority pre-emptive scheduling in a uniprocessor system, compared to an optimal algorithm such as Earliest Deadline First (EDF). 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 taskset that is schedulable according to an optimal scheduling algorithm can be scheduled using fixed priority pre-emptive scheduling. For implicit-deadline tasksets, the speedup factor is 1/ln(2). For constrained-deadline tasksets, the speedup factor is 1/Omega = 1.76322. In this paper, we show that for arbitrary-deadline tasksets, the speedup factor is lower bounded by 1/Omega and upper bounded by 2. Further, when deadline monotonic priority assignment is used, we show that the speedup factor is exactly 2.
Original languageEnglish
Title of host publicationInternational conference on Real-Time and Network Systems
Publication statusPublished - Oct 2009

Keywords

  • real-time
  • scheduling
  • schedulability analysis
  • fixed priority
  • EDF
  • speedup factors
  • resource augmentation
  • uniprocessor

Cite this