Threads et synchronisation

Un processus a un espace d’adressage et, jusqu’ici, un seul flot d’exécution. Mais beaucoup de programmes veulent faire plusieurs choses à la fois : un serveur qui sert de nombreux clients, un navigateur qui décode des images pendant qu’on fait défiler la page, un compilateur qui occupe tous les cœurs de la machine. Des processus séparés le pourraient, mais ils ne partagent pas leur mémoire, et les créer comme passer de l’un à l’autre coûte cher. Les threads (ou fils d’exécution) sont la réponse : plusieurs flots d’exécution dans un même processus, qui partagent sa mémoire. Et dès que deux flots partagent de la mémoire apparaît une nouvelle famille de bugs, contre laquelle le système doit fournir des outils.

Les sujets classiques sont les processus qui coopèrent, les courses critiques qu’ils provoquent, et les sémaphores pour les corriger. Ce chapitre les parcourt en C avec les threads POSIX, mesuré sur l’Apple M2 où il a été écrit, sous macOS et dans une machine virtuelle Linux.

Les threads : un espace d’adressage, plusieurs flots

Chaque thread a ce qu’il lui faut pour s’exécuter seul : ses propres registres, son compteur de programme et sa pile. Tout le reste appartient au processus et est partagé : le code, les variables globales, le tas, les fichiers ouverts. Un pointeur vers un objet du tas est valable dans tous les threads, ce qui rend la coopération bon marché, et permet à deux threads de modifier le même objet au même instant.

#include <pthread.h>

void *work(void *arg) {         // runs in the new thread
    /* ... */
    return NULL;
}

pthread_t t;
pthread_create(&t, NULL, work, NULL);   // start a second flow of execution
/* ... the first flow continues here ... */
pthread_join(t, NULL);                  // wait for it to finish

Le noyau ordonnance des threads, pas des processus : sous Linux, chaque thread est une tâche à part entière, créée par l’appel système clone avec des options qui disent quoi partager avec le parent, et il apparaît sous /proc/<pid>/task. Sur un cœur, un changement de contexte entre deux threads du même processus coûte moins cher qu’entre deux processus, puisque l’espace d’adressage et le TLB restent en place. La création aussi est moins chère. Créer puis rejoindre un thread qui ne fait rien a pris 23 µs sous macOS et 62 à 65 µs dans la VM Linux, contre 0,7 à 1 ms et 0,12 ms pour fork suivi de wait dans le chapitre sur les processus.

L’exemple classique pour montrer l’intérêt des threads est un serveur web doté d’un cache de pages : pendant qu’un thread attend le disque, les autres servent des requêtes depuis le cache partagé. L’image reste juste, même si l’attente du disque est aujourd’hui plus proche de 100 µs que de 20 ms.

Une course critique, pour de vrai

Deux threads ajoutent chacun 1 à un compteur partagé, dix millions de fois. Le total devrait être de vingt millions :

static volatile long counter;   // volatile: really load and store each time

void *work(void *arg) {
    for (long i = 0; i < 10000000; i++)
        counter++;
    return NULL;
}

Trois exécutions sur le M2 sous macOS ont affiché 10091509, 10163404 et 10069050. Dans la VM Linux : 10145520, 10440722 et 10643606. Près de la moitié des incréments ont été perdus, et le nombre change à chaque fois.

La raison est que counter++ n’est pas une étape indivisible. Sur ARM64, il se compile en trois instructions : charger la valeur dans un registre, ajouter 1, la réécrire.

ldr  x9, [x8]        ; read counter
add  x9, x9, #1      ; add 1 in a register
str  x9, [x8]        ; write it back

Si les deux threads chargent la même valeur, tous deux écrivent valeur + 1, et un incrément est perdu. x86-64 le compile en une seule instruction, inc QWORD PTR [rip+counter], mais cela ne change rien : l’instruction lit toujours la mémoire puis l’écrit, et un autre cœur peut s’intercaler entre les deux. La vue micro du simulateur montre les deux transactions séparées sur le bus :

Une lecture de counter sur le bus (READ), l’UAL ajoute 1, puis une écriture (WRITE) : trois cycles de bus en comptant le chargement de l’instruction, dont deux pour la donnée. Sur une machine multicœur, ces deux transactions sont exactement l’endroit où peut tomber l’incrément d’un autre cœur. C’est une course critique (race condition) : le résultat dépend du minutage des threads. Un exemple classique est plus subtil (un réveil perdu entre un producteur et un consommateur), mais la nature est la même : une suite d’opérations qui devrait se dérouler d’un bloc, et ne le fait pas.

L’exclusion mutuelle

La partie du code qui ne doit pas s’exécuter dans deux threads à la fois (ici, counter++) est une section critique. L’outil standard pour la protéger est un mutex (de mutual exclusion, exclusion mutuelle) : un verrou qu’un seul thread à la fois peut tenir.

static pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;

pthread_mutex_lock(&lock);      // blocks while another thread holds it
counter++;
pthread_mutex_unlock(&lock);

Avec le mutex, les trois exécutions ont affiché exactement 20000000, sur les deux systèmes. Le prix : la boucle a pris de 193 à 197 ms sous macOS au lieu de 6,5 ms, et de 610 à 670 ms au lieu de 17 à 19 ms dans la VM Linux.

Comment construire un verrou, quand vérifier « est-il libre ? » puis le prendre est déjà une course ? Avec les instructions atomiques du CPU, qui lisent et modifient un emplacement mémoire en une seule opération indivisible qu’aucun autre cœur ne peut interrompre : les instructions préfixées par lock et cmpxchg sur x86, ldadd, cas et les paires lecture exclusive / écriture exclusive ldxr/stxr sur ARM64. Un mutex est un mot en mémoire : le verrouiller, c’est un compare-et-échange (compare-and-swap) atomique de « libre » vers « pris ». S’il réussit, le thread continue sans jamais entrer dans le noyau. C’est seulement si le verrou est déjà pris que le thread demande au noyau de l’endormir (sous Linux avec l’appel système futex, fast user-space mutex, qui dort jusqu’à ce que le mot à une adresse donnée change), et le thread qui déverrouille le réveille par un autre appel futex. Les sections critiques de Windows, rapides parce qu’elles restent en espace utilisateur, fonctionnent de la même façon.

Les opérations sur les sémaphores étaient autrefois des appels système, rendus indivisibles sur un seul processeur en masquant les interruptions. Ces deux points décrivent des systèmes plus anciens. Les verrous et sémaphores actuels reposent sur des instructions atomiques en espace utilisateur, qui fonctionnent entre plusieurs cœurs, et ne coûtent un appel système que lorsqu’un thread doit réellement attendre.

Les opérations atomiques

Pour un simple compteur, un verrou est excessif : le CPU peut faire tout l’incrément de façon atomique. C11 l’expose :

#include <stdatomic.h>
static _Atomic long counter;

atomic_fetch_add_explicit(&counter, 1, memory_order_relaxed);

Voici ce qu’émettent les compilateurs pour un incrément ordinaire et pour cet incrément atomique :

Avec les atomiques, toutes les exécutions ont affiché 20000000, en 155 à 170 ms sous macOS et 120 à 129 ms sous Linux. L’argument memory_order indique comment l’opération est ordonnée par rapport aux autres accès mémoire du thread ; relâché (relaxed) veut dire « atomique, mais sans promesse d’ordre ». La valeur par défaut, la cohérence séquentielle, est plus forte et utilise sur ARM64 ldaddal au lieu de ldadd. Le chapitre sur l’ISA montre avec des tests décisifs (litmus tests) pourquoi l’ordre compte quand des threads communiquent par la mémoire, et ce que signifient acquisition et libération.

Ce que coûte la synchronisation

Mesure du temps par opération sur 20 millions d’opérations, réparties entre 1 et 8 threads qui frappent tous la même variable :

Trois leçons. Sans contention, un mutex coûte environ 6 à 7 ns, bien moins que les 95 à 155 ns d’un appel système, ce qui confirme qu’aucun appel système n’a lieu. Avec contention, tout ralentit, parce que la ligne de cache qui contient la variable doit voyager de cœur en cœur à chaque opération : un compteur partagé est un goulet d’étranglement, quelle que soit la façon de le protéger. Et sous forte contention, le mutex peut battre l’atomique : le thread qui tient le verrou fait de nombreux incréments d’affilée pendant que les autres dorment, alors que les atomiques font rebondir la ligne à chaque opération. Ce sommeil apparaît dans le nombre de changements de contexte de la VM Linux : quelques dizaines au plus pour les exécutions atomiques, de 1 200 à 3 700 pour le mutex avec deux threads, et environ 115 000 avec huit, chacun étant un endormissement et un réveil par futex.

La réponse pratique est de moins partager. Un programme qui a besoin d’un compte global donne à chaque thread son propre compteur et les additionne à la fin.

Sémaphores et producteur-consommateur

L’exemple central est le problème du producteur-consommateur : un thread produit des éléments dans un tampon borné, un autre les consomme. Le consommateur doit attendre quand le tampon est vide, le producteur quand il est plein. Une première tentative naïve, avec des appels explicites pour dormir et réveiller, contient une course : le consommateur constate que le tampon est vide, le producteur insère un élément et envoie un réveil avant que le consommateur ne se soit endormi, le réveil est perdu, et les deux finissent par dormir pour toujours.

Les sémaphores de Dijkstra corrigent cela. Un sémaphore est un compteur doté de deux opérations atomiques : down (sem_wait en POSIX) le décrémente, ou dort tant qu’il vaut 0 ; up (sem_post) l’incrémente et réveille un dormeur s’il y en a un. Un réveil envoyé trop tôt n’est pas perdu : il reste dans le compte. Deux sémaphores résolvent le producteur-consommateur, l’un comptant les cases vides, l’autre les cases pleines :

sem_t empty_slots, full_slots;          // start at SLOTS and 0

void *producer(void *arg) {
    for (long i = 1; i <= ITEMS; i++) {
        sem_wait(&empty_slots);         // down: wait for a free slot
        buf[in] = i; in = (in + 1) % SLOTS;
        sem_post(&full_slots);          // up: one more item
    }
    return NULL;
}

