Search Results

Documents authored by Ekberg, Pontus

Document
DOI: 10.4230/LIPIcs.ECRTS.2023.2
Towards Efficient Explainability of Schedulability Properties in Real-Time Systems

Authors: Sanjoy Baruah and Pontus Ekberg

Published in: LIPIcs, Volume 262, 35th Euromicro Conference on Real-Time Systems (ECRTS 2023)

Abstract
The notion of efficient explainability was recently introduced in the context of hard-real-time scheduling: a claim that a real-time system is schedulable (i.e., that it will always meet all deadlines during run-time) is defined to be efficiently explainable if there is a proof of such schedulability that can be verified by a polynomial-time algorithm. We further explore this notion by (i) classifying a variety of common schedulability analysis problems according to whether they are efficiently explainable or not; and (ii) developing strategies for dealing with those determined to not be efficiently schedulable, primarily by identifying practically meaningful sub-problems that are efficiently explainable.
Cite as

Sanjoy Baruah and Pontus Ekberg. Towards Efficient Explainability of Schedulability Properties in Real-Time Systems. In 35th Euromicro Conference on Real-Time Systems (ECRTS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 262, pp. 2:1-2:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{baruah_et_al:LIPIcs.ECRTS.2023.2,
  author =	{Baruah, Sanjoy and Ekberg, Pontus},
  title =	{{Towards Efficient Explainability of Schedulability Properties in Real-Time Systems}},
  booktitle =	{35th Euromicro Conference on Real-Time Systems (ECRTS 2023)},
  pages =	{2:1--2:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-280-8},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{262},
  editor =	{Papadopoulos, Alessandro V.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2023.2},
  URN =		{urn:nbn:de:0030-drops-180313},
  doi =		{10.4230/LIPIcs.ECRTS.2023.2},
  annote =	{Keywords: Recurrent Task Systems, Uniprocessor and Multiprocessor Schedulability, Verification, Explanation, Computational Complexity, Approximation Schemes}
}
Document
DOI: 10.4230/LIPIcs.ECRTS.2021.9
Graceful Degradation in Semi-Clairvoyant Scheduling

Authors: Sanjoy Baruah and Pontus Ekberg

Published in: LIPIcs, Volume 196, 33rd Euromicro Conference on Real-Time Systems (ECRTS 2021)

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

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)

Copy BibTex To Clipboard

