Ordonnancement

Une caisse de supermarché, une seule, et quatre clients : trois avec un article, un avec un caddie plein. Les servir dans l'ordre d'arrivée est équitable et peut faire attendre trois personnes vingt minutes pour trois secondes d'achat. Ouvrir une caisse rapide sert d'abord les petits paniers, réduit l'attente moyenne — et laisse le caddie plein attendre indéfiniment si les petits paniers continuent d'arriver.

Tout l'ordonnancement est dans cette scène. Il n'y a pas de bonne réponse, seulement des compromis entre critères qui s'opposent, et le choix dépend de ce que la machine est censée faire. Ce chapitre les pose, les calcule et les compare — c'est le plus arithmétique du cours, et celui qui se travaille le mieux au tableau.

Ce qu'on cherche à optimiser

L'ordonnanceur choisit, parmi les processus prêts au sens du chapitre 3, celui qui obtient le processeur. Six critères servent à juger sa décision, et il est impossible de les satisfaire tous.

Deux oppositions structurent tout le chapitre. Temps de réponse contre débit : donner souvent la main pour que chacun réagisse vite multiplie les changements de contexte, dont le chapitre 3 a rappelé qu'ils sont un pur surcoût. Attente moyenne contre équité : servir d'abord les courts améliore la moyenne et peut faire attendre un long pour toujours.

Le diagramme de Gantt

C'est l'outil de calcul du chapitre, et il faut le tracer même quand on croit pouvoir s'en passer. Prenons quatre processus arrivés ensemble à l'instant 0 :

En les servant dans l'ordre d'arrivée :

1 0        8       12          21        262 ├── P1 ──┼── P2 ─┼──── P3 ───┼─── P4 ──┤3 4Attente :  P1 = 0   P2 = 8   P3 = 12   P4 = 215Attente moyenne = (0 + 8 + 12 + 21) / 4 = 10,256Séjour  : P1 = 8, P2 = 12, P3 = 21, P4 = 26 → moyenne 16,75

Deux règles pour ne pas se tromper. Le temps d'attente d'un processus est son temps de séjour moins son temps d'exécution — autrement dit tout le temps où il aurait voulu le processeur sans l'avoir. Et lorsque les arrivées ne sont pas simultanées, l'attente se compte à partir de l'arrivée, pas de l'instant 0 : c'est l'erreur la plus fréquente en TD.

Les algorithmes classiques

Premier arrivé, premier servi (FIFO). Non préemptif, trivial, équitable au sens strict. Son défaut porte un nom : l'effet convoi. Un processus long placé en tête bloque tous les autres derrière lui, y compris ceux qui n'avaient besoin que d'un instant de processeur avant de repartir sur une entrée/sortie. Réordonnons la file précédente du plus long au plus court — P3, P1, P4, P2 : l'attente moyenne passe de 10,25 à 12, pour exactement le même travail.

Le plus court d'abord (SJF). On sert le processus dont la prochaine rafale de calcul est la plus brève. On démontre qu'il minimise l'attente moyenne — l'argument est simple : échanger deux processus voisins dont le plus long précède le plus court diminue toujours la somme des attentes, donc l'optimum n'a aucune inversion. Sur notre exemple, 7,5 contre 10,25.

Deux objections, et elles sont sérieuses. La famine : un flux continu de tâches courtes peut repousser une tâche longue indéfiniment. Et surtout, on ne connaît pas la durée à l'avance. En pratique on l'estime à partir du passé, par une moyenne exponentielle qui donne plus de poids aux rafales récentes :

Le pari est celui du chapitre 7 d'architecture, transposé : un processus qui vient d'être interactif le restera probablement.

Les priorités. Chaque processus porte un numéro, et le plus prioritaire passe. SJF n'en est qu'un cas particulier, où la priorité est l'inverse de la durée. Même défaut, donc, et la même parade : le vieillissement, qui augmente progressivement la priorité d'un processus en attente. Sans lui, un processus de faible priorité peut attendre des heures — la légende veut qu'un travail soumis en 1967 sur l'IBM 7094 du MIT ait été retrouvé encore en attente lors de l'arrêt de la machine en 1973.

