Ordonnancement Temps Réel - Polytech Marseillefrancois.touchard.perso.luminy.univ-amu.fr/ECM/C2-ordonnancement.… · le but de l'ordonnancement est de permettre le respect de ces

F. Touchard Introduction aux systèmes Temps Réels Ordonnancement 1

OrdonnancementTemps Réel


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


Caractéristiques des tâches (1)

● r : date de réveilmoment 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 = r

0 + k*P

➢ si D = P, tâche à échéance sur requête

r0

d0

r1

d1

r2C

D

P P

t



● 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)



● 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


États d'une tâche

Courante

Bloquée

Inexistante

Prête

ff

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

Passive


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))

U=∑i=1

n Ci

Pi

CH=∑i=1

n Ci

Di

LCit=Di−∑Cit


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


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


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

11

Ordonnancement destâches indépendantes


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


tâches périodiques


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)

● 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%● on peut montrer que RMA est un algorithme « optimal » :

➢ une configuration qui ne peut pas être ordonnancée par RMA ne pourra pas être ordonnée par un autre algorithme à priorité fixe

∑i=1

n Ci

Pi

n 21 /n−1


Rate Monotonic Analysis (RMA)

● exempleT

1 (r

0=0, C=3, P=20), T

2 (r

0=0, C=2, P=5), T

3 (r

0=0, C=2, P=10)

∑Ci

Pi

= 3/202/52/10 = 0,75 n 21 /n−1 = 0,77ordonnança

ble

0 5 7 10 12 15 17 202

T2

0 2 4 12 14 2010

T3

T1

0 4 205 7 9

0 2 4 12 14 20105 7 9 15 17

≤

Prio2 > Prio

3 > Prio

1


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

∑i=1

n Ci

Di

⩽n(21/n−1)


Deadline Monotonic Analysis (DMA)

● exempleT

1 (r

0 = 0, C=3, , D=7, P=20), T

2 (r

0 = 0, C=2, D=4, P=5),

T3 (r

0 = 0, C=2, D=9, P=10)

∑Ci

Di

= 3 /7+2 /4+2 /9 = 1,14 n 21 /n−1 = 0,77≥faut voir...

0 5 7 10 12 15 17 204 9 19142

T2

0 2 5 7 20

T1

0 12 14 207 9 10 19

T3

Prio2 > Prio

1 > Prio

3


Earliest Deadline First (EDF)

● algorithme à priorité variable ou dynamique● 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

● test d'acceptabilité ➢ condition nécessaire

➢ condition suffisante

● on peut montrer que EDF est un algorithme optimal pour les algorithmes à priorité dynamique

∑i=1

n Ci

Pi

≤1

∑i=1

n Ci

Di

≤1


Earliest Deadline First (EDF)

● exempleT1 (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)

∑Ci

Pi

= 3 /202/52/10 = 0,75 < 1

∑Ci

Di

= 3 /72/42/8 = 1,18 > 1

0

0

0

2 5

5

8

7

10 12

12 14

15 17 20

20

20

4

7

9

8 10

19

18

142 5 7

T1

T2

T3

chronogramme


Exercice

● soit une configuration avec 2 tâches à échéance sur requête :

T1 : (r

0 = 0, C

1 = 2, P

1 = 5)

T2 : (r

0 = 0, C

2 = 4, P

2 = 7)

● intervalle d'étude ?● la configuration est-elle ordonnançable avec RMA ?

Justifiez votre réponse.● même question avec EDF● tracer les chronogrammes en indiquant les éventuelles

fautes temporelles


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


Least Laxity First (LLF)

