Chapitre 3:

Ordonnancement
Temps Réel

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 1
Introduction
● Tâches temps réel soumises à des contraintes de temps,
plus ou moins strictes
➢ instant de démarrage
➢ instant de fin
➢ absolus ou relatifs à d'autres tâches
● le but de l'ordonnancement est de permettre le respect
de ces contraintes, lorsque l'exécution se produit dans
un mode courant
● il doit permettre de borner les effets d'incidents ou de
surcharges

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 2
Caractéristiques des tâches (1)
● r : date de réveil
moment du déclenchement de la 1ère requête d'exécution
● C : durée d'exécution maximale (capacité)
● D : délai critique
➢ délai maximum acceptable pour son exécution
● P : période (si tâche périodique)
● d = r+D : échéance (si tâche à contraintes strictes)
● tâche périodique : rk = r0 + k*P
➢ si D = P, tâche à échéance sur requête
P P
D
t
r C d r d r
0 0 1 1 2
F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 3
Caractéristiques des tâches (2)
● paramètres statiques
➢ U = C/P : facteur d'utilisation du processeur
➢ CH = C/D : facteur de charge du processeur
● paramètres dynamiques
➢ s : date du début de l'exécution
➢ e : date de la fin de l'exécution
➢ D(t) = d-t : délai critique résiduel à la date t (0 ≤ D(t) ≤ D)
➢ C(t) : durée d'exécution résiduelle à la date t (0 ≤ C(t) ≤ C)
➢ L = D-C : laxité nominale de la tâche
✔
retard maximum pour son début d'exécution s (si elle est
seule)
➢ L(t) = D(t) - C(t) : laxité nominale résiduelle
✔
retard maximum pour reprendre l'exécution
➢ TR = e - r : temps de réponse de la tâche
➢ CH(t) = C(t)/D(t) : charge résiduelle (0 ≤ CH(t) ≤ C/P)
F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 4
Caractéristiques des tâches (3)
● préemptibles ou non
● dépendance ou indépendance
➢ ordre partiel prédéterminé ou induit
➢ partage de ressources
● priorité externe
➢ ordonnancement hors ligne déterminé à la conception
● gigue (jitter) maximale
➢ variation entre la requête et le début de l'exécution
● urgence ↔ échéance
● importance

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 5
États d'une tâche

Courante

Bloquée Prête

f
f
Inexistante Passive

f : abandon de la requête pour cause de faute temporelle

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 6
Définitions
● configuration : ensemble de n tâches mises en jeu par
l'application
➢ facteur d'utilisation du processeur

➢ facteur de charge
● intervalle d'étude : intervalle de temps minimum pour
prouver l'ordonnançabilité d'une configuration
➢ le PPCM des périodes dans le cas d'une configuration
de tâches périodiques
● laxité du processeur LP(t) = intervalle de temps pendant
lequel le processeur peut rester inactif tout en
respectant les échéances
✔
laxité conditionnelle
(somme sur les tâches déclenchées à la date t et qui
sont devant i du point de vue de l'ordonnancement)
✔ LP(t) = min(LCi(t))
F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 7
Buts de l'ordonnancement
● piloter l'application avec 2 objectifs majeurs :
➢ en fonctionnement nominal : respect des contraintes
temporelles
➢ en fonctionnement anormal (par exemple pannes
matérielles) : atténuer les effets des surcharges et
maintenir un état cohérent et sécuritaire
● ordonnancer = planifier l'exécution des requêtes de façon
à respecter les contraintes de temps
➢ de toutes les requêtes en fonctionnement nominal
➢ d'au moins les requêtes les plus importantes (c'est-à-
dire celles nécessaires à la sécurité du procédé) en
fonctionnement anormal

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 8
Typologie des algorithmes
● en ligne ou hors ligne
➢ choix dynamique ou prédéfini à la conception
● préemptif ou non préemptif
➢ une tâche peut perdre le processeur (au profit d'une
tâche plus prioritaire) ou non
➢ algorithme préemptif ⇔ toutes les tâches préemptibles
● stratégie du meilleur effort ou inclémence
➢ en TR mou, meilleur effort = faire au mieux avec les
processeurs disponibles
➢ en TR dur, obligation des respecter les contraintes
temporelles : inclémence aux fautes temporelles
● centralisé ou réparti

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 9
Plan du cours
● ordonnancement des tâches indépendantes
● ordonnancement des tâches dépendantes
➢ partage de ressources
➢ contraintes de précédence
● ordonnancement en cas de surcharge

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 10
Ordonnancement des
tâches indépendantes

11
Introduction
● tâches indépendantes :
➢ pas de partage de ressources
➢ pas de contraintes de précédence
● cas des algorithmes en ligne
➢ dynamique
➢ sur la base d'une priorité définie
✔
soit de manière empirique
✔
soit à partir d'un paramètre temporel de la tâche
➢ priorité constante ou variable avec le temps
➢ à priorité identique, on évite la préemption
➢ test d'acceptabilité hors ligne si tous les paramètres
sont connus
➢ sinon test de garantie au réveil des tâches

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 12
tâches périodiques

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 13
Rate Monotonic Analysis (RMA)
● algorithme à priorité constante
● basé sur la période (tâches à échéance sur requête) :
➢ la tâche de plus petite période est la plus prioritaire
● test d'acceptabilité (condition suffisante)

● U= )

● quand n est très grand : n(21/n – 1) ~ ln 2 = 0,69

● dans la pratique, on peut rencontrer des
ordonnancements valides qui vont jusqu'à 88%

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 14
Rate Monotonic Analysis (RMA)
● exemple
T1 (r0=0, C=3, P=20), T2 (r0=0, C=2, P=5), T3 (r0=0, C=2,
P=10)
≤
ord
Prio2 > Prio3 > on
na
T1 Prio1 nç
ab
le
0 4 5 7 9 20
T2

0 2 5 7 10 12 15 17 20
T3

0 2 4 10 12 14 20

0 2 4 5 7 9 10 12 14 15 17 20

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 15
Deadline Monotonic Analysis (DMA)
● algorithme à priorité constante
● basé sur le délai critique :
➢ la tâche de plus petit délai critique est la plus
prioritaire
● test d'acceptabilité (condition suffisante)

● équivalent à RMA dans le cas des tâches à échéance

sur requête, meilleur dans les autres cas

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 16
Deadline Monotonic Analysis (DMA)
● exemple
T1(r0 = 0, C=3, , D=7, P=20), T2 (r0 = 0, C=2, D=4, P=5),
T3 (r0 = 0, C=2, D=9, P=10)

fau ≥
tv
o ir
Prio2 > Prio1 > ...
Prio3
T1

0 2 5 7 20
T
2

0 2 4 5 7 9 10 12 14 15 17 19 20
T
3

0 7 9 10 12 14 19 20

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 17
Rate Monotonic Analysis (RMA)

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 18
Rate Monotonic Analysis (RMA)

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 19
Rate Monotonic Analysis (RMA)

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 20
Rate Monotonic Analysis (RMA)

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 21
Earliest Deadline First (EDF)
● algorithme à priorité variable
● basé sur l'échéance
➢ à chaque instant (i.e à chaque réveil de tâche), la
priorité maximale est donnée à la tâche dont
l'échéance est la plus proche

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 22
Earliest Deadline First (EDF)

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 23
Earliest Deadline First (EDF)

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 24
Earliest Deadline First (EDF)
● exemple
T1 (r0 = 0, C=3, , D=7, P=20),
T2 (r0 = 0, C=2, D=4,<P=5),
1
T3 (r0 = 0, C=2, D=8, P=10)
>1
ch
ron
og
T1 ram
me
0 2 5 7 20
T
2

0 2 4 5 7 8 9 10 12 14 15 17 19 20
T
3

0 5 7 8 10 12 14 18 20
F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 25
Least Laxity First (LLF)
● algorithme à priorité variable
● aussi appelé Least Slack Time (LST)
● basé sur la laxité résiduelle
➢ la priorité maximale est donnée à la tâche qui a la
plus petite laxité résiduelle L(t) = D(t) – C(t)
● équivalent à EDF si on ne calcule la laxité qu'au réveil
des tâches
● optimum à trouver entre la granularité du calcul et le
nombre de changements de contexte provoqués

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 26
Least Laxity First (LLF)
T C
P1 6 2
P2 8 2
P3 12 3

La marge = Échéance - durée restante de traitement - temps courant

6 8 12 16 18 24

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 27
 Least Laxity First (LLF)
