Systèmes temps réel et ordonnancement

Systèmes temps réel et ordonnancement

Systèmes temps réel

Les systèmes temps réel sont des systèmes informatiques soumis à des contraintes temporelles en plus des contraintes de correction fonctionnelles usuelles. On distingue trois grands types de systèmes temps réel, compte tenu de l’aspect« respect des contraintes temporelles» :
•Les systèmes Temps-Réel àcontraintes strictes; on parle de contraintes strictes quand on a des contraintes dont le non respect peut avoir des conséquences graves (catastrophes humaines, économiques ou écologiques).
•Les systèmes Temps-Réel à contraintes relatives; on parle de contraintes relatives quand leur non respect est tolérable dans une certaine mesure.
• Les systèmes Temps-Réel à contraintes mixtes qui contiennent des contraintes temporelles strictes et relatives. Un système temps réel doit donc permettre la réalisation des applications temps réel qui possèdent des contraintes temporelles strictes. Les applications temps réel sont structurées en tâches c’est à dire en un flot de contrôle.

Architecture physique et exécutif

Architecture physique

Un système temps réel repose sur un ou plusieurs processeurs pour effectuer les traitements (Figure 1). Il est décomposé en noeuds correspondant à un processeur et aux traitements sur ce processeur au cours de la vie du système. Les architectures matérielles pour le temps réel sont caractérisées par l’importance des entrées-sorties.

Exécutif temps réel

Un exécutif temps réel est un système d’exploitation multitâches dans lequel la durée d’exécution de toute fonction système est documentée (ou bien au moins prédictible et connue). L’exécutif est chargé de faire le lien entre les applications, qui devraient être indépendantes de II.! plate-forme support, et l’architecture physique de la plate forme support.

Ordonnancement temps réel

Le problème de l’ordonnancement temps réel est la définition d’une politique d’attribution du processeur qui respecte les contraintes temporelles de l’application. TI faut donc définir une stratégie et ensuite prouver que les contraintes temporelles sont bien respectées. Ceci peut passer par la construction d’une séquence temporelle de l’ensemble des tâches à exécuter. Cette construction nécessite la définition d’un algorithme d’ordonnancement. De nombreuses études ont été faites sur ce sujet [Cottet et al, 2000J, [Dertouzos et Mok, 89], [Yingfeng et Sang, 95], [Goossens et Devillers,1997J, [Choquet-Geniet et al, 2000]. Mais avant la présentation de ces travaux nous allons donner quelques définitions:

Définition : La séquence d’ordonnancement délivrée est valide si toutes les tâches de la configuration respectent leurs contraintes.
Défnition : Une configuration de tâches est ordonnançable dès qu’il existe au moms un algorithme capable de fournir une séquence valide pour cette configuration. Le test d’ordonnançabilité sert à vérifier qu’une configuration de tâches périodiques donnée soumise à un algorithme d’ordonnancement peut être ordonnancée selon une séquence valide.
Défnition [Choquet-Geniet, 2003]: Algorithme d’ordonnancement optimal Soit T une classe d’applications. Un algorithme d’ordonnancement est dit optimal (éventuellement parmi une sous-famille d’ordonnancements) pour les applications de la classe T si et seulement si quelle que soit l’application de la classe, soit l’algorithme l’ordonnance de manière correcte, soit aucun autre algorithme (de la sous famille) ne le pourra. Selon le degré de connaissance que le système peut avoir des caractéristiques des tâches avant son démarrage et selon l’architecture physique du système plusieurs types d’algorithmes d’ordonnancement peuvent être employés: Les algorithmes peuvent être en ligne ou hors ligne, préemptifs ou non préemptifs, centralisés ou répartis. Pour les algorithmes hors ligne, la construction de la séquence d’exécution est réalisée avant la mise en exploitation du système tandis que pour les algorithmes en ligne, la séquence peut être modifiée si une nouvelle tâche devient prête. Un certains nombre de travaux ont permis d’obtenir des résultats pour l’ordonnancement temps réel de tâches périodiques ou apériodiques que ce soit avec préemption ou non. Parmi ces résultats on a le théorème suivant démontré par Labetoulle .

Ordonnancement des tâches indépendantes

Un grand nombre d’algorithmes d’ordonnancement temps réel est conduit par la notion de priorité qui les amène à ordonnancer dans la liste des tâches prêtes, la tâche qui possède la plus grande priorité. La priorité peut être fixe ou statique si elle est fixée à l’initialisation et si elle reste constante pendant toute la durée de vie de la tâche. Si la priorité évolue dans le temps, elle est dite dynamique. La notion d’optimalité est en générale réduite à la classe à laquelle appartient l’algorithme. Aussi on peut parler d’algorithme optimal dans la classe des algorithmes statiques ou dynamiques.

Algorithmes en ligne à priorités constantes

Rate Monotonie ( RM )

C’est un algorithme qui est basé sur la priorité statique et qui est optimal parmi les algorithmes à priorités fixes pour les applications constituées de tâches indépendantes à échéances sur requête et à départs simultanés. Un tâche a une priorité fixe qui est inversement proportionnelle à sa période. L’algorithme a été introduit par [Liu et Layland, 1973] .

Inverse Deadline (ID) ou Deadline Monotonie (DM)

La politique de cet algorithme attribue la priorité la plus forte à la tâche de plus petit délai critique c’est à dire le temps de réponse maximal toléré. Cet algorithme est optimal parmi les algorithmes à priorités fixes pour les applications constituées de tâches indépendantes à départs simultanés [Choquet-Geniet, 2003]. Les algorithmes RM et ID coïncident si les tâches sont àéchéance sur requête d’après [Choquet Geniet, 2003] et une condition suffisante d’acceptabilité des tâches est U91(2un-l). Les tâches àéchéance sur requête sont les tâches pour lesquelles D=T.

Le rapport de stage ou le pfe est un document d’analyse, de synthèse et d’évaluation de votre apprentissage, c’est pour cela chatpfe.com propose le téléchargement des modèles complet de projet de fin d’étude, rapport de stage, mémoire, pfe, thèse, pour connaître la méthodologie à avoir et savoir comment construire les parties d’un projet de fin d’étude.

Table des matières

1. Introduction
II. Etat de l’art
II.1 Systèmes temps réel et ordonnancement.
II.1.1 Systèmes temps réel.
n.l.l.1 Caractéristiques des tâches
II. 1.1.2 Architecture physique et exécutif
II.1.1.2.1 Architecture physique
II.1.2 Ordonnancement temps réel
II.l.2.l Ordonnancement des tâches indépendantes
II.l.2.1.1 Algorithmes en ligne à priorités constantes
n.l.2.1.1.1 Rate Monotonie (RM)
n.1.2. 1.1.2 Inverse Deadline (ID) ou Deadline Monotonie (DM)
II.1.2.1.2 Algorithmes en ligne à priorités variables
n.1.2.1.2.1 Earlieste Deadline (ED)
II.1.2.1.2.2 I..east Laxity (LL)
II. 1.2.2 Ordonnancement des tâches dépendantes
II.1.2J Complexité de l’ordonnancement multiprocesseurs
II.2 Etude de la cyclicité
II.2.1 Système de tâches indépendantes
II.2.2 Système de tâches quelconques
II.2.3 Cyclicité en environnement multiprocesseurs
III. Description du travail effectué
III.1 Modélisation des tâches
111.1.1 Modèle temporel des tâches
111.1.2 Hypothèses sur la configuration de tâches
111.2 Outils
m.2.1 Le générateur aléatoire d’applications
lII.2.2 L’ordonnanceur d’application
lIL2.2.1 Calcul de l’ensemble « Ready » des tâches prêtes
111.2.2.2 Calcul des priorités des tâches
III.2.2.2.1 Calcul des priorités selon RM
111.2.2.2.2 Calcul des priorités selon ED
1I1.2.2.2.3 Calcul des priorités selon L1.
111.2.2.3 Placement des tâches
1IIJ Calcul de la date d’entrée en phase cyclique
111.4 Expérimentation
IV. Etude
IV.1 Temps creux acycliques
N.2 Dates d’entrée en phase cyclique
N.3 Conclusion de la partie étude
V. Conclusions