Sperrfreie Datenstrukturen: Vollständiger Leitfaden mit Beispielen in C++, Java und .NET

Ein Mutex ist einfach aufgebaut. Man sperrt ihn, ändert den gemeinsamen Zustand und entsperrt ihn wieder. Jeder Thread, der darauf zugreifen möchte, muss warten. Das Problem ist dieses Warten: Bei vielen Kernen und hohem Durchsatz stößt die Serialisierung an ihre Grenzen. Ein Thread, der eine Sperre hält, kann unterbrochen werden, wodurch alle anderen Threads im Leerlauf verharren. Prioritätsumkehr kann dazu führen, dass Threads mit niedriger Priorität Threads mit hoher Priorität blockieren. In Systemen, die Millionen von Operationen pro Sekunde auf Dutzenden von Kernen verarbeiten, verlangsamt die Mutex-Konfliktierung nicht nur die Ausführung, sondern lässt den Durchsatz einbrechen.

Sperrfreie Datenstrukturen ersetzen gegenseitigen Ausschluss durch atomare Operationen. Anstatt Konflikte zu verhindern, tolerieren sie diese und können sich davon erholen. Ein Thread, der einen Vergleichs- und Tauschvorgang nicht besteht, versucht es mit aktualisiertem Zustand erneut. Kein Thread blockiert jemals einen anderen. Mindestens ein Thread erzielt stets Fortschritte. Das Ergebnis ist ein deutlich höherer Durchsatz bei hoher Auslastung, vorhersehbare Latenz ohne Konvoieffekte und die Vermeidung von Deadlocks und Prioritätsumkehr. Der Preis dafür ist die höhere Implementierungskomplexität: Das ABA-Problem, Speicherfreigabekonflikte, falsche Speichernutzung und subtile Anforderungen an die Speicherreihenfolge sind allesamt Fallstricke, die in sperrbasiertem Code nicht auftreten. Dieser Artikel behandelt all diese Aspekte anhand konkreter Codebeispiele.

Lock-Free vs Wait-Free vs Mutex: Welche Methode ist die richtige?

Bevor man sich für einen Implementierungsansatz entscheidet, sollte man sich fragen, welche Fortschrittsgarantie das System tatsächlich benötigt. Die drei Modelle unterscheiden sich darin, was sie bei konkurrierenden Threads versprechen.

Modell	Fortschrittsgarantie	Typische Latenz	Komplexität	Am besten geeignet für
Mutex-/Sperrsystem	Blockiert, Threads warten	Unberechenbar im Wettbewerb	Niedrig	Gemeinsamer Zustand mit geringen Konflikten, einfache Korrektheitsanforderungen
Schlossfrei	Systemweit schreitet mindestens ein Thread voran.	Niedrige Konkurrenz	Hoch	Hochdurchsatz-Warteschlangen, Stapel, Zähler
Wartezeitfrei	Jeder Thread wird pro Thread in begrenzten Schritten beendet.	Begrenzter Worst-Case	Sehr hohe	Echtzeitsysteme, sicherheitskritische Systeme, strenge Latenz-SLAs
frei von Hindernissen	Solo-Fortschritt nur, wenn unbedrängt	Niedrig ohne Konkurrenz	Medium	Prototypen des transaktionalen Gedächtnisses, Forschungskontexte

Sperrfreier Betrieb ist der praktische Standard für hochgradig parallele Produktionssysteme. Die Michael-Scott-Warteschlange, der Treiber-Stack und die meisten produktiven MPMC-Ringpuffer arbeiten sperrfrei. Einzelne Threads können bei extremer Auslastung zwar blockiert werden, das System als Ganzes arbeitet jedoch weiter.

Wartezeitfreie Algorithmen garantieren einen begrenzten Fortschritt pro Thread, erfordern aber deutlich komplexere Algorithmen. Universelle Konstruktionen existieren zwar, verursachen jedoch einen hohen Overhead. Wartezeitfreie Algorithmen eignen sich für harte Echtzeitumgebungen, in denen die Latenz am Ende des Threads wichtiger ist als der durchschnittliche Durchsatz.