@InProceedings{baruah_et_al:LIPIcs.ECRTS.2021.9,
  author =	{Baruah, Sanjoy and Ekberg, Pontus},
  title =	{{Graceful Degradation in Semi-Clairvoyant Scheduling}},
  booktitle =	{33rd Euromicro Conference on Real-Time Systems (ECRTS 2021)},
  pages =	{9:1--9:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-192-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{196},
  editor =	{Brandenburg, Bj\"{o}rn B.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2021.9},
  URN =		{urn:nbn:de:0030-drops-139404},
  doi =		{10.4230/LIPIcs.ECRTS.2021.9},
  annote =	{Keywords: Mixed criticality, semi-clairvoyance, graceful degradation}
}
Document
Artifact
DOI: 10.4230/DARTS.5.1.1
Dual Priority Scheduling is Not Optimal (Artifact)

Authors: Pontus Ekberg

Published in: DARTS, Volume 5, Issue 1, Special Issue of the 31st Euromicro Conference on Real-Time Systems (ECRTS 2019)

Abstract
In dual priority scheduling, periodic tasks are executed in a fixed-priority manner, but each job has two phases with different priorities. The second phase is entered after a fixed amount of time has passed since the release of the job, at which point the job changes its priority. Dual priority scheduling was introduced by Burns and Wellings in 1993 and was shown to successfully schedule many task sets that are not schedulable with ordinary (single) fixed-priority scheduling. Burns and Wellings conjectured that dual priority scheduling is an optimal scheduling algorithm for synchronous periodic tasks with implicit deadlines on preemptive uniprocessors. The related article presents counterexamples to this conjecture, and to some related conjectures that have since been stated. This artifact verifies the counterexamples by means of exhaustive simulations of vast numbers of configurations.
Cite as

Pontus Ekberg. Dual Priority Scheduling is Not Optimal (Artifact). In Special Issue of the 31st Euromicro Conference on Real-Time Systems (ECRTS 2019). Dagstuhl Artifacts Series (DARTS), Volume 5, Issue 1, pp. 1:1-1:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@Article{ekberg:DARTS.5.1.1,
  author =	{Ekberg, Pontus},
  title =	{{Dual Priority Scheduling is Not Optimal}},
  pages =	{1:1--1:2},
  journal =	{Dagstuhl Artifacts Series},
  ISSN =	{2509-8195},
  year =	{2019},
  volume =	{5},
  number =	{1},
  editor =	{Ekberg, Pontus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DARTS.5.1.1},
  URN =		{urn:nbn:de:0030-drops-107293},
  doi =		{10.4230/DARTS.5.1.1},
  annote =	{Keywords: Scheduling, real time systems, dual priority}
}
Document
DOI: 10.4230/LIPIcs.ECRTS.2019.14
Dual Priority Scheduling is Not Optimal

Authors: Pontus Ekberg

Published in: LIPIcs, Volume 133, 31st Euromicro Conference on Real-Time Systems (ECRTS 2019)

Abstract
In dual priority scheduling, periodic tasks are executed in a fixed-priority manner, but each job has two phases with different priorities. The second phase is entered after a fixed amount of time has passed since the release of the job, at which point the job changes its priority. Dual priority scheduling was introduced by Burns and Wellings in 1993 and was shown to successfully schedule many task sets that are not schedulable with ordinary (single) fixed-priority scheduling. Burns and Wellings conjectured that dual priority scheduling is an optimal scheduling algorithm for synchronous periodic tasks with implicit deadlines on preemptive uniprocessors. We demonstrate the falsity of this conjecture, as well as of some related conjectures that have since been stated. This is achieved by means of computer-verified counterexamples.
Cite as

Pontus Ekberg. Dual Priority Scheduling is Not Optimal. In 31st Euromicro Conference on Real-Time Systems (ECRTS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 133, pp. 14:1-14:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{ekberg:LIPIcs.ECRTS.2019.14,
  author =	{Ekberg, Pontus},
  title =	{{Dual Priority Scheduling is Not Optimal}},
  booktitle =	{31st Euromicro Conference on Real-Time Systems (ECRTS 2019)},
  pages =	{14:1--14:9},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-110-8},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{133},
  editor =	{Quinton, Sophie},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2019.14},
  URN =		{urn:nbn:de:0030-drops-107519},
  doi =		{10.4230/LIPIcs.ECRTS.2019.14},
  annote =	{Keywords: Scheduling, real time systems, dual priority}
}
Document
DOI: 10.4230/LIPIcs.ECRTS.2017.8
Applying Real-Time Scheduling Theory to the Synchronous Data Flow Model of Computation

Authors: Abhishek Singh, Pontus Ekberg, and Sanjoy Baruah

Published in: LIPIcs, Volume 76, 29th Euromicro Conference on Real-Time Systems (ECRTS 2017)

Abstract
Schedulability analysis techniques that are well understood within the real-time scheduling community are applied to the analysis of recurrent real-time workloads that are modeled using the synchronous data-flow graph (SDFG) model. An enhancement to the standard SDFG model is proposed, that permits the specification of a real-time latency constraint between a specified input and a specified output of an SDFG. A technique is derived for transforming such an enhanced SDFG to a collection of traditional 3-parameter sporadic tasks, thereby allowing for the analysis of systems of SDFG tasks using the methods and algorithms that have previously been developed within the real-time scheduling community for the analysis of systems of such sporadic tasks. The applicability of this approach is illustrated by applying prior results from real-time scheduling theory to construct an exact preemptive uniprocessor schedulability test for collections of recurrent processes that are each represented using the enhanced SDFG model.
Cite as

Abhishek Singh, Pontus Ekberg, and Sanjoy Baruah. Applying Real-Time Scheduling Theory to the Synchronous Data Flow Model of Computation. In 29th Euromicro Conference on Real-Time Systems (ECRTS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 76, pp. 8:1-8:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{singh_et_al:LIPIcs.ECRTS.2017.8,
  author =	{Singh, Abhishek and Ekberg, Pontus and Baruah, Sanjoy},
  title =	{{Applying Real-Time Scheduling Theory to the Synchronous Data Flow Model of Computation}},
  booktitle =	{29th Euromicro Conference on Real-Time Systems (ECRTS 2017)},
  pages =	{8:1--8:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-037-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{76},
  editor =	{Bertogna, Marko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2017.8},
  URN =		{urn:nbn:de:0030-drops-71517},
  doi =		{10.4230/LIPIcs.ECRTS.2017.8},
  annote =	{Keywords: Real-Time Systems, Synchronous Dataflow (SDF), Hard Real-Time Streaming Dataflow Applications, Algorithms}
}
Document
DOI: 10.4230/LIPIcs.ECRTS.2017.11
Refinement of Workload Models for Engine Controllers by State Space Partitioning

Authors: Morteza Mohaqeqi, Jakaria Abdullah, Pontus Ekberg, and Wang Yi

Published in: LIPIcs, Volume 76, 29th Euromicro Conference on Real-Time Systems (ECRTS 2017)

Abstract
We study an engine control application where the behavior of engine controllers depends on the engine's rotational speed. For efficient and precise timing analysis, we use the Digraph Real-Time (DRT) task model to specify the workload of control tasks where we employ optimal control theory to faithfully calculate the respective minimum inter-release times. We show how DRT models can be refined by finer grained partitioning of the state space of the engine up to a model which enables an exact timing analysis. Compared to previously proposed methods which are either unsafe or pessimistic, our work provides both abstract and tight characterizations of the corresponding workload.
Cite as

Morteza Mohaqeqi, Jakaria Abdullah, Pontus Ekberg, and Wang Yi. Refinement of Workload Models for Engine Controllers by State Space Partitioning. In 29th Euromicro Conference on Real-Time Systems (ECRTS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 76, pp. 11:1-11:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{mohaqeqi_et_al:LIPIcs.ECRTS.2017.11,
  author =	{Mohaqeqi, Morteza and Abdullah, Jakaria and Ekberg, Pontus and Yi, Wang},
  title =	{{Refinement of Workload Models for Engine Controllers by State Space Partitioning}},
  booktitle =	{29th Euromicro Conference on Real-Time Systems (ECRTS 2017)},
  pages =	{11:1--11:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-037-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{76},
  editor =	{Bertogna, Marko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2017.11},
  URN =		{urn:nbn:de:0030-drops-71598},
  doi =		{10.4230/LIPIcs.ECRTS.2017.11},
  annote =	{Keywords: Engine Control Tasks, Schedulability Analysis, Minimum-Time Problem, DRT Task Model}
}
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