Ordonnancement temps réel

Pour un système de tâches, l’ordonnancement consiste à décider dans quel ordre exécuter les tâches. Un ordonnancement temps réel strict a le même objectif mais avec la contrainte supplémentaire qu’aucune instance d’aucune tâche ne rate son échéance. Une des motivations de la théorie de l’ordonnancement, et par extension de l’ordonnancement temps réel, est de concevoir des algorithmes d’ordonnancement qui minimisent les temps de réponse des tâches.

Dans le domaine du temps réel, en plus de décrire un algorithme d’ordonnancement, il est nécessaire de proposer un algorithme qui garantit, pour cet ordonnancement, que les échéances soient respectées.

Ordonnancement hors-ligne / en ligne

L’ordonnancement des tâches temps réel est à la charge de l’ordonnanceur, qui est une des briques logicielles qui composent le système d’exploitation temps réel. L’ordonnanceur peut être vu comme une tâche spécifique chargée de décider dans quel ordre exécuter les autres tâches. On distingue les ordonnancements hors-ligne* des ordonnancements en ligne*.

Pour un ordonnancement hors-ligne, les décisions d’ordonnancement sont connues avant le début de l’ordonnancement. L’ordonnanceur n’a donc pas à calculer ses décisions d’ordonnancement, mais juste à appliquer une politique déjà établie. Au contraire, pour un ordonnancement en ligne, l’ordonnanceur prend ses décisions durant l’ordonnancement en fonction de l’état du système.

Ordonnancement préemptif / non préemptif

Lorsque plusieurs tâches doivent être ordonnancées de manière concurrente, deux approches sont distinguées : les ordonnancement non préemptifs* et ordonnancements préemptifs*. Dans un ordonnancement non préemptif, une tâche qui a été démarrée ne peut pas être interrompue avant d’avoir terminé son exécution.

Avec cette approche, il y a au plus un changement de contexte, c’est-à-dire que l’ordonnanceur remplace le contexte d’exécution d’une instance par celui d’une autre instance. Ces changements de contexte ont un coût qu’il faut prendre en considération durant l’analyse d’ordonnançabilité, bien que l’hypothèse que ce coût soit nul est souvent faite.

Dans un ordonnancement préemptif, l’ordonnanceur peut décider d’interrompre une tâche pour en démarrer une autre. L’avantage de cette approche est de réduire les temps de réponse des tâches les plus prioritaires, de mieux utiliser les processeurs et d’obtenir des taux d’ordonnançabilité plus importants.

Dans le cas d’un ordonnancement conduit par les priorités, ce type d’interruption se produit lorsqu’une instance plus prioritaire que l’instance en cours d’exécution est activée. Avec ce type d’ordonnancement, des tâches se retrouvent en situation de compétition, notamment lorsqu’elles partagent des ressources communes.

Ce problème nécessite de synchroniser les ressources partagées pour garantir leur cohérence. Dans ce manuscrit, nous nous concentrons sur l’étude des algorithmes d’ordonnancement préemptif. Le lecteur intéressé par les résultats sur l’ordonnancement non préemptif pourra se référer entre autres à [GRS96].

Ordonnancement oisif / non oisif Un algorithme d’ordonnancement peut produire un ordonnancement oisif*, c’est-àdire qu’il peut créer un ordonnancement dans lequel un processeur est inactif alors qu’une instance d’une tâche est active.

Cette propriété peut sembler contre-productive, mais elle peut représenter un intérêt dans le cas de la prédictibilité d’un algorithme d’ordonnancement comme nous le verrons dans le chapitre 5. Un ordonnancement non oisif* ne permet pas qu’un processeur soit inactif alors qu’une instance est active. Cette propriété est appelée work-conserving dans la littérature anglophone. 

Ordonnançabilité et faisabilité

Dans un système temps réel strict, la garantie du respect des échéances est obtenue par une analyse d’ordonnançabilité. Le temps de réponse d’une instance d’une tâche est la durée entre l’instant d’activation de cette instance et l’instant de sa terminaison [JP86, AATW93]. Définition 1.10 (Ordonnançabilité d’une tâche). Une tâche est ordonnançable relativement à un algorithme d’ordonnancement si son pire temps de réponse avec cet algorithme est inférieur ou égal à son échéance. Le fait qu’une tâche soit ordonnançable ne garantit en rien l’ordonnançabilité des autres tâches.

Définition 1.11 (Ordonnançabilité d’un ensemble de tâches). Un ensemble de tâches temps réel est ordonnançable relativement à un algorithme d’ordonnancement si toutes les tâches qui le composent sont ordonnançables. Pour décider de l’ordonnançabilité d’un ensemble de tâches relativement à un algorithme d’ordonnancement, il est nécessaire de disposer d’un test d’ordonnançabilité pour cet algorithme d’ordonnancement.

Il n’est pas toujours possible, pour un algorithme donné, de pouvoir procéder à une analyse de temps de réponse pire cas avec une complexité en temps raisonnable. C’est pourquoi pour certaines approches d’ordonnancement, seuls des tests d’ordonnancement suffisants permettent de garantir l’ordonnancement des ensembles de tâches. L’inconvénient de ces tests est qu’ils peuvent décider qu’un ensemble de tâches n’est pas ordonnançable alors qu’il l’est effectivement.