Concepts de base de l'ordonnancement du CPU

Dans un système avec un seul cœur de processeur, un seul processus peut s'exécuter à la fois. D'autres doivent attendre que le cœur du processeur soit libre et puisse être reprogrammé. L'objectif de la multiprogrammation est d'avoir un processus en cours d'exécution à tout moment, afin de maximiser l'utilisation du processeur.

L'idée est relativement simple. Un processus est exécuté jusqu'à ce qu'il doive attendre, généralement l'achèvement d'une requête d'E/S. Dans un système informatique simple, le processeur reste alors inactif. Tout ce temps d'attente est perdu ; aucun travail utile n'est accompli. Avec la multiprogrammation, nous essayons d'utiliser ce temps de manière productive. Plusieurs processus sont conservés en mémoire en même temps. Lorsqu'un processus doit attendre, le système d'exploitation retire le processeur de ce processus et le donne à un autre processus. Ce modèle continue. Chaque fois qu'un processus doit attendre, un autre processus peut prendre en charge l'utilisation du CPU.

Sur un système multicœur, ce concept d'occupation du processeur est étendu à tous les cœurs de traitement du système.

Ce type d'ordonnancement est une fonction fondamentale des systèmes d'exploitation. Presque toutes les ressources informatiques sont programmées avant d'être utilisées. Le CPU est, bien entendu, l'une des principales ressources informatiques. Son ordonnancement est donc essentiel à la conception du système d'exploitation.

Le succès de l'ordonnancement du processeur dépend d'une propriété observée des processus : l'exécution du processus consiste en un cycle d'exécution du processeur et d'attente d'E/S. Les processus alternent entre ces deux états.

L'exécution du processus commence par un CPU burst (rafale d'utilisation du processeur en français). Cela est suivi d'une rafale d'E/S burst (rafale d'utilisation d'E/S en français), qui est suivie d'une autre CPU burst, puis d'une autre E/S burst, et ainsi de suite. Finalement, le CPU burst final se termine par une demande système pour terminer l'exécution.

•  CPU burst - Le moment où le processus est exécuté dans le CPU, c'est-à-dire que le CPU est la ressource utilisée par le processus à ce moment-là.
•  E/S burst- Le moment où le processus demande des E/S et utilise les E/S comme une ressource.

Chaque fois que le processeur devient inactif, le système d'exploitation doit sélectionner l'un des processus dans la file d'attente prête à exécuter. Le processus de sélection est effectué par le planificateur (ordonnanceur) de CPU, qui sélectionne un processus parmi les processus en mémoire prêts à être exécutés et alloue le CPU à ce processus.

Les décisions de planification (ordonnancement) du processeur peuvent avoir lieu dans les quatre circonstances suivantes :

1. Lorsqu'un processus passe de l'état en cours d'exécution à l'état d'attente (par exemple, à la suite d'une demande d'E/S ou d'une invocation de wait() pour l'arrêt d'un processus enfant)
2. Lorsqu'un processus passe de l'état en cours d'exécution à l'état prêt (par exemple, lorsqu'une interruption se produit)
3. Lorsqu'un processus passe de l'état d'attente à l'état prêt (par exemple, à la fin des E/S)
4. Lorsqu'un processus se termine

Pour les situations 1 et 4, il n'y a pas de choix en termes d'ordonnancement. Un nouveau processus (s'il existe dans la file d'attente prête) doit être sélectionné pour être exécuté. En revanche, il existe un choix pour les situations 2 et 3.

Lorsque l'ordonnancement n'a lieu que dans les circonstances 1 et 4, on dit que le schéma d'ordonnancement est non préemptif ou coopératif. Sinon, c'est préemptif. Dans le cadre d'une planification non préemptive, une fois que le CPU a été alloué à un processus, le processus conserve le CPU jusqu'à ce qu'il le libère soit en se terminant, soit en passant à l'état d'attente.

Ordonnancement préemptif

L'ordonnancement préemptif est utilisé lorsqu'un processus passe de l'état en cours d'exécution à l'état prêt ou de l'état d'attente à l'état prêt. Les ressources (principalement les cycles de l'unité centrale) sont allouées au processus pendant une durée limitée, puis retirées. Le processus est à nouveau placé dans la file d'attente des processus prêts s'il lui reste du temps d'utilisation de l'unité centrale. Ce processus reste dans la file d'attente prête jusqu'à ce qu'il ait sa prochaine chance de s'exécuter.

Malheureusement, l'ordonnancement préemptif peut entraîner des situations de concurrence lorsque des données sont partagées entre plusieurs processus. Considérons le cas de deux processus qui partagent des données. Pendant qu'un processus met à jour les données, il est préempté afin que le second processus puisse s'exécuter. Le second processus essaie alors de lire les données, qui sont dans un état incohérent.

Ordonnancement non-préemptif

L'ordonnancement non préemptif est utilisé lorsqu'un processus se termine ou passe de l'état en cours d'exécution à l'état d'attente. Dans cet ordonnancement, une fois que les ressources (cycles de CPU) sont allouées à un processus, celui-ci conserve le CPU jusqu'à ce qu'il soit terminé ou atteigne un état d'attente. Dans le cas de l'ordonnancement non préemptif, il n'interrompt pas un processus en cours d'exécution. Au lieu de cela, il attend jusqu'à ce que le processus termine son temps d'exécution du CPU, puis il peut allouer le CPU à un autre processus.

Un autre composant impliqué dans la fonction de planification du processeur est le répartiteur (dispatcher). Le répartiteur est le module qui donne le contrôle du cœur du CPU au processus sélectionné par le planificateur du CPU. Cette fonction implique les éléments suivants :

•  Changement de contexte d'un processus à un autre
•  Passage en mode utilisateur
•  Sauter à l'emplacement approprié dans le programme utilisateur pour reprendre ce programme

Le répartiteur doit être aussi rapide que possible puisqu'il est invoqué à chaque changement de contexte. Le temps nécessaire au répartiteur pour arrêter un processus et en démarrer un autre est appelé latence de répartition.