Nicht blockierender Algorithmus - Non-blocking algorithm

Nicht zu verwechseln mit Non-Blocking I/O .

In der Informatik wird ein Algorithmus als nicht-blockierend bezeichnet, wenn ein Ausfall oder eine Unterbrechung eines Threads nicht zu einem Ausfall oder einer Unterbrechung eines anderen Threads führen kann; Für einige Operationen bieten diese Algorithmen eine nützliche Alternative zu herkömmlichen Blockierungsimplementierungen . Ein nicht-blockierender Algorithmus ist sperrungsfrei, wenn ein systemweiter Fortschritt garantiert ist , und wartefrei, wenn auch ein pro-Thread-Fortschritt garantiert ist. „Non-blocking“ wurde in der Literatur bis zur Einführung der Obstruktionsfreiheit im Jahr 2003 als Synonym für „lock-free“ verwendet.

Das Wort "non-blocking" wurde traditionell verwendet, um Telekommunikationsnetze zu beschreiben , die eine Verbindung über eine Reihe von Relais leiten konnten, "ohne bestehende Anrufe neu arrangieren zu müssen" (siehe Clos-Netzwerk ). Auch wenn die Telefonzentrale "nicht defekt ist, kann sie immer die Verbindung herstellen" (siehe Nonblocking Minimal Spanning Switch ).

Motivation

Hauptartikel: Nachteile von Schlössern

Der traditionelle Ansatz bei der Multithread-Programmierung besteht darin, Sperren zu verwenden, um den Zugriff auf gemeinsam genutzte Ressourcen zu synchronisieren . Synchronisationsprimitive wie Mutexe , Semaphoren und kritische Abschnitte sind alles Mechanismen, mit denen ein Programmierer sicherstellen kann, dass bestimmte Codeabschnitte nicht gleichzeitig ausgeführt werden, wenn dies die Strukturen des gemeinsamen Speichers beschädigen würde. Wenn ein Thread versucht, eine Sperre zu erlangen, die bereits von einem anderen Thread gehalten wird, wird der Thread blockiert, bis die Sperre frei ist.

Das Blockieren eines Threads kann aus vielen Gründen unerwünscht sein. Ein offensichtlicher Grund ist, dass der Thread, während er blockiert ist, nichts erreichen kann: Wenn der blockierte Thread eine Aufgabe mit hoher Priorität oder Echtzeit ausgeführt hätte, wäre es höchst unerwünscht, seinen Fortschritt zu stoppen.

Andere Probleme sind weniger offensichtlich. Bestimmte Interaktionen zwischen Sperren können beispielsweise zu Fehlerbedingungen wie Deadlock , Livelock und Prioritätsinversion führen . Die Verwendung von Sperren beinhaltet auch einen Kompromiss zwischen grobkörnigem Sperren, das die Möglichkeiten für Parallelität erheblich reduzieren kann , und feinkörnigem Sperren, das ein sorgfältigeres Design erfordert, den Sperraufwand erhöht und anfälliger für Fehler ist.

Im Gegensatz zu blockierenden Algorithmen leiden nicht blockierende Algorithmen nicht unter diesen Nachteilen und können außerdem sicher in Interrupt-Handlern verwendet werden : Obwohl der präemptive Thread nicht wieder aufgenommen werden kann, ist der Fortschritt ohne ihn immer noch möglich. Im Gegensatz dazu kann in einem Interrupt-Handler nicht sicher auf globale Datenstrukturen zugegriffen werden, die durch gegenseitigen Ausschluss geschützt sind, da der präemptive Thread derjenige sein kann, der die Sperre hält – dies kann jedoch leicht korrigiert werden, indem die Interrupt-Anforderung während des kritischen Abschnitts maskiert wird.

Eine sperrfreie Datenstruktur kann verwendet werden, um die Leistung zu verbessern. Eine sperrungsfreie Datenstruktur erhöht die Zeit, die für die parallele Ausführung anstatt für die serielle Ausführung aufgewendet wird, und verbessert die Leistung auf einem Mehrkernprozessor , da der Zugriff auf die gemeinsam genutzte Datenstruktur nicht serialisiert werden muss, um kohärent zu bleiben.

Implementierung

Mit wenigen Ausnahmen verwenden nicht-blockierende Algorithmen atomare Read-Modify-Write- Primitive, die die Hardware bereitstellen muss, von denen die bemerkenswerteste Vergleichs- und Auslagerungsmethode (CAS) ist . Kritische Abschnitte werden fast immer unter Verwendung von Standardschnittstellen über diesen Grundelementen implementiert (im allgemeinen Fall werden kritische Abschnitte blockieren, selbst wenn sie mit diesen Grundelementen implementiert werden). In den 1990er Jahren mussten alle nicht blockierenden Algorithmen "nativ" mit den zugrunde liegenden Primitiven geschrieben werden, um eine akzeptable Leistung zu erzielen. Das aufstrebende Gebiet des Software-Transaktionsspeichers verspricht jedoch Standardabstraktionen zum Schreiben von effizientem nicht-blockierendem Code.

