Property-based timing analysis of distributed real-time systems
| dc.contributor.advisor | Chen, Jian-Jia | |
| dc.contributor.author | Günzel, Mario | |
| dc.contributor.referee | Baruah, Sanjoy | |
| dc.date.accepted | 2024-11-11 | |
| dc.date.accessioned | 2024-12-03T13:36:07Z | |
| dc.date.available | 2024-12-03T13:36:07Z | |
| dc.date.issued | 2024 | |
| dc.description.abstract | For real-time systems, timing requirements must be met to avoid catastrophic outcomes. While the behavior of classical real-time systems is already studied extensively in the literature, the trend towards distributed systems raises new challenges. In this dissertation, we focus on the following two challenges: (i) distributed execution of jobs, resulting in self-suspending task behavior, and (ii) interplay of several distributed tasks, requiring to shift the real-time requirements from a single task to a sequence of tasks, the so-called end-to-end latency of cause-effect chains. Although the study of cause-effect chains and self-suspending tasks has led to a series of results, some of them suffer from missing assumptions or use intuitive extension of classical results on real-time systems, resulting in flawed analyses. We tackle this issue by providing careful analysis of self-suspending tasks and cause-effect chains based on fundamental properties of possible evolutions of the system. The dissertation is structured into five main chapters. In Chapter 2, real-time systems and classical task models used in the literature are introduced. In this dissertation, we pursue a fundamental view on real-time systems, starting from possible system evolutions and schedules, and abstracting task properties afterwards. This is different to the typical procedure of defining the task model first and deriving possible schedules based on the task model. Our approach has the benefit that a task can be observed in different abstraction levels without translating the task into a different task model. Furthermore, in Chapter 2, we introduce scheduling algorithms as a systematic approach to derive task schedules from system evolutions based on the information of the task abstraction, and we discuss analytical literature results for the adherence to real-time requirements. Chapter 3 introduces the challenges that arise from distributed systems. The first challenge is the distributed execution of jobs. This is enabled by refining tasks into smaller blocks which can be distributed on different computing elements. The impact of this refinement on the generation of schedules is discussed and different refined task models are presented. One of them, the so-called self-suspending task model, is in focus for this dissertation. The second challenge is the interplay of distributed tasks. More specifically, if a functionality is not described by a single task but by a sequence of task (a so-called cause-effect chain) then the timing requirement must be shifted from the single task to the cause-effect chain. The resulting timing metric for cause-effect chains is the end-to-end latency. Chapter 4 emphasizes the need for careful, property-based analysis. That is, three counterexamples for literature results are provided. Two of them are related to self-suspending tasks, closing the unresolved issues discussed in a review paper on self-suspending tasks in 2019. The third one disproves a basic result for real-time systems in the context of probabilistic setups. Chapter 5 examines self-suspending tasks. Self-suspending tasks can voluntarily suspend their execution. Such behavior can cause timing anomalies, i.e., the worst-case behavior cannot be observed with maximal execution and suspension time. Therefore, self-suspending tasks require careful analysis and treatment. We provide novel analytical approaches for the Worst-Case Response Time (WCRT) of self-suspending tasks under different scheduling algorithms, namely, (i) Task-level Fixed Priority (T-FP), (ii) Earliest-Deadline-First (EDF) and (iii) EDF-Like (EL), all outperforming the state of the art. Furthermore, we present mechanisms to avoid the analytical pessimism that is necessary to tolerate timing anomalies, namely, segment release time enforcement and segment priority modification. Chapter 6 examines cause-effect chains. While for typical task models the real-time requirement is given on the task-level, for cause-effect chains the end-to-end latency is considered. We prove fundamental properties of the end-to-end latency, namely the compositional property and the equivalence of typical metrics. Furthermore, we provide novel analyses of the worst-case and probabilistic end-to-end latency. For the worst-case end-to-end latency, we focus on a property-based approach, uncovering fundamental principles of literature results and using our insights from the fundamental properties to derive novel solutions. For the probabilistic end-to-end latency, we are one of the first to define a metric. Therefore, we focus on potential pitfalls and conduct careful analysis. | en |
| dc.identifier.uri | http://hdl.handle.net/2003/43007 | |
| dc.identifier.uri | http://dx.doi.org/10.17877/DE290R-24840 | |
| dc.language.iso | en | |
| dc.subject | Real-time systems | en |
| dc.subject | Scheduling | en |
| dc.subject | Self-suspension | en |
| dc.subject | End-to-end latency | en |
| dc.subject.ddc | 004 | |
| dc.subject.rswk | Echtzeitsystem | de |
| dc.subject.rswk | Scheduling | de |
| dc.subject.rswk | Latenz | de |
| dc.title | Property-based timing analysis of distributed real-time systems | en |
| dc.type | Text | |
| dc.type.publicationtype | PhDThesis | |
| dcterms.accessRights | open access | |
| eldorado.secondarypublication | false |