Search Results

Documents authored by Grolleau, Emmanuel

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
Artifact
DOI: 10.4230/DARTS.8.1.4
Scheduling Offset-Free Systems Under FIFO Priority Protocol (Artifact)

Authors: Matheus Ladeira, Emmanuel Grolleau, Fabien Bonneval, Gautier Hattenberger, Yassine Ouhammou, and Yuri Hérouard

Published in: DARTS, Volume 8, Issue 1, Special Issue of the 34th Euromicro Conference on Real-Time Systems (ECRTS 2022)

Abstract
On UAVs, telemetry messages are often sent following a FIFO schedule, and some messages, depending on the FIFO queue state may suffer long delays, and can even be lost if the FIFO queue is full. Considering the high complexity of the problem of assigning offsets to periodic tasks, we propose a new heuristic, called GCD+, that we compare to the methods of the state of the art, showing that GCD+ significantly outperforms them on synthetic tasks sets. Then we use a real UAV use case, based on Paparazzi autopilot, to show that GCD+ behaves well. The proposed algorithm is meant to be the new Paparazzi’s automatic offset assignment method for messages.
Cite as

Matheus Ladeira, Emmanuel Grolleau, Fabien Bonneval, Gautier Hattenberger, Yassine Ouhammou, and Yuri Hérouard. Scheduling Offset-Free Systems Under FIFO Priority Protocol (Artifact). In Special Issue of the 34th Euromicro Conference on Real-Time Systems (ECRTS 2022). Dagstuhl Artifacts Series (DARTS), Volume 8, Issue 1, pp. 4:1-4:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@Article{ladeira_et_al:DARTS.8.1.4,
  author =	{Ladeira, Matheus and Grolleau, Emmanuel and Bonneval, Fabien and Hattenberger, Gautier and Ouhammou, Yassine and H\'{e}rouard, Yuri},
  title =	{{Scheduling Offset-Free Systems Under FIFO Priority Protocol (Artifact)}},
  pages =	{4:1--4:2},
  journal =	{Dagstuhl Artifacts Series},
  ISSN =	{2509-8195},
  year =	{2022},
  volume =	{8},
  number =	{1},
  editor =	{Ladeira, Matheus and Grolleau, Emmanuel and Bonneval, Fabien and Hattenberger, Gautier and Ouhammou, Yassine and H\'{e}rouard, Yuri},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DARTS.8.1.4},
  URN =		{urn:nbn:de:0030-drops-165000},
  doi =		{10.4230/DARTS.8.1.4},
  annote =	{Keywords: Scheduling, non-preemptible, heuristics, FIFO, autopilot}
}
Document
DOI: 10.4230/LIPIcs.ECRTS.2022.11
Scheduling Offset-Free Systems Under FIFO Priority Protocol

Authors: Matheus Ladeira, Emmanuel Grolleau, Fabien Bonneval, Gautier Hattenberger, Yassine Ouhammou, and Yuri Hérouard

Published in: LIPIcs, Volume 231, 34th Euromicro Conference on Real-Time Systems (ECRTS 2022)

Abstract
On UAVs, telemetry messages are often sent following a FIFO schedule, and some messages, depending on the FIFO queue state may suffer long delays, and can even be lost if the FIFO queue is full. Considering the high complexity of the problem of assigning offsets to periodic tasks, we propose a new heuristic, called GCD+, that we compare to the methods of the state of the art, showing that GCD+ significantly outperforms them on synthetic tasks sets. Then we use a real UAV use case, based on Paparazzi autopilot, to show that GCD+ behaves well. The proposed algorithm is meant to be the new Paparazzi’s automatic offset assignment method for messages.
Cite as

Matheus Ladeira, Emmanuel Grolleau, Fabien Bonneval, Gautier Hattenberger, Yassine Ouhammou, and Yuri Hérouard. Scheduling Offset-Free Systems Under FIFO Priority Protocol. In 34th Euromicro Conference on Real-Time Systems (ECRTS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 231, pp. 11:1-11:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{ladeira_et_al:LIPIcs.ECRTS.2022.11,
  author =	{Ladeira, Matheus and Grolleau, Emmanuel and Bonneval, Fabien and Hattenberger, Gautier and Ouhammou, Yassine and H\'{e}rouard, Yuri},
  title =	{{Scheduling Offset-Free Systems Under FIFO Priority Protocol}},
  booktitle =	{34th Euromicro Conference on Real-Time Systems (ECRTS 2022)},
  pages =	{11:1--11:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-239-6},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{231},
  editor =	{Maggio, Martina},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2022.11},
  URN =		{urn:nbn:de:0030-drops-163281},
  doi =		{10.4230/LIPIcs.ECRTS.2022.11},
  annote =	{Keywords: Scheduling, non-preemptible, heuristics, FIFO, autopilot}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact