TY - GEN
T1 - Analysis of EDF for Real-Time Multiprocessor Systems with Resource Sharing
AU - Agrawal, Kunal
AU - Baruah, Sanjoy
AU - Fineman, Jeremy T.
AU - Marchetti-Spaccamela, Alberto
AU - Zhao, Jinhao
N1 - Publisher Copyright:
© Kunal Agrawal, Sanjoy Baruah, Jeremy T. Fineman, Alberto Marchetti-Spaccamela, and Jinhao Zhao.
PY - 2025/7/7
Y1 - 2025/7/7
N2 - The classic Earliest Deadline First (EDF) algorithm is widely studied and used due to its simplicity and strong theoretical performance, but has not been rigorously analyzed for systems where jobs may execute critical sections protected by shared locks. Analyzing such systems is often challenging due to unpredictable delays caused by contention. In this paper, we propose a straightforward generalization of EDF, called EDF-Block. In this generalization, the critical sections are executed non-preemptively, but scheduling and lock acquisition priorities are based on EDF. We establish lower bounds on the speed augmentation required for any non-clairvoyant scheduler (EDF-Block is an example of non-clairvoyant schedulers) and for EDF-Block, showing that EDF-Block requires at least 4.11× speed augmentation for jobs and 4× for tasks. We then provide an upper bound analysis, demonstrating that EDF-Block requires speedup of at most 6 to schedule all feasible job and task sets.
AB - The classic Earliest Deadline First (EDF) algorithm is widely studied and used due to its simplicity and strong theoretical performance, but has not been rigorously analyzed for systems where jobs may execute critical sections protected by shared locks. Analyzing such systems is often challenging due to unpredictable delays caused by contention. In this paper, we propose a straightforward generalization of EDF, called EDF-Block. In this generalization, the critical sections are executed non-preemptively, but scheduling and lock acquisition priorities are based on EDF. We establish lower bounds on the speed augmentation required for any non-clairvoyant scheduler (EDF-Block is an example of non-clairvoyant schedulers) and for EDF-Block, showing that EDF-Block requires at least 4.11× speed augmentation for jobs and 4× for tasks. We then provide an upper bound analysis, demonstrating that EDF-Block requires speedup of at most 6 to schedule all feasible job and task sets.
KW - Competitive Analysis
KW - EDF
KW - Non-Clairvoyant Scheduling
KW - Real-Time Scheduling
KW - Shared Resources
UR - https://www.scopus.com/pages/publications/105010613928
U2 - 10.4230/LIPIcs.ECRTS.2025.15
DO - 10.4230/LIPIcs.ECRTS.2025.15
M3 - Conference contribution
AN - SCOPUS:105010613928
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 37th Euromicro Conference on Real-Time Systems, ECRTS 2025
A2 - Mancuso, Renato
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 37th Euromicro Conference on Real-Time Systems, ECRTS 2025
Y2 - 8 July 2025 through 11 July 2025
ER -