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}
}

Document

DOI: 10.4230/LITES-v003-i001-a004

Optimal Scheduling of Periodic Gang Tasks

Authors: Joël Goossens and Pascal Richard

Published in: LITES, Volume 3, Issue 1 (2016). Leibniz Transactions on Embedded Systems, Volume 3, Issue 1

Abstract

The gang scheduling of parallel implicit-deadline periodic task systems upon identical multiprocessor platforms is considered. In this scheduling problem, parallel tasks use several processors simultaneously. We propose two DPFAIR (deadline partitioning) algorithms that schedule all jobs in every interval of time delimited by two subsequent deadlines. These algorithms define a static schedule pattern that is stretched at run-time in every interval of the DPFAIR schedule. The first algorithm is based on linear programming and is the first one to be proved optimal for the considered gang scheduling problem. Furthermore, it runs in polynomial time for a fixed number m of processors and an efficient implementation is fully detailed. The second algorithm is an approximation algorithm based on a fixed-priority rule that is competitive under resource augmentation analysis in order to compute an optimal schedule pattern. Precisely, its speedup factor is bounded by (2-1/m). Both algorithms are also evaluated through intensive numerical experiments.

Cite as

Joël Goossens and Pascal Richard. Optimal Scheduling of Periodic Gang Tasks. In LITES, Volume 3, Issue 1 (2016). Leibniz Transactions on Embedded Systems, Volume 3, Issue 1, pp. 04:1-04:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@Article{goossens_et_al:LITES-v003-i001-a004,
  author =	{Goossens, Jo\"{e}l and Richard, Pascal},
  title =	{{Optimal Scheduling of Periodic Gang Tasks}},
  journal =	{Leibniz Transactions on Embedded Systems},
  pages =	{04:1--04:18},
  ISSN =	{2199-2002},
  year =	{2016},
  volume =	{3},
  number =	{1},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LITES-v003-i001-a004},
  URN =		{urn:nbn:de:0030-drops-192593},
  doi =		{10.4230/LITES-v003-i001-a004},
  annote =	{Keywords: Real-time systems, Scheduling, Parallel tasks}
}

Search Results

Documents authored by Richard, Pascal

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

Abstract

Cite as

Optimal Scheduling of Periodic Gang Tasks

Abstract

Cite as

Thanks for your feedback!

Could not send message