DROPS

Document

DOI: 10.4230/LIPIcs.ECRTS.2018.26

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

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

Published in: LIPIcs, Volume 106, 30th Euromicro Conference on Real-Time Systems (ECRTS 2018)

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.

Cite as

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)

Copy BibTex To Clipboard

@InProceedings{cerqueira_et_al:LIPIcs.ECRTS.2018.26,
  author =	{Cerqueira, Felipe and Nelissen, Geoffrey and Brandenburg, Bj\"{o}rn B.},
  title =	{{On Strong and Weak Sustainability, with an Application to Self-Suspending Real-Time Tasks}},
  booktitle =	{30th Euromicro Conference on Real-Time Systems (ECRTS 2018)},
  pages =	{26:1--26:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-075-0},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{106},
  editor =	{Altmeyer, Sebastian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2018.26},
  URN =		{urn:nbn:de:0030-drops-89773},
  doi =		{10.4230/LIPIcs.ECRTS.2018.26},
  annote =	{Keywords: real-time scheduling, sustainability, self-suspending tasks, machine-checked proofs}
}

Search Results

Documents authored by Cerqueira, Felipe

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

Abstract

Cite as

Thanks for your feedback!

Could not send message