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

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

On distingue deux types de tâches pour la modélisation de l'application :

On distingue :  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 : 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

On distingue :  Une tâche apériodique Tap (r0, C, R) est caractérisée par les paramètres temporels suivants avec 0 ???C ????R : Une tâche apériodique relative n'a pas de paramètre R défini.

Fig 12 : Modèle de tâche apériodique

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

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

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

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