Le tourniquet (round robin). Chaque processus reçoit un quantum de temps ; à l'expiration, l'interruption d'horloge rend la main au noyau, qui le replace en fin de file. C'est l'algorithme du temps partagé, et le seul de la liste qui borne le temps de réponse : avec $n$ processus et un quantum $q$, aucun n'attend plus de $(n-1)q$.

Le choix de $q$ est un compromis exemplaire. Trop grand, le tourniquet dégénère en FIFO — si le quantum dépasse la plus longue rafale, plus personne n'est jamais préempté. Trop petit, le changement de contexte, qui coûte quelques microsecondes, mange une part croissante du temps : avec un quantum de 100 µs et un changement de contexte de 5 µs, 5 % du processeur part en pure administration. Les valeurs usuelles vont de 10 à 100 millisecondes.

Le classement s'inverse dès qu'on change de critère, et c'est le tableau le plus instructif du chapitre :

Le tourniquet perd sur l'attente parce qu'il découpe chaque processus en tranches, ce qui retarde toutes les fins. Il gagne largement sur le temps de réponse, parce que tout le monde a touché le processeur avant l'instant 16, alors qu'en FIFO le dernier servi attend 21. Sur un poste de travail, c'est le second chiffre que l'utilisateur ressent : personne ne chronomètre une compilation en tapant du texte, mais tout le monde remarque une saisie qui répond avec une seconde de retard.

Les files multi-niveaux

Aucun algorithme simple ne convient à une machine réelle, qui exécute simultanément un éditeur interactif, une compilation et un service réseau. La solution employée par tous les systèmes courants est de les combiner.

Les files multi-niveaux répartissent les processus en catégories — système, interactif, par lots — chacune ayant sa propre file, son propre algorithme et sa propre priorité. Un processus n'en change jamais, ce qui est leur limite : la catégorisation est faite une fois pour toutes, alors que le comportement d'un processus varie.

Les files multi-niveaux avec rétroaction lèvent cette limite, et c'est le mécanisme à comprendre. Un processus entre au niveau le plus prioritaire, avec un quantum court. S'il épuise son quantum, on en déduit qu'il est gourmand en calcul, et on le descend d'un niveau, où il recevra un quantum plus long mais moins souvent. S'il se bloque avant la fin de son quantum — parce qu'il attend une saisie ou un disque —, il est interactif, et il reste haut ou remonte.

Le système classe donc les processus par observation, sans que personne ne les déclare. Un éditeur de texte, qui passe son temps bloqué en attente de frappe, occupe naturellement les niveaux hauts et réagit instantanément ; une compilation, qui consomme tout ce qu'on lui donne, descend et s'exécute quand le reste est calme. On y ajoute du vieillissement pour éviter la famine des niveaux bas.

Préemption

Un ordonnanceur non préemptif ne reprend le processeur que si le processus le rend volontairement : en se terminant, ou en se bloquant sur une entrée/sortie. FIFO et SJF de base sont dans ce cas.

Un ordonnanceur préemptif peut le retirer à tout moment, et cette capacité repose entièrement sur un mécanisme matériel : l'interruption d'horloge du chapitre 8 d'architecture. Sans elle, un programme qui ne rend jamais la main est indélogeable.

C'est plus qu'une question de performance. Un système coopératif, comme les Windows et Mac OS d'avant 1995, est à la merci de chaque programme : une seule boucle infinie gèle la machine entière. La préemption est donc d'abord une question de protection, au sens du chapitre 1 — le système ne peut garantir quoi que ce soit s'il ne peut pas reprendre son processeur.

Elle a un coût, cependant, et il ne se limite pas au changement de contexte : préempter un processus au milieu d'une modification de données partagées est exactement ce qui produit les conditions de concurrence du chapitre 5.

À vous

L'exercice implémente les trois algorithmes sur un même jeu de processus, puis calcule attente et temps de séjour moyens. Le squelette fournit le tracé du diagramme de Gantt en texte : c'est lui qui permet de vérifier un calcul faux, exactement comme au tableau.

Trois expériences valent d'être menées. Comparer FIFO selon l'ordre d'arrivée, pour mesurer l'effet convoi. Vérifier que SJF donne bien le minimum, en essayant de le battre par un autre ordre. Et faire varier le quantum du tourniquet de 1 à 20 pour voir l'attente évoluer, puis dégénérer en FIFO.

