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

Sujets

• Système temps réel
• Algorithme de colonies de fourmis
• Période Yayoi
• Réveillez-vous !
• Occurrence
• Asynchronisme

Informations

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

Extrait

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: [phone] - Fax: [phone]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’obtent