Document Open Access Logo

Scheduling Self-Suspending Tasks: New and Old Results

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

PDF
Thumbnail PDF

File

LIPIcs.ECRTS.2019.16.pdf
  • Filesize: 0.67 MB
  • 23 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

Funding

  • Hoeksma, Ruben: Partially funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) – Project Number 146371743 – TRR 89 Invasive Computing.
  • Megow, Nicole: Partially funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) – Project Number 146371743 – TRR 89 Invasive Computing.

Acknowledgements

The authors thank Minming Li from City University of Hong Kong and Guillaume Sagnol from TU Berlin, for discussions in an early stage of this research. The authors also thank the organizing committee of MAPSP 2017 for planning a discussion session during the workshop, which initialized the study in this paper.

Cite As Get BibTex

Jian-Jia Chen, Tobias Hahn, Ruben Hoeksma, Nicole Megow, and Georg von der Brüggen. Scheduling Self-Suspending Tasks: New and Old Results. In 31st Euromicro Conference on Real-Time Systems (ECRTS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 133, pp. 16:1-16:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.ECRTS.2019.16

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
    0
    Metadata Views

Supplementary Materials

References

  1. Neil C. Audsley and Konstantinos Bletsas. Fixed Priority Timing Analysis of Real-Time Systems with Limited Parallelism. In 16th Euromicro Conference on Real-Time Systems (ECRTS), pages 231-238, 2004. URL: http://dx.doi.org/10.1109/ECRTS.2004.12.
  2. Neil C. Audsley and Konstantinos Bletsas. Realistic Analysis of Limited Parallel Software / Hardware Implementations. In Real-Time and Embedded Technology and Applications Symposium (RTAS), pages 388-395, 2004. URL: http://dx.doi.org/10.1109/RTTAS.2004.1317285.
  3. Sanjoy K. Baruah and Joël Goossens. Scheduling Real-Time Tasks: Algorithms and Complexity. In Joseph Y.-T. Leung, editor, Handbook of Scheduling: Algorithms, Models, and Performance Analysis, chapter 28. CRC Press, 2003. Google Scholar
  4. Enrico Bini and Giorgio C Buttazzo. Measuring the performance of schedulability tests. Real-Time Systems, 30(1-2):129-154, 2005. Google Scholar
  5. Konstantinos Bletsas and Neil C. Audsley. Extended Analysis with Reduced Pessimism for Systems with Limited Parallelism. In 11th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA), pages 525-531, 2005. URL: http://dx.doi.org/10.1109/RTCSA.2005.48.
  6. Vincenzo Bonifaci, Alberto Marchetti-Spaccamela, Nicole Megow, and Andreas Wiese. Polynomial-Time Exact Schedulability Tests for Harmonic Real-Time Tasks. In Proceedings of the IEEE 34th Real-Time Systems Symposium, RTSS 2013, Vancouver, BC, Canada, December 3-6, 2013, pages 236-245. IEEE Computer Society, 2013. Google Scholar
  7. Jian-Jia Chen. Computational Complexity and Speedup Factors Analyses for Self-Suspending Tasks. In Real-Time Systems Symposium (RTSS), pages 327-338, 2016. Google Scholar
  8. Jian-Jia Chen and Björn B. Brandenburg. A Note on the Period Enforcer Algorithm for Self-Suspending Tasks. LITES, 4(1):01:1-01:22, 2017. Google Scholar
  9. Jian-Jia Chen and Cong Liu. Fixed-Relative-Deadline Scheduling of Hard Real-Time Tasks with Self-Suspensions. In Real-Time Systems Symposium (RTSS), pages 149-160, 2014. Google Scholar
  10. Jian-Jia Chen, Geoffrey Nelissen, Wen-Hung Huang, Maolin Yang, Björn Brandenburg, Konstantinos Bletsas, Cong Liu, Pascal Richard, Frédéric Ridouard, Neil Audsley, Raj Rajkumar, Dionisio de Niz, and Georg von der Brüggen. Many suspensions, many problems: a review of self-suspending tasks in real-time systems. Real-Time Systems, September 2018. Google Scholar
  11. Jian-Jia Chen, Georg von der Brüggen, Wen-Hung Huang, and Robert I. Davis. On the Pitfalls of Resource Augmentation Factors and Utilization Bounds in Real-Time Scheduling. In 29th Euromicro Conference on Real-Time Systems, ECRTS, pages 9:1-9:25, 2017. Google Scholar
  12. Jian-Jia Chen, Georg von der Brüggen, Wen-Hung Huang, and Cong Liu. State of the art for scheduling and analyzing self-suspending sporadic real-time tasks. In 23rd IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA, 2017. Google Scholar
  13. Mauro Dell'Amico. Shop Problems With Two Machines and Time Lags. Operations Research, 44(5):777-787, 1996. Google Scholar
  14. UmaMaheswari C. Devi. An Improved Schedulability Test for Uniprocessor Periodic Task Systems. In 15th Euromicro Conference on Real-Time Systems (ECRTS), pages 23-32, 2003. Google Scholar
  15. Zheng Dong, Cong Liu, Soroush Bateni, Kuan-Hsun Chen, Jian-Jia Chen, Georg von der Brüggen, and Junjie Shi. Shared-Resource-Centric Limited Preemptive Scheduling: A Comprehensive Study of Suspension-base Partitioning Approaches. In Proceedings of the 24th IEEE Real-Time and Embedded Technology and Applications Symposium, 2018. Google Scholar
  16. R.L. Graham, E.L. Lawler, J.K. Lenstra, and A.H.G. Rinnooy Kan. Optimization and approximation in deterministic sequencing and scheduling : a survey. Annals of Discrete Mathematics, 5:287-326, 1979. Google Scholar
  17. José C. Palencia Gutiérrez and Michael González Harbour. Schedulability Analysis for Tasks with Static and Dynamic Offsets. In Proceedings of the 19th IEEE Real-Time Systems Symposium, Madrid, Spain, December 2-4, 1998, pages 26-37. IEEE Computer Society, 1998. Google Scholar
  18. Tobias Hahn. Algorithms for scheduling with mandatory suspensions: worst-case and empirical analysis. Master’s thesis, University of Bremen, 2019. Google Scholar
  19. Arne Hamann, Dakshina Dasari, Simon Kramer, Michael Pressler, and Falk Wurst. Communication Centric Design in Complex Automotive Embedded Systems. In 29th Euromicro Conference on Real-Time Systems, ECRTS 2017, pages 10:1-10:20, 2017. Google Scholar
  20. Wen-Hung Huang and Jian-Jia Chen. Self-Suspension Real-Time Tasks under Fixed-Relative-Deadline Fixed-Priority Scheduling. In Design, Automation, and Test in Europe (DATE), pages 1078-1083, 2016. Google Scholar
  21. Wen-Hung Huang, Jian-Jia Chen, and Jan Reineke. MIRROR: symmetric timing analysis for real-time tasks on multicore platforms with shared resources. In Proceedings of the 53rd Annual Design Automation Conference, DAC, pages 158:1-158:6, 2016. Google Scholar
  22. Wen-Hung Huang, Jian-Jia Chen, Husheng Zhou, and Cong Liu. PASS: Priority assignment of real-time tasks with dynamic suspending behavior under fixed-priority scheduling. In Proceedings of the 52nd Annual Design Automation Conference (DAC), 2015. Google Scholar
  23. Wen-Hung Huang, Maolin Yang, and Jian-Jia Chen. Resource-Oriented Partitioned Scheduling in Multiprocessor Systems: How to Partition and How to Share? In Real-Time Systems Symposium (RTSS), pages 111-122, 2016. Google Scholar
  24. Bala Kalyanasundaram and Kirk Pruhs. Speed is As Powerful As Clairvoyance. Journal of ACM, 47(4):617-643, July 2000. Google Scholar
  25. W. Kang, S. Son, J. Stankovic, and M. Amirijoo. I/O-Aware Deadline Miss Ratio Management in Real-Time Embedded Databases. In Proc. of the 28th IEEE Real-Time Systems Symp., pages 277-287, 2007. Google Scholar
  26. W. Kern and W. Nawijn. Scheduling multi-operation jobs with time lags on a single machine. In 2nd Twente Workshop on Graphs and Combinatorial, 1991. Google Scholar
  27. In-Guk Kim, Kyung-Hee Choi, Seung-Kyu Park, Dong-Yoon Kim, and Man-Pyo Hong. Real-time scheduling of tasks that contain the external blocking intervals. In RTCSA, 1995. URL: http://dx.doi.org/10.1109/RTCSA.1995.528751.
  28. Simon Kramer, Dirk Ziegenbein, and Arne Hamann. Real world automotive benchmarks for free. In 6th International Workshop on Analysis Tools and Methodologies for Embedded and Real-time Systems (WATERS), 2015. Google Scholar
  29. Tei-Wei Kuo and Aloysius K. Mok. Load Adjustment in Adaptive Real-Time Systems. In IEEE Real-Time Systems Symposium, pages 160-171, 1991. Google Scholar
  30. John P. Lehoczky. Fixed Priority Scheduling of Periodic Task Sets with Arbitrary Deadlines. In RTSS, pages 201-209, 1990. URL: http://dx.doi.org/10.1109/REAL.1990.128748.
  31. Joseph Y.-T. Leung and Hairong Zhao. Minimizing Sum of Completion Times and Makespan in Master-Slave Systems. IEEE Trans. Computers, 55(8):985-999, 2006. Google Scholar
  32. C. L. Liu and James W. Layland. Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment. Journal of the ACM, 20(1):46-61, 1973. Google Scholar
  33. Jane W. S. Liu. Real-Time Systems. Prentice Hall PTR, 1st edition, 2000. Google Scholar
  34. Li Ming. Scheduling of the Inter-Dependent Messages in Real-Time Communication. In Proc. of the First International Workshop on Real-Time Computing Systems and Applications, 1994. Google Scholar
  35. Aloysius Ka-Lau Mok. Fundamental design problems of distributed systems for the hard-real-time environment. Technical report, Massachusetts Institute of Technology, Cambridge, MA, USA, 1983. Google Scholar
  36. Bo Peng and Nathan Fisher. Parameter Adaptation for Generalized Multiframe Tasks and Applications to Self-Suspending Tasks. In International Conference on Real-Time Computing Systems and Applications (RTCSA), pages 49-58, 2016. Google Scholar
  37. Ragunathan Rajkumar. Dealing with Suspending Periodic Tasks. Technical report, IBM T. J. Watson Research Center, 1991. Google Scholar
  38. Ragunathan Rajkumar, Lui Sha, and John P. Lehoczky. Real-Time Synchronization Protocols for Multiprocessors. In Proceedings of the 9th IEEE Real-Time Systems Symposium (RTSS '88), pages 259-269, 1988. Google Scholar
  39. Frédéric Ridouard, Pascal Richard, and Francis Cottet. Negative Results for Scheduling Independent Hard Real-Time Tasks with Self-Suspensions. In RTSS, pages 47-56, 2004. URL: http://dx.doi.org/10.1109/REAL.2004.35.
  40. Sartaj Sahni. Scheduling Master-Slave Multiprocessor Systems. In Parallel Processing, First International Euro-Par Conference, pages 611-622, 1995. Google Scholar
  41. Sartaj Sahni. Scheduling Master-Slave Multiprocessor Systems. IEEE Trans. Computers, 45(10):1195-1199, 1996. Google Scholar
  42. 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
  43. Sartaj Sahni and George L. Vairaktarakis. The Master-Slave Scheduling Model. In Handbook of Scheduling. Chapman and Hall/CRC, 2004. Google Scholar
  44. Lea Schönberger, Wen-Hung Huang, Georg von der Brüggen, Kuan-Hsun Chen, and Jian-Jia Chen. Schedulability Analysis and Priority Assignment for Segmented Self-Suspending Tasks. In 24th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2018, Hakodate, Japan, August 28-31, 2018, pages 157-167, 2018. Google Scholar
  45. Lui Sha. Real-Time Virtual Machines for Avionics Software Porting and Development. In Real-Time and Embedded Computing Systems and Applications, 9th International Conference, RTCSA, pages 123-135, 2003. Google Scholar
  46. George L. Vairaktarakis. Analysis of scheduling algorithms for master-slave systems. IIE Transactions, 29(11):939-949, November 1997. Google Scholar
  47. Georg von der Brüggen, Jian-Jia Chen, Wen-Hung Huang, and Maolin Yang. Release enforcement in resource-oriented partitioned scheduling for multiprocessor systems. In Proceedings of the 25th International Conference on Real-Time Networks and Systems, RTNS, pages 287-296, 2017. Google Scholar
  48. Georg von der Brüggen, Wen-Hung Huang, and Jian-Jia Chen. Hybrid Self-Suspension Models in Real-Time Embedded Systems. In International Conference on Real-Time Computing Systems and Applications (RTCSA), 2017. Google Scholar
  49. Georg von der Brüggen, Wen-Hung Huang, Jian-Jia Chen, and Cong Liu. Uniprocessor Scheduling Strategies for Self-Suspending Task Systems. In International Conference on Real-Time Networks and Systems (RTNS), 2016. Google Scholar
  50. Georg von der Brüggen, Niklas Ueter, Jian-Jia Chen, and Matthias Freier. Parametric utilization bounds for implicit-deadline periodic tasks in automotive systems. In Proceedings of the 25th International Conference on Real-Time Networks and Systems, RTNS, 2017. Google Scholar
  51. Wenci Yu, Han Hoogeveen, and Jan Karel Lenstra. Minimizing Makespan in a Two-Machine Flow Shop with Delays and Unit-Time Operations is NP-Hard. J. Scheduling, 7(5):333-348, 2004. 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
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact