Document Open Access Logo

On the Equivalence of Maximum Reaction Time and Maximum Data Age for Cause-Effect Chains

Authors Mario Günzel , Harun Teper , Kuan-Hsun Chen , Georg von der Brüggen , Jian-Jia Chen

PDF
Thumbnail PDF

File

LIPIcs.ECRTS.2023.10.pdf
  • Filesize: 0.96 MB
  • 22 pages

Document Identifiers

Author Details

Mario Günzel
  • Department of Computer Science, TU Dortmund University, Germany
Harun Teper
  • Department of Computer Science, TU Dortmund University, Germany
Kuan-Hsun Chen
  • University of Twente, The Netherlands
Georg von der Brüggen
  • Department of Computer Science, TU Dortmund University, Germany
Jian-Jia Chen
  • Lamarr Institute for Machine Learning and Artificial Intelligence, Dortmund, Germany
  • Department of Computer Science, TU Dortmund University, Germany

Funding

This work has been supported by Deutsche Forschungsgemeinschaft (DFG), as part of Sus-Aware (Project No. 398602212). This result is part of a project (PropRT) that has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No. 865170). This work was partially funded by the German Federal Ministry of Education and Research (BMBF) in the course of the 6GEM research hub under grant number 16KISK038.

Cite As Get BibTex

