Abstract
This paper examines the relative effectiveness of fixed priority non-pre-emptive scheduling (FP-NP) in a uniprocessor system, compared to an optimal workconserving non-pre-emptive algorithm; Earliest Deadline First (EDF-NP). 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 EDF-NP can be scheduled using FP-NP scheduling. For sporadic tasksets with implicit, constrained, or arbitrary deadlines, the speedup factor is shown to be lower bounded by 1/Ω ≈ 1.76322 and upper bounded by 2. We also report the results of empirical investigations
into the speedup factor required to ensure schedulability in the non-pre-emptive case.
defined as the factor by which processor speed needs to increase to ensure that any taskset that is schedulable according to EDF-NP can be scheduled using FP-NP scheduling. For sporadic tasksets with implicit, constrained, or arbitrary deadlines, the speedup factor is shown to be lower bounded by 1/Ω ≈ 1.76322 and upper bounded by 2. We also report the results of empirical investigations
into the speedup factor required to ensure schedulability in the non-pre-emptive case.
| Original language | English |
|---|---|
| Title of host publication | International Conference on Real-Time and Network Systems |
| Publication status | Published - Nov 2010 |
Keywords
- real-time
- scheduling
- speedup factor
- resource augmentation
- EDF
- fixed priority
- uniprocessor
- schedulability analysis