License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ECRTS.2017.13
URN: urn:nbn:de:0030-drops-71659
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7165/
Go to the corresponding LIPIcs Volume Portal

Casini, Daniel ; Biondi, Alessandro ; Buttazzo, Giorgio

Semi-Partitioned Scheduling of Dynamic Real-Time Workload: A Practical Approach Based on Analysis-Driven Load Balancing

pdf-format:
LIPIcs-ECRTS-2017-13.pdf (0.9 MB)

Abstract

Recent work showed that semi-partitioned scheduling can achieve near-optimal schedulability performance, is simpler to implement compared to global scheduling, and less heavier in terms of runtime overhead, thus resulting in an excellent choice for implementing real-world systems. However, semi-partitioned scheduling typically leverages an off-line design to allocate tasks across the available processors, which requires a-priori knowledge of the workload. Conversely, several simple global schedulers, as global earliest-deadline first (G-EDF), can transparently support dynamic workload without requiring a task-allocation phase. Nonetheless, such schedulers exhibit poor worst-case performance.

This work proposes a semi-partitioned approach to efficiently schedule dynamic real-time workload on a multiprocessor system. A linear-time approximation for the C=D splitting scheme under partitioned EDF scheduling is first presented to reduce the complexity of online scheduling decisions. Then, a load-balancing algorithm is proposed for admitting new real-time workload in the system with limited workload re-allocation. A large-scale experimental study shows that the linear-time approximation has a very limited utilization loss compared to the exact technique and the proposed approach achieves very high schedulability performance, with a consistent improvement on G-EDF and pure partitioned EDF scheduling.

BibTeX - Entry

@InProceedings{casini_et_al:LIPIcs:2017:7165,
  author =	{Daniel Casini and Alessandro Biondi and Giorgio Buttazzo},
  title =	{{Semi-Partitioned Scheduling of Dynamic Real-Time Workload: A Practical Approach Based on Analysis-Driven Load Balancing}},
  booktitle =	{29th Euromicro Conference on Real-Time Systems (ECRTS 2017)},
  pages =	{13:1--13:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-037-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{76},
  editor =	{Marko Bertogna},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7165},
  URN =		{urn:nbn:de:0030-drops-71659},
  doi =		{10.4230/LIPIcs.ECRTS.2017.13},
  annote =	{Keywords: Semi-partitioned scheduling, dynamic workload, real-time}
}

Keywords: Semi-partitioned scheduling, dynamic workload, real-time
Collection: 29th Euromicro Conference on Real-Time Systems (ECRTS 2017)
Issue Date: 2017
Date of publication: 23.06.2017

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