Quantifying the advantage of EDF vs. RMS schedulability on a uniprocessor using a differential analysis and a power-law total utilization distribution
Dirk Müller, Matthias Werner · 2013
Contrary to the optimal scheduling algorithm Earliest Deadline First (EDF), Rate-Monotonic Scheduling (RMS) can lead to non-schedulable task sets for total utilizations below 1 on a uniprocessor. The quantification of this deficiency has been a topic in real-time science for a long time. We show weaknesses of the scheduling algorithm metrics breakdown utilization, utilization upper bound, and numerical optimality degree. Finally, we suggest a new measure of schedulability called Efficiency and calculate its bounds. It turns out that numerical optimality degree might be too optimistic depending on the assumed total utilization distribution. The main results are the application of a power-law total utilization distribution to quantify the RMS-to-EDF Efficiency and a step-by-step derived lower bound of this Efficiency. We apply a differential analysis of schedulability.