Nebenläufigkeit & Race Conditions

1965 fasste Edsger Dijkstra in Cooperating Sequential Processes zum ersten Mal das Problem, an dem sich das nebenläufige Rechnen bis heute abarbeitet: Was passiert, wenn sich zwei oder mehr sequentielle Prozesse eine Ressource teilen? Sein Gedankenexperiment — die speisenden Philosophen, fünf an einem runden Tisch, jeder auf beide Nachbargabeln angewiesen — veranschaulicht sechzig Jahre später noch immer die ganze Fehlerfamilie, die Nebenläufigkeit erzeugt: Deadlock, Aushungern, Livelock, Race Conditions. Die weiter reichende These stammt von Dijkstra, Tony Hoare und vor allem von Leslie Lamport, dessen Aufsatz Time, Clocks, and the Ordering of Events in a Distributed System von 1978 zu den meistzitierten des Fachs zählt: Nebenläufig zu programmieren ist qualitativ schwerer als sequentiell, weil die Fehler sich nicht reproduzieren lassen, am Timing hängen und im Produktivbetrieb auftauchen, nachdem sie jeden Test überstanden haben.

Im Kern steht der Nichtdeterminismus: Derselbe Code kann bei zwei Läufen verschiedene Ergebnisse liefern, je nachdem, wie die Threads ineinandergreifen — und die Zahl der möglichen Verschränkungen wächst exponentiell mit der Zahl der Operationen, sodass Testen sie grundsätzlich nicht ausschöpfen kann. Der Musterfehler ist die Race Condition: Zwei Threads greifen auf denselben Zustand zu, und wer zuerst ankommt, entscheidet das Ergebnis. Einen Zähler zu erhöhen ist eben nicht atomar — lesen, eins addieren, schreiben können sich so verzahnen, dass zwei gleichzeitige Inkremente den Zähler statt um zwei nur um eins anheben. Moderne Prozessoren verschärfen die Lage, weil sie Speicherzugriffe aus Geschwindigkeitsgründen umordnen: Was ein Thread schreibt, erreicht einen anderen womöglich in anderer Reihenfolge. Erst das Java-Speichermodell (2004) und das C++11-Speichermodell haben festgeschrieben, worauf sich Programmierer überhaupt verlassen dürfen; davor war das Gelände sumpfig. Gezähmt wird Nebenläufigkeit aus mehreren Traditionen heraus: Locks sichern kritische Abschnitte, lassen sich aber schlecht kombinieren — zwei für sich korrekte Bausteine können zusammen verklemmen; atomare Operationen wie Compare-and-Swap tragen die lockfreien Algorithmen; und die Modelle des Nachrichtenaustauschs — das Actor-Modell von Erlang, Goroutines und Channels in Go — ersetzen den geteilten Speicher durch Kommunikation, unter der Losung Nicht durch geteilten Speicher kommunizieren, sondern durch Kommunikation Speicher teilen. Zwei jüngere Ansätze haben die Lage verändert: CRDTs (konfliktfreie replizierte Datentypen) sind Datenstrukturen, deren nebenläufige Änderungen sich konfliktfrei zusammenführen lassen — sie tragen einen großen Teil des heutigen gemeinsamen Bearbeitens: die vielen Editoren auf Yjs- oder Automerge-Basis, dazu Verwandte wie Figma, wo am Ende der Server die Reihenfolge festlegt. Und der Borrow-Checker von Rust stellt schon beim Übersetzen sicher, dass es zu keinem Datum mehr als eine veränderbare Referenz gibt; Data Races sind damit konstruktiv ausgeschlossen. Verteilte Systeme weiten die Nebenläufigkeit auf viele Maschinen aus und nehmen das Versagen hinzu — verlorene Nachrichten, abgestürzte Knoten, zerschnittene Netze. Das CAP-Theorem (Brewer 2000, bewiesen von Gilbert und Lynch 2002) besagt, dass sich von Konsistenz, Verfügbarkeit und Partitionstoleranz höchstens zwei zugleich haben lassen; die FLP-Unmöglichkeit (Fischer-Lynch-Paterson 1985), dass in einem asynchronen System schon ein einziger fehlerhafter Prozess Konsens ausschließt. Scharf und ernüchternd stecken diese Sätze ab, wozu verteilte Systeme überhaupt fähig sind.