Document Open Access Logo

Graceful Degradation in Semi-Clairvoyant Scheduling

Authors Sanjoy Baruah, Pontus Ekberg

PDF

File

Thumbnail PDF
PDF
LIPIcs.ECRTS.2021.9.pdf
  • Filesize: 0.72 MB
  • 21 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Computer systems organization → Embedded and cyber-physical systems
  • Software and its engineering → Real-time schedulability
Keywords
  • Mixed criticality
  • semi-clairvoyance
  • graceful degradation

Metrics

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

Abstract

In the Vestal model of mixed-criticality systems, jobs are characterized by multiple different estimates of their actual, but unknown, worst-case execution time (WCET) parameters. Some recent research has focused upon a semi-clairvoyant model for mixed-criticality systems in which it is assumed that each job reveals upon arrival which of its WCET parameters it will respect. We study the problem of scheduling such semi-clairvoyant systems to ensure graceful degradation of service to less critical jobs in the event that the systems exhibit high-criticality behavior. We propose multiple different interpretations of graceful degradation in such systems, and derive efficient scheduling algorithms that are capable of ensuring graceful degradation under these different interpretations.

Cite As Get BibTex

Sanjoy Baruah and Pontus Ekberg. Graceful Degradation in Semi-Clairvoyant Scheduling. In 33rd Euromicro Conference on Real-Time Systems (ECRTS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 196, pp. 9:1-9:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.ECRTS.2021.9

Author Details

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

Funding

  • Baruah, Sanjoy: National Science Foundation Grants CNS-1814739 and CPS-1932530.
  • Ekberg, Pontus: Swedish Research Council grant 2018-04446.

References

  1. Kunal Agrawal, Sanjoy Baruah, and Alan Burns. Semi-clairvoyance in mixed-criticality scheduling. In Proceedings of the Real-Time Systems Symposium (RTSS), pages 458-468, December 2019. URL: https://doi.org/10.1109/RTSS46320.2019.00047.
  2. 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, pages 182-190, Orlando, Florida, 1990. IEEE Computer Society Press. URL: https://doi.org/10.1109/REAL.1990.128746.
  3. Sanjoy Baruah, Marko Bertogna, and Giorgio Buttazzo. Multiprocessor Scheduling for Real-Time Systems. Springer Publishing Company, Incorporated, 2015. URL: https://doi.org/10.1007/978-3-319-08696-5.
  4. Sanjoy Baruah, Vincenzo Bonifaci, Gianlorenzo D'Angelo, Haohan Li, Alberto Marchetti-Spaccamela, Nicole Megow, and Leen Stougie. Scheduling real-time mixed-criticality jobs. IEEE Transactions on Computers, 2012. URL: https://doi.org/10.1109/TC.2011.142.
  5. Sanjoy Baruah, Vincenzo Bonifaci, Gianlorenzo D'angelo, Haohan Li, Alberto Marchetti-Spaccamela, Suzanne Van Der Ster, and Leen Stougie. Preemptive uniprocessor scheduling of mixed-criticality sporadic task systems. Journal of the ACM, 62(2):14:1-14:33, 2015. URL: https://doi.org/10.1145/2699435.
  6. Sanjoy Baruah and Alan Burns. Sustainable scheduling analysis. In Proceedings of the IEEE Real-time Systems Symposium, pages 159-168, Rio de Janeiro, December 2006. IEEE Computer Society Press. URL: https://doi.org/10.1109/RTSS.2006.47.
  7. Sanjoy Baruah, Alan Burns, and Robert Davis. Response-time analysis for mixed criticality systems. In Proceedings of the IEEE Real-Time Systems Symposium (RTSS), Vienna, Austria, 2011. IEEE Computer Society Press. URL: https://doi.org/10.1109/RTSS.2011.12.
  8. Sanjoy Baruah, Alan Burns, and Zhishan Guo. Scheduling mixed-criticality systems to guarantee some service under all non-erroneous behaviors. In Proceedings of the 2016 28th EuroMicro Conference on Real-Time Systems, ECRTS '16, Toulouse (France), 2016. IEEE Computer Society Press. URL: https://doi.org/10.1109/ECRTS.2016.12.
  9. Sanjoy Baruah, Arvind Easwaran, and Zhishan Guo. MC-Fluid: simplified and optimally quantified. In Real-Time Systems Symposium (RTSS), 2015 IEEE, December 2015. URL: https://doi.org/10.1109/RTSS.2015.38.
  10. Sanjoy Baruah, Haohan Li, and Leen Stougie. Towards the design of certifiable mixed-criticality systems. In Proceedings of the IEEE Real-Time Technology and Applications Symposium (RTAS). IEEE, April 2010. URL: https://doi.org/10.1109/RTAS.2010.10.
  11. I. Borosh and L. Treybig. Bounds on positive integral solutions of linear diophantine equations. Proceedings of the American Mathematical Society, 55:299-304, 1976. URL: https://doi.org/10.1090/S0002-9939-1976-0396605-3.
  12. A. Burns and S. Baruah. Timing faults and mixed criticality systems. In Jones and Lloyd, editors, Dependable and Historic Computing, volume LNCS 6875, pages 147-166. Springer, 2011. URL: https://doi.org/10.1007/978-3-642-24541-1_12.
  13. Alan Burns and Sanjoy Baruah. Towards a more practical model for mixed criticality systems. In Proceedings of the International Workshop on Mixed Criticality Systems (WMC), December 2014. Google Scholar
  14. Alan Burns and Robert Ian Davis. Schedulability analysis for adaptive mixed criticality systems with arbitrary deadlines and semi-clairvoyance. In Proceedings of the IEEE Real-Time Systems Symposium, 2020. URL: https://doi.org/10.1109/RTSS49844.2020.00013.
  15. Jian-Jia Chen, Georg von der Brüggen, Wen-Hung Huang, and Robert I. Davis. On the Pitfalls of Resource Augmentation Factors and Utilization Bounds in Real-Time Scheduling. In Marko Bertogna, editor, 29th Euromicro Conference on Real-Time Systems (ECRTS 2017), volume 76 of Leibniz International Proceedings in Informatics (LIPIcs), pages 9:1-9:25, Dagstuhl, Germany, 2017. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.ECRTS.2017.9.
  16. Lin Chen, Franziska Eberle, Nicole Megow, Kevin Schewior, and Cliff Stein. A general framework for handling commitment in online throughput maximization. In Integer Programming and Combinatorial Optimization (IPCO), pages 141-154, Cham, 2019. Springer International Publishing. Google Scholar
  17. Michael Dertouzos. Control robotics : the procedural control of physical processors. In Proceedings of the IFIP Congress, pages 807-813, 1974. Google Scholar
  18. Pontus Ekberg and Wang Yi. Bounding and shaping the demand of generalized mixed-criticality sporadic task systems. Real-Time Systems, 50(1):48-86, 2014. URL: https://doi.org/10.1007/s11241-013-9187-z.
  19. Rolf Ernst and Marco Di Natale. Mixed criticality systems - A history of misconceptions? IEEE Design & Test, 33(5):65-74, 2016. URL: https://doi.org/10.1109/MDAT.2016.2594790.
  20. Alexandre Esper, Geoffrey Nelissen, Vincent Nélis, and Eduardo Tovar. How realistic is the mixed-criticality real-time system model? In Proceedings of the 23rd International Conference on Real Time and Networks Systems, RTNS '15, pages 139-148, New York, NY, USA, 2015. ACM. URL: https://doi.org/10.1145/2834848.2834869.
  21. Michael R. Garey and David S. Johnson. Computers and Intractability; A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., USA, 1979. Google Scholar
  22. G. Giannopoulou, P Huang, R Ahmed, D Bartolini, and L Thiele. Isolation scheduling on multicores: model and scheduling approaches. Real-Time Systems: The International Journal of Time-Critical Computing, 53:614-667, 2017. URL: https://doi.org/10.1007/s11241-017-9277-4.
  23. Xiaozhe Gu and Arvind Easwaran. Dynamic budget management with service guarantees for mixed-criticality systems. In 2016 IEEE Real-Time Systems Symposium, RTSS 2016, Porto, Portugal, November 29 - December 2, 2016, pages 47-56, 2016. URL: https://doi.org/10.1109/RTSS.2016.014.
  24. Z. Guo, K. Yang, S. Vaidhun, S. Arefin, S. K. Das, and H. Xiong. Uniprocessor mixed-criticality scheduling with graceful degradation by completion rate. In 2018 IEEE Real-Time Systems Symposium (RTSS), pages 373-383, 2018. URL: https://doi.org/10.1109/RTSS.2018.00052.
  25. 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, 1995. IEEE Computer Society Press. URL: https://doi.org/10.1109/SFCS.1995.492478.
  26. Jaewoo Lee, Kieu-My Phan, Xiaozhe Gu, Jiyeon Lee, A. Easwaran, Insik Shin, and Insup Lee. MC-Fluid: Fluid model-based mixed-criticality scheduling on multiprocessors. In Real-Time Systems Symposium (RTSS), 2014 IEEE, pages 41-52, December 2014. URL: https://doi.org/10.1109/RTSS.2014.32.
  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. URL: https://doi.org/10.1145/321738.321743.
  28. A. Mok. Task management techniques for enforcing ED scheduling on a periodic task set. In Proceedings of the 5th IEEE Workshop on Real-Time Software and Operating Systems, pages 42-46, Washington D.C., May 1988. Google Scholar
  29. Dario Socci, Petro Poplavko, Saddek Bensalem, and Marius Bozga. Mixed critical earliest deadline first. In Proceedings of the 2013 25th Euromicro Conference on Real-Time Systems, ECRTS '13, Paris (France), 2013. IEEE Computer Society Press. URL: https://doi.org/10.1109/ECRTS.2013.20.
  30. Steve Vestal. Preemptive scheduling of multi-criticality systems with varying degrees of execution time assurance. In Proceedings of the Real-Time Systems Symposium (RTSS), pages 239-243, Tucson, AZ, December 2007. IEEE Computer Society Press. URL: https://doi.org/10.1109/RTSS.2007.47.
  31. Reinhard Wilhelm. Mixed feelings about mixed criticality (invited paper). In Florian Brandner, editor, Proceedings of the 18th International Workshop on Worst-Case Execution Time Analysis, pages 1:1-1:9. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. URL: https://doi.org/10.4230/OASIcs.WCET.2018.1.
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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact