Document Open Access Logo

Improving the Accuracy of Cache-Aware Response Time Analysis Using Preemption Partitioning

Authors Filip Marković , Jan Carlson, Sebastian Altmeyer, Radu Dobrin

PDF

File

Thumbnail PDF
PDF
LIPIcs.ECRTS.2020.5.pdf
  • Filesize: 0.72 MB
  • 23 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Computer systems organization → Real-time system specification
  • Software and its engineering → Real-time schedulability
Keywords
  • Real-time systems
  • Fixed-Priority Preemptive Scheduling
  • Preemption delay

Metrics

Abstract

Schedulability analyses for preemptive real-time systems need to take into account cache-related preemption delays (CRPD) caused by preemptions between the tasks. The estimation of the CRPD values must be sound, i.e. it must not be lower than the worst-case CRPD that may occur at runtime, but also should minimise the pessimism of estimation. The existing methods over-approximate the computed CRPD upper bounds by accounting for multiple preemption combinations which cannot occur simultaneously during runtime. This over-approximation may further lead to the over-approximation of the worst-case response times of the tasks, and therefore a false-negative estimation of the system’s schedulability. In this paper, we propose a more precise cache-aware response time analysis for sporadic real-time systems under fully-preemptive fixed priority scheduling. The evaluation shows a significant improvement over the existing state of the art approaches.

Cite As Get BibTex