Obstruktionsfreies Verhalten wird in der Produktion selten direkt eingesetzt. Es findet sich in einigen Implementierungen von Transaktionsspeichern und dient als Zwischenschritt beim Korrektheitsnachweis von Algorithmen.

Für die meisten Systeme mit hoher Parallelität gilt: Verwenden Sie einen Mutex, wenn die Konkurrenz gering ist und die Korrektheit einfach ist; verwenden Sie lockfreies Verhalten, wenn der Durchsatz unter Konkurrenz wichtig ist; verwenden Sie wartefreies Verhalten nur dann, wenn die Latenz pro Thread im ungünstigsten Fall eine zwingende Anforderung ist.

Was ist eine sperrfreie Datenstruktur?

Eine Datenstruktur ist sperrfrei, wenn sie garantiert, dass mindestens ein Thread unter allen darauf operierenden Threads seine Operation in einer endlichen Anzahl von Schritten abschließt, unabhängig davon, was andere Threads tun oder wie sie geplant sind. Diese formale Definition hat eine präzise Konsequenz: Kein sperrfreier Algorithmus kann einen Deadlock verursachen. Wenn ein Thread angehalten, suspendiert oder langsam ausgeführt wird, arbeiten die anderen Threads weiter.

Der Mechanismus besteht aus atomaren Operationen, CPU-Befehlen, die als eine einzige unteilbare Einheit ausgeführt werden. Die universelle Primitive ist Compare-and-Swap (CAS) :

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

CAS ist auf Hardwareebene atomar. Auf x86 ist es das CMPXCHG Befehl. Auf ARM wird er implementiert durch LDXR/STXR (Load-Exclusive/Store-Exclusive), die LL/SC-Variante (Load-Linked/Store-Conditional). Ein Thread liest einen Wert, berechnet einen neuen Wert und verwendet CAS, um diesen nur dann zu installieren, wenn er zwischenzeitlich von keinem anderen Thread geändert wurde. Schlägt CAS fehl, versucht der Thread es mit dem neuen Wert erneut.

In C++11 und späteren Versionen wird dies durch folgende Schritte ermöglicht: 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 ist die CAS-Primitive. Im Fehlerfall wird sie aktualisiert. expected automatisch auf den aktuellen Wert zurücksetzen, wodurch die Wiederholungsschleife idiomatisch wird.

Das ABA-Problem: Die größte Gefahr bei Lock-Free

Das ABA-Problem stellt die kontraintuitivste Korrektheitsgefahr bei sperrfreier Programmierung dar. CAS prüft, ob eine Speicherzelle noch den erwarteten Wert enthält, bevor ein neuer Wert eingefügt wird. Es kann nicht erkennen, ob dieser Wert zwischen dem Lesen und dem CAS-Vorgang geändert und wieder zurückgesetzt wurde. Die Speicherzelle scheint zwar noch den ursprünglichen Wert zu haben, aber der zugrundeliegende Systemzustand hat sich auf für CAS nicht erkennbare Weise verändert.

Das Szenario Schritt für Schritt

Betrachten wir einen sperrenfreien Stack, der einen einzelnen Zeiger verwendet. top:

1. Thread A liest top = Node1Der nächste Zeiger von Knoten 1 ist Knoten 2.
2. Thread A wird unterbrochen, bevor sein Pop-Befehl abgeschlossen ist.
3. Thread B entfernt Knoten 1 (der oberste Knoten wird zu Knoten 2), dann entfernt er Knoten 2 (der oberste Knoten wird zu null).
4. Thread B fügt einen neuen Knoten hinzu, der zufällig an derselben Speicheradresse wie Knoten 1 allokiert ist (häufig bei Freilisten-Allokatoren). Top = Knoten 1 (gleicher Zeiger, anderer Inhalt).
5. Thread A wird fortgesetzt. Sein CAS sieht top == Node1 (Erwartungswert), ist erfolgreich und setzt top = Node2Aber Knoten 2 war bereits freigegeben. Katastrophe.

Das ABA-Problem manifestiert sich in jeder Datenstruktur unterschiedlich:

