Plan

Ordonnancement
Obtention des tests de faisabilité entre processus
Analyse de l'interaction entre processus
Inclusion de processus apériodiques
Vers une meilleure maîtrise du temps

Objectifs :
Nous présentons les mécanismes spécifiques qui permettent de prévoir
avec plus d'exactitude le comportement temporel d'un système.
Nous étudions les méthodes d'ordonnancement temps réel.
Ordonnancement /définitions

C'est lors de l'ordonnancement que l'on choisit la tâche qui devient la tâche
courante.
Dans les systèmes temps réel, on espère collecter des informations a priori
pour pouvoir prédire le comportement de l'application.
C'est pourquoi des ordonnancements hors fonctionnement (off line)
prennent les décisions avant l'exécution du système.
Si cela est possible, on a recourt à des algorithmes en ligne (on line) qui
prennent les décisions durant l'exécution du système.
Ordonnancement hors-ligne
La séquence d'ordonnancement est donc pré-calculée avant l'exécution.
A l'exécution, l'ordonnanceur est un simple séquenceur : on parle de cyclic
scheduler
Le séquenceur lit un tableau "modulo la longeur" : pas besoin d'exécutif
multitâche
La mise en œuvre est simple
La surcharge est facilement détectable

Rigidité du séquenceur est une limitation.

1 2 3 4 5 6 7
T1 T1 Nop T2 T3 T1 T2

t=19 (19mod7)=5
Ordonnancement en ligne

L'ordonnanceur implante un algorithme permettant de savoir à tout instant

quel tâche exécuter
L'ordonnancement est un exécutif multitâche conduits par priorité
Les politiques sont importantes et flexibles
Un surcoût en temps et en ressource lors de la mise en œuvre
Les surcharge sont difficile à détecter
Ordonnancement /définitions

Un algorithme est dit statique s'il sait déterminer a priori les

ordonnancements possibles de son système.
Un algorithme est dit dynamique si l'ordonnancement est déterminé lors de
l'exécution. Il permet la prise en compte d'événements « non » prévus.
La faisabilité

Des études ont été menées pour trouver des critères associés aux tâches
pouvant conduire à une politique d'ordonnancement optimale dans certains
cas.
S'il existe un ordonnancement d'un ensemble de tâches qui respecte les
contraintes temporelles associées à ces tâches, alors l'ensemble des tâches
est dit faisable.
Un ordonnancement optimal est un ordonnancement qui peut produire un
ordonnancement pour tout ensemble faisable de tâches.
Critères liés aux tâches

Les tâches périodiques sont celles qui doivent être activées à intervalles
réguliers. Les instants de début d'exécution peuvent varier d'une instance à
l'autre.

Capacité

Deadline

T : période
Exemple :

20 l de fluide 1 versé toutes les 100 ms.

40 l de fluide 2 versé toutes les 150 ms.
Sachant que pour verser un litre de fluide, il faut 1 ms.
100 ms pour une prise de température toutes les 350 ms.

Fluide 2 Fluide 1

Réacteur
Modélisation du problème :

La gestion des 2 fluides et de la température est représentée par 3 tâches

indépendants nommées P1, P2 et P3.

Ces 3 tâches s’effectuent périodiquement avec des temps d’activation

différents (resp. 100, 150 et 350).

Et chacune exige un certain temps d’exécution ( resp. 20, 40 et 100).

Exemple introductif :

T C Fluide 2 Fluide 1
P1 100 20
P2 150 40 Réacteur
P3 350 100

P1
P2
P3

0 100 200 300 400

temps
Exemple introductif :

T C Fluide 1
P1 100 20
P2 150 40 Réacteur
P3 350 100

P1
P2
P3

0 100 200 300 400

temps
Exemple introductif :

T C Fluide 2
P1 100 20
P2 150 40 Réacteur
P3 350 100

P1
P2
P3

0 100 200 300 400

temps
Exemple introductif :

T C
P1 100 20
P2 150 40 Réacteur
P3 350 100

P1
P2
P3

0 100 200 300 400

temps
Exemple introductif :

T C Fluide 1
P1 100 20
P2 150 40 Réacteur
P3 350 100

P1
P2
P3

0 100 200 300 400

temps
Exemple introductif :

