Les systèmes temps réel multiprocesseur
Introduction aux systèmes temps réel
Pour introduire la notion de temps réel, on se réfère généralement à la définition intuitive suivante de Stankovic (1988) : »la correction du système ne dépend pas seulement des résultats logiques des traitements, mais dépend aussi de la date à laquelle ces résultats sont produits ». Ces dates à respecter appelées échéances sont fondamentales pour un système temps réel, et leur dépassement peut induire dans certains cas une défaillance du système pouvant être grave à la fois pour le système et l’environnement contrôlé. Le respect des échéances ne sous-entend pas la rapidité des traitements, puisque ces dates peuvent être, selon le système, de l’ordre de la milliseconde ou du mois, voire des années. Les systèmes temps réel sont en général constitués de deux parties : le système contrôlé souvent appelé procédé ou encore partie opérative, sur lequel on exerce le contrôle, et la partie commande qui interagit avec le premier. Le système de contrôle prend connaissance de l’état du procédé par le biais des capteurs, lui permettant de réaliser un traitement spécifique et d’agir par conséquent sur le procédé par le biais des actionneurs. Le système de contrôle est composé d’une partie logicielle et d’une partie matérielle. Le support d’exécution de cette dernière peut être :
– monocœur : tous les programmes de la partie logicielle s’exécutent en parallélisme apparent.
– multicœur : les programmes de la partie logicielle sont répartis sur plusieurs cœurs, partageant au moins une mémoire commune.
– réparti : les programmes sont répartis sur plusieurs processeurs dépourvus de mémoire commune et d’horloge commune. Ils sont reliés par un médium de communication via lequel ils peuvent communiquer par échanges de messages.
Classification
Les systèmes temps réel sont classés selon le niveau de criticité de leurs contraintes de temps. On parle alors de systèmes (Liu 2000) :
– temps réel dur ou à contraintes strictes (hard en anglais) pour lesquels le dépassement des échéances n’est pas toléré, sous peine de conséquences catastrophiques sur le système lui-même ou son environnement (ex : le système de contrôle du train d’atterrissage d’un avion),
– temps réel souple ou à contraintes relatives (soft en anglais) pour lesquels le dépassement des échéances peut provoquer des dégradations acceptables (ex : le système informatique d’une borne interactive multiservice),
– temps réel ferme (firm en anglais). Ce type de système se situe à la frontière entre les deux contraintes précédentes. Un système temps réel ferme tolère le dépassement des échéances mais à la différence des systèmes à contraintes soft, ces dépassements sont quantifiés (ex : le système de lecture d’une vidéo, normalement cadencé à 25 images par seconde peut tolérer une dégradation passagère à 20 images par seconde). De plus, un résultat produit après échéance n’est pas pris en compte.
Les tâches temps réel
Notion de tâche temps réel
Dans la littérature, le terme tâche se réfère à une suite cohérente d’opérations afin d’exécuter un programme. Ce terme est souvent préféré au terme processus pour signifier la périodicité ou la cyclicité d’exécution. Le terme processus est attaché quant à lui, plutôt au sens de l’unicité de la demande d’exécution. Au moment de son exécution, l’entité tâche est composée d’un ensemble de travaux. Dans un environnement multicœur, ces travaux peuvent être attribués aux différents cœurs en parallèle, mais en règle générale, le parallélisme au sein même d’un travail n’est pas admis. Outre les contraintes de temps que nous allons définir par la suite, les tâches peuvent avoir d’autres contraintes à respecter parmi lesquelles (Silly-Chetto 1993) :
– les contraintes de ressources. Les ressources partagées autres que les processeurs ne sont pas forcément disponibles au moment de l’activation des tâches, et leur accès doit être protégé de manière à assurer leur cohérence (ex : variables partagées en mémoire).
– les contraintes de synchronisation qui imposent un certain ordre d’exécution formulé par des relations de précédence. Lorsqu’aucune relation de précédence n’est appliquée à une tâche, celle-ci est dite indépendante.
– les contraintes d’exécution. Deux modes sont considérés : préemptif et non-préemptif. Une tâche est dite préemptible, si elle peut être interrompue à un instant quelconque et être reprise ultérieurement. Dans le cas non-préemptif, la tâche s’exécute complètement de manière ininterrompue à partir du moment où elle obtient le processeur.
– les contraintes de placement qui portent sur l’identité du (ou des) processeur(s) d’un système multicœur sur lequel une tâche est autorisée à s’exécuter.
Modélisation des tâches temps réel
Dans ce qui suit nous considérons une tâche τi appartenant au système de tâches τ auquel l’on associe l’ensemble de travaux Ji s’exécutant sur l’ensemble de processeurs M.
Définition 1.1 La tâche périodique
D’un point de vue temporel, une tâche périodique τi est caractérisée par le tuple (ri, Ci, Pi, Di) où :
– ri représente la date de réveil de la tâche, c’est-à-dire l’instant du premier travail de τi.
– Ci dénote la durée d’exécution au pire cas, à savoir une limite supérieure sur le temps d’exécution de chaque travail de la tâche τi.
– Pi correspond à la période d’activation, c’est-à-dire à la durée qui sépare deux arrivées successives de travaux pour τi.
– un délai critique Di qui représente l’échéance relative de la tâche, c’est-àdire l’intervalle de temps dont un travail dispose pour s’exécuter.
La tâche périodique τi définit un nombre infini de travaux ayant tous le même temps d’exécution. Chaque travail jn ∈ Ji qui se réveille à l’instant ri + (n − 1)Pi , doit se terminer avant sa date d’échéance absolue di = ri + (n − 1)Pi + Di , ∀n ∈ N∗ .
Cas particuliers de systèmes périodiques
Dans le cas où Pi = Di alors τi est dite à échéance sur requête. De plus, si toutes les tâches périodiques de τ ont la même date de réveil initiale (∀i, j ∈ N rj = ri) alors cette configuration de tâches est dite synchrone, sinon elle est dite asynchrone.
Définition 1.2 La tâche sporadique
Une tâche sporadique τi est caractérisée par le triplet (ri, Ci, Pi, Di) où :
– ri représente l’instant du premier travail de τi.
– Ci dénote la durée d’exécution au pire cas, à savoir une limite supérieure sur le temps d’exécution de chaque travail de la tâche τi .
– Pi correspond à la durée minimale qui sépare deux arrivées successives de travaux pour τi.
– un délai critique Di qui représente l’échéance relative de la tâche, c’est-àdire l’intervalle de temps dont un travail dispose pour s’exécuter.
Ordonnancement temps réel multiprocesseur
L’ordonnanceur des tâches représente une partie essentielle du système de contrôle. Il considère l’entité tâche τi ainsi que tous les travaux Ji de τi , mais sans pour autant considérer les traitements effectués au sein de ces travaux. Il arrive toutefois que l’ordonnanceur prenne en charge certains traitements effectués par les travaux, et ce, à des fins de synchronisation entre tâches. Les objectifs d’un ordonnanceur peuvent différer (ex : optimisation de l’utilisation des ressources, minimisation du temps de réponse, etc.) mais dans tous les cas, l’ordonnanceur doit veiller au respect des échéances des tâches.
Définitions
Nous présentons ci-dessous quelques définitions communément utilisées dans la littérature aussi bien pour les environnements mono et multiprocesseurs.
Définition 1.4 Faisabilité
Un système de tâches τ est dit faisable, s’il existe une configuration d’ordonnancement pour laquelle toutes les tâches s’exécutant sur une plateforme donnée, respectent bien leurs échéances.
Définition 1.5 Ordonnançabilité
Un système de tâches τ est dit ordonnançable par A, s’il existe un algorithme A capable d’ordonnancer toutes les tâches τi dans le respect de leurs échéances.
Définition 1.6 Optimalité
L’algorithme d’ordonnancement A est dit optimal, s’il est capable d’ordonnancer tout système de tâches faisable.
|
Table des matières
Introduction
I État de l’art
1 Les systèmes temps réel multiprocesseur
1.1 Introduction aux systèmes temps réel
1.1.1 Classification
1.1.2 Les tâches temps réel
1.1.3 Taxonomie des plateformes multiprocesseurs
1.2 Ordonnancement temps réel multiprocesseur
1.2.1 Définitions
1.2.2 Types d’ordonnancements
1.2.3 Types d’approches
1.2.4 Types de migrations
1.2.5 Classification des tests d’ordonnançabilité
1.2.6 Algorithmes d’ordonnancement
1.3 synchronisation en temps réel multiprocesseur
1.3.1 Protocoles bloquants
1.3.2 Protocoles non-bloquants
Conclusion
2 Les systèmes transactionnels
2.1 Introduction aux systèmes transactionnels
2.1.1 Les transactions
2.1.2 Les contrôleurs de concurrence
2.2 Le transactionnel temps réel
2.2.1 Les protocoles pessimistes
2.2.2 Les protocoles optimistes
Conclusion
3 Les Mémoires Transactionnelles
3.1 Introduction aux mémoires transactionnelles
3.2 Taxonomie des mémoires transactionnelles
3.2.1 Transactions imbriquées
3.2.2 Granularité des transactions
3.2.3 Faible et forte isolation
3.3 Gestion des conflits
3.3.1 Gestionnaire de contention
3.3.2 Le Helping
3.4 Implémentations des mémoires transactionnelles
3.4.1 Implémentations matérielles (HTM)
3.4.2 Implémentations logicielles (STM)
3.4.3 Implémentations hybrides (HyTM)
3.4.4 Implémentations temps réel
Conclusion
II STM pour les systèmes temps réel soft
4 Adéquation des STMs existantes aux systèmes temps réel soft
4.1 Introduction
4.2 Contexte d’évaluation
4.2.1 Plateforme matérielle
4.2.2 Configuration logicielle
4.2.3 Métriques étudiées
4.3 Évaluations expérimentales
4.3.1 Influence de l’OS
4.3.2 Influence des politiques d’ordonnancement
4.3.3 Influence de l’allocateur mémoire
Conclusion
5 Conception d’une STM temps réel (RT-STM)
5.1 Motivations et objectifs
5.2 La RT-STM
5.2.1 Le modèle transactionnel
5.2.2 La gestion de concurrence
5.2.3 La synchronisation
5.2.4 Règles de résolution de conflits
5.3 Implémentation et évaluation
5.3.1 Implémentation au sein de la OSTM
5.3.2 Évaluation de la RT-STM
Conclusion
6 RT-STM : Protocoles de gestion de concurrence
6.1 Motivations et objectifs
6.2 Formulation du problème
6.3 Modèle du système
6.4 Protocoles pour la RT-STM
6.4.1 Structures de données
6.4.2 Le protocole mono-écrivain (1W)
6.4.3 Le protocole multi-écrivain (MW)
6.5 Évaluation des protocoles
6.5.1 Contexte d’évaluation
6.5.2 La bande passante du système
6.5.3 La progression globale
6.5.4 Le ratio de temps de rejoue
Conclusion
III Extension aux contraintes firm
7 RT-STM en environnement firm
7.1 Motivations et objectif
7.2 Modèles et algorithmes existants
7.2.1 Le modèle de tâche (m,k)-firm
7.2.2 Le modèle transactionnel (mk)-firm
7.3 Modélisation et analyse de la RT-STM firm
7.3.1 Nouveau modèle sous contraintes m-firm
7.3.2 Nouveau modèle sous contraintes de QoS
7.3.3 Analyse du WCET de transactions m-firm
7.4 Extension et évaluation de la RT-STM
7.4.1 Implémentation du modèle m-firm
7.4.2 Évaluation empirique du modèle m-firm
7.4.3 Implémentation de la QoS
7.4.4 Evaluation empirique des garanties de QoS
Conclusion
Conclusion générale
Bibliographie
