PhD Thesis: Anna Friebe
Probabilistic Analysis and Scheduling of Real-Time Systems
| Student | Anna Friebe | |
|---|---|---|
| Advisors |
Thomas Nolte Alessandro V. Papadopoulos Filip Markovic |
|
| Faculty Reviewer | Luca Abeni, Scuola Superiore Sant’Anna, Pisa, Italy | |
| Grading Committee |
Lucia Lo Bello, University of Catania, Catania, Italy Liliana Cucu-Grosjean, INRIA, Paris, France Francisco J. Cazorla, Barcelona Supercomputing Center, Barcelona, Spain Hossein Fotouhi, Mälardalen University, Västerås, Sweden (reserve) |
|
| Defence | Mälardalen University, Västerås, Sweden Room Kappa and Zoom meeting April 29th, 2025 13:00 |
|
| Abstract | In this thesis, probabilistic methods are explored for the analysis and scheduling of real-time systems, where computation times vary significantly. The aim is to enable sufficient timing-related performance while allowing for economic resource provisioning or other average-case objectives. In one line of research, Hidden Markov Models (HMMs) with continuous emission distributions are used to model execution times of periodic tasks. A framework for the identification and validation of such models is presented. Methods are developed for updating model parameters in systems where the execution time behavior changes, and for bounding the deadline miss probability for such periodic tasks in a reservation-based server. For scheduling parallel workload with varying computational demand, a mechanism is proposed for sharing a job queue among several reservation-based servers. The mechanism guarantees executing jobs a certain amount of computational resources prior to their deadline, by enabling job dismissal in overload situations. Another contribution regards parallel synchronous tasks, and the problem of assigning a suitable number of cores to the task, so that the deadline is met while optimizing towards a goal such as minimizing energy consumption. A suitable core assignment is found using a Multi-Armed Bandit (MAB) formulation of the problem, requiring only limited knowledge of the worst-case properties of the task structure. Using derived response time bounds in the MAB formulation reduces the time to convergence and the energy consumption. | |
| Rules and Guidelines |
The PhD procedure summary Rules for Third-cycle Studies at MDH - Chapter 3.1.7 Public Defence of a Thesis |
|
| 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: Efficiently Bounding Deadline Miss Probabilities of Markov Chain Real-Time Tasks . Paper D: Nip It In the Bud - Job Acceptance Multi-Server Paper E: Resource Management for Stochastic Parallel Synchronous Tasks: Bandits to the Rescue |
|
| Publications | Complete list of publications |
Last modified: 2025-04-29 10:17:45 +0200