Document Open Access Logo

Response-Time Analysis for Self-Suspending Tasks Under EDF Scheduling

Authors Federico Aromolo, Alessandro Biondi, Geoffrey Nelissen

PDF

File

Thumbnail PDF
PDF
LIPIcs.ECRTS.2022.13.pdf
  • Filesize: 0.73 MB
  • 18 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Computer systems organization → Real-time systems
  • Software and its engineering → Real-time schedulability
Keywords
  • Real-Time Systems
  • Schedulability Analysis
  • Self-Suspending Tasks
  • EDF Scheduling

Metrics

Abstract

The self-suspending task model proved to be particularly effective in capturing the timing behavior of real-time systems characterized by complex execution patterns, such as computation offloading to hardware accelerators, inter-core synchronization by means of multiprocessor locking protocols, and highly parallel computation. Most of the existing results for the timing analysis of self-suspending tasks do not support the widely adopted Earliest Deadline First (EDF) scheduling algorithm, being instead primarily focused on fixed-priority scheduling. This paper presents a response-time analysis for constrained-deadline self-suspending tasks scheduled under EDF on a uniprocessor system. The proposed analysis is based on a model transformation from self-suspending sporadic tasks to sporadic tasks with jitter, which can then be analyzed using a state-of-the-art analysis method for EDF scheduling. Experimental results are presented to compare the performance of the proposed technique in terms of schedulability ratio with that of the pessimistic suspension-oblivious approach and with a less general technique for task sets with implicit deadlines.

Cite As Get BibTex

