Reservation-Based Federated Scheduling for Parallel Real-Time Tasks

Niklas Ueter, Georg Von Der Brüggen, Jian Jia Chen, Jing Li, Kunal Agrawal

Research output: Chapter in Book/Report/Conference proceedingConference contribution

5 Scopus citations

Abstract

Multicore systems are increasingly utilized in real-time systems in order to address the high computational demands. To fully exploit the advantages of multicore processing, possible intra-task parallelism modeled as a directed acyclic graph (DAG) must be utilized efficiently. This paper considers the scheduling problem for parallel real-time tasks with constrained and arbitrary deadlines. In contrast to prior work in this area, it generalizes federated scheduling and proposes a novel reservation-based approach. Namely, we propose a reservation-based federated scheduling strategy that reduces the problem of scheduling arbitrary-deadline DAG task sets to the problem of scheduling arbitrary-deadline sequential task sets by allocating reservation servers. We provide the general reservation design for sporadic parallel tasks, such that any scheduling algorithm and analysis for sequential tasks with arbitrary deadlines can be used to execute the allocated reservation servers of parallel tasks. Moreover, the proposed reservation-based federated scheduling algorithms provide constant speedup factors with respect to any optimal scheduler for arbitrary-deadline DAG task sets. We demonstrate via numerical and empirical experiments that our algorithms are competitive with the state of the art.

Original languageEnglish (US)
Title of host publicationProceedings - 39th IEEE Real-Time Systems Symposium, RTSS 2018
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages482-494
Number of pages13
ISBN (Electronic)9781538679074
DOIs
StatePublished - Jan 4 2019
Event39th IEEE Real-Time Systems Symposium, RTSS 2018 - Nashville, United States
Duration: Dec 11 2018Dec 14 2018

Publication series

NameProceedings - Real-Time Systems Symposium
Volume2018-December
ISSN (Print)1052-8725

Conference

Conference39th IEEE Real-Time Systems Symposium, RTSS 2018
CountryUnited States
CityNashville
Period12/11/1812/14/18

All Science Journal Classification (ASJC) codes

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications

Keywords

  • DAG
  • Federated Scheduling
  • Parallel Real-Time Tasks
  • Partitioned Scheduling
  • Servers

Fingerprint Dive into the research topics of 'Reservation-Based Federated Scheduling for Parallel Real-Time Tasks'. Together they form a unique fingerprint.

Cite this