• StapelnCAS ist zwar erfolgreich, installiert aber einen veralteten Next-Pointer, was zu einem Use-After-Free-Fehler führt.
• WarteschlangeKopf- oder Schwanzzeiger scheinen unverändert, aber seine Struktur hat sich verändert.
• Verknüpfte ListeEin Knoten scheint sich noch an seiner Position zu befinden, wurde aber entfernt und neu zugewiesen.

Vermeidet LL/SC das ABA-Problem?

Ja, LL/SC (Load-Linked/Store-Conditional) bietet eine stärkere Semantik als CAS und vermeidet naturgemäß ABA. LL markiert die geladene Speicheradresse als „verknüpft“. SC schlägt an derselben Adresse fehl, wenn seit dem LL ein Speicherzugriff auf diese Adresse erfolgte, selbst wenn der Wert auf seinen ursprünglichen Zustand zurückgesetzt wurde. Die Änderungshistorie wird auf Hardwareebene protokolliert, nicht nur der aktuelle Wert.

Die Implementierung von LL/SC auf realer Hardware stößt jedoch an praktische Grenzen. Auf ARM- und POWER-Prozessoren können selbst ohne Konflikte (Kontextwechsel, Cache-Verdrängung) unerwartete LL/SC-Fehler auftreten. Der Code muss daher auch ohne tatsächliche Konflikte Wiederholungsschleifen berücksichtigen. Auf x86-Systemen existiert kein natives LL/SC; CAS ist die Hardware-Primitive. Für x86-Code muss ABA softwareseitig verhindert werden.

ABA verbessern: Drei Ansätze

1. Versionszähler (getaggte Zeiger)

Packen Sie einen Versionszähler in dasselbe atomare Wort wie den Zeiger. Jeder erfolgreiche CAS-Aufruf erhöht den Zähler. Selbst wenn ein Zeiger zu seinem ursprünglichen Wert zurückkehrt, ändert sich der Zähler:

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);
}

Dies ist das gängige Vorgehen in der Praxis. Das 16-Bit-Tag wird nach 65,536 Operationen überschrieben, was theoretisch unsicher, aber für die meisten Systeme praktisch ausreichend ist; es ist äußerst unwahrscheinlich, dass ein Thread genau 65,536 CAS-Zyklen lang an derselben Speicheradresse unterbrochen wird.

2. Gefahrenhinweise

Jeder Thread verwaltet eine kleine Menge von „Hazard-Pointern“, Zeigern auf Knoten, auf die er gerade zugreift. Bevor ein Thread einen Knoten freigibt, prüft er alle Hazard-Pointer-Registrierungen, um sicherzustellen, dass kein anderer Thread darauf zugreift. Ein Knoten, der in einem Hazard-Pointer erscheint, wird so lange zurückgestellt, bis dieser Pointer gelöscht wird.

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;
}

Hazard-Pointer verhindern ABA auf Ebene der Speicherfreigabe: Ein Knoten kann nicht wiederverwendet werden, solange ein Thread einen Hazard-Pointer darauf hält. Dies erfordert das Scannen aller Thread-Hazard-Pointer vor der Freigabe, was zu einem mit der Thread-Anzahl proportionalen Overhead führt.

3. Epochenbasierte Sanierung (EBR)

Threads arbeiten in global verwalteten „Epochen“. Ausgemusterte Knoten werden pro Epoche zwischengespeichert und erst freigegeben, wenn alle Threads die Epoche, in der der Knoten ausgemustert wurde, überschritten haben. EBR ist einfacher zu verwenden als Hazard-Pointer und hat einen geringeren Overhead pro Operation, allerdings mit dem Nachteil eines begrenzten, aber unvorhersehbaren Speicherwachstums während Ruhephasen.

In Java AtomicStampedReference Das ABA-Problem wird direkt angegangen, indem eine Referenz mit einem ganzzahligen Stempel kombiniert wird:

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));
}

Implementierungen von sperrfreien Warteschlangen

Warteschlangen sind die am häufigsten benötigte sperrfreie Datenstruktur. Die kanonische sperrfreie Warteschlange ist die Michael-Scott-Warteschlange, die zwei Zeiger (Kopf- und Endzeiger) und einen Wächterknoten verwendet, um gleichzeitige Einfüge- und Entnahmeoperationen zu ermöglichen.

SPSC-Warteschlange: Maximale Leistung bei minimaler Synchronisierung

Eine Warteschlange mit einem Produzenten und einem Konsumenten eliminiert jegliche Schreib- und Lesekonflikte. Ein Thread schreibt in das Ende, ein anderer liest vom Anfang. Nur der Zeiger auf den Anfang wird von Produzent und Konsument gemeinsam genutzt.

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;
    }
};

Das alignas(64) Die Positionierung von Anfang und Ende des Caches ist entscheidend. Ohne diese Positionierung würden beide in dieselbe Cache-Zeile passen. Jeder Schreibvorgang im Ende des Caches löst eine Cache-Zeileninvalidierung aus, die für den lesenden Kern sichtbar ist, und umgekehrt. Dies führt zu einer falschen gemeinsamen Nutzung, die eigentlich unabhängige Operationen serialisiert.

MPMC-Warteschlange: Multi-Produzent, Multi-Consumer

Eine vollständig parallele MPMC-Warteschlange ist deutlich komplexer. Produktionsimplementierungen verwenden eine Sequenznummer pro Zeitschlitz, um Produzenten und Konsumenten ohne Sperre zu koordinieren:

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: Funktionsweise intern

.NET ConcurrentQueue<T> In .NET 5+ wird eine segmentierte Array-Struktur verwendet. Jedes Segment ist ein Array fester Größe mit einem Kopf- und einem Endindex, die verwaltet werden. Interlocked Operationen (die CAS auf der zugrunde liegenden Hardware entsprechen). Segmente sind über einen flüchtigen Wert verknüpft. _nextSegment Der Zeiger wird verwendet. Enqueue fügt Elemente an das aktuelle letzte Segment an und vergrößert die Segmentkette, sobald sie voll ist. Dequeue liest vom ersten Segment und erhöht den Index des ersten Segments atomar.

Die zentrale Designentscheidung besteht darin, eine globale Marktbindung zu vermeiden. Produzenten konkurrieren ausschließlich im Randbereich des aktuellen Segments. Konsumenten konkurrieren ausschließlich im Hauptbereich. Kein Produzent konkurriert jemals direkt mit einem Konsumenten. Dadurch wird Folgendes erreicht: ConcurrentQueue<T> hocheffizient für Produzent-Verbraucher-Pipelines:

scharf

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);

Cache-Kohärenz und False Sharing in sperrfreiem Code

Cache-Kohärenz ist die unsichtbare Leistungsvariable in sperrfreien Implementierungen. Wenn ein Kern in eine Speicheradresse schreibt, wird die gesamte 64 Byte große Cache-Zeile, die diese Adresse enthält, in den Caches aller anderen Kerne ungültig gemacht. Diese müssen die aktualisierte Zeile abrufen, bevor sie lesen können. In sperrfreiem Code mit häufigen atomaren Aktualisierungen kann diese Cache-Zeilen-Ungültigmachung den größten Kostenfaktor darstellen.

Falsche gemeinsame Nutzung tritt auf, wenn zwei Threads unterschiedliche Variablen ändern, die sich zufällig in derselben Cache-Zeile befinden. Keiner der Threads greift auf dieselben Daten zu, aber das Cache-Kohärenzprotokoll behandelt die gesamte Cache-Zeile als umkämpft:

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
};

Das MESI-Protokoll (Modified, Exclusive, Shared, Invalid) beschreibt, wie x86-CPUs die Cache-Zeilenverwaltung koordinieren. Wenn ein Kern in einen Speicherbereich schreiben möchte, den er mit anderen Kernen teilt (Shared-Zustand), muss er eine Schreibanforderung senden, auf die Bestätigung aller anderen Kerne warten und in den Modified-Zustand wechseln. Dieser Roundtrip zum Kohärenzprotokoll benötigt auf einem Multi-Socket-System 50 bis über 300 Zyklen. Falsche gemeinsame Nutzung wandelt unabhängige, threadlokale Operationen in Cache-Kohärenz-Datenverkehr um und führt so zu einem Leistungsabfall, der eigentlich linear mit der Anzahl der Kerne skalieren sollte.

