Concurrence et synchronisation
Cours complet · informatique (MP2I/MPI), chapitre 22 · MP2I et MPI
Travailler ce chapitre sur Adloun Exercices corrigés de ce chapitre
22.1 Plusieurs fils dans un même programme
Jusqu'ici, un programme faisait une chose à la fois. Les processeurs modernes ont plusieurs cœurs, et un programme peut les employer tous — en lançant plusieurs fils d'exécution qui partagent la même mémoire.
Le programme borne strictement le périmètre : « l'apprentissage des notions liées au parallélisme d'exécution se limite au cas de fils d'exécution (threads) internes à un processus, sur une machine. Les problèmes d'algorithmes répartis et les notions liées aux réseaux et à la communication asynchrone sont hors programme. » Et pour les fils eux-mêmes : « on s'en tient aux notions de base : création, attente de terminaison ».
Un fil est une suite d'instructions exécutée indépendamment, à l'intérieur d'un processus. Tous les fils d'un processus partagent son tas et ses variables globales ; chacun a sa propre pile.
#include <pthread.h>
void* travail(void* arg) { /* ... */ return NULL; }
int main(void) {
pthread_t fil;
pthread_create(&fil, NULL, travail, NULL); /* attributs par défaut */
/* le fil principal continue PENDANT ce temps */
pthread_join(fil, NULL); /* on attend sa terminaison */
return 0;
}
let fil = Thread.create travail () in
Thread.join fil22.2 Le non-déterminisme
C'est la rupture avec tout ce qui précède. L'ordonnanceur du système décide, à chaque instant et sans vous consulter, quel fil progresse. Le même programme, sur la même machine, avec les mêmes données, peut donner deux résultats différents.
Un défaut de concurrence n'est donc pas reproductible : il se manifeste une fois sur mille, en production, jamais pendant les tests. C'est ce qui en fait la catégorie de bogue la plus coûteuse.
int compteur = 0; /* PARTAGÉ par les deux fils */
void* incrementer(void* arg) {
for (int i = 0; i < 100000; i = i + 1) { compteur = compteur + 1; }
return NULL;
}
/* deux fils lancés : on attend 200000. On obtient un nombre INFÉRIEUR,
et différent à chaque exécution. */La raison tient à ce que fait vraiment la machine. compteur = compteur + 1 n'est pas une instruction mais trois :
Les deux fils ont lu , ajouté , écrit . Un incrément a été perdu. C'est une course critique (race condition).
Une opération est atomique si aucun autre fil ne peut l'observer à moitié faite. Une section critique est un morceau de code qui doit s'exécuter atomiquement vis-à-vis des autres fils — typiquement, un accès à une donnée partagée.
Le problème de l'exclusion mutuelle est de garantir qu'au plus un fil est en section critique à la fois.
22.3 Résoudre l'exclusion mutuelle par le logiciel
Le programme demande deux algorithmes : « algorithme de Peterson pour deux fils d'exécution, algorithme de la boulangerie de Lamport pour plusieurs fils d'exécution ». Ils sont présentés « en privilégiant le pseudo-code ».
22.3.1 L'algorithme de Peterson
Méthode : Deux fils, deux drapeaux, un tour de politesse
bool veut[2] = {false, false}; /* veut[i] : le fil i demande à entrer */
int tour = 0; /* à qui la priorité, en cas de conflit */
/* Protocole du fil i (l'autre est j = 1 - i). */
void entrer(int i) {
int j = 1 - i;
veut[i] = true; /* 1. j'annonce mon intention */
tour = j; /* 2. je CÈDE le tour à l'autre */
while (veut[j] && tour == j) { /* attente active */ }
}
void sortir(int i) {
veut[i] = false; /* je libère */
}Deux fils ne peuvent pas être simultanément en section critique.
Démonstration
Supposons les deux entrés. Chacun a donc franchi sa boucle d'attente, ce qui exige ou . Or les deux ont posé avant d'attendre, et aucun n'a encore appelé sortir : les deux drapeaux valent vrai. Chacun a donc franchi grâce à , c'est-à-dire pour les deux : vaudrait à la fois et . Contradiction.
tour = j cède la priorité à l'autre. On attendrait l'inverse. C'est pourtant ce qui garantit l'absence de blocage : si les deux fils demandent en même temps, chacun cède, et le dernier à écrire tour perd — donc l'autre passe. Un seul fil peut être le dernier écrivain : il y a donc toujours exactement un gagnant.
Si chacun s'attribuait le tour, la dernière écriture donnerait la priorité à un fil dont l'autre attendrait le tour indéfiniment.
Deux limites à connaître. D'abord Peterson est écrit pour deux fils : le tableau veut et la variable tour n'ont de sens qu'à deux. Ensuite la boucle while est une attente active : le fil brûle du temps processeur à ne rien faire. C'est acceptable pour une section critique très brève, ruineux sinon — d'où les mutex de la section suivante, qui endorment le fil.
Enfin, une note d'honnêteté : sur les processeurs réels, Peterson exige des barrières mémoire que le C standard n'ajoute pas tout seul. Il est ici un objet d'étude, pas un outil de production.
22.3.2 L'algorithme de la boulangerie
Méthode : fils, comme à la boulangerie : on prend un numéro
bool choisit[N] = {false}; /* le fil i est en train de prendre son numéro */
int numero[N] = {0}; /* son ticket, 0 = pas de ticket */
void entrer(int i) {
choisit[i] = true;
numero[i] = 1 + maximum(numero, N); /* un numéro plus grand que tous */
choisit[i] = false;
for (int j = 0; j < N; j = j + 1) {
if (j == i) { continue; }
while (choisit[j]) { } /* on laisse j finir de choisir */
/* on attend tant que j a un ticket meilleur que le nôtre */
while (numero[j] != 0 &&
(numero[j] < numero[i] ||
(numero[j] == numero[i] && j < i))) { }
}
}
void sortir(int i) { numero[i] = 0; }Le calcul du maximum n'est pas atomique : deux fils peuvent le lire en même temps et prendre le même ticket. La condition numero[j] == numero[i] && j < i tranche alors par l'indice, qui est unique. C'est un ordre lexicographique sur le couple — exactement celui du chapitre chap:induction, et il est total, donc sans ex æquo.
La première boucle while (choisit[j]) est tout aussi nécessaire : sans elle, on pourrait comparer son numéro à un ticket que est en train d'écrire.
La boulangerie garantit davantage que l'exclusion mutuelle : elle est équitable. Un fil qui demande entre après au plus autres, car son numéro est fixé et tous les nouveaux arrivants en prendront un plus grand. Aucun fil ne peut être indéfiniment doublé — ce qu'on appelle la famine.
22.4 Mutex et sémaphores
Un mutex (mutual exclusion) est un verrou fourni par le système : au plus un fil le détient. Un fil qui demande un verrou déjà pris est endormi et réveillé à sa libération — pas d'attente active.
pthread_mutex_t verrou;
pthread_mutex_lock(&verrou);
compteur = compteur + 1; /* section critique */
pthread_mutex_unlock(&verrou);
pthread_mutex_destroy(&verrou);
let m = Mutex.create ()
let () = Mutex.lock m; incr compteur; Mutex.unlock mUn sémaphore porte un compteur entier positif et deux opérations atomiques : sem_wait décrémente, en bloquant si le compteur est nul ; sem_post incrémente et réveille un attendant.
| Mutex | Sémaphore | |
|---|---|---|
| Ce qu'il compte | un verrou, pris ou libre | ressources disponibles |
| Qui libère | celui qui a pris | n'importe quel fil |
| Sert à | protéger une section critique | compter, signaler, synchroniser |
La ligne du milieu est la plus importante : un mutex a un propriétaire, un sémaphore n'en a pas. C'est ce qui permet au sémaphore de signaler d'un fil à un autre.
22.5 Deux schémas classiques
Le programme les nomme : « les concepts sont illustrés sur des schémas de synchronisation classiques : rendez-vous, producteur-consommateur ».
Deux fils doivent atteindre un point avant que l'un ou l'autre ne continue.
sem_t arrive_a, arrive_b;
sem_init(&arrive_a, 0, 0); /* compteur initial : 0 */
sem_init(&arrive_b, 0, 0);
/* fil A */ /* fil B */
travail_a(); travail_b();
sem_post(&arrive_a); sem_post(&arrive_b);
sem_wait(&arrive_b); sem_wait(&arrive_a);
suite_a(); suite_b();L'ordre des deux lignes est vital : chacun signale avant d'attendre. Si l'on inversait — attendre puis signaler — les deux fils attendraient un signal que ni l'un ni l'autre n'a encore envoyé : c'est l'interblocage, et il est immédiat.
Un fil produit, un autre consomme, à travers un tampon de cases. Trois contraintes : ne pas écrire dans un tampon plein, ne pas lire dans un tampon vide, ne pas se marcher dessus.
sem_t vides, pleines;
pthread_mutex_t verrou;
sem_init(&vides, 0, N); /* N cases libres au départ */
sem_init(&pleines, 0, 0); /* 0 élément disponible */
/* producteur */ /* consommateur */
sem_wait(&vides); sem_wait(&pleines);
pthread_mutex_lock(&verrou); pthread_mutex_lock(&verrou);
deposer(x); x = retirer();
pthread_mutex_unlock(&verrou); pthread_mutex_unlock(&verrou);
sem_post(&pleines); sem_post(&vides);Les deux sémaphores comptent les places libres et les éléments présents ; le mutex protège le tampon lui-même. Trois outils, trois rôles distincts — c'est le patron à retenir.
Si le producteur prenait le verrou avant d'attendre une case libre, il s'endormirait en tenant le verrou. Le consommateur ne pourrait alors jamais retirer d'élément pour libérer une case : les deux fils seraient bloqués pour toujours. On n'attend jamais en tenant un verrou.
22.6 Interblocage
Un interblocage (deadlock) survient quand un ensemble de fils s'attendent mutuellement, chacun détenant une ressource que le suivant réclame. Aucun ne progressera jamais.
Cinq philosophes autour d'une table ronde, cinq fourchettes entre eux. Pour manger, il faut les deux fourchettes voisines.
Si chacun prend sa fourchette gauche puis attend la droite, les cinq tiennent une fourchette et attendent celle du voisin : interblocage parfait, et parfaitement symétrique.
Méthode : Trois parades, et pourquoi elles marchent
- Briser la symétrie : un philosophe — un seul — prend sa fourchette droite d'abord. Le cycle d'attente est rompu, donc l'interblocage est impossible.
- Ordonner les ressources : numéroter les fourchettes et toujours prendre la plus petite d'abord. C'est la généralisation de la parade 1, et c'est la règle à retenir : un ordre total sur les verrous interdit tout cycle d'attente.
- Limiter la concurrence : un sémaphore initialisé à n'autorise que quatre philosophes à table. Avec quatre convives et cinq fourchettes, l'un au moins peut toujours manger.
La parade 2 est celle qui se transpose partout : dès qu'un programme prend plusieurs verrous, on les prend toujours dans le même ordre.
L'interblocage : plus personne n'avance. La famine : le système avance, mais un fil précis n'est jamais servi. Une solution peut supprimer l'un et pas l'autre — la parade 3 ci-dessus évite l'interblocage, sans garantir qu'un philosophe malchanceux finisse par manger. Seul un protocole équitable, comme la boulangerie, l'assure.
22.7 Ce qu'il faut retenir
- Les fils partagent le tas et les globales ; chacun a sa pile. Ce qui est partagé doit être protégé.
- Le non-déterminisme rend les défauts non reproductibles : ils survivent aux tests.
x = x + 1n'est pas atomique : c'est lire, ajouter, écrire — et un incrément se perd.- Peterson (deux fils) cède le tour à l'autre ; la boulangerie ( fils) départage par le couple (numéro, indice) et garantit l'équité.
- Un mutex a un propriétaire, un sémaphore compte. Producteur-consommateur emploie les deux, dans cet ordre : sémaphore d'abord, verrou ensuite — on n'attend jamais en tenant un verrou.
- L'interblocage se prévient par un ordre total sur les verrous. Famine et interblocage ne sont pas le même défaut.