Document Open Access Logo

Efficiently Approximating the Probability of Deadline Misses in Real-Time Systems

Authors Georg von der Brüggen , Nico Piatkowski , Kuan-Hsun Chen , Jian-Jia Chen , Katharina Morik

PDF
Thumbnail PDF

File

LIPIcs.ECRTS.2018.6.pdf
  • Filesize: 0.91 MB
  • 22 pages

Document Identifiers

Author Details

Georg von der Brüggen
  • Department of Computer Science, TU Dortmund University, Germany
Nico Piatkowski
  • Department of Computer Science, TU Dortmund University, Germany
Kuan-Hsun Chen
  • Department of Computer Science, TU Dortmund University, Germany
Jian-Jia Chen
  • Department of Computer Science, TU Dortmund University, Germany
Katharina Morik
  • Department of Computer Science, TU Dortmund University, Germany

Funding

This paper is supported by DFG, as part of the Collaborative Research Center SFB876 (http://sfb876.tu-dortmund.de/), project A1 and project B2.

Cite As Get BibTex

Georg von der Brüggen, Nico Piatkowski, Kuan-Hsun Chen, Jian-Jia Chen, and Katharina Morik. Efficiently Approximating the Probability of Deadline Misses in Real-Time Systems. In 30th Euromicro Conference on Real-Time Systems (ECRTS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 106, pp. 6:1-6:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ECRTS.2018.6

Abstract

This paper explores the probability of deadline misses for a set of constrained-deadline sporadic soft real-time tasks on uniprocessor platforms. We explore two directions to evaluate the probability whether a job of the task under analysis can finish its execution at (or before) a testing time point t. One approach is based on analytical upper bounds that can be efficiently computed in polynomial time at the price of precision loss for each testing point, derived from the well-known Hoeffding's inequality and the well-known Bernstein's inequality. Another approach convolutes the probability efficiently over multinomial distributions, exploiting a series of state space reduction techniques, i.e., pruning without any loss of precision, and approximations via unifying equivalent classes with a bounded loss of precision. We demonstrate the effectiveness of our approaches in a series of evaluations. Distinct from the convolution-based methods in the literature, which suffer from the high computation demand and are applicable only to task sets with a few tasks, our approaches can scale reasonably without losing much precision in terms of the derived probability of deadline misses.

Subject Classification

ACM Subject Classification
  • Computer systems organization → Real-time systems
Keywords
  • deadline miss probability
  • multinomial-based approach
  • analytical bound

Metrics

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

Related Versions

References

  1. IEC-61508 Edition 2.0. Functional safety of electrical / electronic / programmable electronic safety-related systems ed2.0. Technical report, International Electrotechnical Commission (IEC), 2010. URL: http://www.iec.ch/functionalsafety/standards/page2.htm.
  2. Philip Axer and Rolf Ernst. Stochastic response-time guarantee for non-preemptive, fixed-priority scheduling under errors. In The 50th Annual Design Automation Conference 2013, DAC '13, Austin, TX, USA, May 29 - June 07, 2013, pages 172:1-172:7, 2013. URL: http://dx.doi.org/10.1145/2463209.2488946.
  3. Robert C. Baumann. Radiation-induced soft errors in advanced semiconductor technologies. IEEE Transactions on Device and Materials Reliability, 5(3):305-316, Sept 2005. URL: http://dx.doi.org/10.1109/TDMR.2005.853449.
  4. Slim Ben-Amor, Dorin Maxim, and Liliana Cucu-Grosjean. Schedulability analysis of dependent probabilistic real-time tasks. In Proceedings of the 24th International Conference on Real-Time Networks and Systems, RTNS 2016, Brest, France, October 19-21, 2016, pages 99-107, 2016. URL: http://dx.doi.org/10.1145/2997465.2997499.
  5. Enrico Bini and Giorgio C. Buttazzo. Schedulability analysis of periodic fixed priority systems. IEEE Trans. Computers, 53(11):1462-1473, 2004. URL: http://dx.doi.org/10.1109/TC.2004.103.
  6. Enrico Bini and Giorgio C. Buttazzo. Measuring the performance of schedulability tests. Real-Time Systems, 30(1-2):129-154, 2005. URL: http://dx.doi.org/10.1007/s11241-005-0507-9.
  7. Jian-Jia Chen, Wen-Hung Huang, and Cong Liu. k2u: A general framework from k-point effective schedulability analysis to utilization-based tests. In 2015 IEEE Real-Time Systems Symposium, RTSS 2015, San Antonio, Texas, USA, December 1-4, 2015, pages 107-118, 2015. URL: http://dx.doi.org/10.1109/RTSS.2015.18.
  8. Kuan-Hsun Chen and Jian-Jia Chen. Probabilistic schedulability tests for uniprocessor fixed-priority scheduling under soft errors. In 12th IEEE International Symposium on Industrial Embedded Systems, SIES 2017, Toulouse, France, June 14-16, 2017, pages 1-8, 2017. URL: http://dx.doi.org/10.1109/SIES.2017.7993392.
  9. José Luis Díaz, Daniel F. García, Kanghee Kim, Chang-Gun Lee, Lucia Lo Bello, José María López, Sang Lyul Min, and Orazio Mirabella. Stochastic analysis of periodic real-time systems. In Proceedings of the 23rd IEEE Real-Time Systems Symposium (RTSS'02), Austin, Texas, USA, December 3-5, 2002, pages 289-300, 2002. URL: http://dx.doi.org/10.1109/REAL.2002.1181583.
  10. Paul Emberson, Roger Stafford, and Robert I. Davis. Techniques for the synthesis of multiprocessor tasksets. In International Workshop on Analysis Tools and Methodologies for Embedded and Real-time Systems (WATERS 2010), pages 6-11, 2010. URL: https://waters2016.inria.fr/files/2017/02/WATERS16-proceedings-final.pdf.
  11. Simon Foucart and Holger Rauhut. A Mathematical Introduction to Compressive Sensing. Springer New York, 2013. URL: http://dx.doi.org/10.1007/978-0-8176-4948-7.
  12. Wassily Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58(301):13-30, 1963. URL: http://www.jstor.org/stable/2282952.
  13. Jie S. Hu, Feihui Li, Vijay Degalahal, Mahmut T. Kandemir, Narayanan Vijaykrishnan, and Mary Jane Irwin. Compiler-directed instruction duplication for soft error detection. In 2005 Design, Automation and Test in Europe Conference and Exposition (DATE 2005), 7-11 March 2005, Munich, Germany, pages 1056-1057, 2005. URL: http://dx.doi.org/10.1109/DATE.2005.98.
  14. ISO-26262-1:2011. Iso/fdis26262: Road vehicles - functional safety. Technical report, International Organization for Standardization (ISO), 2000. URL: https://www.iso.org/standard/43464.html.
  15. Simon Kramer, Dirk Ziegenbein, and Arne Hamann. Real world automotive benchmarks for free. In 6th International Workshop on Analysis Tools and Methodologies for Embedded and Real-time Systems (WATERS), 2015. Google Scholar
  16. John P. Lehoczky, Lui Sha, and Yuqin Ding. The rate monotonic scheduling algorithm: Exact characterization and average case behavior. In Proceedings of the Real-Time Systems Symposium - 1989, Santa Monica, California, USA, December 1989, pages 166-171, 1989. URL: http://dx.doi.org/10.1109/REAL.1989.63567.
  17. Dorin Maxim and Liliana Cucu-Grosjean. Response time analysis for fixed-priority tasks with multiple probabilistic parameters. In Proceedings of the IEEE 34th Real-Time Systems Symposium, RTSS 2013, Vancouver, BC, Canada, December 3-6, 2013, pages 224-235, 2013. URL: http://dx.doi.org/10.1109/RTSS.2013.30.
  18. Michael Mitzenmacher and Eli Upfal. Probability and Computing - Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, 2005. Google Scholar
  19. Bogdan Nicolescu, Raoul Velazco, Matteo Sonza-Reorda, Maurizio Rebaudengo, and Massimo Violante. A software fault tolerance method for safety-critical systems: effectiveness and drawbacks. In Integrated Circuits and Systems Design, pages 101-106, 2002. URL: http://dx.doi.org/10.1109/SBCCI.2002.1137644.
  20. Nahmsuk Oh, Philip P. Shirvani, and Edward J. McCluskey. Error detection by duplicated instructions in super-scalar processors. IEEE Trans. Reliability, 51(1):63-75, 2002. URL: http://dx.doi.org/10.1109/24.994913.
  21. Nico Piatkowski, Sangkyun Lee, and Katharina Morik. Spatio-temporal random fields: compressible representation and distributed estimation. Machine Learning, 93(1):115-139, 2013. URL: http://dx.doi.org/10.1007/s10994-013-5399-7.
  22. Nico Piatkowski and Katharina Morik. Stochastic discrete clenshaw-curtis quadrature. In Proceedings of the 33rd International Conference on Machine Learning, ICML 2016, New York, USA, 19-24 June 2016, JMLR: W&CP. JMLR.org, June 2016. URL: http://jmlr.org/proceedings/papers/v48/piatkowski16.html.
  23. Semeen Rehman, Muhammad Shafique, Pau Vilimelis Aceituno, Florian Kriebel, Jian-Jia Chen, and Jörg Henkel. Leveraging variable function resilience for selective software reliability on unreliable hardware. In Design, Automation and Test in Europe, DATE 13, Grenoble, France, March 18-22, 2013, pages 1759-1764, 2013. URL: http://dx.doi.org/10.7873/DATE.2013.354.
  24. Bogdan Tanasa, Unmesh D. Bordoloi, Petru Eles, and Zebo Peng. Probabilistic response time and joint analysis of periodic tasks. In 27th Euromicro Conference on Real-Time Systems, ECRTS 2015, Lund, Sweden, July 8-10, 2015, pages 235-246, 2015. URL: http://dx.doi.org/10.1109/ECRTS.2015.28.
  25. Georg von der Brüggen, Jian-Jia Chen, and Wen-Hung Huang. 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, pages 90-101, 2015. URL: http://dx.doi.org/10.1109/ECRTS.2015.16.
  26. Georg von der Brüggen, Kuan-Hsun Chen, Wen-Hung Huang, and Jian-Jia Chen. Systems with dynamic real-time guarantees in uncertain and faulty execution environments. In 2016 IEEE Real-Time Systems Symposium, RTSS 2016, Porto, Portugal, November 29 - December 2, 2016, pages 303-314, 2016. URL: http://dx.doi.org/10.1109/RTSS.2016.037.
  27. Georg von der Brüggen, Nico Piatkowski, Kuan-Hsun Chen, Jian-Jia Chen, and Katharina Morik. Efficiently approximating the probability of deadline misses in real-time systems. Technical report, Department of Computer Science, TU Dortmund University, Germany, 2018. URL: https://ls12-www.cs.tu-dortmund.de/daes/media/documents/publications/downloads/2018-brueggen-ecrts-deadline-miss-probability.pdf.
  28. Dakai Zhu, Hakan Aydin, and Jian-Jia Chen. Optimistic reliability aware energy management for real-time tasks with probabilistic execution times. In Proceedings of the 29th IEEE Real-Time Systems Symposium, RTSS 2008, Barcelona, Spain, 30 November - 3 December 2008, pages 313-322, 2008. URL: http://dx.doi.org/10.1109/RTSS.2008.37.
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