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

Back to Research

Last modified: 2023-10-04 09:28:20 +0200