Lic Thesis: Anna Friebe

Timing and Schedulability Analysis of Real-Time Systems using Hidden Markov Models

Anna pic

Student   Anna Friebe  
Advisors   Thomas Nolte  
    Alessandro V. Papadopoulos  
    Filip Markovic  
Faculty Reviewer   Liliana Cucu-Grosjean, INRIA, Paris, France  
Grading   Petru Eles, Linköping University, Linköping, Sweden  
Committee   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  
    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   The Lic procedure summary  
Guidelines   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   Draft version  
Included   Paper A: Identification and Validation of Markov Models with Continuous Emission Distributions for Execution Times .  
Papers   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: 2022-05-31 21:25:57 +0200