Nicht-blockierende SynchronisationNicht-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 TechnikenUm 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 TechnikenNicht-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 SemantikIn 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[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 auchEinzelnachweise
|
Portal di Ensiklopedia Dunia
