Fils d’exécution, conditions de concurrence et verrous

Un fil d’exécution est une séquence d’exécution au sein d’un processus. Plusieurs fils peuvent travailler sur les mêmes données du programme, mais chacun doit avoir sa propre position dans le code et ses propres appels de fonction inachevés.

Ce qui est partagé et ce qui appartient à un fil

Les fils d’un processus partagent le code, les variables globales et statiques, les objets du tas, les descripteurs de fichier ouverts et l’identifiant du processus. Chaque fil possède son propre compteur ordinal, ses registres, sa pile et son identifiant. Une variable globale int total désigne un seul objet partagé. Une variable locale ordinaire int i dans la fonction du travailleur désigne un objet différent à chaque appel.

Un processus à trois fils possède trois piles à des adresses différentes dans le même espace d’adressage. Une pile n’est pas un compartiment protégé : un autre fil peut accéder à une variable locale s’il reçoit son adresse. Ce partage n’est valide que pendant l’existence de la variable. Un pointeur vers le cadre de pile d’une fonction terminée ne peut pas maintenir la variable en vie. De grands tableaux locaux et une récursion profonde peuvent aussi épuiser la pile d’un fil.

Passage d’un fil à l’autre

Le système d’exploitation sauvegarde l’état d’exécution de chaque fil dans un bloc de contrôle de fil d’exécution, ou TCB. Lorsqu’il passe de T1 à T2, il sauvegarde les registres de T1 et restaure ceux de T2. Le calcul inachevé de T1 reste dans ses registres sauvegardés jusqu’à sa reprise.

Pour les fils d’un même processus, l’espace d’adressage reste le même pendant la commutation. Les tables des pages n’ont pas besoin de changer, ce qui rend généralement cette commutation moins coûteuse qu’une commutation entre processus. La mémoire partagée implique aussi des défaillances partagées : une écriture par un pointeur invalide peut endommager les données d’un autre fil, et une erreur qui termine le processus met fin à tous ses fils.

Pourquoi utiliser plusieurs fils ?

Le parallélisme désigne une exécution au même instant sur des cœurs de processeur différents. Quatre parties indépendantes d’un calcul peuvent s’exécuter près de quatre fois plus vite sur quatre cœurs, si le travail partagé et la coordination ne deviennent pas des goulots d’étranglement. Les fils permettent aussi à un programme de travailler pendant une attente : pendant que l’un attend une lecture disque ou une réponse réseau, un autre peut utiliser le processeur.

La concurrence signifie que des exécutions progressent pendant des périodes qui se chevauchent. Sur un cœur, l’ordonnanceur passe d’un fil à l’autre : ils sont donc concurrents sans s’exécuter en parallèle. Un seul cœur permet tout de même des bogues de concurrence : une commutation peut interrompre une mise à jour partagée entre ses instructions machine.

Qui ordonnance les fils ?

Linux et Windows utilisent un modèle un à un : chaque fil applicatif ordinaire correspond à un fil ordonnancé par le noyau. Différents fils peuvent s’exécuter sur différents cœurs et un appel bloquant bloque le fil qui l’a effectué. Une bibliothèque plusieurs à un ordonnance plusieurs fils utilisateur sur un seul fil noyau. Ses commutations peuvent coûter peu, mais elle ne peut pas exécuter ces fils sur plusieurs cœurs et un appel système bloquant peut arrêter tout le groupe.

Créer A avant B ne garantit pas que A s’exécute en premier. Si A affiche « A » et B affiche « B », le résultat peut être « AB » ou « BA ». L’ordre de création détermine quand un fil devient disponible pour s’exécuter ; l’ordonnanceur choisit le moment de son exécution.

L’interface des fils d’exécution POSIX, ou pthreads, démarre une fonction C dans un autre fil. Inclus <pthread.h> et compile avec une commande telle que gcc -pthread -o sum sum.c. L’option -pthread fournit les paramètres de compilation et d’édition de liens pour le code utilisant des fils.

Créer un fil avec des arguments stables

L’appel pthread_create(&t, NULL, worker, arg) stocke un identifiant de fil dans t et démarre worker(arg). Le pointeur d’attributs NULL demande les valeurs par défaut. Un travailleur a la signature void *worker(void *arg) : l’argument et la valeur de retour sont des pointeurs. Une structure permet à ce pointeur unique de transmettre plusieurs champs.

#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>

struct range { int lo, hi; long result; };

void *sum_range(void *arg) {
    struct range *r = arg;
    long sum = 0;
    for (int n = r->lo; n <= r->hi; n++)
        sum += n;
    r->result = sum;
    return NULL;
}

Le créateur prépare deux structures, {1, 50, 0} et {51, 100, 0}, et transmet une adresse différente à chaque travailleur. Garde les deux structures en vie jusqu’à la fin des travailleurs. Chaque travailleur accumule sa somme dans sa propre variable locale sum et n’écrit que dans son propre champ result.

pthread_create renvoie 0 en cas de succès et un numéro d’erreur en cas d’échec. Vérifie directement ce numéro ; la fonction ne définit pas errno pour signaler l’échec. Seule une création réussie fournit un fil dont on peut effectuer la jonction.

Effectuer la jonction avant de lire les résultats

Après avoir créé les deux travailleurs avec succès, le fil principal appelle pthread_join(t[0], NULL) et pthread_join(t[1], NULL). Une jonction bloque jusqu’à la fin du fil visé. Une jonction réussie rend également les écritures de ce travailleur visibles pour le fil qui effectue la jonction. Le fil principal peut alors lire 1 275 et 3 775 et les additionner pour obtenir 5 050 sans mutex : les travailleurs ont écrit dans des objets distincts et le fil principal a attendu avant de les lire.

Démarrer les deux fils avant d’effectuer leur jonction permet à leurs travaux de se chevaucher. Créer un travailleur et effectuer immédiatement sa jonction avant de créer le suivant les fait s’exécuter l’un après l’autre.

Voici le programme principal. Il s’arrête en cas d’erreur pthread et n’utilise donc jamais un identifiant issu d’une création qui a échoué :

static void require_success(int rc) {
    if (rc != 0) {
        fprintf(stderr, "pthread error: %d\n", rc);
        exit(EXIT_FAILURE);
    }
}

int main(void) {
    struct range jobs[2] = {{1, 50, 0}, {51, 100, 0}};
    pthread_t threads[2];
    for (int i = 0; i < 2; i++)
        require_success(pthread_create(&threads[i], NULL,
                                      sum_range, &jobs[i]));
    for (int i = 0; i < 2; i++)
        require_success(pthread_join(threads[i], NULL));
    printf("%ld\n", jobs[0].result + jobs[1].result);
    return 0;
}

