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.2019.16
URN: urn:nbn:de:0030-drops-107532
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10753/
Go to the corresponding LIPIcs Volume Portal

Chen, Jian-Jia ; Hahn, Tobias ; Hoeksma, Ruben ; Megow, Nicole ; von der Brüggen, Georg

Scheduling Self-Suspending Tasks: New and Old Results

pdf-format:
LIPIcs-ECRTS-2019-16.pdf (0.7 MB)

Abstract

In computing systems, a job may suspend itself (before it finishes its execution) when it has to wait for certain results from other (usually external) activities. For real-time systems, such self-suspension behavior has been shown to induce performance degradation. Hence, the researchers in the real-time systems community have devoted themselves to the design and analysis of scheduling algorithms that can alleviate the performance penalty due to self-suspension behavior. As self-suspension and delegation of parts of a job to non-bottleneck resources is pretty natural in many applications, researchers in the operations research (OR) community have also explored scheduling algorithms for systems with such suspension behavior, called the master-slave problem in the OR community.
This paper first reviews the results for the master-slave problem in the OR literature and explains their impact on several long-standing problems for scheduling self-suspending real-time tasks. For frame-based periodic real-time tasks, in which the periods of all tasks are identical and all jobs related to one frame are released synchronously, we explore different approximation metrics with respect to resource augmentation factors under different scenarios for both uniprocessor and multiprocessor systems, and demonstrate that different approximation metrics can create different levels of difficulty for the approximation. Our experimental results show that such more carefully designed schedules can significantly outperform the state-of-the-art.

BibTeX - Entry

@InProceedings{chen_et_al:LIPIcs:2019:10753,
  author =	{Jian-Jia Chen and Tobias Hahn and Ruben Hoeksma and Nicole Megow and Georg von der Br{\"u}ggen},
  title =	{{Scheduling Self-Suspending Tasks: New and Old Results}},
  booktitle =	{31st Euromicro Conference on Real-Time Systems (ECRTS 2019)},
  pages =	{16:1--16:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-110-8},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{133},
  editor =	{Sophie Quinton},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/10753},
  URN =		{urn:nbn:de:0030-drops-107532},
  doi =		{10.4230/LIPIcs.ECRTS.2019.16},
  annote =	{Keywords: Self-suspension, master-slave problem, computational complexity, speedup factors}
}

Keywords: Self-suspension, master-slave problem, computational complexity, speedup factors
Collection: 31st Euromicro Conference on Real-Time Systems (ECRTS 2019)
Issue Date: 2019
Date of publication: 02.07.2019
Supplementary Material: ECRTS 2019 Artifact Evaluation approved artifact available at https://dx.doi.org/10.4230/DARTS.5.1.6

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