Document Open Access Logo

Tightening the Bounds on Cache-Related Preemption Delay in Fixed Preemption Point Scheduling

Authors Filip Markovic, Jan Carlson, Radu Dobrin

PDF
Thumbnail PDF

File

OASIcs.WCET.2017.4.pdf
  • Filesize: 0.5 MB
  • 11 pages

Document Identifiers

Author Details

Filip Markovic
Jan Carlson
Radu Dobrin

Cite As Get BibTex

Filip Markovic, Jan Carlson, and Radu Dobrin. Tightening the Bounds on Cache-Related Preemption Delay in Fixed Preemption Point Scheduling. In 17th International Workshop on Worst-Case Execution Time Analysis (WCET 2017). Open Access Series in Informatics (OASIcs), Volume 57, pp. 4:1-4:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/OASIcs.WCET.2017.4

Abstract

Limited Preemptive Fixed Preemption Point scheduling (LP-FPP) has the ability to decrease and control the preemption-related overheads in the real-time task systems, compared to other limited or fully preemptive scheduling approaches. However, existing methods for computing the preemption overheads in LP-FPP systems rely on over-approximation of the evicting cache blocks (ECB) calculations, potentially leading to pessimistic schedulability analysis.
 
In this paper, we propose a novel method for preemption cost calculation that exploits the benefits of the LP-FPP task model both at the scheduling and cache analysis level. The method identifies certain infeasible preemption combinations, based on analysis on the scheduling level, and combines it with cache analysis information into a constraint problem from which less pessimistic upper bounds on cache-related preemption delays (CRPD) can be derived.
 
The evaluation results indicate that our proposed method has the potential to significantly reduce the upper bound on CRPD, by up to 50% in our experiments, compared to the existing over-approximating calculations of the eviction scenarios.

Subject Classification

Keywords
  • Real-time systems
  • CRPD Analysis
  • WCET analysis
  • Limited Preemptive Scheduling
  • Fixed Preemption Point Approach

Metrics

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

References

  1. 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
  2. Sebastian Altmeyer, Claire Maiza, and Jan Reineke. Resilience analysis: tightening the CRPD bound for set-associative caches. ACM Sigplan Notices, 45(4):153-162, 2010. Google Scholar
  3. Sebastian Altmeyer, Douma Roeland, Will Lunniss, and Robert I. Davis. Evaluation of cache partitioning for hard real-time systems. In Proceedings Euromicro Conference on Real-Time Systems (ECRTS), pages 15-26, 2014. URL: http://dx.doi.org/10.1109/ECRTS.2014.11.
  4. Marko Bertogna, Orges Xhani, Mauro Marinoni, Francesco Esposito, and Giorgio Buttazzo. Optimal selection of preemption points to minimize preemption overhead. In Real-Time Systems (ECRTS), 2011 23rd Euromicro Conference on, pages 217-227. IEEE, 2011. Google Scholar
  5. Enrico Bini and Giorgio C. Buttazzo. Measuring the performance of schedulability tests. Real-Time Systems, 30(1-2):129-154, 2005. Google Scholar
  6. 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., pages 204-212. IEEE, 1996. Google Scholar
  7. Giorgio C. Buttazzo, Marko Bertogna, and Gang Yao. Limited preemptive scheduling for real-time systems. A survey. industrial Informatics, IEEE Transactions on, 9(1):3-15, 2013. Google Scholar
  8. John Cavicchio, Corey Tessler, and Nathan Fisher. Minimizing cache overhead via loaded cache blocks and preemption placement. In Real-Time Systems (ECRTS), 2015 27th Euromicro Conference on, pages 163-173. IEEE, 2015. Google Scholar
  9. CHOCO: Open Source Java Library for Constraint Programming. http://www.choco-solver.org/. Accessed: 2017-04-13.
  10. 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
  11. Rodolfo Pellizzoni, Bach D. Bui, Marco Caccamo, and Lui Sha. Coscheduling of CPU and I/O transactions in cost-based embedded systems. In Real-Time Systems Symposium, 2008, pages 221-231. IEEE, 2008. Google Scholar
  12. Bo Peng, Nathan Fisher, and Marko Bertogna. Explicit preemption placement for real-time conditional code. In Real-Time Systems (ECRTS), 2014 26th Euromicro Conference on, pages 177-188. IEEE, 2014. Google Scholar
  13. Stefan M Petters and Georg Färber. Scheduling analysis with respect to hardware related preemption delay. In Workshop on Real-Time Embedded Systems, London, UK, 2001. Google Scholar
  14. Harini Ramaprasad and Frank Mueller. Tightening the bounds on feasible preemptions. ACM Transactions on Embedded Computing Systems (TECS), 10(2):27, 2010. Google Scholar
  15. 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
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