Erkennung von Falschfreigaben: benutzen perf stat -e cache-misses,L1-dcache-load-misses Unter Linux oder mit dem CPU-Leistungsprofiler von Visual Studio unter Windows. Eine hohe Rate an L1-Cache-Fehlern in einem Multithread-Programm, das in den Cache passt, ist ein starker Indikator für False Sharing.

Speicherreihenfolge: Warum memory_order_relaxed Ist nicht immer ausreichend

C + + std::atomic Operationen legen die gesamte Bandbreite der Speicherreihenfolge des C++11-Speichermodells offen. Die Wahl der falschen Reihenfolge ist nach dem ABA-Problem der zweithäufigste Fehler in sperrfreiem Code.

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);

Ein häufiger Fehler: die Verwendung relaxed für ein Release-Flag. Ein Thread, der ein Release-Flag setzt. ready = true und relaxed Die Bestellung garantiert nicht, dass vorhergehende Schreiben an data sind für andere Threads sichtbar, die lesen readyDas Acquire/Release-Paar schafft die "Hat-Before"-Beziehung, die Autor und Leser verbindet.

Der Treiber-Stack: Sperrfreier Stack in C++

Der Treiber-Stack ist die einfachste nicht-triviale sperrfreie Datenstruktur. Er verwendet eine CAS-Schleife auf einem einzelnen top Zeiger:

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
    }
};