T C Fluide 2
P1 100 20
P2 150 40 Réacteur
P3 350 100

P1
P2
P3

0 100 200 300 400

temps
Exemple introductif :

T C
P1 100 20
P2 150 40 Réacteur
P3 350 100

P1
P2
P3

0 100 200 300 400

temps
Exemple introductif :

T C
P1 100 20
P2
P3
150
350
40
100
!
P1
P2
P3

0 100 200 300 400

temps
Critères liés aux tâches

Les tâches sporadiques ne sont pas activées de façon régulière, mais on

peut définir un temps minimal d'apparition entre deux activations d'instances
successives. Elles ont des contraintes de temps fortes.
Les tâches apériodiques sont activées également à des instants irréguliers
mais avec des échéances plus lâches et sans temps minimal entre deux
activations.

Capacité

Deadline

A A+?
Les algorithmes

Les algorithmes d'ordonnancement

statiques pilotés par tables
statiques préemptifs sur les priorités
dynamiques basés sur une planification à l'exécution
dynamiques basés sur la notion de meilleurs efforts
Les ordonnancements cycliques

On cherche à découper a priori une application en séquences élémentaires

qui ne seront jamais interrompues.

Le modèle d'application est le suivant

Une séquence est une procédure définie par l'utilisateur
Un processus est une suite ordonnée de séquences ; qui s'exécutent
consécutivement, dans l'ordre de la déclaration.
L'ordonnancement des processus est régi par un calendrier, c'est une
table spécifiant la liste des processus à activer ; elle est de longueur
arbitraire et exploitée cycliquement.
Le découpage en séquences élémentaires non interruptibles assure la
protection des données partagées entre les processus.
Exemple

T C D
P1: 25 10 25
P2: 25 8 25
P3: 50 5 50
P4: 50 4 50
P5: 100 2 100

Définir :
un cycle majeur PPCM = (25,50,100)=100
un cycle mineur qui correspond au rythme des interruptions d'horloge.

Pendant le cycle mineur l'application ne peut être interrompue.

Ils définissent des points de contrôle permettant de contrôler que les traitements
applicatifs ont bien respecté leurs échéances.
Exemple

T C D
P1: 25 10 25
P2: 25 8 25
P3: 50 5 50
P4: 50 4 50
P5: 100 2 100

P1 P2 P3P5 P1 P2 P4 - P1 P2 P3 - P1 P2 P4 -
10 8 5 2 10 8 4 3 10 8 5 2 10 8 4 3
IT horloge IT horloge IT horloge IT horloge

25

IT horloge = interruption possible

Les inconvénients

Comment prendre en compte des traitements qui ne sont pas périodiques ?

Comment ajouter un traitement supplémentaire sans modifier tout le
système ?
Difficile si le nombre de processus augmente.
Il n'existe pas de solution optimale dont la complexité soit polynomiale
en fonction du nombre de processus.

Mais, il est très utilisé dans les systèmes critiques, en particulier les
systèmes aéronautiques ou les systèmes de défenses.
Les algorithmes de décisions en ligne

Les prise de décision s'effectuent à partir de critères qui peuvent être

