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 Bearbeiten
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.
Nicht-blockierende Techniken Bearbeiten
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:
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 Bearbeiten
In der Literatur werden zumeist zwei Grade der Garantien über das Laufzeitverhalten nicht-blockierender Algorithmen unterschieden.
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 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 Bearbeiten
Einzelnachweise Bearbeiten
- 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