Bringing Probabilistic Real-Time Guarantees to the Real World

Stochastic analysis of real-time systems has received a remarkable attention in the past few years. In general, this analysis has been mainly focused on sets of applications competing for a shared CPU and assuming independence in the computation and inter-arrival times of the jobs composing the tasks. However, for a large class of modern real-time applications, this assumption cannot be considered realistic. Indeed, this type of applications exhibit important variations in the computation time, making the stochastic analysis not accurate enough to provide precise and tight probabilistic guarantees. Fortunately, for such applications we have verified that the computation time is more faithfully described by a Markov model. Hence, we propose a procedure 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. Additionally, we show how to adapt probabilistic guarantees to a Markovian computation time. Performed over a large set of both synthetic and real robotic applications, our experimental results reveal a very good match between the theoretical findings and the ones obtained experimentally. Finally, the estimation procedure and the stochastic analysis method are integrated into the PRObabilistic deSign of Real--Time Systems (PROSIT) framework