statiques (valeur d'une priorité)
dynamique (dépend du temps)

Dans les modèles statiques, on utilise une transformation hors ligne des
contraintes temporelles en entiers fixes représentant les priorités.
Dans les modèles dynamiques, la priorité évoluera en fonction du temps.
Plan

Ordonnancement
Obtention des tests de faisabilité entre processus
Analyse de l'interaction entre processus
Inclusion de processus apériodiques
Obtention de tests de faisabilité d'ordonnancement

Existe-t-il des tests qui permettent de prévoir si un ensemble de tâches va

respecter ses contraintes temporelles ?
Ordonnancement Rate-Monotonic (monotone par taux)

Il désigne la méthode d'affectation hors ligne de priorités statiques à un

ensemble de tâches.
Les critères retenus pour les tâches sont
les tâches sont périodiques et sont à l'état PRÊT au début de chaque
période.
Leur échéance se situe à la fin de la période.
Les tâches peuvent être préemptées.
Les tâches sont indépendantes les unes des autres.
Le temps d'exécution est connu.
L'affectation des priorités aux tâches se fait en fonction de la fréquence
des tâches.

Si Ti désigne la période de la tâche i, sa priorité est égale à 1/Ti

Conditions suffisantes de l'analyse Rate Monotonic

n
U=  durée i / Période i
i=1

Dans le cas où Di=Ti, n tâches respectent toutes les échéances si :

i, 1  i  n Ui =  C i / T i  i(2 1/i

-1)
i=1
Principe de l'obtention

Cas simplifié de deux tâches.

But :
Atteindre une utilisation maximale du processeur en toute sécurité. On
cherche donc une borne d'utilisation maximale pour tout ensemble de
tâches qui utilisent le processeur au maximum de ses capacités.
Démarche :
Pour un C1 donné on cherche C2 de façon à utiliser un maximum le
processeur.
Taux d'utilisation

1,000
0,970
0,940
Taux d'utilisation

0,910
0,880
0,850
0,820
0,790
0,760
0,730
0,700
1 2 3 4 5 6 7 8 9 10
Û 1,000 0,828 0,780 0,757 0,743 0,735 0,729 0,724 0,721 0,718
Nombre de tâches
Exemple pour RM :

T C
P1 100 20
P2 150 40
P3 350 100
Exemple pour RM :

T C
P1 100 20
P2 150 40
P3 350 100

Ci
Ui 
nn
Ci
Ui  TiTi
i11
i

   
U i  20  40  100 0.753
100 150 350
Exemple pour RM :

T C
P1 100 20
P2 150 40
P3 350 100


 11 

 i i  1 
i2
UUiii
2  1
 

L’application numérique pour n = 3 donne :

  31  
Ui 3  2  1 0,779
 
Exemple pour RM :

T C
P1 100 20
P2 150 40
P3 350 100

On a bien, U0,7530,779
i

 La condition de faisabilité est satisfaite

 On peut appliquer l'algorithme RM.
Exemple pour RM :

T C
P1 100 20
P2 150 40
P3 350 100

P1
P2
P3

0 100 200 300 400 temps

Exemple pour RM :

T C
P1 100 20
P2 150 40
P3 350 100

P1
P2
P3

0 100 200 300 400 temps

Exemple pour RM :

T C
P1 100 20
P2 150 40
P3 350 100

P1
P2
P3

0 100 200 300 400 temps

Exemple pour RM :

T C
P1 100 20
P2 150 40
P3 350 100

P1
P2
P3

0 100 200 300 400 temps

Exemple pour RM :

T C
P1 100 20
P2 150 40
P3 350 100

P1
P2
P3

0 100 200 300 400 temps

Exemple pour RM :

T C Préemption de P3 par P1!!!

P1 100 20
P2 150 40
P3 350 100

P1
P2
P3

0 100 200 300 400 temps

Exemple pour RM :

T C
P1 100 20
P2 150 40
P3 350 100 60

P1
P2
P3

0 100 200 300 400 temps

Exemple pour RM :

T C
P1 100 20
P2 150 40
P3 350 100 60

P1
P2
P3

0 100 200 300 400 temps

Exemple pour RM :

T C
P1 100 20
P2 150 40
P3 350 100 60

P1
P2
P3

0 100 200 300 400 temps

Exemple pour RM :

T C
P1 100 20
P2 150 40
P3 350 100 30

P1
P2
P3

0 100 200 300 400 temps

Exemple pour RM :

T C Préemption de P3 par P2!!!

P1 100 20
P2 150 40
P3 350 100 30

P1
P2
P3

0 100 200 300 400 temps

Exemple pour RM :

T C
P1 100 20
P2 150 40
P3 350 100 30

P1
P2
P3

0 100 200 300 400 temps

Exemple pour RM :

T C Préemption de P3 par P1!!!

P1 100 20
P2 150 40
P3 350 100 20

P1
P2
P3

0 100 200 300 400 temps

Exemple pour RM :

T C
P1 100 20
P2 150 40
P3 350 100

P1
P2
P3

0 100 200 300 400 temps

Exemple pour RM :

P
1
P
2
P
3

0 100 200 300 400 500 600 700

0 20 60
20 60 80
Exemple pour RM :

P
1
P
2
P
3

0 100 200 300 400 500 600 700

Utilisation du modulo.
Remarques :
La condition de faisabilité est très restrictive puisque dans l'exemple
précédent, nous étions limités à utiliser le processeur à 77,9 % de sa
capacité totale.

Mais notre but est de l’utiliser au maximum de ses capacités et cela en toute
sécurité.
Quelques précisions :
On néglige le temps de communication et d'ordonnancement.
Elles sont indépendants les unes des autres.
La capacité de chaque tâche est connue.

Leur échéance se situe à la fin de la période.

Les tâches sont périodiques et sont à l’état prêt au début de chaque
période.
Elles ne se suspendent pas elles-mêmes en cours d'exécution.
Exemple

ID Depart C T
T1 3 20
T2 2 5
T3 2 10

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
T2 T2 T3 T3 T1 T2 T2 T1 T1 nop T2 T2 T3 T3 nop T2 T2 nop nop nop
T1 T1 T1 T1
T2 T2 T2 T2 T2 T2 T2 T2 T2
T3 T3 T3 T3 T3
RM Cas d'échec

ID Depart C T D
T1 1 3 3
T2 1 4 4
T3 2 6 3

1 2
T1 T2 T3
T1 T1
T2 T2
T3 T3

0 : T1 est
1 :déclenchée
T1 Finie
2 : T2
son
Finie
pour
exécution
la
son
:1 exécution
fois
N°1 N°1
0 : T2 est
1 :déclenchée
T2 s'exécute
2 : T3 DEADLINE
pour la :1 fois
DEPASSEE de2

Il existe une solution

Théorème de la zone critique

La condition de l'analyse RM est très restrictive.

Théorème : Si toutes les tâches arrivent initialement dans le système
simultanément et si elles respectent leur première échéance, alors toutes
les échéances seront respectées par la suite, quel que soit l'instant d'arrivée
des tâches.
Remarques : C'est une condition nécessaire et suffisante si toutes les
tâches du système sont initialement prêtes au même instant. C'est
uniquement une condition suffisante dans le cas contraire.
Test de terminaison (completion time test)

Si l'échéance Di est égale à la période Ti, le test est le suivant.

i
i, 1  i  n min  C j / t * t / T j  1
0<t<Di j=1

Avec l'indice le plus faible à la tâche la plus prioritaire.

Méthode itérative pour le théorème de la zone critique

On recherche le temps t tel que :

i
i, 1  i  n,  t  Di, t = Cj * t / T j
j=1

i
Soit W i(t) =  C j * t / T j
j=1

Wi(t) représente la demande cumulée de temps processeur de toutes

les tâches jusqu'à la tâche i dans l'intervalle [0,t].

On recherche Wi(t) / Wi(t)=t par itérations successives et ce pour

toutes les tâches i
i
On part de t0 =  Cj, si l'instant t ne respecte pas la condition, on
j=1 itère en prenant comme nouveau temps t = Wi(t)
Exemple

33==300/100
300/100
P1

P2

P3

100 200 300

Soit W i(t) = Cj *t / T j=40*3

Exemple

Pi T C
P1 100 40
P2 150 40  U = 0.779,
P3 350 100 Mais on va montrer que l'exemple
répond au théorème de la zone critique.

Pour i=1 t0 = C1 = 40 = W1(40) Stop

Pour i=2 t0 = C1+C2 = 80 = W2(80) Stop
Pour i=3 t0 = C1+C2+C3 = 180 (>100 et 150)
W 3(180)= 2C1+2C2+C3 = 260
W 3(260)= 3C1+2C2+C3 = 300
W 3(300)= 3C1+2C2+C3 = 300 c'est la condition recherchée

Les trois tâches sont donc ordonnançables selon le théorème de la

zone critique. La troisième tâche terminera l'exécution de sa première
instance au temps 300.
simulation du comportement

600

500

400 Série1
Série2
300
Série3
200 Série4

100

0
1 30 59 88 117 146 175 204 233 262 291 320 349 378
Autre algorithme : inverse deadline

Algorithme avec comme critère l'inverse de la deadline D

Inverse deadline

ID Depart C T D
T1 3 20 7
T2 2 5 4
T3 2 10 9

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

T2 T2 T1 T1 T1 T2 T2 T3 T3 nop T2 T2 T3 T3 nop T2 T2 nop nop nop

T1 T1 T1 T1

T2 T2 T2 T2 T2 T2 T2 T2 T2

T3 T3 T3 T3 T3
Ordonnancements dynamiques

Les ordonnancements sont dits dynamiques car l'allocation de priorité aux

tâches se fait lorsque le système est en fonctionnement.
Ils utilisent l'un des critères suivant à fin de prendre les décisions :
Échéances la plus proche d'abord (Earliest Deadline First) prend en
compte l'urgence du travail à accomplir.
Marge la plus courte d'abord (Least Laxity Fisrt) prend également en
compte l'urgence du travail à accomplir mais lui rajoute la notion de
durée du travail.
Exemple EDF

T C
P1 6 2
P2 8 2
P3 12 3

6 8 12 16 18 24
Exemple LLF Least Laxity Fisrt

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
Exemple

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é

Critère de l'ordonnançabilité EDF et LLF

Si l'on applique les algorithmes EDF et LLF à des tâches indépendantes

périodiques le critère de faisabilité est donné par :

n
Ui =  C i / T i 1
i=1
Optimalité de l'algorithme d'ordonnancement EDF

L'algorithme EDF est dit optimal car si un algorithme arrive à ordonnancer

un ensemble de tâches possédant des échéances et des temps de
traitement arbitraires, alors EDF saura également le faire.
Plan

Ordonnancement
Obtention des tests de faisabilité entre processus
Analyse de l'interaction entre processus
Inclusion de processus apériodiques
Rappels

la communication et la synchronisation
Analyse de l'interaction entre processus

Prise ne compte des cas de blocage : inversion de priorité

Héritage de priorité
Prise en compte des cas de blocage dans l'analyse RM.
Analyse de l'interaction entre processus

Prise en compte des cas de blocage : inversion de priorité.

Hypothèse supplémentaire : Les tâches accèdent en exclusion mutuelle
à des ressources communes. Ceci rend les tâches potentiellement
dépendantes les unes des autres.
Problème : une tâche de plus faible priorité peut bloquer une autre tâche de
priorité plus forte quand elle est en section critique = Problème de l'inversion
de priorité.
Inversion de Priorité
0 1 4 5 6 7 8 10 12 14 15 16

j1 S

j2
fin
S S S
j3

j3j3démarre
démarreààtps=0
tps=0

t0 Rés

+ Prioritaire
j1 2 S(2)
j2 7
Inversion de Priorité
0 1 2 4 5 6 7 8 10 12 14 15 16

j1 S

j2
fin
S S S
j3

j3j3demande
demandeSSààtps=1
tps=1

t0 Rés

+ Prioritaire
j1 2 S(2)
j2 7
Inversion de Priorité
0 1 2 4 5 6 7 8 10 12 14 15 16

j1 S

j2
fin
S S S
j3

j1j1démarre
démarreààtps=2
tps=2

t0 Rés

+ Prioritaire
j1 2 S(2)
j2 7
Inversion de Priorité
0 1 2 4 5 6 7 8 10 12 14 15 16

j1 S

j2
fin
S S S
j3

j1j1demande
demandeSSqui
quiest
estpris
prispar
parj3j3donc
doncililest
estbloqué
bloquéet
et
redonne
redonnelalamain
mainààj3j3
t0 Rés

+ Prioritaire
j1 2 S(2)
j2 7
Inversion de Priorité
0 1 2 4 5 6 7 8 10 12 14 15 16

j1 S

j2
fin
S S S
j3
À t=7, j2 démarre son exécution et
finit à t=10

t0 Rés

+ Prioritaire
j1 2 S(2)
j2 7
Inversion de Priorité
0 1 2 4 5 6 7 8 10 12 14 15 16

j1 S

j2
fin
S S S
j3
À t=10, j2 finit son exécution
et
redonne la main à j3

t0 Rés

+ Prioritaire
j1 2 S(2)
j2 7
Inversion de Priorité
0 1 2 4 5 6 7 8 10 12 14 15 16

j1 S

j2
fin
S S S
j3
A t=12, j3 relâche S et
j1 profite pour récupérer S qu'elle avait demandé

t0 Rés

+ Prioritaire
j1 2 S(2)
j2 7
Inversion de Priorité
0 1 2 4 5 6 7 8 10 12 14 15 16

j1 S

j2
fin
S S S
j3

À t=15, j1finit son exécution et laisse

j3 finir elle aussi.

t0 Rés

+ Prioritaire
j1 2 S(2)
j2 7
 Inversion de priorité
0 1 2 4 5 6 7 8 10 12 14 15 16

j1 Durée
Durée ?? S

j2
fin
S S S
j3

t0 Rés

+ Prioritaire j1 2 S(2)
j2 7
Solutions à l'inversion de priorité
Une tâche ne doit pas être préemptée systématiquement si elle est en
section critique.
Cette solution est acceptable pour des accès courts. Sinon le système
créera des situations d'inversion de priorité fréquentes et inutilement
longues.
Méthode de l'héritage de priorité (priority inherance).
Le système effectue une gestion dynamique de priorité. L'idée est de
rajouter aux sémaphores la notion de possesseurs.
Héritage de priorité

Le possesseur d'un sémaphore est la tâche qui a demandé et obtenu le

droit de rentrer dans la zone d'exclusion mutuelle protégé par le sémaphore.
Dans l'héritage de priorité simple, les sémaphores gèrent leur file d'attente
en tenant compte des priorités des tâches qui désirent prendre le
sémaphore.
Lorsqu'une tâche détient un sémaphore et qu'une autre le réclame, la
priorité de la tâche qui possède le sémaphore est augmentée au niveau de
la priorité de la tâche qui le réclame.
Exemple

T1 demande S Fin T1

Fin T2

Fin T3
T3 relâche S

T3 demande T3 hérite de la priorité + Prioritaire

et obtient S de T1
Comparaison

?
Autre exemple
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

j4j5demande
j1
les demande
démarre.
tâches
j2 Squi
j4 demande
1Vet 2 ne
est
Spartagent
qui
prisest
donc par
j5pris
j4.j4
aucune
par
bloquebloque
[Link].
j4 j5 donc
qui bloque
j1 Déroulement
bloque j2
et et
hérite
hérite
j1,donc saest
j1 sa
priorité.
normale
priorité.
bloqué jusqu’à la fin.
par j5 qui hérite sa priorité (phénomène de Transitivité).
j5 prend la main puis libère S à tps=11.
taches ri ei 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]
Partage de plusieurs ressources : les inter-blocages possibles

Lorsqu'une tâche peut utiliser plusieurs sémaphores des cas d'inter-blocage

peuvent apparaître.
L'inter-blocage n'est pas dû à une inversion de priorité mais à
l'entrelacement des accès aux sémaphores.
Exemple

P(S1) P(S2) T1 bloquée

T1 démarre

P(S2) P(S1)

T2 démarre T2 bloquée
Solutions

1 Demander l'accès aux sémaphores dans le même ordre.

2 Exécuter en exclusion mutuelle toutes les sections correspondant aux
sections critiques imbriquées. On garantit qu'une tâche ne peut commencer
l'exécution d'une section critique qu'à condition de s'exécuter à un niveau de
priorité supérieur aux niveaux de priorité des sections critiques préemptées.
Solution : Héritage par la méthode du verrou le plus haut
Dans la technique du verrou le plus haut (highest lock) la tâche qui utilise un
sémaphore hérite d'une priorité qui est supérieure au plafond de priorité du
sémaphore.
Le plafond de priorité (priority celling) d'un sémaphore est égal à la
priorité maximale des tâches pouvant prendre le sémaphore.
Cela consiste à maintenir une valeur qui représente la valeur maximale
du plafond courant.

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

Plafond=Max(priorités des verrous pris).
Exemple

P(S1) P(S2) V(S2) V(S1)

