2026-09-30T21:36:34Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26586 2026-09-29T14:35:27Z ddc:004 open_access

Preempt Less, Schedule Better: Revisiting PCG for Real-Time Uniform Processors Hamdani, Yahya Richard, Pascal Bertout, Antoine Goossens, Joël Grolleau, Emmanuel Real-Time Scheduling Uniform Multiprocessor Platforms We address the problem of scheduling periodic implicit-deadline real-time tasks on m uniform processors. We introduce PCG^*, an optimal TL-plane algorithm based on PCG [Chen and Hsueh, 2008], which guarantees at most 2(m - 1) preemptions per TL-plane, matching the best-known theoretical bound for uniform platforms. The proposed algorithm advances the state of the art by offering an optimal real-time scheduling solution with a tight preemption bound within TL-planes. The numerical experiments presented in this work provide strong evidence that PCG^* yields a substantial reduction in the number of preemptions relative to PCG. When applied to identical processor platforms, PCG^* is also a best-possible polynomial time algorithm in terms of preemptions in a TL-plane, matching the (m-1) preemption bound achieved by LRE-TL [Funk, 2010]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Yahya Hamdani and Pascal Richard and Antoine Bertout and Joël Goossens and Emmanuel Grolleau 2026 Is Part Of LIPIcs, Volume 375, 38th European Conference on Real-Time Systems (ECRTS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ECRTS.2026.2 urn:nbn:de:0030-drops-265863 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2026.2 eng https://creativecommons.org/licenses/by/4.0/legalcode