INFORMATIQUE DES

SYSTEMES TEMPS REELS

Cours 2
2. Ordonnancement des
Processus
[Link]
[Link] d'ordonnanceurs
[Link] de l'ordonnanceur d'un système multi-
utilisateur
[Link] non préemptifs
 Premier arrivé premier servi
 Shortest job first
 Round robin/tourniquet
5. Ordonnanceurs préemptifs
 Ordonnancement du plus petit temps de
séjour
 Ordonnancement circulaire
 Ordonnancement avec priorité
 Files multiples (quantum variable)
 1. Introduction
Tout le logiciel d'un ordinateur peut être vu comme un ensemble
de processus dont l'exécution est gérée par un processus
particulier : l'ordonnanceur (Scheduler en anglais). Un
ordonnanceur fait face à deux problèmes principaux :
 le choix du processus à exécuter, et
 le temps d'allocation du processeur au processus choisi.

Un système d'exploitation multitâche est préemptif lorsque

celui-ci peut arrêter (réquisitionner le processeur) à tout
moment n'importe quelle application pour passer la main à la
suivante.
On peut donc lancer plusieurs applications à la fois et passer de
l'une à l'autre, voire lancer une application pendant qu'une
autre effectue un travail.
Il y a aussi des systèmes d'exploitation dits multitâches, qui
sont en fait des multi-tâches coopératifs
Un multitâche coopératif permet à plusieurs applications de
fonctionner et d'occuper des plages mémoire, laissant le
soin à ces applications de gérer cette occupation, au risque
de bloquer tout le système. Par contre, avec un multi-tâche
préemptif , le noyau garde toujours le contrôle (qui fait
quoi, quand et comment), et se réserve le droit de fermer
les applications qui monopolisent les ressources du
Un problème d'ordonnancement consiste à organiser dans
système.
le temps la réalisation de tâches, compte tenu de
contraintes temporelles (délais, contraintes
d'enchaînement) et de contraintes portant sur la
disponibilité des ressources requises. En production
(manufacturière, de biens, de service), on peut le présenter
comme un problème où il faut réaliser le déclenchement et
le contrôle de l'avancement d'un ensemble de commandes
à travers les différents centres composant le système.

Un ordonnancement est défini par le planning d'exécution

 2. Types
d'ordonnanceurs
Il est possible de distinguer trois types d'ordonnanceurs : à long
terme, à moyen terme et à court terme.

À long terme : L'ordonnanceur fait la sélection de programmes à

admettre dans le système pour leur exécution. Les programmes admis
deviennent des processus à l'état prêt. L'admission dépend de la
capacité du système (degré de multiprogrammation) et du niveau de
performance requis.
À moyen terme : Il fait la sélection de processus déjà admis à
débarquer ou rembarquer sur la mémoire. Il effectue ses tâches de
gestion en fonction du degré de multiprogrammation du système, et
aussi des requêtes d'E/S des périphériques.
À court terme : L'ordonnanceur à court terme a comme tâche la
gestion de la file des processus prêts. Il sélectionne en fonction d'une
certaine politique le prochain processus à exécuter. Il effectue aussi le
changement de contexte des processus. Il peut implementer un
ordonnancement préemptif, non préemptif, ou coopératif.
L'ordonnanceur est activé par un événement : interruption du
temporisateur, interruption d'un périphérique, appel système ou signal.
 3. Objectifs de l'ordonnanceur
d'un système multiutilisateur
Les objectifs d'un ordonnanceur d'un système multi-
utilisateur sont, entre autres :
 S'assurer que chaque processus en attente d'exécution
reçoive sa part de temps processeur.
 Minimiser le temps de réponse.
 Utiliser le processeur à 100 % (Utilisation équilibrée des
ressources).
 Prendre en compte des priorités.
 Être prédictibles.
Ces objectifs sont parfois complémentaires, parfois
contradictoires : augmenter la performance par rapport à
l'un d'entre eux peut se faire en détriment d'un autre. Il
est impossible de créer un algorithme qui optimise tous
les critères de façon simultanée.
 4. Ordonnanceurs non
préemptifs
Dans un système à ordonnancement non préemptif ou
sans réquisition, le système d'exploitation choisit le
prochain processus à exécuter, en général, le Premier
Arrivé est le Premier Servi PAPS (ou First-Come First
Served FCFS) ou le plus court d'abord (Short Job First SJF).

Il lui alloue le processeur jusqu'à ce qu'il se termine ou

qu'il se bloque (en attente d'un événement).
Si l'ordonnanceur fonctionne selon la stratégie SJF, il
choisit, parmi le lot de processus à exécuter, le plus court
(plus petit temps d'exécution). Cette stratégie est bien
adaptée au traitement par lots de processus dont les
temps maximaux d'exécution sont connus ou fixés par les
utilisateurs car elle offre un meilleur temps moyen de
séjour. Le temps de séjour d'un processus (temps de
Considérons par exemple un lot de quatre processus dont les
temps respectifs d'exécution sont a, b, c et d.

Le premier processus se termine au bout du temps a.

Le deuxième processus se termine au bout du temps a+b.
Le troisième processus se termine au bout du temps a+b+c.
Le quatrième processus se termine au bout du temps
a+b+c+d .

Le temps moyen de séjour : <t> =

On obtient un meilleur temps de séjour pour a ≤ b ≤ c ≤ d

Toute fois, l'ordonnancement du plus court d'abord est optimal

que si les travaux sont disponibles simultanément
Exempl
e
 A. Premier arrivé premier
servi
Cet algorithme fonctionne de la manière la plus simple
qui soit. Les tâches sont stockées dans une structure de
type FIFO, la première tâche est exécutée, et lorsqu'elle
termine, la suivante est lancée. Les tâches nouvellement
activées sont stockées à la fin de la file d'attente.
 B. Shortest job first
Afin d'éviter que des tâches courtes ne doivent attendre
trop longtemps sur des tâches longues, il est possible
d'appliquer un algorithme où la tâche la plus courte est
servie en premier. De ce fait, les tâches courtes sont
favorisées, et le temps d'attente moyen est minimisé. Un
des problèmes de cette approche est le risque de famine
des tâches longues. Si de nouvelles tâches courtes son
régulièrement réveillées, il se peut qu'elles passent
toujours devant une tâche longue, empêchant ainsi celle-
ci de s'exécuter.
 C. Round robin/tourniquet

L'algorithme du tourniquet (round robin en anglais) vise à

traiter les tâches avec le plus d'équité possible, en
allouant un quantum de temps identique à toutes les
tâches, et à les traiter dans un ordre FIFO. Les tâches
sont placées dans une file d'attente, et la première de la
file est exécutée pendant un quantum de temps. A la fin
de ce quantum, si la tâche n'est pas terminée, elle est
replacée à la fin de la file et une nouvelle tâche est
sélectionnée depuis le début de la file.
 5. Ordonnanceurs préemptifs
Dans un schéma d'ordonnanceur préemptif, ou avec
réquisition, pour s'assurer qu'aucun processus ne s'exécute
pendant trop de temps, les ordinateurs ont une horloge
électronique qui génère périodiquement une interruption.

A chaque interruption d'horloge, le système d'exploitation

reprend la main et décide si le processus courant doit
poursuivre son exécution ou s'il doit être suspendu pour
laisser place à un autre.
S'il décide de suspendre son exécution au profit d'un autre,
il doit d'abord sauvegarder l'état des registres du
processeur avant de charger dans les registres les données
du processus à lancer.

C'est qu'on appelle la commutation de contexte ou le

changement de contexte.
Cette sauvegarde est nécessaire pour pouvoir poursuivre
ultérieurement l'exécution du processus suspendu. Le
processeur passe donc d'un processus à un autre en
exécutant chaque processus pendant quelques dizaines ou
centaines de millisecondes.

Le temps d'allocation du processeur au processus est appelé

quantum.

Cette commutation entre processus doit être rapide, c'est-à-

dire, exiger un temps nettement inférieur au quantum.

Le processeur, à un instant donné, n'exécute réellement

qu'un seul processus, mais pendant une seconde, le
processeur peut exécuter plusieurs processus et donne ainsi
l'impression de parallélisme (pseudo-parallélisme).
Problèmes
:

Choix de la valeur du quantum.

Choix du prochain processus à exécuter dans chacune
des situations suivantes :
 Le processus en cours se bloque (passe à
l'état Attente).
 Le processus en cours passe à l'état Prêt (fin du
quantum...).
 Un processus passe de l'état Attente à l'état Prêt
(fin d'une E/S).
 Le processus en cours se termine.
A. Ordonnancement du plus petit temps de
séjour

L'ordonnancement du plus petit temps de

séjour ou Shortest Remaining Time est la
version préemptive de l'algorithme SJF. Un
processus arrive dans la file de processus,
l'ordonnanceur compare la valeur espérée
pour ce processus contre la valeur du
processus actuellement en exécution. Si le
temps du nouveau processus est plus petit, il
rentre en exécution immédiatement.
 B. Ordonnancement circulaire
L'algorithme du tourniquet, circulaire ou round robin est un
algorithme ancien, simple, fiable et très utilisé. Il
mémorise dans une file du type FIFO (First In First Out) la
liste des processus prêts, c'est-à-dire en attente
d'exécution.
Choix du processus à exécuter
Il alloue le processeur au processus en tête de file,
pendant un quantum de temps. Si le processus se bloque
ou se termine avant la fin de son quantum, le processeur
est immédiatement alloué à un autre processus (celui en
tête de file). Si le processus ne se termine pas au bout de
son quantum, son exécution est suspendue. Le processeur
est alloué à un autre processus (celui en tête de file). Le
processus suspendu est inséré en queue de file. Les
processus qui arrivent ou qui passent de l'état bloqué à
l'état prêt sont insérés en queue de file.
Choix de la valeur du quantum
Un quantum trop petit provoque trop de commutations
de processus et abaisse l’efficacité du processeur. Un
quantum trop élevé augmente le temps de réponse des
courtes commandes en mode interactif.

Un quantum entre 20 et 50 ms est souvent un compromis

raisonnable.
 C. Ordonnancement avec priorité
L'algorithme round robin permet une répartition équitable du processeur.
Cependant il n'est pas intéressant si certains processus sont plus
importants ou urgents que d'autres. L'ordonnanceur à priorité attribue à
chaque processus une priorité. Le choix du processus à élire dépend des
priorités des processus prêts. Les processus de même priorité sont
regroupés dans une file du type FIFO. Il y a autant de files qu'il y a de
niveaux de priorité. L'ordonnanceur choisit le processus le plus prioritaire
qui se trouve en tête de file. En général, les processus de même priorité
sont ordonnancés selon l'algorithme du tourniquet.
 D. Files multiples (quantum variable)

Pour éviter qu'il y ait beaucoup de commutations pour

les processus consommateurs de temps, il est préférable
d'allouer un plus grand quantum à ces processus.
Lorsqu'un processus passe à l'état élu : Pour la première
fois, le processeur lui est alloué pendant un quantum.
Pour la seconde fois, le processeur lui est alloué pendant
2 quantums. Pour la nieme fois, le processeur lui est alloué
pendant 2n-1 quantum. Chaque processus a une priorité.
Cette dernière dépend du nombre de quantum qui lui
sera alloué lors de sa prochaine activation. Les
processus dont le nombre de quantum est le plus petit
sont les plus prioritaires. Les processus prêts sont
répartis selon leur priorité dans des les (FIFO). D'abord
on fait l'élection du processus le plus prioritaire qui se
trouve en tête de file. Lorsque l'exécution d'un processus
 5. Ordonnancement à deux
niveaux
Lors d'une commutation, si le processus élu n'est pas en
mémoire, il faut le charger en mémoire. Le temps de
commutation est deux à trois fois plus élevé que celui
des processus qui se trouvent en mémoire centrale. Pour
éviter ces va-et-vient entre le disque et la mémoire lors
d'une commutation, l'ordonnanceur à deux niveaux
déplace les processus entre le disque et la mémoire
(haut niveau) et choisit le processus à exécuter parmi
ceux qui sont en mémoire (bas niveau). Périodiquement,
l'ordonnanceur de haut niveau retire de la mémoire les
processus qui y sont restés assez longtemps et les
remplace par des processus qui sont restés sur le disque
pendant trop de temps. Pour élire un processus,
l'ordonnanceur de bas niveau se restreint au processus
en mémoire.