Contribution à l’ordonnancement de tâches BGW 

Télécharger le fichier pdf d’un mémoire de fin d’études

Domaines d’applications temps réel

Aujourd’hui, l’informatique temps réel joue un rôle primordial dans notre société où les objets de toutes natures sont connectés pour s’échanger des informations. On parle ainsi de systèmes cyber-physiques, de l’Internet des Objets. Ces objets peuvent être des systèmes temps réel plus ou moins complexes devant ac-quérir des données, traiter des données et expédier des données dans des temps contraints. Ainsi toute notre société se trouve concernée par les systèmes temps réel qu’il s’agisse de produits grand public que de sys-tèmes plus sophistiqués. C’est en particulier le cas des processus complexes de production, des systèmes de commande de vol, des automobiles, de l’acquisition et du suivi de données environnementales, du contrôle de réacteurs chimiques et des centrales nucléaires, des systèmes de télé-médecine, de l’automatisation in-dustrielle, de certains appareils électroniques grand public, etc.
La grande majorité des systèmes temps réel sont des systèmes embarqués. Ces derniers se caractérisent par une liste de contraintes propres découlant de l’environnement physique dans lequel ils sont placés. Ces contraintes peuvent par exemple avoir une incidence sur la taille et le poids du système lorsque résidant sur un petit matériel mobile. Elles peuvent aussi s’exprimer en termes de consommation énergétique car dis-posant d’une très petite batterie ce qui limite la puissance consommée. Ces contraintes environnementales exprimées en température, pression, vibrations peuvent aussi avoir un impact sur le choix des composants électroniques comme c’est le cas pour les applications militaires.
En résumé, les systèmes embarqués sont très différents les uns des autres selon le domaine d’application visé. Cela va des petits appareils portables (par exemple, les téléphones mobiles, caméras, navigateurs, ap-pareils ECG, Holter, jouets intelligents, etc.) à de grands systèmes (par exemple, robots industriels, voitures, avions, etc.).

Architecture d’un système temps réel

L’architecture matérielle sur laquelle un systèmes temps réel exécute ses programmes informatiques, dé-signe l’ensemble des ressources physiques nécessaires d’une part au traitement des données et d’autre part aux interactions entre ce système informatique et l’environnement avec lequel celui-ci interagit. Ces res-sources sont les processeurs, les unités d’entrées/sorties, les mémoires, les réseaux, etc.
En fonction du nombre de processeurs et de l’utilisation éventuelle ou non d’un réseau, on distingue trois grandes catégories d’architectures :
• Architecture monoprocesseur : tous les programmes (tâches) de l’application sont exécutés sur un unique processeur partagé.
• Architecture multiprocesseur centralisée : Les tâches s’exécutent sur plusieurs processeurs le plus souvent identiques qui se partagent une mémoire centrale commune, chaque processeur disposant en plus de sa mémoire propre.
• Architecture multiprocesseur distribuée : Les processeurs ne se partagent aucune mémoire et les pro-cesseurs s’échangent des informations via un bus ou un réseau. En général, les tâches sont assignées statiquement à chacun des processeurs. Éventuellement, elles ne migreront qu’en situation exception-nelle telle que la panne d’un processeur. On parlera alors de reconfiguration dynamique des tâches suite à la modification de l’architecture matérielle. Pour une application de contrôle/commande de procédés industriels, une architecture distribuée pourra utiliser un réseau de terrain tel que CAN (Controller Area Network).
Ce travail de thèse portera sur une architecture matérielle monoprocesseur.

Logiciels temps réel

L’architecture logicielle d’un système informatique temps réel se compose essentiellement de deux compo-sants :
• un exécutif temps réel et
• une application.
Pour être exploitées, les ressources d’une architecture matérielle nécessitent la mise en oeuvre d’un logiciel système appelé Système d’exploitation temps réel (en anglais, RTOS pour Real Time Opérating System) appelé aussi exécutif temps réel. Le coeur de ce logiciel contient les mécanismes indispensables à son fonctionnement et à la gestion des ressources matérielles. Il est appelé noyau temps réel.
L’exécutif a un rôle de centralisateur ou d’interface car il aiguille les événements (interruptions) reçus de l’environnement contrôlé vers le logiciel d’application qui se charge de traiter ces événements en conformité avec les spécifications. Parmi les systèmes d’exploitation les plus connus, on trouve des systèmes orientés à utilisation commerciale comme par exemple, VRTX32, pSOS, OS9, VxWorks Chorus et des systèmes uti-lisés dans le domaine de la recherche comme MARS, Spring, ARTS, RK, TIMIX, MARUTI et HARTOS [21].
L’exécutif temps réel va donc non seulement gérer les ressources matérielles mais aussi gérer le logiciel d’application. Celui-ci se compose de programmes appelés tâches. Une tâche désigne le programme infor-matique qui réalise une fonction par exemple celle nécessaire au contrôle du procédé.
Les tâches font appel, lors de leur exécution, aux services proposés par l’exécutif temps réel et qui assurent principalement la synchronisation et la communication inter-tâches. Ces tâches nécessitent aussi des ser-vices liés à la gestion du temps leur permettant notamment de s’exécuter périodiquement. Elles nécessitent aussi de pouvoir démarrer leur exécution sur l’arrivée d’interruptions matérielles, d’où la présence dans l’exécutif de services de gestion d’événements. Ainsi, à tout instant plusieurs tâches peuvent avoir reçu leur signal de réveil c’est à dire l’événement men-tionnant à l’exécutif l’autorisation de les exécuter. Comme à un moment donné, plusieurs tâches se trouvent prêtes à s’exécuter, se pose un problème de concurrence pour l’accès au processeur.
L’ordonnanceur représente le composant central d’un système d’exploitation temps réel car il est en charge de sélectionner la tâche qui se verra autorisée à s’exécuter. La règle utilisée par l’ordonnanceur pour choisir la future tâche active (tâche en exécution) s’appelle algorithme d’ordonnancement.
Dans beaucoup de RTOS, on trouve des algorithmes d’ordonnancement cycliques et statiques, qui éla-borent la description de l’activité du processeur (appelée séquence d’ordonnancement) de façon hors ligne. En d’autres termes, avant de lancer l’application, on définit la façon dont le temps processeur sera réparti sur les différentes tâches. Cependant, lorsqu’ une plus grande souplesse est nécessaire, on doit faire appel à des techniques d’ordonnancement dites en ligne. Celles-ci construisent la séquence dynamiquement au fur et à mesure que les événements se produisent. La grande partie des algorithmes d’ordonnancement en ligne utilisent la notion de priorité. Chaque tâche se voit affecter une priorité utilisée par l’ordonnanceur pour ordonner la liste des tâches prêtes à tout instant et ainsi sélectionner la plus prioritaire. On fait la distinction entre priorités fixes si assignées hors ligne et priorités dynamiques lorsqu’elles changent de valeurs au cours du temps.
En résumé, un RTOS conventionnel fournit, outre l’ordonnanceur, des services de base comme la com-munication inter-tâches, la synchronisation inter-tâches, la gestion de l’accès aux ressources partagées et la gestion des interruptions.
Dans cette thèse, nous utiliserons un modèle de tâches indépendantes.

Les tâches temps réel

Catégorisation des tâches

Dans un système temps réel, il existe essentiellement trois familles de tâches qui diffèrent selon la nature de l’événement qui les réveille : tâches périodiques, tâches apériodiques et tâches sporadiques.
Dans une application temps réel de contrôle/commande, on utilise des tâches périodiques pour exécuter de manière répétitive et cyclique les fonctions de traitement des données issues de capteurs et les fonctions de régulation et de suivi en boucle fermée. La période d’une tâche périodique découle directement de la vitesse d’évolution du procédé contrôlé c’est à dire de sa dynamique. Selon l’application, la période peut varier de quelques millisecondes à quelques minutes. Toute tâche périodique donne lieu à l’exécution d’une infinité de jobs appelés aussi instances. En général, on exige qu’une instance de tâche termine son exécution avant que l’instance suivante de la même tâche ne soit réveillée.
On dira qu’une tâche est sporadique si elle est cyclique mais que sa période de répétition n’est pas constante.
On connaît toutefois pour cette tâche l’intervalle de temps minimum séparant deux réveils successifs.
Les tâches apériodiques désignent des programmes qui démarrent leur exécution sur l’arrivée d’un événe-ment non régulier et imprévisible et pour lequel il n’est pas possible d’associer un délai d’inter-arrivée. Typiquement, une tâche de traitement d’alarme est une tâche apériodique.

Spécifications d’une tâche périodique

