Implementierung einer sperrenfreien Warteschlange
Gehen Sie den Entwurf einer sperrenfreien Warteschlange für einen Produzenten und einen Konsumenten durch.
Implementierung einer sperrenfreien Warteschlange ist eine kostenlose C++ Academy-Lektion auf CoddyKit. Dies ist Lektion 3 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des C++ Academy-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der C++ Academy-Kurs umfasst insgesamt 4 Lektionen.
Warum lockfreie Queues?
Queues mit Mutexes können bei hoher Konkurrenz zu Engpässen werden. Eine lockfreie Queue ermöglicht es Produzenten und Konsumenten, gleichzeitig Fortschritte zu machen.
SPSC vs. MPMC
Zwei Varianten:
- SPSC – ein Produzent, ein Konsument (am einfachsten und schnellsten)
- MPMC – mehrere Produzenten, mehrere Konsumenten (am allgemeinsten)
SPSC ist die naheliegende Wahl, wenn Sie beide Enden kontrollieren.
Skizze eines SPSC-Ringpuffers
Ein Ringpuffer mit zwei Indizes: head (Consumer) und tail (Producer). Jede Seite aktualisiert ihren eigenen Index.
template <typename T, size_t N>
class SpscQueue {
T buffer_[N];
std::atomic<size_t> head_{0};
std::atomic<size_t> tail_{0};
public:
bool push(const T& v);
bool pop(T& v);
};SPSC-Push
Der Producer prüft die freien Plätze, schreibt die Daten und veröffentlicht sie anschließend durch die Aktualisierung von tail.
bool push(const T& v) {
const size_t t = tail_.load(std::memory_order_relaxed);
const size_t next = (t + 1) % N;
if (next == head_.load(std::memory_order_acquire))
return false; // full
buffer_[t] = v;
tail_.store(next, std::memory_order_release);
return true;
}SPSC-Pop
Der Consumer prüft, ob Daten vorhanden sind, liest sie und veröffentlicht anschließend den neuen Stand durch die Aktualisierung von head.
bool pop(T& v) {
const size_t h = head_.load(std::memory_order_relaxed);
if (h == tail_.load(std::memory_order_acquire))
return false; // empty
v = buffer_[h];
head_.store((h + 1) % N, std::memory_order_release);
return true;
}Kombination der Memory Orders
Der Release-Store auf tail synchronisiert sich mit dem Acquire-Load auf tail im Consumer und umgekehrt. Ohne die richtige Reihenfolge könnten die Datenschreibvorgänge hinter die Aktualisierung des Index verschoben werden.
Cache-Line-Padding
Um False Sharing zu vermeiden, platzieren Sie head_ und tail_ in separaten Cache-Lines (typischerweise 64 Byte voneinander entfernt). Verwenden Sie alignas.
alignas(64) std::atomic<size_t> head_{0};
alignas(64) std::atomic<size_t> tail_{0};MPMC: Deutlich schwieriger
Mehrere Producer oder Consumer erfordern zusätzliche Koordination – in der Regel mit CAS-Schleifen auf gemeinsam genutzten Indizes. Es gibt viele verschiedene Designs (Vyukov queue, MS-queue, auf Hazard Pointern basierende Verfahren).
Boost.Lockfree
Lock-freie Queues in Produktionsqualität sind schwierig zu implementieren. Verwenden Sie Boost.Lockfree oder die ProducerConsumerQueue von Folly, statt eine eigene Implementierung zu entwickeln.
Abwägungen
Lock-freie Queues:
- Höherer Durchsatz unter hoher Konkurrenz
- Begrenzte Latenz (kein Warten auf einen Lock)
- Deutlich schwieriger zu schreiben und zu debuggen
- Fehler bei der Speicherreihenfolge sind lautlos und schwer aufzuspüren
Lock-freien Code testen
Verwenden Sie ThreadSanitizer (-fsanitize=thread), um Data Races zu erkennen. Verwenden Sie Stresstests mit zufällig eingefügten Schlafpausen, um Fehler bei der Reihenfolge aufzudecken.
Wann ein Mutex ausreicht
Die meisten Anwendungen benötigen keine lock-freien Queues. Messen Sie zuerst – eine gut implementierte, durch einen Mutex geschützte Queue bietet oft eine ausreichende Leistung, insbesondere bei gebündelter Verarbeitung.
Kurze Überprüfung
Was ist False Sharing, und warum sollten Sie head_ und tail_ mit Padding in getrennten Cache-Lines platzieren?
Zusammenfassung
Eine lock-freie SPSC-Queue verwendet einen Ringpuffer mit einem dem Producer zugeordneten tail und einem dem Consumer zugeordneten head. Verwenden Sie Acquire-/Release-Reihenfolge und platzieren Sie die Indizes mit Padding in getrennten Cache-Lines. Für MPMC sollten Sie eine getestete Bibliothek bevorzugen.
Häufig gestellte Fragen
Ist die Lektion „Implementierung einer sperrenfreien Warteschlange“ kostenlos?
Ja — der vollständige Text von „Implementierung einer sperrenfreien Warteschlange“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des C++ Academy-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der C++ Academy-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Implementierung einer sperrenfreien Warteschlange“?
Gehen Sie den Entwurf einer sperrenfreien Warteschlange für einen Produzenten und einen Konsumenten durch. Du übst C++ Academy mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.
Brauche ich Erfahrung, um C++ Academy zu starten?
Keine Vorkenntnisse erforderlich. C++ Academy auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 3 von 4.
Wie lange dauert die Lektion „Implementierung einer sperrenfreien Warteschlange“?
Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.
Kann ich in dieser C++ Academy-Lektion Code schreiben und ausführen?
Ja. Jede C++ Academy-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.
Alle Lektionen in diesem Kurs
- std::atomic und Speicherordnungen
- Compare-and-Swap-Muster (CAS)
- Implementierung einer sperrenfreien Warteschlange
- Hazard Pointer und das ABA-Problem