An Algebraic Approach for Fixed-Priority Scheduling of Hard Real-time Systems with Exact Preemption Cost

Patrick Meumeu Yomsi 1 Yves Sorel 1
1 AOSTE - Models and methods of analysis and optimization for systems with real-time and embedding constraints
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Paris-Rocquencourt, COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Résumé : Dans ce papier nous étudions les systèmes temps réel durs composés de tâches préemptives indépendantes dans le cas mono-processeur. Pour de tels systèmes il est obligatoire de respecter toutes les contraintes auxquelles sont soumises toutes les tâches. Bien que des algorithmes d'ordonnancement préemptifs soient capables d'ordonnancer certains systèmes qui ne peuvent être ordonnancés avec aucun algorithme d'ordonnancement non préemptif, la préemption peut avoir un coût non négligeable. Nous proposons donc de considérer explicitement le coût exact de la préemption dans les analyses d'ordonnançabilité afin d'une part d'éviter du gaspillage de ressources et d'autre part de garantir un comportement correct lors de l'exécution en temps réel conforme aux analyses d'ordonnançabilité. Nous présentons dans ce papier cinq contributions. Premièrement nous introduisons un nouveau model pour décrire et analyser les systèmes temps réel durs qui unifie plusieurs modèles comme celui de Liu et Layland ou celui de Mok. Deuxièmement nous montrons l'impact de la prise en compte du coût exact de la préemption pour chaque tâche lors de l'analyse d'ordonnançabilité. Troisièmement en utilisant notre modèle fondé sur une approche algébrique nous proposons de nouvelles conditions d'ordonnançabilité qui prennent en compte le coût exact dû à l'occurence de chaque préemption. Quatrièmement, dans le cas ou l'on considère ce coût exact de la préemption, nous proposons un algorithme d'ordonnancement optimal, au sens de la faisabilité, pour choisir la priorité fixe de chaque tâche. Finalement nous étudions le problème consistant à réduire le nombre de préemptions.
Type de document :
Rapport
[Research Report] RR-7702, INRIA. 2011, pp.43
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00613347
Contributeur : Yves Sorel <>
Soumis le : jeudi 4 août 2011 - 16:13:23
Dernière modification le : vendredi 25 mai 2018 - 12:02:04
Document(s) archivé(s) le : samedi 5 novembre 2011 - 02:21:11

Fichier

RR-7702.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00613347, version 1

Collections

Citation

Patrick Meumeu Yomsi, Yves Sorel. An Algebraic Approach for Fixed-Priority Scheduling of Hard Real-time Systems with Exact Preemption Cost. [Research Report] RR-7702, INRIA. 2011, pp.43. 〈inria-00613347〉

Partager

Métriques

Consultations de la notice

367

Téléchargements de fichiers

245