T1 Prêt

P(S2) P(S1) V(S1) V(S2)

T2 démarre
Solution : Héritage par la méthode du plafond de priorité

Dans la méthode du plafond de priorité (priority ceilling protocol) l'OS

maintient une valeur qui représente la valeur maximale du plafond courant.
Lorsqu'une tâche essaye d'exécuter une section critique, elle est suspendue
sauf si sa priorité est supérieure au plafond de priorité de tous les
sémaphores pris par les autres tâches.
Exemple

P(S2) V(S1)
P(S1) refusé
T1<=Plafond P(S1) V(S2)

T1 démarre

T2 démarre P(S1) V(S1) V(S2)

P(S2) héritage
Plafond = Max(T1,T2)=T1
Exemple

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
?
Comparaison

0 2 4 6 8 10 12 14 16 18 20

1
2
3
4
5

1
2
3
4
5
Plan

Ordonnancement
Obtention des tests de faisabilité entre processus
Analyse de l'interaction entre processus
Inclusion de processus apériodiques
Inclusion de processus apériodiques

On peut penser à interrompre les tâches périodiques pour faire passer les
tâches apériodiques jusqu'à ce que celles ci se terminent. Mais on peut
mettre en péril l'ordonnancement.
On peut affecter la priorité la plus basse aux tâches apériodiques. Cette
solution n'offre qu'un temps de réponse moyen aux tâches apériodiques.
Les serveurs
On affecte un processus périodique en charge de contrôler les taches
apériodiques en leur offrant la possibilité d'exécuter leur activité au niveau
de priorité requis.
Les méthodes existantes
Le serveur par scrutation (polling server)
le serveur différé (deferabe serveur)
Serveur par scrutation