Filip Marković, Jan Carlson, Sebastian Altmeyer, and Radu Dobrin. Improving the Accuracy of Cache-Aware Response Time Analysis Using Preemption Partitioning. In 32nd Euromicro Conference on Real-Time Systems (ECRTS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 165, pp. 5:1-5:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.ECRTS.2020.5

Author Details

Filip Marković
  • Mälardalen University, Västerås, Sweden
Jan Carlson
  • Mälardalen University, Västerås, Sweden
Sebastian Altmeyer
  • University of Augsburg, Germany
Radu Dobrin
  • Mälardalen University, Västerås, Sweden

Acknowledgements

We want to thank our colleagues Sebastian Hahn, Jan Reineke, and Darshit Shah, who provided us with the evaluation data derived from the code-level analysis of benchmark programs. Also, we are very grateful to Davor Čirkinagić who borrowed his powerful computing system for performing schedulability evaluation.

References

  1. Martin Aigner. A characterization of the bell numbers. Discrete mathematics, 205(1-3):207-210, 1999. Google Scholar
  2. Sebastian Altmeyer and Claire Burguiere. A new notion of useful cache block to improve the bounds of cache-related preemption delay. In Real-Time Systems, 2009. ECRTS'09. 21st Euromicro Conference on, pages 109-118. IEEE, 2009. Google Scholar
  3. Sebastian Altmeyer, Robert I Davis, and Claire Maiza. Cache related pre-emption delay aware response time analysis for fixed priority pre-emptive systems. In 2011 IEEE 32nd Real-Time Systems Symposium, pages 261-271. IEEE, 2011. Google Scholar
  4. Sebastian Altmeyer, Robert I Davis, and Claire Maiza. Improved cache related pre-emption delay aware response time analysis for fixed priority pre-emptive systems. Real-Time Systems, 48(5):499-526, 2012. Google Scholar
  5. Sebastian Altmeyer, Roeland Douma, Will Lunniss, and Robert I Davis. On the effectiveness of cache partitioning in hard real-time systems. Real-Time Systems, 52(5):598-643, 2016. Google Scholar
  6. Sebastian Altmeyer, Claire Maiza, and Jan Reineke. Resilience analysis: tightening the CRPD bound for set-associative caches. In ACM Sigplan Notices, volume 45, pages 153-162. ACM, 2010. Google Scholar
  7. Andrea Bastoni, Björn Brandenburg, and James Anderson. Cache-related preemption and migration delays: Empirical approximation and impact on schedulability. Proceedings of OSPERT, pages 33-44, 2010. Google Scholar
  8. Enrico Bini and Giorgio C Buttazzo. Measuring the performance of schedulability tests. Real-Time Systems, 30(1-2):129-154, 2005. Google Scholar
  9. Tobias Blaß, Sebastian Hahn, and Jan Reineke. Write-back caches in wcet analysis. In 29th Euromicro Conference on Real-Time Systems (ECRTS 2017). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017. Google Scholar
  10. Claire Burguière, Jan Reineke, and Sebastian Altmeyer. Cache-related preemption delay computation for set-associative caches-pitfalls and solutions. In 9th International Workshop on Worst-Case Execution Time Analysis (WCET'09). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2009. Google Scholar
  11. José V Busquets-Mataix, Juan José Serrano, Rafael Ors, Pedro Gil, and Andy Wellings. Adding instruction cache effect to schedulability analysis of preemptive real-time systems. In Real-Time Technology and Applications Symposium, 1996. Proceedings., 1996 IEEE, pages 204-212. IEEE, 1996. Google Scholar
  12. Robert I Davis, Sebastian Altmeyer, and Jan Reineke. Response-time analysis for fixed-priority systems with a write-back cache. Real-Time Systems, 54(4):912-963, 2018. Google Scholar
  13. Borivoje Djokić, Masahiro Miyakawa, Satoshi Sekiguchi, Ichiro Semba, and Ivan Stojmenović. Parallel algorithms for generating subsets and set partitions. In International Symposium on Algorithms, pages 76-85. Springer, 1990. Google Scholar
  14. MC Er. A fast algorithm for generating set partitions. The Computer Journal, 31(3):283-284, 1988. Google Scholar
  15. Heiko Falk, Sebastian Altmeyer, Peter Hellinckx, Björn Lisper, Wolfgang Puffitsch, Christine Rochange, Martin Schoeberl, Rasmus Bo Sørensen, Peter Wägemann, and Simon Wegener. Taclebench: A benchmark collection to support worst-case execution time research. In 16th International Workshop on Worst-Case Execution Time Analysis (WCET 2016). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2016. Google Scholar
  16. Jan Gustafsson, Adam Betts, Andreas Ermedahl, and Björn Lisper. The mälardalen wcet benchmarks: Past, present and future. In 10th International Workshop on Worst-Case Execution Time Analysis (WCET 2010). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2010 . Google Scholar
  17. Sebastian Hahn, Michael Jacobs, and Jan Reineke. Enabling compositionality for multicore timing analysis. In Proceedings of the 24th international conference on real-time networks and systems, pages 299-308. ACM, 2016. Google Scholar
  18. Paul R Halmos. Naive set theory. Courier Dover Publications, 2017. Google Scholar
  19. Henry Heberle, Gabriela Vaz Meirelles, Felipe R da Silva, Guilherme P Telles, and Rosane Minghim. Interactivenn: a web-based tool for the analysis of sets through venn diagrams. BMC bioinformatics, 16(1):169, 2015. Google Scholar
  20. Chang-Gun Lee, Joosun Han, Yang-Min Seo, Sang Luyl Min, Rhan Ha, Seongsoo Hong, Chang Yun Park, Minsuk Lee, and Chong Sam Kim. Analysis of cache-related preemption delay in fixed-priority preemptive scheduling. IEEE Transactions on Computers, 47(6):700-713, 1998. Google Scholar
  21. Rodolfo Pellizzoni, Bach D Bui, Marco Caccamo, and Lui Sha. Coscheduling of CPU and I/O transactions in COTS-based embedded systems. In Real-Time Systems Symposium, 2008, pages 221-231. IEEE, 2008. Google Scholar
  22. Harini Ramaprasad and Frank Mueller. Bounding worst-case response time for tasks with non-preemptive regions. In 2008 IEEE Real-Time and Embedded Technology and Applications Symposium, pages 58-67. IEEE, 2008. Google Scholar
  23. Harini Ramaprasad and Frank Mueller. Tightening the bounds on feasible preemptions. ACM Transactions on Embedded Computing Systems (TECS), 10(2):27, 2010. Google Scholar
  24. Syed Aftab Rashid, Geoffrey Nelissen, Sebastian Altmeyer, Robert I Davis, and Eduardo Tovar. Integrated analysis of cache related preemption delays and cache persistence reload overheads. In 2017 IEEE Real-Time Systems Symposium (RTSS), pages 188-198. IEEE, 2017. Google Scholar
  25. Syed Aftab Rashid, Geoffrey Nelissen, Damien Hardy, Benny Akesson, Isabelle Puaut, and Eduardo Tovar. Cache-persistence-aware response-time analysis for fixed-priority preemptive systems. In 2016 28th Euromicro Conference on Real-Time Systems (ECRTS), pages 262-272. IEEE, 2016. Google Scholar
  26. Altmeyer Sebastian, Douma Roeland, Lunniss Will, and I Davis Robert. Evaluation of cache partitioning for hard real-time systems. In proceedings Euromicro Conference on Real-Time Systems (ECRTS), pages 15-26, 2014. Google Scholar
  27. Darshit Shah, Sebastian Hahn, and Jan Reineke. Experimental evaluation of cache-related preemption delay aware timing analysis. In 18th International Workshop on Worst-Case Execution Time Analysis (WCET 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018. Google Scholar
  28. Jan Staschulat, Simon Schliecker, and Rolf Ernst. Scheduling analysis of real-time systems with precise modeling of cache related preemption delay. In Real-Time Systems, 2005.(ECRTS 2005). Proceedings. 17th Euromicro Conference on, pages 41-48. IEEE, 2005. Google Scholar
  29. Gregory Stock, Sebastian Hahn, and Jan Reineke. Cache persistence analysis: Finally exact. In Real-Time Systems Symposium (RTSS), December 2019. Google Scholar
  30. Yudong Tan and Vincent Mooney. Timing analysis for preemptive multitasking real-time systems with caches. ACM Transactions on Embedded Computing Systems (TECS), 6(1):7, 2007. Google Scholar
  31. Hiroyuki Tomiyama and Nikil D Dutt. Program path analysis to bound cache-related preemption delay in preemptive real-time systems. In Proceedings of the eighth international workshop on Hardware/software codesign, pages 67-71. ACM, 2000. 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