You are required to read and agree to the below before accessing a full-text version of an article in the IDE article repository.

The full-text document you are about to access is subject to national and international copyright laws. In most cases (but not necessarily all) the consequence is that personal use is allowed given that the copyright owner is duly acknowledged and respected. All other use (typically) require an explicit permission (often in writing) by the copyright owner.

For the reports in this repository we specifically note that

  • the use of articles under IEEE copyright is governed by the IEEE copyright policy (available at
  • the use of articles under ACM copyright is governed by the ACM copyright policy (available at
  • technical reports and other articles issued by M‰lardalen University is free for personal use. For other use, the explicit consent of the authors is required
  • in other cases, please contact the copyright owner for detailed information

By accepting I agree to acknowledge and respect the rights of the copyright owner of the document I am about to access.

If you are in doubt, feel free to contact

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



Publication Type:

Licentiate Thesis


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 use timing data collected from the system to estimate the timing behavior. The usability of static and measurement-based approaches is limited in many modern systems due to the increased complexity of hardware and software architectures. Static approaches to timing and schedulability analysis are often infeasible due to their 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 an 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 toward 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 the 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.


author = {Anna Friebe},
title = {Timing and Schedulability Analysis of Real-Time Systems using Hidden Markov Models},
month = {June},
year = {2022},
url = {}