Aller au contenu
ELECTRONICS ENGINEERINGelectronics-engineering.com
Systèmes d'exploitation

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/

Pas encore de vote : soyez le premier à noter cette page.

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 AThread Bcounter
lit 55
lit 55
écrit 66
écrit 66

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 :

  1. l’exclusion mutuelle : au plus un thread à la fois dans la section critique ;
  2. 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 ;
  3. 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é à N compte des ressources disponibles.

Producteur et consommateur. Un producteur met des éléments dans un tampon circulaire de N cases, un consommateur les retire. Il faut trois sémaphores : e compte les cases vides (initialement N), f les cases pleines (initialement 0), m protège les indices (initialement 1).

Producteur et consommateur avec un tampon circulaire
Le producteur P écrit à la position i, le consommateur C lit à la position j ; quatre cases sur huit sont pleines. Les sémaphores sont e égal à 4 cases vides, f égal à 4 cases pleines et m égal à 1, exclusion mutuelle libre.
/* 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.

S’abonner
Notifier de
guest
1 commentaire
Le plus ancien
Plus récent Les plus votés
1
0
Vous avez apprécié cet article ? Merci de laisser un commentaire.x