Ordonnancement du processeur (CPU Scheduling)
L'ordonnancement du processeur est une fonction fondamentale des systèmes d'exploitation qui détermine quel processus obtient l'utilisation du CPU à un moment donné. Presque toutes les ressources informatiques sont programmées avant d'être utilisées. Le CPU étant l'une des principales ressources, son ordonnancement est essentiel à la conception du système d'exploitation.
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. L'objectif de la multiprogrammation est d'avoir un processus en cours d'exécution à tout moment, afin de maximiser l'utilisation du processeur.
Sur un système multicœur, ce concept d'occupation du processeur est étendu à tous les cœurs de traitement du système.
Modèle de fonctionnement des processus
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, 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.
- Chaque fois qu'un processus doit attendre, un autre processus peut prendre en charge l'utilisation du CPU.
CPU et E/S bursts
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). Cela est suivi d'un E/S burst (rafale d'utilisation d'E/S), qui est suivie d'un autre CPU burst, puis d'un 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.
Le moment où le processus est exécuté dans le CPU. Le CPU est la ressource utilisée par le processus à ce moment-là.
Exemple : Calculs mathématiques, traitement de données, exécution d'instructions.
Le moment où le processus demande des opérations d'entrée/sortie et utilise les E/S comme ressource.
Exemple : Lecture/écriture sur disque, entrée clavier, communication réseau.
Visualisation du cycle d'un processus
Charge → [CPU burst] → [E/S burst] → [CPU burst] → [E/S burst] → ... → [CPU burst final] → Terminaison
Distribution des durées des CPU bursts
Les durées des CPU bursts varient considérablement selon le type de processus :
| Type de processus | Caractéristique des CPU bursts | Exemple |
|---|---|---|
| Processus interactifs | Bursts courts, nombreuses E/S | Éditeur de texte, shell, interface utilisateur |
| Processus de calcul | Bursts longs, peu d'E/S | Compilation, rendu 3D, simulations scientifiques |
| Processus mixtes | Alternance variable | Base de données, serveur web |
Ordonnanceur de processeur (CPU Scheduler)
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.
Files d'attente d'ordonnancement
- File d'attente des processus prêts : Contient tous les processus prêts à être exécutés, en attente du CPU.
- Files d'attente des périphériques : Contient les processus en attente d'une opération d'E/S spécifique.
Ordonnancement préemptif et non préemptif
Les décisions de planification (ordonnancement) du processeur peuvent avoir lieu dans les quatre circonstances suivantes :
- 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).
- Lorsqu'un processus passe de l'état en cours d'exécution à l'état prêt (par exemple, lorsqu'une interruption se produit).
- Lorsqu'un processus passe de l'état d'attente à l'état prêt (par exemple, à la fin des E/S).
- 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.
Ordonnancement non préemptif (coopératif)
Lorsque l'ordonnancement n'a lieu que dans les circonstances 1 et 4 (passage à l'état d'attente ou terminaison), on dit que le schéma d'ordonnancement est non préemptif ou coopératif.
Caractéristiques :
- Une fois que le CPU a été alloué à un processus, le processus conserve le CPU jusqu'à ce qu'il le libère.
- Libération du CPU soit en se terminant, soit en passant à l'état d'attente.
- Le processus contrôle lui-même la durée d'utilisation du CPU.
- Pas d'interruption en cours d'exécution.
Avantages :
- Pas de problème de concurrence (race conditions) sur les données partagées.
- Plus simple à implémenter.
- Moins de changements de contexte.
Inconvénients :
- Un processus peut monopoliser le CPU.
- Moins adapté aux systèmes interactifs et temps réel.
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 (circonstance 2) ou de l'état d'attente à l'état prêt (circonstance 3).
Caractéristiques :
- Les ressources (cycles CPU) sont allouées au processus pendant une durée limitée.
- Le CPU peut être retiré à un processus avant qu'il ne se termine ou ne passe en attente.
- Le processus est replacé dans la file d'attente des processus prêts s'il lui reste du temps.
L'ordonnancement préemptif peut entraîner des situations de concurrence (race conditions) lorsque des données sont partagées entre plusieurs processus.
Exemple : Deux processus 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.
Avantages :
- Meilleure réactivité pour les processus interactifs.
- Équité entre les processus.
- Nécessaire pour les systèmes temps réel.
Inconvénients :
- Plus complexe à implémenter.
- Nécessite des mécanismes de synchronisation.
- Plus de changements de contexte (overhead).
Tableau comparatif
| Caractéristique | Ordonnancement non préemptif | Ordonnancement préemptif |
|---|---|---|
| Moment de décision | Terminaison ou attente du processus | À tout moment (horloge, priorité) |
| Interruption du processus | Non (le processus cède volontairement le CPU) | Oui (le système peut retirer le CPU) |
| Risque de monopolisation | Élevé | Faible |
| Risque de concurrence | Faible | Élevé |
| Overhead (changements de contexte) | Faible | Plus élevé |
| Systèmes adaptés | Batch, anciens systèmes | Interactifs, temps réel, modernes |
Le répartiteur (Dispatcher)
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.
Fonctions du répartiteur :
- Changement de contexte d'un processus à un autre (sauvegarde de l'état du processus courant, chargement de l'état du nouveau processus).
- Passage en mode utilisateur (après être passé en mode noyau pour l'ordonnancement).
- Saut à l'emplacement approprié dans le programme utilisateur pour reprendre ou démarrer l'exécution.
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 (dispatch latency).
Composantes de la latence de répartition :
| Opération | Description |
|---|---|
| Sauvegarde du contexte | Registres, compteur ordinal, état du processus courant |
| Sélection du nouveau processus | Déjà effectuée par l'ordonnanceur |
| Chargement du contexte | Registres, compteur ordinal, état du nouveau processus |
| Changement de mode | Noyau → utilisateur |
| Invalidation du cache TLB | Nécessaire si changement d'espace d'adressage |
Critères d'ordonnancement
Pour évaluer la qualité d'un algorithme d'ordonnancement, on utilise différents critères :
| Critère | Description | Objectif |
|---|---|---|
| Utilisation du CPU | Pourcentage de temps pendant lequel le CPU est occupé | Maximiser (idéalement 100%) |
| Débit (throughput) | Nombre de processus complétés par unité de temps | Maximiser |
| Temps de rotation (turnaround time) | Temps total entre la soumission et la terminaison d'un processus | Minimiser |
| Temps d'attente (waiting time) | Temps total passé dans la file d'attente prête | Minimiser |
| Temps de réponse (response time) | Temps entre la soumission et la première réponse (pour systèmes interactifs) | Minimiser |
Analyse de traces d'exécution
On observe l'exécution d'un processus qui alterne entre des CPU bursts et des E/S bursts selon la séquence suivante :
CPU burst (5 ms) → E/S burst (10 ms) → CPU burst (3 ms) → E/S burst (8 ms) → CPU burst (4 ms) → Terminaison
Questions :
- Quelle est la durée totale d'exécution du processus (en ms) ?
- Quel est le nombre total de CPU bursts ?
- Quel est le nombre total d'E/S bursts ?
- Dans un système avec un seul processeur, combien de temps le CPU est-il effectivement occupé par ce processus ?
- Si un autre processus est prêt pendant les E/S bursts, que peut faire le système d'exploitation pour améliorer l'utilisation du CPU ?
- Durée totale d'exécution : 5 + 10 + 3 + 8 + 4 = 30 ms
- Nombre de CPU bursts : 3 (5 ms, 3 ms, 4 ms)
- Nombre d'E/S bursts : 2 (10 ms, 8 ms)
- Temps CPU effectif : 5 + 3 + 4 = 12 ms (40% du temps total)
- Amélioration de l'utilisation CPU :
Pendant les E/S bursts (18 ms au total), le CPU est inactif si seul ce processus existe. La multiprogrammation permet d'exécuter un autre processus pendant ces périodes d'attente, maximisant ainsi l'utilisation du CPU. C'est exactement le rôle de l'ordonnancement.
- L'ordonnancement du processeur est essentiel pour maximiser l'utilisation du CPU grâce à la multiprogrammation.
- Les processus alternent entre des CPU bursts (exécution) et des E/S bursts (attente).
- L'ordonnanceur de CPU sélectionne le prochain processus à exécuter parmi la file d'attente prête.
- L'ordonnancement peut être non préemptif (le processus cède volontairement le CPU) ou préemptif (le système peut retirer le CPU à un processus).
- L'ordonnancement préemptif permet une meilleure réactivité mais peut causer des problèmes de concurrence sur les données partagées.
- Le répartiteur (dispatcher) effectue le changement de contexte effectif.
- La latence de répartition est le temps nécessaire pour basculer d'un processus à l'autre.
- Les critères d'évaluation incluent l'utilisation CPU, le débit, les temps de rotation, d'attente et de réponse.
Discussion (0)
Soyez le premier à laisser un commentaire !
Laisser un commentaire
Votre commentaire sera visible après modération.