2026-08-15T21:28:32Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23593 2025-10-27T10:21:53Z ddc:004 open_access

Analysis of EDF for Real-Time Multiprocessor Systems with Resource Sharing Agrawal, Kunal Baruah, Sanjoy Fineman, Jeremy T. Marchetti-Spaccamela, Alberto Zhao, Jinhao Real-Time Scheduling Non-Clairvoyant Scheduling EDF Competitive Analysis Shared Resources 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Kunal Agrawal and Sanjoy Baruah and Jeremy T. Fineman and Alberto Marchetti-Spaccamela and Jinhao Zhao 2025 Is Part Of LIPIcs, Volume 335, 37th Euromicro Conference on Real-Time Systems (ECRTS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ECRTS.2025.15 urn:nbn:de:0030-drops-235932 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2025.15 eng https://creativecommons.org/licenses/by/4.0/legalcode