Aperçu sur les systèmes temps réel

Les systèmes embarqués sont de plus en plus présents dans notre vie quotidienne et connaissent actuellement un essor considérable. Ces systèmes sont caractérisés par une forte interaction avec les procédés contrôlés dans lesquels sont enfouis et par leurs autonomies de fonctionnement, dont l’alimentation est assurée par des batteries [Akl,09]. En plus, de tels systèmes nécessitent généralement des tâches avec des priorités représentant leurs degré d’urgence temporelle qui se synchronisent les unes aux autres, et qui collaborent pour réaliser les objectifs attendus du système. Cette collaboration se fait par l’échange de données et/ou par le partage de ressources. Cependant, cette collaboration engendre des contraintes de précédence et/ou de partage des ressources. Le problème de l’ordonnancement temps réel des tâches soumises à des contraintes temporelles (échéance) et sous contraintes de disponibilité des ressources requises (ressources partagées) dans les systèmes embarqués, a été largement étudié. Les obstacles récemment rencontré dans cette situation sont l’interblocage, l’inversion de priorité,…etc. Le problème d’inversion de priorité se rencontre dans un grand nombre d’applications industrielle (chaine de production), informatiques (programmation concurrente), aérospatial (mission Mars pathfinder 1997), …etc. Dans ce problème, il s’agit ordonnancer des tâches, sur des ressources à accès exclusives (sections critique). Les tâches sont liées entre eux par des relations de partage de ressource, qui expriment qu’une tâche à la fois doit entrer en section critique. Donc, la tâche Ti de plus haute priorité ne peut pas prendre une ressource Rk déjà allouée à une autre tâche Tj tant qu’elle n’est pas libérée.

Aperçu sur les systèmes temps réel 

En informatique industrielle, on parle d’un système temps réel lorsque ce système informatique contrôle (ou pilote) un procédé physique à une vitesse adaptée à l’évolution du procédé contrôlé [Liu,00]. Un système temps réel est toujours décomposé en tâches, chacune ayant des fonctionnalités, des temps d’exécution et des échéances différentes. Ce qui implique que certaines parties des systèmes doivent fonctionner parfaitement car le non respect de quelques contraintes peut conduire à des dégâts matériels et même humaines. La caractéristique la plus importante d’un système temps réel est les restrictions imposées sur le temps de réponse [Bad,08].

Terminologies

– Échéance : est une contrainte temps à laquelle doit au plus tard se produire un événement [DEM&BON,99].
– Prévisibilité : capacité à déterminer le temps des opérations à réaliser [DEM&Bon,99].
– Déterminisme: objectif à atteindre pour connaître le temps d’exécution d’un programme [DEM&Bon,99].
– Contrainte de temps : limite quantifiée sur le temps séparant deux évènements (limite min et/ou max).
– Temps réel : le temps nécessaire pour résoudre un problème ou accompli un travail.

Définition

J. A. Stankovic définit un système temps réel dans [Sta,88] comme suit : « The correctness of the system depends not only on the logical results of computation, but also on the time at which the results are produced », en français, un système dont le comportement dépend non seulement de l’exactitude du traitement effectué, mais également du temps où les résultats de ces traitements sont produits.

Le STR et son environnement 

Les systèmes temps réel sont des systèmes qui possèdent des contraintes temporelles fortes. Lors de l’arrivée d’un stimulus en provenance de l’environnement externe, le système doit réagir dans un délai donné [Sta,88]. La prise en compte de stimulus différents, induit un parallélisme lors de la conception de tels systèmes selon une logique « événementcondition-action ». La conception aboutit généralement à un logiciel formé d’un ensemble de modules synchronisées, communicants et partageant des ressources critiques [Sta,88].

Les capteurs scrutent les événements du système contrôlé, fournissent des mesures, … [DEM&Bon, 99]. Les actionneurs agissent sur le fonctionnement en fonction des traitements du STR sur le système contrôlé [DEM&Bon, 99].

Caractéristiques des STR

Les systèmes temps réel et notamment à contraintes dures doivent répondre à trois critères fondamentaux [DEM&Bon,99] :
1) L’exactitude logique : (exactitude des traitements)
Les mêmes entrées appliquées au système produisent les mêmes résultats.
2) L’exactitude temporelle 
Les temps d’exécution de tâches est déterminé (les délais sont connus ou bornés et le retard est considéré comme une erreur qui peut entraîner de graves conséquences).
3) La fiabilité : (aspect matériel)
Le système répond à des contraintes de disponibilité (matériel/logiciel).

Classification des STR

Classement selon l’environnement 

Systèmes embarqués (enfouis) 

Le concept système embarqué (Embedded system en anglais) désigne un système informatique réactif, autonome dans lequel le processeur/calculateur est intégré (enfoui ou embarqué) dans un système plus large et/ou que le logiciel est entièrement dédié à une application donnée. Le système embarqué est en forte interaction avec l’opérateur et avec le procédé contrôlé dans lequel il est intégré. Cette interaction se fait via un ensemble de périphériques d’entrées/sorties appelés capteurs/actionneurs .

Systèmes répartis (distribués)
Un système réparti est un ensemble de machines autonomes connectées par un réseau, et équipées d’un logiciel dédié à la coordination des activités du système ainsi qu’au partage de ses ressources [Cou,Dol,Kin,94].

Classement selon l’échéance 

Les systèmes temps réel sont classifiés par rapport à la tolérance aux échéances [DEM&Bon,99] :

STR à contrainte strict ou dur (Hard Realtime)
Dans ce cas l’arrivée après échéance d’un évènement attendu ne doit pas se produire c’est-à-dire toutes les échéances doivent être garanties. Parce que le dépassement des échéances cause la défaillance de l’application suivie par celle du système. Par exemple, dans le système de contrôle d’une centrale nucléaire, une défaillance peut avoir des conséquences catastrophiques, telles que la mise en danger de vies humaines et des bouleversements écologiques. Etant données les conséquences du non respect des contraintes temporelles dans les systèmes temps réel strict, il est nécessaire de vérifier avant l’exécution de tels systèmes que les contraintes temporelles seront toujours respectées [Ban,Cuy,Liv,Cab,Rou,Wei,Pua,Dec,02].

Cette vérification est menée par des méthodes d’analyse d’ordonnancement, qui nécessitent la connaissance du pire comportement temporel du système. En général, il s’agit d’un temps d’exécution pire-cas ou WCET (pour Worst Case Execution Time) [Dec,03].

STR à contrainte souple ou mou (Soft Realtime)
Dans ce cas l’arrivée exceptionnelle après échéance d’un évènement attendu ne mettra pas le système en danger c’est-à-dire quelques échéances peuvent ne pas être respectées, de manière occasionnelle. Les exemples typiques d’applications ayant des contraintes temps réel souples sont les applications multimédias. On parle alors de la qualité de service QOS (Quality Of Service), c’est à dire le nombre de traitements qui respectent leurs échéances. Dans ce type de système, on cherche à minimiser le nombre de fautes temporelles des tâches [Akl,09].

STR à contrainte mixte ou hybride (Firm Realtime)
Ce sont des systèmes temps réel à contraintes dur où une faible probabilité de manquer les limites temporelles peut être tolérée. La problématique dans ce contexte est d’éliminer d’une part toute possibilité de fautes temporelles pour les tâches strictes, et de minimiser les fautes temporelles pour les tâches à contraintes souples [Akl,09].

Table des matières

