DROPS

Document

DOI: 10.4230/LIPIcs.ECRTS.2026.2

Preempt Less, Schedule Better: Revisiting PCG for Real-Time Uniform Processors

Authors: Yahya Hamdani, Pascal Richard, Antoine Bertout, Joël Goossens, and Emmanuel Grolleau

Published in: LIPIcs, Volume 375, 38th European Conference on Real-Time Systems (ECRTS 2026)

Abstract

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].

Cite as

Yahya Hamdani, Pascal Richard, Antoine Bertout, Joël Goossens, and Emmanuel Grolleau. Preempt Less, Schedule Better: Revisiting PCG for Real-Time Uniform Processors. In 38th European Conference on Real-Time Systems (ECRTS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 375, pp. 2:1-2:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{hamdani_et_al:LIPIcs.ECRTS.2026.2,
  author =	{Hamdani, Yahya and Richard, Pascal and Bertout, Antoine and Goossens, Jo\"{e}l and Grolleau, Emmanuel},
  title =	{{Preempt Less, Schedule Better: Revisiting PCG for Real-Time Uniform Processors}},
  booktitle =	{38th European Conference on Real-Time Systems (ECRTS 2026)},
  pages =	{2:1--2:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-429-1},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{375},
  editor =	{Kritikakou, Angeliki},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2026.2},
  URN =		{urn:nbn:de:0030-drops-265863},
  doi =		{10.4230/LIPIcs.ECRTS.2026.2},
  annote =	{Keywords: Real-Time Scheduling, Uniform Multiprocessor Platforms}
}

Search Results

Documents authored by Bertout, Antoine

Preempt Less, Schedule Better: Revisiting PCG for Real-Time Uniform Processors

Abstract

Cite as

Thanks for your feedback!

Could not send message