C2 — ProcessusDans le dialogue d’impression, choisissez « Enregistrer au format PDF » comme destination.
Retour

Licence 1 · Systèmes d'exploitation

Cours 2Processus

Le cœur du cours : ce qu'est un processus, comment il naît et meurt, et sur quels critères le système choisit lequel s'exécute.

2 chapitres · 14 h de travail estimé

  1. 1. Notion de processus6 h
  2. 2. Ordonnancement8 h

Chapitre 1 · 6 h

Notion de processus

Programme contre processus, états et transitions, bloc de contrôle ; création et terminaison par fork, exec et wait ; première approche des threads.

Sur une machine de bureau qui « ne fait rien », ps aux | wc -l répond typiquement autour de trois cents. Trois cents processus, pour un utilisateur qui regarde un fond d'écran. Aucun n'occupe le processeur en permanence : la quasi-totalité attend quelque chose — une frappe, un paquet réseau, une échéance.

Ce chapitre définit cet objet, le plus important du cours. Le chapitre 1 a dit que le système abstrait le matériel ; le processus est l'abstraction du processeur. Et le chapitre 4 en tirera la question suivante : quand plusieurs processus sont prêts, lequel élire ?

Un programme n'est pas un processus

La distinction paraît scolaire jusqu'à ce qu'on la manque, après quoi rien du chapitre ne tient.

Un programme est un fichier sur le disque : une suite d'octets, passive, qui ne fait rien. Un processus est une exécution de ce programme : un objet vivant, doté d'un état, de mémoire, de fichiers ouverts, d'un utilisateur propriétaire.

La relation n'est pas de un à un. Un même programme lancé trois fois donne trois processus indépendants, avec chacun ses variables — trois fenêtres d'éditeur qui ne partagent rien. Inversement, un processus peut au cours de sa vie exécuter successivement plusieurs programmes, et c'est précisément ce que fait exec.

L'analogie qui fonctionne : la recette et le plat. La recette se recopie et se range dans un tiroir ; le plat est en train de cuire, occupe une casserole, et deux personnes qui suivent la même recette produisent deux plats distincts.

Ce qu'un processus possède

Un processus, c'est d'abord une image mémoire, découpée en quatre régions dont la disposition est presque universelle :

  adresses hautes  ┌────────────────────┐  │  pile (stack)      │  variables locales, paramètres, adresses de retour  │        ↓           │  croît vers le bas à chaque appel de fonction  │                    │  │        ↑           │  │  tas (heap)        │  allocation dynamique (malloc), croît vers le haut  ├────────────────────┤  │  données           │  variables globales et statiques  ├────────────────────┤  │  code (text)       │  les instructions, en lecture seule  └────────────────────┘  adresses basses

Le code est en lecture seule, ce qui permet à trois exécutions du même programme d'en partager une seule copie en mémoire — économie considérable, et l'une des raisons d'être de la pagination du chapitre 6. Pile et tas croissent l'un vers l'autre : c'est ce qui permet d'ajuster l'espace entre les deux sans le fixer à l'avance, et un débordement de pile est la collision de ces deux frontières.

Le système, lui, décrit chaque processus par un bloc de contrôle de processus (BCP), une structure du noyau qui contient tout ce qu'il faut pour le suspendre et le reprendre :

Contenu du BCPPourquoi
Identifiant (PID), propriétairel'identifier, décider de ses droits
Étatprêt, élu, bloqué (section suivante)
Compteur ordinal et registresreprendre exactement où il en était
Informations mémoiretables de pages du chapitre 6
Fichiers ouvertsles descripteurs 0, 1, 2 du chapitre 2
Priorité, temps consommél'ordonnancement du chapitre 4

Le changement de contexte est l'opération qui sauvegarde le BCP du processus sortant et restaure celui de l'entrant. C'est un pur surcoût — aucun travail utile n'est fait pendant ce temps — et il coûte de l'ordre de la microseconde, sans compter l'effet indirect le plus cher : le cache du chapitre 7 d'architecture est rempli des données de l'ancien processus, et le nouveau recommence à froid.

Cinq états, et une transition qui compte

                   élection        ┌──────┐  ──────────►  ┌──────┐        │ PRÊT │               │ ÉLU  │ ──── exit ───► terminé        └──────┘  ◄──────────  └──────┘           ▲       préemption      │           │                       │ appel bloquant           │  l'événement          │ (lecture disque, attente…)           │  attendu survient     ▼           │                   ┌────────┐           └───────────────────│ BLOQUÉ │                               └────────┘

Le point à ne jamais confondre : prêt et bloqué ne sont pas la même attente.

Un processus prêt attend seulement le processeur. Il a tout ce qu'il lui faut ; donnez-lui le processeur, il repart immédiatement. C'est parmi ces processus, et seulement parmi eux, que l'ordonnanceur choisira au chapitre 4.

