Scheduling Self-Suspending Tasks: New and Old Results (Artifact)

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



PDF
Thumbnail PDF

Artifact Description

DARTS.5.1.6.pdf
  • Filesize: 348 kB
  • 3 pages

Document Identifiers

Author Details

Jian-Jia Chen
  • TU Dortmund University, Germany
Tobias Hahn
  • University of Bremen, Germany
Ruben Hoeksma
  • University of Bremen, Germany
Nicole Megow
  • University of Bremen, Germany
Georg von der Brüggen
  • TU Dortmund University, Germany

Acknowledgements

The authors want to thank Junjie Shi for his help in preparing the artifact.

Cite AsGet BibTex

Jian-Jia Chen, Tobias Hahn, Ruben Hoeksma, Nicole Megow, and Georg von der Brüggen. Scheduling Self-Suspending Tasks: New and Old Results (Artifact). In Special Issue of the 31st Euromicro Conference on Real-Time Systems (ECRTS 2019). Dagstuhl Artifacts Series (DARTS), Volume 5, Issue 1, pp. 6:1-6:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/DARTS.5.1.6

Artifact

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.

Subject Classification

ACM Subject Classification
  • Computer systems organization → Real-time systems
Keywords
  • Self-suspension
  • master-slave problem
  • computational complexity
  • speedup factors

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Jian-Jia Chen, Tobias Hahn, Ruben Hoeksma, Nicole Megow, and Georg von der Brüggen. Scheduling Self-Suspending Tasks: New and Old Results. In Proceedings of the 31st Euromicro Conference on Real-Time Systems (ECRTS 2019), 2019. Google Scholar
  2. Sartaj Sahni and George L. Vairaktarakis. The master-slave paradigm in parallel computer and industrial settings. J. Global Optimization, 9(3-4):357-377, 1996. Google Scholar
  3. Georg von der Brüggen, Wen-Hung Huang, Jian-Jia Chen, and Cong Liu. Uniprocessor Scheduling Strategies for Self-Suspending Task Systems. In Proceedings of the 24th International Conference on Real-Time Networks and Systems, RTNS 2016, Brest, France, October 19-21, 2016, pages 119-128, 2016. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail