Communication et synchronisation

Entre 1985 et 1987, l'appareil de radiothérapie Therac-25 administre à six patients des doses de rayonnement des centaines de fois supérieures à la prescription. Trois en meurent. L'enquête établit que la machine était juste — la plupart du temps. Le défaut n'apparaissait que lorsque l'opérateur modifiait très vite les réglages sur le terminal : une tâche vérifiait la configuration pendant qu'une autre la modifiait, et le faisceau partait sur une valeur incohérente que ni l'une ni l'autre n'avait jamais écrite.

C'est une condition de concurrence, et c'est le sujet de ce chapitre. Elle a trois propriétés qui expliquent qu'elle soit redoutée : elle ne se produit que pour certains entrelacements, donc rarement ; elle disparaît souvent quand on ajoute un affichage pour la déboguer, parce que l'affichage change le minutage ; et elle ne se reproduit pas à la demande. Un programme concurrent qui « marche à l'exécution » ne prouve rien du tout.

Une addition qui n'est pas une opération

Prenons deux fils qui incrémentent une même variable, mille fois chacun. Le résultat attendu est 2000 ; on obtient régulièrement moins.

La raison est que compteur = compteur + 1 n'est pas une instruction machine. Le chapitre 6 d'architecture l'a montré : c'est une lecture, un calcul, une écriture.

1        lw   $t0, compteur       ; lire2        addi $t0, $t0, 1         ; calculer3        sw   $t0, compteur       ; écrire

Et le chapitre 4 a montré que le processeur peut être retiré entre deux instructions quelconques. D'où cet entrelacement, parfaitement légal :

1compteur vaut 52 3Fil A                     Fil B                    compteur4lw   $t0, compteur → 5                                 55                          lw   $t0, compteur → 5       56addi $t0, 1        → 6                                 57                          addi $t0, 1        → 6       58sw   $t0, compteur                                     69                          sw   $t0, compteur           6   ← une incrémentation perdue

Deux incréments, un seul effet. Le bogue n'est pas dans le code — chaque fil est correct — il est dans l'interaction, et il n'apparaît que pour un entrelacement sur des milliers.

La leçon générale : dès que plusieurs exécutions partagent une donnée modifiable, il faut identifier les portions de code qui la manipulent. Ces portions s'appellent des sections critiques, et la règle est qu'une seule exécution à la fois peut se trouver dans une section critique portant sur la même donnée. C'est l'exclusion mutuelle.

Ce qu'une solution doit garantir

Une solution correcte au problème de la section critique satisfait quatre exigences, et il faut les avoir en tête pour juger n'importe quel mécanisme.

L'exclusion mutuelle. Jamais deux exécutions simultanément dans la section critique.

La progression. Si la section est libre et que quelqu'un veut entrer, la décision de savoir qui entre ne peut pas être repoussée indéfiniment. Autrement dit, un processus qui ne demande rien ne doit pas pouvoir bloquer les autres.

L'attente bornée. Il existe une limite au nombre de fois où d'autres peuvent entrer avant qu'un demandeur soit servi. C'est l'exigence anti-famine, et c'est celle que les solutions naïves manquent le plus souvent.

Aucune hypothèse sur les vitesses. La correction ne doit dépendre ni du nombre de processeurs, ni de leur fréquence, ni de l'ordonnanceur. C'est ce qui condamne les solutions « qui marchent parce que le premier fil est toujours plus rapide ».

Une fausse bonne idée mérite d'être écartée tout de suite : masquer les interruptions pendant la section critique. Cela fonctionne, sur une machine à un seul cœur, et c'est ce que fait le noyau lui-même pour des portions très courtes. Mais c'est une instruction privilégiée au sens du chapitre 1 — hors de portée d'un programme utilisateur —, elle gèle tout le système pendant la durée de la section, et surtout elle ne protège rien sur une machine multicœur, où un autre cœur continue d'exécuter le fil concurrent.

Ce qu'il faut, c'est une opération atomique fournie par le matériel : un test-et-mise-à-un (test-and-set) ou une comparaison-et-échange (compare-and-swap) qui lit et écrit en un seul accès indivisible, même vue des autres cœurs. Toutes les primitives qui suivent sont construites là-dessus.

Les sémaphores

Un sémaphore est un entier accompagné d'une file d'attente, sur lequel deux opérations atomiques sont définies. Leurs noms viennent du néerlandais, langue de Dijkstra qui les a inventés en 1965.

1P(s)   « puis-je passer ? »2       s ← s − 13       si s < 0, le processus appelant est BLOQUÉ et mis dans la file de s4 5V(s)   « je libère »6       s ← s + 17       si s ≤ 0, un processus de la file est réveillé et repasse à l'état prêt

Deux détails comptent. La valeur du sémaphore, lorsqu'elle est négative, donne le nombre de processus en attente. Et le blocage est un vrai blocage au sens du chapitre 3 : le processus quitte l'état prêt, donc ne consomme plus de processeur. C'est ce qui distingue le sémaphore de l'attente active (spinlock), qui boucle en relisant une variable — inutilisable pour une attente longue, mais préférable pour une attente de quelques instructions sur une machine multicœur, où le coût de deux changements de contexte dépasserait celui de l'attente.

Deux usages, qu'il ne faut pas confondre.

Un sémaphore binaire, initialisé à 1, réalise l'exclusion mutuelle. On l'appelle alors un mutex, et il a un propriétaire : celui qui verrouille est celui qui déverrouille.

Un sémaphore compteur, initialisé à $n$, gère un stock de $n$ ressources identiques : $n$ places dans un tampon, $n$ connexions à une base. Il n'a pas de propriétaire, et il est parfaitement normal qu'un processus fasse V sur un sémaphore qu'il n'a jamais P.

Le producteur-consommateur

C'est le problème d'école, et c'est aussi le tube du chapitre 2 : un producteur dépose dans un tampon de taille bornée, un consommateur retire. Il faut résoudre trois problèmes distincts, et c'est pourquoi il faut trois sémaphores.

1mutex = 1        exclusion mutuelle sur le tampon2vide  = N        nombre de places libres3plein = 0        nombre d'éléments disponibles4 5Producteur                     Consommateur6répéter                        répéter7    produire un élément            P(plein)     ← attendre qu'il y ait à prendre8    P(vide)   ← attendre           P(mutex)9              une place            retirer du tampon10    P(mutex)                       V(mutex)11    déposer dans le tampon         V(vide)      ← une place s'est libérée12    V(mutex)                       consommer13    V(plein)  ← un de plus

Chaque sémaphore répond à une question différente : mutex protège la structure de données, vide empêche le producteur de déborder un tampon plein, plein empêche le consommateur de lire un tampon vide. Les confondre est l'erreur classique.

L'ordre des P n'est pas interchangeable. Si le producteur faisait P(mutex) avant P(vide), il pourrait prendre le verrou puis se bloquer sur un tampon plein — en gardant le verrou. Le consommateur, qui seul peut libérer une place, resterait bloqué sur P(mutex). Plus personne n'avance : c'est un interblocage, et il tient à l'ordre de deux lignes.

Lecteurs-rédacteurs

Second problème classique, avec une asymétrie utile. Plusieurs lecteurs peuvent consulter une donnée simultanément sans risque — la lecture ne modifie rien. Un rédacteur exige l'exclusivité, contre les autres rédacteurs comme contre les lecteurs.

La solution naïve — un compteur de lecteurs, le premier qui entre prend le verrou d'écriture, le dernier qui sort le rend — a un défaut immédiat : tant qu'il reste au moins un lecteur, le rédacteur n'entre jamais. C'est la famine du rédacteur, et sur une donnée très lue elle est permanente. Les variantes ajoutent une barrière qui bloque les nouveaux lecteurs dès qu'un rédacteur est en attente, ce qui déplace la famine vers les lecteurs — troisième variante équitable, servant les demandes dans l'ordre d'arrivée.

Il n'y a pas de choix universel : c'est une décision de politique, comme au chapitre 4.

L'interblocage

Quatre conditions doivent être simultanément réunies pour qu'un interblocage survienne. Ce sont les conditions de Coffman, et leur intérêt pratique est qu'il suffit d'en casser une.

1. Exclusion mutuelle — au moins une ressource est non partageable.
2. Détention et attente — un processus garde ce qu'il a en attendant autre chose.
3. Non-préemption — on ne peut pas retirer de force une ressource à son détenteur.
4. Attente circulaire — il existe un cycle de processus attendant chacun le suivant.

Trois stratégies, et une quatrième assumée.

La prévention casse une condition par construction. On ne peut guère toucher à la première. On peut exiger qu'un processus demande toutes ses ressources d'un coup, ce qui casse la deuxième au prix d'une mauvaise utilisation. On peut autoriser la préemption des ressources reprenables. Et surtout, le plus employé : imposer un ordre total sur les ressources et exiger qu'on les prenne dans cet ordre croissant, ce qui rend le cycle impossible. C'est une règle de codage simple, vérifiable en relecture, qui suffit dans l'immense majorité des cas.

L'évitement examine chaque demande et ne l'accorde que si le système reste dans un état sûr, c'est-à-dire s'il existe encore un ordre d'exécution qui termine tout le monde. C'est l'algorithme du banquier, qui exige de connaître à l'avance les besoins maximaux de chaque processus — hypothèse rarement réaliste.

La détection et guérison laisse l'interblocage survenir, le détecte en cherchant un cycle dans le graphe d'allocation, puis en sort en tuant un processus ou en annulant une transaction. C'est ce que font les systèmes de gestion de bases de données.

L'autruche, enfin, consiste à ignorer le problème et à redémarrer si nécessaire. C'est le choix des systèmes d'exploitation à usage général, y compris Linux, et il est raisonné : les interblocages y sont rares, et le coût permanent de la prévention dépasserait celui des redémarrages occasionnels.

À vous

L'exercice reproduit le TP en JavaScript, avec un ordonnanceur qui entrelace explicitement deux tâches — puisque le vrai parallélisme n'existe pas dans le navigateur, on le simule, ce qui a l'avantage de rendre l'entrelacement reproductible et donc étudiable.

Trois temps, dans cet ordre. D'abord le compteur partagé sans protection : faites-le perdre des incréments, et repérez dans la trace l'endroit exact où la valeur est écrasée. Ensuite le producteur-consommateur sans synchronisation : il produira des lectures de cases vides et des écrasements. Enfin les trois sémaphores, à placer correctement — et vous êtes invité à essayer l'ordre fautif du quiz pour voir l'interblocage se produire.

// ── Un ordonnanceur à la main ─────────────────────────────────────────────
// Chaque tâche est un générateur : chaque « yield » est un point où le
// processeur peut lui être retiré. C'est exactement la préemption du ch. 4.
function entrelacer(taches, quantum = 1) {
  const files = taches.map((f) => f());
  let restantes = files.length;
  while (restantes > 0) {
    for (const g of files) {
      if (g.fini) continue;
      for (let i = 0; i < quantum; i++) {
        const { done } = g.next();
        if (done) { g.fini = true; restantes--; break; }
      }
    }
  }
}

// ── 1. Le compteur partagé ────────────────────────────────────────────────
let compteur = 0;

function* incrementer(nom, fois) {
  for (let i = 0; i < fois; i++) {
    const lu = compteur;        // lw
    yield;                      // ← le processeur peut être retiré ICI
    const calcule = lu + 1;     // addi
    yield;
    compteur = calcule;         // sw
    yield;
  }
}

compteur = 0;
entrelacer([() => incrementer("A", 50), () => incrementer("B", 50)]);
console.log("sans protection :", compteur, "au lieu de 100");

// ── 2. Le producteur-consommateur ─────────────────────────────────────────
const N = 3;
const tampon = new Array(N).fill(null);
let entree = 0, sortie = 0;
const journal = [];

function* producteur(items) {
  for (const x of items) {
    // ← à protéger : et si le tampon est plein ?
    tampon[entree] = x;
    journal.push("produit " + x + " en " + entree);
    entree = (entree + 1) % N;
    yield;
  }
}

function* consommateur(combien) {
  for (let i = 0; i < combien; i++) {
    // ← à protéger : et si le tampon est vide ?
    const x = tampon[sortie];
    journal.push("consommé " + x + " en " + sortie);
    tampon[sortie] = null;
    sortie = (sortie + 1) % N;
    yield;
  }
}

entrelacer([() => producteur([1, 2, 3, 4, 5, 6]), () => consommateur(6)], 2);
console.log(journal.join("\n"));

// ── À VOUS ────────────────────────────────────────────────────────────────
// 1. Écrivez un sémaphore : P bloque tant que la valeur est nulle, V la
//    relâche. Avec des générateurs, « bloquer » s'écrit : yield tant que la
//    condition n'est pas remplie.
// 2. Protégez le compteur avec un mutex, puis le tampon avec mutex, vide et
//    plein. Vérifiez qu'aucun élément n'est perdu ni lu deux fois.
// 3. Essayez P(mutex) AVANT P(vide) dans le producteur : observez l'arrêt.

function entrelacer(taches, quantum = 1, limite = 100000) {
  const files = taches.map((f) => f());
  let restantes = files.length, pas = 0;
  while (restantes > 0) {
    let progres = false;
    for (const g of files) {
      if (g.fini) continue;
      for (let i = 0; i < quantum; i++) {
        if (pas++ > limite) { console.log("!! plus aucune tâche n'avance : INTERBLOCAGE"); return; }
        const { done } = g.next();
        progres = true;
        if (done) { g.fini = true; restantes--; break; }
      }
    }
    if (!progres) return;
  }
}

// ── Un sémaphore ──────────────────────────────────────────────────────────
// P est un générateur : tant que la valeur est nulle, il rend la main sans
// consommer la ressource. C'est le blocage du chapitre 3, en miniature.
function semaphore(valeur) {
  const s = { v: valeur };
  s.P = function* () { while (s.v <= 0) yield; s.v--; };
  s.V = function () { s.v++; };
  return s;
}

// ── 1. Le compteur, protégé ───────────────────────────────────────────────
let compteur = 0;
const mutexCompteur = semaphore(1);

function* incrementer(fois) {
  for (let i = 0; i < fois; i++) {
    yield* mutexCompteur.P();     // entrée en section critique
    const lu = compteur;
    yield;
    const calcule = lu + 1;
    yield;
    compteur = calcule;
    mutexCompteur.V();            // sortie
    yield;
  }
}

compteur = 0;
entrelacer([() => incrementer(50), () => incrementer(50)]);
console.log("avec mutex :", compteur, "sur 100 attendus");

// ── 2. Producteur-consommateur ────────────────────────────────────────────
const N = 3;
const tampon = new Array(N).fill(null);
let entree = 0, sortie = 0;
const journal = [];

const mutex = semaphore(1);
const vide  = semaphore(N);   // places libres
const plein = semaphore(0);   // éléments disponibles

function* producteur(items) {
  for (const x of items) {
    // L'ORDRE est la clé : le sémaphore de comptage AVANT le mutex. Prendre
    // le mutex d'abord ferait attendre un tampon plein verrou en main, et
    // le consommateur — seul à pouvoir libérer une place — resterait dehors.
    yield* vide.P();
    yield* mutex.P();
    tampon[entree] = x;
    journal.push("produit  " + x + " en case " + entree);
    entree = (entree + 1) % N;
    mutex.V();
    plein.V();
    yield;
  }
}

