Document Open Access Logo

Demystifying the Real-Time Linux Scheduling Latency

Authors Daniel Bristot de Oliveira , Daniel Casini , Rômulo Silva de Oliveira , Tommaso Cucinotta

PDF
Thumbnail PDF

File

LIPIcs.ECRTS.2020.9.pdf
  • Filesize: 1.33 MB
  • 23 pages

Document Identifiers

Author Details

Daniel Bristot de Oliveira
  • Red Hat, Italy
Daniel Casini
  • Scuola Superiore Sant'Anna, Italy
Rômulo Silva de Oliveira
  • Universidade Federal de Santa Catarina, Brazil
Tommaso Cucinotta
  • Scuola Superiore Sant'Anna, Italy

Funding

This work has been partially supported by CAPES, The Brazilian Agency for Higher Education, project PrInt CAPES-UFSC "Automation 4.0."

Acknowledgements

The authors would like to thank Thomas Gleixner, Peter Zijlstra, Steven Rostedt, Arnaldo Carvalho De Melo and Clark Williams for the fruitful discussions about the model, analysis, and tool.

Cite AsGet BibTex

Daniel Bristot de Oliveira, Daniel Casini, Rômulo Silva de Oliveira, and Tommaso Cucinotta. Demystifying the Real-Time Linux Scheduling Latency. In 32nd Euromicro Conference on Real-Time Systems (ECRTS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 165, pp. 9:1-9:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ECRTS.2020.9

Abstract

Linux has become a viable operating system for many real-time workloads. However, the black-box approach adopted by cyclictest, the tool used to evaluate the main real-time metric of the kernel, the scheduling latency, along with the absence of a theoretically-sound description of the in-kernel behavior, sheds some doubts about Linux meriting the real-time adjective. Aiming at clarifying the PREEMPT_RT Linux scheduling latency, this paper leverages the Thread Synchronization Model of Linux to derive a set of properties and rules defining the Linux kernel behavior from a scheduling perspective. These rules are then leveraged to derive a sound bound to the scheduling latency, considering all the sources of delays occurring in all possible sequences of synchronization events in the kernel. This paper also presents a tracing method, efficient in time and memory overheads, to observe the kernel events needed to define the variables used in the analysis. This results in an easy-to-use tool for deriving reliable scheduling latency bounds that can be used in practice. Finally, an experimental analysis compares the cyclictest and the proposed tool, showing that the proposed method can find sound bounds faster with acceptable overheads.

Subject Classification

ACM Subject Classification
  • Computer systems organization → Real-time operating systems
Keywords
  • Real-time operating systems
  • Linux kernel
  • PREEMPT_RT
  • Scheduling latency

Metrics

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

Supplementary Materials

References

  1. L. Abeni, A. Goel, C. Krasic, J. Snow, and J. Walpole. A measurement-based analysis of the real-time performance of linux. In Proceedings. Eighth IEEE Real-Time and Embedded Technology and Applications Symposium, September 2002. Google Scholar
  2. Jade Alglave, Luc Maranget, Paul E. McKenney, Andrea Parri, and Alan Stern. Frightening Small Children and Disconcerting Grown-ups: Concurrency in the Linux Kernel. In Proceedings of the Twenty-Third International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS '18, pages 405-418, New York, NY, USA, 2018. ACM. URL: https://doi.org/10.1145/3173162.3177156.
  3. Neil Audsley, Alan Burns, Mike Richardson, Ken Tindell, and Andy J Wellings. Applying new scheduling theory to static priority pre-emptive scheduling. Software engineering journal, 8(5):284-292, 1993. Google Scholar
  4. Bjorn Brandenbug and James Anderson. Joint Opportunities for Real-Time Linux and Real-Time System Research. In Proceedings of the 11th Real-Time Linux Workshop (RTLWS 2009), pages 19-30, September 2009. Google Scholar
  5. B. B. Brandenburg and M. Gül. Global scheduling not required: Simple, near-optimal multiprocessor real-time scheduling with semi-partitioned reservations. In 2016 IEEE Real-Time Systems Symposium (RTSS), pages 99-110, November 2016. URL: https://doi.org/10.1109/RTSS.2016.019.
  6. John M. Calandrino, Hennadiy Leontyev, Aaron Block, UmaMaheswari C. Devi, and James H. Anderson. Litmus^RT: A testbed for empirically comparing real-time multiprocessor schedulers. In Proceedings of the 27th IEEE International Real-Time Systems Symposium, RTSS '06, pages 111-126, Washington, DC, USA, 2006. IEEE Computer Society. URL: https://doi.org/10.1109/RTSS.2006.27.
  7. Christos G. Cassandras and Stephane Lafortune. Introduction to Discrete Event Systems. Springer Publishing Company, Incorporated, 2nd edition, 2010. Google Scholar
  8. F. Cerqueira and B. Brandenburg. A Comparison of Scheduling Latency in Linux, PREEMPT-RT, and LITMUS-RT. In Proceedings of the 9th Annual Workshop on Operating Systems Platforms for Embedded Real-Time applications, pages 19-29, 2013. Google Scholar
  9. Felipe Cerqueira and Björn Brandenburg. A comparison of scheduling latency in linux, preempt-rt, and litmus rt. In 9th Annual Workshop on Operating Systems Platforms for Embedded Real-Time Applications, pages 19-29. SYSGO AG, 2013. Google Scholar
  10. H. Chishiro. RT-Seed: Real-Time Middleware for Semi-Fixed-Priority Scheduling. In 2016 IEEE 19th International Symposium on Real-Time Distributed Computing (ISORC), pages 124-133, May 2016. URL: https://doi.org/10.1109/ISORC.2016.26.
  11. J. Corbet. Linux at NASDAQ OMX, October 2010. URL: https://lwn.net/Articles/411064/.
  12. T. Cucinotta, A. Mancina, G. F. Anastasi, G. Lipari, L. Mangeruca, R. Checcozzo, and F. Rusina. A real-time service-oriented architecture for industrial automation. IEEE Transactions on Industrial Informatics, 5(3):267-277, August 2009. URL: https://doi.org/10.1109/TII.2009.2027013.
  13. D. B. de Oliveira, R. S. de Oliveira, T. Cucinotta, and L. Abeni. Automata-based modeling of interrupts in the Linux PREEMPT RT kernel. In 2017 22nd IEEE International Conference on Emerging Technologies and Factory Automation (ETFA), pages 1-8, September 2017. URL: https://doi.org/10.1109/ETFA.2017.8247611.
  14. Daniel B. de Oliveira, Rômulo S. de Oliveira, and Tommaso Cucinotta. A thread synchronization model for the preempt_rt linux kernel. Journal of Systems Architecture, page 101729, 2020. URL: https://doi.org/10.1016/j.sysarc.2020.101729.
  15. Daniel Bristot de Oliveira. Mind the gap between real-time Linux and real-time theory, Part I, 2018. URL: https://wiki.linuxfoundation.org/realtime/events/rt-summit2018/schedule#abstracts.
  16. Daniel Bristot de Oliveira. Mind the gap between real-time Linux and real-time theory, Part II, 2018. URL: https://www.linuxplumbersconf.org/event/2/contributions/75/.
  17. Daniel Bristot de Oliveira. Mathmatizing the Latency - Presentation at the Real-time Linux micro-conference, at the Linux Plumbers Conference, September 2019. URL: https://linuxplumbersconf.org/event/4/contributions/413/.
  18. Daniel Bristot de Oliveira, Tommaso Cucinotta, and Rômulo Silva de Oliveira. Efficient formal verification for the linux kernel. In International Conference on Software Engineering and Formal Methods, pages 315-332. Springer, 2019. Google Scholar
  19. Daniel Bristot de Oliveira, Tommaso Cucinotta, and Rômulo Silva de Oliveira. Untangling the Intricacies of Thread Synchronization in the PREEMPT_RT Linux Kernel. In Proceedings of the IEEE 22nd International Symposium on Real-Time Distributed Computing (ISORC), Valencia, Spain, May 2019. Google Scholar
  20. Daniel Bristot de Oliveira and Rômulo Silva de Oliveira. Timing analysis of the PREEMPT_RT Linux kernel. Softw., Pract. Exper., 46(6):789-819, 2016. URL: https://doi.org/10.1002/spe.2333.
  21. A. Dubey, G. Karsai, and S. Abdelwahed. Compensating for timing jitter in computing systems with general-purpose operating systems. In 2009 IEEE International Symposium on Object/Component/Service-Oriented Real-Time Distributed Computing, pages 55-62, March 2009. URL: https://doi.org/10.1109/ISORC.2009.28.
  22. Hasan Fayyad-Kazan, Luc Perneel, and Martin Timmerman. Linux preempt-rt vs commercial rtoss: How big is the performance gap? GSTF Journal on Computing, 3(1), 2013. Google Scholar
  23. Thomas Gleixner. Realtime Linux: academia v. reality. Linux Weekly News, July 2010. URL: https://lwn.net/Articles/397422/.
  24. B. Herzog, L. Gerhorst, B. Heinloth, S. Reif, T. Hönig, and W. Schröder-Preikschat. Intspect: Interrupt latencies in the linux kernel. In 2018 VIII Brazilian Symposium on Computing Systems Engineering (SBESC), pages 83-90, November 2018. Google Scholar
  25. M. Joseph and P. Pandya. Finding Response Times in a Real-Time System. The Computer Journal, 29(5):390-395, January 1986. Google Scholar
  26. J. Lehoczky, L. Sha, and Y. Ding. The rate monotonic scheduling algorithm: exact characterization and average case behavior. In [1989] Proceedings. Real-Time Systems Symposium, pages 166-171, December 1989. Google Scholar
  27. Juri Lelli, Claudio Scordino, Luca Abeni, and Dario Faggioli. Deadline scheduling in the Linux kernel. Software: Practice and Experience, 46(6):821-839, 2016. URL: https://doi.org/10.1002/spe.2335.
  28. Linux Kernel Documentation. Linux tracing technologies. https://www.kernel.org/doc/html/latest/trace/index.html, February 2020. URL: https://www.kernel.org/doc/html/latest/trace/index.html.
  29. G. Matni and M. Dagenais. Automata-based approach for kernel trace analysis. In 2009 Canadian Conference on Electrical and Computer Engineering, pages 970-973, May 2009. URL: https://doi.org/10.1109/CCECE.2009.5090273.
  30. L. Palopoli, T. Cucinotta, L. Marzario, and G. Lipari. AQuoSA - Adaptive Quality of Service Architecture. Softw. Pract. Exper., 39(1):1-31, January 2009. URL: https://doi.org/10.1002/spe.v39:1.
  31. Phoronix Test Suite. Open-source, automated benchmarking. https://www.phoronix-test-suite.com, February 2020. URL: https://www.phoronix-test-suite.com.
  32. Josh Poimboeuf. Introducing kpatch: Dynamic kernel patching. https://www.redhat.com/en/blog/introducing-kpatch-dynamic-kernel-patching, February 2014. URL: https://www.redhat.com/en/blog/introducing-kpatch-dynamic-kernel-patching.
  33. P. J. Ramadge and W. M. Wonham. Supervisory control of a class of discrete event processes. SIAM J. Control Optim., 25(1):206-230, January 1987. URL: https://doi.org/10.1137/0325013.
  34. Red Hat. Inc,. Advanced tuning procedures to optimize latency in RHEL for Real Time. https://access.redhat.com/documentation/en-us/red_hat_enterprise_linux_for_real_time/8/html/tuning_guide/index, February 2020. URL: https://access.redhat.com/documentation/en-us/red_hat_enterprise_linux_for_real_time/8/html/tuning_guide/index.
  35. Red Hat. Inc,. Red Hat Enterprise Linux Hardware Certification. https://access.redhat.com/documentation/en-us/red_hat_enterprise_linux_hardware_certification/1.0/html/test_suite_user_guide/sect-layered-product-certs#cert-for-rhel-for-real-time, February 2020. URL: https://access.redhat.com/documentation/en-us/red_hat_enterprise_linux_hardware_certification/1.0/html/test_suite_user_guide/sect-layered-product-certs#cert-for-rhel-for-real-time.
  36. F. Reghenzani, G. Massari, and W. Fornaciari. Mixed time-criticality process interferences characterization on a multicore linux system. In 2017 Euromicro Conference on Digital System Design (DSD), August 2017. Google Scholar
  37. Paul Regnier, George Lima, and Luciano Barreto. Evaluation of interrupt handling timeliness in real-time linux operating systems. ACM SIGOPS Operating Systems Review, 42(6):52–63, 2008. Google Scholar
  38. Steven Rostedt. Finding origins of latencies using ftrace, 2009. Google Scholar
  39. Carlos San Vicente Gutiérrez, Lander Usategui San Juan, Irati Zamalloa Ugarte, and Víctor Mayoral Vilches. Real-time linux communications: an evaluation of the linux communication stack for real-time robotic applications, August 2018. URL: https://arxiv.org/pdf/1808.10821.pdf.
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 Imprint Privacy Contact