Partage de ressource dans les

systèmes temps réel

Maria ZRIKEM

Ensa de Marrakech

Ensa de Marrakech, Ordonnancement temps réel 1

 Analyse de l’interaction entre processus

Dans une application industrielle, certaines tâches peuvent être

conduites à coopérer pour réaliser une opération donnée. Cette
coopération se traduit par l’enchaînement imposé de certaines de
leurs actions, par échanges de leurs données ou par leur partage
des mêmes ressources. D’un point de vue opérationnel, les
relations de dépendance qui peuvent apparaître ainsi entre les
tâches sont de deux types :
• les contraintes de précédence qui expriment les relations de
synchronisation et de communication entre les tâches ;
• le partage de ressources dont l’utilisation n’est pas possible
qu’on exclusion mutuelle : les ressources critiques.

Ensa de Marrakech, Ordonnancement temps réel 2

 Analyse de l’interaction entre processus
Notations :
• Arrivée Ai (ou Oi Offset)
• Temps de calcul maximum sans préemption Ci
• Echéance (deadline) : relative ou absolue Di
• Date de début (start time) Si
• Date de fin (finish time) Fi
• Retard (lateness) Li = (Di - Fi)
• Laxité (slack time) xi(t) = Di - (t + Ci - ci(t))
Xi = xi(Ai) = (Di - Ai - Ci)
Ci

Ensa de Marrakech, Ordonnancement temps réel 3

 Partages de ressources critiques
Prise en compte des cas de blocage : inversions des priorités
Exemple : 3 taches T1, T2, T3 données dans l’ordre décroissant des
priorités. T1 et T3 partagent une structure de données protégée par le
sémaphore S. Pendant l’exécution de T3 qui a pris S, T1 démarre. T1
préempte T3 et demande S déjà utilisée par T3. Elle se retrouve donc
bloquée pour un temps indéterminé.
T3 demande est obtient S
Démarrage de T1
T1 demande S T1 obtient S
Démarrage de T2

T1 Plus prioritaire
?

T2

T3 Moins prioritaire

Ensa de Marrakech, Ordonnancement temps réel 4

 Partage de ressources critiques
Problème d’inversion de priorité

T2 se termine avant T1, bien que T1 soit plus prioritaire

T1 est retardée par toutes les tâches de priorité intermédiaire

T3 demande est obtient S

Démarrage de T1
T1 demande S T1 obtient S
Démarrage de T2

T1 Plus prioritaire
?

T2

T3 Moins prioritaire

Ensa de Marrakech, Ordonnancement temps réel 5

 Partage de ressources critiques

Problème d’inversion de priorité

▪ La tâche T3 de priorité intermédiaire qui n’utilise pas la ressource R1 retarde
la tâche T2 et donc la tâche T1

• Il peut y avoir une infinité de tâches T2

• L’attente de T1 ne peut pas âtre bornée

Pouvoir borner l’attente de T1 et inclure cette borne au

test d’acceptabilité́ de la configuration ordonnancer

Test classique + facteur de blocage B

Ensa de Marrakech, Ordonnancement temps réel 6

à
 Héritage de priorité
Héritage de priorité simple ((PIP = Priority Inheritance
Protocol)
⇒ On utilise des sémaphores à priorités, i.e. sachant gérer des files
d’attentes en tenant compte des priorités des tâches qui désirent
prendre le sémaphore
⇒ Lorsque une tâche détient le sémaphore et qu’une autre le réclame, la
priorité de la tâche possédant le sémaphore est augmentée au niveau
de la priorité de la tâche qui réclame le sémaphore. La tâche qui
possède le sémaphore « hérite » ainsi de la priorité de la tâche qui
réclame le sémaphore. Ceci permet de limiter à une seule fois le nombre
de situations d'inversion de priorités.
⇒ Le prix à payer est le blocage des tâches de priorités intermédiaires qui
ne partagent pas la même ressource. Lorsqu'une tâche T bloque
l'exécution de tâches de priorités supérieures, la tâche T s'exécute avec
la priorité maximale des tâches en attente.

Ensa de Marrakech, Ordonnancement temps réel 7

 Analyse de l’interaction entre processus
Héritage de priorité simple (PIP)
Régle d’héritage de priorité : qd blocage d’une tâche T lors de l’accès R, la
tâche bloquante Tl hérite de la priorité courante de T; utilisation par Tl de la
priorité héritée jusqu’ libération de R, o elle retrouve la priorité de la tâche la
plus prioritaire encore bloquée sur R

Ensa de Marrakech, Ordonnancement temps réel 8

à
ù
à
 Analyse de l’interaction entre processus
Héritage de priorité simple (PIP)
Exemple : 3 taches P1, P2, P3 données dans l’ordre décroissant des priorités.
P1 et P3 partagent une structure de données protégée par le sémaphore S.
Pendant l’exécution de P3 qui a pris S, P1 démarre. P1 préempte P3 et
demande S déjà utilisée par P3.
⇒ On garantit que P3 ne sera pas préemptée par P2 quand elle utilisera son
P3 demande est obtient S
sémaphore
Préemption par P1
P1 demande S P1 obtient S Fin P1

P1

P2

P3

P3 hérite de la priorité de P1 P3 relâche S Début P2 Fin P2 Fin P3

Ensa de Marrakech, Ordonnancement temps réel 9
 Analyse de l’interaction entre processus
Héritage de priorité simple (PIP)
Propriétés
• Temps de blocage born (sauf situation d'interblocage)
➢ Possibilité́ de vérification à priori des échéances
• Interblocages possibles
• Pour implanter PIP, il n’est pas nécessaire de connaitre quelle tâche utilise
quelle ressource (par contre, nécessaires pour calculer les temps de
blocage)

Remarque
• N’élimine pas l’inversion de priorité, la rend juste de durée bornée

Ensa de Marrakech, Ordonnancement temps réel 10

é
 Analyse de l’interaction entre processus
Héritage de priorité simple (PIP)
• T1 retardée au plus de la durée de la section critique
• MAIS

- Difficile dans le cas d’une section critique longue

- Blocage des processus de haute priorité n’utilisant pas la section

critique

Ensa de Marrakech, Ordonnancement temps réel 11

 Analyse de l’interaction entre processus
Héritage de priorité simple (PIP)
Remarque: héritage transitif en cas de sections critiques emboitées
• si T partage une ressource R avec T' moins prio qu'elle
• si la section critique sur R inclut l'utilisation d'une ressource R’
• si R' est utilisée par une tâche T'' moins prioritaire que T’
• T' dépend de T'' et par transitivité, T dépend de T''

Temps de blocage
• Définition : durée pendant laquelle une tâche T ne peut plus progresser
cause d'une tâche moins prioritaire qu'elle
• Remarque : une tâche prête peut subir un « blocage » tel qu’il est défini ici

Ensa de Marrakech, Ordonnancement temps réel 12

à
 Analyse de l’interaction entre processus
Comparaison Fin P1

P1
?

P2

P3

Fin P1

P1

P2

P3

Ensa de Marrakech, Ordonnancement temps réel 13

 Héritage de priorité
Héritage de priorité simple : exemple

taches ri ci Prio-i Sections critiques

j1 7 3 1 [V;1]
j2 5 3 2 [S;1]
j3 4 2 3
j4 2 6 4 [V;2,5[S;1,5]]
j5 0 6 5 [S;4]

Ensa de Marrakech, Ordonnancement temps réel 14

 Héritage de priorité
Héritage de priorité simple : exemple
taches ri ci pi Sections critiques
j1 7 3 1 [V;1]
j2 5 3 2 [S;1]
j3 4 2 3
j4 2 6 4 [V ; 2,5 [S;1,5] ]
j5 0 6 5 [S;4]

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

1
2
3
4
5
Ensa de Marrakech, Ordonnancement temps réel 15
 Héritage de priorité
Partage de plusieurs ressources : les iterblocages possibles
Exemple : situation où une tâche P1 exécute la séquence P(S1), P(S2),
tandis que la tâche P2 exécute la séquence P(S2), P(S1). Si l'exécution est
entrelacée comme l'indique le diagramme, les deux tâches se trouvent à
jamais bloquées.

P2 démarre P1 Démarre P1 veut prendre S2

P(S1) P(S2)
P(S2)
P2 veut prendre S1
P(S1)

P
1
P1 est bloquée
Préemption

P2 est bloquée
P2

S2 pris S1 pris

Ensa de Marrakech, Ordonnancement temps réel 16

 Héritage de priorité
Partage de plusieurs ressources : les iterblocages possibles
⇒ Pour assurer l'absence d'interblocage, on doit garantir qu'une tâche ne
pourra commencer l'exécution d'une section critique qu'à condition de
s'exécuter à un niveau de priorité supérieur aux niveaux de priorités
des sections critiques préemptées. Ceci revient à ordonner totalement
les priorités des sections critiques.

⇒ Pour arriver à cet ordre, on définit le plafond de priorité (priority ceiling)

d'un sémaphore (ou priorité d’un sémaphore). Il est égal à la priorité
maximale des tâches pouvant prendre le sémaphore. Cette priorité est
déterminée lors de la conception de l'application.

Priorité(sémaphore) = priorité_max(tâches qui prennent le sémaphore).

Ensa de Marrakech, Ordonnancement temps réel 17

 Héritage de priorité
Héritage par la méthode du verrou le plus haut
Dans la technique d'héritage de priorité par verrou le plus haut (highest
lock), la tâche qui utilise le sémaphore hérite d'une priorité qui est
supérieure au plafond de priorité du sémaphore. Ce protocole a pour effet
d'allonger les périodes d'inversion de priorité : une tâche de plus forte
priorité ne pourra pas démarrer si la tâche de moindre priorité utilise un
sémaphore que la première tâche est susceptible de prendre

π(S1)=π(S1)=Prio T1 P1 prête P1 Démarre P(S1)

P1
P2 démarre P(S2) P(S1) V(S1) V(S2)

P2

S2 pris S1 pris

Ensa de Marrakech, Ordonnancement temps réel 18

 Héritage de priorité
Héritage par la méthode du plafond de priorité (Priority
Ceiling Protocol : PCP)
Dans la méthode dite plafond de priorité, le système d'exploitation maintient
une variable qui représente la valeur maximale des priorités des
sémaphores pris ou plafond courant : lorsqu'une tâche essaye d'exécuter
l'une de ses sections critiques (en essayant de prendre un sémaphore), elle
est suspendue sauf si sa priorité est supérieure aux plafonds de priorités
de tous les sémaphores pris par les autres tâches. Si la tâche T est ainsi
bloquée par la tâche Tp qui possède le sémaphore ayant le plus haut
plafond de priorité, alors Tp bloque T et hérite, en quelque sorte, de la
priorité de T.
⇒ Cette méthode garantit qu'une tâche de haute priorité sera bloquée par au
plus une section critique d'une tâche de priorité inférieure et minimise le
temps de blocage.

Plafond = Max(priorités des sémaphores pris).

Ensa de Marrakech, Ordonnancement temps réel 19

 Héritage de priorité
Héritage par la méthode du plafond de priorité (Priority
Ceiling Protocol : PCP)

Définitions :

Priorité plafond (priority ceiling) d’une ressource R :

π(R) = priorité maximale des tâches qui utilisent la ressource R

Priorité plafond courante (current priority ceiling, ou ceiling) un instant T :

π(t) = maximum des priorités plafond des resources utilisées en t

Ensa de Marrakech, Ordonnancement temps réel 20

à
 Héritage de priorité
Héritage par la méthode du plafond de priorité (Priority
Ceiling Protocol : PCP)
Protocol
• Règle d’allocation de la ressource R demandée par une tâche T
➢ Ressource occupée : blocage (idem PIP)
➢ Ressource libre
✓ T strictement plus prioritaire que π(t), allocation de R T
✓ Sinon, R allouée T si c’est T qui possède la ressource de plafond
π(t), sinon, T est bloquée (diffèrent PIP)
• Règle d’h ritage de priorité
Quand il y’a blocage d’une tâche T lors de l’accès R, la tâche bloquante Ti
hérite de la priorité de T prio(T), et ce jusqu’ ce qu’il libère toute ressource
de plafond supérieur ou égal prio(T). A ce moment, Ti reprend la priorité
qu’elle avait quand elle a acquis la ressource.

Ensa de Marrakech, Ordonnancement temps réel 21

é
à
à
à
à
à
 Héritage de priorité
Héritage par la méthode du plafond de priorité
Exemple : Soient deux tâches T1 et T2 et deux structures de données
partagées protégées par les sémaphores S1 et S2. On suppose que T1
prend les sémaphores dans l'ordre S1 et S2 et T2 les prend dans l'ordre
inverse ; de plus, T1 est de priorité plus grande que T2. Comme T1 et T2
utilisent les deux sémaphores, le plafond de priorité de S1 est égal à la
priorité de T1. Il en va de même pour S2.
π(S1)=π(S2)=Prio T1
T1 Démarre P(S1) refusée car
Prio(T1) ≤ plafond courant

T1

π(t) =Plafond courant=

Max(prio T1, Prio T2)=
Prio T1

T2

S1 pris
T2 démarre P(S2) P(S1) V(S1) V(S2)
S2
pris
Ensa de Marrakech, Ordonnancement temps réel 22
 Héritage de priorité
Héritage par la méthode du plafond de priorité (PCP)
Exemple : partage de ressource R entre T1, T3, T2 utilise une ressource R’
π(R)= prio(T1); π(R') = prio(T2);

Ensa de Marrakech, Ordonnancement temps réel 23

 Héritage de priorité
Exercice

taches ri ci pi Sections critiques

j1 7 3 1 [V;1]
j2 5 3 2 [S;1]
j3 4 2 3
j4 2 6 4 [V;2,5[S;1,5]]
j5 0 6 5 [S;4]

Ensa de Marrakech, Ordonnancement temps réel 24

 taches
j1
ri
7
ci
3
pi
1
Sections
[V;1] Exemple
j2 5 3 2 [S;1]
j3 4 2 3
j4 2 6 4 [V;2,5[S;1,5]] π(V)=Prio(J1)=1
j5 0 6 5 [S;4]
π(S)=Prio(J2)=2

0 1 2 4 6 8 10 12 14 16 18 20

1
2
3
4
5

1
2=П(t)
P4< P1>
3
4
5

Ensa de Marrakech, Ordonnancement temps réel 25

 Comparaison

PCP 0 2 4 6 8 10 12 14 16 18 20

1
2
3
4
5

PIP
1
2
3
4
5

Ensa de Marrakech, Ordonnancement temps réel 26

 Héritage de priorité
Héritage par la méthode du plafond de priorité (PCP)
✓ Propri t s
• Dur e de blocage born e : borne = dur e maximale d’une section critique
d'une t che de priorit inf rieure (plus faible qu’avec PIP)
• Dur e de blocage pour une t che Ti = Dur e de la plus longue section
critique d'une t che de priorité inf rieure et gard e par un s maphore s tel
que π(s) ≥ prio(Ti)
- Identifier les sections critiques des t ches de priorité inf rieure qui
peuvent bloquer Ti (direct + push-through)
- Filtrer toutes les sections critiques vérifiant π(s) ≥ prio(Ti) et prendre le
maximum
• Dur e de blocage maximal Bi plus faible qu’avec PIP
• Pas d’interblocages possibles
✓ Mais nécessite de connaitre toutes les ressources partagées par toutes les
t ches (non transparent pour l’utilisateur)
✓ n’élimine pas l’inversion de priorité, en rend durée bornée

Ensa de Marrakech, Ordonnancement temps réel 27

â
é
é
é
â
é
é
â
é
é
é
â
é
â
é
é
é
é
é
 Héritage de priorité
Protocole de priorité plafond immédiat (Immediate Ceiling
Priority Protocol ICPP)

• Le principe de ICPP est identique à celui de PCP, sauf qu'ici une tâche a
une priorité dynamique qui est le maximum de sa priorité fixe et des
priorités plafond de toutes les ressources qu'elle occupe.
• La priorité d’une tâche augmente dès qu'elle prend une ressource.
• Pas d’interblocages possibles

Ensa de Marrakech, Ordonnancement temps réel 28

 Héritage de priorité
Protocole de priorité plafond immédiat (Immediate Ceiling
Priority Protocol ICPP)

Exemple : Considérons 3 tâches J0, J1 et J2 , avec P0 > P1 > P2,

ainsi que trois ressources partagées R0, R1 et R2 telles que :
• J0 utilise R0 puis R1
• J1 utilise R2
• J2 utilise R2 puis R1
On a donc:
• П(R0)= P0,
• П(R1)= P0,
• П(R2)= P1

Ensa de Marrakech, Ordonnancement temps réel 29

 Héritage de priorité
Protocole de priorité plafond immédiat (Immediate Ceiling
Priority Protocol ICPP)
• J0 utilise R0 puis R1 • П(R0)= P0 P0 > P1 > P2

• J1 utilise R2 • П(R1)= P0

• J2 utilise R2 puis R1 • П(R2)= P1

R0 R1
Exécution J0
normale

R2
Section critique J1

R2 R1 R2
J2
P2
P0
P1

P2

t0 t1 t2 t3 t4 t5 t6 t7 t8 t9

Ensa de Marrakech, Ordonnancement temps réel 30

 Héritage de priorité
Protocole de priorité plafond immédiat (Immediate Ceiling
Priority Protocol ICPP)
R0 R1
Exécution J0
normale
R2
Section critique J1

R2 R1 R2
J2
P2
П(R0)= P0 P0
P1
П(R1)= P0
P2
П(R2)= P1
t0 t1 t2 t3 t4 t5 t6 t7 t8 t9
A t1 : J2 peut prendre R2. J2 entre en section critique avec P2 = П2 = P1.
A l'instant t7 : J1 ne peut prendre R2
A t2 : J1 est activé, J2 peut continuer à s'exécuter car P2 = P1. car cette ressource est prise (par J2 ),
J2 reprend donc son exécution.
A t3 : J2 peut prendre R1 car P2 ≥ Пc et J2 a pris la ressource R2 (Пc = П2).
P2 continue son exécution avec A l'instant t8 : J2 libère R2 et reprend
sa priorité initiale P2: J1 préempte J2
P2 = max{П1 , П2 }= П1 = P0 et prend R2 car on a P1 > Пc.
A t4 : J0 est activé, J2 peut continuer à s'exécuter car P2 = P0. A l'instant t9 : J1 termine son
exécution, J2 peut reprendre et
A t5 : J2 libère R1 et retrouve sa priorité P2 = P1. J2 est alors préemptée par terminer la sienne.
J0 qui commence son exécution.
A t6 : J0 termine son exécution, J1 ou J2 peuvent reprendre la leur
puisqu'elles ont la même priorité, ici par exemple J1 reprend son exécution.
Ensa de Marrakech, Ordonnancement temps réel 31
 Héritage de priorité
Protocole à priorité de pile (Stack Resource Policy SRP)

Idée de base de SRP :

• Les tâches sont bloquées au démarrage de leur exécution si on sait que les
ressources qu'elles utilisent ne seront pas disponibles.
• Elle anticipe encore plus le blocage.
Propriétés :
• Implémentation très simple.
• Une tâche se bloque au plus une fois avant le démarrage de son exécution.
• L'ordre d'exécution est comme une "pile".

Ensa de Marrakech, Ordonnancement temps réel 32

 Héritage de priorité
Protocole à priorité de pile (Stack Resource Policy SRP)
• SRP introduit les notions de niveau de préemption (preemption level) et de
plafond de préemption (preemption ceiling).
• Chaque tâche Ti possède un niveau de préemption fixe П'i, et une tâche Ti
ne peut préempter une tâche Tj que si П'i > П'j.
• SRP peut être utilisé aussi bien avec RM qu'avec EDF.
• En priorité fixe, le niveau de préemption d'une tâcheTi est défini comme sa
priorité : П'i = Pi.
• En EDF, le niveau de préemption sera défini comme étant l'inverse de
l'échéance relative d'une tâche : π’i= 1/Di .
• Chaque ressource Rk possède un plafond de préemption П’(Rk) qui est le
maximum des niveaux de préemption des tâches pouvant bloquer sur R k.
• Le système possède un plafond de préemption П’s(t) qui est le maximum
des П’(Rk) utilisées à l’instant t.

Ensa de Marrakech, Ordonnancement temps réel 33

 Héritage de priorité
Protocole à priorité de pile (Stack Resource Policy SRP)

Règles de SRP :
• Une tâche Ti qui arrive à l’instant t peut s’exécuter seulement si :
➢ Si la tâches la plus prioritaires.
➢ Son niveau de préemption est supérieur au plafond de préemption du
système (plafond de préemption courent) : П'i > Π’s(t)

Ensa de Marrakech, Ordonnancement temps réel 34

 Héritage de priorité
Protocole à priorité de pile (Stack Resource Policy SRP)
Exemple (avec priorité statique) :

• La tâche T3 augmente le niveau de préemption à p1

• La tâche T2 ne peut commencer car p2 < Π’s(t) = p1

• La tâche T1 ne peut commencer car p1 = Π’s(t) = p1

• Quand la tâche T3 libère la ressource, le niveau de préemption du système

baisse et toutes les autres tâches peuvent démarrer a s’exécuter.

Ensa de Marrakech, Ordonnancement temps réel 35

 Héritage de priorité
protocole à priorité de pile (Stack Resource Policy SRP)
Propriétés : les même propriétés du PCP tiennent en SRP et en particulier :
• Th1 : Une tâche peut être bloquée au maximum une fois par toute ressource
ou tâche.
• Th2 : Le SRP empêche l’interblocage.
• Corollaire : La durée maximale de blocage d'une tâche est au maximum la
longueur d'une section critique.

➔ Le temps de blocage est le même qu’en PCP (c’est le temps de blocage minimal)

Ensa de Marrakech, Ordonnancement temps réel 36

 Héritage de priorité
Protocole à priorité de pile (Stack Resource Policy SRP)
SRP Vs. PCP

• SRP réduit le nombre de préemption

• SRP est simple implémenter :
➢ pas besoin de faire de l’héritage.
➢ pas besoin de bloquer les tâches dans des files de sémaphores.
➢ il est possible aux tâches de partager la même pile d’exécution.

Ensa de Marrakech, Ordonnancement temps réel 37

 Héritage de priorité
Protocole à priorité de pile (Stack Resource Policy SRP)
Préemption de l’ordonnancement

• Utiliser SRP équivaut à désactiver sélectivement la préemption pour une

durée limitée.
• Nous pouvons désactiver la préemption uniquement pour certains groupes de
tâches.
• Le SRP est une généralisation du mécanisme de masquage de préemption.

Ensa de Marrakech, Ordonnancement temps réel 38

 Analyse de l’interaction entre processus
Les protocoles de synchronisation avec EDF
Le protocole d'héritage de priorité et le protocole de priorité à pile peuvent être
utilisés sous EDF sans aucune modification.
• Sous PIP :
• Lorsqu'une tâche de priorité supérieure est bloquée par une tâche de
priorité inférieure sur un sémaphore partagé, la tâche de priorité inférieure
hérite de la priorité de la tache bloquée.
• Dans EDF, la priorité d’une tâche est inversement proportionnelle à son
échéance absolue.
• Ici, on doit substituer une tâche de priorité supérieure à une tâche avec
une échéance précoce et hériter de la priorité avec une échéance
absolue.

Ensa de Marrakech, Ordonnancement temps réel 39

 Analyse de l’interaction entre processus
Les protocoles de synchronisation avec EDF
Niveau de préemption
• Pour calculer le temps de blocage, nous devons d’abord ordonner les
tâches en fonction de leurs niveaux de préemption.
• En priorité fixe, le niveau de préemption est le même que la priorité.
• Dans EDF, le niveau de préemption est défini comme étant πi =1/Di

Ensa de Marrakech, Ordonnancement temps réel 40

 Analyse de l’interaction entre processus
Les protocoles de synchronisation avec EDF
Niveau de préemption
• Si Ti peut préempter Tj, alors les deux conditions suivantes doivent être
remplies :
• Ti arrive après que Tj ait commencé à s'exécuter et donc ai > aj
• Le délai absolu de Ti est plus court que le délai absolu de Tj (di ≤ dj)
Il s'ensuit que :
di =ai +Di ≤ dj =aj +Dj
Di −Dj ≤ aj −ai <0

Di <Dj

πi > πj

Ensa de Marrakech, Ordonnancement temps réel 41

 Tâches avec contraintes de précédence

On dit qu’il existe une contrainte de précédence entre la tâche

Ti et la tâche Tj ou Ti précède Tj si Tj doit attendre la fin
d’exécution de Ti pour commencer sa propre exécution.

On note : Ti < Tj

Exemple du graphe de précédence liant les neufs tâches

d’une application temps réel :

T5
T8
T2

T1 T4 T6 T7

T3 T9

Ensa de Marrakech, Ordonnancement temps réel 42

Tâches avec contraintes de précédence

Ensa de Marrakech, Ordonnancement temps réel 43

 Tâches avec contraintes de précédence

Objectifs:

1. Dans le cadre d’un ordonnancement préemptif basé sur la

priorité, quelle est la modification des paramètres de tâches
qui permettra une exécution dans le respect des échéances

2. Décider de la faisabilité hors ligne, i.e. Valider à priori

l’ordonnançabilité d’une configuration de tâches
indépendantes

Ensa de Marrakech, Ordonnancement temps réel 44

 Tâches avec contraintes de précédence

▪ Transformer la configuration de taches en une configuration

de taches indépendante

▪ Travaux de [Chetto 1990] en se basant sur l’algorithme ED

▪ Généralisation aux algorithmes RM et DM par [Babau 1996]

Ensa de Marrakech, Ordonnancement temps réel 45

s

 Tâches avec contraintes de précédence

Une réponse à la question 1 a été faite par Blazewicz [BLA 76] et
Chetto et al [CHE 90].

▪ Principe de la solution : rendre les tâches indépendantes en

modifiant leurs paramètres. Si Ti < Tj, la transformation des
paramétres doit respecter :

✓ rj ≥ r i

✓ prioi > prioj dans le respect de la politique d’ord. utilisée

▪ Hypothèses : Tâches soit apériodiques, soit périodiques de

même période (Si une tache est périodique, l’autre l’est
obligatoirement et PA=PB)
▪ Technique : selon RM, Selon EDF

Ensa de Marrakech, Ordonnancement temps réel 46

 Contraintes de précédence et « Rate Monotonic »
On transformes hors ligne l’ensemble des tâches avec contraintes de
précédence en un ensembles de tâches indépendantes pour lequel te test de
faisabilité RM est respecté. Cette transformation s’opère sur le paramètre de
réveil r et sur l’affectation des priorités :

• r*i = Max(ri, r*j) , Tj < Ti

• si Ti < Tj , prioi > prioj dans le respect de RM

Exemple de tâches à départ simultané liées

par des contraintes de précédence
T3
T1 T2 T3 T4 T5 T6
T1 T2 T5 6 5 4 3 2 1

Tableau des priorités respectant les contraintes

T4
Précédence et celle de la RM.
T6

Ensa de Marrakech, Ordonnancement temps réel 47

 Contraintes de précédence et « Deadline Monotonic »
Le principe est de modifier les dates de réveil et les délais
critiques (les échéance) de manière à avoir l’échéance d’une
tâche inférieur à celles de ses successeurs :

• r*i = Max(ri, r*j) , Tj < Ti

• D*i = Max(Di, D*j) , Tj < Ti

• si Ti < Tj , prioi > prioj dans le respect de DM

Ensa de Marrakech, Ordonnancement temps réel 48

 Contraintes de précédence et « EDF »
• Une tâche ne sera activable que si tous ses prédécesseurs ont
terminé leur exécution :

r*i = Max(ri , Max(r*j + Cj)) , Tj < Ti

• l’échéance d’une tâche doit être inférieur à toutes les

échéances de ses successeurs immédiat diminuées de leurs
temps d’exécution :

D*i = Min(Di , Min(D*j - Cj) , Ti < Tj)

T1 T2 T3

Calculs des r*i Calculs des D*i

Ensa de Marrakech, Ordonnancement temps réel 49

 Contraintes de précédence
Exemple :
On considère les 5 tâches T1, T2, T3, T4 et T5 liées par le graphe de
précédences suivant :

Paramètres des tâches RM EDF

Tâche ri Ci Di r*i Prioi r*i D*i
T3
T1 0 1 5 0 2 0 3
T1 T5
T2 5 2 7 5 1 5 7
T4
T3 0 2 5 0 3 1 5

T2 T4 0 1 10 5 3 7 9

T5 0 3 12 5 4 8 12

Prise en compte des contrainte de précédence par modification

des paramètres temporels et affectation des priorités
Ensa de Marrakech, Ordonnancement temps réel 50
 Contraintes de précédence

Ensa de Marrakech, Ordonnancement temps réel 51

 Contraintes de précédence

Ensa de Marrakech, Ordonnancement temps réel 52

 Contraintes de précédence

Ensa de Marrakech, Ordonnancement temps réel 53

 Contraintes de précédence

Ensa de Marrakech, Ordonnancement temps réel 54

 Contraintes de précédence

Ensa de Marrakech, Ordonnancement temps réel 55

 Contraintes de précédence

Ensa de Marrakech, Ordonnancement temps réel 56

 Contraintes de précédence

Ensa de Marrakech, Ordonnancement temps réel 57

 Contraintes de précédence

Ensa de Marrakech, Ordonnancement temps réel 58

 Contraintes de précédence

Ensa de Marrakech, Ordonnancement temps réel 59

 Contraintes de précédence

Ensa de Marrakech, Ordonnancement temps réel 60

 Contraintes de précédence

Ensa de Marrakech, Ordonnancement temps réel 61

 Contraintes de précédence

Ensa de Marrakech, Ordonnancement temps réel 62

 Contraintes de précédence

Ensa de Marrakech, Ordonnancement temps réel 63

 Contraintes de précédence

Ensa de Marrakech, Ordonnancement temps réel 64