1999-thesis-grolleau.. - DOCTEUR DE L UNIVERSITE DE POITIERS ...
246 pages
Français

1999-thesis-grolleau.. - DOCTEUR DE L'UNIVERSITE DE POITIERS ...

Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres
246 pages
Français
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres

Description

THESE
Pour l'obtention du grade de
DOCTEUR DE L'UNIVERSITE DE POITIERS
Ecole Nationale Supérieure de Mécanique et d’Aérotechnique
Faculté des Sciences Fondamentales et Appliquées
Ecole Doctorale des Sciences pour l’Ingénieur
(Diplôme National – Arrêté du 30 Mars 1992)
Secteur de Recherche : INFORMATIQUE
Présentée et soutenue publiquement par
Emmanuel GROLLEAU
Le 29 Novembre 1999
Ordonnancement temps réel hors-ligne optimal
à l’aide de réseaux de Petri
en environnement monoprocesseur et multiprocesseur.
Directeurs de Thèse : Francis COTTET, Annie CHOQUET-GENIET
JURY
Président : P. Estraillier Professeur, Université de La Rochelle, L3I
Rapporteurs : G. Juanole Professeur, Université Paul Sabatier, LAAS
G. Vidal-Naquet Professeur, Supélec, LRI
Examinateurs : A. Choquet-Geniet Maître de Conférences, Université de Poitiers, LISI
F. Cottet Professeur, ENSMA, LISI
A-M. Deplanche Maître de Conférences, Université de Nantes, IRCyN
LABORATOIRE D'INFORMATIQUE SCIENTIFIQUE ET INDUSTRIELLE
Ecole Nationale Supérieure de Mécanique et d'Aérotechnique
Téléport 2 - 1, avenue Clément Ader - BP 40109 - 86961 Futuroscope
Tél: 05.49.49.80.63 - Fax: 05.49.49.80.64 Remerciements
J’exprime mes plus vifs remerciements à Annie Choquet-Geniet pour avoir encadré mon
travail de thèse. Ses conseils constants m’ont été une aide inestimable et ont largement contri-
bué à ma formation de chercheur.
Je tiens à remercier le Professeur Francis Cottet, qui m’a permis d’intégrer l’équipe Temps
Réel, pour les ...

Sujets

Informations

Publié par
Nombre de lectures 309
Langue Français
Poids de l'ouvrage 2 Mo

Exrait

