Quantized
EDF Scheduling
Performance
with Known Distribution
When the system has only two priority levels, i.e. two priority bins, the
system quantizes the deadline in the following way.
Under such situation, we want to know what the lateness in each priority bin
and total lateness are. Further, we want to know what is the best
partitioning (i.e. the optimal choice of L) for the priority bins. The
following three figures show the lateness of priority bin 1, bin 2 and total
lateness on different partition point L when the deadline is uniformly
distributed. We found uniform partitioning is the best partitioning in
this case. This conclusion has been extended to multiple bins.
When there are multiple priority bins, there maybe many different partitioning
strategies: uniform partitioning, logarithmic partitioning, and other partitionings.
 
By minimizing the lateness against all partitioning points, we found for a uniform deadline
distribution, uniform bin partitioning is the optimal partitioning for minimizing the lateness.
|
Q-MARS
