End-to-End Timing Analysis of Sporadic Cause-Effect Chains in Distributed Systems

Abstract

A cause-effect chain is used to define the logical order of data dependent tasks, which is independent from the execution order of the jobs of the (periodic/sporadic) tasks. Analyzing the worst-case End-to-End timing behavior, associated to a cause-effect chain, is an important problem in embedded control systems. For example, the detailed timing properties of modern automotive systems are specified in the AUTOSAR Timing Extensions.

In this paper, we present a formal End-to-End timing analysis for distributed systems. We consider the two most important End-to-End timing semantics, i.e., the button-to-action delay (termed as the maximum reaction time) and the worst-case data freshness (termed as the maximum data age). Our contribution is significant due to the consideration of the sporadic behavior of job activations, whilst the results in the literature have been mostly limited to periodic activations. The proof strategy shows the (previously unexplored) connection between the reaction time (data age, respectively) and immediate forward (backward, respectively) job chains. Our analytical results dominate the state of the art for sporadic task activations in distributed systems and the evaluations show a clear improvement for synthesized task systems as well as for a real world automotive benchmark setting.

References

1. AUTOSAR. 2017. Specification of Timing Extensions, Release 4.3.1. (Aug. 2017).
2. M. Becker, D. Dasari, S. Mubeen, M. Behnam, and T. Nolte. 2016. Mechaniser-a timing analysis and synthesis tool for multi-rate effect chains with job-level dependencies. In 7th International Workshop on Analysis Tools and Methodologies for Embedded and Real-time Systems (WATERS).
3. M. Becker, D. Dasari, S. Mubeen, M. Behnam, and T. Nolte. 2016. Synthesizing job-level dependencies for automotive multi-rate effect chains. In 22nd IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2016, Daegu, South Korea, August 17--19, 2016. 159--169. DOI:https://doi.org/10.1109/RTCSA.2016.41
4. M. Becker, S. Mubeen, D. Dasari, M. Behnam, and T. Nolte. 2017. A generic framework facilitating early analysis of data propagation delays in multi-rate systems (Invited paper). In IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA. 1--11. DOI:https://doi.org/10.1109/RTCSA.2017.8046323
5. A. Benveniste, P. Caspi, P. L. Guernic, H. Marchand, J.-P. Talpin, and S. Tripaki. 2002. A protocol for loosely time-triggered architectures. In Embedded Software, Second International Conference, EMSOFT. 252--265. DOI:https://doi.org/10.1007/3-540-45828-X_19
6. E. Bini and G. C. Buttazzo. 2005. Measuring the performance of schedulability tests. Real-Time Systems 30, 1--2 (2005), 129--154. DOI:https://doi.org/10.1007/s11241-005-0507-9
7. Bosch. 1991. Controller Area Network Specification 2.0.
8. A. Burns. 1994. Preemptive priority-based scheduling: An appropriate engineering approach. In Advances in Real-Time Systems, chapter 10. Prentice Hall, 225--248.
9. A. Davare, Q. Zhu, M. D. Natale, C. Pinello, S. Kanajan, and A. L. Sangiovanni-Vincentelli. 2007. Period optimization for hard real-time distributed automotive systems. In Design Automation Conference, DAC. 278--283. DOI:https://doi.org/10.1145/1278480.1278553
10. P. Emberson, R. Stafford, and R. I. Davis. 2010. Techniques for the synthesis of multiprocessor tasksets. In International Workshop on Analysis Tools and Methodologies for Embedded and Real-time Systems (WATERS 2010). 6--11.
11. N. Feiertag, K. Richter, J. Nordlander, and J. Jonsson. 2009. 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.
12. J. Forget, F. Boniol, and C. Pagetti. 2017. Verifying end-to-end real-time constraints on multi-periodic models. In 22nd IEEE International Conference on Emerging Technologies and Factory Automation, ETFA. 1--8. DOI:https://doi.org/10.1109/ETFA.2017.8247612
13. A. Hamann, D. Dasari, S. Kramer, M. Pressler, and F. Wurst. 2018. 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 (2018), 2578--2589. DOI:https://doi.org/10.1109/TCAD.2018.2861016
14. A. Hamann, D. Dasari, S. Kramer, M. Pressler, and F. Wurst. 2017. Communication centric design in complex automotive embedded systems. In Euromicro Conference on Real-Time Systems, ECRTS. 10:1--10:20.
15. T. Klaus, F. Franzmann, M. Becker, and P. Ulbrich. 2018. 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. ACM, 93--103.
16. T. Kloda, A. Bertout, and Y. Sorel. 2018. Latency analysis for data chains of real-time periodic tasks. In 23rd IEEE International Conference on Emerging Technologies and Factory Automation, ETFA. 360--367. DOI:https://doi.org/10.1109/ETFA.2018.8502498
17. H. Kopetz. 2011. Real-Time Systems - Design Principles for Distributed Embedded Applications. Springer. DOI:https://doi.org/10.1007/978-1-4419-8237-7
18. S. Kramer, D. Ziegenbein, and A. Hamann. 2015. Real world automotive benchmark for free. In 6th International Workshop on Analysis Tools and Methodologies for Embedded and Real-time Systems (WATERS).
19. J. P. Lehoczky, L. Sha, and Y. Ding. 1989. The rate monotonic scheduling algorithm: Exact characterization and average case behavior. In IEEE Real-Time Systems Symposium’89. 166--171. DOI:https://doi.org/10.1109/REAL.1989.63567
20. C. L. Liu and J. W. Layland. 1973. Scheduling algorithms for multiprogramming in a hard-real-time environment. J. ACM 20, 1 (1973), 46--61. DOI:https://doi.org/10.1145/321738.321743
21. A. K. Mok. 1983. Fundamental Design Problems of Distributed Systems for the Hard-Real-Time Environment. Technical Report. Massachusetts Institute of Technology, Cambridge, MA, USA.
22. S. Mubeen, J. Mäki-Turja, and M. Sjödin. 2012. 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. IEEE, 165--168.
23. S. Mubeen, J. Mäki-Turja, and M. Sjödin. 2012. Translating end-to-end timing requirements to timing analysis model in component-based distributed real-time systems. SIGBED Review 9, 4 (2012), 17--20. DOI:https://doi.org/10.1145/2452537.2452539
24. A. Rajeev, S. Mohalik, M. G. Dixit, D. B. Chokshi, and S. Ramesh. 2010. Schedulability and end-to-end latency in distributed ecu networks: Formal modeling and precise estimation. In Proceedings of the Tenth ACM International Conference on Embedded Software. ACM, 129--138.
25. J. Schlatow and R. Ernst.. 2016. Response-time analysis for task chains in communicating threads. In IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS). 245--254. DOI:https://doi.org/10.1109/RTAS.2016.7461359
26. Symtavision. [n.d.]. SymTA/S Toolbox. http://www.symtavision.com/symtas.html
27. K. Tindell and J. Clark. 1994. Holistic schedulability analysis for distributed hard real-time systems. Microprocessing and Microprogramming 40, 2--3 (1994), 117--134. DOI:https://doi.org/10.1016/0165-6074(94)90080-9
28. G. von der Bruggen, J.-J. Chen, and W.-H. Huang. 2015. Schedulability and optimization analysis for non-preemptive static priority scheduling based on task utilization and blocking factors. In Euromicro Conference on Real-Time Systems, ECRTS. 90--101. DOI:https://doi.org/10.1109/ECRTS.2015.16
29. G. von der Brüggen, N. Ueter, J. Chen, and M. Freier. 2017. 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. 108--117.

Index Terms

• Computer systems organization

  • Real-time systems