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
  • P, sa période
  • 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 :
  • r, sa date de réveil
  • 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