Dynamic routing of real-time jobs among parallel EDF queues: A performance study |
| |
Authors: | Mehdi Kargahi [Author Vitae] Ali Movaghar [Author Vitae] |
| |
Affiliation: | a School of Computer Science, IPM, P.O. Box: 19395-5746, Tehran, Iran b Department of Computer Engineering, Sharif University of Technology, P.O. Box: 11365-9517, Tehran, Iran |
| |
Abstract: | This paper introduces an analytical method for approximating the performance of a firm 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 the number of jobs in each queue. Migration among the queues is not allowed. An important performance measure to consider 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 for at least three different stationary policies, we find that the existing errors are relatively small. |
| |
Keywords: | Approximation methods Dynamic routing policies Earliest-deadline-first (EDF) scheduling algorithm Performance analysis Firm real-time systems |
本文献已被 ScienceDirect 等数据库收录! |
|