Le serveur de scrutation a la priorité la plus forte. On définit une capacité

Cm pour cette tâche en fonction du profil d'arrivée des événements
apériodiques à servir.
Le serveur est divisé en deux parties
La première regarde périodiquement s'il y a des événements
périodiques à traiter
La deuxième partie est déclenchée s'il y a au moins un événement en
attente d'être traité.
Exemple

T C
P1 10 2 t C
P2 15 6 e1 2 1.5
S 5 2 e2 6 2

e1 e2

0.5

2 5 6 10 11.5 13.5

Scrutation Prise en compte

e1 sera pris en compte e2 prise en compte immédiate
en 5
Serveurs d'événements apériodiques

On fournit une ressource privée (une tâche fictive) à l'usage exclusif des
tâches apériodiques.
On crée une tâche périodique DS, de capacité Cds et de période Tds qui
servent à définir sa priorité selon la méthode RM.
Si toutes les tâches apériodiques sont traitées avec moins de capacité, on
abandonne plus tôt la tâche DS (la capacité non utilisée est alors perdue).
 Exemple
ID Depart C T D
T1 3 20 20
T2 2 10 10
Ta1 4 2
Ta2 10 1
Ta3 11 2
serveur 2 5 5

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
T2 T2 T1 T1 T1 Ta1 Ta1 nop nop nop Ta2 Ta3 T2 T2 nop Ta3 nop nop nop nop
T1 T1 T1 T1
T2 T2 T2 T2 T2
Ta1 Ta1 Ta1
Ta2 Ta2
Ta3 Ta3 Ta3
serveur
Exemple

