Document Open Access Logo

On Strong and Weak Sustainability, with an Application to Self-Suspending Real-Time Tasks

Authors Felipe Cerqueira, Geoffrey Nelissen, Björn B. Brandenburg

PDF
Thumbnail PDF

File

LIPIcs.ECRTS.2018.26.pdf
  • Filesize: 0.87 MB
  • 21 pages

Document Identifiers

Author Details

Felipe Cerqueira
  • Max Planck Institute for Software Systems (MPI-SWS), Kaiserslautern, Germany
Geoffrey Nelissen
  • CISTER Research Centre, ISEP, Polytechnic Institute of Porto (IPP), Porto, Portugal
Björn B. Brandenburg
  • Max Planck Institute for Software Systems (MPI-SWS), Kaiserslautern, Germany

Funding

This work was funded by Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) - 391919384, and partially supported by National Funds through FCT (Portuguese Foundation for Science and Technology) within the CISTER Research Unit (CEC/04234).

Cite As Get BibTex

Felipe Cerqueira, Geoffrey Nelissen, and Björn B. Brandenburg. On Strong and Weak Sustainability, with an Application to Self-Suspending Real-Time Tasks. In 30th Euromicro Conference on Real-Time Systems (ECRTS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 106, pp. 26:1-26:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ECRTS.2018.26

Abstract

Motivated by an apparent contradiction regarding whether certain scheduling policies are sustainable, we revisit the topic of sustainability in real-time scheduling and argue that the existing definitions of sustainability should be further clarified and generalized. After proposing a formal, generic sustainability theory, we relax the existing notion of (strongly) sustainable scheduling policy to provide a new classification called weak sustainability. Proving weak sustainability properties allows reducing the number of variables that must be considered in the search of a worst-case schedule, and hence enables more efficient schedulability analyses and testing regimes even for policies that are not (strongly) sustainable. As a proof of concept, and to better understand a model for which many mistakes were found in the literature, we study weak sustainability in the context of dynamic self-suspending tasks, where we formalize a generic suspension model using the Coq proof assistant and provide a machine-checked proof that any JLFP scheduling policy is weakly sustainable with respect to job costs and variable suspension times.

Subject Classification

ACM Subject Classification
  • Software and its engineering → Real-time schedulability
Keywords
  • real-time scheduling
  • sustainability
  • self-suspending tasks
  • machine-checked proofs

Metrics

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

References

  1. Yasmina Abdeddaïm and Damien Masson. The scheduling problem of self-suspending periodic real-time tasks. In Proceedings of the 20th International Conference on Real-Time and Network Systems, RTNS'12, pages 211-220, 2012. Google Scholar
  2. Theodore P. Baker and Sanjoy K. Baruah. Sustainable multiprocessor scheduling of sporadic task systems. In Proceedings of the 21st Euromicro Conference on Real-Time Systems, ECRTS '09, pages 141-150, 2009. Google Scholar
  3. Sanjoy Baruah. Scheduling periodic tasks on uniform multiprocessors. Information Processing Letters, 80(2):97-104, 2001. Google Scholar
  4. Sanjoy Baruah. Feasibility analysis of preemptive real-time systems upon heterogeneous multiprocessor platforms. In Proceedings of the 25th Real-Time Systems Symposium, RTSS'04, pages 37-46. IEEE, 2004. Google Scholar
  5. Sanjoy Baruah and Alan Burns. Sustainable scheduling analysis. In Proceedings of the 27th Real-Time Systems Symposium, RTSS'06, pages 159-168. IEEE, 2006. Google Scholar
  6. Alan Burns and Sanjoy Baruah. Sustainability in real-time scheduling. Journal of Computing Science and Engineering, 2(1):74-97, 2008. Google Scholar
  7. 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'16, pages 273-284. IEEE, 2016. Google Scholar
  8. Jian-Jia Chen, Geoffrey Nelissen, Wen-Hung Huang, Maolin Yang, Björn Brandenburg, Konstantinos Bletsas, Cong Liu, Pascal Richard, Frédéric Ridouard, Neil Audsley, Raj Rajkumar, and Dionisio de Niz. Many suspensions, many problems: A review of self-suspending tasks in real-time systems. Technical Report 854, Department of Computer Science, TU Dortmund, 2016. Google Scholar
  9. Sudarshan K. Dhall and C. L. Liu. On a real-time scheduling problem. Operations Research, 26(1):127-140, 1978. Google Scholar
  10. Rhan Ha. Validating Timing Constraints in Multiprocessor and Distributed Systems. PhD thesis, University of Illinois at Urbana-Champaign, 1995. Google Scholar
  11. Rhan Ha and Jane WS Liu. Validating timing constraints in multiprocessor and distributed real-time systems. In Proceedings of the 14th International Conference on Distributed Computing Systems, ICDCS'94, pages 162-171. IEEE, 1994. Google Scholar
  12. In-Guk Kim, Kyung-Hee Choi, Seung-Kyu Park, Dong-Yoon Kim, and Man-Pyo Hong. Real-time scheduling of tasks that contain the external blocking intervals. In Proceedings of the 2nd International Workshop on Real-Time Computing Systems and Applications, RTCSA'95, pages 54-59. IEEE, 1995. Google Scholar
  13. Chung Laung Liu and James W Layland. Scheduling algorithms for multiprogramming in a hard-real-time environment. Journal of the ACM, 20(1):46-61, 1973. Google Scholar
  14. Aloysius Ka-Lau Mok. Fundamental design problems of distributed systems for the hard-real-time environment. PhD thesis, Massachusetts Institute of Technology, 1983. Google Scholar
  15. \prosa - Weak Sustainability. Supplemental material and formal proofs, URL: http://prosa.mpi-sws.org/releases/sustainability.
  16. Ragunathan Rajkumar. Dealing with suspending periodic tasks. IBM Thomas J. Watson Research Center, 1991. Google Scholar
  17. Dongkun Shin and Jihong Kim. A profile-based energy-efficient intra-task voltage scheduling algorithm for hard real-time applications. In Proceedings of the 2001 International Symposium on Low Power Electronics and Design, pages 271-274. ACM/IEEE, 2001. 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