● exemplemême configuration que pour EDFT1 (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...

0 8 10 12 15 17 204 9 19142 5 7

T1

T2

T3

1 3 6 11 13 16 18

0 8 10 12 15 17 204 9 19142 5 71 3 6 11 13 16 18

0 8 10 12 15 17 204 9 19142 5 71 3 6 11 13 16 18

t = 0 L

1 = 7-3 = 4, L

2 = 4-2 = 2, L

3 = 8-2 = 6

t = 1 L

1 = 3, L

2= 2, L

3 = 5

t = 2 L

1 = 2, L

3 = 4

t = 3L

1 = 2, L

3 = 3

t = 4L

1 = 2, L

3 = 2

t = 5L

2 = 2, L

3 = 1

t = 6L

2 = 1, L

3 = 1

t = 7L

2 = 0


Traitement des tâches apériodiques


Introduction

● tâches prises en compte dans une configuration comprenant déjà des tâches périodiques critiques➢ les tâches apériodiques peuvent être critiques (contrainte

stricte) ou non (contrainte relative)

● 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➢ besoin d'une hypothèse sur le taux d'arrivée maximal des

requêtes➢ les tâches apériodiques dont le taux d'arrivée est borné

supérieurement sont dites « sporadiques »✔ ⇒ la charge dûe aux tâches apériodiques est bornée✔ on peut garantir la réponse

➢ si le taux d'arrivée n'est pas borné : pas de garantie possible✔ mais garantie éventuelle au cas par cas ✔ test d'acceptance pour les tâches apériodiques critiques

(fermes)


Introduction

● 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➢ beaucoup d'études d'algorithmes


Tâches apériodiquesà contraintes relatives


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 (tâches

critiques)

● ordonnancement relatif des tâches apériodiques en mode FIFO

● préemption des tâches apériodiques par les tâches périodiques

● traitement le plus simple, mais le moins performant


Traitement d'arrière-plan (2)

● ordonnancement RMA des tâches périodiques● exemple

Tp1 (r

0=0, C=2, P=5), Tp

2 (r

0=0, C=2, P=10)

Ta3 (r=3, C=2), Ta

4 (r=10, C=1), Ta

5 (r=11, C=2)

0 5 7 10 12 15 17 202

Tp1

0 14 20102 4 12

Tp2

Temps creux

4 5 7 10 14 15 17 20

Ta3

Ta4

Ta5

4 5 14 171510 11

Tâches apériodiques

7 8 193


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 (RMA)➢ 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


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 (amélioration du temps de réponse)



● exemple de serveur par scrutation (ordonnancement RMA)➢ 2 tâches périodiques : Tp

1 (r0=0, C=3, P=20) Tp

2 (r0=0, C=2, P=10)

➢ serveur : Tps (r0=0, C=2, P=5)

0 202

Tp1

5

0 2 12 14 2010

Tp2

0 2 12 15 2010

Tps

115 7 17

4

4 7 9

∑Ci

Pi

= 3/202/52/10 = 0,75 n 21 /n−1 = 0,77≤



● exemple de serveur par scrutation (ordonnancement RMA)➢ 2 tâches périodiques : Tp

1 (r0=0, C=3, P=20) Tp

2 (r0=0, C=2, P=10)

➢ serveur : Tps (r0=0, C=2, P=5)

➢ tâches apériodiques : Ta3 (r=4, C=2), Ta

4 (r=10, C=1), Ta

5 (r=11, C=2)

0 202

Tp1

5

0 2 12 14 2010

Tp2

0 2 12 15 2010

Tps

5 7 1711

012

Capacité capacitéperdue

Ta5

Tâches apériodiquesTa3

Ta4


● 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



● 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

Traitement par serveur sporadique (1)



● 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 + T

s

➢ RA : montant de la récupération à effectuer à RT✔ calculée à l'instant t

I où le serveur devient inactif ou que la

capacité est épuisée✔ égal à la capacité consommée pendant l'intervalle [t

A, t

I]



● exemple de serveur sporadique à haute priorité➢ 2 tâches périodiques : Tp

1 (r

0=0, C=3, P=20), Tp

2 (r

0=0, C=2, P=10)

➢ serveur : Tps (r

0=0, C=2, P=5)

➢ tâches apériodiques : Ta3 (r=4, C=2), Ta

4 (r=10, C=1), Ta

5 (r=11, C=2)

0 20

Tp1

2 4 7

20 20

Tp2

10

6

12 14

0

Tps

4 6 10 11 12 15 16

Ta5

9012

Capacité

10 12 15 205

Tâches apériodiquesTa3

Ta4


Exercice

● 2 tâches périodiques + 1 serveur sporadique➢ Tp

1 : t

1 = 0, C

1 = 1, T

1 = 5

➢ Tp2 : t

2 = 0, C

2 = 4, T

2 = 15

➢ SS : Cs = 5, T

s = 10

● tâches apériodiques :➢ Ta

1 : t

a1 = 4, C

a1 = 2

➢ Ta2 : t

a2 = 8, C

a2 = 2

● ordonnancement ?


Tâches apériodiquesà contraintes strictes


● les algorithmes précédents restent possibles● mais exécution d'un test d'acceptance avant l'acceptation

ou le rejet de la tâche :➢ suffisamment de temps CPU disponible (processeur oisif ou

capacité serveur disponible) avant l'échéance de la tâche apériodique


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


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


● exemple➢ Tp

1 (r

0=0, C=3, D=7, P=20), Tp

2 (r

0=0, C=2, D=4, P=5),

Tp3 (r

0=0, C=1, D=8, P=10)

➢ Ta4 (r=4, C=2, d=10), Ta

5 (r=10, C=1, d=18),

Ta6 (r=11, C=2, d=16)

Ta6

Tp1

Tp2

Tp3

0

0

2

2

5

4 5 6

5 6

7

8

8

9 10

10

12

12 13

14 15

17

18

19 20

20

20Temps creux

0 8 10 13 15 17 20

Ta4 Ta

5



0 11 15 17 184 13108 16


● exemple➢ Tp

1 (r

0=0, C=3, D=7, P=20), Tp

2 (r

0=0, C=2, D=4, P=5),

Tp3 (r

0=0, C=1, D=8, P=10)

➢ Ta4 (r=4, C=2, d=10), Ta

5 (r=10, C=2, d=18),

Ta6 (r=11, C=2, d=16)

16

Tp1

Tp2

Tp3

0

0

2

2

5

4 5 6

5 6

7

8

8

9 10

10

12

12 13

14 15

17

18

19 20

20

20Temps creux

0 8 10 13 15 17 20

Ta4 Ta