Un processus bloqué attend autre chose : la fin d'une lecture disque, un paquet réseau, une saisie. Lui donner le processeur ne servirait à rien — il ne pourrait rien en faire. Il ne redevient prêt que lorsque l'événement attendu survient, ce qui est signalé par une interruption, exactement au sens du chapitre 8 d'architecture.

Deux transitions distinctes mènent donc hors de l'état élu, et il faut les nommer correctement. L'appel bloquant est volontaire : le processus demande une opération lente et se met de côté de lui-même. La préemption est subie : l'interruption d'horloge rend la main au noyau, qui décide de retirer le processeur à un processus pourtant capable de continuer. Sans préemption, un programme en boucle infinie gèlerait la machine — c'est exactement ce qui se passait sur les systèmes coopératifs des années 1990.

Quiz · 1 question

Un processus effectue une lecture de fichier de 5 ms. Pendant ce temps, l'ordonnanceur doit-il le considérer comme candidat au processeur ?

  • Oui : il est prêt à reprendre dès que la lecture se termine, autant lui laisser le processeurcandidat quand même
  • Non : il est BLOQUÉ, pas prêt. Lui donner le processeur ne servirait à rien puisqu'il ne peut rien faire tant que la donnée n'est pas arrivée ; il ne redeviendra prêt qu'à l'interruption du contrôleur disquebloqué, donc hors course
  • Oui, mais avec une priorité réduite pendant la durée de la lecturepriorité réduite

Réponse : C'est la distinction centrale du chapitre. PRÊT signifie « il ne me manque que le processeur » ; BLOQUÉ signifie « il me manque autre chose, et le processeur n'y changerait rien ». Un processus qui attend un disque n'a aucune instruction à exécuter avant que la donnée soit là : l'élire ferait perdre un changement de contexte pour rien. L'ordonnanceur ne choisit donc QUE parmi les prêts. Le passage de bloqué à prêt est déclenché par l'interruption que lève le contrôleur en fin de transfert — c'est le mécanisme du chapitre 8 d'architecture, et c'est ce qui rend l'attente d'entrée/sortie « gratuite » pour le reste du système : pendant ces 5 ms, d'autres processus travaillent.

Créer un processus : fork, exec, wait

Unix crée les processus d'une façon qui déroute au premier abord et qui se révèle très économique en concepts.

fork duplique le processus appelant. L'enfant reçoit une copie de l'image mémoire du parent, de ses variables, de ses descripteurs de fichier ouverts, de son environnement. Les deux processus reprennent à la même instruction, celle qui suit le fork.

D'où la particularité qui surprend tout le monde : fork rend deux fois, une fois dans chaque processus, et sa valeur de retour est le seul moyen de savoir où l'on est.

pid = fork();if (pid < 0)        // échec : pas de nouveau processus    perror("fork");else if (pid == 0)  // ici, JE SUIS L'ENFANT    ...else                // ici, JE SUIS LE PARENT ; pid est le PID de l'enfant    ...

Le choix est délibéré : l'enfant n'a pas besoin qu'on lui dise son PID, il peut le demander par getpid. C'est le parent qui a besoin de connaître celui de l'enfant, pour l'attendre ou le tuer plus tard.

exec remplace l'image mémoire du processus courant par celle d'un autre programme. Le PID ne change pas, les descripteurs ouverts restent ouverts — mais le code, les données et la pile sont écrasés, et on ne revient jamais d'un exec réussi.

La combinaison des deux donne le schéma que le shell du chapitre 2 exécute à chaque commande : fork pour se dupliquer, puis exec dans l'enfant pour devenir le programme demandé, pendant que le parent attend. Séparer les deux opérations peut sembler tortueux ; c'est en réalité ce qui rend les redirections possibles. Entre le fork et le exec, l'enfant est encore le shell : il peut refermer son descripteur 1 et le rouvrir sur un fichier, puis lancer le programme, qui écrira dans le fichier sans jamais savoir qu'il ne s'adresse pas à l'écran.

wait suspend le parent jusqu'à la terminaison d'un enfant et récupère son code de retour — celui que exit a fourni, et que le shell teste dans un if. Deux situations anormales portent des noms qu'il faut connaître :

Un processus zombie est terminé mais dont le parent n'a pas encore appelé wait. Son BCP subsiste, uniquement pour conserver le code de retour. C'est normal et bref ; cela devient une fuite si le parent n'attend jamais ses enfants.

Un processus orphelin a perdu son parent avant sa propre fin. Il est adopté par le processus d'initialisation, de PID 1, qui appelle wait en permanence — ce qui garantit qu'un orphelin ne deviendra pas un zombie éternel. Tous les processus forment ainsi un arbre enraciné en PID 1.

Les fils d'exécution

Un processus a un seul fil d'exécution : un compteur ordinal, une pile. Un fil (thread) en ajoute d'autres à l'intérieur du même processus.

Ce qui est partagé entre les fils d'un processus : le code, les données globales, le tas, les fichiers ouverts. Ce qui reste propre à chacun : la pile, les registres, le compteur ordinal.

Deux conséquences, exactement opposées. La bonne : la communication est immédiate, puisqu'une variable globale est visible de tous, et la création d'un fil coûte bien moins qu'un fork, qui doit dupliquer une image mémoire. La mauvaise : cette même mémoire partagée est le terrain des conditions de concurrence du chapitre 5. Deux processus séparés ne peuvent pas se corrompre mutuellement ; deux fils, si, et ils le font.

Il en découle une règle de choix : des tâches indépendantes s'écrivent en processus, des tâches qui doivent échanger beaucoup de données s'écrivent en fils — et acceptent alors la synchronisation qui va avec.

Quiz · 1 question

Pourquoi Unix sépare-t-il fork et exec en deux appels système, plutôt que de fournir une seule primitive « lancer un programme » ?

  • Pour des raisons historiques : la fusion des deux serait aujourd'hui préférablehéritage historique
  • Parce que l'intervalle entre les deux appartient encore à l'enfant tel qu'il était : c'est là que le shell redirige les descripteurs, change de répertoire ou abaisse ses droits, avant que le nouveau programme prenne la placel'intervalle est utile
  • Parce que fork est réservé aux processus et exec aux fils d'exécutiondeux objets différents

Réponse : La séparation est le point de génie du modèle. Après fork, l'enfant est encore une copie du shell : il exécute du code du shell, avec les structures du shell. Il peut donc préparer l'environnement du futur programme — refermer le descripteur 1 et le rouvrir sur un fichier pour une redirection, brancher un tube, changer de répertoire courant, abandonner des privilèges. Puis exec écrase le code sans toucher aux descripteurs, et le programme lancé écrit dans le fichier sans avoir la moindre idée qu'il ne s'adresse pas à l'écran. Une primitive unique « lancer un programme » devrait recevoir en paramètres toutes les personnalisations imaginables ; c'est le choix de Windows avec CreateProcess et sa dizaine d'arguments.

À vous

L'exercice simule fork, exec et wait : chaque processus est un objet avec son PID, son parent, son état et son code de retour, et l'appel à fork doit produire deux exécutions à partir d'un seul appel.

Trois choses à obtenir. L'arbre des processus, affiché en indentant les enfants. Le zombie : un enfant terminé dont le parent n'a pas appelé wait reste dans la table. Et l'adoption : un enfant dont le parent meurt d'abord doit être rattaché au PID 1.

Exercice de code

Complétez fork, exit et wait : arbre des processus, zombie et adoption par le PID 1.

Point de départ

// Table des processus du noyau. Chaque entrée est un BCP simplifié.
let PROCHAIN_PID = 1;
const TABLE = [];

function creer(parent, nom) {
  const p = { pid: PROCHAIN_PID++, parent, nom, etat: "prêt", code: null, attend: false };
  TABLE.push(p);
  return p;
}

const init = creer(null, "init");        // PID 1, la racine de l'arbre
const trouver = (pid) => TABLE.find((p) => p.pid === pid);

// fork : duplique le processus courant. Rend le PID de l'enfant au parent,
// et 0 à l'enfant — ici on rend les deux, à l'appelant de simuler.
function fork(courant, nomEnfant) {
  const enfant = creer(courant.pid, nomEnfant ?? courant.nom);
  return { auParent: enfant.pid, aLEnfant: 0, enfant };
}

// exec : remplace le programme. Le PID ne change PAS.
function exec(processus, programme) {
  processus.nom = programme;
  return processus;
}

// exit : le processus se termine. Son BCP survit tant que le parent n'a pas
// récupéré son code de retour.
function sortir(processus, code) {
  processus.etat = "zombie";
  processus.code = code;
  // ← à écrire : les enfants de ce processus deviennent orphelins
}

// wait : le parent récupère un enfant zombie et libère son BCP.
function attendre(parent) {
  const zombie = TABLE.find((p) => p.parent === parent.pid && p.etat === "zombie");
  if (!zombie) return null;
  TABLE.splice(TABLE.indexOf(zombie), 1);   // le BCP disparaît enfin
  return { pid: zombie.pid, code: zombie.code };
}

function arbre(pid = 1, profondeur = 0) {
  const p = trouver(pid);
  if (!p) return;
  console.log("  ".repeat(profondeur) + "PID " + p.pid + "  " + p.nom +
              "  [" + p.etat + (p.code !== null ? ", code " + p.code : "") + "]");
  for (const e of TABLE.filter((x) => x.parent === pid)) arbre(e.pid, profondeur + 1);
}

// ── À VOUS ────────────────────────────────────────────────────────────────
// 1. Dans sortir(), rattachez les enfants du mourant au PID 1 (adoption).
// 2. Écrivez le scénario du shell : fork, exec dans l'enfant, wait dans le
//    parent — et vérifiez qu'aucun zombie ne subsiste à la fin.

