TY - GEN
T1 - Tardiness bounds for global EDF with deadlines different from periods
AU - Erickson, Jeremy
AU - Guan, Nan
AU - Baruah, Sanjoy
PY - 2010/12/1
Y1 - 2010/12/1
N2 - The Earliest Deadline First (EDF) scheduling algorithm is known to be suboptimal for meeting all deadlines under global scheduling on multiprocessor platforms. However, EDF is an attractive choice for scheduling soft-real-time systems on multiprocessors. Previous work has demonstrated that the maximum tardiness is bounded, and has derived formulas for computing tardiness bounds, in EDF-scheduled real-time systems that can be modeled as collections of recurrent tasks modeled using the well-known implicit-deadline (Liu and Layland) task model. This research extends the applicability of previous techniques to systems that are modeled using the more general arbitrary sporadic task model. It also improves on prior work even for implicit-deadline systems. An algorithm is derived here that computes tardiness bounds in polynomial time. Previously, these bounds could only have been approximated in sub-exponential time.
AB - The Earliest Deadline First (EDF) scheduling algorithm is known to be suboptimal for meeting all deadlines under global scheduling on multiprocessor platforms. However, EDF is an attractive choice for scheduling soft-real-time systems on multiprocessors. Previous work has demonstrated that the maximum tardiness is bounded, and has derived formulas for computing tardiness bounds, in EDF-scheduled real-time systems that can be modeled as collections of recurrent tasks modeled using the well-known implicit-deadline (Liu and Layland) task model. This research extends the applicability of previous techniques to systems that are modeled using the more general arbitrary sporadic task model. It also improves on prior work even for implicit-deadline systems. An algorithm is derived here that computes tardiness bounds in polynomial time. Previously, these bounds could only have been approximated in sub-exponential time.
UR - http://www.scopus.com/inward/record.url?scp=78650924043&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-17653-1_22
DO - 10.1007/978-3-642-17653-1_22
M3 - Conference article published in proceeding or book
SN - 3642176526
SN - 9783642176524
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 286
EP - 301
BT - Principles of Distributed Systems - 14th International Conference, OPODIS 2010, Proceedings
T2 - 14th International Conference on Principles of Distributed Systems, OPODIS 2010
Y2 - 14 December 2010 through 17 December 2010
ER -