Structures de données sans verrouillage : guide complet avec exemples en C++, Java et .NET

Un mutex est simple d'utilisation : on le verrouille, on modifie l'état partagé, puis on le déverrouille. Chaque thread souhaitant y accéder attend son tour. Le problème réside dans cette attente : avec un grand nombre de cœurs et un débit élevé, cette sérialisation devient un facteur limitant. Un thread détenant un verrou peut être préempté, immobilisant ainsi tous les autres threads. L'inversion de priorité peut entraîner le blocage de threads prioritaires par des threads de faible priorité. Dans les systèmes traitant des millions d'opérations par seconde sur des dizaines de cœurs, la contention des mutex ne se contente pas de ralentir le système ; elle anéantit le débit.

Les structures de données sans verrou remplacent l'exclusion mutuelle par des opérations atomiques. Au lieu d'empêcher les conflits, elles les tolèrent et s'en remettent. Un thread qui échoue lors d'une comparaison et d'un échange réessaie avec un état mis à jour. Aucun thread ne bloque jamais un autre. Au moins un thread progresse toujours. Il en résulte un débit considérablement amélioré en cas de forte contention, une latence prévisible sans effets de convoi, et l'élimination des interblocages et des inversions de priorité dès la conception. Le prix à payer est la complexité d'implémentation : le problème ABA, les risques de récupération de mémoire, le faux partage et les exigences subtiles d'ordonnancement de la mémoire sont autant de pièges qui n'existent pas dans le code basé sur les verrous. Cet article les aborde tous avec des exemples de code concrets.

Verrouillage sans interruption vs verrouillage sans attente vs mutex : lequel utiliser ?

Avant de choisir une approche d'implémentation, il convient de se demander de quelle garantie de progression le système a réellement besoin. Les trois modèles diffèrent par ce qu'ils promettent lorsque des threads s'affrontent.

Modèle	Garantie de progrès	Latence typique	Complexité	Idéal pour
Verrouillage par mutex / à base de verrou	Blocage, les threads attendent	Imprévisible en situation de conflit	Low	État partagé à faible contention, exigences de correction simples
Sans serrure	À l'échelle du système, au moins un thread progresse.	Faible sous-contestation	Haute	Files d'attente à haut débit, piles, compteurs
Sans attente	Chaque thread se termine en étapes délimitées.	Cas le plus défavorable limité	Très élevé	Systèmes temps réel, critiques pour la sécurité, SLA stricts en matière de latence
Sans obstruction	Progression en solo, uniquement lorsqu'elle n'est pas contestée	Bas sans contestation	Moyenne	Prototypes de mémoire transactionnelle, contextes de recherche

Sans serrure Il s'agit du comportement par défaut pour les systèmes de production à forte concurrence. La file d'attente Michael-Scott, la pile Treiber et la plupart des tampons circulaires MPMC de production sont sans verrou. En cas de contention extrême, certains threads peuvent être bloqués, mais le système dans son ensemble continue de fonctionner.

Sans attente Garantit une progression bornée par thread, mais exige des algorithmes nettement plus complexes. Des constructions universelles existent, mais engendrent une surcharge importante. Les algorithmes sans attente conviennent aux contextes temps réel critiques où la latence limite est plus importante que le débit moyen.

Sans obstruction Elle est rarement utilisée directement en production. Elle apparaît dans certaines implémentations de mémoire transactionnelle et sert d'étape intermédiaire pour prouver la correction des algorithmes.

Pour la plupart des systèmes à forte concurrence : utilisez un mutex lorsque la contention est faible et que la correction est simple, utilisez une solution sans verrou lorsque le débit en cas de contention est important, utilisez une solution sans attente uniquement lorsque la latence par thread dans le pire des cas est une exigence absolue.

Qu'est-ce qu'une structure de données sans verrou ?

Une structure de données est sans serrure Un algorithme sans verrou garantit qu'au moins un thread parmi tous ceux qui l'exécutent terminera son opération en un nombre fini d'étapes, indépendamment de l'activité des autres threads ou de leur ordonnancement. Cette définition formelle a une conséquence précise : aucun algorithme sans verrou ne peut provoquer d'interblocage. Si un thread est arrêté, suspendu ou s'exécute lentement, les autres threads continuent de progresser.

Le mécanisme repose sur les opérations atomiques, des instructions du processeur qui s'exécutent comme une seule unité indivisible. La primitive universelle est Comparer et échanger (CAS):

CAS(location, expected, new_value):
  if *location == expected:
    *location = new_value
    return true
  else:
    return false  // someone else changed it first

CAS est atomique au niveau matériel. Sur x86, c'est le CMPXCHG instruction. Sur ARM, elle est implémentée via LDXR/STXR (chargement exclusif/stockage exclusif), qui correspond à la variante LL/SC (chargement lié/stockage conditionnel). Un thread lit une valeur, en calcule une nouvelle et utilise CAS pour l'installer uniquement si personne ne l'a modifiée entre-temps. En cas d'échec de CAS, le thread réessaie avec la nouvelle valeur.

En C++11 et versions ultérieures, cela est exposé via std::atomic:

cpp

#include <atomic>

// Atomic increment using CAS loop
void atomic_add(std::atomic<int>& counter, int delta) {
    int expected = counter.load(std::memory_order_relaxed);
    while (!counter.compare_exchange_weak(
        expected,
        expected + delta,
        std::memory_order_release,
        std::memory_order_relaxed))
    {
        // expected is updated on failure -- retry with fresh value
    }
}

compare_exchange_weak est la primitive CAS. En cas d'échec, elle se met à jour. expected à la valeur actuelle automatiquement, rendant la boucle de nouvelle tentative idiomatique.

Le problème de l'ABA : le piège le plus dangereux du sans-verrouillage

Le problème ABA est le risque de correction le plus contre-intuitif en programmation sans verrouillage. CAS vérifie si une adresse mémoire contient toujours la valeur attendue avant d'en installer une nouvelle. Il ne peut pas détecter si cette valeur a été modifiée puis rétablie entre la lecture et l'exécution de CAS. L'adresse mémoire semble toujours contenir la valeur d'origine, mais l'état sous-jacent du système a changé de manière imperceptible pour CAS.

Le scénario étape par étape

Considérons une pile sans verrou utilisant un seul pointeur. top:

1. Le fil A lit top = Node1Le prochain pointeur de Node1 est Node2.
2. Le thread A est interrompu avant la fin de son traitement.
3. Le thread B supprime Node1 (top devient Node2), puis supprime Node2 (top devient null).
4. Le thread B insère un nouveau nœud, qui se trouve être alloué à la même adresse mémoire que Node1 (cas fréquent avec les allocateurs à liste libre). Top = Node1 (même pointeur, contenu différent).
5. Le thread A reprend. Son CAS voit top == Node1 (valeur attendue), réussit et définit top = Node2mais Node2 était déjà libéré. ​​Catastrophe.

Le problème ABA se manifeste différemment dans chaque structure de données :

• StackCAS réussit, mais installe un pointeur suivant obsolète, provoquant une utilisation de mémoire après libération.
• QueueL'indicateur de tête ou de queue semble inchangé, mais sa structure a changé.
• Liste chaînéeUn nœud semble toujours être en place, mais il a été supprimé et réalloué.

La méthode LL/SC permet-elle d'éviter le problème de l'ABA ?

Oui, LL/SC (Load-Linked/Store-Conditional) fournit plus efficacement La sémantique est plus simple que celle de CAS et évite naturellement ABA. LL marque l'adresse mémoire chargée comme « liée ». SC sur la même adresse échoue si une écriture a eu lieu à cette adresse depuis LL, même si la valeur a été restaurée à son état initial. L'historique des modifications est suivi au niveau matériel, et non seulement la valeur actuelle.

Cependant, les implémentations LL/SC sur du matériel réel présentent des limitations pratiques. Sur ARM et POWER, des défaillances LL/SC intempestives peuvent survenir même sans contention (changements de contexte, évictions de cache). Le code doit gérer les boucles de nouvelle tentative, même en l'absence de conflits réels. Sur x86, LL/SC n'est pas implémenté nativement ; CAS constitue la primitive matérielle. Pour le code x86, l'ABA doit être empêchée par logiciel.

Améliorer l'ABA : trois approches

1. Compteurs de version (pointeurs étiquetés)

Intégrez un compteur de version dans le même mot atomique que le pointeur. Chaque opération CAS réussie incrémente ce compteur. Même si le pointeur retrouve sa valeur initiale, le compteur reste différent.

cpp

#include <atomic>
#include <cstdint>

struct TaggedPtr {
    uintptr_t ptr : 48;  // pointer (48-bit virtual address space)
    uintptr_t tag : 16;  // version counter
};

std::atomic<TaggedPtr> top;

bool cas_with_tag(std::atomic<TaggedPtr>& loc,
                  TaggedPtr expected,
                  void* new_ptr) {
    TaggedPtr desired = { (uintptr_t)new_ptr, expected.tag + 1 };
    return loc.compare_exchange_strong(expected, desired);
}

Il s'agit de l'approche standard en pratique. L'étiquette 16 bits est réinitialisée après 65 536 opérations, ce qui est théoriquement dangereux mais acceptable en pratique pour la plupart des systèmes ; il est extrêmement improbable qu'un thread soit préempté pendant exactement 65 536 cycles CAS au même emplacement.

2. Indicateurs de danger

Chaque thread conserve un petit ensemble de « pointeurs de risque », pointant vers les nœuds auxquels il accède actuellement. Avant de libérer un nœud, un thread vérifie tous les registres de pointeurs de risque pour s'assurer qu'aucun autre thread n'y accède. Un nœud figurant dans un pointeur de risque est différé jusqu'à ce que ce pointeur soit effacé.

cpp

// Simplified hazard pointer pattern
thread_local void* hazard_ptr = nullptr;

void* safe_load(std::atomic<void*>& head) {
    void* ptr;
    do {
        ptr = head.load(std::memory_order_acquire);
        hazard_ptr = ptr;                          // announce we are using this
        // memory fence ensures announcement is visible before validation
        std::atomic_thread_fence(std::memory_order_seq_cst);
    } while (ptr != head.load(std::memory_order_acquire)); // validate still valid
    return ptr;
}

void safe_release() {
    hazard_ptr = nullptr;
}

Les pointeurs de risque empêchent l'analyse comportementale appliquée (ABA) lors de la récupération de la mémoire : un nœud ne peut être réutilisé tant qu'un thread détient un pointeur de risque le concernant. Cela nécessite l'analyse de tous les pointeurs de risque des threads avant leur libération, ce qui engendre une surcharge proportionnelle au nombre de threads.

3. Récupération basée sur les époques (EBR)

Les threads fonctionnent par « époques » suivies globalement. Les nœuds arrêtés sont mis en mémoire tampon pour chaque époque et ne sont libérés que lorsque tous les threads ont dépassé l'époque au cours de laquelle le nœud a été arrêté. EBR est plus simple à utiliser que les pointeurs de risque et présente une surcharge par opération plus faible, au prix d'une croissance de la mémoire limitée mais imprévisible pendant les périodes d'inactivité.

En Java, AtomicStampedReference résout directement le problème ABA en associant une référence à un timbre numérique :

Java

import java.util.concurrent.atomic.AtomicStampedReference;

AtomicStampedReference<Node> top =
    new AtomicStampedReference<>(null, 0);

void push(Node newNode) {
    int[] stamp = new int[1];
    Node current;
    do {
        current = top.get(stamp);
        newNode.next = current;
    } while (!top.compareAndSet(current, newNode, stamp[0], stamp[0] + 1));
}

Implémentations de files d'attente sans verrou

Les files d'attente sont la structure sans verrou la plus couramment utilisée. La file d'attente sans verrou de référence est la file d'attente de Michael-Scott, qui utilise deux pointeurs (tête et queue) et un nœud sentinelle pour permettre des opérations d'enfilement et de défilement simultanées.

File d'attente SPSC : Performances maximales avec une synchronisation minimale

Une file d'attente à producteur unique et consommateur unique élimine toute contention d'écriture et de lecture. Un thread écrit dans la queue ; un autre lit dans la tête. Seul le pointeur vers la tête est partagé entre le producteur et le consommateur.

cpp

#include <atomic>
#include <array>

template<typename T, size_t Capacity>
class SPSCQueue {
    std::array<T, Capacity> buffer;
    alignas(64) std::atomic<size_t> head{0}; // consumer reads head
    alignas(64) std::atomic<size_t> tail{0}; // producer writes tail
    // alignas(64) puts each on a separate cache line -- prevents false sharing

public:
    bool push(const T& item) {
        size_t t = tail.load(std::memory_order_relaxed);
        size_t next = (t + 1) % Capacity;
        if (next == head.load(std::memory_order_acquire))
            return false; // full
        buffer[t] = item;
        tail.store(next, std::memory_order_release);
        return true;
    }

    bool pop(T& item) {
        size_t h = head.load(std::memory_order_relaxed);
        if (h == tail.load(std::memory_order_acquire))
            return false; // empty
        item = buffer[h];
        head.store((h + 1) % Capacity, std::memory_order_release);
        return true;
    }
};

Le alignas(64) La présence de données en tête et en queue de cache est cruciale. Sans cela, les deux parties tiennent sur la même ligne de cache. Chaque écriture en queue de cache provoque une invalidation de la ligne de cache visible par le cœur de lecture, et inversement, un partage erroné qui sérialise des opérations qui devraient être indépendantes.

File d'attente MPMC : multi-producteur multi-consommateur

Une file d'attente MPMC entièrement concurrente est nettement plus complexe. Les implémentations en production utilisent un numéro de séquence par emplacement pour coordonner les producteurs et les consommateurs sans verrouillage :

cpp

#include <atomic>
#include <array>

template<typename T, size_t Capacity>
class MPMCQueue {
    struct Slot {
        std::atomic<size_t> sequence;
        T data;
    };

    alignas(64) std::array<Slot, Capacity> slots;
    alignas(64) std::atomic<size_t> enqueue_pos{0};
    alignas(64) std::atomic<size_t> dequeue_pos{0};

public:
    MPMCQueue() {
        for (size_t i = 0; i < Capacity; ++i)
            slots[i].sequence.store(i, std::memory_order_relaxed);
    }

    bool push(const T& item) {
        size_t pos = enqueue_pos.fetch_add(1, std::memory_order_relaxed);
        Slot& slot = slots[pos % Capacity];
        size_t seq = slot.sequence.load(std::memory_order_acquire);
        // wait for the slot to be ready for writing
        while (seq != pos) {
            seq = slot.sequence.load(std::memory_order_acquire);
        }
        slot.data = item;
        slot.sequence.store(pos + 1, std::memory_order_release);
        return true;
    }

    bool pop(T& item) {
        size_t pos = dequeue_pos.fetch_add(1, std::memory_order_relaxed);
        Slot& slot = slots[pos % Capacity];
        size_t seq = slot.sequence.load(std::memory_order_acquire);
        while (seq != pos + 1) {
            seq = slot.sequence.load(std::memory_order_acquire);
        }
        item = slot.data;
        slot.sequence.store(pos + Capacity, std::memory_order_release);
        return true;
    }
};

.NET ConcurrentQueue : Fonctionnement interne

.NET ConcurrentQueue<T> Dans .NET 5+, une structure de tableau segmenté est utilisée. Chaque segment est un tableau de taille fixe avec un index de tête et de queue géré par Interlocked opérations (qui correspondent à CAS sur le matériel sous-jacent). Les segments sont liés via un flux volatil _nextSegment La méthode `enqueue` ajoute un élément au segment de queue courant, allongeant la chaîne de segments lorsqu'elle est pleine. La méthode `dequeue` lit le segment de tête et incrémente l'index de tête de manière atomique.

La décision de conception clé consiste à éviter un verrouillage global. Les producteurs ne sont en concurrence que sur l'indice de queue du segment actuel. Les consommateurs ne sont en concurrence que sur l'indice de tête. Aucun producteur n'est jamais en concurrence directe avec un consommateur. Cela rend ConcurrentQueue<T> très efficace pour les chaînes de valeur entre producteurs et consommateurs :

tranchant

using System.Collections.Concurrent;
using System.Threading;

// .NET ConcurrentQueue -- lock-free, thread-safe, FIFO
var queue = new ConcurrentQueue<int>();

// Producer thread
var producer = Task.Run(() => {
    for (int i = 0; i < 1_000_000; i++)
        queue.Enqueue(i);
});

// Consumer thread
var consumer = Task.Run(() => {
    long sum = 0;
    while (!queue.IsEmpty || !producer.IsCompleted) {
        if (queue.TryDequeue(out int item))
            sum += item;
        else
            Thread.SpinWait(1);  // brief spin before retry
    }
    return sum;
});

await Task.WhenAll(producer, consumer);

Cohérence du cache et faux partage dans le code sans verrou

La cohérence du cache est une variable de performance invisible dans les implémentations sans verrouillage. Lorsqu'un cœur écrit à une adresse mémoire, la ligne de cache de 64 octets contenant cette adresse est invalidée dans les caches de tous les autres cœurs. Ces derniers doivent récupérer la ligne mise à jour avant de pouvoir lire. Dans un code sans verrouillage avec des mises à jour atomiques fréquentes, cette invalidation de ligne de cache peut devenir le coût prépondérant.

Faux partage Cela se produit lorsque deux threads modifient des variables différentes qui partagent une même ligne de cache. Aucun des deux threads n'accède aux mêmes données, mais le protocole de cohérence du cache considère la ligne de cache entière comme étant partagée.

cpp

// BAD: head and tail on the same cache line
struct BadQueue {
    std::atomic<size_t> head;   // bytes 0-7
    std::atomic<size_t> tail;   // bytes 8-15
    // both fit in the same 64-byte cache line
    // producer writing tail invalidates head in consumer's cache
};

// GOOD: head and tail on separate cache lines
struct GoodQueue {
    alignas(64) std::atomic<size_t> head;
    alignas(64) std::atomic<size_t> tail;
    // each on its own cache line -- no false sharing
};

Le protocole MESI (Modifié, Exclusif, Partagé, Invalide) décrit la gestion des lignes de cache par les processeurs x86. Lorsqu'un cœur souhaite écrire dans une zone partagée avec d'autres cœurs (état Partagé), il doit diffuser une requête d'écriture, attendre l'accusé de réception de tous les cœurs partageant la zone, puis passer à l'état Modifié. Ce trajet aller-retour vers le protocole de cohérence prend entre 50 et plus de 300 cycles sur un système multiprocesseur. Un partage incorrect transforme les opérations locales à chaque thread en trafic de cohérence de cache, ce qui dégrade les performances qui devraient être linéaires avec le nombre de cœurs.

Détection des faux partages: utilisation perf stat -e cache-misses,L1-dcache-load-misses Sous Linux ou via le profileur de performances du processeur de Visual Studio sous Windows, un taux élevé d'échecs de cache L1 dans un programme multithread dont la mémoire tient dans le cache est un indicateur fort de partage erroné.

Ordre de mémoire : pourquoi memory_order_relaxed Cela ne suffit pas toujours

C + + std::atomic Les opérations exposent l'ensemble des possibilités d'ordonnancement de la mémoire du modèle C++11. Choisir un mauvais ordonnancement est le deuxième bogue le plus fréquent dans le code sans verrou, après le problème ABA.

cpp

// The five memory orderings and when each applies:

// relaxed: no synchronization, only atomicity
// Use for: counters where only the final value matters
counter.fetch_add(1, std::memory_order_relaxed);

// acquire: reads see all writes by threads that released this location
// Use for: reading shared state protected by a flag
if (ready.load(std::memory_order_acquire)) {
    use(data); // guaranteed to see all writes made before ready was set
}

// release: writes are visible to threads that acquire this location
// Use for: publishing shared state
data = compute();
ready.store(true, std::memory_order_release);

// acq_rel: acquire + release in one operation
// Use for: read-modify-write operations like CAS in the middle of a chain
node.compare_exchange_strong(expected, desired,
    std::memory_order_acq_rel,   // success
    std::memory_order_acquire);  // failure

// seq_cst: total order across all seq_cst operations, all cores
// Use for: when you need a global consistent view (but slowest)
flag.store(true, std::memory_order_seq_cst);

Une erreur courante : utiliser relaxed pour un indicateur de version. Un thread qui définit ready = true au relaxed La commande ne garantit pas que les écritures précédentes à data sont visibles par d'autres fils de discussion qui lisent readyLe couple acquisition/diffusion crée la relation d'antériorité qui relie l'auteur et le lecteur.

La pile Treiber : pile sans verrou en C++

La pile de Treiber est la structure de données sans verrou la plus simple et non triviale. Elle utilise une boucle CAS sur un seul élément. top aiguille:

cpp

#include <atomic>

template<typename T>
class TreiberStack {
    struct Node {
        T data;
        Node* next;
        explicit Node(T d) : data(std::move(d)), next(nullptr) {}
    };

    std::atomic<Node*> top{nullptr};

public:
    void push(T data) {
        Node* node = new Node(std::move(data));
        node->next = top.load(std::memory_order_relaxed);
        while (!top.compare_exchange_weak(
            node->next,          // expected -- updated on failure
            node,                // desired
            std::memory_order_release,
            std::memory_order_relaxed))
        { /* retry */ }
    }

    bool pop(T& result) {
        Node* node = top.load(std::memory_order_acquire);
        while (node) {
            if (top.compare_exchange_weak(
                node,
                node->next,      // new top
                std::memory_order_acquire,
                std::memory_order_relaxed))
            {
                result = std::move(node->data);
                // WARNING: cannot free node here safely without hazard pointers or EBR
                // delete node; -- ABA hazard if another thread reads node->next
                return true;
            }
        }
        return false; // empty
    }
};

Le commentaire sur delete node Il est crucial de noter que la suppression naïve constitue le risque lié à l'ABA décrit précédemment. Dans une pile Treiber en production, la récupération des nœuds nécessite des pointeurs de risque, une récupération basée sur les époques ou le ramasse-miettes (Java/C# gère cela automatiquement).

Structures de données sans verrou en Java

La bibliothèque standard de Java fournit des implémentations sans verrou de qualité production dans java.util.concurrent:

Classe	Structure	Progression	Remarques
AtomicReference<T>	Valeur unique	Sans serrure	CAS sur la référence d'objet
AtomicStampedReference<T>	Valeur + timbre	Sans serrure	Prévention ABA via compteur de version
ConcurrentLinkedQueue<T>	File d'attente Michael-Scott	Sans serrure	FIFO, illimité
ConcurrentLinkedDeque<T>	Deque sans cadenas	Sans serrure	Les deux extrémités
LongAdder	Counter	Sans serrure	Comptage à haut débit et à bandes

LongAdder Il convient de noter ce point en particulier. Plutôt qu'un unique compteur atomique en concurrence entre tous les threads, il utilise un tableau de compteurs organisé en bandes, chacun étant accessible par un sous-ensemble de threads. La contention est ainsi répartie sur les bandes plutôt que concentrée en un seul point. Le total est calculé de manière différée. sum()Pour les opérations d'incrémentation à haute fréquence sur de nombreux threads, LongAdder surperforme de façon spectaculaire AtomicLong.incrementAndGet():

Java

import java.util.concurrent.atomic.LongAdder;

// BAD for high-concurrency counting: all threads contend on one location
AtomicLong counter = new AtomicLong(0);
counter.incrementAndGet(); // single CAS -- all threads collide

// GOOD for high-concurrency counting: contention distributed across stripes
LongAdder adder = new LongAdder();
adder.increment();  // updates thread-local stripe -- minimal contention
long total = adder.sum(); // sum all stripes lazily

Comment SMART TS XL Soutient le développement de systèmes sans verrouillage

Le code sans verrouillage est parmi les plus difficiles à concevoir correctement. Les bogues sont non déterministes, n'apparaissent que dans certaines configurations d'entrelacement et souvent uniquement en production à grande échelle. L'analyse statique résout ce problème en examinant les propriétés structurelles du code avant son exécution, plutôt que d'attendre l'apparition d'une condition de concurrence.

SMART TS XL Il analyse l'intégralité des chemins d'exécution du code concurrent, en traçant la relation entre les opérations atomiques et les emplacements mémoire qu'elles protègent. Pour les systèmes mêlant code sans verrou, composants hérités ou architectures multilingues, il offre une visibilité transversale impossible à obtenir avec les outils monolingues : comment une zone de mémoire partagée accédée par un composant C++ sans verrou est liée au service Java qui y accède, ou comment une file d'attente concurrente alimente un pipeline de traitement COBOL.

Le analyse de code statique Cette fonctionnalité permet d'identifier les schémas associés aux risques de concurrence : chargements atomiques sans sémantique d'acquisition correspondante, boucles CAS qui ne mettent pas à jour la valeur attendue en cas d'échec, structures de données partagées où les champs accédés par différents threads sont regroupés sans remplissage d'alignement. analyse d’impact La fonctionnalité permet de suivre les composants en aval qui dépendent d'une structure de données concurrente partagée, afin que les modifications apportées à l'interface de la structure ou à la stratégie de récupération puissent être correctement circonscrites avant que la modification ne soit effectuée.

Pour les systèmes d'entreprise où les composants sans verrouillage doivent coexister avec le traitement par lots traditionnel, les intergiciels de mise en file d'attente de messages et les couches de services modernes, SMART TS XL's mappage des dépendances fournit une vue architecturale de la manière dont les chemins de données concurrents connectent les composants écrits dans différents langages sur l'ensemble de la pile système.

Quand l'option sans serrure est une mauvaise décision

L'absence de verrou n'est pas toujours préférable à l'utilisation d'un mutex. Le choix d'une structure sans verrou dépend du profil de contention réel de la charge de travail. Avec un faible nombre de threads ou une faible contention, un mutex bien implémenté est plus rapide car il évite la surcharge liée aux boucles de nouvelle tentative atomiques et à l'invalidation des lignes de cache entre les cœurs.

Utilisez un mutex lorsque :

• Le nombre de fils est faible (inférieur à 4-8) ou les conflits sont peu fréquents.
• La section critique est longue et complexe (les boucles sans verrouillage deviennent coûteuses par rapport à la section).
• La correction est plus importante que le débit et l'algorithme est plus simple avec un verrou
• La plateforme dispose d'un verrouillage efficace basé sur les futex (Linux) pthread_mutex, Windows SRWLOCK)

Utilisez le mode sans verrouillage lorsque :

• Le nombre de threads est élevé et la contention est maintenue.
• Les opérations sont courtes (la surcharge de la boucle CAS est faible par rapport à l'opération).
• Le blocage est inacceptable (threads temps réel, gestionnaires d'interruptions, gestionnaires de signaux).
• Composer avec d'autres structures sans verrou où un verrou introduirait des dépendances d'ordre de verrouillage

Utilisez l'option sans attente lorsque :

• Chaque thread doit s'exécuter dans un délai imparti, indépendamment des autres threads.
• Exigences critiques en temps réel ou de sécurité où la famine est inacceptable
• L'algorithme peut être structuré pour prendre en charge l'exécution en étapes limitées par thread.

La discipline de la programmation sans verrou ne consiste pas à la choisir partout, mais précisément là où ses propriétés – progression non bloquante, élimination des interblocages, tolérance à la préemption – correspondent aux exigences réelles du système.