A Markovian model for the computation time of real-time applications

Many real–time applications consist of a cyclic execution of computation activities (jobs) with stochastic computation time. In order to identify the probability that such applications will meet their deadlines, it is crucial to have a model for the random process describing the computation time. In many interesting applications, a Markovian model, in which the system stochastically switches within a discrete set of operating conditions (modes), is apparently a good fit for the actual behaviour of the process. In this paper, we discuss procedures and methods for the collection of samples of the computation time and for the identification of the underlying models based on the theory of hidden Markov models (HMM).