const shell = creer(1, "bash");
const f = fork(shell, "bash");
exec(f.enfant, "grep");
sortir(f.enfant, 0);
console.log("— avant wait —"); arbre();
console.log("wait rend :", attendre(shell));
console.log("— après wait —"); arbre();

Solution

let PROCHAIN_PID = 1;
const TABLE = [];

function creer(parent, nom) {
  const p = { pid: PROCHAIN_PID++, parent, nom, etat: "prêt", code: null, attend: false };
  TABLE.push(p);
  return p;
}

const init = creer(null, "init");
const trouver = (pid) => TABLE.find((p) => p.pid === pid);

function fork(courant, nomEnfant) {
  const enfant = creer(courant.pid, nomEnfant ?? courant.nom);
  return { auParent: enfant.pid, aLEnfant: 0, enfant };
}

function exec(processus, programme) {
  processus.nom = programme;
  return processus;
}

function sortir(processus, code) {
  processus.etat = "zombie";
  processus.code = code;
  // Adoption : un enfant ne doit jamais rester sans parent, sinon personne
  // n'appellerait jamais wait pour lui et son BCP fuirait définitivement.
  // Le processus 1 attend en permanence, c'est son unique travail.
  for (const enfant of TABLE.filter((p) => p.parent === processus.pid)) {
    enfant.parent = 1;
  }
}

function attendre(parent) {
  const zombie = TABLE.find((p) => p.parent === parent.pid && p.etat === "zombie");
  if (!zombie) return null;
  TABLE.splice(TABLE.indexOf(zombie), 1);
  return { pid: zombie.pid, code: zombie.code };
}

function arbre(pid = 1, profondeur = 0) {
  const p = trouver(pid);
  if (!p) return;
  console.log("  ".repeat(profondeur) + "PID " + p.pid + "  " + p.nom +
              "  [" + p.etat + (p.code !== null ? ", code " + p.code : "") + "]");
  for (const e of TABLE.filter((x) => x.parent === pid)) arbre(e.pid, profondeur + 1);
}

console.log("— 1. le shell lance une commande : fork, exec, wait —");
const shell = creer(1, "bash");
const a = fork(shell, "bash");
exec(a.enfant, "grep");
sortir(a.enfant, 0);
arbre();
console.log("wait rend :", attendre(shell), "  (le BCP est libéré)");

console.log("");
console.log("— 2. un parent qui n'attend pas : le zombie reste —");
const b = fork(shell, "ls");
sortir(b.enfant, 2);
arbre();

console.log("");
console.log("— 3. adoption : le parent meurt avant son enfant —");
const c = fork(shell, "bash");
const petitFils = fork(c.enfant, "sleep");
sortir(c.enfant, 0);          // le parent intermédiaire disparaît…
arbre();                       // …et son enfant est passé sous le PID 1
console.log("le processus " + petitFils.enfant.pid +
            " a désormais pour parent le PID " + petitFils.enfant.parent);

En travaux pratiques

Travaux pratiques 3 · 3 h

Premier noyau du mini-shell

Créer des processus, les remplacer, les attendre — et écrire les cinquante lignes qui font l'essentiel d'un interpréteur de commandes.

Avant de commencer

  • Les TP 1 et 2
  • gcc, et la page de manuel de fork au chapitre 2

Énoncé

  1. Le premier forkÉcrivez un programme qui appelle fork une fois et affiche, dans les deux branches, son identifiant et celui de son père. Exécutez-le dix fois et notez si l'ordre des lignes varie.
  2. Compter les processusÉcrivez un programme avec trois appels à fork successifs, sans aucun test. Prédisez le nombre de lignes affichées AVANT d'exécuter, puis vérifiez. Indice : Chaque appel double la population.
  3. Remplacer le programmeFaites exécuter la commande ls par le fils, avec execvp. Vérifiez que la ligne écrite après l'appel n'est jamais atteinte, et expliquez pourquoi.
  4. AttendreFaites attendre le père avec wait, récupérez le code de sortie du fils, et affichez-le. Testez avec un fils qui réussit, un qui échoue, un qui est tué par un signal.
  5. Fabriquer un zombieÉcrivez un programme dont le père n'attend pas et dort trente secondes. Observez le fils dans ps pendant ce temps, et notez son état.
  6. Fabriquer un orphelinInversez : le fils survit au père. Affichez l'identifiant de son père avant et après la mort de celui-ci.
  7. Le mini-shellAssemblez : une boucle qui lit une ligne, la découpe en mots, crée un processus, exécute la commande et attend. Faites-le fonctionner avec ls, echo et une commande inexistante.
  8. L'arrière-planAjoutez la reconnaissance d'une esperluette finale : la commande s'exécute sans que le shell attende. Vérifiez ensuite ce qui arrive à vos processus terminés.

C'est réussi quand

  • Trois fork affichent huit lignes, et vous saviez le prédire
  • Votre shell exécute ls, signale proprement une commande inconnue, et ne quitte pas
  • Vous savez expliquer ce qu'est un zombie sans employer le mot « planté »

Correction

Un appel, deux retourspremier-fork.c
pid_t p = fork();

if (p < 0)       perror("fork");
else if (p == 0) printf("fils   : pid=%d ppid=%d\n", getpid(), getppid());
else             printf("père   : pid=%d fils=%d\n", getpid(), p);

fork est le seul appel qui revient DEUX fois : une fois dans chaque processus. La valeur de retour est la seule différence entre les deux — 0 chez le fils, l'identifiant du fils chez le père. Tout le reste est identique : mêmes variables, mêmes valeurs, même point d'exécution. Et l'ordre d'affichage varie d'une exécution à l'autre, parce que c'est l'ordonnanceur qui décide.

Trois fork, huit processus
fork(); fork(); fork();
printf("bonjour\n");     → 8 lignes

1 → 2 → 4 → 8   (chaque appel double)

n appels sans test → 2 puissance n processus

L'erreur classique est de compter 3 ou 4 : on oublie que le fils exécute LUI AUSSI les fork suivants. C'est le même raisonnement qu'une bombe à fork, et c'est aussi pourquoi tout système sérieux limite par utilisateur le nombre de processus.

exec ne revient pasexec.c
if (fork() == 0) {
  execvp("ls", (char*[]){"ls", "-l", NULL});
  perror("execvp");   /* atteint SEULEMENT si exec a échoué */
  _exit(127);
}

exec ne crée pas un processus : il REMPLACE le programme du processus courant, en gardant l'identifiant, les descripteurs de fichiers ouverts et le père. Il n'y a donc pas de retour à attendre — la seule raison d'atteindre la ligne suivante est un échec. C'est la séparation fork/exec, propre à Unix, qui permet au shell de préparer les redirections ENTRE les deux.

Lire le statut de sortie
int statut;
wait(&statut);

if (WIFEXITED(statut))        printf("code %d\n", WEXITSTATUS(statut));
else if (WIFSIGNALED(statut)) printf("tué par le signal %d\n", WTERMSIG(statut));

Le statut n'est pas le code de sortie : c'est un entier codé, dont il faut extraire les champs avec les macros. Un programme tué par un signal n'a AUCUN code de sortie — d'où la nécessité de tester d'abord comment il s'est terminé. C'est ce que le shell affiche dans sa variable de statut, et ce sur quoi repose le set -e du TP 2.

Zombie et orphelin
ZOMBIE  : le fils est mort, le père n'a pas fait wait
ps → « defunct » ou état Z
il ne consomme ni mémoire ni processeur, mais garde une
ENTRÉE dans la table des processus, ressource finie

ORPHELIN : le père est mort avant le fils
ppid du fils passe à 1 (ou au subreaper)
init fait wait à sa place → jamais de zombie durable

Un zombie n'est pas un processus qui plante : c'est un cadavre que personne n'a réclamé. Le système garde son code de sortie tant que le père ne l'a pas lu. Un serveur qui crée des fils sans jamais faire wait épuise la table des processus en quelques heures — panne réelle et fréquente, dont le symptôme est un fork qui échoue ailleurs sur la machine.

Le mini-shellshell.c
while (1) {
  printf("$ "); fflush(stdout);
  if (!fgets(ligne, sizeof ligne, stdin)) break;   /* Ctrl-D */

  int fond = 0;
  char *args[64]; int n = 0;
  for (char *m = strtok(ligne, " \t\n"); m; m = strtok(NULL, " \t\n"))
      args[n++] = m;
  args[n] = NULL;
  if (n == 0) continue;
  if (strcmp(args[n-1], "&") == 0) { fond = 1; args[--n] = NULL; }

  pid_t p = fork();
  if (p == 0) {
      execvp(args[0], args);
      fprintf(stderr, "%s : commande introuvable\n", args[0]);
      _exit(127);
  }
  if (!fond) waitpid(p, NULL, 0);
  while (waitpid(-1, NULL, WNOHANG) > 0) ;   /* récolte les zombies */
}

Cinquante lignes, et c'est bien la structure d'un vrai shell : lire, découper, créer, remplacer, attendre. La dernière ligne est celle qu'on oublie — sans elle, chaque commande lancée en arrière-plan laisse un zombie. Le TP 5 ajoutera les tuyaux et les redirections, qui se placent dans le fils entre fork et exec.

Ce que la suite en fait

Le chapitre 4 prend la suite immédiate. Nous avons maintenant des processus, dont certains sont prêts ; il faut choisir. Les états définis ici sont exactement les entrées de l'ordonnanceur, et le changement de contexte est le coût qu'il faut amortir — c'est lui qui interdit un quantum de temps trop court.

Le bloc III part de la remarque sur les fils : dès que deux exécutions partagent de la mémoire, elles peuvent se corrompre. Le chapitre 5 montrera comment, et comment l'empêcher.

À retenir

Flashcards · 5 cartes

Qu'est-ce qui distingue un programme d'un processus ?
Le programme est un fichier passif sur le disque ; le processus est une EXÉCUTION de ce programme, un objet vivant avec son état, sa mémoire, ses fichiers ouverts, son propriétaire. La relation n'est pas de un à un : un même programme lancé trois fois donne trois processus indépendants, et un processus peut exécuter successivement plusieurs programmes — c'est ce que fait exec.
Quelle est la différence entre l'état PRÊT et l'état BLOQUÉ ?
Un processus PRÊT n'attend que le processeur : donnez-le-lui, il repart. Un processus BLOQUÉ attend autre chose (fin d'une lecture disque, paquet réseau, saisie) et le processeur ne lui servirait à rien. L'ordonnanceur ne choisit QUE parmi les prêts. Le passage de bloqué à prêt est déclenché par l'interruption du périphérique concerné.
Que fait fork, et pourquoi dit-on qu'il « rend deux fois » ?
Il duplique le processus appelant : l'enfant reçoit une copie de l'image mémoire, des variables, des descripteurs et de l'environnement, et les deux reprennent à la même instruction. La valeur de retour est le SEUL moyen de savoir où l'on est : 0 dans l'enfant, le PID de l'enfant dans le parent, négatif en cas d'échec. L'enfant n'a pas besoin qu'on lui donne son PID (getpid suffit) ; c'est le parent qui a besoin de celui de l'enfant.
Pourquoi fork et exec sont-ils deux appels séparés ?
Parce que l'intervalle entre les deux est utile. Après fork, l'enfant est encore une copie du shell : il peut refermer le descripteur 1 et le rouvrir sur un fichier, brancher un tube, changer de répertoire, abandonner des privilèges. Puis exec écrase le code sans toucher aux descripteurs, et le programme lancé écrit dans le fichier sans le savoir. C'est ce qui rend les redirections du chapitre 2 possibles.
Qu'est-ce qu'un zombie, qu'est-ce qu'un orphelin ?
Un ZOMBIE est un processus terminé dont le parent n'a pas encore appelé wait : son bloc de contrôle subsiste uniquement pour conserver le code de retour. Normal et bref ; c'est une fuite si le parent n'attend jamais. Un ORPHELIN a perdu son parent avant sa propre fin : il est adopté par le processus 1, qui appelle wait en permanence, ce qui garantit qu'il ne restera pas zombie.

Chapitre 2 · 8 h

Ordonnancement

Temps de réponse, temps d'attente et équité ; FIFO, SJF, priorités, tourniquet et files multi-niveaux ; préemption et calculs de moyennes sur diagrammes de Gantt.

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.

CritèreDéfinitionQui s'en soucie
Temps de séjourde l'arrivée à la finle travail par lots
Temps d'attentetemps passé dans la file des prêtstout le monde
Temps de réponsede l'arrivée à la première exécutionl'interactif
Débitprocessus terminés par unité de tempsle serveur
Utilisationpart du temps où le processeur travaillele serveur
Équitépas de processus indéfiniment ignoréle système partagé

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 :

ProcessusDurée
P18
P24
P39
P45

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

 0        8       12          21        26 ├── P1 ──┼── P2 ─┼──── P3 ───┼─── P4 ──┤ Attente :  P1 = 0   P2 = 8   P3 = 12   P4 = 21Attente moyenne = (0 + 8 + 12 + 21) / 4 = 10,25Sé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 :

τn+1=αtn+(1α)τn\tau_{n+1} = \alpha\, t_n + (1-\alpha)\, \tau_n

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 nn processus et un quantum qq, aucun n'attend plus de (n1)q(n-1)q.

Le choix de qq 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.

Graphique

Temps d'attente moyen sur la même charge (P1=8, P2=4, P3=9, P4=5)

  • Tourniquet, quantum 4 : 13,2513.25
  • FIFO, ordre P3 P1 P4 P2 : 1212
  • FIFO, ordre P1 P2 P3 P4 : 10,2510.25
  • Le plus court d'abord : 7,57.5
Même charge, mêmes durées, même processeur : seul l'ordre de service change, et l'attente moyenne varie de 7,5 à 13,25. SJF donne bien le minimum — mais il l'obtient en faisant attendre le plus long, qui n'a aucune garantie de passer un jour. Et le tourniquet est le PIRE des quatre sur ce critère, ce qui ne le disqualifie pas : voir le tableau ci-dessous.

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

AlgorithmeAttente moyenneTemps de réponse moyen
FIFO (P1 P2 P3 P4)10,2510,25
Le plus court d'abord7,57,5
Tourniquet, quantum 413,256

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.