5



0 11 15 17 184 13108

X Ta6


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



● exemple ➢ Tp

1 (r

0=0, C=3, D=7, P=20), Tp

2 (r

0=0, C=2, D=4, P=5),

➢ Tp3 (r

0=0, C=1, D=8, P=10)

➢ Ta4 (r=4, C=2, d=10), Ta

5 (r=10, C=1, d=18),

Ta4

Ta5

Tp3

Tp2

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

Tp1

0 2 5 7 20

60 5 8 10 14 18 201512 13


0 8 10 11 13 14 184



● exemple ➢ Tp

1 (r

0=0, C=3, D=7, P=20), Tp

2 (r

0=0, C=2, D=4, P=5),

➢ Tp3 (r

0=0, C=1, D=8, P=10)

➢ Ta4 (r=4, C=2, d=10), Ta

5 (r=10, C=1, d=18),

Ta6 (r=11, C=2, d=16)

Ta4

Ta5

Tp3

Tp2

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

Tp1

0 2 5 7 20

60 5 8 10 14 18 201512 13


0 8 10 11 13 14 184 12

Ta6



● exemple ➢ Tp

1 (r

0=0, C=3, D=7, P=20), Tp

2 (r

0=0, C=2, D=4, P=5),

➢ Tp3 (r

0=0, C=1, D=8, P=10)

➢ Ta4 (r=4, C=2, d=10), Ta

5 (r=10, C=2, d=18),

Ta6 (r=11, C=2, d=16)

Ta4

Ta5

Tp3

Tp2

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

Tp1

0 2 5 7 20

60 5 8 10 14 18 201512 13


0 8 10 11 13 14 184 12

Ta6

48

Ordonnancementde tâches

dépendantes


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)

50

Présentation des contraintes


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

✔ Ta < T

b indique que la tâche T

a est un prédécesseur de T

b

✔ Ta → T


a est un prédécesseur

immédiat de Tb

T1

T2 T

3

T5

T4



● 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

✔ Ta < T


a est un prédécesseur de T

b

✔ Ta → T


a est un prédécesseur

immédiat de Tb

T1

T2 T

3

T5

T4

T1 < T

2

T1 < T

4

T1 T

2

T1 T

4


➢ exemple : reconnaissance de formes

acq1 acq2

image1 image2

forme

hauteur

diff

reconn

✘ 8 tâches● 2 acquisitions● 2 traitements image● analyse de forme● analyse des différences● calcul de hauteur● reconnaissance finale


camérastéréoscopique objets défilants

sur un tapis roulant

systèmed'acquisition

et de traitement


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


● phénomènes de blocage et d'inversion de priorité

Exécution normale

Section critique

Priorité(T1) > Priorité(T

2)

T1

T2

Demande

Demande

Libère

Libère


➢ le délai imposé par T2 à T

1 est « normal »

Δt


● phénomènes de blocage et d'inversion de priorité

Exécution normale

Section critique

Priorité(T1) > Priorité(T

3) > Priorité(T

2)

T1

T2

Demande

Demande

T3

Libère

Libère


➢ le délai supplémentaire apporté à T1 par T

3 est dû au

phénomène d' « inversion de priorité »

δt


● 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

Quelques « anomalies » d'ordonnancement


● exemple ➢ 9 tâches de priorités décroissantes

(Prio(Ji) > Prio(J

j)) ⇔ i > j

➢ contraintes de précédence et temps d'exécution :

J1 (3)

J2 (2)

J3 (2)

J4 (2) J

5 (4)

J6 (4)

J7 (4)

J8 (4)

J9 (9)



➢ ordonnancement optimal sur un système à 3 processeurs

➢ sur un système à 4 processeurs :

1 2 3 4 5 6 7 8 9 10 11 12 13 1415 16 17 180

J1

J9

J2

J4

J5

J7

J3

J6

J8

P1

P2

P3

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 180

J1

J9

J2

J4

J5

J7

J3

J6

J8

P1

P2

P3

P4

J1 (3)

J2 (2)

J3 (2)

J4 (2) J

5 (4)

J6 (4)

J7 (4)

J8 (4)

J9 (9)




➢ en réduisant d'une unité le temps de calcul des tâches

1 2 3 4 5 6 7 8 9 10 11 12 13 1415 16 17 180

J1

J9

J2

J4

J5

J7

J3

J6

J8

P1

P2

P3

1 2 3 4 5 6 7 8 9 10 11 12 13 1415 16 17 180

J1

J9

J2

J4

J5

J7

J3

J6

J8

P1

P2

P3

J1 (3)

J2 (2)

J3 (2)

J4 (2) J

5 (4)

J6 (4)

J7 (4)

J8 (4)

J9 (9)

J1 (2)

J2 (1)

J3 (1)

J4 (1) J

5 (3)

J6 (3)

J7 (4)

J8 (3)

J9 (8)




➢ en supprimant quelques relations de précédence

1 2 3 4 5 6 7 8 9 10 11 12 13 1415 16 17 180

J1

J9

J2

J4

J5

J7

J3

J6

J8

P1

P2

P3

1 2 3 4 5 6 7 8 9 10 11 12 13 1415 16 17 180

J1

J9

J2

J4

J5

J7

J3

J6

J8P

1

P2

P3

J1 (3)

J2 (2)

J3 (2)

J4 (2) J

5 (4)

J6 (4)

J7 (4)

J8 (4)

J9 (9)

J1 (3)

J2 (2)

J3 (2)

J4 (2) J

5 (4)

J6 (4)

J7 (4)

J8 (4)

J9 (9)



● exemple d'anomalie sur des contraintes de ressources➢ 5 tâches allouées statiquement à 2 processeurs

J2 et J

4 partagent une ressource exclusive

➢ si on réduit le temps d'exécution de J1

1 2 3 4 5 6 7 8 9 10 11 12 13 1415 16 17 180 19 20 21 22

J1

J2

J4

J5

J3

P1

P2

1 2 3 4 5 6 7 8 9 10 11 12 13 1415 16 17 180 19 20 21 22

J1

J2

J4

J5

J3

P1

P2


Algorithmes d'ordonnancement


● ici, seulement précédence simple➢ si T

i est périodique de période P

i, alors T

j l'est aussi et P

j = P

i

● 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 T

i → T

j alors la règle de transformation doit respecter

✘ rj r

i

✘ Prioi > Prio

j

➢ validation de l'ordonnançabilité selon des critères utilisés pour des tâches indépendantes

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{r

i, r*

j} pour tous les j tels que T

j → T

i

✔ si Ti → T

j alors Prio

i > Prio

j dans le respect de la règle

d'affectation des priorités par RMA