Une tâche périodique sera notée i. Liu et Layland sont à l’origine en 1973 des premiers travaux sur l’or-donnancement de tâches périodiques dans un système temps réel. i est modélisée par quatre paramètres (ri; Ci; Ti; Di) définis comme suit :
• ri : Date de réveil de la première instance de i, qui correspond à la date de début d’exécution au plus tôt de i.
• Ci : Durée d’exécution nécessaire au processeur pour exécuter toute instance de i. En réalité, le temps d’exécution effectif d’une tâche varie entre une borne minimum Ci # ou BCET (Best Case Execution Time) et une borne maximum Ci  » ou WCET (Worst Case Execution Time) c’est à dire Ci # Ci Ci « . Généralement, on étudie le comportement du système dans la situation pire cas c’est à dire avec Ci = Ci « .
• Ti : Période de répétition de i qui est prête à être exécutée au début de chaque période.
• Di : Délai critique ou échéance relative de i. On a donc : di = ri + Di où di désigne l’échéance absolue de la première instance de i.
De ces paramètres temporels associés à chaque tâche, on en déduit des grandeurs caractéristiques de l’application temps réel :
• le facteur d’utilisation du processeur noté Up. Cette grandeur comprise entre 0 et 1 indique le pour-centage de temps durant lequel le processeur se trouve occupé à exécuter des tâches de l’application. Ainsi, on dit que le processeur est surchargé si le taux d’utilisation est supérieur à 1. Autrement dit, une condition nécessaire de faisabilité dans le cas d’une application temps réel à contraintes dures est que le processeur soit sous-chargé c’est à dire que Up 1.

L’ordonnancement temps réel

Dans ce paragraphe, nous rappelons quelques notions importantes pour la suite de la thèse relatives à l’or-donnancement d’un ensemble de tâches temps réel.

Ordonnancement préemptif versus non préemptif

Un algorithme d’ordonnancement est dit préemptif, lorsque la tâche en exécution peut être interrompue à chaque moment pour donner le processeur à une autre tâche suivant une règle d’ordonnancement spécifiée. Selon un algorithme d’ordonnancement non préemptif (non interruptible), la tâche qui commence son exé-cution ne peut pas être interrompue jusqu’à ce qu’elle finisse. Toute tâche temps réel, qu’elle soit périodique, sporadique ou apériodique est caractérisée par une date appelée échéance avant laquelle la tâche doit ter-miner son exécution. Intuitivement, on comprend qu’un ordonnanceur non préemptif n’est pas adapté à ce contexte où l’exécution d’une tâche longue mais peu urgente engendrerait le manquement de l’échéance d’une tâche très urgente. C’est la raison pour laquelle dans la très grande majorité des études et des RTOS, l’ordonnanceur est préemptif.

Ordonnancement en ligne versus hors ligne

Un algorithme d’ordonnancement est dit hors ligne, lorsque la séquence d’ordonnance est construite avant le lancement de l’application. L’ordonnancement généré par cette méthode est enregistré dans une table puis exécuté par le séquenceur.
Cette approche statique est très efficace mais très rigide car elle suppose que tous les paramètres, y compris les dates de réveil, soient figées. Elle n’est donc pas adaptée pour effectuer une reconfiguration du logiciel et/ou du matériel en présence de pannes matérielles ou de fautes logicielles.
Un algorithme est dit en ligne, lorsque la décision d’ordonnancement se prend à chaque fois qu’une tâche se réveille, se bloque dans l’attente d’un événement ou d’une ressource occupée ou qu’une tâche se termine.
Le seul inconvénient d’un ordonnanceur en ligne par rapport à un ordonnanceur hors-ligne réside dans les surcoûts d’exécution appelés overhead. C’est la raison pour laquelle tout algorithme d’ordonnancement temps réel doit être évalué par sa complexité algorithmique qui donne une indication sur la quantité d’ove-rhead temporel engendré à la mise en oeuvre.
Comme indiqué précédemment, l’énorme avantage d’un ordonnanceur en ligne tient dans sa grande flexibi-lité et son adaptabilité pour prendre en compte l’arrivée imprévisible de tâches, la variation des paramètres temporels des tâches comme leur durée d’exécution effective. Ceci est rendu possible car il effectue une construction progressive de la séquence d’ordonnancement et peut remettre en question une séquence d’or-donnancement à l’arrivée de tout nouvel événement. Dans cette thèse, nous nous intéressons à des systèmes temps réel pouvant être sujets à des fautes et des surcharges de traitement imprévisibles. D’où la nécessité de se focaliser sur des ordonnanceurs préemptifs en ligne, assez flexibles pour s’adapter dynamiquement à ces situations.

