////
Wie man lock-freie Algorithmen programmiert, am Beispiel von Produzent und Konsument
Lock-freie Programmierung verzichtet auf Mutexe und andere blockierende Mechanismen. Stattdessen wird der gemeinsame Zustand ausschließlich über atomare Operationen verändert. Der zentrale Gedanke ist Fortschritt ohne Blockieren.
Dabei sind einige Punkte grundlegend:
-
Getrennte Verantwortlichkeiten: Jeder gemeinsam genutzte Zustand sollte möglichst genau einem Thread ›gehören‹. Andere Threads dürfen ihn lesen, aber nicht verändern. Je klarer diese Rollen sind, desto einfacher wird der Code.
-
Atomare Zustandsübergänge: Änderungen am gemeinsamen Zustand müssen atomar sichtbar werden. Dazu dienen atomare Variablen und Compare-Exchange oder klar geordnete Stores und Loads.
-
Kein Warten auf Locks: Wenn ein Thread gerade nicht weiterarbeiten kann, darf er keinen anderen Thread blockieren. Er erkennt den Zustand und versucht es später erneut.
-
Fortschritt statt Fairness: Lock-freiheit garantiert nicht, dass jeder Thread vorankommt, sondern dass irgendein Thread vorankommt. Das unterscheidet lock-frei von wait-frei.
-
Speicherordnung ist Teil der Logik: Die Reihenfolge, in der Daten geschrieben und sichtbar gemacht werden, ist entscheidend. ›Daten zuerst, Zustand danach‹ ist ein häufiges Muster.
Schauen wir uns dazu ein klassisches Szenario an. Ein Thread erzeugt fortlaufend Daten, ein anderer verarbeitet sie. Beide laufen parallel und tauschen Daten über einen gemeinsamen Puffer aus. Den Erzeuger nennt man Produzent, den Verbraucher Konsument. Dieses Muster ist weit verbreitet:
- Logging
- Streaming
- Messwertverarbeitung
- Datenpipelines
Hier ist Blockieren besonders unerwünscht, weil ein wartender Thread den gesamten Datenfluss verzögert.
Die Aufgaben von Produzent und Konsument sind klar:
- Der Produzent erzeugt Werte und legt sie in einem gemeinsamen Puffer ab.
- Der Konsument entnimmt diese Werte und verarbeitet sie weiter.
- Beide Threads laufen unabhängig voneinander.
- Der Produzent darf den Konsumenten nicht anhalten und umgekehrt.
Statt sich über Mutexe zu koordinieren, prüfen beide nur den Zustand des Puffers: voll oder leer.
Der folgende Code implementiert einen einfachen Ringpuffer mit genau einem Produzenten und genau einem Konsumenten. Beide Threads kommunizieren ausschließlich über zwei atomare Indizes.
#include <stdatomic.h>
#include <threads.h>
#include <stdio.h>
#include <time.h>
constexpr int N = 8;
typedef struct {
int buf[N];
atomic_int w;
atomic_int r;
} ringbuffer_t;
static int next(int i) { return (i + 1) % N; }
int rb_push(ringbuffer_t *q, int x) {
int w = atomic_load_explicit(&q->w, memory_order_relaxed);
int r = atomic_load_explicit(&q->r, memory_order_acquire);
if (next(w) == r) return 0; // voll
q->buf[w] = x;
atomic_store_explicit(&q->w, next(w), memory_order_release);
return 1;
}
int rb_pop(ringbuffer_t *q, int *out) {
int r = atomic_load_explicit(&q->r, memory_order_relaxed);
int w = atomic_load_explicit(&q->w, memory_order_acquire);
if (r == w) return 0; // leer
*out = q->buf[r];
atomic_store_explicit(&q->r, next(r), memory_order_release);
return 1;
}
static void msleep(long ms) {
struct timespec ts = {
.tv_sec = ms / 1000,
.tv_nsec = (ms % 1000) * 1000000L
};
thrd_sleep(&ts, nullptr);
}
int producer(void *arg) {
ringbuffer_t *q = arg;
for (int i = 1; i <= 20; i++) {
while (!rb_push(q, i)) {
puts("P: wartet (Puffer voll)");
msleep(40);
}
printf("P: schreibt %d\n", i);
msleep(10);
}
while (!rb_push(q, 0)) {}
return 0;
}
int consumer(void *arg) {
ringbuffer_t *q = arg;
int x;
for (;;) {
if (!rb_pop(q, &x)) {
puts("C: wartet (Puffer leer)");
msleep(80);
continue;
}
if (x == 0) break;
printf("C: liest %d\n", x);
msleep(60);
}
return 0;
}
int main() {
ringbuffer_t q = { .w = 0, .r = 0 };
thrd_t prod, cons;
thrd_create(&prod, producer, &q);
thrd_create(&cons, consumer, &q);
thrd_join(prod, nullptr);
thrd_join(cons, nullptr);
}
Der Ringpuffer besteht aus einem festen Array und zwei atomaren Indizes:
wzeigt auf die nächste Schreibposition.rzeigt auf die nächste Leseposition.
Der Produzent schreibt ausschließlich w, der Konsument ausschließlich r. Beide lesen den jeweils anderen Index, verändern ihn aber nie. Damit gibt es keinen konkurrierenden Schreibzugriff auf dieselbe Variable.
Der Algorithmus ist lock-freie, weil keine Mutexe oder blockierenden Primitive verwendet werden. Wenn der Produzent nicht schreiben kann, ist der Puffer voll. Dann kann der Konsument mindestens ein Element lesen. Wenn der Konsument nicht lesen kann, ist der Puffer leer. Dann kann der Produzent mindestens ein Element schreiben. Es existiert kein Zustand, in dem beide Threads gleichzeitig aufeinander warten.
##todo##
Das ABA-Problem
Dieser Stack hat jedoch ein subtiles Problem: das ABA-Problem. Wenn ein Thread einen Knoten A liest, dann pausiert wird, ein anderer Thread A entfernt und später wieder denselben Knoten A (an derselben Speicheradresse) einfügt, wird der erste Thread nicht bemerken, dass zwischenzeitlich Änderungen stattfanden. Die Compare-Exchange-Operation wird erfolgreich sein, obwohl die Struktur sich verändert hat. Dies kann zu Korruptionen führen.
// Vereinfachte Illustration des ABA-Problems
// Thread 1: Liest head = A
// Thread 2: Pop A, Pop B, Push A (head ist wieder A)
// Thread 1: Compare-Exchange erfolgreich, aber zwischenzeitlich veränderte Struktur
Die Lösung für das ABA-Problem ist typischerweise die Verwendung von Versionsnummern oder Tagged Pointers, die zusätzlich zur Adresse eine Versionsnummer speichern. Jede Änderung inkrementiert die Version, sodass ABA-Situationen erkannt werden. Die Implementierung ist komplex und plattformabhängig.
Praxis, Grenzen und typische Fehler
Lock-freie Programmierung erfordert tiefes Verständnis des Memory-Models und sorgfältige Analyse aller möglichen Interleaving-Szenarien. Fehler sind oft nicht reproduzierbar und zeigen sich nur unter hoher Last. Es ist ratsam, existierende, getestete lock-freie Datenstrukturen zu verwenden, statt eigene zu implementieren. Bibliotheken wie die Concurrency Kit oder Boost.Lockfree bieten robuste Implementierungen gängiger Datenstrukturen.
Die Performance-Vorteile lock-freier Algorithmen sind signifikant, besonders bei hohem Konflikt zwischen Threads. Während Threads bei Mutexen blockieren und Kontextwechsel anfallen, arbeiten lock-freie Algorithmen kontinuierlich. Allerdings ist die Implementierung fehleranfällig, und bei niedrigem Konflikt können Mutexe sogar schneller sein, da sie weniger Overhead haben.
Ein häufiger Fehler ist die Annahme, dass lock-freier Code automatisch schneller ist. Dies stimmt nur unter bestimmten Bedingungen. Bei niedrigem Konflikt oder einfachen Operationen kann ein gut implementierter Mutex schneller sein als ein lock-freier Algorithmus mit vielen Retry-Schleifen. Man sollte messen und vergleichen, statt blind lock-freie Strukturen zu verwenden.
Ein weiterer Fehler ist die unzureichende Behandlung des ABA-Problems. Viele naive lock-freie Implementierungen funktionieren unter normalen Umständen, scheitern aber unter hoher Last, wenn Speicher wiederverwendet wird. Man muss entweder das ABA-Problem vollständig vermeiden (etwa durch Verwendung von Garbage Collection) oder es durch Versioning lösen.
Lock-freie Programmierung ist ein spezialisiertes Gebiet, das nur in Performance-kritischen Szenarien mit hohem Konkurrenzdruck sinnvoll ist. Für die meisten Anwendungen sind Mutexe ausreichend und deutlich einfacher korrekt zu implementieren. Wenn man lock-freie Techniken einsetzt, sollte man bestehende, gut getestete Implementierungen verwenden und nur bei zwingender Notwendigkeit eigene schreiben.
==== Fence-Operationen
Fence-Operationen, auch Memory Barriers genannt, sind Synchronisationsprimitive, die Ordnungsgarantien zwischen Speicheroperationen etablieren, ohne an spezifische atomare Variablen gebunden zu sein. Sie beeinflussen die Reihenfolge, in der Speicherzugriffe sichtbar werden, indem sie verhindern, dass bestimmte Umsortierungen durch Compiler oder Prozessor stattfinden. Fences sind ein Low-Level-Werkzeug für fortgeschrittene Synchronisationsmuster und werden typischerweise nur benötigt, wenn man sehr feinkörnige Kontrolle über Memory-Ordnung braucht.
Die Funktion atomic_thread_fence() fügt eine Fence-Operation mit der angegebenen Memory Order in den Programmfluss ein. Eine Fence wirkt als Barriere: Speicheroperationen vor der Fence dürfen nicht über sie hinweg nach hinten verschoben werden, und Operationen nach der Fence dürfen nicht nach vorne verschoben werden. Die genaue Semantik hängt von der Memory Order ab.
Eine Acquire-Fence garantiert, dass alle Speicherzugriffe nach der Fence die Ergebnisse aller Schreiboperationen sehen, die vor einer entsprechenden Release-Operation in einem anderen Thread stattfanden. Eine Release-Fence garantiert, dass alle Speicherzugriffe vor der Fence für Threads sichtbar sind, die nach einer entsprechenden Acquire-Operation kommen. Fences etablieren also Happens-Before-Relationen ähnlich wie atomare Operationen mit Acquire- oder Release-Semantik, aber ohne an eine spezifische Variable gebunden zu sein.
#include <stdio.h>
#include <threads.h>
#include <stdatomic.h>
int data = 0;
atomic_int flag = 0;
int producer(void *arg) {
data = 42; // Normale Schreiboperation
atomic_thread_fence(memory_order_release);
atomic_store_explicit(&flag, 1, memory_order_relaxed);
puts("Producer: Daten geschrieben");
// 📣 Producer: Daten geschrieben
return 0;
}
int consumer(void *arg) {
while (atomic_load_explicit(&flag, memory_order_relaxed) == 0) {
// Warten
}
atomic_thread_fence(memory_order_acquire);
printf("Consumer: Gelesene Daten: %d\n", data);
// 📣 Consumer: Gelesene Daten: 42
return 0;
}
int main() {
thrd_t prod, cons;
thrd_create(&cons, consumer, nullptr);
thrd_create(&prod, producer, nullptr);
thrd_join(prod, nullptr);
thrd_join(cons, nullptr);
}
In diesem Beispiel schreibt der Producer erst data, fügt dann eine Release-Fence ein, und setzt schließlich das Flag mit relaxed-Semantik. Der Consumer liest das Flag mit relaxed-Semantik, fügt eine Acquire-Fence ein, und liest dann data. Die Kombination aus Release-Fence im Producer und Acquire-Fence im Consumer etabliert eine Happens-Before-Relation, die den Zugriff auf data sicher macht.
Man könnte dasselbe Resultat erreichen, indem man das Flag mit Release- bzw. Acquire-Semantik schreibt und liest, ohne explizite Fences. Der Vorteil von Fences liegt darin, dass eine einzige Fence mehrere relaxed Operations abdecken kann, was in manchen Szenarien effizienter ist.
#include <stdio.h>
#include <threads.h>
#include <stdatomic.h>
int data1 = 0;
int data2 = 0;
atomic_int flag1 = 0;
atomic_int flag2 = 0;
int multi_producer(void *arg) {
data1 = 10;
data2 = 20;
atomic_thread_fence(memory_order_release);
atomic_store_explicit(&flag1, 1, memory_order_relaxed);
atomic_store_explicit(&flag2, 1, memory_order_relaxed);
return 0;
}
int multi_consumer(void *arg) {
while (atomic_load_explicit(&flag1, memory_order_relaxed) == 0 ||
atomic_load_explicit(&flag2, memory_order_relaxed) == 0) {
// Warten auf beide Flags
}
atomic_thread_fence(memory_order_acquire);
printf("Consumer: data1=%d, data2=%d\n", data1, data2);
// 📣 Consumer: data1=10, data2=20
return 0;
}
int main() {
thrd_t prod, cons;
thrd_create(&cons, multi_consumer, nullptr);
thrd_create(&prod, multi_producer, nullptr);
thrd_join(prod, nullptr);
thrd_join(cons, nullptr);
}
Hier schützt eine einzige Release-Fence beide Schreiboperationen auf data1 und data2, und beide Flag-Operationen können relaxed sein. Dies ist effizienter als jedes Flag mit Release-Semantik zu setzen.
Eine seq_cst-Fence ist die stärkste Form. Sie etabliert eine totale Ordnung aller seq_cst-Fences über alle Threads hinweg. Dies bedeutet: Wenn Thread A eine seq_cst-Fence ausführt und Thread B eine andere seq_cst-Fence ausführt, dann sehen alle Threads eine konsistente Reihenfolge dieser Fences. Diese starke Garantie ist selten notwendig, kann aber in komplexen Synchronisationsszenarien hilfreich sein.
#include <stdio.h>
#include <stdatomic.h>
int main() {
// Seq_cst Fence für globale Ordnung
atomic_thread_fence(memory_order_seq_cst);
puts("Alle vorherigen Operationen sind global sichtbar");
// 📣 Alle vorherigen Operationen sind global sichtbar
}
Zusätzlich zu atomic_thread_fence() gibt es atomic_signal_fence(), die nur die Compiler-Optimierungen beeinflusst, aber keine Hardware-Barrieren einfügt. Signal-Fences sind nützlich in Signal-Handlern, wo man verhindern will, dass der Compiler Zugriffe umsortiert, aber keine Prozessor-Synchronisation benötigt, da Signal-Handler im selben Thread laufen.
#include <stdio.h>
#include <signal.h>
#include <stdatomic.h>
volatile sig_atomic_t signal_received = 0;
void signal_handler(int sig) {
atomic_signal_fence(memory_order_acquire);
signal_received = 1;
atomic_signal_fence(memory_order_release);
}
int main() {
signal(SIGINT, signal_handler);
puts("Warte auf Signal (Ctrl+C)");
while (!signal_received) {
// Warten
}
puts("Signal empfangen");
}
Die Signal-Fences garantieren, dass der Compiler die Zugriffe auf signal_received nicht umsortiert, ohne teure Hardware-Barrieren einzufügen. Dies ist ausreichend, da Signal-Handler synchron im selben Thread ausgeführt werden.(Quelle: ISO/IEC 9899:2024, § 7.17.4 Fences)
Fences sind ein mächtiges, aber komplexes Werkzeug. Ihre korrekte Verwendung erfordert tiefes Verständnis des Memory-Models und der Hardware-Architektur. In den meisten Fällen sind atomare Operationen mit expliziter Memory Order einfacher zu verstehen und ausreichend. Fences sollten nur verwendet werden, wenn sie einen klaren Vorteil bieten, etwa bei der Synchronisation vieler Variablen mit einem einzigen Synchronisationspunkt.
Ein häufiger Fehler ist die Verwendung von Fences ohne klares Verständnis ihrer Semantik. Fences allein etablieren keine Synchronisation – sie müssen mit atomaren Operationen kombiniert werden, die als Synchronisationspunkte dienen. Eine Fence ohne entsprechende atomare Operation ist wirkungslos.
Ein weiterer Fehler ist die Überbenutzung von Fences. Viele Entwickler fügen Fences ›zur Sicherheit‹ ein, ohne zu verstehen, ob sie wirklich benötigt werden. Dies verringert die Performance ohne Nutzen. Man sollte Fences nur gezielt einsetzen, nachdem man verifiziert hat, dass sie notwendig sind.
Die Wahl zwischen atomaren Operationen mit expliziter Memory Order und Fences ist oft eine Frage des Designs und der Performance-Charakteristiken. Für einfache Synchronisationsmuster sind atomare Operationen mit Acquire-Release-Semantik klarer und wartbarer. Für komplexe Szenarien mit vielen Variablen können Fences effizienter sein. Man sollte messen und vergleichen, welcher Ansatz für den konkreten Anwendungsfall besser funktioniert.
Fences sind das letzte Puzzleteil im Verständnis des C-Memory-Models. Sie bieten die feinkörnigste Kontrolle über Memory-Ordnung und ermöglichen hochoptimierte Synchronisationsprotokolle. Ihre Komplexität bedeutet jedoch, dass sie nur in spezialisierten, Performance-kritischen Szenarien eingesetzt werden sollten. Für die große Mehrheit nebenläufiger Programme sind atomare Operationen mit expliziter Memory Order und Mutexe die bessere Wahl. ////