THESE Pour l'obtention du grade de DOCTEUR DE L'UNIVERSITE DE POITIERS Ecole Nationale Supérieure de Mécanique et d’Aérotechnique Faculté des Sciences Fondamentales et Appliquées Ecole Doctorale des Sciences pour l’Ingénieur (Diplôme National – Arrêté du 30 Mars 1992) Secteur de Recherche : INFORMATIQUE Présentée et soutenue publiquement par Emmanuel GROLLEAU Le 29 Novembre 1999 Ordonnancement temps réel hors-ligne optimal à l’aide de réseaux de Petri en environnement monoprocesseur et multiprocesseur. Directeurs de Thèse : Francis COTTET, Annie CHOQUET-GENIET JURY Président : P. Estraillier Professeur, Université de La Rochelle, L3I Rapporteurs : G. Juanole Professeur, Université Paul Sabatier, LAAS G. Vidal-Naquet Professeur, Supélec, LRI Examinateurs : A. Choquet-Geniet Maître de Conférences, Université de Poitiers, LISI F. Cottet Professeur, ENSMA, LISI A-M. Deplanche Maître de Conférences, Université de Nantes, IRCyN LABORATOIRE D'INFORMATIQUE SCIENTIFIQUE ET INDUSTRIELLE Ecole Nationale Supérieure de Mécanique et d'Aérotechnique Téléport 2 - 1, avenue Clément Ader - BP 40109 - 86961 Futuroscope Tél: 05.49.49.80.63 - Fax: 05.49.49.80.64 Remerciements J’exprime mes plus vifs remerciements à Annie Choquet-Geniet pour avoir encadré mon travail de thèse. Ses conseils constants m’ont été une aide inestimable et ont largement contri- bué à ma formation de chercheur. Je tiens à remercier le Professeur Francis Cottet, qui m’a permis d’intégrer l’équipe Temps Réel, pour les nombreuses et fructueuses discussions sur mon travail. Cette thèse est le fruit d’un travail mené au sein du Laboratoire d’Informatique Scientifi- que et Industrielle dirigé par le Professeur Guy Pierra, à qui je tiens à exprimer toute ma gra- titude pour les moyens techniques et scientifiques qu’il a mis à ma disposition. Je tiens à remercier le Professeur Guy Juanole et le Professeur Guy Vidal-Naquet qui ont accepté la lourde charge de rapporteurs, ainsi que Anne-Marie Deplanche et le Professeur Pascal Estraillier pour l’honneur qu’ils m’ont fait en acceptant d’être examinateurs de mon jury. J’adresse un remerciement particulier à Dominique Geniet, qui, grâce à sa relecture très attentive de mon rapport, m’a permis d’en améliorer sensiblement la qualité, et à Yamine Aït- Ameur, Maximilien Holle ainsi qu’à Pascal Richard pour les discussions fructueuses sur le plan scientifique, que nous avons eues. Je remercie tous les membres du laboratoire, et particulièrement Manu, Ricou, Dag, Tex, Fabricio, JCP, Laurent et Dave pour les bon moments que nous avons passés ensemble, ce qui m’a permis d’affronter la route et le rail quotidiennement. Enfin, un grand merci à Patricia qui m’a soutenu et encouragé pendant toute la durée de ce travail. SOMMAIRE Sommaire Introduction générale _______________________________________________________2 ETAT DE L’ART _________________________________________________________________ 3 I Systèmes temps réel et ordonnancement_______________________________________4 I-1 Introduction au temps réel ________________________________________________5 I-1.1 Le contrôle de procédé ____________________________________________________ 6 I-1.2 Hypothèse synchrone et asynchrone __________________________________________ 6 I-1.2.1 Hypothèse synchrone _________________________________________________ 6 I-1.2.2 L’hypothèse asynchrone _______________________________________________ 7 I-1.3 Les systèmes temps réel ___________________________________________________ 9 I-1.3.1 L’exécutif temps réel__________________________________________________ 9 I-1.3.1.a Gestion des tâches _______________________________________________________ 9 I-1.3.1.b Gestion des communications et des synchronisations___________________________ 10 I-1.3.1.c Gestion des ressources critiques ___________________________________________ 14 I-1.3.1.d La gestion du temps_____________________________________________________ 16 I-1.3.2 Contextes temps réel 17 I-1.3.3 Tâches temps réel 17 I-1.3.3.a Tâches périodiques _____________________________________________________ 17 I-1.3.3.b Tâches non périodiques__________________________________________________ 21 I-1.3.3.c Contextes d’ordonnancement _____________________________________________ 23 I-1.4 Conclusion_____________________________________________________________ 25 I-2 L’ordonnancement des systèmes de tâches temps réel _________________________27 I-2.1 Propriétés générales des algorithmes d’ordonnancement 27 I-2.1.1 Notions de validité, de puissance, et d’optimalité___________________________ 27 I-2.1.2 Validation temporelle de systèmes temps réel _____________________________ 29 I-2.1.2.a Approches en-ligne _____________________________________________________ 30 I-2.1.2.b Approches hors-ligne ___________________________________________________ 30 I-2.1.2.c Validation par simulation ________________________________________________ 31 I-2.2 Ordonnancement en-ligne _________________________________________________ 32 I-2.2.1 Ordonnancement en-ligne de tâches indépendantes _________________________ 32 I-2.2.1.a Algorithmes à priorités statiques ___________________________________________ 32 I-2.2.1.b Algorithmes à priorités variables 38 I-2.2.1.c Récapitulatif sur l’ordonnancement de tâches indépendantes en environnement monoprocesseur _______________________________________________________________ 42 I-2.2.2 Ordonnancement en-ligne de tâches communicantes ________________________ 42 I-2.2.3 Partage de ressources 46 I-2.2.3.a Le protocole à priorité héritée (PPH)________________________________________ 49 I-2.2.3.b Le protocole à priorité plafond (PPP) _______________________________________ 51 I-2.2.3.c Le protocole d’allocation de la pile (PAP) ___________________________________ 54 I-2.2.3.d Conclusion sur la gestion de ressources dans les algorithmes en-ligne______________ 55 I-2.3 Ordonnancement et complexité en environnement multiprocesseur_________________ 56 I-2.4 Approches hors-ligne_____________________________________________________ 59 I-2.5 Conclusion_____________________________________________________________ 63 II Extensions des Réseaux de Petri____________________________________________64 II-1 Réseaux de Petri autonomes_____________________________________________65 II-1.1 Définitions et notations __________________________________________________ 65 II-1.2 Langage d’un réseau de Petri ______________________________________________ 67 II-1.3 Réseaux de Petri colorés _________________________________________________ 69 II-2 Réseaux de Petri prenant en compte le temps _______________________________71 i Sommaire II-2.1 Réseaux de Petri temporels _______________________________________________ 71 II-2.1.1 Définitions et notations ______________________________________________ 71 II-2.1.2 Puissance d’expression 73 II-2.2 Réseaux de Petri temporisés 75 II-2.3 Rétri autonomes avec la règle de tir maximal ________________________ 78 II-2.4 Conclusion ____________________________________________________________ 79 CONTRIBUTION _______________________________________________________________ 81 III Etude de la Cyclicité des Ordonnancements de Tâches Périodiques _____________82 III-1 Etude des temps creux acycliques _______________________________________85 III-1.1 Cas des systèmes de tâches indépendantes ___________________________________ 87 III-1.1.1 La date d’occurrence du dernier temps creux acyclique est bornée ____________ 90 III-1.1.2 L’état d’un système est identique après le dernier temps creux acyclique et une méta-période plus tard______________________________________________________ 91 III-1.2 Cas des systèmes de tâches quelconques ____________________________________ 91 III-1.2.1 Définition des chaînes d’attente 92 III-1.2.2 Périodicité des chaînes d’attente 95 III-1.2.3 Cyclicité des ordonnancements dans le cas général ________________________ 96 III-1.2.3.a La date d’occurrence du dernier temps creux acyclique est bornée _______________97 III-1.2.3.b L’état d’un système est identique après le dernier temps creux acyclique et une méta- période plus tard _______________________________________________________________98 III-2 Conclusion ________________________________________________________103 III-2.1 Cas des algorithmes conservatifs _________________________________________ 103 III-2.2 Cas des algorithmes non conservatifs ______________________________________ 106 IV Etude de Systèmes Temps Réel à l'Aide de Réseaux de Petri: Cas Monoprocesseur110 IV-1 Modélisation _______________________________________________________111 IV-1.1 Hypothèses générales __________________________________________________ 111 IV-1.2 Principe général ______________________________________________________ 113 IV-1.3 Système d’horlogerie 114 IV-1.4 Systèmes de tâches ____________________________________________________ 116 IV-1.4.1 Modélisation des blocs indépendants __________________________________ 116 IV-1.4.2 Modélisation des communications ____________________________________ 118 IV-1.4.3 Modélisation des ressources critiques _________________________________ 119 IV-1.4.4 Schéma global d’une tâche__________________________________________ 120 IV-1.5 Prise en compte des temps creux _________________________________________ 122 IV-1.6 Prise en compte des dates de réveil _______________________________________ 122 IV-1.7 Prise en compte des contraintes temporelles ________________________________ 123 IV-1.7.1 Tâches à échéance avant requête _____________________________________ 123 IV-1.7.2 Tâches à échéance sur requête 124 IV-1.7.3 Cas général ______________________________________________________ 124 IV-1.8 Récapitulatif _________________________________________________________ 125 IV-1.9 Exemples de modélisation ______________________________________________ 127 IV-1.9.1 Tâches à échéance sur requête à départ simultané, avec une ressource en écriture et une boîte aux lettres 127 IV-1.9.2 Illustration de l’obtention des séquences non conservatives ________________ 128 IV-1.9.3 Tâches comportant des parties non préemptibles _________________________ 129 IV-2 Etude_____________________________________________________________133 IV-2.1 Profondeur du graphe d’accessibilité ______________________________________ 133 IV-2.2 Représentation du graphe d’accessibilité ___________________________________ 134 ii Sommaire IV-2.2.1 Deux tâches simultanées indépendantes de charge 100% __________________ 134 IV-2.2.2 Deux tâches différées indépendantes de charge 100%_____________________ 134 IV-2.3 Complexité et taille du graphe d’accessibilité _______________________________ 135 IV-2.3.1 Borne théorique à la taille du graphe d’accessibilité ______________________ 136 IV-2.3.2 Structure de données utilisée pour stocker et rechercher les marquages _______ 139 IV-2.4 Obtention des séquences d’ordonnancement valides __________________________ 141 IV-2.4.1 Construction du graphe des marquages ________________________________ 142 IV-2.4.1.a Construction en largeur________________________________________________ 142 IV-2.4.1.b Construction en profondeur ____________________________________________ 143 IV-2.4.1.c Comparatif d’une construction en largeur par rapport à en profondeur ___________ 143 IV-2.4.2 Diminution des cas de retours arrière__________________________________ 144 IV-2.4.3 Diminution de la taille du graphe des marquages_________________________ 146 IV-2.4.3.a Contraintes de successeur ______________________________________________ 146 IV-2.4.3.b Contraintes absolues__________________________________________________ 147 IV-2.4.4 Extraction de séquences d’ordonnancement optimales ____________________ 149 IV-2.4.4.a Exécution au plus tôt _________________________________________________ 150 IV-2.4.4.b Optimisation du temps de réponse _______________________________________ 151 IV-2.4.4.c Optimisation du taux de réaction ________________________________________ 153 IV-2.4.4.d Optimisation du retard ________________________________________________ 154 IV-2.4.4.e Minimisation de la gigue 155 IV-2.4.4.f Répartition des temps creux ____________________________________________ 160 IV-2.4.4.g Discussion sur les critères qualitatifs _____________________________________ 161 V Etude de Systèmes Temps Réel à l'Aide de Réseaux de Petri: Cas Multiprocesseur 164 V-1 Hypothèses matérielles________________________________________________165 V-2 Modélisation________________________________________________________167 V-3 Etude _____________________________________________________________171 V-3.1 Profondeur du graphe d’accessibilité_______________________________________ 171 V-3.2 Représentation du graphe d’accessibilité____________________________________ 171 V-3.2.1 Deux tâches simultanées indépendantes de charge 100% __________________ 171 V-3.2.2 Deux tâches simultanées indépendantes de charge inférieure à 100% _________ 172 V-3.3 Taille du graphe d’accessibilité ___________________________________________ 173 V-3.4 Obtention des séquences d’ordonnancement valides___________________________ 174 V-3.4.1 Placement des tâches a posteriori _____________________________________ 174 V-3.4.2 Diminution des cas de retours arrière __________________________________ 174 V-3.4.3 Note sur les contraintes de successeur 175 V-3.4.4 Diminution de la taille du graphe des marquages _________________________ 176 V-3.4.5 Extraction de séquences d’ordonnancement optimales _____________________ 176 VI Application de l’Etude __________________________________________________178 VI-1 Présentation de PeNSMARTS __________________________________________179 VI-1.1 Saisie du système de tâches à étudier ______________________________________ 179 VI-1.2 Génération du modèle RdP______________________________________________ 181 VI-1.3 Génération des séquences d’ordonnacement ________________________________ 182 VI-2 Etude de cas _______________________________________________________185 VI-2.1 Description du procédé_________________________________________________ 185 VI-2.2 Spécification du contrôle _______________________________________________ 186 VI-2.3 Implémentation 187 Conclusion ______________________________________________________________192 iii Sommaire Bibliographie ____________________________________________________________196hie liée à l’étude _________________________________________________206 Annexes_________________________________________________________________208 I-1 Etude du _______________________________________________________209ppcm I-2 Notions de complexité211 I-3 Fonctionnement d’un réseau de Petri avec la règle de tir maximal_______________215 I-4 Preuves relatives au résultat de cyclicité des ordonnancements _________________219 I-5 Algorithme de placement de tâches évitant les changements de contexte inutiles ___225 Index ___________________________________________________________________226 Index des Figures _________________________________________________________230 iv NTRODUCTION GÉNÉRALE I
  • Accueil Accueil
  • Univers Univers
  • Ebooks Ebooks
  • Livres audio Livres audio
  • Presse Presse
  • BD BD
  • Documents Documents