Document Open Access Logo

A Mathematical Comparison Between Response-Time Analysis and Real-Time Calculus for Fixed-Priority Preemptive Scheduling

Authors Victor Pollex, Frank Slomka

PDF
Thumbnail PDF

File

LIPIcs.ECRTS.2022.7.pdf
  • Filesize: 0.83 MB
  • 25 pages

Document Identifiers

Author Details

Victor Pollex
  • INCHRON AG, Erlangen, Germany
Frank Slomka
  • Institute of Embedded Systems/Real-Time Systems, Faculty of Engineering and Computer Science, Universität Ulm, Germany

Funding

  • Pollex, Victor: This work was supported by Federal Ministry of Education and Research under the grant agreement number 01IS21031A.
  • Slomka, Frank: This work was supported by Federal Ministry of Education and Research under the grant agreement number 01IS21031B.

Cite AsGet BibTex

Victor Pollex and Frank Slomka. A Mathematical Comparison Between Response-Time Analysis and Real-Time Calculus for Fixed-Priority Preemptive Scheduling. In 34th Euromicro Conference on Real-Time Systems (ECRTS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 231, pp. 7:1-7:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ECRTS.2022.7

Abstract

Fixed-priority preemptive scheduling is a popular scheduling scheme for real-time systems. This is accompanied by a vast amount of research on how to analyse and check whether these systems satisfy their real-time requirements. Two methods that emerged from this research are the response-time analysis and the real-time calculus. These two methods have been compared empirically on the basis of several abstract systems showing that for some systems one method gives better results than the other and for other systems both methods appear to give the same results. However, empirical analyses inherently contain uncertainty. To get a definitive answer we compare both methods mathematically and we show that both methods give the same results for systems that use fixed-priority preemptive scheduling and independent tasks.

Subject Classification

ACM Subject Classification
  • Computer systems organization → Real-time systems
  • Computer systems organization → Embedded and cyber-physical systems
  • Software and its engineering → Scheduling
Keywords
  • real-time systems
  • fixed-priority scheduling
  • response-time analysis
  • real-time calculus

Metrics

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

References

  1. 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, September 1993. URL: https://doi.org/10.1049/sej.1993.0034.
  2. Neil C. Audsley, Alan Burns, Robert I. Davis, Ken W. Tindell, and Andy J. Wellings. Fixed Priority Pre-emptive Scheduling: An Historical Perspective. Real Time Systems, 8(2-3):173-198, March 1995. URL: https://doi.org/10.1007/BF01094342.
  3. Marc Boyer and Pierre Roux. A common framework embedding network calculus and event stream theory. Technical report, ONERA - The french aerospace lab, May 2016. Preprint. URL: https://hal.archives-ouvertes.fr/hal-01311502.
  4. Marc Boyer and Pierre Roux. Embedding network calculus and event stream theory in a common model. In 21st IEEE International Conference on Emerging Technologies and Factory Automation, ETFA 2016, Berlin, Germany, September 6-9, 2016, pages 1-8. IEEE, 2016. URL: https://doi.org/10.1109/ETFA.2016.7733565.
  5. Samarjit Chakraborty, Simon Künzli, and Lothar Thiele. A General Framework for Analysing System Properties in Platform-Based Embedded System Designs. In 2003 Design, Automation and Test in Europe Conference and Exposition (DATE 2003), 3-7 March 2003, Munich, Germany, pages 10190-10195. IEEE Computer Society, 2003. URL: https://doi.org/10.1109/DATE.2003.10083.
  6. Rene L. Cruz. A Calculus for Network Delay, Part I: Network Elements in Isolation. IEEE Transactions on Information Theory, 37(1):114-131, January 1991. URL: https://doi.org/10.1109/18.61109.
  7. Rene L. Cruz. A Calculus for Network Delay, Part II: Network Analysis. IEEE Transactions on Information Theory, 37(1):132-141, January 1991. URL: https://doi.org/10.1109/18.61110.
  8. Markus Fidler. A Survey of Deterministic and Stochastic Service Curve Models in the Network Calculus. IEEE Communications Surveys & Tutorials, 12(1):59-86, 2010. URL: https://doi.org/10.1109/SURV.2010.020110.00019.
  9. Mathai Joseph and Paritosh Pandya. Finding Response Times in a Real-Time System. The Computer Journal, 29(5):390-395, January 1986. URL: https://doi.org/10.1093/comjnl/29.5.390.
  10. Jean-Yves Le Boudec and Patrick Thiran. Network Calculus: A Theory of Deterministic Queuing Systems for the Internet, volume 2050 of Lecture Notes in Computer Science. Springer, 2001. URL: https://doi.org/10.1007/3-540-45318-0.
  11. John P. Lehoczky. Fixed Priority Scheduling of Periodic Task Sets with Arbitrary Deadlines. In Proceedings of the Real-Time Systems Symposium - 1990, Lake Buena Vista, Florida, USA, December 1990, pages 201-209. IEEE Computer Society, December 1990. URL: https://doi.org/10.1109/REAL.1990.128748.
  12. C. L. Liu and James W. Layland. Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment. Journal of the ACM, 20(1):46-61, January 1973. URL: https://doi.org/10.1145/321738.321743.
  13. Martin Naedele, Lothar Thiele, and Michael Eisenring. Characterizing Variable Task Releases and Processor Capacities. Technical report, ETH Zürich, 1999. URL: https://doi.org/10.3929/ethz-a-004289034.
  14. Simon Perathoner, Ernesto Wandeler, Lothar Thiele, Arne Hamann, Simon Schliecker, Rafik Henia, Razvan Racu, Rolf Ernst, and Michael González Harbour. Influence of Different System Abstractions on the Performance Analysis of Distributed Real-Time Systems. In Christoph M. Kirsch and Reinhard Wilhelm, editors, Proceedings of the 7th ACM & IEEE International conference on Embedded software, EMSOFT 2007, September 30 - October 3, 2007, Salzburg, Austria, pages 193-202. ACM, 2007. URL: https://doi.org/10.1145/1289927.1289959.
  15. Victor Pollex, Steffen Kollmann, and Frank Slomka. Generalizing Response-Time Analysis. In 16th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2010, Macau, SAR, China, 23-25 August 2010, pages 203-211. IEEE Computer Society, 2010. URL: https://doi.org/10.1109/RTCSA.2010.36.
  16. Kai Richter. Compositional Scheduling Analysis Using Standard Event Models. PhD thesis, Technical University Carolo-Wilhemina of Braunschweig, 2005. URL: https://doi.org/10.24355/dbbs.084-200511080100-362.
  17. Simon Schliecker. Performance Analysis of Multiprocessor Real-Time Systems with Shared Resources. PhD thesis, Technical University Carolo-Wilhemina of Braunschweig, 2011. URL: https://doi.org/10.24355/dbbs.084-201111210932-0.
  18. Simon Schliecker, Jonas Rox, Matthias Ivers, and Rolf Ernst. Providing Accurate Event Models for the Analysis of Heterogeneous Multiprocessor Systems. In Catherine H. Gebotys and Grant Martin, editors, Proceedings of the 6th International Conference on Hardware/Software Codesign and System Synthesis, CODES+ISSS 2008, Atlanta, GA, USA, October 19-24, 2008, pages 185-190. ACM, 2008. URL: https://doi.org/10.1145/1450135.1450177.
  19. Frank Slomka and Mohammadreza Sadeghi. HeRTA: Heaviside Real-Time Analysis, 2020. Preprint. URL: https://doi.org/10.48550/arXiv.2007.12112.
  20. Frank Slomka and Mohammadreza Sadeghi. Beyond the limitations of real-time scheduling theory: a unified scheduling theory for the analysis of real-time systems. SICS Software-Intensive Cyber Physical Systems, 35(3-4):201-236, 2021. URL: https://doi.org/10.1007/s00450-021-00429-1.
  21. Frank Slomka and Mohammadreza Sadeghi. Work-in-Progress Abstract: On the relationship between scheduling theory and real-time calculus. In 27th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2021, Houston, TX, USA, August 18-20, 2021, pages 195-197. IEEE, 2021. URL: https://doi.org/10.1109/RTCSA52859.2021.00030.
  22. Alfred Tarski. A lattice-theoretical fixpoint theorem and its applications. Pacific Journal of Mathematics, 5(2):285-309, 1955. URL: https://doi.org/10.2140/pjm.1955.5.285.
  23. Lothar Thiele, Samarjit Chakraborty, and Martin Naedele. Real-time calculus for scheduling hard real-time systems. In IEEE International Symposium on Circuits and Systems, ISCAS 2000, Emerging Technologies for the 21st Century, Geneva, Switzerland, 28-31 May 2000, Proceedings, pages 101-104. IEEE, 2000. URL: https://doi.org/10.1109/ISCAS.2000.858698.
  24. Ken Tindell and John Clark. Holistic schedulability analysis for distributed hard real-time systems. Microprocessing and Microprogramming, 40(2-3):117-134, April 1994. URL: https://doi.org/10.1016/0165-6074(94)90080-9.
  25. Ken W. Tindell, Alan Burns, and Andy J. Wellings. An Extendible Approach for Analyzing Fixed Priority Hard Real-Time Tasks. Real-Time Systems, 6(2):133-151, March 1994. URL: https://doi.org/10.1007/BF01088593.
  26. Ernesto Wandeler. Modular Performance Analysis and Interface-Based Design for Embedded Real-Time Systems. PhD thesis, Swiss Federal Institute of Technology Zurich, 2006. URL: https://doi.org/10.3929/ethz-a-005328667.
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