Présentation du chapitre

Les systèmes temps réel réalisent des traitements complexes que l’on qualifie de critiques car ils sont sou-mis à des contraintes strictes qui portent d’une part sur la justesse des résultats issus des calculs et d’autre part sur les dates auxquelles ces résultats doivent être disponibles. Le non respect de ces exigences peut alors avoir des conséquences catastrophiques du point de vue économique, matériel voire humain (perte d’argent, de temps, ou de vies humaines dans le pire cas). Pour cette raison, ils doivent mettre en oeuvre des mécanismes de tolérance aux fautes. Dans ce chapitre, nous revenons sur les concepts de base de la tolérance aux fautes pour l’informatique temps réel. Nous nous focalisons ensuite sur les fautes dites temporelles. Et nous décrivons les principales méthodes qui se donnent comme objectif de limiter l’impact de ces fautes temporelles sur la qualité du service rendu dans un système temps réel surchargé.

Surcharge et faute temporelle

Notion de surcharge

Considérons une architecture monoprocesseur qui doit supporter l’exécution d’un ensemble de tâches pério-diques. Celle-ci inflige au processeur une charge de traitement définie par le pourcentage de temps pendant lequel le processeur travaille. Dans un système dit sous-chargé, ce taux appelé aussi facteur d’utilisation est inférieur ou égal à un. Nous avons vu dans les paragraphes précédents les principaux ordonnanceurs reconnus pour leur haute performance. Toutefois, nous devons noter que ces ordonnanceurs ont un comportement satisfaisant et détermi-niste uniquement lorsque les tests d’ordonnançabilité ont été effectués et s’avèrent satisfaits. Dans le cas contraire, ces ordonnanceurs peuvent avoir un comportement complètement indéterministe ce qui est le cas de EDF. En effet, si sur un intervalle de temps, la charge infligée au processeur est supérieure à sa capacité de traitement, l’identité des tâches qui violeront leur échéance est difficilement prévisible. Les algorithmes classiques tel que RM et EDF doivent donc être remplacés par des ordonnanceurs plus adéquats en cas de surcharge.
Surcharge : On dit qu’un processeur est en surcharge si la capacité de traitement du processeur est inférieure à la charge de traitement qu’on lui inflige.
Surcharge temporaire : On dit qu’un processeur est en surcharge temporaire sur un intervalle de temps donné si sa capacité de traitement est inférieure à la charge qu’on lui afflige sur cet intervalle.
L’origine de la surcharge d’un processeur peut avoir lieu dans plusieurs circonstances. Par exemple, il peut s’avérer très difficile d’estimer le WCET de certaines tâches. Si la valeur du WCET a été mal estimée ou si le test d’ordonnançabilité a été effectué sur la base de valeurs moyennes de la durée d’exécution, des surcharges de traitement intermittentes pourront avoir lieu. Il va de soi que ces surcharges ne sont tolérées que dans des systèmes temps réel souples ou fermes.

Notion de faute temporelle

La défaillance ou panne d’un système est la conséquence d’une erreur qui elle-même est la conséquence d’une faute activée.
La faute : La faute dans un système informatique peut correspondre à un défaut dans un composant matériel, ou dans un composant logiciel de ce système. Elle est le plus souvent de nature accidentelle à cause des phénomènes physiques ou de l’imperfection naturelle de l’homme. Une faute peut dormir jusqu’à ce qu’un événement provoque son activation (par exemple, une division par zéro).
Les fautes dans un système temps réel sont divisées en trois catégories selon leur persistance tempo-relle : fautes permanentes, fautes transitoires et fautes intermittentes. Beaucoup d’auteurs affirment que la fréquence d’apparition des fautes transitoires et intermittentes est très grande par rapport à celle de fautes permanentes [40]. On rapporte que les fautes transitoires surviennent 30 fois plus que les fautes perma-nentes dans un système temps réel [129].
Les fautes peuvent avoir une nature fonctionnelle ou temporelle :
• Faute fonctionnelle : La valeur délivrée par le système est fausse c’est à dire non conforme à sa spé-cification, ou en dehors d’une plage de valeurs attendues.
• Faute temporelle : L’instant auquel la valeur est délivrée se trouve en dehors de l’intervalle de temps spécifié. Dans le cas d’un système temps réel, une faute temporelle correspond à la non délivrance du résultat à l’échéance spécifiée.
Dans la suite de cette thèse, nous nous focalisons sur les fautes intermittentes de nature tempo-relle.

