Synchronisation und Datenkonfliktfreiheit

Synchronisationsmechanismen koordinieren nebenläufige Threads, sodass auf gemeinsam genutzte Daten sicher zugegriffen wird, und Datenkonfliktfreiheit ist die Eigenschaft, die nebenläufige Programme vorhersehbar macht.

Definition

Synchronisation ist die Koordination nebenläufiger Aktivitäten, um eine Reihenfolge oder gegenseitigen Ausschluss bei gemeinsam genutzten Ressourcen zu erzwingen, und Datenkonfliktfreiheit ist die Eigenschaft, dass nicht zwei Threads gleichzeitig auf dieselbe Speicherstelle zugreifen, wobei mindestens einer schreibt, ohne dazwischenliegende Synchronisation.

Scope

Dieses Thema behandelt die Mechanismen und Eigenschaften, die den nebenläufigen Zugriff auf gemeinsam genutzten Zustand korrekt machen: gegenseitiger Ausschluss, Sperren (Locks), Semaphore und Monitore, Bedingungsvariablen, Lock-freie und Wait-freie Algorithmen, Transaktionsspeicher, die Happens-Before-Relation und die Erkennung von Datenkonflikten. Es befasst sich mit Verklemmungen (Deadlock), Atomarität und der Disziplin, die erforderlich ist, um Programme datenkonfliktfrei zu halten.

Core questions

• Wie wird gegenseitiger Ausschluss erreicht und welche Gefahren birgt er (Verklemmung, Verhungern)?
• Was unterscheidet Sperr-basierte von Sperr-freien Synchronisationen?
• Wie definiert die Happens-Before-Relation Datenkonflikte?
• Wie können Datenkonflikte automatisch erkannt werden?

Key theories

Gegenseitiger Ausschluss

Dijkstras Lösung für das Problem der nebenläufigen Steuerung etablierte den gegenseitigen Ausschluss als grundlegende Synchronisationsanforderung, die garantiert, dass kritische Abschnitte nicht gleichzeitig ausgeführt werden.

Transaktionsspeicher

Herlihy und Moss schlugen Transaktionsspeicher vor, bei dem Gruppen von Speicheroperationen atomar ausgeführt werden, was eine zusammensetzbare Alternative zu feinkörnigem Locking für den Aufbau nebenläufiger Datenstrukturen bietet.

Happens-Before und dynamische Race-Erkennung

Aufbauend auf Lamports Happens-Before-Relation zeigte der Eraser-Detektor, wie Datenkonflikte dynamisch gefunden werden können, indem eine Locking-Disziplin überprüft wird, was ein Beispiel für die automatisierte Race-Erkennung ist.

Clinical relevance

Eine korrekte Synchronisation ist unerlässlich für zuverlässige nebenläufige und parallele Software; Datenkonflikte verursachen in der Praxis einige der schwer fassbarsten Fehler. Race-Detektoren, Transaktionsspeicher und disziplinierte Synchronisationsmuster sind zentrale Werkzeuge für den Aufbau zuverlässiger Multithread-Systeme.

History

Dijkstras Lösung für den gegenseitigen Ausschluss von 1965 und seine späteren Semaphore begründeten die Synchronisation, gefolgt von Hoare und Brinch Hansens Monitoren. Lamports Happens-Before-Relation von 1978 liegt modernen Race-Definitionen zugrunde; Herlihy und Moss führten 1993 den Transaktionsspeicher ein, und dynamische Race-Detektoren wie Eraser (1997) und spätere Happens-Before-Tools wurden zum Standard für das Debugging von Nebenläufigkeit.

Debates

Sperren (Locks) versus Sperr-freie und transaktionale Ansätze

Entwickler diskutieren traditionelle sperrbasierte Synchronisation, die einfach, aber anfällig für Verklemmungen und schlechte Komposition ist, gegenüber sperrfreien Algorithmen und Transaktionsspeicher, die die Komposition und Fortschrittsgarantien auf Kosten von Komplexität oder Overhead verbessern.

Key figures

• Edsger Dijkstra
• Leslie Lamport
• Maurice Herlihy
• C. A. R. Hoare
• Stefan Savage

Seminal works

• dijkstra1965
• herlihy1993
• savage1997
• lamport1978

Frequently asked questions

Was ist ein Datenkonflikt?

Ein Datenkonflikt tritt auf, wenn zwei Threads gleichzeitig auf dieselbe Speicherstelle zugreifen, mindestens ein Zugriff ein Schreibzugriff ist und die Zugriffe nicht durch Synchronisation geordnet sind, was in den meisten Speichermodellen zu undefiniertem oder unvorhersehbarem Verhalten führt.

Was ist der Unterschied zwischen sperrbasierten und sperrfreien Synchronisationen?

Sperrbasierte Synchronisation verwendet gegenseitigen Ausschluss, sodass nur ein Thread gleichzeitig einen kritischen Abschnitt betritt, während sperrfreie Synchronisation atomare Operationen verwendet, um zu garantieren, dass ein Thread immer Fortschritt macht, ohne Sperren zu halten, wodurch Verklemmungen vermieden werden.