License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ECRTS.2023.18
URN: urn:nbn:de:0030-drops-180477
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18047/
Go to the corresponding LIPIcs Volume Portal

Aromolo, Federico ; Nelissen, Geoffrey ; Biondi, Alessandro

Replication-Based Scheduling of Parallel Real-Time Tasks

pdf-format:
LIPIcs-ECRTS-2023-18.pdf (0.8 MB)

Abstract

Multiprocessors have become the standard computing platform for real-time embedded systems. To efficiently leverage the computational power of such platforms, software tasks are often characterized by an internal structure where concurrent subtasks can execute in parallel on different processors. Existing strategies for the scheduling of parallel real-time tasks on multiprocessor platforms, such as partitioned, global, and federated scheduling, were inspired by earlier techniques that were not conceived to explicitly support parallel tasks, thus carrying advantages but also well-known limitations. This paper introduces replication-based scheduling, a specialized scheduling paradigm for parallel real-time DAG tasks. Replication-based scheduling leverages the internal structure of the parallel tasks to assign replicas of the subtasks to different processors, while ensuring that exactly one replica of each subtask will be executed at runtime for every task instance. This approach aims at preserving the advantages of partitioned scheduling while simplifying the timing analysis. The replication-based scheduling framework is first defined, together with a strategy for implementing replication-based scheduling in real-time operating systems. Then, offline allocation strategies for subtask replicas and a response-time analysis are presented. In the provided experiments, the schedulability achieved with replication-based scheduling is compared with that of existing techniques for the scheduling of parallel real-time tasks on multiprocessors.

BibTeX - Entry

@InProceedings{aromolo_et_al:LIPIcs.ECRTS.2023.18,
  author =	{Aromolo, Federico and Nelissen, Geoffrey and Biondi, Alessandro},
  title =	{{Replication-Based Scheduling of Parallel Real-Time Tasks}},
  booktitle =	{35th Euromicro Conference on Real-Time Systems (ECRTS 2023)},
  pages =	{18:1--18:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-280-8},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{262},
  editor =	{Papadopoulos, Alessandro V.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/18047},
  URN =		{urn:nbn:de:0030-drops-180477},
  doi =		{10.4230/LIPIcs.ECRTS.2023.18},
  annote =	{Keywords: Real-Time Systems, Scheduling Algorithms, Schedulability Analysis, Parallel Tasks}
}

Keywords: Real-Time Systems, Scheduling Algorithms, Schedulability Analysis, Parallel Tasks
Collection: 35th Euromicro Conference on Real-Time Systems (ECRTS 2023)
Issue Date: 2023
Date of publication: 03.07.2023

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI