lockfree

sperrfrei

lockfree ist eine Sammlung sperrenfreier Datenstrukturen, die in Standard-C++11 geschrieben sind und für alle Plattformen geeignet sind – von Deep Embedded bis HPC.

Was sind sperrenfreie Datenstrukturen?

Sperrenfreie Datenstrukturen sind Datenstrukturen, die Thread- und Interrupt-sicher für die gleichzeitige Verwendung sind, ohne dass Mechanismen zum gegenseitigen Ausschluss verwendet werden müssen. Sie sind am nützlichsten für die Kommunikation zwischen Prozessen und lassen sich je nach Anzahl der Operationen und Threads oft viel besser skalieren als sperrenbasierte Strukturen.

Warum lockfree verwenden?

• Geschrieben im Standard-C++11, kompatibel mit allen Plattformen, die es unterstützen
• Alle Datenstrukturen sind in ihren jeweiligen Anwendungsfällen Thread- und Interrupt-sicher
• Keine dynamische Zuordnung
• Optimiert für hohe Leistung
• MIT-Lizenz
• Zusätzliche APIs für neuere C++-Versionen

Welche Datenstrukturen stehen zur Verfügung?

Single-Produzenten-Single-Consumer-Datenstrukturen

• Warteschlange – Am besten für Einzelelementoperationen, extrem schnelle, einfache API, bestehend aus nur 2 Methoden.
• Ringpuffer – Eine allgemeinere Datenstruktur mit der Fähigkeit, mehrere Elemente gleichzeitig zu verarbeiten, verwendet Standardbibliothekskopien und ist daher für Massenoperationen sehr schnell.
• Bipartite Buffer – Eine Variation des Ringpuffers mit der Fähigkeit, immer linearen Platz im Puffer bereitzustellen, ermöglicht die Verarbeitung im Puffer.
• Prioritätswarteschlange – Eine Variation der Warteschlange mit der Möglichkeit, unterschiedliche Prioritäten für Elemente bereitzustellen, sehr nützlich für Dinge wie Signale, Ereignisse und Kommunikationspakete.

Diese Datenstrukturen sind leistungsfähiger und sollten im Allgemeinen immer dann verwendet werden, wenn nur ein Thread/Interrupt Daten pusht und ein anderer sie abruft.

Multi-Produzenten-Multi-Consumer-Datenstrukturen

• Warteschlange – Am besten für Einzelelementoperationen, extrem schnelle, einfache API, bestehend aus nur 2 Methoden.
• Prioritätswarteschlange – Eine Variation der Warteschlange mit der Möglichkeit, unterschiedliche Prioritäten für Elemente bereitzustellen, sehr nützlich für Dinge wie Signale, Ereignisse und Kommunikationspakete.

Diese Datenstrukturen sind allgemeiner und unterstützen mehrere Produzenten und Konsumenten gleichzeitig. Im Vergleich zu Datenstrukturen mit einem einzigen Produzenten und einem einzigen Konsumenten weisen sie jedoch einen Speicher- und Leistungsaufwand auf. Sie erfordern außerdem atomare Anweisungen, die bei einigen Low-End-Mikrocontrollern fehlen können.

Wie kommt man

Es gibt drei Hauptwege, um an die Bibliothek zu gelangen:

• Verwenden von CMake FetchContent()
• Als Git-Submodul
• Durch Herunterladen einer Veröffentlichung von GitHub

Konfiguration

lockfree verwendet standardmäßig die Cacheline-Ausrichtung für Indizes, um das Phänomen der falschen Freigabe zu vermeiden und so den Leistungsverlust der Cacheline-Invalidierung auf Cache-kohärenten Systemen zu vermeiden. Dadurch werden die Indizes standardmäßig auf LOCKFREE_CACHELINE_LENGTH , 64 ausgerichtet.

Auf eingebetteten Systemen sollte LOCKFREE_CACHE_COHERENT fast immer auf false gesetzt werden, um Speicherverschwendung zu vermeiden.

Darüber hinaus haben einige Systeme eine untypische Cacheline-Länge (z. B. haben die Apple M1/M2-CPUs eine Cacheline-Länge von 128 Bytes), und LOCKFREE_CACHELINE_LENGTH sollte in diesen Fällen entsprechend eingestellt werden.

Bekannte Einschränkungen

Alle Datenstrukturen in lockfree sind nur für die Verwendung für triviale Typen gedacht.

FAQ

Warum sollte ich dies anstelle des Sperrens von Datenstrukturen auf einem gehosteten Computer verwenden?

Der Hauptgrund für die Verwendung einer sperrenfreien Datenstruktur in gehosteten Umgebungen besteht darin, Probleme im Zusammenhang mit Sperren wie Deadlocks, Prioritätsumkehr und nichtdeterministische Zugriffslatenz zu vermeiden. Bei ordnungsgemäßer Verwendung können sperrenfreie Datenstrukturen in einigen Szenarien auch die Leistung verbessern.

Darüber hinaus bietet lockfree eine Möglichkeit, Anwendungen und Bibliotheken zu erstellen, die so kompiliert werden können, dass sie sowohl in POSIX- als auch in Nicht-POSIX-Umgebungen funktionieren, ohne #ifdef oder Polymorphismus.

Warum sollte dies gegenüber den von RTOS bereitgestellten IPC-Mechanismen auf einem eingebetteten System verwendet werden?

Während das Sperren auf eingebetteten Systemen wie Mikrocontrollern normalerweise nicht teuer ist, gibt es eine große Vielfalt an RTOS und keine standardisierte API zum Sperren. Die Tatsache, dass von 8051 bis RISC-V mehrere Architekturen vorhanden sind, führt dazu, dass auch die Interrupt-Management-Methoden nicht standardisiert sind.

lockfree bietet eine Möglichkeit, portablen eingebetteten Code mit vernachlässigbaren Leistungseinbußen im Gegensatz zum Sperren zu erstellen. Code mit lockfree kann so kompiliert werden, dass er auf jeder eingebetteten Plattform läuft, die C++11 unterstützt. Darüber hinaus kann der Code problemlos auf einem Host-Computer getestet werden, ohne dass ein Mock-Vorgang erforderlich ist.

Welche Vorteile bietet die Verwendung von C++ gegenüber C für die Bibliothek?

• Typensicherheit, da Datenstrukturen auf Typ- und Größenvorlagen basieren
• Viel einfachere und weniger fehleranfällige Instanziierung
• Höhere Leistung aufgrund der zur Kompilierungszeit bekannten Größe und der Nur-Header-Implementierung
• Bei der Kapselung ist der Datenpuffer ein Klassenmitglied und wird nicht von einem Zeiger übergeben

Wie ist die formale Klassifizierung der Datenstrukturen in lockfree ?

Alle Strukturen in lockfree sind begrenzt , arraybasiert und sperrenfrei , spsc-Datenstrukturen sind außerdem wartefrei und terminierungssicher .

Theorie und Referenzen

Weitere Einblicke in die sperrenfreie Programmierung finden Sie hier:

• Diese brillante Talkreihe von Herb Sutter
• Live Lock-Free- oder Deadlock-Talkserie von Fedor Pikus
• Dmitry Vyukovs ausgezeichneter Blog