T D C ML
T1 3 3 1 =Deadline-C_restante
T2 4 4 1
T3 6 3 2

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
T3 T1 T3 T2 T1 T2 T3 T1 T3 T1 T2 nop T3 T1 T3 T2 T1 T2 T3 T1
T1 T1 T1 T1 T1 T1 T1 T1
T2 T2 T2 T2 T2 T2
T3 T3 T3 T3 T3 T3 T3 T3

Ici T3 peut être aussi ordonnancé

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 28
Least Laxity First (LLF)
● exemple
même configuration que pour EDF
T1 (r0 = 0, C=3, , D=7, P=20), T2 (r0 = 0, C=2, D=4, P=5),
T3 (r0 = 0, C=2, D=8, P=10)
● laxité calculée à t = 0, 1, 2, 3, etc...
t=7 0
1
2
3
4
5
6
L21 = 0
7-3L32=
3,
2,
1, ==4,
2,1
4LL23 == 4-2
3
2 5 = 2, L3 = 8-2 =
6
T1

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

T
2

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
T
3

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 29
Traitement des tâches apériodiques

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 30
Introduction
● tâches prises en compte dans une configuration
comprenant déjà des tâches périodiques
● a priori, on ne connaît pas l'instant d'arrivée de la requête
de réveil de la tâche apériodique
● contraintes temporelles strictes ou relatives
● buts à atteindre :
➢ si contraintes relatives : minimiser le temps de
réponse
➢ si contraintes strictes : maximiser le nombre de
tâches acceptées en respectant leurs contraintes
● 2 grandes catégories de traitement
➢ traitement en arrière-plan
➢ traitement par serveurs

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 31
 Tâches à contraintes relatives

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 32
Traitement d'arrière-plan (1)
● tâches apériodiques ordonnancées quand le processeur
est oisif
➢ les tâches périodiques restent les plus prioritaires
● ordonnancement relatif des tâches apériodiques en
mode FIFO
● traitement le plus simple, mais le moins performant

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 33
Traitement d'arrière-plan (2)
● exemple
Tp1 (r0=0, C=2, P=5), Tp2 (r0=0, C=2, P=10)
Ta3 (r=3, C=2), Ta4 (r=10, C=1), Ta5 (r=11, C=2)
➢ ordonnancement RMA des tâches périodiques
Tp
1

0 2 5 7 10 12 15 17 20
Tp
2

0 2 4 10 12 14 20
Temps creux

4 5 7 10 14 15 17 20
Tâches apériodiques

3 4 5 7 8 10 11 14 15 17 19

Ta3 Ta4 Ta5

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 34
Traitement par serveur (1)
● un serveur est une tâche périodique créée spécialement
pour prendre en compte les tâches apériodiques
● serveur caractérisé par
➢ sa période
➢ son temps d'exécution : capacité du serveur
➢ serveur généralement ordonnancé suivant le même
algorithme que les autres tâches périodiques
➢ une fois actif, le serveur sert les tâches apériodiques
dans la limite de sa capacité.
➢ l'ordre de traitement des tâches apériodiques ne dépend
pas de l'algorithme général

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 35
Traitement par serveur par scrutation (1)
● Serveurs par scrutation (polling)
➢ à chaque activation, traitement des tâches en suspens
jusqu'à épuisement de la capacité ou jusqu'à ce qu'il
n'y ait plus de tâches en attente
➢ si aucune tâche n'est en attente (à l'activation ou parce
que la dernière tâche a été traitée) , le serveur se
suspend immédiatement et perd sa capacité qui peut
être réutilisée par les tâches périodiques

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 36
Traitement par serveur par scrutation (2)
● exemple de serveur par scrutation (ordonnancement RMA)
➢ 2 tâches périodiques : Tp1 (r0=0, C=3, P=20) Tp2 (r0=0, C=2, P=10)
➢ serveur : Tps (r0=0, C=2, P=5)

Tp
1
0 2 4 5 7 9 20
Tp
2

0 2 4 10 12 14 20
Tp
s

0 2 5 7 10 11 12 15 17 20

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 37
Traitement par serveur par scrutation (3)
● exemple de serveur par scrutation (ordonnancement RMA)
➢ 2 tâches périodiques : Tp1 (r0=0, C=3, P=20) Tp2 (r0=0, C=2, P=10)
➢ serveur : Tps (r0=0, C=2, P=5)
➢ tâches apériodiques : Ta3 (r=4, C=2), Ta4 (r=10, C=1), Ta5 (r=11, C=2)

Tp
1
0 2 5 20
Tp
2

0 2 10 12 14 20
Tp
s

0 2 5 7 10 11 12 15 17 20
Capacité Ta3 Ta4 Ta5 Tâches apériodiques
2
1
0

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 38
Traitement par serveur par scrutation (4)
● limitations du serveur par scrutation
➢ perte de la capacité si aucune tâche apériodique en attente
➢ si occurrence d'une tâche apériodique alors que le serveur
est suspendu, il faut attendre la requête suivante

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 39
Traitement par serveur sporadique (1)
● Serveur sporadique
➢ améliore le temps de réponse des tâches apériodiques
sans diminuer le taux d'utilisation du processeur pour
les tâches périodiques
➢ comme le serveur ajournable mais ne retrouve pas sa
capacité à période fixe
➢ le serveur sporadique peut être considéré comme une
tâche périodique « normale » du point de vue des
critères d'ordonnancement

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 40
Traitement par serveur sporadique (2)
● calcul de la récupération de capacité
➢ le serveur est dit « actif » quand la priorité de la tâche
courante Pexe est supérieure ou égale à celle du
serveur Ps
➢ le serveur est dit « inactif » si Pexe < Ps
➢ RT : date de la récupération
✔ calculée dès que le serveur devient actif (t A)
✔ égale à tA + Ts
➢ RA : montant de la récupération à effectuer à RT
✔ calculée à l'instant tI où le serveur devient inactif ou
que la capacité est épuisée
✔
égal à la capacité consommée pendant l'intervalle
[tA, tI]

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 41
Traitement par serveur sporadique (3)
● exemple de serveur sporadique à haute priorité
➢ 2 tâches périodiques : Tp1 (r0=0, C=3, P=20), Tp2 (r0=0, C=2, P=10)
➢ serveur : Tps (r0=0, C=2, P=5)
➢ tâches apériodiques : Ta3 (r=4, C=2), Ta4 (r=10, C=1), Ta5 (r=11, C=2)

Tp
1
0 2 4 6 7 20
Tp
2

0 2 10 12 14 20
Tp
s

