Quantifying the Sub-optimality of Uniprocessor Fixed Priority Pre-emptive Scheduling for Sporadic Tasksets with Arbitrary Deadlines
R.I. Davis, T. Rothvoß, S.K. Baruah and A. Burns
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)≈1.44270. For constrained-deadline tasksets, the speedup factor is 1/Ω≈1.76322. In this paper, we show that for arbitrary-deadline tasksets, the speedup factor is lower bounded by 1/Ω≈1.76322 and upper bounded by 2. Further, when deadline monotonic priority assignment is used, we show that the speedup factor is exactly 2.
BibTex Entry
@inproceedings{Davis2009c,
abstract_html = { },
author = {R.I. Davis and T. Rothvoß and S.K. Baruah and A. Burns},
booktitle = {Real-Time Networks and Systems Conference},
title = {Quantifying the Sub-optimality of Uniprocessor Fixed Priority Pre-emptive Scheduling for Sporadic Tasksets with Arbitrary Deadlines},
year = {2009}
}