// Chaque processus : nom, instant d'arrivée, durée de calcul.
const CHARGE = [
  { nom: "P1", arrivee: 0, duree: 8 },
  { nom: "P2", arrivee: 0, duree: 4 },
  { nom: "P3", arrivee: 0, duree: 9 },
  { nom: "P4", arrivee: 0, duree: 5 },
];

// Un ordonnancement est une suite de tranches [nom, debut, fin].
function bilan(nom, charge, tranches) {
  const gantt = tranches
    .map((t) => t.nom + " " + t.debut + "-" + t.fin)
    .join(" | ");

  let attente = 0, sejour = 0, reponse = 0;
  for (const p of charge) {
    const siennes = tranches.filter((t) => t.nom === p.nom);
    const fin = siennes[siennes.length - 1].fin;
    const premiere = siennes[0].debut;
    sejour  += fin - p.arrivee;
    attente += fin - p.arrivee - p.duree;   // séjour moins temps de calcul
    reponse += premiere - p.arrivee;
  }
  const n = charge.length;
  console.log(nom);
  console.log("   " + gantt);
  console.log("   attente " + (attente / n).toFixed(2) +
              " | séjour " + (sejour / n).toFixed(2) +
              " | réponse " + (reponse / n).toFixed(2));
}

// FIFO : dans l'ordre d'arrivée, chacun jusqu'au bout.
function fifo(charge) {
  const file = [...charge].sort((a, b) => a.arrivee - b.arrivee);
  const tranches = [];
  let t = 0;
  for (const p of file) {
    t = Math.max(t, p.arrivee);
    tranches.push({ nom: p.nom, debut: t, fin: t + p.duree });
    t += p.duree;
  }
  return tranches;
}

// SJF non préemptif : parmi les ARRIVÉS, le plus court d'abord.
function sjf(charge) {
  return [];   // ← à écrire
}

// Tourniquet : chacun reçoit au plus « quantum », puis repasse en fin de file.
function tourniquet(charge, quantum) {
  return [];   // ← à écrire
}

// ── À VOUS ────────────────────────────────────────────────────────────────
// 1. Écrivez sjf et tourniquet.
// 2. Vérifiez : FIFO 10,25 — SJF 7,50 — tourniquet q=4 : attente 13,25 mais
//    réponse 6. Expliquez pourquoi le tourniquet perd sur l'un et gagne
//    sur l'autre.
// 3. Faites varier le quantum de 1 à 20 : à partir de quelle valeur le
//    tourniquet redevient-il exactement FIFO ?

bilan("FIFO, ordre d'arrivée", CHARGE, fifo(CHARGE));

const CHARGE = [
  { nom: "P1", arrivee: 0, duree: 8 },
  { nom: "P2", arrivee: 0, duree: 4 },
  { nom: "P3", arrivee: 0, duree: 9 },
  { nom: "P4", arrivee: 0, duree: 5 },
];

function bilan(nom, charge, tranches) {
  const gantt = tranches.map((t) => t.nom + " " + t.debut + "-" + t.fin).join(" | ");
  let attente = 0, sejour = 0, reponse = 0;
  for (const p of charge) {
    const siennes = tranches.filter((t) => t.nom === p.nom);
    const fin = siennes[siennes.length - 1].fin;
    sejour  += fin - p.arrivee;
    attente += fin - p.arrivee - p.duree;
    reponse += siennes[0].debut - p.arrivee;
  }
  const n = charge.length;
  console.log(nom);
  console.log("   " + gantt);
  console.log("   attente " + (attente / n).toFixed(2) +
              " | séjour " + (sejour / n).toFixed(2) +
              " | réponse " + (reponse / n).toFixed(2));
}

function fifo(charge) {
  const file = [...charge].sort((a, b) => a.arrivee - b.arrivee);
  const tranches = [];
  let t = 0;
  for (const p of file) {
    t = Math.max(t, p.arrivee);
    tranches.push({ nom: p.nom, debut: t, fin: t + p.duree });
    t += p.duree;
  }
  return tranches;
}