0 4 6 10 11 12 15 16
Capacité Ta3 Ta4 Ta5 Tâches apériodiques
2
1
0
5 9 10 12 15 20

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 42
 Tâches à contraintes strictes

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 43
Principe de l'ordonnancement
● ordonnancer les tâches en EDF
● A chaque nouvelle tâche apériodique, faire tourner une
"routine de garantie" pour vérifier que toutes les
contraintes temporelles seront respectées
➢ si oui, accepter la tâche.
➢ si non, refuser la tâche.
● 2 politiques d'acceptation dynamique :
➢ acceptation dans les temps creux
➢ ordonnancement conjoint
● favorise les tâches périodiques

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 44
acceptation dans les temps creux (1)
● ordonnancement EDF des tâches périodiques
● les tâches apériodiques acceptées sont ordonnancées
dans les temps creux des tâches périodiques (~
méthode d'arrière-plan) selon l'algorithme EDF
● routine de garantie (au réveil d'une tâche apériodique):
➢ teste l'existence d'un temps creux suffisant entre le
réveil et l'échéance de la tâche apériodique)
➢ vérifie que l'acceptation de la nouvelle tâche ne remet
pas en cause le respect des contraintes temporelles
des autres tâches apériodiques déjà acceptées et
non encore terminées
➢ si OK, la tâche est ajoutée à la liste des tâches
apériodiques

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 45
acceptation dans les temps creux (2)
● exemple
➢ Tp1 (r0=0, C=3, D=7, P=20), Tp2 (r0=0, C=2, D=4, P=5),
Tp3 (r0=0, C=1, D=8, P=10)
➢ Ta4 (r=4, C=2, d=10), Ta5 (r=10, C=1, d=18),
Ta6 (r=11, C=2, d=16)
Tp
1
0 2 5 7 20
Tp
2
2 4 5 6 8 9 10 1 14 1 17 19 20
Tp 2 5
3
0 5 6 8 10 12 13 18 20
Temps creux

0 8 10 13 15 17 20
Tâches apériodiques

0 4 8 10 11 13 15 16 17 18
Ta4 Ta5 Ta6

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 46
acceptation dans les temps creux (3)
● exemple
➢ Tp1 (r0=0, C=3, D=7, P=20), Tp2 (r0=0, C=2, D=4, P=5),
Tp3 (r0=0, C=1, D=8, P=10)
➢ Ta4 (r=4, C=2, d=10), Ta5 (r=10, C=2, d=18),
Ta6 (r=11, C=2, d=16)
Tp
1
0 2 5 7 20
Tp
2
2 4 5 6 8 9 10 1 14 1 17 19 20
Tp 2 5
3
0 5 6 8 10 12 13 18 20
Temps creux

0 8 10 13 15 17 20
Tâches apériodiques

0 4 8 10 11 13 15 16 17 18
Ta4 Ta5 X Ta6

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 47
ordonnancement conjoint (1)
● la séquence des tâches périodiques n'est plus immuable
● à l'arrivée de chaque nouvelle tâche apériodique,
construction d'une nouvelle séquence EDF
➢ si la construction est possible : acceptation de la tâche
➢ sinon rejet

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 48
ordonnancement conjoint (2)
● exemple
➢ Tp1 (r0=0, C=3, D=7, P=20), Tp2 (r0=0, C=2, D=4, P=5),
➢ Tp3 (r0=0, C=1, D=8, P=10)
➢ Ta4 (r=4, C=2, d=10), Ta5 (r=10, C=1, d=18),

Tp
1
Tp2 0 2 5 7 20

2 4 5 6 8 9 10 12 15 17 19 20
Tp3

0 5 6 8 10 12 13 14 15 18 20

Tâches apériodiques

0 4 8 10 11 13 14 18
Ta5
Ta4
F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 49
ordonnancement conjoint (3)
● exemple
➢ Tp1 (r0=0, C=3, D=7, P=20), Tp2 (r0=0, C=2, D=4, P=5),
➢ Tp3 (r0=0, C=1, D=8, P=10)
➢ Ta4 (r=4, C=2, d=10), Ta5 (r=10, C=1, d=18),
Ta6 (r=11, C=2, d=16)

Tp
1
Tp2 0 2 5 7 20

2 4 5 6 8 9 10 12 15 17 19 20
Tp3

0 5 6 8 10 12 13 14 15 18 20

Tâches apériodiques

0 4 8 10 11 12 13 14 18
Ta5
Ta4 Ta6
F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 50
ordonnancement conjoint (3)
● exemple
➢ Tp1 (r0=0, C=3, D=7, P=20), Tp2 (r0=0, C=2, D=4, P=5),
➢ Tp3 (r0=0, C=1, D=8, P=10)
➢ Ta4 (r=4, C=2, d=10), Ta5 (r=10, C=2, d=18),
Ta6 (r=11, C=2, d=16)

Tp
1
Tp2 0 2 5 7 20

2 4 5 6 8 9 10 12 15 17 19 20
Tp3

0 5 6 8 10 12 13 14 15 18 20

Tâches apériodiques

0 4 8 10 11 12 13 14 18
Ta5
Ta4 Ta6
F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 51
Ordonnancement
de tâches
dépendantes

52
Plan
● types de contraintes étudiées
➢ contraintes de précédence
➢ contraintes liées au partage de ressources critiques
● présentation et illustration des contraintes
● algorithmes pour les ordonnancer
● étude de cas : la mission Pathfinder sur Mars (TD)

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 53
Présentation des contraintes

54
Contraintes de précédence (1)
● Contraintes de précédence
➢ sur l'ordre d'exécution des tâches les unes par rapport
aux autres
➢ généralement décrites par un graphe orienté G
✔ Ja < Jb indique que la tâche Ja est un prédécesseur
de Jb
✔ Ja → Jb indique que la tâche Ja est un prédécesseur
immédiat de Jb
J1

J2 J3

J4 J5

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 55
Contraintes de précédence (2)
● Contraintes de précédence
➢ sur l'ordre d'exécution des tâches les unes par rapport
aux autres
➢ généralement décrites par un graphe orienté G
✔ Ja < Jb indique que la tâche Ja est un prédécesseur
de Jb
✔ Ja → Jb indique que la tâche Ja est un prédécesseur
immédiat de Jb
J1

J1 <
J2 J3 JJ2  J
1 2

J1 <
J4 J5 J
J4  J
1 4

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 56
Contraintes de précédence (3)
➢ exemple : reconnaissance de formes

caméra
stéréoscopique 
objets défilants
sur un tapis roulant
système
acq
d'acquisition
1 traitement
et de
acq
2

ima ima
ge1 ge2

✘8 tâches diff form

●
2 acquisitions e
●
2 traitements image
●
analyse de forme
●
analyse des différences haut
●
calcul de hauteur eur
●
reconnaissance finale
reco
nn

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 57
Partage de ressources (1)
● contraintes sur les accès aux ressources
➢ ressource : toute structure logicielle qui peut être
utilisée par une tâche pour son exécution
➢ privée si dédiée à la tâche
➢ partagée si elle peut être utilisée par plusieurs tâche
➢ exclusive si une seule tâche à la fois peut l'utiliser
➢ l'accès séquentiel par plusieurs tâches à une ressource
exclusive nécessite un mécanisme de
synchronisation
➢ les codes implémentant les opérations en exclusion
mutuelle sont des sections critiques

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 58
Partage de ressources (2)
● phénomènes de blocage et d'inversion de priorité
Demande Libère
Δt
J1

Demande Libère

J2

Priorité(J1) > Priorité(J2)

Exécution normale

Section critique

➢ le délai imposé par J2 à J1 est « normal »

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 59
Partage de ressources (3)
● phénomènes de blocage et d'inversion de priorité
Demande Libère
δt
J1

J3

Demande Libère

J2

Priorité(J1) > Priorité(J3) >

Priorité(JExécution
2) normale

Section critique

➢ le délai supplémentaire apporté à J1 par J3 est dû au

phénomène d' « inversion de priorité »
F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 60
Quelques « anomalies » d'ordonnancement
●Théorème de Graham : si un ensemble de tâches est
ordonnancé de façon optimale sur un système multi-
processeur avec des priorités assignées, des temps
d'exécution fixées et des contraintes de précédence, alors
le fait d'augmenter le nombre de processeurs, de réduire
les temps d'exécution ou de relaxer les contraintes de
précédence peut conduire à détériorer la durée
d'exécution de l'algorithme

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 61
Quelques « anomalies » d'ordonnancement
●exemple
➢9 tâches de priorités décroissantes
(Prio(Ji) > Prio(Jj)) ⇔ i > j
➢ contraintes de précédence et temps d'exécution :

J9 (9)
J1 (3)

J8 (4)
J2 (2)
J7 (4)

J3 (2)
J6 (4)

J4 (2) J5 (4)

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 62
Quelques « anomalies » d'ordonnancement
➢ ordonnancement optimal sur un système à 3 processeurs
J 1
J9
(9)
(3) J8
J2 (4)
(2) J7
J3 (4)
J6
(2)
P J1 J9 J4
(4)
J5
(2)
P
1 J2 J4 J5 J7 (4)

P
2 J3 J6 J8
3

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
➢ sur un système à 4 processeurs :

P J1 J8
P
1 J2 J5 J9
P
2 J3 J6
P4
3 J4 J7

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 63
Quelques « anomalies » d'ordonnancement
➢ordonnancement optimal sur un système à J1 J9
(9)
(3)
3 processeurs J2
J8
(4)
(2) J7
J3 (4)
J6
(2)
J1 J9 (4)
P J4 J5
J2 J4 J5 J7 (2) (4)
P
1
J3 J6 J8
P
2

3
0 1 2 3 4 5 6 7 8 9 1 1 1 1 1 1 1 1 1
0 1 2 3 4 5 6 7 8
➢ en réduisant d'une unité le temps de calcul des tâches
J1 J9
(2) (8)
P J1 J5 J8 J2
J8
(3)
J7
P
1
J2 J4 J6 J9 (1)
J3 (4)
J6
P
2
J3 J7 (1)
(3)
J4 J5
3 (1) (3)

0 1 2 3 4 5 6 7 8 9 1 1 1 1 1 1 1 1 1
0 1 2 3 4 5 6 7 8

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 64
Quelques « anomalies » d'ordonnancement
➢ordonnancement optimal sur un système J1 J9

à 3 processeurs (3)
J2
(9)
J8
(4)
(2) J7
J3 (4)
J6
J1 J9 (2)
P J4
(4)
J5
J2 J4 J5 J7 (2) (4)
P
1
J3 J6 J8
P
2

0 1 2 3 4 5 6 7 8 9 1 1 1 1 1 1 1 1 1
0 1 2 3 4 5 6 7 8
➢en supprimant quelques relations de J1
J9
(9)
précédence (3)
J2
J8
(4)
(2) J7
J3 (4)
J6
(2)
(4)
J1 J8 J9 J4 J5
P (2) (4)
J2 J4 J5
P
1
J3 J7 J6
P
2

3
0 1 2 3 4 5 6 7 8 9 1 1 1 1 1 1 1 1 1
0 1 2 3 4 5 6 7 8
F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 65
Quelques « anomalies » d'ordonnancement
●exemple d'anomalie sur des contraintes de ressources
➢5 tâches allouées statiquement à 2 processeurs
J2 et J4 partagent une ressource exclusive

P J1 J2
P
1 J3 J4 J5
2

0 1 2 3 4 5 6 7 8 9 1 1 1 1 1 1 1 1 1 1 2 2 2
➢ si on réduit le temps d'exécution
0 1 2 de3J 4 5 6 7 8 9 0 1 1
2

P J1 J2
P
1 J3 J4 J5
2

0 1 2 3 4 5 6 7 8 9 1 1 1 1 1 1 1 1 1 1 2 2 2
0 1 2 3 4 5 6 7 8 9 0 1 2
F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 66
Algorithmes d'ordonnancement
Contraintes de précédence
●ici, seulement précédence simple
➢ si Ti est périodique de période Pi, alors Tj l'est aussi et Pj = Pi
●principe de l'établissement de l'ordonnancement :
➢transformer l'ensemble des tâches dépendantes en un ensemble
de tâches « indépendantes » que l'on ordonnancera par un
algorithme classique
➢par des modifications des paramètres des tâches

✔si Ti → T j alors la règle de transformation doit respecter

 ri
✘rj
✘Prioi > Prioj

➢validation de l'ordonnançabilité selon des critères utilisés pour des

tâches indépendantes

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 68
Contraintes de précédence
●contraintes de précédence et Rate Monotonic
➢la transformation s'opère hors ligne sur la date de réveil et sur
les délais critiques
✔r*i = Max{ri, r*j} pour tous les j tels que Tj → Ti
✔si T → T
i j alors Prioi > Prioj dans le respect de la règle d'affectation
des priorités par RMA

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 69
Contraintes de précédence
●contraintes de précédence et Deadline Monotonic
➢la transformation s'opère hors ligne sur la date de réveil et sur
les délais critiques
✔r*i = Max{ri, r*j} pour tous les j tels que Tj → Ti
✔D* = Max{Di, D* } pour tous les j tels que T → T
i j j i
✔si T → T
i j alors Prioi > Prioj dans le respect de la règle d'affectation
des priorités par DMA

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 70
Contraintes de précédence
●contraintes de précédence et EDF
➢modification des échéances de façon à ce qu'une tâche ait
toujours un di inférieur à celui de ses successeurs (algorithme de
Chetto et al.)
➢une tâche ne doit être activable que si tous ses prédécesseurs

ont terminé leur exécution

➢modification de la date de réveil et de l'échéance
✔r*i = Max{ri, Max{r*j + Cj}} pour tous les j tels que Tj → Ti
✔d* = Min{d , Min{d* - C }} pour tous les j tels que T → T
i i j j i j
✔
on itère sur les prédécesseurs et successeurs immédiats
✔
on commence les calculs par les tâches qui n'ont pas de prédécesseurs
pour le calcul des r et par les tâches qui n'ont pas de successeur pour le
calcul des d

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 71
Contraintes de précédence
●exemple

T3
T1
T5

T4
T2

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 72
Contraintes de précédence
●exemple

T3
T1
T5

T4
T2

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 73
Contraintes de précédence
●exemple
T1 n'a pas de
T3
T1 prédécesseur
T5
r*1 = 0
T4
T2

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 74
Contraintes de précédence
●exemple
T2 n'a pas de
T3
T1 prédécesseur
T5
r*2 = 5
T4
T2

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 75
Contraintes de précédence
●exemple
T3 a T1 pour
T3
T1 prédécesseur
T5
r*3 = Max(r3, r*1+C1) =
T4 1
T2

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 76
Contraintes de précédence
●exemple
T4 a T1 et T2 pour
T3
T1 prédécesseurs
T5
r*4 = Max(r4,
T4 Max(r*1+C1,r*2+C2))
T2
=7

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 77
Contraintes de précédence
●exemple
T5 a T3 et T4 pour
T3
T1 prédécesseurs
T5
r*5 = Max(r5,
T4 Max(r*3+C3,r*4+C4))
T2
=8

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 78
Contraintes de précédence
●exemple
T5 n'a pas de
T3
T1 successeur
T5
d*5 = 12
T4
T2

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 79
Contraintes de précédence
●exemple
T4 a T5 pour
T3
T1 successeur
T5
d*4 = Min(d4,Min(d*5-
T4 C5))
T2
=9

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 80
Contraintes de précédence
●exemple
T3 a T5 pour
T3
T1 successeur
T5
d*3 = Min(d3,Min(d*5-
T4 C5))
T2
=5

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 81
Contraintes de précédence
●exemple
T2 a T4 pour
T3
T1 successeur
T5
d*2 = Min(d2,Min(d*4-
T4 C4))
T2
=5

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 82
Contraintes de précédence
●exemple
T1 a T3 et T4 pour
T3
T1 successeurs
T5
d*2 = Min(d2,Min(d*3-C3,
T4 d*4-C4))
T2
=3

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 83
Contraintes de précédence
T1
●exemple 0 1 2 3 4 5 6 7 8 9 1 1 1
T2 0 1 2

T3 0 1 2 3 4 5 6 7 8 9 1 1 1
T1 T3 0 1 2
T5 0 1 2 3 4 5 6 7 8 9 1 1 1
T4 0 1 2

T4 0 1 2 3 4 5 6 7 8 9 1 1 1
T2 T5 0 1 2

0 1 2 3 4 5 6 7 8 9 1 1 1
0 1 2

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 84
Contraintes de précédence
T1
●exemple 0 1 2 3 4 5 6 7 8 9 1 1 1
T2 0 1 2

T3 0 1 2 3 4 5 6 7 8 9 1 1 1
T1 T3 0 1 2
T5 0 1 2 3 4 5 6 7 8 9 1 1 1
T4 0 1 2

T4 0 1 2 3 4 5 6 7 8 9 1 1 1
T2 T5 0 1 2

0 1 2 3 4 5 6 7 8 9 1 1 1
0 1 2

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 85
Contraintes de précédence
T1
●exemple 0 1 2 3 4 5 6 7 8 9 1 1 1
T2 0 1 2

T3 0 1 2 3 4 5 6 7 8 9 1 1 1
T1 T3 0 1 2
T5 0 1 2 3 4 5 6 7 8 9 1 1 1
T4 0 1 2

T4 0 1 2 3 4 5 6 7 8 9 1 1 1
T2 T5 0 1 2

0 1 2 3 4 5 6 7 8 9 1 1 1
0 1 2

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 86
Partage de ressources critiques
●
une ressource critique ne peut
●
être utilisée simultanément par plusieurs tâches
●
être réquisitionnée par une autre tâche
●
notion de section critique
●
séquence d'instructions pendant lesquelles on utilise une
ressource critique
➢sans problème dans le cas d'un ordonnancement non

préemptif, mais c'est rarement le cas dans un environnement

temps réel ⇒ évaluation du temps de réponse très difficile,
sinon impossible
✔
abondante littérature !

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 87
Partage de ressources critiques
●inversion de priorité
➢phénomène dû à la présence simultanée de priorités fixes et de
ressources à accès exclusif dans un environnement préemptif
✔
exemple de 4 tâches de priorités décroissantes
prio(T1) > prio(T2) > prio(T3) > prio(T4)
✔
si pas de partage de ressource commune :

T1
T2

T3

T4

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 88
Partage de ressources critiques
●inversion de priorité
➢phénomène dû à la présence simultanée de priorités fixes et de
ressources à accès exclusif dans un environnement préemptif
✔
exemple de 4 tâches de priorités décroissantes
prio(T1) > prio(T2) > prio(T3) > prio(T4)
✔
si partage d'une ressource commune

T1
R
T2
1

T3
R R
T4
1 1

✔le retard de T2 dû à T3 est une "inversion de priorité", non prévue

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 89
Héritage de priorité
●principe : attribuer à la tâche qui possède la ressource la
priorité de la tâche de plus haute priorité qui attend la
ressource
● hypothèses de travail
➢ n tâches périodiques T1, T2, ... , Tn (période Pi, capacité
Ci) à échéance sur requête
➢ partageant m ressources R1, R2, ... , Rm
➢ chaque ressource Rj est gardée par un sémaphore
binaire Sj limitant une section critique zi,j (pour Ti)
➢ Pi : priorité nominale, pi : priorité active
P1 > P2 > ... > Pn
➢ zi,j ⊂ zi,k ou zi,k ⊂ zi,j ou zi,j ∩ zi,k = ∅ ∀ zi,j et zi,k

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 90
Héritage de priorité
● définition du protocole d'héritage de priorité
➢ les tâches sont ordonnancées suivant leur priorité
active
➢ quand une tâche Ti cherche à entrer dans une section
critique zi,j et que la ressource Rj est déjà possédée
par une tâche Tk, de priorité plus faible, alors Ti se
bloque (sinon Ti entre dans zi,j)
➢ la tâche Ti, bloquée, transmet sa priorité à Tk qui peut
alors redémarrer et terminer l'exécution de la section
critique zk,j
➢ quand Tk sort de la section critique, il relâche le
sémaphore Sj et la tâche de plus haute priorité est
réveillée. Si aucune tâche n'est encore bloquée par
Tk, alors pk est ramenée à Pk, sinon on donne à pk la
plus haute des priorités des tâches en attente
F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 91
Héritage de priorité
● exemple
➢ sans héritage de priorité
R
1
T1

T2
R
1
T3

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 92
Héritage de priorité
● exemple
➢ sans héritage de priorité
R
1
Blocage
Blocage
T1
direct
direct
T2
R
1
T3

Blocage
Blocage
✔
avec héritage de priorité
R
indirect
indirect
T1 1

T2
R
T3 1

p
P
3

P
1

F. Touchard 3 Marseille IRM4 SICA 2012-13

Polytech Introduction aux systèmes Temps Réels Ordonnancement 93
Héritage de priorité
● propriétés du protocole d'héritage des priorités
➢ le temps de blocage B d'une tâche de haute priorité
par une tâche de plus basse priorité nominale est
borné
➢ mais le calcul de ce temps de blocage maximum
peut être très complexe
➢ condition nécessaire d'ordonnançabilité par un
algorithme Rate Monotonic :

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 94
Héritage de priorité
● problèmes rémanents
➢ blocages en chaîne
R R
T1 a b

R
T2 b

R
T3 a

➢ étreinte fatale (deadlock), si 2 tâches utilisent 2

ressources imbriquées, mais dans l'ordre inverse
T1 T2
R R
wait (Sa) wait (Sb)
T1 a b
wait (Sb) wait (Sa)
R R
signal (Sb) signal (Sa)
T2 b a
signal (Sa) signal (Sb)

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 95
Priorité plafonnée
●introduit à la fin des années 80 pour résoudre le
problème d'inversion de priorité tout en prévenant
l'occurence de deadlocks et de blocages en chaîne
● amélioration du protocole d'héritage de priorité : une
tâche ne peut pas entrer dans une section critique
s'il y a un sémaphore acquis qui pourrait la bloquer
● principe : on attribue à chaque sémaphore une priorité
plafond égale à la plus haute priorité des tâches qui
pourraient l'acquérir. Une tâche ne pourra entrer
dans la section critique que si elle possède une
priorité supérieure à toutes celles des priorités
plafond des sémaphores acquis par les autres
tâches

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 96
Priorité plafonnée
● définition du protocole
➢ on attribue à chaque sémaphore Sk une priorité plafond
C(Sk) égale à la plus haute priorité des tâches
susceptibles de l'acquérir
➢ soit Ti la tâche prête de plus haute priorité : l'accès au
processeur est donné à Ti
➢ soit S* le sémaphore dont la priorité plafond C(S*) est
la plus grande parmi tous les sémaphores déjà
acquis par des tâches autres que Ti
➢ pour entrer dans une section critique gardée par un
sémaphore Sk, Ti doit avoir une priorité supérieure à
C(S*). Si Pi ≤ C(S*), l'accès à Sk est dénié et on dit
que Ti est bloquée sur S* par la tâche qui possède S*

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 97
Priorité plafonnée
● exemple
➢ 3 tâches T0, T1, T2 de priorités décroissantes P0 > P1
> P2
✔ T0 accède séquentiellement à 2 sections critiques
gardées par les sémaphores S0 et S1
✔ T1 accède à une section critique gardée par S 2
✔ T2 accède à la section critique gardée par S 2 et
aussi, de manière imbriquée, à S1
➢ les priorités plafond sont :
✔ C(S0) = P0
✔ C(S1) = P0
✔ C(S2) = P1

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 98
Priorité plafonnée

R R
T0 0 S 1 S1 C(S0) = P0
R 0 C(S1) = P0
T1 2 S C(S2) = P1
R R R 2
T2 2S S 1 S1 S1 1 S
p 2 2 2
P20
P1
P2
t t t t t4 t5 t6 t7 t8 t9 t1
0 1 2 3 0

➢ à t0, T2 est activée et démarre. Le sémaphore S2 est

demandé et obtenu (il n'y a pas d'autre ressource
en cours d'utilisation)

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 99
Priorité plafonnée

R R
T0 0 S 1 S1 C(S0) = P0
R 0 C(S1) = P0
T1 2 S C(S2) = P1
R R R 2
T2 2S S 1 S1 S1 1 S
p 2 2 2
P20
P1
P2
t t t t t4 t5 t6 t7 t8 t9 t1
0 1 2 3 0

➢ à t1, T1 est activée et préempte T2

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 100
Priorité plafonnée

R R
T0 0 S 1 S1 C(S0) = P0
R 0 C(S1) = P0
T1 2 S C(S2) = P1
R R R 2
T2 2S S 1 S1 S1 1 S
p 2 2 2
P20
P1
P2
t t t t t4 t5 t6 t7 t8 t9 t1
0 1 2 3 0

➢ à t2, T1 demande S2 et est bloquée par le protocole

car la priorité de T1 n'est pas supérieure à la
priorité plafond C(S2)=P1 (S2 est le seul
sémaphore acquis à t2)
T2 hérite de la priorité de T1 et redémarre
F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 101
Priorité plafonnée

R R
T0 0 S 1 S1 C(S0) = P0
R 0 C(S1) = P0
T1 2 S C(S2) = P1
R R R 2
T2 2S S 1 S1 S1 1 S
p 2 2 2
P20
P1
P2
t t t t t4 t5 t6 t7 t8 t9 t1
0 1 2 3 0

➢ à t3, T2 demande et obtient le sémaphore S1 , car

aucune autre tâche ne détient de ressource

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 102
Priorité plafonnée

R R
T0 0 S 1 S1 C(S0) = P0
R 0 C(S1) = P0
T1 2 S C(S2) = P1
R R R 2
T2 2S S 1 S1 S1 1 S
p 2 2 2
P20
P1
P2
t t t t t4 t5 t6 t7 t8 t9 t1
0 1 2 3 0

➢ à t4 T0 est réveillée et préempte T2

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 103
Priorité plafonnée

R R
T0 0 S 1 S1 C(S0) = P0
R 0 C(S1) = P0
T1 2 S C(S2) = P1
R R R 2
T2 2S S 1 S1 S1 1 S
p 2 2 2
P20
P1
P2
t t t t t4 t5 t6 t7 t8 t9 t1
0 1 2 3 0

➢ à t5, T0 demande le sémaphore S0 qui n'est détenu par

aucune autre tâche. Le protocole bloque néanmoins
T0 parce que sa priorité n'est pas supérieure à la plus
grande priorité plafond des sémaphores déjà détenus
(S2 et S1) : P0
T2 hérite de la priorité de T0 et peut redémarrer
F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 104
Priorité plafonnée

R R
T0 0 S 1 S1 C(S0) = P0
R 0 C(S1) = P0
T1 2 S C(S2) = P1
R R R 2
T2 2S S 1 S1 S1 1 S
p 2 2 2
P20
P1
P2
t t t t t4 t5 t6 t7 t8 t9 t1
0 1 2 3 0

➢ à t6, T2 relâche S1. Sa priorité p2 est ramenée à P1,

plus haute priorité des tâches bloquées par T2
T0 peut alors préempter T2 et acquérir S0

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 105
Priorité plafonnée

R R
T0 0 S 1 S1 C(S0) = P0
R 0 C(S1) = P0
T1 2 S C(S2) = P1
R R R 2
T2 2S S 1 S1 S1 1 S
p 2 2 2
P20
P1
P2
t t t t t4 t5 t6 t7 t8 t9 t1
0 1 2 3 0

➢ à t7 quand T0 demande S1, le seul sémaphore encore

tenu est S2 avec une priorité plafond P1  T0
(priorité P0 > P1) obtient S1

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 106
Priorité plafonnée

R R
T0 0 S 1 S1 C(S0) = P0
R 0 C(S1) = P0
T1 2 S C(S2) = P1
R R R 2
T2 2S S 1 S1 S1 1 S
p 2 2 2
P20
P1
P2
t t t t t4 t5 t6 t7 t8 t9 t1
0 1 2 3 0

➢ à t8, T0 se termine. T2 peut reprendre son exécution,

toujours avec la même priorité P1

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 107
Priorité plafonnée

R R
T0 0 S 1 S1 C(S0) = P0
R 0 C(S1) = P0
T1 2 S C(S2) = P1
R R R 2
T2 2S S 1 S1 S1 1 S
p 2 2 2
P20
P1
P2
t t t t t4 t5 t6 t7 t8 t9 t1
0 1 2 3 0

➢ à t9, T2 relâche S2. Sa priorité est ramenée à sa

valeur nominale P2. T1 peut alors préempter T2 et
redémarrer
➢ à t10, T1 se termine, T2 peut redémarrer et se
terminer
F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 108
Priorité plafonnée
● on a le même critère d'ordonnançabilité par RMA que
dans le cas du protocole d'héritage de priorité

● mais le calcul du temps de blocage maximum de chaque

tâche est plus simple :
➢ on peut démontrer que le temps de bloquage maximum
Bi d'une tâche Ti est la durée de la plus longue des
sections critiques parmi celles appartenant à des
tâches de priorité inférieure à Pi et gardées par des
sémaphores dont la priorité plafond est supérieure ou
égale à Pi

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 109
 Ordonnancement en
situations de surcharge

110
Plan
● notions liées à la surcharge
➢ définitions
➢ métrique
● schémas d'ordonnancement
➢ classes d'algorithmes
➢ tâches périodiques
➢ tâches quelconques

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 111
Notion 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

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 112
Notion de surcharge
● effet "domino" dû à l'arrivée d'une tâche supplémentaire
dans un ordonnancement EDF

C=4

C=4

C=1,5

C=1,5

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 113
Notion de surcharge
● effet "domino" dû à l'arrivée d'une tâche supplémentaire
dans un ordonnancement EDF

C=2
Bo
u m
!
C=4
Bo
u m
!
C=4
Bo
u m
!
C=1,5
Bo
u m
!
C=1,5

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 114
Notion de surcharge
● dans un contexte temps réel préemptible de n tâches
périodiques indépendantes à échéance sur requête, la
charge est équivalente au facteur d'utilisation U :

● cas général
➢ basée sur le fait que pour une tâche unique de capacité
Ci et de délai critique Di , la charge dans l'intervalle
[ri, di] est ri = Ci/Di (di = ri + Di)
➢ calculée au réveil des tâches (date t = ri)

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 115
Notion de surcharge
●exemple
J1 : (C1 = 2, r1 = 3, d1 = 6)
J2 : (C2 = 3, r2 = 1, d2 = 7)
J3 : (C3 = 1, r3 = 2, d3 = 9)

àt=3
J r1(3) = 2/3
1

J r2(3) = 3/4
2

J r3(3) = 4/6
3 0 1 2 3 4 5 6 7 8 9

r(3) = 3/4

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 116
Notion de surcharge
● en l'absence de possibilité de surcharge, l'optimalité d'un
algorithme est facile à définir et l'importance relative
des tâches n'a pas d'intérêt
● en présence d'un système où l'arrivée dynamique de
tâches est autorisée, il n'y a pas d'algorithme qui
puisse garantir la bonne exécution de l'ensemble des
tâches
● l'importance de l'exécution d'une tâche ne peut pas se
définir seulement à l'aide de son échéance
➢ il est sûrement plus important de faire la mesure d'un
capteur toutes les 10s que de mettre à jour l'heure
sur l'écran de contrôle toute les secondes

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 117
Notion de surcharge
● nécessité de définir une valeur associée à la tâche qui
reflète son importance relative par rapport aux autres
tâches
➢ dans les tâches temps réel, l'échéance fait partie aussi
de la définition de la valeur de la tâche
➢ intérêt de définir une "fonction d'utilité" qui décrit
l'importance de la tâche en fonction du temps
v(fi) v(fi)

non temps réel mou

fi fi

v(fi) v(fi)

ferme dur

fi fi

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 118
Notion de surcharge
● évaluation de la performance d'un algorithme par
● où v(fi) est l'utilité de la tâche à sa terminaison
● remarque : si une tâche temps réel dur dépasse son
échéance, alors ΓA vaut -
● il faut réserver les ressources (entre autres la CPU) pour
garantir les tâches "dures"
● pour un ensemble de n tâches Ji (Ci, Di, Vi), où Vi est
l'utilité de la tâche quand elle se termine avant son
échéance, la valeur maximale de ΓA est

● en conditions de surcharge, la qualité d'un algorithme A se

mesure en comparant ΓA à Γmax
F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 119
Gestion des situations de surcharge
● Rappel : en présence d'un système où l'arrivée
dynamique de tâches est autorisée, il n'y a pas
d'algorithme qui puisse garantir la bonne exécution de
l'ensemble des tâches
● seulement des politiques plus ou moins bien adaptées
aux circonstances
➢ tâches périodiques
➢ tâches quelconques

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 120
Tâches périodiques
● pas d'arrivée dynamique de nouvelles tâches
● durées d'exécutions variables, non forcément bornables
● 2 politiques présentées :
➢ méthode du mécanisme à échéance
➢ méthode du calcul approché

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 121
Méthode du mécanisme à échéance (1)
● principe :
➢ chaque tâche a 2 versions
✔
version primaire assurant une bonne qualité de
service mais dans un temps indéterminé
✔
version secondaire fournissant un résultat
suffisamment acceptable au bout d'un temps
connu
● l'algorithme de tolérance aux fautes doit assurer le
respect de toutes les échéances, soit par le primaire
soit par le secondaire
➢ si les 2 marchent, on garde le primaire
➢ si le primaire ne réussit pas, le secondaire doit réussir
➢ ordonnancement = juxtaposition d'une séquence des
primaires et d'une des secondaires + règle de
décision pour commuter de l'une à l'autre
F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 122
Méthode du mécanisme à échéance (2)
● 2 politiques possibles :
➢ politique de la Première Chance :
✔
Prio (Secondaires) > Prio (Primaires)
✔
⇒ les primaires sont exécutés dans les temps creux
du processeur après leur secondaire
➢ politique de la Seconde Chance :
✔
primaires exécutés avant les secondaires
✔
secondaires exécutés plus tard
✔
si le primaire réussit, le secondaire n'est pas exécuté
● pour obtenir un minimum de qualité de service, il faut un
certain pourcentage de réussite des primaires et donc
garder suffisamment de temps de processeur pour
cela

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 123
Méthode du calcul approché
● chaque tâche est décomposée en 2 parties :
➢ mandataire, fournissant un résultat approché et devant
s'exécuter dans le respect de son échéance
➢ optionnelle, affinant le résultat et exécutée seulement
s'il reste assez de temps
● évite les surcoûts dûs à la coordination entre plusieurs
versions d'une même tâche
● même remarque que précédemment à propos de la
qualité de service minimale

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 124
Tâches quelconques
● modèle canonique des tâches insuffisant, basé sur
➢ urgence ↔ délai critique
● un nouveau paramètre est nécessaire:
➢ importance, codant le caractère primordial de la tâche
dans l'application
➢ définition subjective (cahier des charges)

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 125
Tâches quelconques
● cause fréquente des fautes temporelles : occurrence
d'une tâche apériodique
➢ possible de les rejeter par une routine de garantie,
éventuellement vers un autre processeur moins
chargé dans un environnement réparti
✔
mais le mécanisme est lourd
➢ ⇒ ordonnancement à importance
● 3 classes de politiques pour décider l'acceptation (ou le
rejet) des nouvelles tâches :
➢ meilleur effort
➢ avec garantie
➢ robuste

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 126
Tâches quelconques
● meilleur effort
➢ pas de prédiction en cas de surcharge
➢ les nouvelles tâches sont toujours acceptées
➢ seul moyen d'action : les niveaux relatifs des priorités

toujours Queue des

tâch tâches en cours
e acceptée
prêtes

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 127
Tâches quelconques
● avec garantie
➢ un test d'acceptance est exécuté à l'arrivée de chaque
nouvelle tâche, garantissant la bonne exécution de
toutes les tâches et basé sur les pires hypothèses
➢ si le test d'acceptance n'est pas positif, la tâche est
rejetée
✔
éventuellement, recyclage des tâches rejetées pour
profiter d'une exécution plus rapide que prévue
d'une tâche acceptée
acceptée
test Queue des
tâche en cours
d'acceptabili tâches prêtes
té
rejetée

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 128
Tâches quelconques
● robuste
➢ séparation des contraintes temporelles et de
l'importance des tâches
➢ 2 politiques : une pour l'acceptation de nouvelles
tâches, une pour le rejet de tâches
➢ quand une nouvelle tâche arrive, on exécute un test
d'acceptabilité
✔
si le test passe, la tâche est mise dans la queue des
tâches prêtes
✔
si le test ne passe pas, on exécute l'algorithme de
rejet qui permet d'éliminer une ou plusieurs tâches
de moindre importance
✔
éventuellement, recyclage des tâches rejetées pour
profiter d'une exécution plus rapide que prévue
d'une tâche acceptée

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 129
Tâches quelconques
● robuste
➢ séparation des contraintes temporelles et de
l'importance des tâches
➢ 2 politiques : une pour l'acceptation de nouvelles
tâches, une pour le rejet de tâches
➢ quand une nouvelle tâche arrive, on exécute un test
d'acceptabilité
politique
d'ordonnanceme
nt
tâch Queue des
e Planning tâches en cours
politique prêtes
de Queue des
recyclage tâches politique
rejetées de
réjection

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 130
Test de garantie
● exécuté à chaque réveil d'une tâche
➢ vérifie si la nouvelle tâche peut être exécutée sans
provoquer de faute temporelle
➢ basé sur l'évaluation de la laxité
● T = {Ti(t, Ci(t), di)} tâches actives à t, classées par
di < dj si i<j ordre décroissant d'échéance

➢ surcharge détectée quand LP(t) <0

➢ tâches fautives ⇔ LCi(t) < 0
➢

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 131
Ordonnancement par importance
● critère d'importance utilisé pour éliminer des exécutions
de tâches parmi celles dont les échéances sont
inférieures ou égales à celle de la tâche fautive
● plusieurs politiques possibles :
➢ stabilisation de l'importance des tâches ordonnancées
➢ maximisation de la somme des importances des tâches
garanties

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 132
Stabilisation de l'importance (1)
● assurer que ce sont les tâches les plus importantes qui
font le moins de fautes temporelles
● amélioration du modèle des tâches :
➢ mode de fonctionnement normal
➢ modes de fonctionnement de survie, invoqués quand le
mode de fonctionnement normal doit être arrêté
➢ propriétés d'exécution du mode normal
✔
ajournabilité, quand l'exécution de la tâche peut être
supprimée avant qu'elle n'ait commencé
✔
révocabilité, quand l'exécution de la tâche peut être
supprimée alors qu'elle est déjà commencée
✔
les 4 combinaisons sont possibles

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 133
Stabilisation de l'importance (2)
● 3 modes de survie :
➢ ajournement
➢ révocation
➢ faute temporelle
● les modes d'ajournement et de révocation contiennent
les opérations à exécuter dans chaque cas
➢ communication de résultats à d'autres tâches,
exécution d'un travail paliatif, suppression de tâches
liées par une précédence, etc...
● le mode de faute temporelle est exécuté quand la tâche
commet la faute, et doit être défini pour chacun des
modes normal, ajournement et révocation

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 134
Stabilisation de l'importance (3)
Task T is
begin
Mode Normal
actions du mode normal(Cn,dn,propriétés,Impn)
Mode Ajournement
actions du mode ajournement(Caj,daj,exécution
obligatoire)
Mode Révocation
actions du mode révocation(Crv,drv,exécution
obligatoire)
Mode Faute Temporelle
actions si Faute Temporelle mode normal(Cnf)
actions si Faute Temporelle mode ajournement(Cajf)
actions si Faute Temporelle mode révocation(Crvf)
end

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 135
Stabilisation de l'importance (4)
● exemple
Task T1 is
begin
Mode_Normal(C=10,Ajournable, Revocable, Imp=5)
Acquerir(Capteur);
Lire(Capteur, Temp);
Restituer(Capteur);
-- calculs sur Temp
Temp := Calcul();
-- envoi de Temp à la tâche T2
Send(Temp, {T2});
Old_Temp := Temp;
Mode_Révocation (C=3, Obligatoire, Imp=5)
-- ajournement de T1
Restituer(Capteur);
Ajourner(T2);
Mode_Ajournement (C=2, Obligatoire, Imp=5)
-- calcul d'une valeur depuis l'ancienne valeur
Temp := Old_Temp * facteur_correction
Send(Temp, {T2});
end ;

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 136
Stabilisation de l'importance (5)
● politique de contrôle
➢ par un contrôleur de charge en amont de
l'ordonnanceur

Réveil Mode Normal

Modes normaux
contrôleur de charge non supprimés ordonnanceur
●
détection de surcharge Modes de survie Earliest Deadline First
●
suppressions d'exécution en ●
critère : urgence
fonction de l'importance

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 137
Stabilisation de l'importance (6)
● détection de la surcharge par évaluation de la laxité
➢ à chaque réveil, calcul de la laxité courante de chaque
mode actif
M = {Mxi (r, Cxi(r), dxi, Impxi} avec x = n, aj ou rv, i = 1,
m
et dxi < dxj (i<j) l'ensemble des modes actifs à la date
r triés par échéance croissante
laxité du mode Mxi :
➢ si toutes les laxités sont positives, pas de surcharge
⇒ ordonnancement de la tâche par EDF
➢ M n'est pas ordonnançable s'il existe un mode Mxf pour
lequel la laxité Lxf(r) est négative. Le mode Mxf est
fautif et la surcharge est
|Lxf(r)|

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 138
Stabilisation de l'importance (7)
● résorption de la surcharge par utilisation de l'importance
➢ M' = {Mni(r, Cni(r), dni, Impni), i=1,p, M' ⊆ M l'ensemble
des modes normaux ajournables ou révocables dont
l'échéance dni est inférieure ou égale à dnf
➢ le contrôleur supprime les modes normaux un par un
par ordre croissant d'importance. A chaque
suppression, le mode de survie correspondant est
activé (révocation ou ajournement suivant que la
tâche est démarrée ou non)
➢ la surcharge est résorbée quand la somme des temps
d'exécution des modes de survie activés est
supérieure ou égale à la valeur de la surcharge
➢ s'il n' y a pas assez de modes normaux dans M', alors
des fautes temporelles subsisteront et il faudra
exécuter les modes de survie faute temporelle
F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 139
Optimisation de la somme des importances
● algorithme RED (Robust Earliest Deadline) [Buttazzo]
➢ gestion des tâches apériodiques dans un environnement
temps réel ferme
➢ introduit la notion de tolérance sur l'échéance, c'est-à-
dire le retard après l'échéance pendant lequel le
résultat est encore acceptable
➢ tâches caractérisées par
✔ le temps d'exécution dans le pire des cas C i
✔ l'échéance normale Di (échéance "primaire")
✔ la tolérance sur l'échéance Mi (échéance
"secondaire")
✔ la valeur Vi
➢ les tâches sont acceptées sur leur échéance secondaire
et ordonnancées sur leur échéance primaire

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 140
Optimisation de la somme des importances
● détection de la surcharge par les algorithmes classiques
basés sur la laxité résiduelle
● pour un ensemble de tâches J={J 1, J2,... , Jn} classées
par ordre d'échéances croissantes, la laxité résiduelle
peut être calculée efficacement par la formule
Li = Li-1 + (di – di-1) - ci(t)
● on peut définir
➢ le temps de dépassement : Ei = max (0, -(Li + Mi))
➢ le temps de dépassement maximal : Emax = max(Ei)
● un ordonnancement sera
➢ faisable ssi Li ³ 0 pour toutes les tâches
➢ tolérant ssi il existe des Li < 0 mais que Emax = 0

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 141
Optimisation de la somme des importances
● test d'acceptance pour la tâche Jnew

E = 0 ;
L0 = 0 ;
d0 = current_time() ;
J' = J ∪ {Jnew} ;
k = <position de Jnewdans l'ensemble J'> ;

for each task J'i telle que i ≥ k do {

/* calcul du temps de dépassement maximum */
Li = Li-1 + (di - di-1) - ci ;
if (Li + Mi < -E) then E = -(Li + Mi) ;
}

if (E > 0) {
<selectionner un sous-ensemble J* de tâches à rejeter>;
<rejeter les tâches de J*> ;
}
F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 142
Optimisation de la somme des importances
● plusieurs stratégies pour respecter les échéances des
tâches critiques
➢ la plus simple : rejet d'une tâche, en choisissant la
tâche de plus petite importance dont le temps
d'exécution résiduel est plus grand que la surcharge
● les tâches rejetées sont mises dans une file d'attente,
classées par ordre décroissant de valeur
● quand une tâche termine son exécution avant sa pire
échéance, l'algorithme essaie de réinjecter les tâches
de plus grande valeur et de laxité positive. Les tâches
de laxité négative sont définitivement éliminées

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 143
exemple
● 2 tâches périodiques
➢ Tp1 (r0=0, C=1, D=7, P=10, Imp=3)
➢ Tp2 (r0=0, C=3, D=4, P=5, Imp=1)
● 4 tâches apériodiques
➢ Tap3 (r0=4, C=0.2, d=5, Imp=4)
➢ Tap4 (r0=5.5, C=1, d=10, Imp=5)
➢ Tap5 (r0=6, C=1, d=8, Imp=2)
➢ Tap6 (r0=7, C=1.5, d=9.5, Imp=6)
● ordonnancées par EDF
● T(t) est la configuration des tâches actives à l'instant t
● d est la date de l'échéance
(ne pas confondre avec le délai critique D)

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 144
exemple
● à t=0, Tp1 et Tp2 se réveillent
➢ T(0)={Tp2(C(0)=3, d=4), Tp1(C(0)=1, d=7)}
➢ L(Tp2) = 4 - 0 - 3 = 1
➢ L(Tp1) = 7 – 0 – 3 = 4
➢ pas de surcharge, Tp2 est élue, puis Tp1 est élue à t=3

0 4 5 5.5 6 7 8 9 9.5 10

Tp1
C=1, D=7,
P=10, Imp=3

Tp2
C=3, D=4,
P=5, Imp=1

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 145
exemple
● à t=4, Tap3 se réveille
➢ T(4) = {Tap3(C(4)=0.2, d=5)}
➢ L(Tap3) = 5 – 4 – 0.2 = 0.8
➢ pas de surcharge, Tap3 est élue

0 4 5 5.5 6 7 8 9 9.5 10

Tp1
C=1, D=7,
Tap3
P=10, Imp=3 r0= 4
C=0.2,
d=7, Imp=4
Tp2
C=3, D=4,
P=5, Imp=1

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 146
exemple
● à t=5, Tp2 se réveille
➢ T(5) = {Tp2(C(5)=3, d=9)}
➢ L(Tp2) = 9 – 5 – 3 = 1
➢ pas de surcharge, Tp2 est élue

0 4 5 5.5 6 7 8 9 9.5 10

Tp1
C=1, D=7,
Tap3
P=10, Imp=3 r0= 4
C=0.2,
d=7, Imp=4
Tp2
C=3, D=4,
P=5, Imp=1

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 147
exemple
● à t=5.5, Tap4 se réveille
➢ T(5.5) = {Tp2(C(5.5)=2.5, d=9), Tap4(C(5.5)=1, d=10)}
➢ L(Tp2) = 9 – 5.5 – 2.5 = 1
➢ L(Tap4) = 10 – 5.5 – 1 – 2.5 = 1
➢ pas de surcharge, Tp2 garde la CPU

0 4 5 5.5 6 7 8 9 9.5 10

Tp1
C=1, D=7,
Tap3 Tap4
P=10, Imp=3 r0= 4 r0= 5,5 C=1,
C=0.2, d=10, Imp=5
d=7, Imp=4
Tp2
C=3, D=4,
P=5, Imp=1

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 148
exemple
● à t=6, Tap5 se réveille
➢ T(6) = {Tap5(C(6)=1, d=8), Tp2(C(6)=2, d=9) Tap4(C(6)=1, d=10)}
➢ L(Tap5) = 8 – 6 – 1 = 1
➢ L(Tp2) = 9 – 6 – 1 – 2 =0
➢ L(Tap4) = 10 – 6 – 1 – 2 – 1 = 0
➢ pas de surcharge, Tap5 préempte Tp2

0 4 5 5.5 6 7 8 9 9.5 10

Tp1
C=1, D=7,
Tap3 Tap4 Tap5
P=10, Imp=3 r0= 4 r0= 5,5 C=1, r0= 6 C=1,
C=0.2, d=10, Imp=5 d=8, Imp=2
d=7, Imp=4
Tp2
C=3, D=4,
P=5, Imp=1

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 149
exemple
● à t=7, Tap6 se réveille
➢ T(7) = {Tp2(C(7)=2, d=9), Tap6(C(7)=1.5, d=9.5), Tap4(C(7)=1,
d=10)}
➢ L(Tp2) = 9 – 7 - 2 = 0
➢ L(Tap6) = 9.5 – 7 – 2 - 1.5 = -1
➢ surcharge, Tap6 est fautive avec une surcharge de 1
➢ suppression de tâches dont les échéances sont inférieures ou
égales à celles de Tap6 par ordre croissant des importances
⇒ suppression de Tp2
➢

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 150
exemple
● nouvelle configuration à t=7
➢ T(7) = {Tap6(C(7)=1.5, d=9.5), Tap4(C(7)=1, d=10)}
➢ L(Tap6) = 9.5 – 7 – 1.5 = 1
➢ L(Tap4) = 10 – 7 – 1 – 1.5 = 0.5

0 4 5 5.5 6 7 8 9 9.5 10

Tp1 Tap6
C=1, D=7,
Tap3 Tap4 Tap5
P=10, Imp=3 r0= 4 r0= 5,5 C=1, r0= 6 C=1, r0= 7 C=1.5,
C=0.2, d=10, Imp=5 d=8, Imp=2 d=9,5, Imp=6
d=7, Imp=4
Tp2
C=3, D=4,
P=5, Imp=1

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 151
exemple
● si on avait utilisé un simple algorithme à routine de garantie

0 4 5 5.5 6 7 8 9 9.5 10

Tp1 Tap3 Tap5

C=1, D=7, P=10, r0=4, C=0.2, d=5, r0=6, C=1,
Imp=3 Imp=4 d=8,
Tp2 Tap4 Imp=2 Tap6
C=3, D=4, P=5, r0=5.5, C=1, d=10, r0=7, C=1.5,
Imp=1 Imp=5 d=9.5, Imp=6
➢ temps creux [4,5] = 1: Tap3 acceptée
➢ temps creux [5.5, 10] = 2 : Tap4 acceptée
➢ temps creux [6, 8] = 0 : Tap5 refusée
➢ temps creux [7, 9.5] = 1.5, mais Tap4 doit rester garantie :
Tap6 refusée

F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 152
Conclusion
● on a vu comment ordonnancer "théoriquement" des tâches
ayant des contraintes temporelles de façon à respecter
ces contraintes ou à minimiser les effets du non-respect,
tout en ayant éventuellement des contraintes de
précédence et/ou de partage de ressources
● on va voir étudier maintenant les outils qui vont nous aider
à satisfaire ces contraintes
➢ systèmes d'exploitation
➢ outils de programmation
✔
gestion des tâches (création, destruction, priorités,
etc...)
✔
gestion du temps (alarmes, chronomètres, etc...)
✔
outils de communication (files de messages, mémoire
partagée, etc...)
✔
outils de synchronisation (sémaphores, mutex,
variables conditionnelles, etc...)
F. Touchard Polytech Marseille IRM4 SICA 2012-13 Introduction aux systèmes Temps Réels Ordonnancement 153
TD

154