● 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{r

i, r*


j → T

i

✔ D*i = Max{Di, D*


j → T

i

✔ si Ti → T

j alors Prio

i > Prio

j dans le respect de la règle

d'affectation des priorités par DMA



● 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{r

i, Max{r*

j + C

j}} pour tous les j tels que T

j → T

i

✔ d*i = Min{d

i, Min{d*

j - C

j}} pour tous les j tels que T

i → T

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



● exemple

T1

T2

T3

T4

T5

Paramètres destâches

Tâche ri Ci di

T1 0 1 5T2 5 2 7T3 0 2 5T4 0 1 10T5 0 3 12



● exemple

T1

T2

T3

T4

T5


EarliestDeadline

Tâche ri Ci di r*i d*i

T1 0 1 5T2 5 2 7T3 0 2 5T4 0 1 10T5 0 3 12



● exemple

T1

T2

T3

T4

T5


EarliestDeadline


T1 0 1 5 0T2 5 2 7T3 0 2 5T4 0 1 10T5 0 3 12

T1 n'a pas de prédécesseurr*1 = 0



● exemple

T1

T2

T3

T4

T5


EarliestDeadline


T1 0 1 5 0T2 5 2 7 5T3 0 2 5T4 0 1 10T5 0 3 12

T2 n'a pas de prédécesseurr*2 = 5



● exemple

T1

T2

T3

T4

T5


EarliestDeadline


T1 0 1 5 0T2 5 2 7 5T3 0 2 5 1T4 0 1 10T5 0 3 12


T3 a T1 pour prédécesseurr*3 = Max(r3, r*1+C1) = 1


● exemple

T1

T2

T3

T4

T5


EarliestDeadline

Tâche ri Ci di r*i

T1 0 1 5 0T2 5 2 7 5T3 0 2 5 1T4 0 1 10 7T5 0 3 12


T4 a T1 et T2 pour prédécesseursr*4 = Max(r4, Max(r*1+C1,r*2+C2)) = 7


● exemple

T1

T2

T3

T4

T5


EarliestDeadline


T1 0 1 5 0T2 5 2 7 5T3 0 2 5 1T4 0 1 10 7T5 0 3 12 8


T5 a T3 et T4 pour prédécesseursr*5 = Max(r5, Max(r*3+C3,r*4+C4)) = 8


● exemple

T1

T2

T3

T4

T5


EarliestDeadline


T1 0 1 5 0T2 5 2 7 5T3 0 2 5 1T4 0 1 10 7T5 0 3 12 8 12

T5 n'a pas de successeurd*5 = 12



● exemple

T1

T2

T3

T4

T5


EarliestDeadline


T1 0 1 5 0T2 5 2 7 5T3 0 2 5 1T4 0 1 10 7 9T5 0 3 12 8 12


T4 a T5 pour successeurd*4 = Min(d4,Min(d*5-C5)) = 9


● exemple

T1

T2

T3

T4

T5


EarliestDeadline


T1 0 1 5 0T2 5 2 7 5T3 0 2 5 1 5T4 0 1 10 7 9T5 0 3 12 8 12




● exemple

T1

T2

T3

T4

T5


EarliestDeadline


T1 0 1 5 0T2 5 2 7 5 7T3 0 2 5 1 5T4 0 1 10 7 9T5 0 3 12 8 12




● exemple

T1

T2

T3

T4

T5


EarliestDeadline


T1 0 1 5 0 3T2 5 2 7 5 7T3 0 2 5 1 5T4 0 1 10 7 9T5 0 3 12 8 12


T1 a T3 et T4 pour successeursd*2 = Min(d2,Min(d*3-C3, d*4-C4)) = 3


● exemple

T1

T2

T3

T4

T5


EarliestDeadline


T1 0 1 5 0 3T2 5 2 7 5 7T3 0 2 5 1 5T4 0 1 10 7 9T5 0 3 12 8 12

T

3

T

2

T

1

T

4

T

5

0 1 2 3 4 5 6 7 8 9 10 11 12

0 1 2 3 4 5 6 7 8 9 10 11 12

0 1 2 3 4 5 6 7 8 9 10 11 12

0 1 2 3 4 5 6 7 8 9 10 11 12

0 1 2 3 4 5 6 7 8 9 10 11 12



● exemple

T1

T2

T3

T4

T5


EarliestDeadline


T1 0 1 5 0 3T2 5 2 7 5 7T3 0 2 5 1 5T4 0 1 10 7 9T5 0 3 12 8 12

T

3

T

2

T

1

T

4

T

5

0 1 2 3 4 5 6 7 8 9 10 11 12

0 1 2 3 4 5 6 7 8 9 10 11 12

0 1 2 3 4 5 6 7 8 9 10 11 12

0 1 2 3 4 5 6 7 8 9 10 11 12

0 1 2 3 4 5 6 7 8 9 10 11 12



● exemple

T1

T2

T3

T4

T5


EarliestDeadline


T1 0 1 5 0 3T2 5 2 7 5 7T3 0 2 5 1 5T4 0 1 10 7 9T5 0 3 12 8 12

T

3

T

2

T

1

T

4

T

5

0 1 2 3 4 5 6 7 8 9 10 11 12

0 1 2 3 4 5 6 7 8 9 10 11 12

0 1 2 3 4 5 6 7 8 9 10 11 12

0 1 2 3 4 5 6 7 8 9 10 11 12

0 1 2 3 4 5 6 7 8 9 10 11 12



● 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 !

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(T

1) > prio(T

2) > prio(T

3) > prio(T

4)

✔ si pas de partage de ressource commune :

T1

T2

T3

T4



● 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(T

1) > prio(T

2) > prio(T

3) > prio(T

4)

✔ si partage d'une ressource commune

✔ le retard de T2 dû à T

3 est une "inversion de priorité", non prévue

T1

T2

T3

T4

R1

R1

R1



● 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 T

1, T

2, ... , T

n (période P

i, capacité C

i)

à échéance sur requête➢ partageant m ressources R

1, R

2, ... , R

m

➢ chaque ressource Rj est gardée par un sémaphore binaire

Sj limitant une section critique z

i,j (pour T

i)

➢ Pi : priorité nominale, p

i : priorité active

P1 > P

2 > ... > P

n

➢ zi,j ⊂ zi,k ou zi,k ⊂ zi,j ou zi,j ∩ zi,k = ∅ ∀ zi,j et zi,k

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 T

i cherche à entrer dans une section

critique zi,j et que la ressource R

j est déjà possédée par une

tâche Tk, de priorité plus faible, alors T

i se bloque (sinon T

i

entre dans zi,j)

➢ la tâche Ti, bloquée, transmet sa priorité à T

k 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 p

k est ramenée à

Pk, sinon on donne à p

k la plus haute des priorités des

tâches en attente



● exemple➢ sans héritage de priorité

R1

R1

T1

T2

T3



● exemple➢ sans héritage de priorité

✔ avec héritage de priorité

p3

P1

P3

R1

R1

R1

R1

T1

T2

T3

T1

T2

T3


Blocagedirect

Blocagedirect

Blocageindirect

Blocageindirect


● 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 :

∀ i , 1≤ i≤n , ∑k=1i C

k

Tk

Bi

Ti

≤ i 2 1 /i−1



● problèmes rémanents➢ blocages en chaîne

➢ étreinte fatale (deadlock), si 2 tâches utilisent 2 ressources imbriquées, mais dans l'ordre inverse

Ra

Rb

Ra R

b

T1

T2

T3

T1

T2

Rb

Rb

Ra

Ra

wait (Sa)wait (Sb)signal (Sb)signal (Sa)

wait (Sb)wait (Sa)signal (Sa)signal (Sb)

T1 T2



● 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

Priorité plafonnée


● définition du protocole➢ on attribue à chaque sémaphore S

k une priorité plafond

C(Sk) égale à la plus haute priorité des tâches susceptibles

de l'acquérir➢ soit T

i 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 T

i

➢ pour entrer dans une section critique gardée par un sémaphore S

k, T

i doit avoir une priorité supérieure à

C(S*). Si Pi ≤ C(S*), l'accès à S

k est dénié et on dit que T

i

est bloquée sur S* par la tâche qui possède S*



➢ quand une tâcheTi est bloquée sur l'acquisition d'un

sémaphore, elle transmet sa priorité à la tâche Tk qui

possède le sémaphore (héritage par Tk de la priorité de T

i)

➢ quand Tk sort de la section critique, elle libère le sémaphore

et la tâche de plus haute priorité bloquée sur le sémaphore est réveillée. La priorité active de T

k est modifiée :

✔ si Tk ne bloque aucune autre tâche, elle revient à sa priorité

nominale✔ sinon, T

k prend la priorité la plus élevée des tâches qu'elle

bloque

➢ l'héritage de priorité est transitif : si T3 bloque T

2 et T

2

bloque T1, alors J

3 récupère la priorité de T

1 via T

2



● exemple➢ 3 tâches T

0, T

1, T

2 de priorités décroissantes P

0 > P

1 > P

2

✔ T0 accède séquentiellement à 2 sections critiques gardées

par les sémaphores S0 et S

1

✔ 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(S

0) = P

0

✔ C(S1) = P

0

✔ C(S2) = P

1



➢ à t0, T

2 est activée et démarre. Le sémaphore S

2 est

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


T0

T1

T2

p2

P2

P1

P0

S2

R2

R2

S2 S1

R1

t0 t1 t2 t3t4

t5

R0

S1

t6

S0 S1

R1

t7

S2

t8

S2

t10

R1

C(S0) = P

0

C(S1) = P

0

C(S2) = P

1

t9


➢ à t1, T

1 est activée et préempte T

2


T0

T1

T2

p2

P2

P1

P0

S2

R2

R2

S2 S1

R1

t0 t1 t2 t3t4

t5

R0

S1

t6

S0 S1

R1

t7

S2

t8

S2

t10

R1

C(S0) = P

0

C(S1) = P

0

C(S2) = P

1

t9


➢ à t2, T

1 demande S

2 et est bloquée par le protocole car la

priorité de T1 n'est pas supérieure à la priorité plafond

C(S2)=P

1 (S

2 est le seul sémaphore acquis à t

2)

T2 hérite de la priorité de T

1 et redémarre


T0

T1

T2

p2

P2

P1

P0

S2

R2

R2

S2 S1

R1

t0 t1 t2 t3t4

t5

R0

S1

t6

S0 S1

R1

t7

S2

t8

S2

t10

R1

C(S0) = P

0

C(S1) = P

0

C(S2) = P

1

t9


➢ à t3, T

2 demande et obtient le sémaphore S

1 , car aucune

autre tâche ne détient de ressource


T0

T1

T2

p2

P2

P1

P0

S2

R2

R2

S2 S1

R1

t0 t1 t2 t3t4

t5

R0

S1

t6

S0 S1

R1

t7

S2

t8

S2

t10

R1

C(S0) = P

0

C(S1) = P

0

C(S2) = P

1

t9


➢ à t4 T

0 est réveillée et préempte T

2


T0

T1

T2

p2

P2

P1

P0

S2

R2

R2

S2 S1

R1

t0 t1 t2 t3t4

t5

R0

S1

t6

S0 S1

R1

t7

S2

t8

S2

t10

R1

C(S0) = P

0

C(S1) = P

0

C(S2) = P

1

t9


➢ à t5, T

0 demande le sémaphore S

0 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 (S

2 et S

1) : P

0

T2 hérite de la priorité de T

0 et peut redémarrer


T0

T1

T2

p2

P2

P1

P0

S2

R2

R2

S2 S1

R1

t0 t1 t2 t3t4

t5

R0

S1

t6

S0 S1

R1

t7

S2

t8

S2

t10

R1

C(S0) = P

0

C(S1) = P

0

C(S2) = P

1

t9


➢ à t6, T

2 relâche S

1. Sa priorité p

2 est ramenée à P

1, plus

haute priorité des tâches bloquées par T2

T0 est réveillée et peut alors préempter T

2 et acquérir S

0

puisque la priorité plafond de S2 (seul sémaphore encore

pris) est égale à P1


T0

T1

T2

p2

P2

P1

P0

S2

R2

R2

S2 S1

R1

t0 t1 t2 t3t4

t5

R0

S1

t6

S0 S1

R1

t7

S2

t8

S2

t10

R1

C(S0) = P

0

C(S1) = P

0

C(S2) = P

1

t9


➢ à t7 quand T

0 demande S

1, le seul sémaphore encore tenu

est S2 avec une priorité plafond P

1 T

0 (priorité P

0 > P

1)

obtient S1

T0

T1

T2

p2

P2

P1

P0

S2

R2

R2

S2 S1

R1

t0 t1 t2 t3t4

t5

R0

S1

t6

S0 S1

R1

t7

S2

t8

S2

t10

R1

C(S0) = P

0

C(S1) = P

0

C(S2) = P

1


t9


➢ à t8, T

0 se termine. T

2 peut reprendre son exécution,

toujours avec la même priorité P1


T0

T1

T2

p2

P2

P1

P0

S2

R2

R2

S2 S1

R1

t0 t1 t2 t3t4

t5

R0

S1

t6

S0 S1

R1

t7

S2

t8

S2

t10

R1

C(S0) = P

0

C(S1) = P

0

C(S2) = P

1

t9


➢ à t9, T

2 relâche S

2. Sa priorité est ramenée à sa valeur

nominale P2. T

1 peut alors préempter T

2 et redémarrer

➢ à t10

, T1 se termine, T

2 peut redémarrer et se terminer

C(S0) = P

0

C(S1) = P

0

C(S2) = P

1


T0

T1

T2

p2

P2

P1

P0

S2

R2

R2

S2 S1

R1

t0 t1 t2 t3t4

t5

R0

S1

t6

S0 S1

R1

t7

S2

t8

S2

t10

R1

C(S0) = P

0

C(S1) = P

0

C(S2) = P

1

t9


● 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 B

i

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 à P

i et gardées par des sémaphores dont la

priorité plafond est supérieure ou égale à Pi

Bi = max j ,k {D j ,k ∣ P jPi , C Sk ≥Pi}

∀ i , 1≤i≤n, ∑k=1

i Ck

Tk

Bi

T i

≤ i21/ i−1



exercice

● tâches avec demandes de ressources imbriquées


exemple : la mission Pathfinder

109

Ordonnancement en situations de surcharge


Plan

● notions liées à la surcharge➢ définitions ➢ métrique

● schémas d'ordonnancement➢ classes d'algorithmes➢ tâches périodiques➢ tâches quelconques


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


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


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

C=2Bo

um!

Boum!

Boum!

Boum!


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é C

i

et de délai critique Di , la charge dans l'intervalle [r

i, d

i] est

= Ci/D

i (d

i = r

i + D

i)

➢ calculée au réveil des tâches (date t = ri)

➢

U=∑i=1

n Ci

T i

i t =

∑dk≤di

ck t

di−t = max i t


Notion de surcharge

● exemple J

1 : (C

1 = 2, r

1 = 3, d

1 = 6)

J2 : (C

2 = 3, r

2 = 1, d

2 = 7)

J3 : (C

3 = 1, r

3 = 2, d

3 = 9)

1(3) = 2/3

2(3) = 3/4

3(3) = 4/6

(3) = 3/4

0 1 2 3 4 5 6 7 8 9

J1

J2

J3

i=

∑dk≤di

ck t

di−t

à t = 3


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


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)