Es wurde auch viel Forschung betrieben, um grundlegende Datenstrukturen wie Stacks , Warteschlangen , Sets und Hash-Tabellen bereitzustellen . Diese ermöglichen es Programmen, auf einfache Weise Daten zwischen Threads asynchron auszutauschen.

Außerdem sind einige nicht blockierende Datenstrukturen schwach genug, um ohne spezielle atomare Grundelemente implementiert zu werden. Zu diesen Ausnahmen gehören:

  • ein Single-Reader-Single-Writer- Ringpuffer- FIFO mit einer Größe, die den Überlauf eines der verfügbaren vorzeichenlosen Integer-Typen gleichmäßig aufteilt, kann mit nur einer Speicherbarriere bedingungslos sicher implementiert werden
  • Read-Copy-Update mit einem einzigen Writer und beliebig vielen Readern. (Die Leser sind wartefrei; der Schreiber ist normalerweise gesperrt, bis er Speicher zurückfordern muss).
  • Read-Copy-Update mit mehreren Writern und beliebig vielen Readern. (Die Leser sind wartefrei; mehrere Schreiber serialisieren in der Regel mit einer Sperre und sind nicht frei von Behinderungen).

Mehrere Bibliotheken verwenden intern sperrenfreie Techniken, aber es ist schwierig, sperrenfreien Code zu schreiben, der korrekt ist.

Wartefreiheit

Wait-Freiheit ist die stärkste nicht-blockierende Garantie des Fortschritts, die Kombination garantiert systemweiten Durchsatz mit Hunger -Freiheit. Ein Algorithmus ist wartefrei, wenn jede Operation eine Grenze für die Anzahl der Schritte hat, die der Algorithmus braucht, bevor die Operation abgeschlossen ist. Diese Eigenschaft ist für Echtzeitsysteme kritisch und immer schön zu haben, solange die Leistungskosten nicht zu hoch sind.

In den 1980er Jahren wurde gezeigt, dass alle Algorithmen wartefrei implementiert werden können, und viele Transformationen aus seriellem Code, sogenannte universelle Konstruktionen , wurden demonstriert. Die resultierende Leistung entspricht jedoch im Allgemeinen nicht einmal naiven Blockierungsdesigns. Mehrere Veröffentlichungen haben seitdem die Leistung universeller Konstruktionen verbessert, aber ihre Leistung liegt immer noch weit unter Blockierungskonstruktionen.

Mehrere Veröffentlichungen haben die Schwierigkeit untersucht, wartefreie Algorithmen zu erstellen. Es hat sich beispielsweise gezeigt, dass die weit verbreiteten atomaren bedingten Primitive CAS und LL/SC keine hungerfreien Implementierungen vieler üblicher Datenstrukturen bereitstellen können, ohne dass die Speicherkosten linear in der Anzahl der Threads ansteigen.

In der Praxis stellen diese unteren Grenzen jedoch keine wirkliche Barriere dar, da die Ausgabe einer Cache-Line oder eines exklusiven Reservierungsgranulats (bis zu 2 KB auf ARM) Speicher pro Thread im Shared Memory für praktische Systeme nicht als zu kostspielig angesehen wird (normalerweise die Menge von logisch erforderlicher Speicher ist ein Wort, aber physisch kollidieren CAS-Operationen auf derselben Cache-Zeile, und LL/SC-Operationen in derselben exklusiven Reservierungs-Granula kollidieren, so dass die physikalisch erforderliche Speichermenge größer ist).

Wartefreie Algorithmen waren bis 2011 sowohl in der Forschung als auch in der Praxis selten. Im Jahr 2011 präsentierten Kogan und Petrank jedoch ein wartefreies Warteschlangengebäude auf dem CAS- Primitiven, das allgemein auf gemeinsamer Hardware verfügbar ist. Ihre Konstruktion erweiterte die sperrenfreie Warteschlange von Michael und Scott, die in der Praxis oft eine effiziente Warteschlange ist. Ein Folgepapier von Kogan und Petrank lieferte eine Methode, um wartefreie Algorithmen schnell zu machen, und nutzte diese Methode, um die wartefreie Warteschlange praktisch so schnell wie ihr sperrenfreies Gegenstück zu machen. Ein nachfolgendes Papier von Timnat und Petrank lieferte einen automatischen Mechanismus zum Generieren wartefreier Datenstrukturen aus sperrfreien. Somit stehen jetzt für viele Datenstrukturen wartefreie Implementierungen zur Verfügung.

