Output details

Exact quantification of the sub-optimality of uniprocessor fixed priority pre-emptive scheduling

<07>The most influential paper in real-time scheduling research is arguably Liu and Layland’s seminal work from 1973 that characterises the maximum performance penalty in using fixed priority pre-emptive scheduling rather than an optimal algorithm (Earliest Deadline First), for tasks with deadlines equal to their periods. Since 1973, the equivalent problem for the more practical case of tasks with deadlines no greater than their periods has been open. This paper closes that problem, providing an answer, proven from first principles in Theorem 4 (Lemmas 1-13), as well as a disparate proof of Liu and Layland’s famous result (Theorem 8, Corollary 9).