fi

v(fi)

fi

v(fi)

fi

v(fi)

fi

non temps réel mou

durferme


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 (C

i, D

i, V

i), où V

i 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

Γ A=∑i=1

n

v( f i)

Γ A=∑i=1

n

v( f i)


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


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é


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


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


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


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)


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


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

Queue destâches prêtes en courstâche toujours acceptée


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

tâcheacceptée Queue des

tâches prêtes en courstest d'acceptabilité

rejetée


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


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é

tâche

politiqued'ordonnancement

Queue destâches prêtes en coursPlanning

politiquede réjection

Queue destâches rejetées

politiquede recyclage


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, C

i(t), d

i)} tâches actives à t, classées par

di < d

j si i<j ordre décroissant d'échéance

➢ surcharge détectée quand LP(t) <0➢ tâches fautives ⇔ LC

i(t) < 0

LCi t=Di−∑j

C j t ,dj≤di Di=di−r i

LP t=MinLCi t


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


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



● 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



Task T is

beginMode 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


● exempleTask T1 is

beginMode_Normal(C=10,Ajournable, Revocable, Imp=5)

Acquerir(Capteur);Lire(Capteur, Temp);Restituer(Capteur); calculs sur TempTemp := Calcul(); envoi de Temp à la tâche T2Send(Temp, {T2});Old_Temp := Temp;

