Lic Thesis: Anna Friebe
Timing and Schedulability Analysis of Real-Time Systems using Hidden Markov Models
| Student | Anna Friebe | |
|---|---|---|
| Advisors | Thomas Nolte Alessandro V. Papadopoulos Filip Markovic |
|
| Faculty Reviewer | Liliana Cucu-Grosjean, INRIA, Paris, France | |
| Grading Committee | Petru Eles, Linköping University, Linköping, Sweden Anton Cervin, Lund University, Lund, Sweden Andreas Ryve, Mälardalen University, Sweden (reserve) |
|
| Defence | Mälardalen University, Västerås, Sweden Room Delta and Zoom meeting (Link will be made public) June 21st, 2022 14:00 |
|
| Abstract | In real-time systems functional requirements are coupled to timing requirements - a specified event needs to occur at the appropriate time. In order to ensure that timing requirements are fulfilled, there are two main approaches, static and measurement-based. The static approach relies on modeling the hardware and software and calculating upper bounds for the timing behavior. On the other hand, measurement-based approaches uses timing data collected from the system to estimate the timing behavior. Usability of static and measurement-based approaches are limited in many modern systems due to increased complexity of hardware and software architectures. Static approaches to timing and schedulability analysis are often infeasible due to the complexity. Measurement-based approaches require that design-time measurements are representative of the timing behavior at runtime, which is problematic to ensure in many cases. Designing systems that guarantee the timing requirements without excessive resource overprovisioning is a challenge. A Hidden Markov Model (HMM) describes a system where the behavior is state-dependent. In this thesis we model the execution time distribution of a periodic task as a HMM where the states are associated with continuous emission distributions. By modeling the execution times in this manner with a limited number of parameters, a step is taken on the path towards tracking and controlling timing properties at runtime. We present a framework for parameter identification of an HMM with Gaussian emission distributions from timing traces, and validation of the identified models. In evaluated cases, the parameterized models are valid in relation to timing traces. For cases where design-time measurements are not representative of the system at runtime, we present a method for online adaptive update of the emission distributions of an HMM. Evaluation with synthetic data shows that the estimate tracks the ground truth distribution. A method for estimating the deadline miss probability for a task with execution times modeled by an HMM with Gaussian emission distributions, in a Constant Bandwidth Server (CBS) is proposed. The method is evaluated with simulation and for a synthetic task with a known Markov Chain structure running on real hardware. |
|
| Rules and Guidelines | The Lic procedure summary Rules for Third-cycle Studies at MDH - Chapter 3.1.7 Public Defence of a Thesis Instructions regarding public defences and licentiate seminars on account of the outbreak of Covid19 (Coronavirus) |
|
| Thesis | Thesis | |
| Included Papers | Paper A: Identification and Validation of Markov Models with Continuous Emission Distributions for Execution Times . Paper B: Adaptive Runtime Estimate of Task Execution Times using Bayesian Modeling . Paper C: Estimating Deadline Miss Probabilities of Continuous-Emission Markov Chain Tasks . |
|
| Publications | Complete list of publications |
Last modified: 2023-10-04 09:28:20 +0200