function sjf(charge) {
  const restants = charge.map((p) => ({ ...p }));
  const tranches = [];
  let t = 0;
  while (restants.length > 0) {
    // On ne choisit que parmi les processus DÉJÀ ARRIVÉS : ignorer cette
    // condition revient à ordonnancer avec une connaissance du futur.
    const arrives = restants.filter((p) => p.arrivee <= t);
    if (arrives.length === 0) { t = Math.min(...restants.map((p) => p.arrivee)); continue; }
    const choisi = arrives.reduce((a, b) => (b.duree < a.duree ? b : a));
    tranches.push({ nom: choisi.nom, debut: t, fin: t + choisi.duree });
    t += choisi.duree;
    restants.splice(restants.indexOf(choisi), 1);
  }
  return tranches;
}

function tourniquet(charge, quantum) {
  const reste = new Map(charge.map((p) => [p.nom, p.duree]));
  const file = [...charge].sort((a, b) => a.arrivee - b.arrivee).map((p) => p.nom);
  const tranches = [];
  let t = 0;
  while (file.length > 0) {
    const nom = file.shift();
    const tranche = Math.min(quantum, reste.get(nom));
    tranches.push({ nom, debut: t, fin: t + tranche });
    t += tranche;
    reste.set(nom, reste.get(nom) - tranche);
    // Non terminé : il repart en FIN de file, derrière ceux qui attendaient.
    if (reste.get(nom) > 0) file.push(nom);
  }
  return tranches;
}

bilan("FIFO, ordre d'arrivée", CHARGE, fifo(CHARGE));

const DECROISSANT = [CHARGE[2], CHARGE[0], CHARGE[3], CHARGE[1]];
bilan("FIFO, du plus long au plus court (effet convoi)", DECROISSANT, fifo(DECROISSANT));

bilan("Le plus court d'abord", CHARGE, sjf(CHARGE));
bilan("Tourniquet, quantum 4", CHARGE, tourniquet(CHARGE, 4));

console.log("");
console.log("— effet du quantum —");
for (const q of [1, 2, 4, 8, 9, 20]) {
  const t = tourniquet(CHARGE, q);
  const commutations = t.length - 1;
  bilan("quantum " + q + " (" + commutations + " commutations)", CHARGE, t);
}
// Dès que le quantum atteint la plus longue rafale (9), plus personne n'est
// jamais préempté : le tourniquet EST FIFO, aux mêmes chiffres près. Et à
// quantum 1, l'attente est la pire de toutes, pour trois fois plus de
// commutations — chacune coûtant, dans une vraie machine, quelques
// microsecondes de pur surcoût.

En travaux pratiques

tâche  arrivée  durée
A       0       24
B       0        3
C       0        3

PAPS (A, B, C)          attente : 0, 24, 27  → moyenne 17,0
PCD  (B, C, A)          attente : 0,  3,  6  → moyenne  3,0

une tâche de 100 devant dix tâches de 1 :
PAPS : attente moyenne 100,0
PCD  : attente moyenne   5,0

la longue bloque tout le monde, comme un camion
sur une route à une voie

quantum | attente moy. | changements de contexte | surcoût
 1    |     4,2      |         120             | 12 %
 4    |     5,1      |          31             |  3 %
20    |     9,8      |           7             |  1 %

changement de contexte ≈ 1 à 5 µs
(sauvegarder les registres, changer la table des pages, vider le TLB)

priorités fixes : une tâche de priorité 10 arrive toutes les 5 ms,
une tâche de priorité 1 n'est JAMAIS élue → famine

vieillissement : priorité += 1 toutes les 100 ms d'attente
→ la tâche de priorité 1 finit par dépasser 10, et passe

# deux boucles à égalité
top → 50 % / 50 %

nice -n 19 ./boucle2
top → 95 % / 5 %      (la courtoisie 19 est le poids le plus faible)

chrt -f 99 ./boucle
→ AUCUN processus normal ne s'exécute plus : votre terminal gèle

Ce que la suite en fait

Le bloc III commence là où celui-ci s'arrête. La préemption vient d'être présentée comme une nécessité ; le chapitre 5 montre son revers. Retirer le processeur à un processus au milieu d'une suite d'instructions qui modifie une donnée partagée laisse cette donnée dans un état incohérent, que le processus suivant lira.

L'exercice de ce chapitre y prépare directement : vous y aurez découpé des exécutions en tranches et fait alterner des processus. Il suffira de leur donner une variable commune pour que le problème apparaisse.

À retenir