T C
P1 6 2 t C
P2 8 3 e1 1 .5
Ds 5 1 e2 7 2
e3 14 1
e1 e2 e3

Épuisement Renouvellement
de DS de DS
Serveur périodique et ordonnancement dynamique EDF

Les ordonnancements dynamiques permettent a priori, une meilleure

utilisation du processeur. L'idée est de servir les tâches aux contraintes plus
lâches au moyen de serveurs périodiques.
Exemple

T C t C
P1 6 2 e1 1.5 .5
P2 8 3 e2 6 2
Ds 4 1
Arrive e2 et EDF plus gd
e1 e2

Épuisement
de DS

E2 est là mais P1 plus urgent

EDFP1=12-9 EDFe2=3

Renouvelement
de DS
 Serveur sporadique
ID Depart C T D
T1 3 20 20
T2 2 10 10
Ta1 4 2
Ta2 10 1
Ta3 11 2
serveur 2 5 5

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
T2 T2 T1 T1 Ta1 Ta1 T1 nop nop nop Ta2 Ta3 T2 T2 nop Ta3 nop nop nop nop
T1 T1 T1 T1
T2 T2 T2 T2 T2
Ta1 Ta1 Ta1
Ta2 Ta2
Ta3 Ta3 Ta3
serveur
Résumé : Rate Monotonic

Algorithme statique d'assignation de priorité

Test : charge totale sous la contrainte n(2 1/n-1)
Analyse exacte par le théorème de la zone critique
RM peut être augmenté pour prendre en compte les situations de blocage et
les événements apériodiques.
Optimal car si un autre algorithme statique arrive à produire un
ordonnancement alors RM y arrive aussi.
Résumé : Earliest Dealine First

