Nicht-blockierende Synchronisation

Grundidee und Bedeutung

Nicht-blockierende Synchronisation (englisch „non-blocking“ oder „lock-free synchronization“) ist eine Technik der Informatik zur Synchronisation paralleler Prozesse, ohne bestimmte Programmabschnitte sperren zu müssen. Sie dient insbesondere dazu, nicht-blockierende Datenstrukturen in parallelen Systemen zu implementieren.

Dabei werden Datenstrukturen ausschließlich durch atomare Operationen verändert. Atomare Operationen werden als unteilbare Vorgänge ausgeführt, sodass während einer Änderung keine Inkonsistenz entsteht.

Blockierende Synchronisation und ihre Nachteile

Bei traditioneller Synchronisation werden Locking-Techniken wie Semaphore und Mutexe verwendet. Sie definieren kritische Abschnitte, in denen nur ein Prozess exklusiven Zugriff auf bestimmte Betriebsmittel erhält. Andere Prozesse, die gleichzeitig in einen solchen Abschnitt eintreten wollen, werden blockiert.

Wichtige Nachteile sind:

• Verklemmung (Deadlock): Gegenseitige Abhängigkeiten zwischen Sperren können dazu führen, dass Prozesse dauerhaft aufeinander warten.
• Effizienzverlust: Die Parallelität sinkt. Nach dem Amdahlschen Gesetz kann die Gesamtleistung dadurch begrenzt werden. Eine feinere Granularität der Sperren, etwa die Sperrung einzelner Elemente statt eines gesamten Objekts, kann den Effekt in bestimmten Fällen reduzieren.
• Fehleranfälligkeit: Kritische Abschnitte müssen korrekt erkannt und gesperrt werden. Das ist nicht trivial und erschwert außerdem Erweiterbarkeit und Wartbarkeit.
• Prioritätsinversion: Prozesse hoher Priorität können durch einfache Prozesse aufgehalten werden, die benötigte Locks halten. Locks auf Systemebene beeinträchtigen im Allgemeinen auch das Echtzeit-Verhalten.

Verfahren, Nachteile und Vorteile

Bei kleinen Änderungen, etwa bei der Referenzzählung oder der Manipulation von Zeigern, können Prozessorbefehle wie Compare-and-swap oder Load-Link/Store-Conditional eingesetzt werden. Umfangreichere Änderungen werden zunächst auf Kopien der ursprünglichen Objekte angewendet. Wurde das Objekt währenddessen von anderen Prozessen verändert, schlägt die Operation zunächst fehl und muss wiederholt werden.

Nicht-blockierende Verfahren sind häufig komplex und schwer verständlich, weil sie atomare Änderungen erfordern. Ihre effiziente und universelle Umsetzung ist weiterhin ein aktuelles Forschungsgebiet. Außerdem kann Verhungern (englisch „starvation“) auftreten: Eine komplexe Änderung wird immer wieder durch kürzere Änderungen ungültig gemacht und kommt dadurch nicht zum Abschluss. Verhungern gilt als Kehrseite der Verklemmung bei blockierender Synchronisation.

Dafür ist das Problem der Prioritätsumkehrung gelöst. Nicht-blockierende Algorithmen sind oft robuster und effizienter; ihre komplexen Implementierungen lassen sich besser kapseln, einmal pro Datentyp umsetzen und anschließend wiederverwenden.

Wait-free und Lock-free

Für das Laufzeitverhalten werden meist zwei Garantiegrade 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 jedoch Verzögerungen auftreten.

Wait-free-Implementierungen sind sehr aufwendig. Sie sind hoch komplex, und Speicher- sowie Zeitbedarf steigen meist mit der Anzahl der beteiligten Prozesse beziehungsweise Threads. Es gibt Implementierungen für einfache Warteschlangen und Stacks, doch das Thema ist weiterhin ein aktuelles Forschungsgebiet. Jeder wait-free-Algorithmus ist zugleich lock-free.

Lock-freie Algorithmen haben sich in der Praxis bereits als Alternative zu Locks etabliert.