Synchronisation : section critique, Peterson, sémaphores et moniteurs
Conditions de course, exigences de la section critique, exclusion mutuelle de Peterson démontrée, test-and-set et CAS, sémaphores, producteur et consommateur, moniteurs.
https://www.electronics-engineering.com/fr/synchronisation-section-critique-peterson-semaphores/
Quand plusieurs threads ou processus accèdent aux mêmes données, le résultat peut dépendre de l’ordre imprévisible dans lequel leurs instructions s’entremêlent. Ce sont les bogues les plus difficiles à trouver : ils apparaissent une fois sur un million d’exécutions et disparaissent quand on ajoute un affichage de débogage. Dans cette leçon, nous regardons les conditions de course, les exigences d’une section critique, l’algorithme de Peterson avec la démonstration de l’exclusion mutuelle, les instructions atomiques, les sémaphores avec le problème du producteur et du consommateur, et les moniteurs.
La condition de course
L’instruction C counter++ paraît indivisible, mais le processeur l’exécute en trois pas : il lit la valeur en mémoire dans un registre, l’incrémente, la réécrit. Si deux threads l’exécutent ensemble à partir de 5 :
| Thread A | Thread B | counter |
|---|---|---|
| lit 5 | 5 | |
| lit 5 | 5 | |
| écrit 6 | 6 | |
| écrit 6 | 6 |
Deux incréments, mais le compteur vaut 6 : l’un s’est perdu. C’est une condition de course (race condition). Deux threads qui font chacun un million d’incréments sur un multicœur finissent presque toujours avec moins de deux millions, et avec une valeur différente à chaque exécution.
La section critique
Le code qui accède aux données partagées est une section critique. Une solution correcte doit garantir :
- l’exclusion mutuelle : au plus un thread à la fois dans la section critique ;
- le progrès : si personne n’est dans la section critique et que quelqu’un veut entrer, la décision ne peut pas être reportée indéfiniment ;
- l’attente bornée : un thread qui demande à entrer y parvient après un nombre borné d’entrées des autres.
L’algorithme de Peterson
Pour deux threads, 0 et 1, deux variables partagées suffisent : flag[i] est vrai quand le thread i veut entrer, turn indique qui doit céder le passage.
/* code of thread i; j = 1 - i is the other */
flag[i] = true; /* I want to enter */
turn = j; /* but I give way to the other */
while (flag[j] && turn == j)
; /* wait */
/* critical section */
flag[i] = false; /* leave */Théorème. L’algorithme de Peterson garantit l’exclusion mutuelle.
Démonstration. Supposons, par l’absurde, que les deux threads soient dans la section critique. Alors flag[0] et flag[1] sont tous deux vrais, parce que chacun l’a mis à vrai avant d’entrer et ne le remet à faux qu’en sortant. Considérons le dernier thread qui a écrit turn, par exemple le thread 1, qui a écrit turn = 0. À partir de ce moment, turn vaut 0 et flag[0] est vrai, donc la condition de la boucle du thread 1, flag[0] && turn == 0, est vraie : le thread 1 n’a pas pu passer la boucle après son écriture. Mais la boucle vient après l’écriture dans son code : contradiction. Il en va de même en échangeant les rôles. ∎
Le progrès et l’attente bornée se démontrent aussi. Sur les processeurs modernes, cependant, l’algorithme ne fonctionne qu’avec des barrières mémoire, parce que le processeur et le compilateur peuvent réordonner les lectures et les écritures à des adresses différentes (leçon sur les systèmes multicœurs) : c’est une idée d’enseignement, non un outil pratique.
Les instructions atomiques
Les processeurs offrent des instructions qui lisent et modifient un mot de mémoire de façon indivisible :
- test-and-set : écrit vrai et renvoie la valeur précédente ;
- compare-and-swap (CAS) : n’écrit une nouvelle valeur que si la valeur courante égale une valeur attendue, et indique si cela a réussi.
Avec elles, on construit un verrou tournant (spinlock) : un thread répète test-and-set jusqu’à obtenir la valeur faux. C’est bien pour des sections critiques très courtes sur un multicœur ; sinon il gaspille du CPU, et il vaut mieux que le thread se bloque et cède le processeur.
Les sémaphores
Un sémaphore (Dijkstra, 1965) est un entier avec deux opérations atomiques :
- wait (ou P) : si la valeur est positive, il la décrémente, sinon il bloque le thread jusqu’à ce qu’elle devienne positive ;
- signal (ou V) : incrémente la valeur et réveille un thread en attente, s’il y en a.
Un sémaphore initialisé à 1 est un mutex : wait avant la section critique, signal après. Un sémaphore initialisé à
compte des ressources disponibles.
Producteur et consommateur. Un producteur met des éléments dans un tampon circulaire de
cases, un consommateur les retire. Il faut trois sémaphores : e compte les cases vides (initialement
), f les cases pleines (initialement 0), m protège les indices (initialement 1).

/* producer */ /* consumer */
wait(e); wait(f);
wait(m); wait(m);
buf[i] = x; i = (i+1) % N; y = buf[j]; j = (j+1) % N;
signal(m); signal(m);
signal(f); signal(e);Le producteur se bloque sur e quand le tampon est plein, le consommateur sur f quand il est vide. L’ordre des wait compte : si le producteur faisait wait(m) avant wait(e) et trouvait le tampon plein, il se bloquerait en détenant m, et le consommateur ne pourrait plus entrer pour libérer une case. C’est un interblocage (leçon sur l’interblocage).
Les moniteurs
Les sémaphores sont puissants mais faciles à mal utiliser : un wait oublié ou échangé casse tout. Les langages modernes offrent des constructions de plus haut niveau. Un moniteur regroupe des données partagées et des procédures, avec la garantie qu’un seul thread à la fois exécute une procédure ; pour attendre une condition à l’intérieur du moniteur, on utilise des variables de condition, avec les opérations wait (qui libère le moniteur pendant l’attente) et signal. En Java, tout objet est un moniteur (synchronized, wait, notify) ; en C et C++, on utilise les mutex et les variables de condition de la bibliothèque de threads.
Une alternative est d’éviter le partage : structures de données sans verrou fondées sur le compare-and-swap, ou threads qui ne partagent rien et ne communiquent que par messages, comme dans les langages Go et Erlang.






Ciao, sono l'autore di «Sincronizzazione: sezione critica, Peterson, semafori e monitor». Domande, dubbi, segnalazioni di errori o richieste di approfondimento sono benvenuti: scriveteli qui sotto e vi rispondo io. Potete anche votare la pagina con le stelle all'inizio dell'articolo.Hi, I am the author of “Synchronisation: critical section, Peterson, semaphores and monitors”. Questions, doubts, error reports and requests for more detail are all welcome: write them below and I will answer. You can also rate the page with the stars at the top of the article.