Quiz · 1 question

Un administrateur observe qu'un serveur passe 20 % de son temps en changements de contexte. Le quantum du tourniquet est réglé à 20 µs et un changement de contexte coûte 5 µs. Quel réglage corrige la situation, et quel effet secondaire faut-il accepter ?

  • Réduire encore le quantum, pour que chaque processus soit servi plus souventréduire encore
  • Augmenter le quantum : à 20 µs de travail utile pour 5 µs d'administration, un quart du temps est perdu ; en passant à 200 µs on descend à 2,4 %, au prix d'un temps de réponse plus longaugmenter le quantum
  • Supprimer la préemption : sans quantum, il n'y a plus de changement de contextesupprimer la préemption

Réponse : Le surcoût est le rapport du coût de commutation à la somme quantum + commutation : 5/25 = 20 %. Réduire le quantum aggraverait la situation — à 5 µs de quantum, la moitié du processeur partirait en administration. L'augmenter à 200 µs ramène le surcoût à 5/205, soit 2,4 %. L'effet secondaire est mécanique : avec n processus prêts, le temps de réponse maximal vaut (n−1) × quantum, donc il est multiplié par dix. C'est le compromis central du tourniquet, et il n'a pas de solution — seulement un réglage, différent sur un serveur de calcul et sur un poste de bureau. Supprimer la préemption ramènerait au comportement des systèmes coopératifs, où un programme en boucle gèle la machine.

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.

Quiz · 1 question

Dans une file multi-niveaux avec rétroaction, un processus qui se bloque avant la fin de son quantum est maintenu ou remonté en priorité haute. Quelle est la logique ?

  • Il est récompensé pour sa modération, ce qui incite les programmeurs à écrire du code économerécompense
  • Se bloquer tôt signale un processus interactif ou orienté entrées/sorties : il consomme peu de processeur mais doit réagir vite, et le maintenir haut coûte peu tout en améliorant le temps de réponsesignal de comportement
  • Un processus bloqué ne consomme rien, sa priorité n'a donc aucune importancesans importance

Réponse : Le système ne dispose d'aucune déclaration d'intention : il déduit la nature d'un processus de son COMPORTEMENT observé. Épuiser son quantum trahit un calcul long, qui gagne à recevoir de gros quanta rarement — moins de changements de contexte. Se bloquer avant la fin trahit un processus qui attend le monde extérieur : il ne prendra de toute façon que quelques microsecondes de processeur, donc le placer en tête ne coûte presque rien et fait toute la différence sur le temps de réponse perçu. C'est ce mécanisme qui explique qu'un éditeur reste fluide pendant une compilation, sans que personne ait rien configuré.

À 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.

Exercice de code

Implémentez SJF et le tourniquet, puis comparez attente, séjour et temps de réponse.

Point de départ

// 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));

Solution

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

Travaux pratiques 4 · 3 h

Qui passe en premier

Simuler les politiques d'ordonnancement pour en voir les effets, puis les retrouver sur la vraie machine avec les outils qui règlent les priorités.

Avant de commencer

  • Le TP 3 : création de processus
  • Les commandes nice, chrt, top

Énoncé

  1. Simuler à la mainCinq tâches, avec dates d'arrivée et durées données. Calculez à la main les temps d'attente et de rotation moyens pour premier arrivé premier servi, puis pour le plus court d'abord.
  2. L'effet convoiConstruisez un jeu de tâches où une longue arrive en premier. Comparez les deux politiques et mesurez l'écart d'attente moyenne.
  3. Le tourniquetSimulez le tourniquet avec un quantum de 1, puis 4, puis 20. Tracez l'attente moyenne et le nombre de changements de contexte en fonction du quantum. Indice : Ces deux courbes vont dans des sens opposés : c'est tout le problème.
  4. La famineAvec un ordonnancement par priorités fixes, construisez une situation où une tâche n'est jamais élue. Ajoutez ensuite le vieillissement et vérifiez qu'elle finit par passer.
  5. Sur la vraie machineLancez deux boucles de calcul infinies et observez leur partage du processeur. Changez la courtoisie de l'une avec nice et mesurez le nouveau partage.
  6. Interactif contre calculLancez une boucle de calcul, puis tapez dans un éditeur. La frappe reste-t-elle fluide ? Expliquez ce que fait l'ordonnanceur, et pourquoi il a raison.
  7. Le temps réelLancez un processus avec chrt en politique FIFO temps réel et observez ce qui arrive aux autres. Faites-le dans une machine virtuelle, et dites pourquoi cet avertissement est là.

C'est réussi quand

  • Vos deux moyennes concordent avec la simulation à la main
  • Vous montrez qu'un quantum trop petit dégrade le débit
  • nice -n 19 sur une boucle change visiblement le partage dans top
  • Vous savez expliquer pourquoi le plus court d'abord est optimal ET inapplicable

Correction

Les deux politiques, chiffrées
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