Introduction générale
Chapitre I Aperçu sur les systèmes temps réel
I.1 Introduction
I.2 Terminologies
I.3 Définition
I.4 Le STR et son environnement
I.5 Caractéristiques des STR
I.6 Classification des STR
I.6.1 Classement selon l’environnement
I.6.1.1 Systèmes embarqués (enfouis)
I.6.1.2 Systèmes répartis (distribués)
I.6.2 Classement selon l’échéance
I.6.2.1 STR à contrainte strict (Hard Realtime)
I.6.2.2 STR à contrainte souple (Soft Realtime)
I.6.2.3 STR à contrainte mixte ou hybride (Firm Realtime)
I.7 Domaines d’applications
I.8 le jeu de tâches temps réel
I.8.1 Définition d’une tâche temps réel
I.8.2 Les paramètres typiques d’une tâche Ti
I.8.3 Le cycle de vie et la gestion des tâches temps réel
I.8.4 les modèles de tâches
I.8.4.1 Les tâches périodiques
I.8.4.2 Les tâches sporadiques
I.8.4.3 Les tâches apériodiques
I.8.4.4 les tâches dépendantes
I.8.4.5 les tâches indépendantes
I.9 Conclusion
Chapitre II Ordonnancement temps réel des tâches
II.1 Introduction
II.2 Définition
II.3 Objectifs
II.4 Contexte d’ordonnancement
II.4.1 Définition
II.4.2 Communication
II.4.3 Architecture cible
II.5 Test d’ordonnancement et notion d’ordonnançabilité
II.6 Politiques d’ordonnancement
II.6.1 Présentation
II.6.1.1 Ordonnancement en ligne
II.6.1.1.1 Ordonnancement de tâches indépendantes
II.6.1.1.1.1 Algorithmes à priorité fixe (statique)
II.6.1.1.1.2 Algorithmes à priorité variable (dynamique)
II.6.1.1.2 Ordonnancement de tâches dépendantes
II.6.1.1.2.1 Ordonnancement avec des contraintes de précédences
II.6.1.1.2.2 Ordonnancement des tâches périodiques sous contraintes de ressources
II.6.1.1.2.3 Ordonnancement des tâches sous contraintes de ressources et de précédences
II.6.1.1.3 Avantages
II.6.1.1.4 Inconvénients
II.6.1.2 Ordonnancement hors ligne
II.6.1.2.1 Les algorithmes d’ordonnancements
II.6.1.2.2 Avantages
II.6.1.2.3 Inconvénients
II.6.2 Validation
II.7 Conclusion
Chapitre III État de l’art sur le phénomène d’inversion de priorité
III.1 Introduction
III.2 La problématique
III.3 Définitions
III.3.1 Priorité des taches
III.3.2 Inversion de priorité
III.4 Exemple illustratif
III.5 Remèdes au problème
III.5.1 L’héritage des priorités
III.5.1.1 PIP (Priority Inheritance Protocol)
III.5.1.1.1 Principe
III.5.1.1.2 Règles d’ordonnancements
III.5.1.1.3 Exemple
III.5.1.1.4 Caractéristiques
III.5.1.1.5 Avantages
III.5.1.1.6 Inconvénients
III.5.2 Protocoles à plafond de priorité (PCP : Priority Ceiling Protocols)
III.5.2.1 OCPP (Original Ceiling Priority Protocol)
III.5.2.1.1 Principe
III.5.2.1.2 Règles d’ordonnancements
III.5.2.1.3 Exemple
III.5.2.1.4 Caractéristiques
III.5.2.1.5 Avantages
III.5.2.2 ICPP (Immediate Ceiling Priority Protocol)
III.5.2.2.1 Principe
III.5.2.2.2 Exemple
III.5.2.2.3 Caractéristiques
III.5.2.2.4 Avantages
III.5.2.2.5 Inconvénients
III.5.3 Stack Resource
III.5.3.1 SRP (Stack Resource Policy)
III.5.3.1.1 Principe
III.5.3.1.2 Règle d’ordonnancements
III.5.3.1.3 Exemple
III.5.3.1.4 Caractéristiques
III.5.3.1.5 Avantages
III.5.3.1.6 Inconvénients
III.6 Etude comparatif
III.7 Exemple concret
III.8 Conclusion
Chapitre IV Le protocole CDP proposé
IV.1 Introduction
IV.2 L’objectif
IV.3 Notations
IV.4 L’outil de gestion du temps
IV.5 Le protocole CDP
IV.5.1 Le principe du CDP
IV.5.2 Les règles d’ordonnancement proposés pour CDP
IV.5.3 Exemples d’applications
IV.5.4 Les caractéristiques du CDP
IV.5.5 Avantages
IV.5.6 Désavantages
IV.6 Étude comparative
IV.6.1 L’exemple avec les priorités des tâches assignées
IV.6.2 L’exemple avec PIP (Priority Inheritance Protocol)
IV.6.3 L’exemple avec OCPP (Original Ceiling Priority Protocol)
IV.6.4 L’exemple avec ICPP (Immediate Ceiling Priority Protocol)
IV.6.5 L’exemple avec SRP (Stack Resource Policy)
IV.6.6 L’exemple avec CDP (Ceiling Dynamic Protocol)
IV.7 Comparaison des résultats
IV.8 Conclusion
Conclusion générale

Lire le rapport complet