Dynamique
Test : charge totale < 100%
Entraîne le moins de changements de contexte
EDF est optimal car on peut transformer tout ordonnancement arbitraire en
ordonnancement EDF.
EDF peut être augmenté pour prendre en compte les situations de blocage
et les événements apériodiques.
Meilleur algorithme quand la loi d'arrivée des tâches est quelconque et
quand on ne connaît par leur capacité.
Exercice 1

On considère un système constitué de deux tâches périodiques

indépendantes s'exécutant sur un processeur. Ces deux tâches sont
définies par :

Pi T C
T1 4 2
P2 10 5

Ces deux tâches sont elles ordonnançables par l'analyse Rate Monotonic ?
Sont elles ordonnaçables par EDF ?
Exercice 2
On considère un système constitué de trois tâches périodiques définies par :

Pi T C D
T1 100 20 100
P2 150 78 150
P3 160 30 145
On applique d'abord l'analyse Rate Monotonic sur les tâches. Grâce au test de
terminaison, calculer l'instant auquel la tâche3 termine sa première exécution.
Respecte-t-elle son échéance ?
On classe maintenant les trois tâches en fonction de leurs échéances (analyse
deadline Monotonic). Utiliser le test suffisant de l'analyse RM pour prouver que les
tâches 1,3 sont ordonnançables ( on considère que la tâche C subit un blocage E3
égal à T3-D3.
Plan :
Introduction
I) De la théorie à la pratique
II) Mise en œuvre du simulateur
1) Modélisation des tâches
2) Gestion des priorités Java
3) Problèmes engendrés par l’OS
4) Démonstration du simulateur.
Conclusion
Le cœur du scheduler :

Comment gérer les priorités des threads pour qu’un

ordonnancement tel que Rate Monotonic soit
respecté ?
Gestion de priorité (1) :

1ère idée :

Attribuer un niveau de priorité à chaque tâche à ordonnancer.

Gestion de priorité (1) :

Problème : !
Si le nombre de tâches est supérieur au nombre de priorités…
Gestion de priorité (2) :

2 ème idée : Utiliser 3 niveaux de priorités.

1 niveau pour le scheduler : priorité maximum

1 autre pour la tâche courante : priorité intermédiaire
1 autre pour les autres tâches : priorité minimum.
Gestion de priorité (3) :
priorité

Max
Java scheduler

virtuel Middle

machine T1 T2 T3 T4 Min
Gestion de priorité (4) :
priorité

Max
Java scheduler

virtuel Middle

machine T1 T2 T3 T4 Min
Gestion de priorité (5) :
priorité

Max
Java scheduler

virtuel Middle
T2

machine T1 T3 T4 Min
Gestion de priorité (7) :
priorité
Sleep Max
Java scheduler
60 ns

virtuel Middle
T2

machine T1 T3 T4 Min
Gestion de priorité (8) :
priorité

Max
Java scheduler

virtuel Middle
T2

machine T1 T3 T4 Min
Gestion de priorité (9) :
priorité

Max
Java scheduler

virtuel Middle
T2

machine T1 T3 T4 Min
Gestion de priorité (10) :
priorité

Max
Java scheduler

virtuel Middle

machine T1 T2 T3 T4 Min
Annexe Inversion de Priorité
0 1 2 4 5 6 7 8 10 12 14 15 16

j1 S

j2
fin
S S S
j3
À t=7, j2 A démarre
t=12, j3 relâche S et et
son exécution
j1 S
profiteÀÀ t=10,j2
t=15,
pour finit son
j1finit
récupérer Sson exécution
exécution
qu'elle etet laisse
avait demandé
j1j1j3j3 démarre
j3 finit
demande
démarre à
demande
j1
j3 demande
demande
ààtps=0
t=10
démarre
S qui à
tps=0
j1 démarre
S quiSestà
esttps=1
tps=2
pris
ààtps=1 par
tps=2
pris j3 donc
par j3 donc il est bloqué
il estàbloquéet
et
redonne
redonne la main
j3 finir j3
elle aussi.
redonnelalamain mainààj3j3
t0 Rés

+ Prioritaire
j1 2 S(2)
j2 7