Publication
This paper examines the relative effectiveness of fixed priority pre-emptive scheduling in a uniprocessor system, compared to an optimal algorithm. 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. The maximum value for the processor speedup factor is shown to be 1/Omega = 1.76322 for tasksets where all task deadlines are less than or equal to their periods, and 1/ln(2) = 1.44270 for tasksets where all task deadlines are equal to their periods. The derivation of this latter result provides an alternative proof of the well-know Liu and Layland result.We refer to this factor as the processor speedup factor for fixed priority pre- emptive scheduling. Liu and Layland (1973) considered the pre-emptive scheduling of synchronous1 tasksets comprising independent periodic tasks, with bounded execution times, and deadlines equal to their periods. We refer to such tasksets as implicit-deadline tasksets. Liu and Layland showed that Earliest Deadline First (EDF) can schedule any implicit-deadline taskset with a total utilisation2 less than or equal to 100% ( 1 ≤ U ). Liu and Layland also showed that rate monotonic3 priority assignment is the optimal fixed priority assignment policy for implicit-deadline tasksets, and that using this priority assignment policy, fixed priority pre- emptive scheduling can schedule any implicit-deadline