4 Ordonnancement temps réel
4.1 Caractéristiques de l'ordonnancement temps réel
Dans un système temps réel, le but principal de l'ordonnancement est de permettre le respect des contraintes temporelles associées
à l'application et aux tâches. Chaque tâche possède un délai critique qui est le temps maximal dont elle dispose pour s'exécuter
depuis sa date de réveil. La date butoir résultante est appelée échéance. Le dépassement d'une échéance est appelé faute temporelle.
Beaucoup d'applications temps réel sont des applications embarquées et critiques et il est nécessaire de certifier l'
ordonnancement
réalisé, c'est-à-dire de vérifier avant le lancement de l'application (hors ligne) le respect des contraintes temporelles.
Cette certification s'effectue à l'aide de tests d'acceptabilité qui prennent en compte les paramètres temporels des tâches
et notamment les temps d'exécutions des tâches. Il faut donc pouvoir connaître ces temps d'exécutions et surtout pouvoir les
borner. Pour cela l'exécutif doit être déterministe. Les tests d'acceptabilité sont rarement des conditions nécessaires et
suffisantes. On établit donc soit des conditions nécessaires, soit des conditions suffisantes. Les tests d'acceptabilité utilisent
les temps d'exécution maximum des tâches pour pouvoir certifier les exécutions. Il faut donc être capable de calculer ces
temps d'exécutions maximums. Pour cela, le sup
port
d'exécution, l'exécutif temps réel, doit être déterministe. Un exécutif temps réel déterministe est un exécutif pour lequel
les temps de certaines opérations système et matérielles élémentaires peuvent être bornés : temps de commutation, temps de
prise en compte des interruptions, etc...
4.2 Les algorithmes d'ordonnancement temps réel
4.2.1 Classification des algorithmes d'ordonnancement temps réel
L'ordonnancement peut être en ligne ou hors ligne. Un ordonnancement hors ligne établit avant le lancement de l'application
une séquence fixe d'exécution des tâches à partir de tous les paramètres de celles-ci. Cette séquence est rangée dans une
table et exécutée en ligne par un automate. Avec un ordonnancement en ligne, la séquence d'exécution des tâches est établie
dynamiquement par l'ordonnanceur au cours de la vie de l'application en fonction des événements qui surviennent (réveils des
tâches, blocage, etc...). Dans ce dernier cas, l'
ordonnanceur
choisit le prochaine tâche à élire en fonction d'un critère de priorité.
4.2.2 Modélisation de l'application temps réel pour la certification
On distingue deux types de tâches pour la modélisation de l'application :
- les tâches périodiques : Elles correspondent aux mesures sur le procédé ; elles se réveillent régulièrement (toutes les P
unités de temps)
- les tâches apériodiques : Elles correspondent aux événements ; elles se réveillent de manière aléatoire
Les tâches périodiques
On distingue :
- périodiques strictes : contraintes temporelles dures à respecter absolument
- périodiques relatives : contraintes temporelles molles qui peuvent être non respectées de temps à autre (sans échéance)
- périodiques à échéance sur requête (délai critique = période)
Une tâche périodique Tp (r0, C, R, P) est caractérisée par les paramètres temporels suivants avec 0 ???C ?????R ????P :
- r0, sa date de premier réveil
- rk, la date de réveil de la kème requête, rk = r0 + kP
- C, son temps d'exécution maximum
- R, son délai critique et dk, sa date d'échéance qui est telle que échéance d = rk + R
- C(t) : le temps d'exécution restant à t
- R(t) : le délai critique dynamique c'est-à dire le temps restant à t jusqu'à d.
Une tâche périodique relative n'a pas de paramètre R défini. Une tâche périodique à échéance sur requête est une tâche pour
laquelle R = P.
 |
Fig 11 : Modèle de tâche périodique
|
|
Les tâches apériodiques
On distingue :
- apériodiques strictes : contraintes temporelles dures à respecter absolument
- apériodiques relatives : contraintes temporelles molles qui peuvent être non respectées de temps à autre (sans échéance)
Une tâche apériodique Tap (r0, C, R) est caractérisée par les paramètres temporels suivants avec 0 ???C ????R :
- C, son temps d'exécution maximum
- R, son délai critique et dk, sa date d'échéance qui est telle que échéance d = rk + R
- C(t) : le temps d'exécution restant à t
- R(t) : le délai critique dynamique c'est-à dire le temps restant à t jusqu'à d.
Une tâche apériodique relative n'a pas de paramètre R défini.
 |
Fig 12 : Modèle de tâche apériodique
|
|
4.2.3 Ordonnancement en ligne préemptifs pour des tâches périodiques indépendantes.
Nous ordonnançons un ensemble de tâches périodiques (configuration). Les priorités affectées aux tâches sont soit constantes
(évaluées hors ligne et fixes par la suite), soit dynamiques (elles changent dans la vie de la tâche) L'ordonnancement d'un
ensemble de tâches périodiques est cyclique et la séquence se répète de manière similaire sur ce que l'on appelle la période
d'étude. Pour un ensemble de tâches à départ simultanée (t = 0), la période d'étude est : [0, PPCM(Pi)]
L'ordonnancement Rate Monotonic (RM)
Avec cet algorithme, la priorité d'une tâche est fonction de sa période, de telle sorte que la tâche de plus petite période
est la tâche la plus prioritaire. Pour un ensemble de tâches à échéance sur requête, le test d'acceptabilité d'une configuration
de n tâches est (condition suffisante) donné sur la figure qui suit. La figure ci-dessous donne un exemple pour trois tâches
périodiques à échéance sur requête, Tp1(r0=0, C=3, P=20), Tp2(r0=0, C=2, P=5) et Tp3(r0=0, C=2, P=10). La tâche la plus prioritaire
est la tâche Tp2 et la tâche la moins prioritaire est la tâche Tp1. La séquence est décrite sur la période d'étude, soit l'intervalle
[0, 20]. Les trois tâches respectent leurs contraintes temporelles. La condition suffisante est vérifiée ; on a : 3/20 + 2/5
+ 2/10 = 0.75 < 0.77
 |
Fig 13 : Ordonnancement Rate Monotonic
|
|
Ordonnancement Inverse Deadline (ID)
Avec cet algorithme, la priorité d'une tâche est fonction de son délai critique. La tâche la plus prioritaire est la tâche
de plus petit délai critique. Cet algorithme constitue une généralisation de l'algorithme Rate Monotonic à des tâches quelconques.
Une condition suffisante d'acceptabilité de tâches est donné sur la figure qui suit : La figure ci-dessous donne un exemple
pour trois tâches périodiques Tp1(r0=0, C=3, R=7, P=20), Tp2(r0=0, C=2, R=4, P=5) et Tp3(r0=0, C=2, R=9, P=10). La tâche la
plus prioritaire est la tâche Tp2 et la tâche la moins prioritaire est la tâche Tp3. La condition suffisante n'est pas vérifiée
; en effet on a : 3/7 + 2/4 + 2/9 = 1.14 > 1. Mais le chronogramme construit sur la période d'étude de la configuration prouve
que l'
ordonnancement
des trois tâches s'effectue sans faute temporelle.
 |
Fig 14 : Ordonnancement Inverse Deadline
|
|
Ordonnancement Earliest Deadline (EDF)
La priorité maximale à l'instant t est accordée à la tâche dont l'échéance est la plus proche. La priorité des tâches est
maintenant dynamique. La figure ci-dessous donne un exemple pour trois tâches périodiques Tp1(r0=0, C=3, R=7, P=20), Tp2(r0=1,
C=2, R=4, P=5) et Tp3(r0=0, C=1, R=8, P=10). À l'instant t=0, les trois tâches sont réveillées et la tâche pour laquelle l'échéance
est la plus proche est la tâche Tp2, qui donc s'exécute. À l'instant t=2, la tâche Tp2 a terminé son exécution et c'est maintenant
la tâche Tp1 qui est la plus prioritaire. À l'instant t=5, la tâche Tp1 se termine et la tâche Tp2 se réveille de nouveau.
Mais, c'est maintenant la tâche Tp3 pour laquelle la date d'échéance est à t=8 qui est devenue la plus prioritaire. C'est
donc elle qui s'exécute. On voit donc que contrairement à ce qui se passe avec les algorithmes à priorité fixe où les priorités
des tâches sont calculées une fois pour toutes à l'initialisation du système, ici les priorités des tâches évoluent les unes
par rapport aux autres en fonction de leur urgence. Ainsi, à l'instant t=0, la tâche Tp2 est plus prioritaire que la tâche
Tp3, mais le rap
port
d'urgence est inversé à l'instant t=5.
 |
Fig 15 : Ordonnancement Earliest Deadline
|
|
Ordonnancement
Ordonnancement de processus
Ordonnancement temps réel
|