RT5-GL4-IMI4
Systèmes Temps-Réel
Chapitre 8 :
Ordonnancement sous Contraintes
Temps Réel (Partie 3)
Olfa Mosbahi
olfamosbahi@[Link]
Plan
▪ Types de Tâches
▪ Caractéristiques des Tâches
▪ Caractérisation d'un ordonnancement
▪ Problème d’ordonnancement
▪ Définitions
▪ Ordonnancement de Tâches périodiques indépendantes
▪ Ordonnancement de Tâches apériodiques
▪ Ordonnancement de Tâches périodiques dépendantes
1
Ordonnancement de tâches périodiques
Tâches à contraintes de ressources
Problème : Inversion de priorité
Si A >B et A est bloqué par une ressource détenue par B.
B s’exécute pendant que A attend.
Exemple 1: Ordonnancement par priorité classique A = {T1, T2, T3}
T1 et T3 en exclusion mutuelle sur une ressource R
priorité(T1) > priorité (T2) > priorité (T3)
activation P(R)
T1
activation
T2
P(R) V(R)
T3
2
Ordonnancement de tâches périodiques
Tâches à contraintes de ressources
Solution : Priority Inheritance Protocol (PIP) protocole à héritage de priorité
Toute tâche en section critique hérite la priorité de la plus haute des tâches en
attente de la ressource.
A = {T1, T2, T3}
T1 et T3 en exclusion mutuelle sur une ressource R
priorité(T1) > priorité (T2) > priorité (T3)
activation P(R)
T1
activation
T2
P(R) V(R)
T3
Minimise le retard de T1 - mais ne résout pas l’interblocage
3
Ordonnancement de tâches périodiques
Tâches à contraintes de ressources
Exemple 2:
A>B>C
R : ressource partagée
Entre A et C
4
Ordonnancement de tâches périodiques
Tâches à contraintes de ressources
Solution :
5
6
Partage de Ressources
PIP : Priority Inheritance Protocol
Calcul du temps de blocage
A>B>C
util(R,A) = 1
util(R,B) = 1
util(R,C) = 0
7
Partage de Ressources
PIP : Priority Inheritance Protocol
8
Partage de Ressources
PIP : Priority Inheritance Protocol
9
Partage de Ressources
PIP : Priority Inheritance Protocol
C>B>A
Bi = c(k) = 5 (temps de blocage)
util(k,A) = 0 BA = util(k,A) * c(k) = 0
util(k,B) = 1 BB = util(k,B) * c(k) = 5
util(k,C) = 1 Bc = util(k,C) * c(k) = 5
RC = Cc + Bc = 5 + 5 = 10 < 20
RB = CB + BB +IB =20 + 10 + 5 = 35 <= 35
RA = CA + IA = 9+60=69 < 75
le système est ordonnançable
10
11
Partage de Ressources
PCP : Priority Ceiling Protocol
12
Partage de Ressources
PCP : Priority Ceiling Protocol
13
Partage de Ressources
PCP : Priority Ceiling Protocol
d>c>b>a
14
Partage de Ressources
PCP : Priority Ceiling Protocol
15
Partage de Ressources
PCP : Priority Ceiling Protocol
C(k) : Temps d’occupation
de la tache i par une ressource k
16
Partage de Ressources
PCP : Priority Ceiling Protocol
17
Partage de Ressources
PCP immédiat
18
Partage de Ressources
PCP immédiat
19
20
21
22
23