Facteur presque six, sur exactement le même travail. Le plus court d'abord est PROUVÉ optimal pour l'attente moyenne — et inapplicable, parce qu'il demande de connaître la durée à l'avance. Les ordonnanceurs réels l'ESTIMENT à partir du passé, en supposant qu'un processus qui a été court le restera.

L'effet convoi
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

C'est la raison pour laquelle un système interactif n'utilise jamais PAPS. Et l'effet ne se limite pas au processeur : la même forme apparaît sur un disque, sur un verrou de base de données, ou dans une file d'attente de pipeline. Reconnaître un convoi est plus utile que retenir le nom des politiques.

Le quantum, et son compromis
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)

Petit quantum : bonne réactivité, mauvais débit. Grand quantum : l'inverse, et à la limite on retombe sur PAPS. Linux ne fixe d'ailleurs plus de quantum constant — son ordonnanceur calcule une part de temps proportionnelle au poids de chaque tâche. Le compromis n'a pas disparu, il est devenu dynamique.

Famine et vieillissement
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

Le vieillissement garantit qu'aucune tâche n'attend indéfiniment, au prix d'une entorse à la priorité déclarée. C'est un choix explicite : on préfère l'ÉQUITÉ à la stricte hiérarchie. Un système temps réel dur fait le choix inverse, et assume la famine — parce qu'y rater une échéance est pire que d'affamer une tâche.

Sur la machine réelle
# 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

nice ne réserve pas un pourcentage : il pondère. Une tâche courtoise obtient tout le processeur si personne d'autre n'en veut. La politique FIFO temps réel, elle, ne PRÉEMPTE JAMAIS au profit d'une tâche normale : une boucle infinie en priorité 99 monopolise un cœur jusqu'à l'extinction. D'où l'avertissement, et d'où le fait que cette politique demande les privilèges administrateur.

Pourquoi la frappe reste fluide

Un éditeur passe son temps bloqué en attente d'entrée-sortie, pas à calculer. Quand une touche arrive, il est réveillé et l'ordonnanceur le fait passer AVANT la boucle de calcul, parce que son temps d'exécution consommé est très inférieur à sa part équitable. C'est ce qui distingue les tâches gourmandes en calcul de celles gourmandes en entrées-sorties, et c'est la raison pour laquelle un système peut être à la fois pleinement chargé et parfaitement réactif — la charge n'est pas la latence.

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

Flashcards · 5 cartes

Comment calcule-t-on le temps d'attente d'un processus, et quelle erreur guette ?
Temps d'attente = temps de séjour − temps d'exécution, c'est-à-dire tout le temps passé dans la file des prêts sans avoir le processeur. L'erreur classique en TD : quand les arrivées ne sont pas simultanées, l'attente se compte à partir de l'ARRIVÉE du processus, pas de l'instant 0.
Qu'est-ce que l'effet convoi, et quel algorithme minimise l'attente moyenne ?
L'effet convoi : en FIFO, un processus long placé en tête bloque tous les autres derrière lui, y compris ceux qui ne voulaient qu'un instant de processeur. SJF (le plus court d'abord) minimise l'attente moyenne — échanger deux voisins dont le long précède le court diminue toujours la somme des attentes. Mais il provoque la FAMINE des longs et suppose de connaître les durées, qu'on doit estimer par moyenne exponentielle sur les rafales passées.
Comment choisit-on le quantum d'un tourniquet ?
C'est un compromis. Trop grand, le tourniquet dégénère en FIFO : si le quantum dépasse la plus longue rafale, personne n'est jamais préempté. Trop petit, le changement de contexte (quelques microsecondes) mange une part croissante du temps — le surcoût vaut commutation / (quantum + commutation). Valeurs usuelles : 10 à 100 ms. Garantie apportée : avec n processus prêts, l'attente ne dépasse pas (n−1) × quantum.
Comment fonctionne une file multi-niveaux avec rétroaction ?
Un processus entre au niveau le plus prioritaire avec un quantum court. S'il ÉPUISE son quantum, il est jugé gourmand en calcul et DESCEND d'un niveau (quantum plus long, moins souvent). S'il se BLOQUE avant la fin, il est jugé interactif et reste haut ou remonte. Le système classe donc par observation, sans déclaration — c'est ce qui garde un éditeur fluide pendant une compilation. On y ajoute du vieillissement contre la famine.
Sur quoi repose la préemption, et pourquoi est-ce d'abord une question de protection ?
Sur l'interruption d'horloge, mécanisme matériel : sans elle, un processus qui ne rend jamais la main est indélogeable. Un système coopératif est à la merci de chaque programme — une boucle infinie gèle la machine, comme sur les systèmes d'avant 1995. Le système ne peut rien garantir s'il ne peut pas reprendre son processeur. Contrepartie : préempter au milieu d'une modification de données partagées produit les conditions de concurrence du chapitre 5.