Soutenance mémoire
Architecture des systèmes embarqués
Un système embarqué comporte une partie matérielle formée d’un ensemble d’éléments physiques : processeur(s), mémoire(s) et entrées/sorties, une partie logicielle qui consiste en des programmes, et une source d’énergie. Les systèmes embarqués nécessitent parfois d’utiliser plusieurs processeurs pouvant être de types différents. Un premier classement des architectures pour système embarqué dépend du nombre de processeurs : architecture monoprocesseur ou multiprocesseur. Il existe différents classements pour les architectures multiprocesseurs :
20 Ordonnancement des systèmes temps réel embarqués
– homogène/hétérogène selon la nature des processeurs de l’architecture :
– identiques : les processeurs sont interchangeables et ont la même puissance de calcul ;
– uniformes : chaque processeur est caractérisé par sa puissance de calcul avec l’interprétation suivante : lorsqu’un travail s’exécute sur un processeur de puissance de calcul s pendant t unités de temps, il réalise s × t unités de travail ;
– indépendants : un taux d’exécution ri,j est associé à chaque couple travailprocesseur (Ji, Pj ), avec l’interprétation suivante : le travail ; le travail Ji réalise (ri,j × t) unités de travail lorsqu’il s’exécute sur le processeur Pj pendant t unités de temps. Dès lors la vitesse de progression sur un même processeur varie éventuellement d’un travail à l’autre ;
– homogène/hétérogène selon la nature des communications entre processeurs :
– homogène : les coûts de communication entre chaque paire de processeurs de l’architecture sont toujours les mêmes ;
– hétérogène : les coût de communication entre processeurs varient d’une paire de processeurs à une autre ;
– parallèle/distribuée selon le type de mémoire de l’architecture :
– parallèle : les processeurs communiquent par mémoire partagée ;
– distribuée : les processeurs ne partagent pas de mémoire et ont leur propre mémoire qui est ainsi dite distribuée. Ils communiquent par envoi/réception de messages.
Contraintes matérielles
Ces contraintes sont dues aux restrictions de ressources dans les systèmes embarqués. La puissance de calcul et la mémoire de ces systèmes sont limitées. Cela est dû aux limitations de poids, de volume (avions), de consommation d’énergie (véhicules), ou de prix. Parmi ces différentes contraintes, la gestion de la mémoire et la consommations sont les principales contraintes étudiées dans la littérature. L’accès aux mémoires reste toujours plus lent comparé à la vitesse des processeurs qui ne cesse de croître. Bien que la capacité mémoire dans les systèmes embarqués augmente, elle reste toujours insuffisante pour des applications qui deviennent de plus en plus complexes. Les premières techniques de gestion de la mémoire étaient manuelles comme la réservation de mémoire (instruction « malloc » en langage C) et comme la restitution de mémoire (instruction « free » en langage C). Des techniques automatiques où l’intervention de l’utilisateur est (quasi) nulle ont été introduites plus tard. Ces techniques restent plus complexes à mettre en œuvre. La complexité des systèmes embarqués ne cesse d’augmenter, ce qui engendre des consommations d’énergie de plus en plus élevées. La consommation d’énergie est un paramètre essentiel dans le développement des applications embarquées. L’utilisation de processeurs puissants cadencés à des fréquences élevées génère des consommations d’énergie élevées [Koc00]. Une technique importante de minimisation de la consommation d’énergie est basée sur la minimisation du « makespan » qui correspond au temps total d’exécution des tâches [LL08], afin d’utiliser des processeurs moins puissants pour avoir les mêmes résultats obtenus avec des processeurs puissants et qui consomment plus d’énergie [Ven06, Par02, Gar05,Koc00].
Tâches temps réel
Une tâche temps réel est une séquence d’instructions constituant l’unité de base d’un système temps réel. Les tâches réalisent des entrées/sorties et des calculs permettant de commander des procédés via un ensemble de capteurs et d’actionneurs, éventuellement tout ou rien, par exemple ensemble de tâches réalisant le contrôleur de vitesse d’une voiture ou le pilotage automatique d’un avion. Elles sont soumises à des contraintes temporelles qui doivent être respectées. Par exemple il faut désactiver avant un certain temps le contrôleur de vitesse d’une voiture lorsqu’on actionne les freins. On suppose que les caractéristiques temporelles sont des entiers non négatifs multiples d’unité de temps en général égale à la période de l’horloge du processeur. Les tâches périodiques se répètent indéfiniment et leurs instances sont séparées par une période constante. Une tâche périodique est activée par le déclenchement d’une interruption produite par un timer externe, à une date appelée date d’activation. Chaque instance s’exécute pendant une durée d’exécution maximale et doit terminer son exécution avant une échéance relative à sa date d’activation. Une tâche périodique est représentée par quatre paramètres : une date d’activation, un temps d’exécution maximum (pire cas), une échéance relative et une période. Les tâches apériodiques doivent s’exécuter au moins une fois et ne se répètent pas nécessairement indéfiniment. Une tâche apériodique est représentée par trois paramètres : une date d’activation, un temps d’exécution maximum et une échéance relative à sa date d’activation. Différents procédés d’ordonnancement de tâches apériodiques d’un système temps réel sont exposés dans [SSL89]. Les tâches sporadiques sont un cas particulier de tâches apériodiques. Ce sont des tâches qui se répètent indéfiniment avec une période minimum. En d’autres termes, deux instances peuvent être séparées d’une valeur plus grande que cette période minimum. Une tâche sporadique est représentée par quatre paramètres : une date d’activation, un temps d’exécution maximum, une échéance relative à sa date d’activation et une durée minimum entre deux activations successives de la tâche.
EDF (Earliest Deadline First)
Cet algorithme a été présenté par Jackson en 1955 [Jac55] puis par Liu et Layland en 1973 [LL73]. C’est un ordonnancement qui peut être préemptif ou non préemptif et est à priorité dynamique. Il s’applique à des tâches périodiques indépendantes et à échéance sur requête. Le principe d’allocation de priorités dans cet algorithme est que la tâche dont l’échéance absolue arrive le plus tôt aura la priorité la plus élevée. Les priorités sont réévaluées à chaque fois que l’ordonnanceur doit déterminer la prochaine tâche à exécuter. Par exemple lorsqu’une nouvelle tâche est activée et que son échéance est la plus proche comparée à celles des autres tâches prêtes à être exécutées.
Classification des fautes selon leurs sources
Les fautes et leurs sources sont extrêmement diverses. Les trois points de vue principaux selon lesquels on peut les classer sont leur nature, leur origine et leur persistance [Lap92]. La nature des fautes conduit à distinguer :
– les fautes accidentelles, qui apparaissent ou sont créées de manière fortuite,
– les fautes intentionnelles, qui sont créées délibérément, avec une intention qui peut être présumée nuisible. L’origine des fautes regroupe elle-même les points de vue suivants :
– la cause phénoménologique, qui conduit à distinguer :
– les fautes physiques, qui sont dues à des phénomènes physiques adverses.
– les fautes humaines, qui résultent d’imperfections humaines ;
– les frontières du système, qui conduisent à distinguer :
– les fautes internes, qui sont les parties de l’état du système qui, lorsqu’activées par les traitements, produiront une ou des erreurs,
– les fautes externes, qui résultent de l’interférence ou des interactions du système avec son environnement physique (perturbations électro magnétiques, radiation, température, vibrations, …) ou humain ;
– la phase de création par rapport à la vie du système, qui conduit à distinguer :
– les fautes de conception, qui résultent d’imperfections commises soit au cours du développement du système (de l’expression des besoins à la recette, y compris l’établissement des procédures d’exploitation ou de maintenance), soit au cours de modifications ultérieures,
– les fautes opérationnelles, qui apparaissent durant l’exploitation du système.
– La persistance temporelle conduit à distinguer :
– les fautes permanentes, dont la présence n’est pas reliée à des conditions ponctuelles, internes (processus de traitement) ou externes (environnement),
– les fautes temporaires, qui sont reliées à de telles conditions, et qui sont donc présentes pour une durée limitée.
|
Table des matières
Liste des figures
Liste des tableaux
Introduction générale
Contexte
Objectif
Plan général de la thèse
I État de l’art
1 Ordonnancement des systèmes temps réel embarqués
1.1 Systèmes temps réel embarqués
1.1.1 Caractéristiques
1.1.2 Architecture des systèmes embarqués
1.1.3 contraintes des systèmes temps réel embarqués
1.1.3.1 contraintes temporelles
1.1.3.2 contraintes matérielles
1.2 Ordonnancement de tâches temps réel
1.2.1 Tâches temps réel
1.2.1.1 Modèles de tâches
1.2.1.2 contraintes temps réel
1.2.2 Typologie des algorithmes d’ordonnancement
1.2.3 Algorithmes d’ordonnancement monoprocesseur
1.2.3.1 Préemptifs périodiques , apériodiques et sporadiques
1.2.3.2 Non préemptifs périodiques stricts
1.2.4 Algorithmes d’ordonnancement multiprocesseur
1.2.4.1 Approche globale
1.2.4.2 Approche partitionnée
1.2.4.3 Approche semi-partitionnée
1.3 Graphes d’algorithme et d’architecture
1.3.1 Graphe d’algorithme
1.3.2 Graphe d’architecture
1.4 Conclusion
2 Tolérance aux fautes des systèmes temps réel embarqués
2.1 Introduction
2.2 Terminologies de la tolérance aux fautes
2.2.1 Faute
2.2.2 Erreur
2.2.3 Défaillance
2.3 Tolérance aux fautes
2.3.1 Principes de la tolérance aux fautes
2.3.2 Tolérance aux fautes logicielles et matérielles
2.4 Redondances pour la tolérance aux fautes matérielles
2.4.1 Redondance logicielle
2.4.1.1 Redondance active
2.4.1.2 Redondance passive
2.4.1.3 Redondance hybride
2.4.1.4 Comparaison entre les trois types de redondance
2.4.2 Redondance matérielle
2.4.2.1 Généralités
2.4.2.2 Redondance modulaire triple
2.4.2.3 Cas général de la redondance modulaire
2.5 Conclusion
II Ordonnancement temps réel monoprocesseur
3 Ordonnancement temps réel monoprocesseur non préemptif périodique strict
3.1 Introduction
3.2 Stratégie d’ordonnancement
3.3 Analyse d’ordonnançabilité de tâches harmoniques
3.3.1 Arbre d’ordonnancement
3.3.2 Toutes les tâches ont des périodes distinctes
3.3.3 Certaines tâches ont des périodes identiques
3.3.4 Algorithme d’ordonnancement
3.4 Analyse d’ordonnançabilité de tâches non harmoniques
3.4.1 Conditions d’ordonnançabilité pour deux tâches
3.4.2 Conditions d’ordonnançabilité pour plus de deux tâches
3.4.2.1 Tâche candidate à période multiple du PGCD
3.4.2.2 Tâche candidate à période non multiple du PGCD
3.4.3 Tri des tâches selon les multiplicités de leurs périodes
3.4.4 Algorithme d’ordonnancement
3.5 Phase transitoire et phase permanente
3.6 Analyse de performances
3.6.1 Algorithme de génération de tâches
3.6.2 Simulations et discussion des résultats
3.7 Conclusion
4 Ordonnancement temps réel monoprocesseur combinant non préemptif et préemptif
4.1 Introduction
4.2 Combinaison de tâches NPPS et PP
4.2.1 Stratégie d’ordonnancement
4.2.2 Analyse d’ordonnançabilité
4.3 Ordonnancement de tâches préemptives périodiques strictes
4.3.1 Modèle de tâches
4.3.2 Analyse d’ordonnançabilité
4.4 Conclusion
III Ordonnancement temps réel multiprocesseur
5 Ordonnancement temps réel multiprocesseur non préemptif périodique strict
5.1 Introduction
5.2 Analyse d’ordonnançabilité
5.3 Déroulement
5.3.1 Périodicité et transfert de données
5.3.2 Algorithme de déroulement
5.4 Ordonnancement
5.4.1 Prise en compte des coûts de communications
5.4.2 Algorithme d’ordonnancement
5.5 Conclusion
6 Ordonnancement multiprocesseur non préemptif périodique strict tolérant aux fautes
6.1 Introduction
6.2 Présentation du problème de tolérance aux fautes
6.2.1 Modèle de fautes
6.2.2 Données du problème de tolérance aux fautes
6.2.3 Notations et définitions
6.3 Transformation de graphe pour la tolérance aux fautes
6.3.1 Tolérance aux fautes des processeurs
6.3.2 Tolérance aux fautes des bus de communication
6.3.3 Tolérance aux fautes des processeurs et des bus de communication
6.4 Ordonnancement tolérant aux fautes
6.4.1 Algorithme d’analyse d’ordonnançabilité
6.4.2 Algorithme de déroulement
6.4.3 Algorithme d’ordonnancement
6.5 Conclusion
IV Développements logiciels et application au CyCab
7 Développements du logiciel SynDEx
7.1 Méthodologie AAA et principes de SynDEx
7.2 Graphe d’algorithme et d’architecture
7.2.1 Algorithme
7.2.2 Architecture
7.2.3 Caractérisations temporelles
7.3 Mise à plat
7.4 Adéquation dans SynDEx V7
7.4.1 Analyse d’ordonnançabilité
7.4.2 Déroulement
7.4.3 Ordonnancement
7.5 Génération automatique de code
7.5.1 Génération de macro-code
7.5.2 Génération de code exécutable
7.6 Améliorations apportées à SynDEx
7.6.1 Adéquation
7.6.2 Extension de SynDEx à la tolérance aux fautes
7.7 Conclusion
8 Application au suivi automatique de CyCabs tolérant aux fautes
8.1 Histoire de la conduite automatique à l’INRIA
8.2 Caractéristiques générales du CyCab
8.3 Applications de commande de CyCabs
8.3.1 Application manuelle
8.3.2 Application automatique
8.4 Architecture à base de dsPIC et de bus CAN
8.4.1 Banc de test
8.4.2 Cycab tolérant aux fautes
8.5 Code source du dsPIC
8.6 Tolérance aux fautes sur le banc de test
8.6.1 Tolérance aux fautes des bus CAN
8.6.1.1 Détection d’erreurs
8.6.1.2 Traitement des erreurs détectées
8.6.2 Tolérance aux fautes des dsPICs
8.6.2.1 Détection d’erreurs
8.6.2.2 Traitement des erreurs détectées
8.7 Tolérance aux fautes sur le CyCab : application de suivi
8.7.1 Communication entre dsPICs et MPC555
8.7.2 Application SynDEx de base de suivi automatique de CyCabs
8.7.3 Tolérance aux fautes des bus CAN
8.7.4 Tolérance aux fautes des dsPICs
8.8 Conclusion
Conclusion générale et perspectives
Conclusion générale
Perspectives
V Annexes
A PC embarqué Linux/RTAI, microcontrôleurs MPC555 et dsPIC33
A.1 PC embarqué
A.2 Microcontrôleur MPC555
A.3 Microcontrôleur dsPIC33FJ128MC708
B Code source des dsPIC pour les communications inter-processeurs
C Programmation des dsPICs pour la tolérance aux fautes
C.1 Tolérance aux fautes sur le banc de test
C.1.1 Tolérance aux fautes des bus CAN
C.1.1.1 Détection d’erreurs
C.1.1.2 Traitement des erreurs détectées
C.1.2 Tolérance aux fautes des dsPICs
C.1.2.1 Détection d’erreurs
C.1.2.2 Traitement des erreurs détectées
C.2 Tolérance aux fautes sur le CyCab
C.2.1 Communication entre dsPICs et MPC555
Télécharger le rapport complet