Pour recueillir un pointeur renvoyé, transmets l’adresse où le recevoir : void *answer; pthread_join(t, &answer);. Le pointeur doit désigner une zone mémoire qui survit au travailleur, comme de la mémoire allouée sur le tas ou une structure appartenant au créateur. Renvoyer &local_result depuis le travailleur est invalide, car sa variable locale cesse d’exister au retour de la fonction.

Éviter de partager une variable de boucle qui change

Transmettre &i à chaque travailleur dans une boucle de création revient à transmettre plusieurs fois la même adresse. Les travailleurs peuvent la lire après que la boucle l’a modifiée : plusieurs peuvent donc recevoir le même identifiant apparent. Utilise plutôt un tableau : affecte ids[i] = i, transmets &ids[i] et garde le tableau en vie et inchangé jusqu’à la fin de toutes les jonctions.

Terminer les fils et les processus délibérément

Le retour de main, ou l’appel de exit() dans n’importe quel fil, termine tout le processus et peut interrompre les travailleurs. Le fil principal effectue normalement leur jonction avant de se terminer. L’appel de pthread_exit() ne termine que le fil appelant ; les autres peuvent continuer.

Un fil détaché libère automatiquement ses ressources de fil lorsqu’il se termine et ne peut pas faire l’objet d’une jonction. Veille à ce que chaque fil joignable fasse une fois l’objet d’une jonction ou soit détaché. La jonction attend la fin du fil ; elle ne protège pas deux travailleurs qui mettent à jour le même objet pendant qu’ils s’exécutent tous deux.

L’instruction counter++ semble simple, mais l’incrément d’un entier partagé ordinaire n’est pas une opération indivisible. Il charge généralement une valeur, effectue une addition dans un registre et stocke le résultat. Un autre fil peut s’exécuter entre ces étapes.

Un suivi qui perd un incrément

Pars de counter égal à 50. Considère le chargement, l’addition et le stockage comme des étapes machine distinctes :

Deux incréments auraient dû produire 52. T1 écrase au contraire le résultat de T2 avec une valeur calculée à partir de l’ancienne valeur 50. C’est une mise à jour perdue.

Une commutation de contexte conserve les registres de T1 dans son TCB. Lorsque T1 reprend, son registre contient toujours 51 ; il ne recharge pas le compteur partagé simplement parce que T2 s’est exécuté. L’erreur réside dans la séquence non protégée, pas dans la restauration d’un registre incorrect par l’ordonnanceur.

Comparer avec une exécution en série

Si T1 termine les trois étapes avant que T2 ne charge la valeur, T1 stocke 51 puis T2 stocke 52. Inverser l’ordre d’exécution des fils entiers donne aussi 52. Le résultat entrelacé 51 ne peut provenir d’aucun des deux ordres en série. Pour repérer ce type de défaillance, marque une lecture, place une écriture d’un autre fil après celle-ci, puis reprends le calcul du premier fil fondé sur sa lecture périmée.

Ce suivi est un modèle du bogue au niveau machine. En C réel, des accès conflictuels non synchronisés à un entier partagé ordinaire constituent une course aux données, qui entraîne un comportement indéfini. Le C ne limite pas ce programme aux résultats d’un simple modèle d’entrelacement d’instructions.

Pourquoi la réussite des tests est une preuve faible

Deux fils effectuant chacun 10 000 000 d’incréments devraient produire 20 000 000. Des exécutions expérimentales non protégées peuvent afficher différents totaux plus faibles, comme 19 345 221 et 19 221 041 dans des exemples publiés. Une exécution dont le résultat paraît correct signifie seulement que le résultat observé était acceptable cette fois-là.

La fenêtre de vulnérabilité peut ne durer que quelques instructions. Un nombre de cœurs différent, d’autres choix du compilateur ou la charge du système peuvent révéler un ordonnancement que des milliers d’exécutions précédentes n’ont pas rencontré. Pour deux fils effectuant chacun un incrément modélisé à partir de zéro, le modèle de suivi permet d’obtenir 1 ou 2. Avec au moins deux incréments par fil, de rares ordonnancements peuvent laisser un total aussi faible que 2 même lorsque le nombre d’incréments prévus augmente.

Corriger l’opération, pas son apparence

Déclarer l’entier volatile ne rend pas son chargement, son addition et son stockage indivisibles et ne synchronise pas les fils. Écrire tout le travail sur une seule ligne ne change rien. Même une instruction x86 qui ajoute directement à la mémoire doit utiliser la forme atomique appropriée pour assurer la coordination entre les cœurs.

Protège toute la lecture-modification-écriture avec un mutex partagé ou utilise une opération atomique de lecture-modification-écriture de C11 telle que atomic_fetch_add. Ce besoin existe aussi sur un seul cœur : une commutation déclenchée par l’horloge peut séparer le chargement du stockage, même sans exécution parallèle.

Une erreur de concurrence peut concerner un accès mémoire ou toute une règle métier. Identifie à la fois les objets partagés et l’opération qui doit paraître indivisible aux autres fils.

Condition de concurrence ou course aux données ?

Une condition de concurrence se produit lorsque la justesse dépend du moment relatif des opérations. Une course aux données se produit lorsque différents fils accèdent au même emplacement mémoire sans synchronisation, qu’au moins l’un y écrit et qu’au moins un accès est non atomique. En C11 et C++11, une course aux données entraîne un comportement indéfini.

Des accès atomiques peuvent éviter une course aux données alors qu’une opération plus large présente toujours une condition de concurrence. Par exemple, des lectures et écritures protégées individuellement ne maintiennent pas la validité d’une décision entre ces accès. Deux fils peuvent chacun lire un solde suffisant, libérer le verrou, puis effectuer un retrait sur la base de cette décision périmée.

Étudier un retrait

Un solde commence à 100. Deux fils demandent chacun 80. La règle consiste à n’accepter un retrait que si le solde le permet.

1. T1 vérifie 100 et décide que son retrait peut réussir.
2. T2 vérifie aussi 100 et prend la même décision.
3. T1 soustrait 80, ce qui laisse 20.
4. T2 agit sur la base de sa décision antérieure et soustrait 80 de 20, ce qui laisse −60.

