Dynamic Routing of Real-Time Jobs among Parallel EDF Queues: A Performance Study

This paper introduces an analytical method for approximating the performance of a soft real-time system consisting of a number of parallel infinite-capacity single-server queues. The service discipline for the individual queues is earliest-deadline-first (EDF). Real-time jobs with exponentially distributed relative deadlines arrive according to a Poisson process. Jobs either all have deadlines until the beginning of service or deadlines until the end of service. Upon arrival, a job joins a queue according to a state-dependent stationary policy, where the state of the system is derived from the number of jobs in each queue. Migration among the queues is not allowed. The important performance measure to calculate is the overall loss probability of the system. The system is approximated by a Markovian model in the long run. 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.

Keywords:

approximation methods , dynamic routing , earliestdeadline-first (EDF) scheduling policy , performance analysis , soft real-time systems