function* consommateur(combien) {
  const recus = [];
  for (let i = 0; i < combien; i++) {
    yield* plein.P();
    yield* mutex.P();
    const x = tampon[sortie];
    recus.push(x);
    journal.push("consommé " + x + " en case " + sortie);
    tampon[sortie] = null;
    sortie = (sortie + 1) % N;
    mutex.V();
    vide.V();
    yield;
  }
  journal.push("reçus : " + recus.join(" ") + (recus.includes(null) ? "  << une case vide !" : "  (aucune perte)"));
}

entrelacer([() => producteur([1, 2, 3, 4, 5, 6]), () => consommateur(6)], 2);
console.log(journal.join("\n"));

// ── 3. L'ordre fautif ─────────────────────────────────────────────────────
// Décommentez pour voir l'interblocage : le producteur prend le mutex, se
// bloque sur un tampon plein sans le rendre, et le consommateur ne peut
// plus entrer pour libérer une place.
//
// function* producteurFautif(items) {
//   for (const x of items) {
//     yield* mutex.P();      // <- le verrou d'abord…
//     yield* vide.P();       // <- …et l'attente ensuite, verrou en main
//     ...

En travaux pratiques

2 fils × 1 000 000 incréments, attendu : 2 000 000

1 372 449
1 511 087
2 000 000      ← arrive parfois, ce qui rend le bogue si dangereux
1 208 331

le nombre de résultats justes dépend de la machine, de la charge,
et du niveau d'optimisation

compteur++;   se compile en :

  mov  eax, [compteur]     ; LIRE
  add  eax, 1              ; MODIFIER
  mov  [compteur], eax     ; ÉCRIRE

fil A : lit 100
fil B : lit 100          ← avant que A n'écrive
fil A : écrit 101
fil B : écrit 101        ← une incrémentation PERDUE

mutex               : 0,182 s
atomique (fetch_add): 0,031 s
compteurs séparés   : 0,004 s

/* mutex */              /* atomique */          /* séparé */
pthread_mutex_lock(&m);  atomic_fetch_add(       long local = 0;
compteur++;                &compteur, 1);        for(…) local++;
pthread_mutex_unlock(&m);                        atomic_fetch_add(
                                                 &total, local);

while (tampon_vide()) ;        /* attente active : 100 % de processeur
                                à ne rien faire */

sem_wait(&plein);              /* le fil est ENDORMI par le noyau,
                                0 % de processeur */

mesure : 99 % d'un cœur contre 0,3 %

fil 1 : lock(A) … lock(B)
fil 2 : lock(B) … lock(A)        ← ordre inverse : blocage

gdb → thread 1 arrêté dans lock(B), thread 2 dans lock(A)

/* correction : un ORDRE GLOBAL, ici par adresse */
if (&m1 < &m2) { lock(&m1); lock(&m2); }
else           { lock(&m2); lock(&m1); }

void a(void) { lock(&m); b(); unlock(&m); }
void b(void) { lock(&m); … }     /* le MÊME mutex */

→ un seul fil, bloqué en attendant un verrou qu'il détient lui-même

/* les deux sorties */
1. mutex récursif (PTHREAD_MUTEX_RECURSIVE) — le pansement
2. séparer : une fonction publique qui verrouille, une interne
 qui suppose le verrou déjà pris — la vraie correction

Ce que la suite en fait

Le bloc IV change de ressource mais garde la logique. La mémoire du chapitre 6 est une ressource partagée entre processus, allouée et reprise par le système, et les mêmes questions y reviennent : qui obtient quoi, dans quel ordre, et que faire quand il n'y en a plus.

Le lien le plus direct est ailleurs. La table des pages du chapitre 6 est une structure de données du noyau, modifiée par plusieurs cœurs à la fois : elle est elle-même une section critique, protégée par les mécanismes de ce chapitre. Le système d'exploitation est le premier programme concurrent auquel s'appliquent les règles qu'il fournit aux autres.

À retenir