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.
Our objective are to predict behavior for a
system with limited priority granularity with stochastic tasks,•
provide worst case performance guarantees in a soft real-time environment,
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
worst case with unknown deadline distribution. We found: