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) / Bernardo, Villalba; Palopoli, Luigi; Abeni, Luca; Fontanelli, Daniele. - ELETTRONICO. - (2017), pp. 175-186. ((Intervento presentato al convegno RTAS 2017 tenutosi a Pittsburgh, PA, USA nel 18-21 April , 2017 [10.1109/RTAS.2017.18].

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

Bernardo Villalba;Luigi Palopoli;Luca Abeni;Daniele Fontanelli
2017

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.
Proceedings of the 23rd IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS 2017)
Los Alamitos, CA
IEEE Computer Society
978-1-5090-5269-1
Bernardo, Villalba; Palopoli, Luigi; Abeni, Luca; Fontanelli, Daniele
Probabilistic Real-Time Guarantees: There Is Life Beyond the i.i.d. Assumption (Outstanding Paper) / Bernardo, Villalba; Palopoli, Luigi; Abeni, Luca; Fontanelli, Daniele. - ELETTRONICO. - (2017), pp. 175-186. ((Intervento presentato al convegno RTAS 2017 tenutosi a Pittsburgh, PA, USA nel 18-21 April , 2017 [10.1109/RTAS.2017.18].
File in questo prodotto:
File Dimensione Formato  
main.pdf

Solo gestori archivio

Descrizione: Articolo
Tipologia: Versione editoriale (Publisher’s layout)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 4.25 MB
Formato Adobe PDF
4.25 MB Adobe PDF   Visualizza/Apri

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: http://hdl.handle.net/11572/197172
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 8
  • ???jsp.display-item.citation.isi??? 4
social impact