Probabilistic Real-Time Guarantees: There Is Life Beyond the i.i.d. Assumption (Outstanding Paper)

A large class of modern real–time applications exhibits important variations in the computation time and is resilient to occasional deadline misses. In such cases, probabilistic methods, in which the probability of a deadline miss can be guaranteed and related to the scheduling design choices, can be an important tool for system design. Several techniques for probabilistic guarantees exist for the resource reservation scheduler and are based on the assumption that the process describing the application is independent and identically distributed (i.i.d.). In this paper, we consider a particular class of robotic application for which this assumption is not verified. For such applications, we have verified that the computation time is more faithfully described by a Markov model. We propose techniques based on the theory of hidden Markov models to extract the structure of the model from the observation of a number of execution traces of the application. As a second contribution, we show how to adapt probabilistic guarantees to a Markovian computation time. Our experimental results reveal a very good match between the theoretical findings and the experiments.