Protéger uniquement la soustraction ne corrige pas cette séquence. Protège la vérification et la soustraction avec le même verrou, détenu sans interruption. Un fil laisse alors 20, et le suivant vérifie 20 et refuse le retrait. Un autre ordonnancement non protégé peut perdre une soustraction et laisser 20 après le versement des deux retraits, ce qui est également incorrect.

Repérer la section critique

Une section critique est la portion de code accédant aux données partagées qui doit exclure les accès concurrents. Une séquence de lecture-modification-écriture lit d’abord les données, calcule une nouvelle valeur et la réécrit. Une séquence de vérification puis action détermine si une action est autorisée, puis l’effectue. Les opérations sur les listes, l’initialisation différée et la création de fichiers peuvent aussi contenir ces séquences.

Un verrou assure l’exclusion mutuelle : au plus un fil participant à la fois se trouve dans la zone protégée. Une opération atomique apparaît aux autres fils participants comme une seule opération complète ; ils ne peuvent pas observer un état inachevé. Un mutex n’offre cette vue qu’au code qui respecte la même règle de verrouillage.

Tous les objets n’ont pas besoin d’un verrou. Les données auxquelles un seul fil accède restent privées tant que leur adresse n’est pas partagée. Les données entièrement initialisées avant le démarrage des travailleurs et seulement lues ensuite peuvent être partagées sans verrouillage. Détermine qui peut accéder à un objet et si des écritures se chevauchent avec son utilisation, plutôt que de te limiter à l’endroit où il a été déclaré.

Ce que garantit une solution correcte

• Exclusion mutuelle : les fils concurrents ne peuvent pas entrer ensemble.
• Progression : lorsque la section est libre et que des fils souhaitent y entrer, les fils qui n’essaient pas d’entrer ne peuvent pas retarder indéfiniment le choix d’un entrant.
• Attente bornée : après une demande, le nombre d’entrées concurrentes qui peuvent la précéder est limité.

En C11, atomic_fetch_add(&count, 1) effectue une mise à jour atomique sur un atomic_int. L’atomicité est garantie même sur une plateforme qui implémente l’opération avec un verrou interne de bibliothèque. Rendre atomiques individuellement deux champs de comptes ne transforme toujours pas un transfert entre eux en une transaction atomique unique ; la relation entre les champs doit aussi être protégée.

Un mutex est un verrou qui permet à un seul fil à la fois de posséder une zone protégée. Un fil l’acquiert avant d’accéder aux données protégées et le libère ensuite. Si un autre fil le détient, un appel de verrouillage bloquant attend.

Initialiser le mutex partagé

Utilise pthread_mutex_t de <pthread.h>. Un mutex statique peut être initialisé avec pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER;. Un objet créé dynamiquement peut initialiser son champ avec pthread_mutex_init(&obj->lock, NULL). L’initialisation doit être terminée avant qu’un fil utilise le mutex.

Voici une opération sur un compteur utilisant un mutex partagé initialisé statiquement. La fonction auxiliaire vérifie les valeurs renvoyées par pthread, qui sont directement des numéros d’erreur :

#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>

static pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER;
static long counter = 0;  // guarded by m

static void check(int rc) {
    if (rc != 0) {
        fprintf(stderr, "pthread error: %d\n", rc);
        exit(EXIT_FAILURE);
    }
}

void increment(void) {
    check(pthread_mutex_lock(&m));
    counter = counter + 1;
    check(pthread_mutex_unlock(&m));
}

Toute lecture ou mise à jour concurrente de counter doit suivre cette même règle. Une fonction distincte utilisant un autre mutex ne serait pas coordonnée avec increment.

Que se passe-t-il pendant que le mutex est détenu ?

T1 verrouille m, charge le compteur, calcule et stocke le résultat. Si T2 appelle pthread_mutex_lock(&m) pendant cet intervalle, il ne peut pas poursuivre après l’appel avant d’avoir acquis le mutex une fois que T1 l’a libéré. T1 peut toujours subir une préemption : un mutex empêche les entrées concurrentes, pas les commutations de contexte.

Pour la règle du solde, détiens le mutex avant d’évaluer balance >= amount. Ne soustrais la somme que si la vérification réussit, enregistre le succès ou l’échec, puis déverrouille. Un solde de 100 avec deux demandes de 80 permet exactement un retrait et laisse 20.

Choisir comment attendre

pthread_mutex_trylock(&m) revient immédiatement : 0 signifie que l’appelant a acquis le mutex ; EBUSY signifie qu’il ne l’a pas acquis parce que le mutex était détenu. Dans ce dernier cas, il peut effectuer un autre travail et ne doit pas accéder aux données protégées. pthread_mutex_timedlock attend jusqu’à une échéance absolue. Ces interfaces exigent toujours de vérifier les codes de retour et de ne libérer un verrou qu’après une acquisition réussie.

Respecter la possession et la durée de vie

Le fil possesseur libère le mutex. Un mutex normal non récursif bloque si son possesseur essaie de le verrouiller à nouveau. Un mutex avec vérification d’erreurs signale les erreurs comme un nouveau verrouillage avec EDEADLK ou un déverrouillage par un autre fil avec EPERM. Un mutex récursif compte les acquisitions répétées par son possesseur et exige le même nombre de libérations. Ne compte pas sur un mutex par défaut pour diagnostiquer une utilisation incorrecte : son comportement dépend du type auquel l’implémentation l’associe et de l’opération.

Lorsque tous les fils ont cessé d’utiliser le mutex et qu’il est déverrouillé, appelle pthread_mutex_destroy. Détruire ou libérer un objet alors qu’un autre fil peut encore le verrouiller compromet la durée de vie du mutex. Transmettre le mutex par pointeur préserve son identité ; le copier ne crée pas un autre accès valide au même verrou.

La granularité du verrouillage est la quantité d’état partagé couverte par un verrou. Elle détermine quelles opérations doivent s’attendre mutuellement, même lorsqu’elles s’exécutent sur des cœurs différents.

Un grand verrou ou plusieurs petits verrous ?

Une conception à gros grain place un mutex autour d’une structure ou d’un sous-système entier. Sa règle de protection est simple, mais des opérations sans lien entre elles sont sérialisées. Une conception à grain fin attribue des mutex distincts à des comptes, des alvéoles ou des zones distincts. Les fils peuvent alors travailler simultanément dans différentes zones, au prix d’un plus grand nombre d’opérations de verrouillage et de règles plus compliquées.

Place le verrou à côté de l’état qu’il protège :

struct account {
    pthread_mutex_t lock;
    long balance;
    unsigned id;
};

