Document Open Access Logo

Towards Efficient Explainability of Schedulability Properties in Real-Time Systems

Authors Sanjoy Baruah , Pontus Ekberg

PDF
Thumbnail PDF

File

LIPIcs.ECRTS.2023.2.pdf
  • Filesize: 0.91 MB
  • 20 pages

Document Identifiers

Author Details

Sanjoy Baruah
  • Washington University in Saint Louis, MO, USA
Pontus Ekberg
  • Uppsala University, Sweden

Funding

  • Baruah, Sanjoy: US National Science Foundation (Grants CNS-2141256 and CNS-2229290).
  • Ekberg, Pontus: Swedish Research Council grant 2018-04446.

Cite As Get BibTex

Sanjoy Baruah and Pontus Ekberg. Towards Efficient Explainability of Schedulability Properties in Real-Time Systems. In 35th Euromicro Conference on Real-Time Systems (ECRTS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 262, pp. 2:1-2:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.ECRTS.2023.2

Abstract

The notion of efficient explainability was recently introduced in the context of hard-real-time scheduling: a claim that a real-time system is schedulable (i.e., that it will always meet all deadlines during run-time) is defined to be efficiently explainable if there is a proof of such schedulability that can be verified by a polynomial-time algorithm. We further explore this notion by (i) classifying a variety of common schedulability analysis problems according to whether they are efficiently explainable or not; and (ii) developing strategies for dealing with those determined to not be efficiently schedulable, primarily by identifying practically meaningful sub-problems that are efficiently explainable.

Subject Classification

ACM Subject Classification
  • Computer systems organization → Real-time systems
  • Software and its engineering → Scheduling
Keywords
  • Recurrent Task Systems
  • Uniprocessor and Multiprocessor Schedulability
  • Verification
  • Explanation
  • Computational Complexity
  • Approximation Schemes

Metrics

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

References

  1. K. Albers and F. Slomka. An event stream driven approximation for the analysis of real-time systems. In Proceedings of the EuroMicro Conference on Real-Time Systems, pages 187-195, Catania, Sicily, July 2004. IEEE Computer Society Press. Google Scholar
  2. Sanjeev Arora and Boaz Barak. Computational Complexity - A Modern Approach. Cambridge University Press, 2009. Google Scholar
  3. Giorgio Ausiello, Alberto Marchetti-Spaccamela, Pierluigi Crescenzi, Giorgio Gambosi, Marco Protasi, and Viggo Kann. Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties. Springer Verlag, 1999. Google Scholar
  4. T. P. Baker and A. Shaw. The cyclic executive model and Ada. In Proceedings of the 9th Real-Time Systems Symposium (RTSS), pages 120-129, 1988. Google Scholar
  5. T. P. Baker and A. Shaw. The cyclic executive model and Ada. Real-Time Systems, 1(1):7-25, 1989. Google Scholar
  6. S. Baruah, R. Howell, and L. Rosier. Algorithms and complexity concerning the preemptive scheduling of periodic, real-time tasks on one processor. Real-Time Systems: The International Journal of Time-Critical Computing, 2:301-324, 1990. Google Scholar
  7. S. Baruah, A. Mok, and L. Rosier. Preemptively scheduling hard-real-time sporadic tasks on one processor. In Proceedings of the 11th Real-Time Systems Symposium (RTSS), pages 182-190, Orlando, Florida, 1990. IEEE Computer Society Press. Google Scholar
  8. Sanjoy Baruah and Pontus Ekberg. Certificates of real-time schedulability. In International Workshop on Explainability of Real-time Systems and their Analysis (ERSA), 2022. Google Scholar
  9. Sanjoy Baruah and Nathan Fisher. The partitioned multiprocessor scheduling of deadline-constrained sporadic task systems. IEEE Transactions on Computers, 55(7):918-923, July 2006. Google Scholar
  10. Kimaya Bedarkar, Mariam Vardishvili, Sergey Bozhko, Marco Maida, and Björn B. Brandenburg. From intuition to Coq: A case study in verified response-time analysis of FIFO scheduling. In IEEE Real-Time Systems Symposium, RTSS 2022, Houston, TX, USA, December 5-8, 2022, pages 197-210. IEEE, 2022. URL: https://doi.org/10.1109/RTSS55097.2022.00026.
  11. Yves Bertot and Pierre Castéran. Interactive theorem proving and program development: Coq’Art: the calculus of inductive constructions. Springer Science & Business Media, 2013. Project website: URL: https://coq.inria.fr.
  12. V. Bonifaci, A. Marchetti-Spaccamela, N. Megow, and A. Wiese. Polynomial-time exact schedulability tests for harmonic real-time tasks. In Proceedings of the 34th Real-Time Systems Symposium (RTSS), pages 236-245, December 2013. Google Scholar
  13. Sergey Bozhko and Björn B. Brandenburg. Abstract Response-Time Analysis: A Formal Foundation for the Busy-Window Principle. In Marcus Völp, editor, Proceedings of the 32nd Euromicro Conference on Real-Time Systems (ECRTS), volume 165 of Leibniz International Proceedings in Informatics (LIPIcs), pages 22:1-22:24, Dagstuhl, Germany, 2020. URL: https://doi.org/10.4230/LIPIcs.ECRTS.2020.22.
  14. Björn B. Brandenburg and Mahircan Gül. Global scheduling not required: Simple, near-optimal multiprocessor real-time scheduling with semi-partitioned reservations. In Proceedings of the 37th IEEE Real-Time Systems Symposium (RTSS), pages 99-110, 2016. URL: https://doi.org/10.1109/RTSS.2016.019.
  15. Felipe Cerqueira, Felix Stutz, and Björn B. Brandenburg. PROSA: A case for readable mechanized schedulability analysis. In Proceedings of the 28th Euromicro Conference on Real-Time Systems (ECRTS), pages 273-284, 2016. URL: https://doi.org/10.1109/ECRTS.2016.28.
  16. T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms. MIT Press, third edition, 2009. Google Scholar
  17. Robert Davis, Thomas Rothvoss, Sanjoy Baruah, and Alan Burns. Exact quantification of the sub-optimality of uniprocessor fixed priority pre-emptive scheduling. Real-Time Systems: The International Journal of Time-Critical Computing, 43(3):211-258, 2009. Google Scholar
  18. Friedrich Eisenbrand and Thomas Rothvoß. EDF-schedulability of synchronous periodic task systems is coNP-hard. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), January 2010. Google Scholar
  19. P. Ekberg and W. Yi. Uniprocessor feasibility of sporadic tasks remains coNP-complete under bounded utilization. In Proceedings of the 36th Real-Time Systems Symposium (RTSS), pages 87-95, 2015. Google Scholar
  20. P. Ekberg and W. Yi. Uniprocessor feasibility of sporadic tasks with constrained deadlines is strongly coNP-complete. In Proceedings of the 27th Euromicro Conference on Real-Time Systems (ECRTS), pages 281-286, 2015. Google Scholar
  21. Pontus Ekberg and Sanjoy Baruah. Partitioned scheduling of recurrent real-time tasks. In Proceedings of the 42nd Real-Time Systems Symposium (RTSS), pages 356-367, 2021. URL: https://doi.org/10.1109/RTSS52674.2021.00040.
  22. Pontus Ekberg and Wang Yi. Fixed-priority schedulability of sporadic tasks on uniprocessors is NP-hard. In Proceedings of the 38th Real-Time Systems Symposium (RTSS), pages 139-146. IEEE Computer Society, 2017. URL: https://doi.org/10.1109/RTSS.2017.00020.
  23. M. Joseph and P. Pandya. Finding response times in a real-time system. The Computer Journal, 29(5):390-395, October 1986. Google Scholar
  24. B. Kalyanasundaram and K. Pruhs. Speed is as powerful as clairvoyance. In 36th Annual Symposium on Foundations of Computer Science (FOCS'95), pages 214-223, Los Alamitos, October 1995. IEEE Computer Society Press. Google Scholar
  25. B. Kalyanasundaram and K. Pruhs. Speed is as powerful as clairvoyance. Journal of the ACM, 37(4):617-643, 2000. Google Scholar
  26. J. Lehoczky, L. Sha, and Y. Ding. The rate monotonic scheduling algorithm: Exact characterization and average case behavior. In Proceedings of the 10th Real-Time Systems Symposium (RTSS), pages 166-171. IEEE Computer Society Press, December 1989. Google Scholar
  27. C. Liu and J. Layland. Scheduling algorithms for multiprogramming in a hard real-time environment. Journal of the ACM, 20(1):46-61, 1973. Google Scholar
  28. Xingwu Liu, Zizhao Chen, Xin Han, Zhenyu Sun, and Zhishan Guo. Tighter bounds of speedup factor of partitioned EDF for constrained-deadline sporadic tasks. In 2021 IEEE Real-Time Systems Symposium (RTSS), pages 431-440, 2021. URL: https://doi.org/10.1109/RTSS52674.2021.00046.
  29. Marco Maida, Sergey Bozhko, and Björn B. Brandenburg. Foundational Response-Time Analysis as Explainable Evidence of Timeliness. In Proceedings of the 34th Euromicro Conference on Real-Time Systems (ECRTS), volume 231 of Leibniz International Proceedings in Informatics (LIPIcs), pages 19:1-19:25, Dagstuhl, Germany, 2022. URL: https://doi.org/10.4230/LIPIcs.ECRTS.2022.19.
  30. Aloysius Mok. Fundamental Design Problems of Distributed Systems for The Hard-Real-Time Environment. PhD thesis, Laboratory for Computer Science, Massachusetts Institute of Technology, 1983. Available as Technical Report No. MIT/LCS/TR-297. Google Scholar
  31. Christos H. Papadimitriou. Computational Complexity. Addison-Wesley, 1994. Google Scholar
  32. Cynthia A. Phillips, Cliff Stein, Eric Torng, and Joel Wein. Optimal time-critical scheduling via resource augmentation. In Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, pages 140-149, El Paso, Texas, 4-6 May 1997. Google Scholar
  33. Adi Shamir. IP = PSPACE. J. ACM, 39(4):869-877, October 1992. URL: https://doi.org/10.1145/146585.146609.
  34. Vijay V. Vazirani. Approximation Algorithms. Springer-Verlag, Berlin-Heidelberg-New York-Barcelona-Hong Kong-London-Milan-Paris-Singapur-Tokyo, 2001. Google Scholar
  35. Reinhard Wilhelm, Jakob Engblom, Andreas Ermedahl, Niklas Holsti, Stephan Thesing, David Whalley, Guillem Bernat, Christian Ferdinand, Reinhold Heckmann, Tulika Mitra, Frank Mueller, Isabelle Puaut, Peter Puschner, Jan Staschulat, and Per Stenström. The worst-case execution-time problem - overview of methods and survey of tools. ACM Transactions on Embedded Computing Systems, 7(3):36:1-36:53, May 2008. 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