Introduction

Dans tout système multitâches l'un (si ce n'est le) des problèmes centraux est celui de l'ordonnancement, c'est-à-dire la sélection à un instant donné du processus auquel le processeur sera alloué. C'est la composante du système assurant cette fonction, l'ordonnanceur (scheduler) qui permet de garantir une exécution concurrente de plusieurs tâches. Il est bien clair que les objectifs visés ne sont pas les mêmes selon la nature du système considéré et par suite les stratégies mises en oeuvre dans les ordonnanceurs de ces différents types de systèmes sont différents.
Le problème d'ordonnancement est encore plus délicat dans un système temps réel, car non seulement il faut résoudre le problème classique, mais il faut en plus tenir compte de la forte contrainte qu'est le temps réel. Pour cela, on utilise la priorité d'une tâche. Celle-ci est liée à son caractère plus ou moins critique.

Pour résumer, le contexte dans lequel on se place est donc le suivant:

• il existe un pool de processus attendant le processeur (ce qui correspond à l'état prêt);
• le rôle de l'ordonnanceur est d'affecter équitablement le processeur aux processus en optimisant son utilisation relativement à certains critères.

Quelques notions de base

- Les processus ont au cours de leur existence différents états possibles. Citons les trois principaux:

• actif (running): il s'exécute effectivement sur un processeur (qui lui a donc été alloué);
• prêt (ready): il est prêt à s'exécuter mais il n'a pas encore été élu par l'ordonnanceur et attend donc de l'être;
• endormi (waiting): il est attente d'un évéement (différent de l'allocation d'un processeur). Il peut s'agir de la terminaison d'une entrée-sortie ou d'une opération logique (pose d'un verrou, opération P sur un sémaphore, lecture dans un tube vide, ...).

• de manière la plus évidente, quand le processus actif se termine. Dans les premiers systèmes assurant un fonctionnement en train de tâches (batch processing), c'était la seule situation où le changement de tâche active était réalisé;
• assez naturellement lorsque processus actif se bloque (passe à état endormi): cela suppose que d'autres processus sont susceptibles d'être activés et donc sont présents en mémoire. Cela correspond au concept de multiprogrammation;
• lors d'une interruption physique: c'est typiquement une interruption d'horloge dans un système à temps partagé.

• taux d'utilisation du processeur;
• débit: nombre de tâches prises en compte pendant une période donnée;
• temps d'exécution entre le lancement et la terminaison. Ce temps est la somme du temps CPU, du temps passé à l'état prêt et celui passé à l'état endormi (plus le temps de chargement);
• temps d'attente moyen: ce critère concerne le temps moyen passé à l'état prêt;
• temps de réponse: ce critère concerne le temps moyen de prise en compte d'une requête.

- Priorité: valeur numérique associée à une tâche permettant de classer les différents tâches selon leur importance. En général il s'agit de valeurs entières, les petites valeurs correspondant souvent aux grandes priorités.
Ces priorités peuvent être statiques (si elles sont fixées au lancement des tâches et ne sont pas modifiées par le système) ou dynamiques (si elles sont mises à jour périodiquement par le système).
Ainsi, typiquement, dans un système temps réel, les priorités sont fixes et reflètent le caractère critique des tâches. Dans les systèmes orientés sur le partage du temps, les priorités sont dynamiques: schématiquement la priorité d'un processsus y diminuera si le processus est gros consommateur de CPU et augmentera dans le cas contraire (ce qui favorisera les processus interactifs).

- Quantum/tranche de temps (time slicing): le temps est découpé en tranches et, à chaque tranche une interruption permet à l'ordonnanceur du système de reprendre le contrôle;

- Tourniquet (round robin): c'est la technique de base consistant à allouer alternativement le processeur à chacun des processus prêts pour une durée maximale correspondant au quantum de temps (elle sera inférieure pour les tâches s'endormant durant leur période d'activité).

Les algorithmes d'ordonnancement généraux

- Ordonnancement FCFS

L'algorithme FCFS (First-Come-First-Served) (premier arrivé, premier servi) est le plus simple des algorithmes d'ordonnancement.

- Ordonnancement SJF

L'algorithme SJF (Shortest-Job-First) (le plus court en premier)

Les algorithmes d'ordonnancement pour le temps-réel

- Ordonnancement cyclique

- L'ordonnancement HPF

L'algorithme HPF (Highest Priority First) repose sur des priorités statiques associées aux différentes tâches selon la méthode d'analyse monotone par taux (Rate-Monotonic Scheduling). Le principe en est le suivant:

• les tâches sont périodiques et la priorité d'une tâche est inversement proportionnelle à sa période;
• les tâches peuvent être préemptées et les temps de commutation sont négligeables. L'idée sous-jacente à cette approche est qu'une tâche est d'autant plus critique que sa période est courte;
• les tâches peuvent être préemptées et les temps
• les temps d'éxécution des tâches sont connus.

Dans l'exemple ci-dessous (en cliquant sur l'image, une version animée en est donnée), les trois tâches ont des périodes respectives de 10, 15 et 35 unités de temps, soit des priorités respectives 0.1, 0.07 et 0.03. Le temps de traitement nécessaire à chacune de leur période est respectivement de 4, 4 et 12 unités de temps.

Au temps 35, la tâche T₃ a consommé 10 des 12 unités de temps nécessaires au traitement et le temps correspondant à sa période, un nouvel exemplaire en est lancé provoquant probablement l'abandon du traitement de l'occurrence en cours de traitement avant que celui-ci n'ait donné de résultat.

- L'ordonnancement EDF

La stratégie EDF (Earliest-Deadline First) est basée sur des priorités dynamiques : une tâche est d'autant plus prioritaire que son échéance est proche.

- L'ordonnancement LLF

La stratégie LLF (Least-Laxity First) est une variante de EDF.

Exemples

- JAVA

Une thread Java hérite à sa création de la priorité de celle qui la crée (de la même manière qu'un processus hérite de la priorité de son processus père lors d'un fork). Cette priorité peut être modifiée ultérieurement en lui appliquant la méthode setPriority. Les priorités des threads sont comprises entre les valeurs MIN_PRIORITY et MAX_PRIORITY définies dans la classe Thread (1 pour MIN_PRIORITY, 10 pour MAX_PRIORITY et 5 comme priorité standard NORM_PRIORITY).
L'algorithme d'ordonnancement utilisé est un algorithme préemptif avec tourniquet sur les systèmes supportant le temps partagé (par tranchage du temps). De manière plus précise, une thread restera active jusqu'à ce que l'une des conditions suivantes soit réalisée:

• elle se termine (!!!);
• elle relâche spontanément; le processeur en appelant la méthode statique yield (noter que cela ne permettra pas d'élire une thread de priorité inférieure);
• une thread de plus grande priorité est prête;
• si le système sous-jacent supporte le time-slicing; la thread a consommé son quantum (attention, le runtime Java n'implémente pas lui-même cette politique).

- MACH

A chaque activité (thread) est associé en vue de sa prise en compte par l'ordonnanceur d'un couple formé de

• la classe d'ordonnancement,
• la priorité.

Le noyau de Mach est de manière standard configuré avec les politiques suivantes:

• Earliest Deadline First: elle s'applique pour des systèmes temps-réel où des activités sont créées ou supprimées dynamiquement;
• Rate Monotonic: elle s'utilise pour des groupes d'activités dont on connaît par avance l'utilisation CPU;
• priorité fixe: chaque activité a une priorité fixe comprise entre 0 (la plus forte) et 31 (la plus faible);
• temps partagé: chaque activité a une priorité initiale comprise entre 0 (la plus forte) et 31 (la plus faible) à laquelle est ajouté une valeur entière fonction du temps CPU qu'elle a consommé récemment;
• arrière plan (background): les activités de cette classe sont activées uniquement lorsqu'aucune activité d'une autre classe n'est prête.

- CHORUS

Comme c'est le cas dans MACH, dans le système CHORUS une activité possède une classe d'ordonnancement et une priorité dans cette classe. D'un point de vue interne, une activité possède une priorité système comprise entre 0 (la plus grande priorité) et 255 (la plus petite).
Par défaut, une politique FIFO est appliquée:

• les 256 niveaux de priorité sont disponibles;
• une activité ne peut être préemptée que par une activité de priorité strictement supérieure (il n'y a donc pas de tourniquet entre activités de même priorité). Dans ce cas elle est placée en tête de la file des activités en attente avec sa priorité;
• lorsqu'une activité passe de l'état endormi à l'état prêt elle est placée en queue de la file des activités en attente avec sa priorité.

• la classe FIFO telle que définie précédemment;
• la classe RR (Round Robin) dont les caractéristiques sont les suivantes:
  • les 256 niveaux de priorité sont disponibles;
  • comme c'est le cas pour la classe FIFO, une activité peut être préemptée par une activité de priorité strictement supérieure (quelle que soit sa classe de priorité). Elle est alors placée en tête de la file dont elle relè
  • de plus, lorsqu'une activité de cette classe est élue; elle reçoît le processeur pour un quantum de temps. Si à l'expiration de ce délai elle est encore active, elle est interrompue et placée en queue de la file dont elle relève: cela signifie qu'une activité de même priorité (de l'une quelconque des classes) peut être élue;
• la classe RT (Real-Time): il s'agit d'une implantation de la classe d'ordonnancement RT telle que définie dans les versions SVR4 d'UNIX. La stratégie est un tourniquet où une valeur du quantum peut être définie pour chaque activité (les priorités système correspondantes sont comprises entre 95 et 155).

Remarque: on retrouve la même approche avec les deux classes FIFO et RR proposées dans l'interface POSIX pour les activités (les PTHREADS). Une troisième politique (TS) correspondant à l'ordonnancement temps partagé à la Unix y a été ajoutée.

- QNX

On y retrouve la même approche avec les deux classes FIFO et RR. Une troisième classe y a également été ajoutée (l'ordonnancement adaptatif) utilisé pour les aspects temps-partagé. Lorsqu'un processus (QNX a adopté le parti pris de ne pas utiliser le concept de threads) a consommé tout son quantum de temps, sa priorité est décrémentée (dégénérescence de priorité) et lorsqu'il s'endort, il reprend sa priorité initiale.
Cependant dans ce système basé sur un micro-noyau, le modèle client/serveur est largement utilisé pour le développement de nouvelles applications et services. Quelles que soit la politique d'ordonnancement adoptée pour ces applications, les clients s`exécutent généralement à une priorité inférieure à celle des serveurs. Dans ces conditions, si un client de faible priorité requiert un service d'un serveur de haute priorité en lui adressant un message, cette requête sera a priori traité avec la priorité élevée du serveur. Donc d'une certaine manière le client verra sa priorité augmentée. On peut imaginer qu'ainsi la requête non prioritaire s`exécutera au détriment d'applications plus prioritaires que le client (mais moins prioritaire que le serveur). C'est pour cette raison qu'il est possible pour un serveur de spécifier qu'il traitera les demandes avec la priorité de ses clients (client-driven priority). Finalement afin de pouvoir traiter une nouvelle demande plus prioritaire qui arriverait pendant le traitement d'une requête, la priorité de la requête sera adoptée immédiatement par le serveur pour poursuivre le traitement en cours.