Mode_Révocation (C=3, Obligatoire, Imp=5) ajournement de T1Restituer(Capteur);Ajourner(T2);

Mode_Ajournement (C=2, Obligatoire, Imp=5) calcul d'une valeur depuis l'ancienne valeurTemp := Old_Temp * facteur_correctionSend(Temp, {T2});

end ;




● politique de contrôle➢ par un contrôleur de charge en amont de l'ordonnanceur

Modes normaux non supprimés

Modes de survie

Réveil Mode Normal

contrôleur de charge

● détection de surcharge● suppressions d'exécution en fonction de l'importance

ordonnanceur

Earliest Deadline First● critère : urgence



● détection de la surcharge par évaluation de la laxité➢ à chaque réveil, calcul de la laxité courante de chaque

mode actifM = {M

xi (r, C

xi(r), d

xi, Imp

xi} avec x = n, aj ou rv, i = 1, m

et dxi < d

xj (i<j) l'ensemble des modes actifs à la date r triés

par échéance croissantelaxité du mode M

xi :

➢ 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 M

xf est fautif et la

surcharge est |L

xf(r)|



● résorption de la surcharge par utilisation de l'importance➢ M' = {M

ni(r, C

ni(r), d

ni, Imp

ni), i=1,p, M' M l'ensemble des ⊆

modes normaux ajournables ou révocables dont l'échéance d

ni est inférieure ou égale à d

nf

➢ 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


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 de l'importance de la tâche

➢ les tâches sont acceptées sur leur échéance secondaire et ordonnancées sur leur échéance primaire

✔ (tolérance > 0) est différent de (échéance plus lointaine)


● détection de la surcharge par les algorithmes classiques basés sur la laxité résiduelle

● pour un ensemble de tâches J={J1, J

2,... , J

n} classées par

ordre d'échéances croissantes, la laxité résiduelle peut être calculée efficacement par la formuleL

i = L

i-1 + (d

i – d

i-1) - c

i(t)

● on peut définir ➢ le temps de dépassement : E

i = max (0, -(L

i + M

i))

➢ le temps de dépassement maximal : Emax

= max(Ei)

● un ordonnancement sera➢ faisable ssi L

i ≥ 0 pour toutes les tâches

➢ tolérant ssi il existe des Li < 0 mais que E

max = 0




● 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'> ; /* vs échéance */

for each task J'i telle que i ≥ k do { /* calcul du temps de dépassement maximum */ Li = Li1 + (di di1) ci ; if (Li + Mi < E) then E = (Li + Mi) ;}

if (E > 0) { <selectionner un sousensemble J* de tâches à rejeter>; <rejeter les tâches de J*> ;}


● 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



exemple

● 2 tâches périodiques➢ Tp

1 (r

0=0, C=1, D=7, P=10, Imp=3)

➢ Tp2 (r

0=0, C=3, D=4, P=5, Imp=1)

● 4 tâches apériodiques➢ Tap

3 (r

0=4, C=0.2, d=5, Imp=4)

➢ Tap4 (r

0=5.5, C=1, d=10, Imp=5)

➢ Tap5 (r

0=6, C=1, d=8, Imp=2)

➢ Tap6 (r

0=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)


exemple

● à t=0, Tp1 et Tp

2 se réveillent

➢ T(0)={Tp2(C(0)=3, d=4), Tp

1(C(0)=1, d=7)}

➢ L(Tp2) = 4 - 0 - 3 = 1

➢ L(Tp1) = 7 – 0 – 3 = 4

➢ pas de surcharge, Tp2 est élue, puis Tp

1 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


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, P=10, Imp=3

Tp2

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

Tap3

r0= 4 C=0.2,

d=7, Imp=4


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, P=10, Imp=3

Tp2

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

Tap3

r0= 4 C=0.2,

d=7, Imp=4


exemple

● à t=5.5, Tap4 se réveille

➢ T(5.5) = {Tp2(C(5.5)=2.5, d=9), Tap

4(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, P=10, Imp=3

Tp2

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

Tap3

r0= 4 C=0.2,

d=7, Imp=4

Tap4r0= 5,5 C=1,d=10, Imp=5


exemple


➢ T(6) = {Tap5(C(6)=1, d=8), Tp

2(C(6)=2, d=9) Tap

4(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 Tp

2

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

Tap3

r0= 4 C=0.2,

d=7, Imp=4

Tap4r0= 5,5 C=1,d=10, Imp=5

Tap5r0= 6 C=1,

d=8, Imp=2


exemple


➢ T(7) = {Tp2(C(7)=2, d=9), Tap

6(C(7)=1.5, d=9.5), Tap

4(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 Tap

6 par ordre croissant des importances

⇒ suppression de Tp2


exemple

● nouvelle configuration à t=7➢ T(7) = {Tap

6(C(7)=1.5, d=9.5), Tap

4(C(7)=1, d=10)}

➢ L(Tap6) = 9.5 – 7 – 1.5 = 1

➢ L(Tap4) = 10 – 7 – 1 – 1.5 = 0.5

Tap6r0= 7 C=1.5,

d=9,5, Imp=6

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

Tap3

r0= 4 C=0.2,

d=7, Imp=4

Tap4r0= 5,5 C=1,d=10, Imp=5

Tap5r0= 6 C=1,

d=8, Imp=2


exemple

● si on avait utilisé un simple algorithme à routine de garantie

➢ 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

0 4 5 5.5 6 7 8 9 109.5

Tp1

Tp2

Tap3

Tap4

Tap5

Tap6

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

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

r0=4, C=0.2, d=5, Imp=4

r0=5.5, C=1, d=10,

Imp=5

r0=6, C=1,

d=8, Imp=2

r0=7, C=1.5, d=9.5,

Imp=6


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➢ supports physiques de communication (bus de terrain) ➢ 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...)



Exercice

● traitement en arrière plan avec un algorithme EDF

➢ Tp1 : (r0 = 0, C = 5, D = 25, P = 30)

➢ Tp2 : (r0 = 0, C = 10, D = 40, P = 50)

➢ Tp3 : (r0 = 0, C = 20, D = 55, P = 75)

● période d’étude, ordonnançabilité chronogramme, temps creux ?

➢ Tap1 : (r0 = 40, C = 10, D = 15)

➢ Tap2 : (r0 = 70, C = 15, D = 35)

➢ Tap3 : (r0 = 100, C = 20, D = 40)

➢ Tap4 : (r0 = 105, C = 5, D = 25)

➢ Tap5 : (r0 = 120, C = 5, D = 15)

● Quelles sont les tâches qui peuvent être ordonnancées dans les temps creux des tâches périodiques ?

Documents

Ordonnancement Temps Réel - Polytech Marseillefrancois.touchard.perso.luminy.univ-amu.fr/ECM/C2-ordonnancement.… · le but de l'ordonnancement est de permettre le respect de ces