Ordonnancement dans les systèmes d'exploitation - Définition

Introduction

Dans les systèmes d'exploitation, l’ordonnanceur désigne le composant du noyau du système d'exploitation qui choisit les processus qui vont être exécutés par les processeurs d'un ordinateur. En anglais, l'ordonnanceur est appelé scheduler.

Un processus peut avoir besoin de la ressource processeur pour, par exemple, effectuer des calculs, déclencher une interruption, etc. La plupart des composants matériel, et en particulier le processeur d'un ordinateur, n'est pas capable d'effectuer plusieurs traitements simultanément. Pour la très grande majorité des ordinateurs, avoir un seul processeur implique de ne pouvoir effectuer qu'un traitement à la fois.

Or, à un instant donné, il est possible qu'il y ait plus de processus à exécuter qu'il n'y a de processeurs. Il est courant que de nombreux programmes soient exécutés en parallèle sur une machine.

Un des rôles du système d'exploitation, et plus précisément de l'ordonnanceur du noyau, est de permettre à tous ces processus de s'exécuter et d'utiliser le processeur de manière optimale du point de vue de l'utilisateur. Pour arriver à donner l'illusion que plusieurs tâches sont traitées simultanément, l'ordonnanceur du noyau du système s'appuie sur les notions de commutation de contexte et d'ordonnancement.

Commutation de contexte et élection

Pour effectuer ces tâches, l'ordonnanceur procède de la manière suivante : à intervalles réguliers, le système appelle une procédure d'ordonnancement qui élit le processus à exécuter. Si le nouveau processus est différent de l'ancien alors survient un changement de contexte, opération qui consiste à sauvegarder le contexte d'exécution de l'ancienne tâche, comme par exemple, les registres du processeur. Cette structure de données est généralement appelée PCB. Le système d'exploitation restaure le PCB de la nouvelle tâche.

Exemple

Si n tâches doivent être exécutées de manière simultanée et qu'il est physiquement impossible pour l'ordinateur de traiter plus d'une tâche simultanément, le noyau commute rapidement le contexte d'exécution des n tâches, de manière à ce que :

• une seule tâche soit exécutée à la fois ;
• globalement toutes les tâches soient exécutées.

Par exemple, avec 3 tâches cela peut se décomposer par

1. Sauvegarde par le noyau des contextes d'exécutions de 3 tâches,
2. commutation de contexte et élection de la nouvelle tâche n°1
   • Chargement par le noyau du contexte de la tâche 1.
   • Exécution des instructions de la tâche 1 pendant x milli-secondes
   • Sauvegarde du contexte de la tâche 1
3. commutation de contexte et élection de la nouvelle tâche n°2
   • Chargement par le noyau du contexte de la tâche 2.
   • Exécution des instructions de la tâche 2 pendant x milli-secondes
   • Sauvegarde du contexte de la tâche 2
4. commutation de contexte et élection de la nouvelle tâche n°3
   • Chargement par le noyau du contexte de la tâche 3.
   • Exécution des instructions de la tâche 3 pendant x milli-secondes
   • Sauvegarde du contexte de la tâche 3
5. commutation de contexte et élection de la nouvelle tâche n°1
   • Chargement par le noyau du contexte de la tâche 1.
   • Exécution des instructions de la tâche 1 pendant x milli-secondes
   • Sauvegarde du contexte de la tâche 1

…

(3 tâches ordonnancées avec l'algorithme Round-robin (Chacun son tour)).

Algorithmes d'ordonnancement

• Round-robin
• Rate-monotonic scheduling (RMS)
• Earliest deadline first scheduling (EDF)
• FIFO
• Shortest job first (SJF, ou SJN -Shortest Job Next-)
• Completely Fair Scheduler (CFS)