Overview People Publications Sponsors Links




Quantized EDF Scheduling


Modern computing systems are becoming increasingly powerful with respect to computing resources, the size of temporary and permanent storage, bandwidth and interconnectivity. At the same time, application capabilities and user demands are also rapidly increasing. Therefore, even as the available resources grow, an improper resource management policy can lead to resource conflicts across applications and lower the quality of service delivered to applications. For real-time applications, sophisticated resource management policies are crucial to be able to guarantee that the timing requirements of those tasks are met. 

In real-time system research area, the EDF (Earliest Deadline First) scheduling algorithm has been long studied, and is known to offer high levels of schedulable utilization; however, it requires an infinite granularity of priorities. In reality, an infinite set of priorities is impossible to achieve, especially in small real-time devices or in communication systems in which task priorities must be expressed using a small set of priority bits. In such systems, the relative deadline must be quantized and added to the clock time before it is inserted into the priority queue. We call this scheme Quantized EDF (Q-EDF).  Typical examples may include embedded real-time devices such as sensors, mobile network devices, etc. 


                                          Sensor Networks                                                    Equipment Networks

Our objective are to predict behavior for a system with limited priority granularity with stochastic tasks, to provide worst case performance guarantees in a soft real-time environment, and to optimize the performance of Quantized EDF scheduling.

In this project, we defined the model for Quantized EDF Scheduling (Q-EDF) and its lateness was analyzed.  With the methodolgy of Real-Time Queueing Theory (RTQT), we analyzed the performance with known deadline distribution, also the worst case with unknown deadline distribution. We found:  


Uniform partition is the optimal partition for uniform deadlines.
Given first two moments of the incoming tasks, deadline range and mean deadline, uniform partition is the optimal partition for the worst case of unknown deadline distributions
(Counter-intuitive since the worst-case analysis for fixed priority scheduling recommended logarithmic partitioning)
In many practical cases, 3-bits (8 bins) are sufficient to encode relative deadline with minimal loss.