Optimal partitioning for quantized EDF scheduling

The quantized earliest deadline first (Q-EDF) scheduling policy assumes a limited number of priority levels available to express task (or packet) deadlines. This situation arises in computer and communication systems in which priority levels must be expressed using a limited number of bits. The range of possible deadlines is partitioned into bins, and a task whose deadline lies within the range of a bin is assigned a quantized deadline equal to the left endpoint of the bin. We assume soft real-time tasks arrive according to a renewal process, have random service requirements, and have random deadlines drawn from a probability distribution. Using real-time queueing theory, a general method for computing the long run fraction of tasks that miss their actual deadlines (or their quantized deadlines) is presented. Results are given for uniform deadline distributions, and the optimal bin partitioning is determined for this distribution. The theoretical results show excellent agreement with simulation results. Finally, assuming only the min, mean, and max task deadlines are specified, we determine the worst-case deadline distribution given any specified priority bin choice, then optimize the priority bin choice to minimize the worst-case lateness relative to EDF. For this Q-EDF partition, we determine the number of bins needed to achieve a given performance relative to EDF. We show that for practical cases with soft deadlines, 3 bits are sufficient to achieve nearly the same performance with Q-EDF as with pure EDF.