Nicht-blockierende Synchronisation
Nicht-blockierende Synchronisation (englisch non-blocking oder auch lock-free synchronization) ist eine Technik in der Informatik, um parallele Prozesse zu synchronisieren, ohne dabei bestimmte Programmabschnitte sperren zu müssen. Insbesondere dient sie zur Implementierung von nicht-blockierenden Datenstrukturen in parallelen Systemen.
Blockierende Techniken
Um Inkonsistenzen im Ablauf von parallelen Prozessen, die auf gemeinsamen Speicher zugreifen, zu vermeiden, werden traditionell Locking-Techniken wie Semaphore und Mutexe eingesetzt, die kritische Abschnitte definieren, in denen nur ein Prozess exklusiven Zugriff auf bestimmte Betriebsmittel erhält. Wollen andere Prozesse gleichzeitig in einen kritischen Abschnitt eintreten, werden sie blockiert.
Dieser Ansatz hat eine Reihe von Nachteilen.
- Verklemmung
- Es kann zu Verklemmungen (deadlock) kommen, wenn es gegenseitige Abhängigkeiten zwischen Sperren gibt.
- Effizienzverlust
- Die Parallelität des Programms wird verringert (siehe Amdahlsches Gesetz). In bestimmten Fällen kann dieser Effekt durch eine feinere Granularität der Sperren reduziert werden (z. B. Sperren des Zugriffs auf einzelne Elemente eines Objektes, statt Sperrung des gesamten Objekts).
- Fehleranfälligkeit
- Die korrekte Identifikation und Sperrung der kritischen Abschnitte ist nicht trivial und dadurch fehleranfällig. Auch die Erweiterbarkeit und Wartbarkeit des Programms wird erschwert.
- Prioritätsinversion
- Betrachtet man das gesamte System, kommt das Problem der Prioritätsinversion hinzu, wobei Prozesse hoher Priorität von einfachen Prozessen durch gehaltene Locks aufgehalten werden können. Locks auf Systemebene beeinträchtigen im Allgemeinen auch das Echtzeit-Verhalten des Systems.
Nicht-blockierende Techniken
Nicht-blockierende Synchronisationtechniken umgehen die Definition von kritischen Abschnitten dadurch, dass sie zu keinem Zeitpunkt Inkonsistenzen erzeugen. Datenstrukturen werden dabei ausschließlich durch atomare Operationen modifiziert. Sind die Änderungen klein, wie in der Referenzzählung oder bei der Manipulation von Zeigern, können Prozessor-Befehle wie Compare-and-swap oder Load-Link/Store-Conditional verwendet werden. Sind die Modifikationen umfangreicher, werden sie zunächst auf Kopien der ursprünglichen Objekte durchgeführt. Wurde das Objekt während der Erstellung der Modifikation von anderen Prozessen verändert, schlägt die Operation zunächst fehl und muss wiederholt werden.
Nachteile dieser Techniken sind:
- Komplexität
- Die Notwendigkeit von atomaren Änderungen führt häufig zu komplexen und schwer verständlichen Algorithmen. Die Implementierung effizienter und universeller nicht-blockierender Datenstrukturen ist ein aktuelles Forschungsgebiet.
- Verhungern
- Durch die Möglichkeit des Fehlschlags kann es zu einer Situation kommen, in der eine komplexe Änderung immer wieder von kürzeren Änderungen ungültig gemacht wird und dadurch „verhungert“ (engl. starvation). Das Verhungern ist die Kehrseite der Verklemmung in der blockierenden Synchronisation.
Im Gegenzug ist das Problem der Prioritätsumkehrung aufgelöst, und die Algorithmen sind oft robuster und effizienter. Die komplexen und schwer wartbaren Algorithmen sind zudem besser gekapselt. Sie müssen nur einmal für jeden Datentyp implementiert werden und können wiederverwendet werden.
Wait-free und Lock-free Semantik
In der Literatur werden zumeist zwei Grade der Garantien über das Laufzeitverhalten nicht-blockierender Algorithmen unterschieden.
- Wait-free
- Alle Operationen aller beteiligten Prozesse werden durchgeführt, unabhängig von den parallel laufenden Prozessen im System.
- Lock-free
- Keine Operation wird aufgehalten, durch mögliche Überschneidungen mit anderen Prozessen können aber Verzögerungen auftreten.
Der Aufwand für wait-free Implementierungen ist allerdings sehr hoch. Zum einen ist die Implementierung hoch komplex, zum anderen steigt der Speicher- und Zeitbedarf solcher Algorithmen meist mit der Anzahl der beteiligten Prozesse bzw. Threads. Es existieren Implementierungen für einfache Warteschlangen[1] und Stacks, das Thema ist aber noch ein aktuelles Forschungsgebiet. Alle wait-free Algorithmen sind auch lock-free.
Die Lock-freien Algorithmen haben sich in der Praxis aber schon als Alternative zu Locks etabliert.
Siehe auch
Einzelnachweise
- Alex Kogan and Erez Petrank. 2011. Wait-free queues with multiple enqueuers and dequeuers. In Proceedings of the 16th ACM symposium on Principles and practice of parallel programming (PPoPP '11). ACM, New York, NY, USA, S. 223–234. doi:10.1145/1941553.1941585