INFORMATIQUE DES

SYSTEMES TEMPS REELS

Cours 3
III. Ordonnancement de Tâches
Périodiques Préemptif à
Priorités Fixes
1.Introduction
2.Ordonnancements A
priorité Fixe
 Rate-Monotonic
(RM)
 Deadline Monotonic
(DM)
 1. Introduction
Dans la littérature, le terme tâche est souvent préféré pour signifier,
la périodicité ou la manière cyclique d'exécution que celui du
processus dont l'aspect est attaché plutôt, au sens de l'unicité de la
demande d'exécution.
Les tâches doivent entre autres respecter des délais critiques
imposés par les dynamiques de l'environnement à contrôler. D'un
point de vue temporel, les paramètres suivants peuvent caractériser
une tâche :
La date de réveil : qui correspond à l'instant à partir duquel la tâche
peut commencer son exécution,
ˆ La durée d'exécution : égale à la borne supérieure du temps
processeur nécessaire à l'exécution de la tâche,
ˆ Le délai critique : qui est l'intervalle de temps, à partir de la
date de réveil, durant lequel la tâche doit s'exécuter. En dehors de
cet intervalle, son exécution devient inutile.
ˆ La période : est l'intervalle de temps fixe qui sépare les
arrivées successives d'une tâche. Ce paramètre concerne les tâches
activées par un signal périodique provenant d'une horloge temps réel
interne, c'est le cas par exemple de l'acquisition de données. Ce type
de tâches est appelé tâches périodiques.
 2. Ordonnancements A priorité
Fixe

Cette sous-partie présente les algorithmes qui

appartiennent à la famille des algorithmes
d'ordonnancement à priorité fixe.

Chaque tache a une certaine priorité, dont héritent ses

travaux, et qui est dénie avant l'exécution du système et
qui ne varie pas au cours de la vie du système.

Généralement, l'ordonnancement est préemptif, mais ce

n'est pas une obligation.

En l'absence de précision, l'ordonnanceur présenté sera

considéré comme préemptif.
 A. Rate-Monotonic (RM) / Ordonnancement à taux
monotone
L'ordonnanceur Rate Monotonic (RM) est un
ordonnanceur à priorité fixe. La priorité des taches est
fonction de leur période. Plus précisément, plus la
période est petite et plus la tache est prioritaire.
RM
préemptif
On peut dire que Rate Monotonic (RM) est un algorithme
qui est basé sur des priorités statiques et qui est
optimal. Une tâche dispose d'une priorité fixe qui est
inversement
Condition
proportionnelle à la période.
suffisante
L'ordonnancement Rate Monotonic d'un ensemble de n
tâches périodiques est faisable si le facteur d'utilisation
U vérifie la relation suivante :
Pour avoir un meilleur ordre de grandeur, il est
intéressant de calculer la limite de cette fonction pour n
qui devient grand. On trouve que pour n > 5, la valeur
obtenue est déjà très proche de la limite, à savoir
environ 0,7.

Enfin, si les périodes des taches sont harmoniques, alors

la condition suffisante d'ordonnancabilité de RM
devient :
Caractéristiques du RM

Le Rate monotonic a été introduit par Liu and Layland en

1973.
- Basé sur les priorités
- Priorités fixes
- Les tâches sont périodiques :
 pas de communication,
 temps de commutation négligeable
- L'échéance correspond à la période (Di =Pei )
- Complexité faible et implémentation facile dans un OS
- Algorithme optimal dans la classe des algorithmes à
priorité fixe si la(les) condition(s) d'ordonnançabilité
sont satisfaites :
- On calcule la priorité de chaque tâche comme suit :
Puis l'ordonnanceur sélectionne le processus avec la plus
haute priorité.
Conditions d'ordonnançabilité : Pour qu'un ensemble de
tâches soit ordonnançable pour le Rate-Monotonic, il
suffit que :

Le tableau suivant donne les valeurs de U pour un

nombre de tâches de 1 à 10 :
 B. Deadline Monotonic (DM)

L'ordonnanceur Deadline Monotonic est un ordonnanceur

à priorité fixe avec pour priorité l'échéance relative de la
tâche. Plus l'échéance est petite et plus la tache est
prioritaire. L’affectation des priorités est optimale pour
des systèmes de taches synchrones à échéance
contrainte. Dans le cas des systèmes à échéances
implicites, Deadline Monotonic et Rate Monotonic se
confondent. La condition suffisante pour DM pour des
systèmes de taches à échéance contrainte, donnée par
l'équation suivante, est similaire à celle de RM.

U(1) = 1 ; U(2) = 0,828 ; U(3) = 0,779 ; U (1) = ln2

≈ 0,693
Deadline Monotonic est un algorithme à priorité fixe
proche de Rate Monotonic à ceci près qu'il affecte à une
tâche une priorité inversement proportionnelle au délai
critique.
L'ordonnancement à priorités fixes

Intérêts :
- Mécanisme simple
- S'implante naturellement dans les OS du marché
Inconvénients :
- Hypothèses restrictives
- Indépendance des tâches impérative pour l'utilisation
des conditions de faisabilité
- Borne supérieure pour le facteur d'utilisation du
processeur
INFORMATIQUE
DES SYSTEMES
TEMPS REELS
Cours 4
 IV. Ordonnancement
de Tâches Périodiques
Préemptif à Priorités
Dynamiques
1.Introduction
2.Earliest Deadline First (EDF)
3.Least Laxity First (LLF)
 Avantage et inconvénient
4.Ordonnancement en situations de
surcharge
 Introduction

Nous avons jusqu'à présent considéré que la priorité

affectée à une tâche restait constante pendant toute la
durée de l'application. Nous allons nous intéresser à une
autre catégorie d'algorithme d'ordonnancement pour
laquelle la priorité des tâches varie au cours de
l'exécution d'une tâche. Cette priorité est fonction d'une
caractéristique temporelle dynamique de la tâche.
 A. Earliest Deadline First (EDF)
L'algorithme d'ordonnancement EDF a été
introduit par Lui et Layland en 1973. C'est un
algorithme d'ordonnancement qui peut être
préemptif ou non préemptif et qui s'applique à
des tâches périodiques indépendantes à
échéance sur requête (Ti= Di).
La plus grande priorité à la date t est allouée à la
tâche dont l'échéance absolue est la plus proche.
EDF est optimal pour les tâches indépendantes
préemptibles. Une condition d'ordonnançabilité
nécessaire et susante de EDF pour un ensemble
de tâches périodiques à échéance sur requête
noté Γn est donnée par :
Earliest deadline first scheduling ("échéance proche =
préparation en premier") est un algorithme d'ordonnancement
préemptif, à priorité dynamique, utilisé dans les systèmes
temps réel. Il attribue une priorité à chaque requête en
fonction de l'échéance de cette dernière selon la règle : Plus
l'échéance d'une tâche est proche, plus sa priorité est grande.
De cette manière, au plus vite le travail doit être réalisé, au
plus il a de des
La priorité chances d'être
tâches exécuté.au cours de leur exécution
est variable
et fonction de la prochaine échéance. Pour une instance k
d'une tâche Ti, la priorité est liée à la prochaine échéance di;k
de cette tâche. À un instant t, la priorité peut être calculée à
partir du délai critique dynamique Di(t) qui s'exprime sous la
forme :
Nous pouvons faire les deux remarques suivantes :
• La priorité est variable, elle change au cours de l'exécution ;
• La priorité augmente si le délai critique dynamique de la tâche diminue.
Ce qu'il faut retenir
 Principe : à chaque instant, la tâche la plus prioritaire est
celle dont l'échéance absolue di est la plus proche
 Propriété : EDF est optimal dans la classe des algorithmes
préemptifs pour des tâches périodiques indépendantes
telles que Di ≤ Ti
 Condition de faisabilité : Si Di = Ti :

 Condition suffisante :
 B. Least Laxity First (LLF)
L'algorithme d'ordonnancement LLF se base sur la laxité.
La tâche dont la laxité est la plus faible comparée à toutes
les tâches prêtes aura la plus grande priorité. Cet
algorithme est optimal pour les tâches indépendantes
préemptibles.
D'après ce qui précède, la condition d'ordonnançabilité de
LLF et celle de EDF sont les mêmes. C'est-à-dire que la
condition d'ordonnançabilité nécessaire et susante de LLF
pour un ensemble de tâches périodiques à échéance sur
requête Γn est donnée par :

NB: La laxité LA est l'écart maximal entre la date

d'activation de la tâche A et sa date de démarrage de sorte
que l'échéance DA soit respectée.
Lorsque plusieurs tâches possèdent la même laxité,
l'algorithme LLF a l'inconvénient d'engendrer un grand
nombre de préemption ce qui explique qu'il soit aussi peu
utilisé dans le cas de monoprocesseur.

- Principe : à chaque instant, la tâche la plus prioritaire est

celle dont la laxité
L(t) = ri + Di - (t + Ci(t))

Marge = échéance - durée restante de traitement-temps

courant
(Marge la plus courte d'abord)
-Propriété : LLF est optimal dans la classe des algorithmes
préemptifs pour des tâches périodiques indépendantes
telles que Di ≤ Ti
Ce qu'il faut retenir

 Condition de faisabilité : Si Di = Ti :

 Condition suffisante :
 Avantage et inconvénient

Intérêts :

- Simplicité de mise en œuvre

- Optimisation de l'usage des ressources
- Bien adapté aux tâches périodiques à courtes
échéances

Inconvénients :

- Indépendance des tâches impératives pour l'utilisation

des conditions de faisabilité
- Instabilité en cas de surcharge (EDF)
- Nombreux changements de contexte dans certains cas
(LLF)
- Difficilement implantable dans les OS actuels
 Ordonnancement en situations
de surcharge
Quand la charge du processeur est telle qu'il est impossible
de respecter toutes les échéances.
Origines possibles multiples:
 matériel, par exemple une transmission défectueuse qui fait
qu'un signal arrive en retard (réseau surchargé)
 contention sur une ressource critique
 réveil de tâches apériodiques suite à des alarmes

Les algorithmes à priorités classiques (du type EDF ou RMA)

offrent des performances souvent médiocre en cas de
surcharge
Effet "domino" dû à l'arrivée d'une tâche supplémentaire
dans un ordonnancement EDF