Lock-Freiheit

Die Sperrfreiheit ermöglicht das Verhungern einzelner Threads, garantiert jedoch einen systemweiten Durchsatz. Ein Algorithmus ist blockierungsfrei, wenn bei ausreichend langer Laufzeit der Programm-Threads mindestens einer der Threads Fortschritte macht (für eine sinnvolle Definition des Fortschritts). Alle wartefreien Algorithmen sind frei von Sperren.

Insbesondere wenn ein Thread suspendiert ist, garantiert ein blockierungsfreier Algorithmus, dass die verbleibenden Threads noch Fortschritte machen können. Wenn also zwei Threads um denselben Mutex-Lock oder Spinlock konkurrieren können, ist der Algorithmus nicht sperrenfrei. (Wenn wir einen Thread aussetzen, der die Sperre hält, wird der zweite Thread blockiert.)

Ein Algorithmus ist sperrungsfrei, wenn unendlich oft Operationen von einigen Prozessoren in einer endlichen Anzahl von Schritten erfolgreich sind. Wenn beispielsweise N Prozessoren versuchen, eine Operation auszuführen, werden einige der N Prozesse die Operation in einer endlichen Anzahl von Schritten erfolgreich beenden und andere können fehlschlagen und bei einem Fehler erneut versuchen . Der Unterschied zwischen wartefrei und sperrungsfrei besteht darin, dass der wartefreie Betrieb durch jeden Prozess garantiert in einer endlichen Anzahl von Schritten erfolgreich ist, unabhängig von den anderen Prozessoren.

Im Allgemeinen kann ein blockierungsfreier Algorithmus in vier Phasen ablaufen: die eigene Operation abschließen, eine behindernde Operation unterstützen, eine behindernde Operation abbrechen und warten. Der Abschluss der eigenen Operation wird durch die Möglichkeit der gleichzeitigen Hilfeleistung und Abtreibung erschwert, ist jedoch ausnahmslos der schnellste Weg zum Abschluss.

Die Entscheidung, wann bei einem Hindernis geholfen, abgebrochen oder gewartet werden soll, liegt in der Verantwortung eines Konfliktmanagers . Dies kann sehr einfach sein (Operationen mit höherer Priorität unterstützen, Operationen mit niedrigerer Priorität abbrechen) oder optimierter sein, um einen besseren Durchsatz zu erzielen oder die Latenz von priorisierten Operationen zu verringern.

Die korrekte gleichzeitige Unterstützung ist normalerweise der komplexeste Teil eines sperrfreien Algorithmus und oft sehr kostspielig in der Ausführung: nicht nur der unterstützende Thread wird langsamer, sondern dank der Mechanik des gemeinsamen Speichers wird auch der unterstützte Thread verlangsamt , falls es noch läuft.

Hindernisfreiheit

Hindernisfreiheit ist die schwächste natürliche, nicht blockierende Fortschrittsgarantie. Ein Algorithmus ist hindernisfrei, wenn zu irgendeinem Zeitpunkt ein einzelner Thread, der isoliert (dh mit allen blockierenden Threads ausgesetzt) ​​für eine begrenzte Anzahl von Schritten ausgeführt wird, seine Operation abschließt. Alle sperrenfreien Algorithmen sind frei von Hindernissen.

Die Hindernisfreiheit erfordert nur, dass jeder teilweise abgeschlossene Vorgang abgebrochen und die vorgenommenen Änderungen rückgängig gemacht werden können. Das Verwerfen der gleichzeitigen Unterstützung kann oft zu viel einfacheren Algorithmen führen, die leichter zu validieren sind. Die Aufgabe eines Konfliktmanagers ist es, zu verhindern, dass das System ständig unter Spannung steht.

Einige hindernisfreie Algorithmen verwenden ein Paar von "Konsistenzmarkierungen" in der Datenstruktur. Prozesse, die die Datenstruktur lesen, lesen zuerst einen Konsistenzmarker, lesen dann die relevanten Daten in einen internen Puffer, lesen dann den anderen Marker und vergleichen dann die Marker. Die Daten sind konsistent, wenn die beiden Marker identisch sind. Marker können nicht identisch sein, wenn das Lesen durch einen anderen Prozess unterbrochen wird, der die Datenstruktur aktualisiert. In einem solchen Fall verwirft der Prozess die Daten im internen Puffer und versucht es erneut.

Siehe auch

Verweise

Externe Links