void *consumer(void *arg) {
    long sum = 0;
    for (long i = 1; i <= ITEMS; i++) {
        sem_wait(&full_slots);          // down: wait for an item
        sum += buf[out]; out = (out + 1) % SLOTS;
        sem_post(&empty_slots);         // up: one more free slot
    }
    *(long *)arg = sum;
    return NULL;
}

Avec un tampon de 8 cases et un million d’éléments, la somme du consommateur a donné 500000500000, le bon total, à chaque exécution sous Linux, à environ 4 µs par élément : les threads passent l’essentiel de leur temps à dormir et à se réveiller mutuellement. Avec un seul producteur et un seul consommateur, chaque index n’est touché que par un thread, donc aucun mutex n’est nécessaire ; avec plusieurs producteurs, in en demanderait un.

Sous macOS, le même programme échoue dès la première ligne : sem_init renvoie −1 avec ENOSYS, « Function not implemented ». macOS n’accepte que les sémaphores POSIX nommés (sem_open) et propose ses propres alternatives, comme les sémaphores de Grand Central Dispatch. La norme qui promettait la portabilité ne la garantit pas pour chaque appel.

Les variables de condition

L’outil le plus courant aujourd’hui est un mutex associé à des variables de condition, qui font partie de l’API pthread. Une variable de condition permet à un thread de dormir jusqu’à ce qu’un autre signale un changement, en relâchant le mutex pendant son sommeil et en le reprenant avant de revenir :

pthread_mutex_lock(&m);
while (count == 0)                        // re-check after every wakeup
    pthread_cond_wait(&not_empty, &m);    // unlock, sleep, relock
int item = buf[out]; out = (out + 1) % SLOTS; count--;
pthread_cond_signal(&not_full);
pthread_mutex_unlock(&m);

Contrairement à un sémaphore, une variable de condition n’a pas de mémoire : un signal sans personne pour l’attendre est perdu. C’est pourquoi la condition est tenue dans des variables ordinaires protégées par le mutex (count ici), et pourquoi on la teste dans une boucle while : l’état est vérifié sous le verrou, si bien qu’aucun réveil ne peut tomber entre le test et l’endormissement. Le même million d’éléments est passé en environ 1 µs par élément sous macOS et 4,2 à 4,6 µs dans la VM Linux, avec la bonne somme.

L’interblocage

Les verrous résolvent les courses et créent un nouveau problème. Deux threads ont chacun besoin de deux mutex, a et b, et les prennent dans des ordres opposés :

void *t1(void *x) { for (;;) { lock(&a); lock(&b); rounds++; unlock(&b); unlock(&a); } }
void *t2(void *x) { for (;;) { lock(&b); lock(&a); rounds++; unlock(&a); unlock(&b); } }

Si t1 prend a pendant que t2 prend b, chacun attend pour toujours le verrou que tient l’autre. Un thread de surveillance qui vérifie toutes les 0,1 s que rounds augmente encore l’a surpris à chaque fois, dix exécutions sur dix : après 19 tours au minimum et 3 474 au maximum. En faisant prendre a en premier à t2, comme t1, le même programme a tourné 5 s et 177 millions de tours sans accroc.

Un interblocage (deadlock) exige quatre conditions à la fois (Coffman et ses collègues, 1971) : des ressources utilisées en exclusion mutuelle ; des threads qui gardent une ressource en attendant une autre ; pas de préemption (on ne peut pas retirer un verrou à celui qui le tient) ; et une attente circulaire. En supprimer une seule suffit à l’empêcher. En pratique, les programmes brisent le cercle : tous les threads prennent les verrous dans le même ordre global, comme dans la correction ci-dessus. Les bases de données, qui ne peuvent pas imposer d’ordre à des transactions arbitraires, détectent plutôt les cycles et annulent l’une des transactions en cause.

À retenir

• Les threads sont des flots d’exécution qui partagent un espace d’adressage ; chacun a ses registres et sa pile. Ils coûtent moins cher à créer que des processus : 23 µs sous macOS, 62 à 65 µs dans la VM Linux.
• Une course critique est un résultat qui dépend du minutage. counter++ exécuté par deux threads a perdu près de la moitié de 20 millions d’incréments, parce que c’est une lecture, une addition et une écriture.
• Un mutex protège une section critique. Il repose sur des instructions atomiques et n’entre dans le noyau (via futex sous Linux) que pour dormir : environ 6 à 7 ns sans contention.
• Les atomiques (lock inc, ldadd) rendent une opération indivisible : 2 ns en mode relâché, 4 ns en cohérence séquentielle. Sous contention, toute variable partagée coûte des dizaines de nanosecondes par opération.
• Les sémaphores comptent les réveils pour qu’aucun ne soit perdu, et résolvent le producteur-consommateur avec deux compteurs ; macOS n’implémente pas les sémaphores anonymes. Les variables de condition avec un mutex sont l’alternative habituelle, toujours attendues dans une boucle while.
• Un interblocage exige exclusion mutuelle, détention en attente, absence de préemption et attente circulaire. Prendre les verrous dans un ordre fixe l’empêche.