Federico Aromolo, Alessandro Biondi, and Geoffrey Nelissen. Response-Time Analysis for Self-Suspending Tasks Under EDF Scheduling. In 34th Euromicro Conference on Real-Time Systems (ECRTS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 231, pp. 13:1-13:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.ECRTS.2022.13

Author Details

Federico Aromolo
  • Scuola Superiore Sant'Anna, Pisa, Italy
Alessandro Biondi
  • Scuola Superiore Sant'Anna, Pisa, Italy
Geoffrey Nelissen
  • Eindhoven University of Technology, Eindhoven, The Netherlands

Supplementary Materials

References

  1. Federico Aromolo, Alessandro Biondi, Geoffrey Nelissen, and Giorgio Buttazzo. Event-driven delay-induced tasks: Model, analysis, and applications. In Proceedings of the 27th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS 2021), pages 53-65. IEEE, 2021. Google Scholar
  2. Sanjoy K. Baruah, Louis E. Rosier, and Rodney R. Howell. Algorithms and complexity concerning the preemptive scheduling of periodic, real-time tasks on one processor. Real-Time Systems, 2(4):301-324, 1990. Google Scholar
  3. Enrico Bini and Giorgio C. Buttazzo. Measuring the performance of schedulability tests. Real-Time Systems, 30(1-2):129-154, 2005. Google Scholar
  4. Alessandro Biondi, Alessio Balsini, Marco Pagani, Enrico Rossi, Mauro Marinoni, and Giorgio Buttazzo. A framework for supporting real-time applications on dynamic reconfigurable FPGAs. In Proceedings of the 37th IEEE Real-Time Systems Symposium (RTSS 2016), pages 1-12. IEEE, 2016. Google Scholar
  5. Björn B. Brandenburg. Multiprocessor real-time locking protocols. In Yu-Chu Tian and David Charles Levy, editors, Handbook of Real-Time Computing, pages 1-99. Springer, 2020. Google Scholar
  6. Felipe Cerqueira, Geoffrey Nelissen, and Björn B. Brandenburg. On strong and weak sustainability, with an application to self-suspending real-time tasks. In Proceedings of the 30th Euromicro Conference on Real-Time Systems (ECRTS 2018), pages 26:1-26:21, 2018. Google Scholar
  7. Jian-Jia Chen, Geoffrey Nelissen, and Wen-Hung Huang. A unifying response time analysis framework for dynamic self-suspending tasks. In Proceedings of the 28th Euromicro Conference on Real-Time Systems (ECRTS 2016), pages 61-71. IEEE, 2016. Google Scholar
  8. 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, and Georg von der Brüggen. Many suspensions, many problems: A review of self-suspending tasks in real-time systems. Real-Time Systems, 55(1):144-207, 2019. Google Scholar
  9. UmaMaheswari C. Devi. An improved schedulability test for uniprocessor periodic task systems. In Proceedings of the 15th Euromicro Conference on Real-Time Systems (ECRTS 2003), pages 23-30. IEEE, 2003. Google Scholar
  10. Zheng Dong and Cong Liu. Closing the loop for the selective conversion approach: A utilization-based test for hard real-time suspending task systems. In Proceedings of the 37th IEEE Real-Time Systems Symposium (RTSS 2016), pages 339-350. IEEE, 2016. Google Scholar
  11. 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-based partitioning approaches. In Proceedings of the 24th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS 2018), pages 164-176. IEEE, 2018. Google Scholar
  12. Glenn A. Elliott, Bryan C. Ward, and James H. Anderson. GPUSync: A framework for real-time GPU management. In Proceedings of the 34th IEEE Real-Time Systems Symposium (RTSS 2013), pages 33-44. IEEE, 2013. Google Scholar
  13. Paul Emberson, Roger Stafford, and Robert I. Davis. Techniques for the synthesis of multiprocessor tasksets. In Proceedings of the 1st International Workshop on Analysis Tools and Methodologies for Embedded and Real-time Systems (WATERS 2010), pages 6-11, 2010. Google Scholar
  14. José Fonseca, Geoffrey Nelissen, Vincent Nélis, and Luís Miguel Pinho. Response time analysis of sporadic DAG tasks under partitioned scheduling. In Proceedings of the 11th IEEE Symposium on Industrial Embedded Systems (SIES 2016), pages 1-10. IEEE, 2016. Google Scholar
  15. Laurent George, Nicolas Rivierre, and Marco Spuri. Preemptive and non-preemptive real-time uniprocessor scheduling. Research Report RR-2966, INRIA, France, 1996. Google Scholar
  16. Mario Günzel, Niklas Ueter, and Jian-Jia Chen. Suspension-aware fixed-priority schedulability test with arbitrary deadlines and arrival curves. In Proceedings of the 42nd IEEE Real-Time Systems Symposium (RTSS 2021), pages 418-430. IEEE, 2021. Google Scholar
  17. Mario Günzel, Georg von der Brüggen, and Jian-Jia Chen. Suspension-aware earliest-deadline-first scheduling analysis. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 39(11):4205-4216, 2020. Google Scholar
  18. Cong Liu and James H. Anderson. Suspension-aware analysis for hard real-time multiprocessor scheduling. In Proceedings of the 25th Euromicro Conference on Real-Time Systems (ECRTS 2013), pages 271-281. IEEE, 2013. Google Scholar
  19. Geoffrey Nelissen and Alessandro Biondi. The SRP resource sharing protocol for self-suspending tasks. In Proceedings of the 39th IEEE Real-Time Systems Symposium (RTSS 2018), pages 361-372. IEEE, 2018. Google Scholar
  20. Geoffrey Nelissen, José Fonseca, Gurulingesh Raravi, and Vincent Nélis. Timing analysis of fixed priority self-suspending sporadic tasks. In Proceedings of the 27th Euromicro Conference on Real-Time Systems (ECRTS 2015), pages 80-89. IEEE, 2015. Google Scholar
  21. Marco Spuri. Analysis of deadline scheduled real-time systems. Research Report RR-2772, INRIA, France, 1996. Google Scholar
  22. Georg von der Brüggen, Wen-Hung Huang, and Jian-Jia Chen. Hybrid self-suspension models in real-time embedded systems. In Proceedings of the 23rd IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA 2017), pages 1-9. IEEE, 2017. Google Scholar
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact