Improved approximate response time bounds for static-priority tasks

Abstract : We consider sporadic tasks with static priorities and constrained deadlines to be executed upon a uniprocessor platform. Pseudo-polynomial time algorithms are known for computing worst-case response times for this task model. Some applications require to evaluate efficiently upper bounds of response times. For this purpose, we propose parametric algorithms that allow to make a tradeoff between quality of results and computational effort according to an input accuracy parameter. In this paper, we present a parametric polynomial-time algorithm for computing upper bounds of worst-case response times, that is based on an improved FPTAS (Fully Polynomial Time Approximation Scheme). Then, we show that our bound does not achieve constant error bound in comparison with the exact worstcase response time. However, using the resource augmentation technique, we obtain a performance guarantee that allows to define a compromise between our response-time bound and processor capacity requirements. The algorithm average behavior is then analyzed through numerical experimentations.
Type de document :
Communication dans un congrès
Giorgio Buttazzo and Pascale Minet. 16th International Conference on Real-Time and Network Systems (RTNS 2008), Oct 2008, Rennes, France. 2000
Liste complète des métadonnées

Littérature citée [17 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00336498
Contributeur : Anne Jaigu <>
Soumis le : mardi 4 novembre 2008 - 12:00:22
Dernière modification le : mardi 4 novembre 2008 - 12:09:14
Document(s) archivé(s) le : lundi 7 juin 2010 - 20:20:45

Fichier

nguyen.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00336498, version 1

Collections

Citation

Thi Huyen Chau Nguyen, Pascal Richard, Enrico Bini. Improved approximate response time bounds for static-priority tasks. Giorgio Buttazzo and Pascale Minet. 16th International Conference on Real-Time and Network Systems (RTNS 2008), Oct 2008, Rennes, France. 2000. 〈inria-00336498〉

Partager

Métriques

Consultations de la notice

174

Téléchargements de fichiers

97