Origine des fautes temporelles

La tolérance aux fautes temporelles représente la propriété d’un système à pouvoir délivrer un service conforme à sa spécification en présence de fautes temporelles.
Dans un système temps réel, chaque instance de tâche périodique doit idéalement produire un résultat final exact c’est à dire se terminer, avant son échéance. Un système temps réel idéal serait donc celui qui, sur toute la durée de vie de l’application, ne présente aucune faute temporelle. En d’autres termes, c’est un système où chaque échéance de tâche produit un résultat exact avant son échéance.
Les causes de l’occurrence de fautes temporelles sont multiples :
• défaillance du processeur : par exemple, un des circuits subit des perturbations électromagnétiques temporaires,
• défaillance du lien de communication : la tâche attend indéfiniment une donnée en provenance d’un autre processeur pour pouvoir continuer son traitement,
• idem que précédemment, la tâche attend indéfiniment une mesure à partir d’un capteur défaillant,
• le processeur se trouve en surcharge de traitement. Il ne peut satisfaire toutes les échéances des tâches étant donné sa capacité de traitement limitée,
• le code exécuté par une tâche boucle indéfiniment pour certaines données d’entrée.
• etc.
En résumé, nous devons donc distinguer deux origines distinctes à la faute temporelle :
• la surcharge de traitement,
• et la défaillance d’origine logicielle ou matérielle.
La plupart des méthodes présentées dans la littérature pour la conception des systèmes tolérants aux fautes se concentrent sur la défaillance du matériel (processeurs et liens de communications) qui engendrent des fautes fonctionnelles et non des fautes temporelles. Ces méthodes utilisent la réplication appelée aussi redondance pour concevoir des systèmes sûrs de fonctionnement en toutes circonstances.

Redondances logicielles

La redondance logicielle consiste à répliquer les tâches en plusieurs versions de code, identiques ou non. Si une version est l’objet d’une faute temporelle, au moins une autre version de la même tâche doit être exempte de faute temporelle.
Il existe deux approches pour implémenter la redondance logicielle dans un système informatique :
1. La redondance active impose que toutes les versions d’une même tâche soient systématiquement exé-cutées.
2. La redondance passive suppose qu’une seule des versions de chaque composant logiciel, appelée version primaire, est exécutée à la fois. Les autres versions sont appelées versions de sauvegarde ou versions secondaires (en anglais back-up). Le nombre de versions secondaires dépend du nombre maximum de fautes pouvant survenir. Une version secondaire n’est exécutée que consécutivement à l’arrivée d’une faute concernant une autre version de la même tâche. C’est pourquoi, on parle de redondance dynamique passive.
L’inconvénient majeur de la redondance active réside dans le supplément de charge de traitement qu’elle engendre. De ce fait, cela augmente la probabilité d’engendrer des fautes temporelles sur une architecture matérielle monoprocesseur car les versions ne peuvent pas s’exécuter en parallèle.

Fautes temporelles et temps réel souple

Dans les applications à contraintes souples, aucun niveau minimal de QdS n’est requis. D’où le caractère optionnel d’un test de faisabilité hors-ligne. L’ordonnanceur fera au mieux pour ne produire aucune faute temporelle ce qui reste toutefois impossible sur un processeur en surcharge de traitement ou sujet à des défaillances. Les ordonnanceurs généralement utilisés dans ce contexte sont ceux décrits ci-dessous.

Approche Best Effort

