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, equivalent to 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, assuming an optimal priority assignment policy.
For constrained-deadline tasksets where all task deadlines are less than or equal to their periods, the maximum value for the processor speedup factor is shown to be 1/Omega a parts per thousand 1.76322 (where Omega is the mathematical constant defined by the transcendental equation ln (1/Omega)=Omega, hence, Omega a parts per thousand 0.567143). Further, for implicit-deadline tasksets where all task deadlines are equal to their periods, the maximum value for the processor speedup factor is shown to be 1/ln (2)a parts per thousand 1.44270. The derivation of this latter result provides an alternative proof of the well-known Liu and Layland result.
| Original language | English |
|---|---|
| Pages (from-to) | 211-258 |
| Number of pages | 48 |
| Journal | Real-Time Systems |
| Volume | 43 |
| Issue number | 3 |
| Early online date | 17 Jul 2009 |
| DOIs | |
| Publication status | Published - 1 Nov 2009 |
Keywords
- real-time
- schedulability analysis
- EDF
- fixed priority
- speedup factor
- resource augmentation