DROPS

Volume

LIPIcs, Volume 196

33rd Euromicro Conference on Real-Time Systems (ECRTS 2021)

ECRTS 2021, July 5-9, 2021, Virtual Conference

Editors: Björn B. Brandenburg

Document

Artifact

DOI: 10.4230/DARTS.8.1.7

Foundational Response-Time Analysis as Explainable Evidence of Timeliness (Artifact)

Authors: Marco Maida, Sergey Bozhko, and Björn B. Brandenburg

Published in: DARTS, Volume 8, Issue 1, Special Issue of the 34th Euromicro Conference on Real-Time Systems (ECRTS 2022)

Abstract

This artifact provides the means to validate and reproduce the results of the associated paper “Foundational Response-Time Analysis as Explainable Evidence of Timeliness”. The artifact demonstrates how to (i) generate task sets needed to run the experiments, (ii) prepare and run POET on the generated input, (iii) plot the figures presented in the paper, and (iv) visually inspect the generated certificates.

Cite as

Marco Maida, Sergey Bozhko, and Björn B. Brandenburg. Foundational Response-Time Analysis as Explainable Evidence of Timeliness (Artifact). In Special Issue of the 34th Euromicro Conference on Real-Time Systems (ECRTS 2022). Dagstuhl Artifacts Series (DARTS), Volume 8, Issue 1, pp. 7:1-7:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@Article{maida_et_al:DARTS.8.1.7,
  author =	{Maida, Marco and Bozhko, Sergey and Brandenburg, Bj\"{o}rn B.},
  title =	{{Foundational Response-Time Analysis as Explainable Evidence of Timeliness (Artifact)}},
  pages =	{7:1--7:2},
  journal =	{Dagstuhl Artifacts Series},
  ISSN =	{2509-8195},
  year =	{2022},
  volume =	{8},
  number =	{1},
  editor =	{Maida, Marco and Bozhko, Sergey and Brandenburg, Bj\"{o}rn B.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DARTS.8.1.7},
  URN =		{urn:nbn:de:0030-drops-165038},
  doi =		{10.4230/DARTS.8.1.7},
  annote =	{Keywords: hard real-time systems, response-time analysis, uniprocessor, Coq, Prosa, fixed priority, EDF, preemptive, non-preemptive, verification}
}

Document

DOI: 10.4230/LIPIcs.ECRTS.2022.19

Foundational Response-Time Analysis as Explainable Evidence of Timeliness

Authors: Marco Maida, Sergey Bozhko, and Björn B. Brandenburg

Published in: LIPIcs, Volume 231, 34th Euromicro Conference on Real-Time Systems (ECRTS 2022)

Abstract

The paper introduces foundational response-time analysis (RTA) as a means to produce strong and independently checkable evidence of temporal correctness. In a foundational RTA, each response-time bound calculated comes with an auto-generated certificate of correctness - a short and human-inspectable sequence of machine-checked proofs that formally show the claimed bound to hold. In other words, a foundational RTA yields explainable results that can be independently verified (e.g., by a certification authority) in a rigorous manner (with an automated proof checker). Consequently, the analysis tool itself does not need to be verified nor trusted. As a proof of concept, the paper presents POET, the first foundational RTA tool. POET generates certificates based on Prosa, the to-date largest verified framework for schedulability analysis, which is based on Coq. The trusted computing base is hence reduced to the Coq proof checker and its dependencies. POET currently supports two scheduling policies (earliest-deadline-first, fixed-priority), two preemption models (fully preemptive, fully non-preemptive), arbitrary deadlines, periodic and sporadic tasks, and tasks characterized by arbitrary arrival curves. The paper describes the challenges inherent in the development of a foundational RTA tool, discusses key design choices, and reports on its scalability.

Cite as

Marco Maida, Sergey Bozhko, and Björn B. Brandenburg. Foundational Response-Time Analysis as Explainable Evidence of Timeliness. In 34th Euromicro Conference on Real-Time Systems (ECRTS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 231, pp. 19:1-19:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{maida_et_al:LIPIcs.ECRTS.2022.19,
  author =	{Maida, Marco and Bozhko, Sergey and Brandenburg, Bj\"{o}rn B.},
  title =	{{Foundational Response-Time Analysis as Explainable Evidence of Timeliness}},
  booktitle =	{34th Euromicro Conference on Real-Time Systems (ECRTS 2022)},
  pages =	{19:1--19:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-239-6},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{231},
  editor =	{Maggio, Martina},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2022.19},
  URN =		{urn:nbn:de:0030-drops-163363},
  doi =		{10.4230/LIPIcs.ECRTS.2022.19},
  annote =	{Keywords: hard real-time systems, response-time analysis, uniprocessor, Coq, Prosa, fixed priority, EDF, preemptive, non-preemptive, verification}
}

Document

Complete Volume

DOI: 10.4230/LIPIcs.ECRTS.2021

LIPIcs, Volume 196, ECRTS 2021, Complete Volume

Authors: Björn B. Brandenburg

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

Abstract

LIPIcs, Volume 196, ECRTS 2021, Complete Volume

Cite as

33rd Euromicro Conference on Real-Time Systems (ECRTS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 196, pp. 1-370, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@Proceedings{brandenburg:LIPIcs.ECRTS.2021,
  title =	{{LIPIcs, Volume 196, ECRTS 2021, Complete Volume}},
  booktitle =	{33rd Euromicro Conference on Real-Time Systems (ECRTS 2021)},
  pages =	{1--370},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2021},
  URN =		{urn:nbn:de:0030-drops-139309},
  doi =		{10.4230/LIPIcs.ECRTS.2021},
  annote =	{Keywords: LIPIcs, Volume 196, ECRTS 2021, Complete Volume}
}

Document

Front Matter

DOI: 10.4230/LIPIcs.ECRTS.2021.0

Front Matter, Table of Contents, Preface, Conference Organization

Authors: Björn B. Brandenburg

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

Abstract

Front Matter, Table of Contents, Preface, Conference Organization

Cite as

33rd Euromicro Conference on Real-Time Systems (ECRTS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 196, pp. 0:i-0:xii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{brandenburg:LIPIcs.ECRTS.2021.0,
  author =	{Brandenburg, Bj\"{o}rn B.},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{33rd Euromicro Conference on Real-Time Systems (ECRTS 2021)},
  pages =	{0:i--0:xii},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2021.0},
  URN =		{urn:nbn:de:0030-drops-139317},
  doi =		{10.4230/LIPIcs.ECRTS.2021.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}

Document

Artifact

DOI: 10.4230/DARTS.6.1.3

Abstract Response-Time Analysis: A Formal Foundation for the Busy-Window Principle (Artifact)

Authors: Sergey Bozhko and Björn B. Brandenburg

Published in: DARTS, Volume 6, Issue 1, Special Issue of the 32nd Euromicro Conference on Real-Time Systems (ECRTS 2020)

Abstract

This artifact provides the means to validate and reproduce the results of the associated paper "Abstract Response-Time Analysis: A Formal Foundation for the Busy-Window Principle". In this artifact we demonstrate how to compile the source code and automatically check the proofs of each theorem. We also provide references to all key results claimed to be proven in the paper (including Abstract RTA and all eight instantiations), so that readers may confirm that no proofs have been omitted.

Cite as

Sergey Bozhko and Björn B. Brandenburg. Abstract Response-Time Analysis: A Formal Foundation for the Busy-Window Principle (Artifact). In Special Issue of the 32nd Euromicro Conference on Real-Time Systems (ECRTS 2020). Dagstuhl Artifacts Series (DARTS), Volume 6, Issue 1, pp. 3:1-3:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@Article{bozhko_et_al:DARTS.6.1.3,
  author =	{Bozhko, Sergey and Brandenburg, Bj\"{o}rn B.},
  title =	{{Abstract Response-Time Analysis: A Formal Foundation for the Busy-Window Principle (Artifact)}},
  pages =	{3:1--3:2},
  journal =	{Dagstuhl Artifacts Series},
  ISSN =	{2509-8195},
  year =	{2020},
  volume =	{6},
  number =	{1},
  editor =	{Bozhko, Sergey and Brandenburg, Bj\"{o}rn B.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DARTS.6.1.3},
  URN =		{urn:nbn:de:0030-drops-123930},
  doi =		{10.4230/DARTS.6.1.3},
  annote =	{Keywords: hard real-time systems, response-time analysis, uniprocessor, busy window, fixed priority, EDF, verification, Coq, Prosa, preemptive, non-preemptive, limited-preemptive}
}

Document

DOI: 10.4230/LIPIcs.ECRTS.2020.6

Nested, but Separate: Isolating Unrelated Critical Sections in Real-Time Nested Locking

Authors: James Robb and Björn B. Brandenburg

Published in: LIPIcs, Volume 165, 32nd Euromicro Conference on Real-Time Systems (ECRTS 2020)

Abstract

Prior work has produced multiprocessor real-time locking protocols that ensure asymptotically optimal bounds on priority inversion, that support fine-grained nesting of critical sections, or that are independence-preserving under clustered scheduling. However, while several protocols manage to come with two out of these three desirable features, no protocol to date accomplishes all three. Motivated by this gap in capabilities, this paper introduces the Group Independence-Preserving Protocol (GIPP), the first protocol to support fine-grained nested locking, guarantee a notion of independence preservation for fine-grained nested locking, and ensure asymptotically optimal priority-inversion bounds. As a stepping stone, this paper further presents the Clustered k-Exclusion Independence-Preserving Protocol (CKIP), the first asymptotically optimal independence-preserving k-exclusion lock for clustered scheduling. The GIPP and the CKIP rely on allocation inheritance (a.k.a. migratory priority inheritance) as a key mechanism to accomplish independence preservation.

Cite as

James Robb and Björn B. Brandenburg. Nested, but Separate: Isolating Unrelated Critical Sections in Real-Time Nested Locking. In 32nd Euromicro Conference on Real-Time Systems (ECRTS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 165, pp. 6:1-6:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{robb_et_al:LIPIcs.ECRTS.2020.6,
  author =	{Robb, James and Brandenburg, Bj\"{o}rn B.},
  title =	{{Nested, but Separate: Isolating Unrelated Critical Sections in Real-Time Nested Locking}},
  booktitle =	{32nd Euromicro Conference on Real-Time Systems (ECRTS 2020)},
  pages =	{6:1--6:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-152-8},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{165},
  editor =	{V\"{o}lp, Marcus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2020.6},
  URN =		{urn:nbn:de:0030-drops-123691},
  doi =		{10.4230/LIPIcs.ECRTS.2020.6},
  annote =	{Keywords: multiprocessor real-time locking, nested locking, independence preservation, suspension-oblivious analysis, priority inversion, asymptotically optimal blocking, RNLP, OMIP}
}

Document

DOI: 10.4230/LIPIcs.ECRTS.2020.22

Abstract Response-Time Analysis: A Formal Foundation for the Busy-Window Principle

Authors: Sergey Bozhko and Björn B. Brandenburg

Published in: LIPIcs, Volume 165, 32nd Euromicro Conference on Real-Time Systems (ECRTS 2020)

Abstract

This paper introduces the first general and rigorous formalization of the classic busy-window principle for uniprocessors. The essence of the principle is identified as a minimal set of generic, high-level hypotheses that allow for a unified and general abstract response-time analysis, which is independent of specific scheduling policies, workload models, and preemption policy details. From this abstract core, the paper shows how to obtain concrete analysis instantiations for specific uniprocessor schedulers via a sequence of refinement steps, and provides formally verified response-time bounds for eight common schedulers and workloads, including the widely used fixed-priority (FP) and earliest-deadline first (EDF) scheduling policies in the context of fully, limited-, and non-preemptive sporadic tasks. All definitions and proofs in this paper have been mechanized and verified with the Coq proof assistant, and in fact form the common core and foundation for verified response-time analyses in the Prosa open-source framework for formally proven schedulability analyses.

Cite as

Sergey Bozhko and Björn B. Brandenburg. Abstract Response-Time Analysis: A Formal Foundation for the Busy-Window Principle. In 32nd Euromicro Conference on Real-Time Systems (ECRTS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 165, pp. 22:1-22:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{bozhko_et_al:LIPIcs.ECRTS.2020.22,
  author =	{Bozhko, Sergey and Brandenburg, Bj\"{o}rn B.},
  title =	{{Abstract Response-Time Analysis: A Formal Foundation for the Busy-Window Principle}},
  booktitle =	{32nd Euromicro Conference on Real-Time Systems (ECRTS 2020)},
  pages =	{22:1--22:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-152-8},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{165},
  editor =	{V\"{o}lp, Marcus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2020.22},
  URN =		{urn:nbn:de:0030-drops-123850},
  doi =		{10.4230/LIPIcs.ECRTS.2020.22},
  annote =	{Keywords: hard real-time systems, response-time analysis, uniprocessor, busy window, fixed priority, EDF, verification, Coq, Prosa, preemptive, non-preemptive, limited-preemptive}
}

Document

Artifact

DOI: 10.4230/DARTS.5.1.5

Response-Time Analysis of ROS 2 Processing Chains Under Reservation-Based Scheduling (Artifact)

Authors: Daniel Casini, Tobias Blaß, Ingo Lütkebohle, and Björn B. Brandenburg

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

Abstract

This artifact provides the means to validate and reproduce the results of the associated paper "Response-Time Analysis of ROS 2 Processing Chains under Reservation-Based Scheduling." It consists of two independent components. First, it contains a model validation component that validates the paper’s claims about the ROS 2 executor’s callback scheduling. Second, it contains the source code for the paper’s case study, i.e., an implementation of the proposed response-time analysis and a model of the move_base navigation stack.

Cite as

Daniel Casini, Tobias Blaß, Ingo Lütkebohle, and Björn B. Brandenburg. Response-Time Analysis of ROS 2 Processing Chains Under Reservation-Based Scheduling (Artifact). In Special Issue of the 31st Euromicro Conference on Real-Time Systems (ECRTS 2019). Dagstuhl Artifacts Series (DARTS), Volume 5, Issue 1, pp. 5:1-5:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@Article{casini_et_al:DARTS.5.1.5,
  author =	{Casini, Daniel and Bla{\ss}, Tobias and L\"{u}tkebohle, Ingo and Brandenburg, Bj\"{o}rn B.},
  title =	{{Response-Time Analysis of ROS 2 Processing Chains Under Reservation-Based Scheduling}},
  pages =	{5:1--5:2},
  journal =	{Dagstuhl Artifacts Series},
  ISSN =	{2509-8195},
  year =	{2019},
  volume =	{5},
  number =	{1},
  editor =	{Casini, Daniel and Bla{\ss}, Tobias and L\"{u}tkebohle, Ingo and Brandenburg, Bj\"{o}rn B.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DARTS.5.1.5},
  URN =		{urn:nbn:de:0030-drops-107330},
  doi =		{10.4230/DARTS.5.1.5},
  annote =	{Keywords: ROS, real-time systems, response-time analysis, robotics, resource reservation}
}

Document

DOI: 10.4230/LIPIcs.ECRTS.2019.6

Response-Time Analysis of ROS 2 Processing Chains Under Reservation-Based Scheduling

Authors: Daniel Casini, Tobias Blaß, Ingo Lütkebohle, and Björn B. Brandenburg

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

Abstract

Bounding the end-to-end latency of processing chains in distributed real-time systems is a well-studied problem, relevant in multiple industrial fields, such as automotive systems and robotics. Nonetheless, to date, only little attention has been given to the study of the impact that specific frameworks and implementation choices have on real-time performance. This paper proposes a scheduling model and a response-time analysis for ROS 2 (specifically, version "Crystal Clemmys" released in December 2018), a popular framework for the rapid prototyping, development, and deployment of robotics applications with thousands of professional users around the world. The purpose of this paper is threefold. Firstly, it is aimed at providing to robotic engineers a practical analysis to bound the worst-case response times of their applications. Secondly, it shines a light on current ROS 2 implementation choices from a real-time perspective. Finally, it presents a realistic real-time scheduling model, which provides an opportunity for future impact on the robotics industry.

Cite as

Daniel Casini, Tobias Blaß, Ingo Lütkebohle, and Björn B. Brandenburg. Response-Time Analysis of ROS 2 Processing Chains Under Reservation-Based Scheduling. In 31st Euromicro Conference on Real-Time Systems (ECRTS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 133, pp. 6:1-6:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{casini_et_al:LIPIcs.ECRTS.2019.6,
  author =	{Casini, Daniel and Bla{\ss}, Tobias and L\"{u}tkebohle, Ingo and Brandenburg, Bj\"{o}rn B.},
  title =	{{Response-Time Analysis of ROS 2 Processing Chains Under Reservation-Based Scheduling}},
  booktitle =	{31st Euromicro Conference on Real-Time Systems (ECRTS 2019)},
  pages =	{6:1--6:23},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2019.6},
  URN =		{urn:nbn:de:0030-drops-107431},
  doi =		{10.4230/LIPIcs.ECRTS.2019.6},
  annote =	{Keywords: ROS, real-time systems, response-time analysis, robotics, resource reservation}
}

Document

DOI: 10.4230/LIPIcs.ECRTS.2019.9

From Iteration to System Failure: Characterizing the FITness of Periodic Weakly-Hard Systems

Authors: Arpan Gujarati, Mitra Nasri, Rupak Majumdar, and Björn B. Brandenburg

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

Abstract

Estimating metrics such as the Mean Time To Failure (MTTF) or its inverse, the Failures-In-Time (FIT), is a central problem in reliability estimation of safety-critical systems. To this end, prior work in the real-time and embedded systems community has focused on bounding the probability of failures in a single iteration of the control loop, resulting in, for example, the worst-case probability of a message transmission error due to electromagnetic interference, or an upper bound on the probability of a skipped or an incorrect actuation. However, periodic systems, which can be found at the core of most safety-critical real-time systems, are routinely designed to be robust to a single fault or to occasional failures (case in point, control applications are usually robust to a few skipped or misbehaving control loop iterations). Thus, obtaining long-run reliability metrics like MTTF and FIT from single iteration estimates by calculating the time to first fault can be quite pessimistic. Instead, overall system failures for such systems are better characterized using multi-state models such as weakly-hard constraints. In this paper, we describe and empirically evaluate three orthogonal approaches, PMC, Mart, and SAp, for the sound estimation of system’s MTTF, starting from a periodic stochastic model characterizing the failure in a single iteration of a periodic system, and using weakly-hard constraints as a measure of system robustness. PMC and Mart are exact analyses based on Markov chain analysis and martingale theory, respectively, whereas SAp is a sound approximation based on numerical analysis. We evaluate these techniques empirically in terms of their accuracy and numerical precision, their expressiveness for different definitions of weakly-hard constraints, and their space and time complexities, which affect their scalability and applicability in different regions of the space of weakly-hard constraints.

Cite as

Arpan Gujarati, Mitra Nasri, Rupak Majumdar, and Björn B. Brandenburg. From Iteration to System Failure: Characterizing the FITness of Periodic Weakly-Hard Systems. In 31st Euromicro Conference on Real-Time Systems (ECRTS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 133, pp. 9:1-9:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{gujarati_et_al:LIPIcs.ECRTS.2019.9,
  author =	{Gujarati, Arpan and Nasri, Mitra and Majumdar, Rupak and Brandenburg, Bj\"{o}rn B.},
  title =	{{From Iteration to System Failure: Characterizing the FITness of Periodic Weakly-Hard Systems}},
  booktitle =	{31st Euromicro Conference on Real-Time Systems (ECRTS 2019)},
  pages =	{9:1--9:23},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2019.9},
  URN =		{urn:nbn:de:0030-drops-107468},
  doi =		{10.4230/LIPIcs.ECRTS.2019.9},
  annote =	{Keywords: reliability analysis, MTTF/FIT analysis, weakly-hard constraints}
}

Document

DOI: 10.4230/LIPIcs.ECRTS.2019.21

Response-Time Analysis of Limited-Preemptive Parallel DAG Tasks Under Global Scheduling

Authors: Mitra Nasri, Geoffrey Nelissen, and Björn B. Brandenburg

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

Abstract

Most recurrent real-time applications can be modeled as a set of sequential code segments (or blocks) that must be (repeatedly) executed in a specific order. This paper provides a schedulability analysis for such systems modeled as a set of parallel DAG tasks executed under any limited-preemptive global job-level fixed priority scheduling policy. More precisely, we derive response-time bounds for a set of jobs subject to precedence constraints, release jitter, and execution-time uncertainty, which enables support for a wide variety of parallel, limited-preemptive execution models (e.g., periodic DAG tasks, transactional tasks, generalized multi-frame tasks, etc.). Our analysis explores the space of all possible schedules using a powerful new state abstraction and state-pruning technique. An empirical evaluation shows the analysis to identify between 10 to 90 percentage points more schedulable task sets than the state-of-the-art schedulability test for limited-preemptive sporadic DAG tasks. It scales to systems of up to 64 cores with 20 DAG tasks. Moreover, while our analysis is almost as accurate as the state-of-the-art exact schedulability test based on model checking (for sequential non-preemptive tasks), it is three orders of magnitude faster and hence capable of analyzing task sets with more than 60 tasks on 8 cores in a few seconds.

Cite as

Mitra Nasri, Geoffrey Nelissen, and Björn B. Brandenburg. Response-Time Analysis of Limited-Preemptive Parallel DAG Tasks Under Global Scheduling. In 31st Euromicro Conference on Real-Time Systems (ECRTS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 133, pp. 21:1-21:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{nasri_et_al:LIPIcs.ECRTS.2019.21,
  author =	{Nasri, Mitra and Nelissen, Geoffrey and Brandenburg, Bj\"{o}rn B.},
  title =	{{Response-Time Analysis of Limited-Preemptive Parallel DAG Tasks Under Global Scheduling}},
  booktitle =	{31st Euromicro Conference on Real-Time Systems (ECRTS 2019)},
  pages =	{21:1--21:23},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2019.21},
  URN =		{urn:nbn:de:0030-drops-107587},
  doi =		{10.4230/LIPIcs.ECRTS.2019.21},
  annote =	{Keywords: parallel DAG tasks, global multiprocessor scheduling, schedulability analysis, non-preemptive jobs, precedence constraints, worst-case response time, OpenMP}
}

Document

DOI: 10.4230/LIPIcs.ECRTS.2018.9

A Response-Time Analysis for Non-Preemptive Job Sets under Global Scheduling

Authors: Mitra Nasri, Geoffrey Nelissen, and Björn B. Brandenburg

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

Abstract

An effective way to increase the timing predictability of multicore platforms is to use non-preemptive scheduling. It reduces preemption and job migration overheads, avoids intra-core cache interference, and improves the accuracy of worst-case execution time (WCET) estimates. However, existing schedulability tests for global non-preemptive multiprocessor scheduling are pessimistic, especially when applied to periodic workloads. This paper reduces this pessimism by introducing a new type of sufficient schedulability analysis that is based on an exploration of the space of possible schedules using concise abstractions and state-pruning techniques. Specifically, we analyze the schedulability of non-preemptive job sets (with bounded release jitter and execution time variation) scheduled by a global job-level fixed-priority (JLFP) scheduling algorithm upon an identical multicore platform. The analysis yields a lower bound on the best-case response-time (BCRT) and an upper bound on the worst-case response time (WCRT) of the jobs. In an empirical evaluation with randomly generated workloads, we show that the method scales to 30 tasks, a hundred thousand jobs (per hyperperiod), and up to 9 cores.

Cite as

Mitra Nasri, Geoffrey Nelissen, and Björn B. Brandenburg. A Response-Time Analysis for Non-Preemptive Job Sets under Global Scheduling. In 30th Euromicro Conference on Real-Time Systems (ECRTS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 106, pp. 9:1-9:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{nasri_et_al:LIPIcs.ECRTS.2018.9,
  author =	{Nasri, Mitra and Nelissen, Geoffrey and Brandenburg, Bj\"{o}rn B.},
  title =	{{A Response-Time Analysis for Non-Preemptive Job Sets under Global Scheduling}},
  booktitle =	{30th Euromicro Conference on Real-Time Systems (ECRTS 2018)},
  pages =	{9:1--9:23},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2018.9},
  URN =		{urn:nbn:de:0030-drops-89941},
  doi =		{10.4230/LIPIcs.ECRTS.2018.9},
  annote =	{Keywords: global multiprocessor scheduling, schedulability analysis, non-preemptive tasks, worst-case response time, best-case response time}
}

Document

DOI: 10.4230/LIPIcs.ECRTS.2018.16

Quantifying the Resiliency of Fail-Operational Real-Time Networked Control Systems

Authors: Arpan Gujarati, Mitra Nasri, and Björn B. Brandenburg

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

Abstract

In time-sensitive, safety-critical systems that must be fail-operational, active replication is commonly used to mitigate transient faults that arise due to electromagnetic interference (EMI). However, designing an effective and well-performing active replication scheme is challenging since replication conflicts with the size, weight, power, and cost constraints of embedded applications. To enable a systematic and rigorous exploration of the resulting tradeoffs, we present an analysis to quantify the resiliency of fail-operational networked control systems against EMI-induced memory corruption, host crashes, and retransmission delays. Since control systems are typically robust to a few failed iterations, e.g., one missed actuation does not crash an inverted pendulum, traditional solutions based on hard real-time assumptions are often too pessimistic. Our analysis reduces this pessimism by modeling a control system's inherent robustness as an (m,k)-firm specification. A case study with an active suspension workload indicates that the analytical bounds closely predict the failure rate estimates obtained through simulation, thereby enabling a meaningful design-space exploration, and also demonstrates the utility of the analysis in identifying non-trivial and non-obvious reliability tradeoffs.

Cite as

Arpan Gujarati, Mitra Nasri, and Björn B. Brandenburg. Quantifying the Resiliency of Fail-Operational Real-Time Networked Control Systems. In 30th Euromicro Conference on Real-Time Systems (ECRTS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 106, pp. 16:1-16:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{gujarati_et_al:LIPIcs.ECRTS.2018.16,
  author =	{Gujarati, Arpan and Nasri, Mitra and Brandenburg, Bj\"{o}rn B.},
  title =	{{Quantifying the Resiliency of Fail-Operational Real-Time Networked Control Systems}},
  booktitle =	{30th Euromicro Conference on Real-Time Systems (ECRTS 2018)},
  pages =	{16:1--16:24},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2018.16},
  URN =		{urn:nbn:de:0030-drops-89884},
  doi =		{10.4230/LIPIcs.ECRTS.2018.16},
  annote =	{Keywords: probabilistic analysis, reliability analysis, networked control systems}
}

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-dev.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}
}

16 Search Results for "Brandenburg, Björn B."

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Thanks for your feedback!

Could not send message