Un ordonnanceur Best-Effort accepte systématiquement les tâches qui arrivent sans test d’acceptation et les insère dans la file des tâches prêtes. Ainsi, les tâches sont ordonnancées jusqu’à leur terminaison ou jusqu’à dépassement d’échéance. Comme il n’y a aucune prédiction de surcharge, l’ordonnancement est basé sur les priorités données aux tâches. Ce type d’approche est souvent sensible à l’effet Domino.
Dans [57], Koren et Shasha proposent un algorithme d’ordonnancement en ligne, appelé D over adapté aux systèmes temps réel surchargés. D over est optimal dans le sens où il donne le meilleur facteur de compétitivité parmi tous les algorithmes en ligne. Ce facteur est de 0; 25. Rappelons que le facteur de compétitivité renseigne sur la performance d’un algorithme en ligne comparée à celle d’un algorithme clair-voyant qui a une connaissance de l’avenir.
Dans le cas où aucune surcharge n’est détectée, D over se comporte comme l’algorithme EDF . La détection d’une surcharge se fait lorsqu’une tâche prête atteint sa date de démarrage au plus tard souvent appelée LST (Latest Start Time) donnée par l’échéance minorée de la durée d’exécution. A cet instant, une tâche doit être abandonnée : soit la tâche qui a atteint son LST soit une autre tâche.
L’ensemble des tâches prêtes se divise en deux sous-ensembles disjoints : les tâches privilégiées et les tâches en attente. Chaque fois qu’une tâche est préemptée, elle devient une tâche privilégiée. Cependant, à chaque fois qu’une tâche est exécutée au plus tard sur son LST , toutes les tâches prêtes (si elles sont préemptées ou jamais exécutées) deviennent des tâches en attente.
Lorsqu’une surcharge est détectée sur l’atteinte par une tâche z de son LST , la valeur de z est comparée à la valeur totale Vpriv de toutes les tâches privilégiées (y compris la valeur vcurr de la tâche en cours d’exécution).

Approche à garantie

Chaque tâche qui arrive subit un test d’acceptation en ligne ( en anglais, guarantee ou admission test) empêchant le système d’être surchargé. Si le test réussit, la tâche est acceptée ; sinon elle est rejetée. Ces ordonnanceurs ont l’avantage par rapport aux ordonnanceurs Best-Effort de rejeter toute nouvelle tâche pouvant causer la surcharge du système. Cependant, il ne prennent pas en compte les valeurs associées à l’importance des tâches. Une variante de EDF avec test d’acceptation appelé GED (pour Guaranteed Earliest Deadline) est présenté dans [16].

Table des matières

