A Method for Performance Analysis of Earliest-Deadline-First Scheduling Policy |
| |
Authors: | Mehdi Kargahi Ali Movaghar |
| |
Affiliation: | (1) Department of Computer Engineering, Sharif University of Technology, Tehran, Iran |
| |
Abstract: | This paper introduces an analytical method to approximate the fraction of jobs missing their deadlines in a soft real-time
system when the earliest-deadline-first (EDF) scheduling policy is used. In the system, jobs either all have deadlines until
the beginning of service (DBS) and are non-preemptive, or have deadlines until the end of service (DES) and are preemptive.
In the former case, the system is represented by an M/M/m/EDF+G model, i.e., a multi-sever queue with Poisson arrival, exponential service, and generally distributed relative deadlines.
In the latter case, it is represented by an M/M/1/EDF+G model, i.e., a single-server queue with the same specifications as before. EDF is known to be optimal in both of the above
cases. The optimality property of EDF scheduling policy is used for the estimation of a key parameter, namely the loss rate
when there are n jobs in the system. The estimation is possible by assuming an upper bound and a lower bound for this parameter and then linearly
combining these two bounds together. The resulting Markov chains can then be easily solved numerically. Comparing numerical
and simulation results, we find that the existing errors are relatively small. |
| |
Keywords: | analytical methods approximation methods earliest-deadline-first (EDF) multiprocessor systems performance modeling soft real-time (SRT) systems |
本文献已被 SpringerLink 等数据库收录! |
|