Der Kommentar zu delete node ist kritisch: Unüberlegtes Löschen stellt die zuvor beschriebene ABA-Gefahr dar. In einem produktiven Treiber-Stack erfordert die Knotenfreigabe Hazard-Pointer, epochenbasierte Freigabe oder Garbage Collection (Java/C# übernimmt dies automatisch).

Java-Sperrfreie Datenstrukturen

Die Standardbibliothek von Java bietet produktionsreife, sperrfreie Implementierungen in java.util.concurrent:

Klasse	Struktur	Progress	Notizen
AtomicReference<T>	Einzelwert	Schlossfrei	CAS auf Objektverweis
AtomicStampedReference<T>	Wert + Briefmarke	Schlossfrei	ABA-Prävention durch Versionszähler
ConcurrentLinkedQueue<T>	Michael-Scott-Warteschlange	Schlossfrei	FIFO, unbegrenzt
ConcurrentLinkedDeque<T>	schlossfreie Deque	Schlossfrei	Beide Enden
LongAdder	Counter	Schlossfrei	Streifenmuster, Hochdurchsatzzählung

LongAdder Besonders hervorzuheben ist Folgendes: Anstatt eines einzelnen atomaren Zählers, der über alle Threads hinweg konkurriert, wird ein gestreiftes Array von Zählern verwendet, auf das jeweils nur eine Teilmenge der Threads zugreift. Die Konflikte verteilen sich auf die Streifen, anstatt sich auf einen einzigen Ort zu konzentrieren. Die Summe wird verzögert berechnet. sum()Für hochfrequente Inkrementoperationen über viele Threads hinweg, LongAdder deutlich übertreffen 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

Wie SMART TS XL Unterstützt die Entwicklung sperrfreier Systeme

Sperrfreier Code gehört zu den am schwierigsten zu implementierenden Codearten. Die Fehler sind nicht deterministisch, treten nur bei bestimmten Codeverschachtelungen auf und oft erst im Produktivbetrieb bei großem Umfang. Statische Codeanalyse begegnet diesem Problem, indem sie die Struktur des Codes vor der Ausführung untersucht, anstatt auf das Auftreten einer Race Condition zu warten.

SMART TS XL Es analysiert die vollständigen Ausführungspfade von nebenläufigem Code und verfolgt, wie atomare Operationen mit den von ihnen geschützten Speicheradressen zusammenhängen. Für Systeme, die sperrfreien Code mit Legacy-Komponenten oder mehrsprachigen Architekturen kombinieren, bietet es die grenzüberschreitende Transparenz, die Tools für einzelne Sprachen nicht bieten können: Wie hängt beispielsweise ein gemeinsam genutzter Speicherbereich, auf den eine sperrfreie C++-Komponente zugreift, mit dem Java-Dienst zusammen, der daraus liest, oder wie eine nebenläufige Warteschlange in eine COBOL-basierte Verarbeitungspipeline einfließt?

Die statische Codeanalyse identifiziert Muster, die auf Parallelitätskonflikte hinweisen: atomare Ladevorgänge ohne entsprechende Akquisitionssemantik, CAS-Schleifen, die den erwarteten Wert im Fehlerfall nicht aktualisieren, und gemeinsam genutzte Datenstrukturen, in denen Felder, auf die von verschiedenen Threads zugegriffen wird, ohne Ausrichtungsauffüllung zusammenliegen. Die Auswirkungsanalyse verfolgt, welche nachgelagerten Komponenten von einer gemeinsam genutzten, parallelen Datenstruktur abhängen, sodass Änderungen an der Schnittstelle oder der Rückgewinnungsstrategie der Struktur vor ihrer Implementierung korrekt definiert werden können.

Für Unternehmenssysteme, in denen sperrfreie Komponenten mit veralteter Stapelverarbeitung, Message-Queuing-Middleware und modernen Serviceschichten koexistieren müssen, SMART TS XL Abhängigkeitszuordnung bietet die architektonische Sichtweise darauf, wie parallele Datenpfade Komponenten verbinden, die in verschiedenen Sprachen geschrieben sind, und zwar über den gesamten Systemstapel hinweg.

Wann Lock-Free die falsche Wahl ist

Sperrfreie Strukturen sind nicht immer besser als Mutexe. Die Vorteile sperrfreier Strukturen hängen vom jeweiligen Konfliktprofil der Arbeitslast ab. Bei wenigen Threads oder geringer Konfliktrate ist ein gut implementierter Mutex schneller, da er den Overhead atomarer Wiederholungsschleifen und der Cache-Zeilen-Invalidierung über mehrere Kerne hinweg vermeidet.

Verwenden Sie einen Mutex, wenn:

• Die Fadenzahl ist niedrig (unter 4-8) oder es kommt selten zu Reibungsproblemen.
• Der kritische Abschnitt ist lang und komplex (sperrfreie Schleifen werden im Verhältnis zum Abschnitt teuer).
• Korrektheit ist wichtiger als Durchsatz, und der Algorithmus ist mit einer Sperre einfacher.
• Die Plattform verfügt über eine effiziente Futex-basierte Sperrung (Linux). pthread_mutex, Windows SRWLOCK)

Sperrfrei verwenden, wenn:

• Die Fadenzahl ist hoch und die Konkurrenzsituation anhaltend.
• Die Operationen sind kurz (der Overhead der CAS-Schleife ist im Verhältnis zur Operation gering).
• Blockierungen sind inakzeptabel (Echtzeit-Threads, Interrupt-Handler, Signal-Handler).
• Kombination mit anderen sperrfreien Strukturen, bei denen eine Sperre Sperrreihenfolgeabhängigkeiten einführen würde

Warten Sie nicht, wenn:

• Jeder Thread muss unabhängig von anderen Threads innerhalb einer vorgegebenen Zeit abgeschlossen werden.
• Harte Echtzeit- oder sicherheitskritische Anforderungen, bei denen ein Ausfall inakzeptabel ist
• Der Algorithmus kann so strukturiert werden, dass er eine begrenzte Schrittfolge pro Thread unterstützt.

Die Disziplin der sperrfreien Programmierung besteht nicht darin, sie überall zu wählen, sondern sie genau dort zu wählen, wo ihre Eigenschaften – nicht blockierender Ablauf, Vermeidung von Deadlocks, Toleranz gegenüber Präemption – den tatsächlichen Anforderungen des Systems entsprechen.