I État de l’art 
1 Fondamentaux de l’informatique temps réel 
1.1 Présentation du chapitre
1.2 Systèmes temps réel
1.2.1 Définitions importantes
1.2.2 Domaines d’applications temps réel
1.2.3 Architecture d’un système temps réel
1.2.4 Logiciels temps réel
1.3 Les tâches temps réel
1.3.1 Catégorisation des tâches
1.3.2 Spécifications d’une tâche périodique
1.4 L’ordonnancement temps réel
1.4.1 Ordonnancement préemptif versus non préemptif
1.4.2 Ordonnancement en ligne versus hors ligne
1.4.3 Autres caractéristiques d’un ordonnanceur
1.4.4 Définitions
1.4.5 Performance d’un ordonnanceur
1.4.6 Overheads d’un ordonnanceur
1.5 Ordonnancement de tâches périodiques
1.5.1 Résultat fondamental
1.5.2 Rate Monotonic (RM)
1.5.3 Deadline Monotonic (DM)
1.5.4 Earliest Deadline First (EDF)
1.5.5 Least Laxity First (LLF)
1.6 Analyse d’ordonnançabilité pour EDF
1.6.1 Analyse basée sur le facteur d’utilisation
1.6.2 Analyse basée sur le temps de réponse
1.6.3 Analyse basée sur la demande processeur
1.7 EDF au plus tard
1.8 Conclusion
2 Gestion contrôlée des fautes temporelles 
2.1 Présentation du chapitre
2.2 Surcharge et faute temporelle
2.2.1 Notion de surcharge
2.2.2 Notion de faute temporelle
2.2.3 Origine des fautes temporelles
2.2.4 Redondances logicielles
2.3 Fautes temporelles et temps réel souple
2.3.1 Approche Best Effort
2.3.2 Approche à garantie
2.3.3 Approche robuste
2.4 Fautes temporelles et temps réel dur
2.4.1 Problématique
2.4.2 Le Calcul Imprécis
2.4.3 Le modèle élastique
2.5 Fautes temporelles et temps réel ferme
2.5.1 Problématique
2.5.2 Résolution de surcharge par pertes
2.6 Le Mécanisme à Échéance
2.6.1 Description du Mécanisme à Échéance
2.6.2 Implémentation pour le temps réel dur
2.6.3 Ordonnancement de la Première Chance
2.6.4 Ordonnancement de la Dernière Chance
2.7 Le modèle Skip-over
2.7.1 Description
2.7.2 Analyse d’ordonnançabilité
2.7.3 Stratégies d’ordonnancement
2.7.4 Commentaires
2.8 Conclusion
II Contribution à la modélisation de tâches temps réel 
3 BGW : un nouveau modèle de tâche 
3.1 Présentation du chapitre
3.2 Le modèle
3.3 Ordonnancement sous le modèle BGW
3.3.1 Objectif d’un algorithme d’ordonnancement
3.3.2 Mise en oeuvre d’un ordonnanceur
3.4 Secteurs d’utilisation du modèle BGW
3.5 Variante BGW1
3.5.1 Présentation
3.5.2 Test de faisabilité pour BGW1
3.5.3 Cas particuliers
3.5.4 Exemple illustratif
3.6 Ordonnancement basique pour BGW1
3.7 Variante BGW2
3.7.1 Présentation
3.7.2 Test de Faisabilité pour BGW2
3.7.3 Cas particuliers
3.7.4 Exemple illustratif
3.8 Ordonnancement basique pour BGW2
3.9 Variante BGW3
3.9.1 Présentation
3.9.2 Test de faisabilité
3.9.3 Cas particuliers
3.9.4 Exemple illustratif
3.9.5 Ordonnancement basique pour BGW3
3.10 Commentaires
3.10.1 Apports de BGW
3.10.2 Quelle variante choisir ?
3.11 Conclusion
III Contribution à l’ordonnancement de tâches BGW 
4 Ordonnancements élémentaires pour BGW 
4.1 Présentation du chapitre
4.2 Critères de performances adoptés
4.3 Description schématique d’un ordonnanceur
4.4 Ordonnanceur AbP
4.5 Ordonnanceur GbW a
4.6 Ordonnanceur GbW p
4.7 Environnement de simulation
4.7.1 Génération des tâches périodiques
4.7.2 Création et gestion des listes d’instances
4.7.3 Ordonnancement
4.7.4 Dispatcher
4.7.5 Affichage et enregistrement des résultats
4.8 Analyse de performances par variation de charge
4.8.1 Configuration de l’expérience
4.8.2 Analyse du taux de succès global NSJ
4.8.3 Analyse du taux de succès des primaires NP J
4.8.4 Analyse du temps processeur gaspillé WTR
4.8.5 Analyse du taux de préemption PR
4.8.6 Bilan de l’analyse
4.9 Analyse de performances avec charge secondaire fixe
4.9.1 Configuration de l’expérience
4.9.2 Analyse du taux de succès NSJ
4.9.3 Analyse du taux de succès NP J
4.9.4 Analyse du temps processeur gaspillé WTR
4.9.5 Analyse du taux de préemption PR
4.10 Conclusion
5 Ordonnancements évolués pour BGW 
5.1 Introduction
5.2 Description des ordonnanceurs
5.3 Technique de dernière chance pour le modèle BGW
5.4 Stratégie d’ordonnancement LCP
5.5 Stratégie d’ordonnancement LCJ
5.6 Stratégie d’ordonnancement LCP − t
5.6.1 Algorithme LCP-t
5.7 Stratégie d’ordonnancement LCJ − t
5.7.1 Algorithme LCJ − t
5.8 Simulations et évaluation de performances
5.8.1 Analyse des systèmes légèrement contraints
5.8.2 Analyse des systèmes lourdement contraints
5.8.3 Synthèse de l’étude
5.9 Conclusion
6 Ordonnancements équitables pour BGW 
6.1 Introduction
6.2 Équité de service et uniformité de service
6.3 Stratégie d’ordonnancement MSJ
6.4 Stratégie d’ordonnancement MSP
6.5 Ordonnanceur MDJ
6.6 Ordonnanceur MDP
6.7 Simulations et évaluation des performances
6.7.1 Équité de service au sens de la QdS1
6.7.2 Équité de service au sens de la QdS2
6.7.3 Uniformité de service au sens de la QdS1
6.7.4 Uniformité de service au sens de la QdS2
6.7.5 Autres mesures
6.8 Commentaires
6.9 Conclusion
Conclusion générale et perspectives

Télécharger le rapport complet