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.

Probabilistic real-time guarantees: There is life beyond the i.i.d. assumption (outstanding paper)

Abeni, Luca;
2017-01-01

Abstract

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.
2017
9781509052691
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11382/518781
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 11
social impact