Mario Günzel, Harun Teper, Kuan-Hsun Chen, Georg von der Brüggen, and Jian-Jia Chen. On the Equivalence of Maximum Reaction Time and Maximum Data Age for Cause-Effect Chains. In 35th Euromicro Conference on Real-Time Systems (ECRTS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 262, pp. 10:1-10:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.ECRTS.2023.10

Abstract

Real-time systems require a formal guarantee of timing-constraints, not only for individual tasks but also for data-propagation. The timing behavior of data-propagation paths in a given system is typically described by its maximum reaction time and its maximum data age. This paper shows that they are equivalent.
To reach this conclusion, partitioned job chains are introduced, which consist of one immediate forward and one immediate backward job chain. Such partitioned job chains are proven to describe maximum reaction time and maximum data age in a universal manner. This universal description does not only show the equivalence of maximum reaction time and maximum data age, but can also be exploited to speed up the computation of such significantly. In particular, the speed-up for synthesized task sets based on automotive benchmarks can be up to 1600. 
Since only very few non-restrictive assumptions are made, the equivalence of maximum data age and maximum reaction time holds for almost any scheduling mechanism and even for tasks which do not adhere to the typical periodic or sporadic task model. This observation is supported by a simulation of a ROS2 navigation system.

Subject Classification

ACM Subject Classification
  • Computer systems organization → Embedded and cyber-physical systems
  • Software and its engineering → Real-time systems software
Keywords
  • End-to-End
  • Timing Analysis
  • Maximum Data Age
  • Maximum Reaction Time
  • Cause-Effect Chain
  • Robot Operating Systems 2 (ROS2)

Metrics

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

References

  1. AUTOSAR. Specification of timing extensions (AUTOSAR CP R21-11). https://www.autosar.org/fileadmin/user_upload/standards/classic/21-11/AUTOSAR_TPS_TimingExtensions.pdf, 2021. Accessed: 2022-10-18.
  2. Matthias Becker, Dakshina Dasari, Saad Mubeen, Moris Behnam, and Thomas Nolte. Mechaniser-a timing analysis and synthesis tool for multi-rate effect chains with job-level dependencies. In Workshop on Analysis Tools and Methodologies for Embedded and Real-time Systems (WATERS), 2016. Google Scholar
  3. Matthias Becker, Dakshina Dasari, Saad Mubeen, Moris Behnam, and Thomas Nolte. Synthesizing job-level dependencies for automotive multi-rate effect chains. In International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA), pages 159-169, 2016. URL: https://doi.org/10.1109/RTCSA.2016.41.
  4. Matthias Becker, Dakshina Dasari, Saad Mubeen, Moris Behnam, and Thomas Nolte. End-to-end timing analysis of cause-effect chains in automotive embedded systems. J. Syst. Archit., 80(C):104-113, October 2017. URL: https://doi.org/10.1016/j.sysarc.2017.09.004.
  5. Matthias Becker, Saad Mubeen, Dakshina Dasari, Moris Behnam, and Thomas Nolte. A generic framework facilitating early analysis of data propagation delays in multi-rate systems. In International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA), pages 1-11, 2017. URL: https://doi.org/10.1109/RTCSA.2017.8046323.
  6. Albert Benveniste, Paul Caspi, Paul Le Guernic, Hervé Marchand, Jean-Pierre Talpin, and Stavros Tripakis. A protocol for loosely time-triggered architectures. In EMSOFT, pages 252-265, 2002. URL: https://doi.org/10.1007/3-540-45828-X_19.
  7. Hyunjong Choi, Mohsen Karimi, and Hyoseung Kim. Chain-based fixed-priority scheduling of loosely-dependent tasks. In International Conference on Computer Design (ICCD). IEEE, 2020. Google Scholar
  8. Abhijit Davare, Qi Zhu, Marco Di Natale, Claudio Pinello, Sri Kanajan, and Alberto L. Sangiovanni-Vincentelli. Period optimization for hard real-time distributed automotive systems. In Design Automation Conference, DAC, pages 278-283, 2007. URL: https://doi.org/10.1145/1278480.1278553.
  9. Marco Dürr, Georg von der Brüggen, Kuan-Hsun Chen, and Jian-Jia Chen. End-to-end timing analysis of sporadic cause-effect chains in distributed systems. ACM Trans. Embedded Comput. Syst. (Special Issue for CASES), 18(5s):58:1-58:24, 2019. URL: https://doi.org/10.1145/3358181.
  10. Nico Feiertag, Kai Richter, Johan Nordlander, and Jan Jonsson. A compositional framework for end-to-end path delay calculation of automotive systems under different path semantics. In Workshop on Compositional Theory and Technology for Real-Time Embedded Systems, 2009. Google Scholar
  11. Julien Forget, Frédéric Boniol, and Claire Pagetti. Verifying end-to-end real-time constraints on multi-periodic models. In ETFA, pages 1-8, 2017. URL: https://doi.org/10.1109/ETFA.2017.8247612.
  12. Alain Girault, Christophe Prevot, Sophie Quinton, Rafik Henia, and Nicolas Sordon. Improving and estimating the precision of bounds on the worst-case latency of task chains. IEEE Trans. on CAD of Integrated Circuits and Systems, (Special Issue for EMSOFT), 37(11):2578-2589, 2018. URL: https://doi.org/10.1109/TCAD.2018.2861016.
  13. Mario Günzel, Kuan-Hsun Chen, Niklas Ueter, Georg von der Brüggen, Marco Dürr, and Jian-Jia Chen. Timing analysis of asynchronized distributed cause-effect chains. In IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS), pages 40-52, 2021. URL: https://doi.org/10.1109/RTAS52030.2021.00012.
  14. Arne Hamann, Dakshina Dasari, Simon Kramer, Michael Pressler, and Falk Wurst. Communication centric design in complex automotive embedded systems. In Euromicro Conference on Real-Time Systems, ECRTS, pages 10:1-10:20, 2017. URL: https://doi.org/10.4230/LIPIcs.ECRTS.2017.10.
  15. Christoph M. Kirsch and Ana Sokolova. The logical execution time paradigm. In Advances in Real-Time Systems, pages 103-120. Springer, 2012. URL: https://doi.org/10.1007/978-3-642-24349-3_5.
  16. Tobias Klaus, Florian Franzmann, Matthias Becker, and Peter Ulbrich. Data propagation delay constraints in multi-rate systems: Deadlines vs. job-level dependencies. In Proceedings of the 26th International Conference on Real-Time Networks and Systems, pages 93-103. ACM, 2018. Google Scholar
  17. Tomasz Kloda, Antoine Bertout, and Yves Sorel. Latency analysis for data chains of real-time periodic tasks. In IEEE International Conference on Emerging Technologies and Factory Automation, ETFA, pages 360-367, 2018. URL: https://doi.org/10.1109/ETFA.2018.8502498.
  18. Alix Munier Kordon and Ning Tang. Evaluation of the Age Latency of a Real-Time Communicating System Using the LET Paradigm. In Marcus Völp, editor, 32nd Euromicro Conference on Real-Time Systems (ECRTS 2020), volume 165 of Leibniz International Proceedings in Informatics (LIPIcs), pages 20:1-20:20, Dagstuhl, Germany, 2020. Schloss Dagstuhl-Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.ECRTS.2020.20.
  19. Simon Kramer, Dirk Ziegenbein, and Arne Hamann. Real world automotive benchmarks for free. In International Workshop on Analysis Tools and Methodologies for Embedded and Real-time Systems (WATERS), 2015. Google Scholar
  20. Jorge Martinez, Ignacio Sañudo, and Marko Bertogna. End-to-end latency characterization of task communication models for automotive systems. Real-Time Syst., 56(3):315-347, July 2020. URL: https://doi.org/10.1007/s11241-020-09350-3.
  21. Saad Mubeen, Jukka Mäki-Turja, and Mikael Sjödin. Implementation of end-to-end latency analysis for component-based multi-rate real-time systems in rubus-ice. In Factory Communication Systems (WFCS), 2012 9th IEEE International Workshop on, pages 165-168. IEEE, 2012. Google Scholar
  22. Saad Mubeen, Jukka Mäki-Turja, and Mikael Sjödin. Translating end-to-end timing requirements to timing analysis model in component-based distributed real-time systems. SIGBED Review, 9(4):17-20, 2012. URL: https://doi.org/10.1145/2452537.2452539.
  23. Open Robotics. Ros 2 documentation: Foxy, May 2022. URL: https://docs.ros.org/en/foxy.
  24. AC Rajeev, Swarup Mohalik, Manoj G Dixit, Devesh B Chokshi, and S Ramesh. Schedulability and end-to-end latency in distributed ecu networks: formal modeling and precise estimation. In International Conference on Embedded Software, pages 129-138, 2010. Google Scholar
  25. Johannes Schlatow and Rolf Ernst. Response-time analysis for task chains in communicating threads. In IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS), pages 245-254, 2016. URL: https://doi.org/10.1109/RTAS.2016.7461359.
  26. Johannes Schlatow, Mischa Möstl, Sebastian Tobuschat, Tasuku Ishigooka, and Rolf Ernst. Data-age analysis and optimisation for cause-effect chains in automotive control systems. In IEEE International Symposium on Industrial Embedded Systems (SIES), pages 1-9, 2018. Google Scholar
  27. Harun Teper, Mario Günzel, Niklas Ueter, Georg von der Brüggen, and Jian-Jia Chen. End-to-end timing analysis in ros2. In 43rd IEEE Real-Time Systems Symposium (RTSS), 2022. Google Scholar
  28. Rémy Wyss, Frédéric Boniol, Claire Pagetti, and Julien Forget. End-to-end latency computation in a multi-periodic design. In Proceedings of the 28th Annual ACM Symposium on Applied Computing, SAC, pages 1682-1687, 2013. URL: https://doi.org/10.1145/2480362.2480678.
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