Scheduling self-suspending tasks: New and old results

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

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

4 Downloads (Pure)

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.

Original languageEnglish
Title of host publication31st Euromicro Conference on Real-Time Systems, ECRTS 2019
EditorsSophie Quinton
PublisherDagstuhl
Pages1-23
Number of pages23
ISBN (Electronic)9783959771108
DOIs
Publication statusPublished - 1 Jul 2019
Externally publishedYes
Event31st Euromicro Conference on Real-Time Systems, ECRTS 2019 - Stuttgart, Germany
Duration: 9 Jul 201912 Jul 2019
Conference number: 31

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume133
ISSN (Print)1868-8969

Conference

Conference31st Euromicro Conference on Real-Time Systems, ECRTS 2019
Abbreviated titleECRTS 2019
CountryGermany
CityStuttgart
Period9/07/1912/07/19

Keywords

  • Computational complexity
  • Master-slave problem
  • Self-suspension
  • Speedup factors

Fingerprint Dive into the research topics of 'Scheduling self-suspending tasks: New and old results'. Together they form a unique fingerprint.

Cite this