Une opération sur un compte prend son mutex. Un transfert entre deux comptes distincts nécessite les deux mutex, car il modifie leur relation. Choisis un ordre fixe, par exemple par identifiant de compte croissant, et utilise-le sur chaque chemin. Sinon, un fil peut détenir A et attendre B pendant qu’un autre détient B et attend A.

Un verrou plafonne le débit

Supposons que chaque opération détienne un verrou global unique pendant 2 µs. Le travail protégé peut achever au plus une opération toutes les 2 µs :

Ajouter des cœurs ne permet pas à deux opérations de détenir simultanément le même mutex. Le surcoût du verrou et les autres tâches peuvent réduire encore le débit obtenu. La durée de la partie protégée constitue donc une limite utile à calculer avant d’espérer une accélération.

Raccourcir la section sans compromettre l’opération

Prépare le travail privé avant d’acquérir le mutex. Pour une insertion dans une liste, alloue le nouveau nœud et renseigne d’abord sa clé. N’acquiers le mutex de la liste qu’au moment de lire la tête actuelle et de chaîner le nœud. Un échec d’allocation se produit alors sans qu’un verrou soit détenu.

Des entrées-sorties lentes, un affichage ou un rappel inconnu peuvent bloquer tous les fils en attente. Déplace ce travail hors de la section lorsque les données peuvent y rester valides. Garde ensemble une décision et la mise à jour qui en dépend : raccourcir un retrait en déverrouillant entre la vérification du solde et la soustraction compromet sa justesse.

Évaluer trois propriétés distinctes

L’exclusion mutuelle demande si la conception empêche réellement les entrées conflictuelles. L’équité demande si un fil en attente finit par obtenir son tour ou peut subir une famine. Les performances concernent le coût du verrou avec un fil, plusieurs fils sur un processeur et des fils sur plusieurs processeurs. Un verrou peut être correct tout en étant inéquitable ou lent.

La contention se produit lorsque des fils se disputent un verrou déjà détenu. En cas de forte contention, ils déplacent aussi entre les cœurs les lignes de cache du verrou et des données partagées. Dans une expérience publiée sur un compteur, un million de mises à jour par un fil ont pris environ 0,03 s, mais deux fils en effectuant chacun un million ont mis plus de 5 s ; ces mesures concernent cette configuration et ne sont pas des durées universelles.

Pour une expérience de passage à l’échelle, garde fixe le travail de chaque fil. Un passage à l’échelle idéal permet à N fils sur N cœurs d’effectuer N fois plus de travail dans le temps initial. Commence par une structure simple et correcte, mesure l’attente et le temps total, puis répartis un verrou uniquement là où la concurrence supplémentaire compense le surcoût ajouté.

Un mutex peut être parfaitement implémenté alors qu’un programme l’utilise incorrectement. Examine tout le chemin parcouru dans une fonction, y compris les lectures, les erreurs, les rappels et la destruction des objets.

Libérer le verrou à chaque sortie

Cette fonction laisse le verrou détenu sur son chemin d’échec :

pthread_mutex_lock(&m);
if (failed) return -1;
update_shared_state();
pthread_mutex_unlock(&m);

Le fil qui effectue le retour peut se terminer, mais le mutex reste détenu. Un appelant ultérieur attend alors une libération qui ne se produira jamais. Utilise un seul chemin de nettoyage ou place un déverrouillage avant chaque retour. Avec des appels pthread vérifiés, la structure peut être :

int rc = -1;
check(pthread_mutex_lock(&m));
if (!failed) {
    update_shared_state();
    rc = 0;
}
check(pthread_mutex_unlock(&m));
return rc;

Il est plus facile d’examiner un seul point de libération que plusieurs points dispersés. La propriété essentielle est que chaque verrou acquis avec succès soit libéré à chaque sortie ordinaire.

Respecter aussi la règle de protection pour les lectures

Une fonction d’état qui « ne fait que lire » peut être en concurrence avec une fonction de mise à jour. Elle peut aussi observer des champs liés à différentes étapes d’une même mise à jour. Si une opération sur une liste publie un nœud avant d’avoir renseigné tous ses champs, un lecteur non protégé peut suivre un pointeur vers des données inachevées. Acquiers le verrou indiqué pour chaque accès dont la justesse en dépend.

Utiliser des mutex différents pour le même objet ne résout rien. Si T1 prend lockA et T2 prend lockB, les deux acquisitions peuvent réussir. Un mutex déclaré comme nouvelle variable locale dans chaque travailleur rend cette erreur facile à manquer : chaque fil verrouille son propre objet, donc aucune exclusion partagée n’existe.

Préserver l’identité et les limites de l’opération

Un pthread_mutex_t ne peut pas être copié par affectation ou par copie de la structure qui le contient, puis utilisé comme second accès au mutex. Utiliser la copie entraîne un comportement indéfini. Transmets un pointeur vers le mutex partagé d’origine.

Vérifie aussi où les libérations ont lieu. Une fonction qui verrouille pour vérifier un solde, déverrouille, puis verrouille à nouveau pour soustraire une somme a protégé les accès individuels, mais laissé la décision devenir périmée. Garde toute la séquence de vérification puis action sous la protection continue du verrou.

Éviter de s’attendre soi-même

Appeler du code inconnu en détenant un mutex peut entraîner un nouvel accès inattendu au même objet protégé. Avec un mutex normal, un second appel de verrouillage par le possesseur bloque ce dernier. Un mutex avec vérification d’erreurs signale cette erreur, tandis qu’un mutex récursif autorise des acquisitions imbriquées et exige autant de déverrouillages. Choisis le type délibérément ; n’utilise pas la récursivité pour masquer une conception de protection peu claire.

Évite si possible les entrées-sorties lentes et les mises en sommeil dans une section critique partagée. Avant de détruire le mutex ou de libérer l’objet qui le contient, assure-toi qu’aucun fil ne le possède ni ne peut y accéder à nouveau. L’initialisation, l’utilisation et la destruction doivent suivre un ordre clair.

Utiliser des outils d’exécution pour révéler les défaillances observées

ThreadSanitizer, activé avec -fsanitize=thread, et Helgrind de Valgrind peuvent signaler les courses aux données et les utilisations incorrectes de verrous dans les exécutions observées. Combine leurs rapports avec un examen des accès partagés et des entrelacements possibles. Une exécution sans signalement établit que l’outil n’a trouvé aucun problème dans ces exécutions ; un chemin non testé exige toujours un raisonnement.

Un verrou a besoin d’un moyen fiable de choisir un seul possesseur. Une lecture ordinaire suivie d’une écriture ordinaire laisse un intervalle dans cette décision, même si le travail protégé est très court.

Le contrôle des interruptions a un rôle limité

Sur un processeur, un noyau peut désactiver brièvement les interruptions autour d’une section critique non bloquante afin d’y empêcher une préemption provoquée par une interruption. Cela suppose de rester sur le processeur sans se bloquer ni provoquer volontairement une commutation. Le noyau utilise cette technique pour de courtes opérations internes.

Ce n’est pas un mutex général pour les applications. Les instructions de contrôle des interruptions sont privilégiées ; donner à une application un accès illimité lui permettrait de monopoliser le processeur. Désactiver les interruptions sur un cœur n’empêche pas les autres cœurs d’accéder aux mêmes données. De longues périodes de désactivation retardent aussi le traitement des interruptions et peuvent entraîner la perte d’événements sur certains périphériques.

Suivre le verrou à indicateur défaillant

Considère ce pseudocode proche du C :

while (flag == 1) { }
flag = 1;
// critical section
flag = 0;

Pars de flag à 0. T1 le teste et quitte la boucle, puis s’interrompt avant l’affectation. T2 teste le même 0, lui affecte 1 et entre. T1 reprend, lui affecte 1 et entre aussi. Les deux ont passé le test avant que l’un d’eux ne prenne possession du verrou.

Rendre la lecture et l’écriture individuellement atomiques supprimerait une course aux données sur l’indicateur, mais laisserait deux opérations distinctes dans ce protocole. La prise de possession nécessite une lecture-modification-écriture atomique ou un algorithme de synchronisation plus complet.

La boucle vide est une attente active : elle vérifie à répétition tout en consommant du temps processeur. Sur un processeur, un fil qui attend activement après avoir provoqué la préemption du possesseur ne peut pas l’aider à libérer le verrou plus tôt. Il doit finir par laisser le possesseur s’exécuter.

La solution de Peterson pour deux fils

L’algorithme de Peterson coordonne deux fils avec un indicateur d’intérêt par fil et un tour partagé. Le fil i effectue :

flag[i] = 1;
turn = 1 - i;
while (flag[1 - i] == 1 && turn == 1 - i) { }
// critical section
flag[i] = 0;

Il annonce son intérêt, donne la priorité à l’autre fil en cas d’égalité et attend seulement tant que l’autre est intéressé et prioritaire. En cohérence séquentielle, les opérations de chaque fil conservent l’ordre du programme et tous les fils observent un ordre commun. Dans ce modèle, l’algorithme de Peterson assure l’exclusion mutuelle, la progression et l’attente bornée pour deux fils.

L’ordre des accès mémoire compte aussi

Les processeurs et compilateurs modernes peuvent rendre visibles les opérations mémoire dans un ordre différent de celui du code source. Un stockage peut rester dans un tampon pendant qu’un chargement ultérieur lit la mémoire. Les deux fils peuvent alors voir l’indicateur d’intérêt de l’autre à 0 et entrer tous les deux. Des entiers C partagés ordinaires introduisent aussi des courses aux données.

Une implémentation valide nécessite des opérations atomiques et un ordre adaptés, par exemple des opérations atomiques C11 à cohérence séquentielle pour les indicateurs et le tour. volatile ne fournit pas cette synchronisation. Les verrous utilisables en pratique combinent une opération indivisible de prise de possession et des garanties sur l’ordre des accès mémoire, afin que les accès protégés restent du bon côté de l’acquisition et de la libération.

Une lecture-modification-écriture atomique combine la lecture d’un emplacement et sa mise à jour en une seule action indivisible. Elle ferme l’intervalle qui permet à deux fils de passer ensemble un test ordinaire d’indicateur.

Échanger l’indicateur et examiner son ancienne valeur

Le test et positionnement, ou échange atomique, écrit une nouvelle valeur et renvoie l’ancienne. Avec un indicateur initialement à 0, T1 y échange la valeur 1 et reçoit 0, donc il entre. T2 y échange la valeur 1 et reçoit 1, donc il attend. Tant que la libération n’écrit pas 0, aucun autre échange ne peut renvoyer 0.

Voici un verrou à attente active C11 utilisant les opérations atomiques à cohérence séquentielle par défaut :

#include <stdatomic.h>

static atomic_flag held = ATOMIC_FLAG_INIT;

void lock(void) {
    while (atomic_flag_test_and_set(&held)) { }
}

void unlock(void) {
    atomic_flag_clear(&held);
}

L’ordre compte autant que l’indicateur. L’acquisition doit maintenir les accès ultérieurs de la section critique après l’acquisition réussie ; la libération doit maintenir les accès antérieurs de la section critique avant la libération. La remise à zéro de l’indicateur doit aussi être atomique ; mélanger des stockages ordinaires et des accès atomiques ne permet pas de mettre en œuvre ce passage de relais.

Comparer avant de remplacer

La comparaison et échange, ou CAS, ne modifie une valeur que lorsqu’elle est égale à une valeur attendue. Supposons que deux fils lisent un compteur à 7 et souhaitent chacun ajouter 1. T2 réussit à remplacer 7 par 8. La tentative de T1 pour remplacer 7 par 8 échoue alors : T1 réessaie à partir de 8 et le remplace par 9. La nouvelle tentative préserve les deux incréments.

En C11, atomic_compare_exchange_strong renvoie un succès ou un échec et met à jour l’argument attendu en cas d’échec. Certains pseudocodes proches du matériel renvoient à la place l’ancienne valeur stockée. Vérifie quelle convention un suivi utilise. Sur x86, xchg avec un opérande mémoire effectue un échange, tandis que lock cmpxchg fournit une comparaison et échange atomique.

Autres mécanismes matériels de base

Le chargement lié et écriture conditionnelle, ou LL/SC, lit une valeur tout en établissant une réservation, puis tente une écriture. L’écriture conditionnelle échoue si une autre écriture a invalidé la réservation ; elle peut aussi échouer pour d’autres raisons et doit donc figurer dans une boucle de nouvelles tentatives. Les instructions LDXR/STXR d’ARM et lr/sc de RISC-V prennent en charge cette séquence.

La lecture et addition ajoute une quantité de manière atomique et renvoie l’ancienne valeur. C11 la fournit sous la forme atomic_fetch_add ; x86 fournit lock xadd. Le retour de l’ancienne valeur est utile pour distribuer des numéros de tickets uniques.

Le C garantit le comportement atomique des opérations de sa bibliothèque atomique. Il n’exige pas que chaque type atomique soit sans verrou ; certaines opérations utilisent un verrou interne de bibliothèque. atomic_flag bénéficie de la garantie sans verrou, et atomic_is_lock_free vérifie les autres objets.

Correct ne signifie pas équitable ou rapide

Un verrou fondé sur le test et positionnement assure l’exclusion mutuelle, mais pas l’ordre d’arrivée : un fil peut perdre à répétition la course après une libération et subir une famine. Sur un processeur, quatre fils avec des tranches de 10 ms à tour de rôle peuvent gaspiller 30 ms en attente active pour trois fils en attente avant que le possesseur ayant subi une préemption s’exécute à nouveau. Sur plusieurs cœurs, si le possesseur s’exécute et que les sections sont courtes, une brève attente active peut éviter le surcoût de la mise en sommeil et du réveil.

Un verrou fondé sur le test et positionnement mémorise s’il est détenu, mais pas qui attend. Un verrou à tickets ajoute un ordre d’arrivée à l’aide d’un distributeur atomique de tickets et d’un compteur indiquant le numéro servi.

Prendre un numéro, puis attendre son tour

Les deux compteurs commencent à 0. Chaque appelant incrémente ticket de manière atomique et conserve son ancienne valeur dans mine. Il n’entre que lorsque turn est égal à mine. Le possesseur libère le verrou en augmentant turn d’une unité.

#include <stdatomic.h>

static atomic_uint ticket = 0;
static atomic_uint turn = 0;

void lock(void) {
    unsigned mine = atomic_fetch_add(&ticket, 1);
    while (atomic_load(&turn) != mine) { }
}

void unlock(void) {
    atomic_fetch_add(&turn, 1);
}

Ces opérations atomiques C11 par défaut assurent à la fois l’atomicité et un ordre à cohérence séquentielle. Chaque appelant conserve mine dans sa propre variable locale. Le compteur partagé de tickets distribue des numéros uniques parmi les tickets en cours.

Suivre trois arrivées

A prend le ticket 0 et entre car turn vaut 0. B prend le ticket 1 et attend. C prend le ticket 2 et attend. Le prochain ticket inutilisé est maintenant 3, tandis que le tour courant est toujours 0.

Lorsque A libère le verrou, turn devient 1, donc B entre. C attend toujours le tour 2. La libération par B fait passer turn à 2 et C entre. Un fil nouvellement arrivé reçoit le ticket 3 et ne peut pas passer devant C.

Cette distinction compte lors d’un suivi : ticket indique le prochain numéro à distribuer ; turn indique le numéro servi. Prendre un ticket ne modifie que le distributeur. La libération fait avancer le service.

Ce que garantit l’équité

Un appelant attend derrière les fils ayant des tickets antérieurs. Si chaque détenteur finit par libérer le verrou et que les fils devant lui peuvent s’exécuter, les arrivants ultérieurs ne peuvent pas le dépasser. Le nombre de sections critiques concurrentes devant lui est borné par les tickets antérieurs encore en cours. Cela assure une attente bornée et empêche la famine sous ces conditions de progression.

La garantie concerne l’ordre d’entrée, pas le temps écoulé. Un détenteur qui reste bloqué longtemps peut aussi faire attendre longtemps tous les appelants suivants. Un numéro de ticket ne peut pas obliger l’ordonnanceur à exécuter son détenteur.

Les coûts qui subsistent avec l’ordre des tickets

Chaque fil en attente utilise toujours l’attente active. Si le fil dont le tour arrive ensuite n’est pas ordonnancé, les fils suivants prêts à s’exécuter attendent même si aucun fil n’occupe actuellement la section critique. C’est un coût d’ordonnancement dû à l’ordre strict.

Les fils en attente lisent aussi un même emplacement partagé turn. Chaque libération modifie la ligne de cache qu’ils surveillent tous, ce qui produit du trafic entre les cœurs. Les verrous à attente active fondés sur une file réduisent ce trafic en permettant à chaque fil de surveiller un emplacement local distinct ; Linux est passé des verrous à tickets à des conceptions fondées sur une file.

Les compteurs de tickets réels utilisent l’arithmétique non signée. Les tests d’égalité peuvent fonctionner malgré le rebouclage lorsque le nombre de tickets en cours reste inférieur au nombre de valeurs possibles du compteur. Réutiliser un numéro alors qu’un ticket antérieur de même numéro est encore en cours détruirait l’unicité et l’exclusion.

Un verrou correct peut gaspiller la majeure partie du temps d’un processeur en attente. La bonne stratégie dépend de la possibilité pour le possesseur de s’exécuter et de la durée pendant laquelle il détiendra le verrou.

Céder le processeur fait passer son tour

Un fil en attente peut appeler yield() après une tentative de prise de possession échouée. La cession le fait passer de l’état en cours d’exécution à l’état prêt afin que l’ordonnanceur puisse choisir un autre fil. Il reste prêt à s’exécuter : il peut donc être rapidement choisi et échouer à nouveau. Avec 100 fils sur un processeur, jusqu’à 99 fils en attente peuvent chacun s’exécuter et céder le processeur avant qu’un possesseur ayant subi une préemption obtienne un nouveau tour. La cession réduit l’attente active, mais ne garantit pas un ordre d’entrée équitable.

Le blocage retire le fil des tâches prêtes à s’exécuter

Un verrou avec mise en sommeil place un appelant qui n’a pas réussi à l’acquérir dans une file d’attente. Celui-ci ne consomme pas de temps processeur pendant qu’il est bloqué. Le déverrouillage réveille un fil en attente afin qu’il puisse s’exécuter à nouveau. Un petit verrou de garde interne à attente active peut protéger l’indicateur et la file ; il n’est détenu que pendant de brèves opérations de gestion.

Séparer « décider de dormir » de « dormir effectivement » crée un risque de réveil perdu :

1. Un fil en attente se place dans la file et libère le verrou de garde.
2. Il est interrompu avant d’appeler park().
3. Le possesseur libère le verrou et appelle unpark() pour ce fil.
4. Si ce réveil est ignoré, le fil se met ensuite en sommeil alors que personne ne peut plus le réveiller.

L’appel setpark() de Solaris annonce l’intention de dormir. Un appel de réveil intervenant entre-temps fait alors revenir immédiatement l’appel de mise en sommeil ultérieur. Le protocole relie la décision au blocage effectif.

Linux utilise une comparaison et un blocage atomiques

Un futex combine un mot en mémoire utilisateur et une prise en charge de l’attente par le noyau. futex_wait(addr, expected) ne bloque que si le mot est toujours égal à la valeur attendue ; la vérification et la décision de blocage sont atomiques vis-à-vis des opérations sur ce mot futex. Si un déverrouillage l’a déjà modifié, l’appelant ne se met pas en sommeil sur la base de la valeur attendue périmée.

futex_wake(addr, n) réveille jusqu’à n fils en attente. Un verrou sans contention peut être acquis et libéré avec des instructions atomiques en espace utilisateur, sans appel système. Les mutex pthread de glibc sous Linux utilisent les futex pour les attentes avec contention. Un réveil rend un fil prêt à s’exécuter ; son protocole de verrouillage doit encore établir sa possession avant qu’il accède aux données protégées.

Attendre activement un instant, puis dormir

Un verrou à deux phases attend d’abord activement pendant un court moment, puis bloque si l’attente se prolonge. L’attente active peut être utile lorsque le possesseur s’exécute sur un autre cœur et que l’attente prévue est plus courte que la mise en sommeil suivie du réveil. Le blocage est préférable pour les longues attentes ou lorsque les fils prêts à s’exécuter sont plus nombreux que les cœurs. Sur un processeur, un fil en attente active ne peut pas aider un possesseur non ordonnancé à finir.

La priorité d’ordonnancement peut empêcher la progression

Dans une inversion de priorité, un fil de priorité élevée attend un mutex détenu par un fil de faible priorité, tandis que des tâches de priorité moyenne empêchent le possesseur d’accéder au processeur. Mettre en sommeil le fil de priorité élevée évite l’attente active, mais ne supprime pas ce délai d’ordonnancement.

L’héritage de priorité élève temporairement la priorité du possesseur à celle du fil en attente le plus prioritaire, lui permettant de finir et de libérer le verrou. Le Mars Pathfinder de la NASA a subi des redémarrages dus à une inversion de priorité en 1997 ; l’activation de l’héritage de priorité du mutex a corrigé le problème. Un fil de priorité élevée en attente active sur un processeur unique avec un ordonnancement strict par priorité peut avoir un effet pire : il peut empêcher complètement le possesseur de faible priorité de s’exécuter.

Un compteur partagé est facile à protéger avec un seul mutex. Ses opérations increment, decrement et get acquièrent chacune le même verrou, agissent et le libèrent. Il est exact, mais toutes les mises à jour passent par un seul point partagé.

Pourquoi le compteur exact devient un goulot d’étranglement

Sur plusieurs cœurs, un mutex sérialise les opérations sur le compteur. Les cœurs transfèrent aussi la possession des lignes de cache du verrou et du compteur. Ajouter des travailleurs peut augmenter l’attente plus vite que le travail utile. Remplacer le mutex par atomic_fetch_add supprime le surcoût explicite du verrou sur les processeurs courants, mais chaque mise à jour écrit toujours au même emplacement partagé.

Un compteur approché répartit les mises à jour entre des compteurs locaux et les transfère par lots vers un compteur global. La valeur globale qu’il indique omet délibérément les incréments locaux récents.

Construire la mise à jour du local vers le global

Conserve un compteur et un mutex par cœur, un compteur global avec son propre mutex et un seuil S. Pour chaque incrément :

1. Choisis l’emplacement local pour cette mise à jour et acquiers son mutex.
2. Ajoute 1 au décompte local.
3. S’il atteint S, acquiers le mutex global tout en détenant encore le mutex local.
4. Ajoute ce décompte local au décompte global, remets le décompte local à 0 et libère le mutex global.
5. Libère le mutex local.

Garde le même emplacement pendant toute la mise à jour. Les fils qui utilisent des emplacements différents touchent généralement des verrous différents et n’acquièrent le mutex global que lors d’un transfert. La lecture du décompte global suit aussi sa règle de verrouillage.

Suivre un transfert par lot

Avec quatre cœurs et S égal à 5, supposons que leurs totaux de mises à jour soient 7, 3, 4 et 0. Le cœur 1 transfère 5 à son cinquième incrément et conserve ensuite 2 incréments locaux. Les décomptes locaux finaux sont 2, 3, 4 et 0. Le décompte global est de 5 et le total réel de 14 : neuf incréments restent locaux.

Après des mises à jour achevées par incréments unitaires, chaque décompte local est compris entre 0 et S − 1. Avec P cœurs, le retard du total global peut atteindre au plus :

Pour quatre cœurs et S égal à 5, la borne est de 16. Cette borne concerne les mises à jour achevées et les décomptes locaux restants ; ne l’applique pas au milieu d’un transfert.

Choisir le seuil selon le travail

Un seuil plus petit rend la valeur plus actuelle, mais nécessite davantage d’acquisitions du verrou global. Avec S égal à 1, chaque incrément est transféré au niveau global, ce qui ajoute le surcoût du verrou local sans éviter le goulot d’étranglement global. Un seuil plus grand améliore le passage à l’échelle des mises à jour, mais augmente le retard possible. Dans une expérience publiée, S égal à 1024 a permis à quatre fils d’effectuer quatre millions de mises à jour presque dans le temps nécessaire à un fil pour en effectuer un million.

Un instantané exact doit détenir tous les mutex locaux dans un ordre fixe, puis le mutex global avant d’additionner les décomptes. Cet ordre est cohérent avec les mises à jour qui prennent un verrou local avant le verrou global. L’instantané arrête les transferts concurrents pendant la lecture ; lire chaque champ séparément pourrait compter un transfert deux fois ou le manquer.

Les compteurs approchés conviennent aux statistiques qui tolèrent une visibilité différée. Un compteur de références qui détermine quand la mémoire peut être libérée nécessite une méthode exacte : un décompte sous-estimé pourrait libérer un objet encore utilisé.

Une liste chaînée partagée doit préserver à la fois ses liens et la durée de vie de ses nœuds. Un mutex autour de chaque opération constitue une première conception utile, car chaque parcours et chaque modification partagés suivent une seule règle.

Comment deux insertions perdent un nœud

Supposons que la liste commence à A. T1 prépare le nœud X et T2 prépare le nœud Y. Sans verrou partagé, tous deux peuvent lire head == A, affecter A au champ next de leur nouveau nœud, puis stocker leur propre nœud dans head. La dernière affectation de la tête masque le premier nœud inséré. Ce nœud devient inaccessible : une insertion est perdue et sa mémoire fuit.

