Non-preemptive earliest-deadline-first scheduling policy: a performance study

This paper introduces an analytical method for approximating the performance of a soft real-time system modeled by a single-server queue. The service discipline in the queue is earliest-deadline-first (EDF), which is an optimal scheduling policy. Real-time jobs with exponentially distributed deadlines arrive according to a Poisson process. All jobs have deadlines until the end of service and are served non-preemptively. Occurrences of transient faults in the server are also taken into account. The important performance measure to calculate is the loss probability due to deadline misses and/or transient faults. The system is approximated by a Markovian model in the long run. A key parameter, namely, the loss rate when there are n jobs in the system is used in the model, which is estimated by partitioning the system into two virtual subsystems. The resulting model can then be solved analytically using standard Markovian solution techniques. Comparing numerical and simulation results, we find that the existing errors are relatively small.