Document Open Access Logo

DMAC: Deadline-Miss-Aware Control

Authors Paolo Pazzaglia, Claudio Mandrioli, Martina Maggio , Anton Cervin

PDF
Thumbnail PDF

File

LIPIcs.ECRTS.2019.1.pdf
  • Filesize: 0.65 MB
  • 24 pages

Document Identifiers

Author Details

Paolo Pazzaglia
  • Scuola Superiore Sant'Anna, Pisa, Italy
  • Department of Automatic Control, Lund University, Sweden
Claudio Mandrioli
  • Department of Automatic Control, Lund University, Sweden
Martina Maggio
  • Department of Automatic Control, Lund University, Sweden
Anton Cervin
  • Department of Automatic Control, Lund University, Sweden

Acknowledgements

All authors from Lund University are part of the ELLIIT Excellence Center. This work was partially supported by the Wallenberg Artificial Intelligence, Autonomous Systems and Software Program (WASP) funded by Knut and Alice Wallenberg Foundation.

Cite AsGet BibTex

Paolo Pazzaglia, Claudio Mandrioli, Martina Maggio, and Anton Cervin. DMAC: Deadline-Miss-Aware Control. In 31st Euromicro Conference on Real-Time Systems (ECRTS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 133, pp. 1:1-1:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ECRTS.2019.1

Abstract

The real-time implementation of periodic controllers requires solving a co-design problem, in which the choice of the controller sampling period is a crucial element. Classic design techniques limit the period exploration to safe values, that guarantee the correct execution of the controller alongside the remaining real-time load, i.e., ensuring that the controller worst-case response time does not exceed its deadline. This paper presents DMAC: the first formally-grounded controller design strategy that explores shorter periods, thus explicitly taking into account the possibility of missing deadlines. The design leverages information about the probability that specific sub-sequences of deadline misses are experienced. The result is a fixed controller that on average works as the ideal clairvoyant time-varying controller that knows future deadline hits and misses. We obtain a safe estimate of the hit and miss events using the scenario theory, that allows us to provide probabilistic guarantees. The paper analyzes controllers implemented using the Logical Execution Time paradigm and three different strategies to handle deadline miss events: killing the job, letting the job continue but skipping the next activation, and letting the job continue using a limited queue of jobs. Experimental results show that our design proposal - i.e., exploring the space where deadlines can be missed and handled with different strategies - greatly outperforms classical control design techniques.

Subject Classification

ACM Subject Classification
  • Computing methodologies → Computational control theory
  • Computer systems organization → Embedded software
  • Software and its engineering → Real-time systems software
  • Theory of computation → Stochastic control and optimization
Keywords
  • Weakly-Hard Real-Time Systems
  • Deadline Miss Handling
  • Control Design

Metrics

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

Supplementary Materials

References

  1. Leonie Ahrendts, Sophie Quinton, and Rolf Ernst. Finite ready queues as a mean for overload reduction in weakly-hard real-time systems. In Proceedings of the 25th International Conference on Real-Time Networks and Systems, pages 88-97. ACM, 2017. Google Scholar
  2. Sebastian Altmeyer, Liliana Cucu-Grosjean, and Robert I Davis. Static probabilistic timing analysis for real-time systems using random replacement caches. Real-Time Systems, 51(1):77-123, 2015. Google Scholar
  3. Sebastian Altmeyer and Robert I Davis. On the correctness, optimality and precision of static probabilistic timing analysis. In Proceedings of the conference on Design, Automation &Test in Europe, page 26. European Design and Automation Association, 2014. Google Scholar
  4. Amir Aminifar, Soheil Samii, Petru Eles, Zebo Peng, and Anton Cervin. Designing high-quality embedded control systems with guaranteed stability. In 2012 IEEE 33rd Real-Time Systems Symposium, pages 283-292. IEEE, 2012. Google Scholar
  5. Karl J Åström and Björn Wittenmark. Computer-controlled systems: theory and design. Courier Corporation, 2013. Google Scholar
  6. Philip Axer, Maurice Sebastian, and Rolf Ernst. Probabilistic response time bound for CAN messages with arbitrary deadlines. In Design, Automation &Test in Europe Conference &Exhibition (DATE), 2012, pages 1114-1117. IEEE, 2012. Google Scholar
  7. Guillem Bernat, Alan Burns, and Albert Liamosi. Weakly hard real-time systems. IEEE transactions on Computers, 50(4):308-321, 2001. 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. Alessandro Biondi, Marco Di Natale, Giorgio C Buttazzo, and Paolo Pazzaglia. Selecting the transition speeds of engine control tasks to optimize the performance. ACM Transactions on Cyber-Physical Systems, 2(1):1, 2018. Google Scholar
  10. Rainer Blind and Frank Allgöwer. Towards networked control systems with guaranteed stability: Using weakly hard real-time constraints to model the loss process. In Decision and Control (CDC), 2015 IEEE 54th Annual Conference on, pages 7510-7515. IEEE, 2015. Google Scholar
  11. Giuseppe C Calafiore and Marco C Campi. The scenario approach to robust control design. IEEE Transactions on Automatic Control, 51(5):742-753, 2006. Google Scholar
  12. Francisco J Cazorla, Eduardo Quiñones, Tullio Vardanega, Liliana Cucu, Benoit Triquet, Guillem Bernat, Emery Berger, Jaume Abella, Franck Wartel, Michael Houston, et al. Proartis: Probabilistically analyzable real-time systems. ACM Transactions on Embedded Computing Systems (TECS), 12(2s):94, 2013. Google Scholar
  13. Anton Cervin. Analysis of overrun strategies in periodic control tasks. In Proc. 16th IFAC World Congress, Prague, Czech Republic, page 137. Citeseer, 2005. Google Scholar
  14. Anton Cervin. JitterTime 1.0 reference manual. Technical report, Department of Automatic Control, Lund University, 2019. Technical Report TFRT-7658. Google Scholar
  15. Anton Cervin, Dan Henriksson, Bo Lincoln, Johan Eker, and K-E Arzen. How does control timing affect performance? Analysis and simulation of timing using Jitterbug and TrueTime. IEEE control systems, 23(3):16-30, 2003. Google Scholar
  16. Anton Cervin, Bo Lincoln, Johan Eker, Karl-Erik Arzén, and Giorgio Buttazzo. The jitter margin and its application in the design of real-time control systems. In Proceedings of the 10th International Conference on Real-Time and Embedded Computing Systems and Applications, pages 1-9. Gothenburg, Sweden, 2004. Google Scholar
  17. Kuan-Hsun Chen and Jian-Jia Chen. Probabilistic schedulability tests for uniprocessor fixed-priority scheduling under soft errors. In Industrial Embedded Systems (SIES), 2017 12th IEEE International Symposium on, pages 1-8. IEEE, 2017. Google Scholar
  18. Kuan-Hsun Chen, Georg Von Der Brüggen, and Jian-Jia Chen. Analysis of deadline miss rates for uniprocessor fixed-priority scheduling. In 2018 IEEE 24th International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA), pages 168-178. IEEE, 2018. Google Scholar
  19. Hoon Sung Chwa, Kang G Shin, and Jinkyu Lee. Closing the gap between stability and schedulability: a new task model for Cyber-Physical Systems. In 2018 IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS), pages 327-337. IEEE, 2018. Google Scholar
  20. G. Darivianakis, A. Eichler, R. S. Smith, and J. Lygeros. A Data-Driven Stochastic Optimization Approach to the Seasonal Storage Energy Management. IEEE Control Systems Letters, 1(2):394-399, 2017. Google Scholar
  21. Robert Davis, Tullio Vardanega, Franck Wartel, Liliana Cucu-Grosjean, et al. PROXIMA: a probabilistic approach to the timing behaviour of mixed-criticality systems. Ada User Journal, 2:118-122, 2014. Google Scholar
  22. Robert I Davis, Luca Santinelli, Sebastian Altmeyer, Claire Maiza, and Liliana Cucu-Grosjean. Analysis of probabilistic cache related pre-emption delays. In Real-Time Systems (ECRTS), 2013 25th Euromicro Conference on, pages 168-179. IEEE, 2013. Google Scholar
  23. José Luis Díaz, Daniel F García, Kanghee Kim, Chang-Gun Lee, L Lo Bello, José María López, Sang Lyul Min, and Orazio Mirabella. Stochastic analysis of periodic real-time systems. In Real-Time Systems Symposium, 2002. RTSS 2002. 23rd IEEE, pages 289-300. IEEE, 2002. Google Scholar
  24. Goran Frehse, Arne Hamann, Sophie Quinton, and Matthias Woehrle. Formal Analysis of Timing Effects on Closed-Loop Properties of Control Software. In RTSS, pages 53-62, 2014. Google Scholar
  25. Mongi Ben Gaid, Daniel Simon, and Olivier Sename. A design methodology for weakly-hard real-time control. IFAC Proceedings Volumes, 41(2):10258-10264, 2008. Google Scholar
  26. Vijay Gupta, Babak Hassibi, and Richard M Murray. Optimal LQG control across packet-dropping links. Systems &Control Letters, 56(6):439-446, 2007. Google Scholar
  27. Zain AH Hammadeh, Sophie Quinton, and Rolf Ernst. Extending typical worst-case analysis using response-time dependencies to bound deadline misses. In Embedded Software (EMSOFT), 2014 International Conference on, pages 1-10. IEEE, 2014. Google Scholar
  28. Thomas A Henzinger, Benjamin Horowitz, and Christoph Meyer Kirsch. Giotto: A time-triggered language for embedded programming. In International Workshop on Embedded Software, pages 166-184. Springer, 2001. Google Scholar
  29. Byung Kook Kim. Task scheduling with feedback latency for real-time control systems. In Real-Time Computing Systems and Applications, 1998. Proceedings. Fifth International Conference on, pages 37-41. IEEE, 1998. Google Scholar
  30. Leonidas Kosmidis, Jaume Abella, Eduardo Quiñones, and Francisco J Cazorla. A cache design for probabilistically analysable real-time systems. In Proceedings of the Conference on Design, Automation and Test in Europe, pages 513-518. EDA Consortium, 2013. Google Scholar
  31. Antzela Kosta, Nikolaos Pappas, Anthony Ephremides, and Vangelis Angelakis. Age and value of information: Non-linear age case. In Information Theory (ISIT), 2017 IEEE International Symposium on, pages 326-330. IEEE, 2017. Google Scholar
  32. 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
  33. John P Lehoczky. Fixed priority scheduling of periodic task sets with arbitrary deadlines. In Real-Time Systems Symposium, 1990. Proceedings., 11th, pages 201-209. IEEE, 1990. Google Scholar
  34. Bo Lincoln and Anton Cervin. Jitterbug: A tool for analysis of real-time control performance. In Proceedings of the 41st IEEE Conference on Decision and Control, 2002., volume 2, pages 1319-1324. IEEE, 2002. Google Scholar
  35. Steffen Linsenmayer and Frank Allgower. Stabilization of networked control systems with weakly hard real-time dropout description. In Decision and Control (CDC), 2017 IEEE 56th Annual Conference on, pages 4765-4770. IEEE, 2017. Google Scholar
  36. Rui Liu, Alex F Mills, and James H Anderson. Independence thresholds: Balancing tractability and practicality in soft real-time stochastic analysis. In Real-Time Systems Symposium (RTSS), 2014 IEEE, pages 314-323. IEEE, 2014. Google Scholar
  37. Bruce L. Miller and Harvey M. Wagner. Chance Constrained Programming with Joint Constraints. Oper. Res., 13(6), 1965. Google Scholar
  38. Johan Nilsson, Bo Bernhardsson, and Bjorn Wittenmark. Stochastic analysis and control of real-time systems with random time delays. Automatica, 34(1), 1998. Google Scholar
  39. Claire Pagetti, David Saussié, Romain Gratia, Eric Noulard, and Pierre Siron. The ROSACE case study: From Simulink specification to multi/many-core execution. In 20th IEEE Real-Time and Embedded Technology and Applications Symposium, pages 309-318, 2014. Google Scholar
  40. Paolo Pazzaglia, Marco Di Natale, Giorgio Buttazzo, and Matteo Secchiari. A framework for the co-simulation of engine controls and task scheduling. In International Conference on Software Engineering and Formal Methods, pages 438-452. Springer, 2017. Google Scholar
  41. Paolo Pazzaglia, Luigi Pannocchi, Alessandro Biondi, and Marco Di Natale. Beyond the Weakly Hard Model: Measuring the Performance Cost of Deadline Misses. In 30th Euromicro Conference on Real-Time Systems (ECRTS 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018. Google Scholar
  42. Parameswaran Ramanathan. Overload management in real-time control applications using (m,k)-firm guarantee. IEEE Transactions on Parallel and Distributed Systems, 10(6):549-559, 1999. Google Scholar
  43. Ola Redell and Martin Sanfridson. Exact best-case response time analysis of fixed priority scheduled tasks. In Real-Time Systems, 2002. Proceedings. 14th Euromicro Conference on, pages 165-172. IEEE, 2002. Google Scholar
  44. Luca Schenato, Bruno Sinopoli, Massimo Franceschetti, Kameshwar Poolla, and S Shankar Sastry. Foundations of control and estimation over lossy networks. Proceedings of the IEEE, 95(1):163-187, 2007. Google Scholar
  45. Bruno Sinopoli, Luca Schenato, Massimo Franceschetti, Kameshwar Poolla, and Shankar Sastry. An LQG optimal linear controller for control systems with packet losses. In Decision and Control, 2005 and 2005 European Control Conference. CDC-ECC'05. 44th IEEE Conference on, pages 458-463. IEEE, 2005. Google Scholar
  46. Damoon Soudbakhsh, Linh Thi Xuan Phan, Anuradha M Annaswamy, and Oleg Sokolsky. Co-design of arbitrated network control systems with overrun strategies. IEEE Transactions on Control of Network Systems, 5(1):128-141, 2018. Google Scholar
  47. Youcheng Sun and Marco Di Natale. Weakly Hard Schedulability Analysis for Fixed Priority Scheduling of Periodic Real-Time Tasks. ACM Transactions on Embedded Computing Systems (TECS), 16(5s):171, 2017. Google Scholar
  48. Zhendong Sun. Switched linear systems: control and design. Springer Science &Business Media, 2006. Google Scholar
  49. Bogdan Tanasa, Unmesh D Bordoloi, Petru Eles, and Zebo Peng. Probabilistic response time and joint analysis of periodic tasks. In Real-Time Systems (ECRTS), 2015 27th Euromicro Conference on, pages 235-246. IEEE, 2015. Google Scholar
  50. Eelco P van Horssen, AR Baghban Behrouzian, Dip Goswami, Duarte Antunes, Twan Basten, and WPMH Heemels. Performance analysis and controller improvement for linear systems with (m,k)-firm data losses. In 2016 European Control Conference (ECC), pages 2571-2577. IEEE, 2016. Google Scholar
  51. 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 LIPIcs-Leibniz International Proceedings in Informatics, volume 106 of ECRTS. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018. Google Scholar
  52. Franck Wartel, Leonidas Kosmidis, Code Lo, Benoit Triquet, Eduardo Quinones, Jaume Abella, Adriana Gogonel, Andrea Baldovin, Enrico Mezzetti, Liliana Cucu, et al. Measurement-based probabilistic timing analysis: Lessons from an integrated-modular avionics case study. In Industrial Embedded Systems (SIES), 2013 8th IEEE International Symposium on, pages 241-248. IEEE, 2013. Google Scholar
  53. Reinhard Wilhelm, Jakob Engblom, Andreas Ermedahl, Niklas Holsti, Stephan Thesing, David Whalley, Guillem Bernat, Christian Ferdinand, Reinhold Heckmann, Tulika Mitra, et al. The worst-case execution-time problem—overview of methods and survey of tools. ACM Transactions on Embedded Computing Systems (TECS), 7(3):36, 2008. Google Scholar
  54. Wenbo Xu, Zain AH Hammadeh, Alexander Kroller, Rolf Ernst, and Sophie Quinton. Improved deadline miss models for real-time systems using typical worst-case analysis. In 2015 27th Euromicro Conference on Real-Time Systems (ECRTS), pages 247-256. IEEE, 2015. Google Scholar
  55. Yang Xu, Karl-Erik Årzén, Anton Cervin, Enrico Bini, and Bogdan Tanasa. Exploiting job response-time information in the co-design of real-time control systems. In Embedded and Real-Time Computing Systems and Applications (RTCSA), 2015 IEEE 21st International Conference on, pages 247-256. IEEE, 2015. Google Scholar
  56. Tatsuya Yoshimoto and Toshimitsu Ushio. Optimal arbitration of control tasks by job skipping in cyber-physical systems. In Proceedings of the 2011 IEEE/ACM Second International Conference on Cyber-Physical Systems, pages 55-64. IEEE Computer Society, 2011. 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 Imprint Privacy Contact