La séquence protégée doit comprendre la lecture de la tête actuelle, la définition du nouveau lien et la publication de la nouvelle tête. Un verrou placé uniquement autour de l’affectation finale permettrait aux deux fils de construire leurs liens à partir de la même tête périmée.

Préparer les données privées avant d’acquérir le verrou

Un nouveau nœud reste privé jusqu’à son chaînage dans la liste partagée. L’allocation et l’initialisation de la clé peuvent avoir lieu avant l’acquisition. Avec la fonction auxiliaire qui vérifie les appels pthread, présentée plus tôt, l’insertion peut s’écrire :

int insert(list_t *list, int key) {
    node_t *node = malloc(sizeof(*node));
    if (node == NULL) return -1;
    node->key = key;

    check(pthread_mutex_lock(&list->lock));
    node->next = list->head;
    list->head = node;
    check(pthread_mutex_unlock(&list->lock));
    return 0;
}

Un échec d’allocation provoque un retour avant qu’un mutex soit détenu. La section partagée reste courte, tandis que la vérification de head et la mise à jour du lien restent ensemble. Une allocation sûre vis-à-vis des fils ne rend pas la liste elle-même sûre : ses liens ont toujours besoin de leur propre protection.

Les lecteurs respectent la même règle

Une recherche prend le mutex de la liste avant de lire head et le conserve pendant le parcours. Cela la coordonne avec l’insertion et la suppression. Définis une variable de résultat avant la boucle, mets-la à jour en cas de correspondance et sors de la boucle vers un point de déverrouillage unique avant le retour. Sinon, un retour anticipé en cas de succès dans la boucle verrouillée nécessiterait sa propre libération.

Dans cette conception, la suppression détient le même mutex pendant qu’elle retire un nœud de la chaîne. Les autres parcours ne peuvent pas se trouver dans ce nœud, car ils ont aussi besoin du mutex. Ne le libère que lorsqu’aucune autre opération ne peut encore y accéder. Si une API permet à un appelant de conserver un pointeur vers un nœud après le déverrouillage, cette utilisation supplémentaire nécessite sa propre règle de durée de vie ; le verrou de la liste ne la couvre plus à lui seul.

Déterminer si les verrous par nœud sont avantageux

Le verrouillage par couplage acquiert le verrou du nœud suivant avant de libérer celui du nœud courant. Ce chevauchement préserve un chemin protégé pendant la progression du parcours. Plusieurs opérations peuvent alors occuper différentes zones de la liste.

La concurrence supplémentaire a un prix : chaque nœud visité ajoute des opérations de verrouillage et de déverrouillage, même lorsqu’aucun autre fil n’est à proximité. Une charge comportant beaucoup de parcours peut devenir plus lente que la version à mutex unique. Verrouiller des groupes de nœuds est une solution intermédiaire. Compare la conception plus compliquée à la conception simple sous la charge réelle, recherches infructueuses et chemins de suppression compris.

Un mutex par structure constitue un bon point de départ, mais il peut sérialiser des opérations qui touchent des zones différentes. Deux améliorations utiles consistent à utiliser un verrou par extrémité de file et un verrou par alvéole de hachage.

Garder une sentinelle en tête de file

Une file à deux verrous commence avec un nœud sentinelle D et head == tail == D. D ne contient aucun élément courant de la file. Le premier élément réel, s’il existe, se trouve à head->next. Un mutex de tête sérialise les retraits ; un mutex de queue sérialise les ajouts. Un ajout et un retrait peuvent donc progresser ensemble.

L’ajout prépare de manière privée la valeur d’un nouveau nœud et son lien suivant nul. Sous le mutex de queue, il publie ce nœud par le champ next de l’ancienne queue et déplace tail vers le nouveau nœud. Le retrait utilise le mutex de tête pour lire le lien suivant de l’ancienne sentinelle. S’il est nul, il déverrouille et indique que la file est vide. Sinon, il copie la première valeur réelle, déplace head vers ce nœud, déverrouille et libère l’ancienne sentinelle.

Le nœud qui contenait la valeur renvoyée devient la sentinelle suivante. Le libérer immédiatement laisserait head pendant.

Suivre le déplacement de la sentinelle

Pars de D. L’ajout de 5 crée N5 et établit le lien D -> N5, avec tail == N5. L’ajout de 8 ajoute N8, ce qui produit D -> N5 -> N8. Un retrait renvoie 5, déplace head vers N5 et libère D. N5 est maintenant la sentinelle ; seule la valeur 8 reste dans la file. Après un autre retrait, N8 devient la sentinelle et la file est vide.

Les deux extrémités partagent toujours un lien

Lorsque la file est vide, l’ajout peut écrire le champ next de la sentinelle courante pendant que le retrait le lit sous un autre mutex. Les deux mutex seuls ne synchronisent pas ces accès. En C11, déclare next comme pointeur atomique et publie-le et charge-le avec un ordre approprié ; les stockages et chargements atomiques à cohérence séquentielle par défaut suffisent. La publication doit rendre visible la valeur préparée du nœud avant que le retrait ne la lise.

Attendre un élément nécessite un mécanisme de signalement en plus du verrouillage.

Hacher la clé, puis verrouiller l’alvéole

Une table de hachage de taille fixe peut utiliser une liste sûre vis-à-vis des fils dans chaque alvéole, chacune avec son propre mutex. Avec 101 alvéoles et bucket = key % 101, les clés 7 et 50 utilisent des verrous différents. Les clés 7 et 108 sont toutes deux associées à l’alvéole 7 et doivent y être sérialisées. Les collisions influent sur la contention autant que sur la longueur des recherches.

Tous les accès à la liste d’une alvéole suivent la règle de verrouillage de cette alvéole, y compris les lectures. Le redimensionnement modifie la correspondance avec les alvéoles et déplace les entrées ; cette conception simple nécessite donc un accès exclusif à toute la table pendant le redimensionnement. Un mutex d’alvéole seul ne peut pas protéger une modification qui touche toutes les alvéoles.

Affiner seulement après avoir trouvé le goulot d’étranglement

Commence par une carte de l’état partagé : quels champs sont partagés, quel mutex ou quelle opération atomique protège chacun et quand les nœuds deviennent accessibles ou peuvent être libérés. Vérifie chaque retour et chaque chemin d’échec d’allocation. Raisonne sur les entrelacements, teste sous charge avec un détecteur de courses et mesure la contention avant d’ajouter des verrous plus fins.