3. Ordonnancement : mécanismes, objectifs et méthode
3.1. Prêt, exécuté et bloqué
L’ordonnanceur choisit parmi les unités prêtes : processus, threads noyau, tâches ou jobs selon le modèle du problème. Une tâche bloquée attend un événement et n’est pas candidate au CPU. Les transitions centrales sont prêt→exécution et exécution→prêt lors d’une préemption. Une fin retire la tâche; un blocage la met en attente; un réveil la remet parmi les prêts.
Cette distinction vaut autant après un sémaphore, un mutex, une condition ou une E/S. Un signal ne réalise pas le travail de la tâche réveillée; il permet sa candidature. Les algorithmes simples servent de briques pour des ordonnanceurs réels plus complexes, sans que leurs compositions ou des politiques distribuées soient développées dans la séance.
3.2. Quand décider et pourquoi une commutation coûte
Une création (fork ou création de thread), une fin, un blocage, un réveil, une cession volontaire avec yield, une interruption d’E/S ou une interruption d’horloge peuvent provoquer une décision. Une occasion de décider n’impose pas une commutation : le courant peut rester le meilleur candidat admissible ou être seul prêt.
Changer de processus implique, dans le modèle du support, passage utilisateur/noyau, sauvegarde du contexte sortant, gestion ou changement d’espace d’adressage/MMU, calcul de sélection, restauration du contexte et retour utilisateur. Ce temps ne fait pas progresser directement le travail de l’application. Des coûts petits mais très fréquents peuvent réduire le débit utile.
La préemption retire le CPU sans attendre que la tâche termine, bloque ou cède. Les interruptions d’horloge permettent notamment de reprendre la main face à une boucle infinie en mode utilisateur. Une boucle de calcul infinie n’est pas une tâche bloquée sur E/S. Le cours emploie parfois quantum pour l’intervalle entre ticks et pour la tranche autorisée; ces deux paramètres peuvent être distincts en réalité. Pour un exercice, suivre sa règle exacte.
| Contexte | Orientation et raison | Ordre de grandeur pédagogique |
|---|---|---|
| Lots | Long travail utile, peu de commutations, débit | Environ 200 ms dans l’exemple serveur |
| Interactif | Reprises fréquentes et faible délai de réaction | Environ 5–20 ms pour des exemples PC |
| Temps réel | Réponse prévisible compatible avec contraintes temporelles | Exemple QNX réglable jusqu’à 40 µs |
Ces valeurs viennent des supports; elles ne fixent pas les valeurs par défaut actuelles de tous les systèmes. Une horloge fréquente permet de réagir vite à une tâche prioritaire, mais n’oblige pas à remplacer le courant à chaque tick. Présence de candidats, priorité et politique déterminent ensemble le choix.
Une tâche I/O bound a de courtes rafales CPU entre des E/S. La servir rapidement après un réveil lui permet de lancer plus tôt la prochaine E/S, de rebloquer et de libérer le CPU. La faire attendre longtemps peut aussi laisser le disque inactif. Une tâche CPU bound demande de longues rafales de calcul. Il faut donc regarder l’utilisation de toutes les composantes, pas seulement le temps CPU d’une tâche.
Le temps de réponse concerne la rapidité ressentie par une tâche; le débit concerne le travail réalisé par unité de temps. L’équité donne une progression raisonnable en moyenne, éventuellement pondérée. La famine est l’attente indéfinie d’une tâche pourtant prête, continuellement écartée au profit de nouvelles tâches courtes ou prioritaires. Aucun choix ne maximise tous les objectifs pour toute charge.
3.3. Variables, formules et démarche de simulation
Pour chaque processus i, noter : arrivée A_i, besoin CPU total B_i, première prise du CPU S_i, fin F_i. Dans les exemples sans E/S bloquante ni coût de commutation :
Code (text) · sélectionner pour copier
Traitement T_i = F_i - A_i
Attente totale W_i = T_i - B_i
Première réponse R_i = S_i - A_i
Moyenne = somme des valeurs / nombre de processus
Le « temps de traitement » du cours est le délai arrivée→fin, et non seulement le temps CPU B. Sans préemption ni blocage, W=S−A. Avec préemption, W cumule aussi les attentes après chaque interruption : R n’est alors pas W. Si un problème distingue les périodes bloquées sur E/S, T−B contient ces périodes et ne suffit pas à isoler l’attente dans la file prête.
Finir à 9 n’implique pas avoir reçu neuf unités CPU : une tâche exécutée de 3 à 9 en reçoit six. Quand A=0, F et T sont numériquement égaux; avec une arrivée décalée, il faut la soustraire. Les petites arrivées epsilon du premier FCFS sont arrondies dans le tableau du cours, mais doivent être gardées si l’exercice exige des valeurs exactes.
Pour construire une simulation :
- Relever arrivées, besoins, politique, quantum, coût éventuel, règle des égalités et événements simultanés.
- Ne rendre candidates que les tâches arrivées et prêtes. Si aucune ne l’est, représenter l’intervalle inactif.
- Tracer jusqu’au prochain événement pertinent et soustraire uniquement le CPU réellement exécuté au reste de la tâche.
- Ajouter les nouvelles arrivées et appliquer la politique : poursuivre si non préemptive, comparer les restes en SRT, gérer fin de tranche et file en RR.
- Consigner chaque fin, puis calculer T, W et les moyennes avec les A réels.
- Vérifier que les intervalles d’une tâche totalisent B et qu’aucune ne commence avant A. Sans temps mort ni coût, la durée globale égale la somme des besoins.
La chronologie doit être correcte avant les moyennes. Une formule correcte appliquée à un ordre faux ne répare pas la simulation. Le support ne définit pas toutes les égalités ni l’ordre arrivée/expiration au même instant : employer la convention de l’énoncé, sans inventer une règle universelle.