Synchronisation: Nebenläufige Prozesse sicher steuern

Stell dir zwei Threads vor, die dasselbe Bankguthaben verändern. Beide können grundsätzlich korrekt programmiert sein. Trotzdem kann ein falscher Endwert entstehen, wenn ihre einzelnen Schritte ungünstig ineinandergreifen.

Nebenläufig bedeutet: Die Arbeitsschritte mehrerer Prozesse können sich zeitlich überlappen oder abwechseln. Entscheidend ist nicht, ob tatsächlich mehrere Prozessorkerne gleichzeitig rechnen. Schon eine verschachtelte Ausführung auf einem Kern kann Synchronisationsfehler auslösen.

Synchronisation erfüllt verschiedene Aufgaben:

• Sie schützt gemeinsame Daten vor widersprüchlichen Änderungen.
• Sie teilt begrenzte Ressourcen wie Geräte zu.
• Sie ordnet Ereignisse, wenn ein Prozess auf einen anderen warten muss.
• Sie unterstützt die Übergabe von Informationen zwischen Prozessen.

Dateisynchronisation verfolgt ein anderes Ziel: Sie bringt Datenbestände mehrerer Speicherorte auf einen gemeinsamen Stand. Auf dieser Seite geht es dagegen um die Koordination nebenläufiger Prozesse.

Ausgangswert eines Kontos: 3000 Euro. Zwei Prozesse führen fast gleichzeitig eine Abhebung aus:

• Prozess A möchte 500 Euro abheben.
• Prozess B möchte 2300 Euro abheben.

Jede Abhebung besteht aus mehreren Schritten: Guthaben lesen, Rest berechnen, Rest prüfen und neuen Wert schreiben.

Das Überschreiben einer zwischenzeitlichen Änderung heißt Lost Update, also verlorene Aktualisierung. Der Fehler ist schwer zu finden, weil andere Ausführungsreihenfolgen ein korrektes Ergebnis liefern können.

Bei einer vollständigen seriellen Ausführung A vor B oder B vor A bleibt jeweils das korrekte Guthaben von 200 Euro übrig. Die einzelnen Abhebungen sind also nicht grundsätzlich falsch. Problematisch ist ihre ungeschützte Verschachtelung.

Die Folge „lesen, berechnen, prüfen, schreiben“ greift auf den gemeinsamen Zustand guthaben zu. Sie darf nicht von einer zweiten Abhebung überlappt werden.

Der gesamte zusammengehörige Vorgang muss atomar erscheinen: Für andere Prozesse wirkt er wie ein einziger unteilbarer Schritt. Nur den Schreibbefehl zu schützen reicht beim Bankbeispiel nicht. Beide Prozesse könnten den gleichen alten Wert schon vorher gelesen haben.

Eine typische Struktur sieht so aus:

text enter_cs(Ressource) gemeinsamen Wert lesen neuen Wert berechnen und prüfen gemeinsamen Wert schreiben leave_cs(Ressource)

enter_cs wartet, bis der geschützte Bereich frei ist. leave_cs gibt ihn anschließend wieder frei.

Eine gute Steuerung kritischer Abschnitte muss mehrere Anforderungen erfüllen:

1. Gegenseitiger Ausschluss (Mutual Exclusion): Höchstens ein Prozess befindet sich im geschützten Abschnitt.
2. Fortschritt: Ein Eintrittswunsch wird schließlich erfüllt. Es entsteht weder Deadlock noch dauerhaftes Verhungern.
3. Unabhängigkeit: Prozesse außerhalb des kritischen Abschnitts behindern den darin arbeitenden Prozess nicht unnötig.
4. Keine Geschwindigkeitsannahme: Die Lösung darf nicht davon abhängen, welcher Prozess normalerweise schneller ist.

Nicht jeder Synchronisationsmechanismus wartet auf dieselbe Weise. Die erwartete Wartezeit und die Anzahl verfügbarer Ressourcen helfen bei der Auswahl.

Mutex: genau ein Prozess im Abschnitt

Ein Mutex schützt einen kritischen Abschnitt durch gegenseitigen Ausschluss. Ein Prozess sperrt ihn vor dem Zugriff und gibt ihn danach wieder frei. Andere Prozesse müssen warten, solange die Sperre belegt ist.

Für die Abhebung genügt ein gemeinsamer Mutex um die vollständige Lese-Änderungs-Schreib-Folge. Dadurch sieht die zweite Abhebung erst den bereits aktualisierten Kontostand.

Semaphor: blockieren und Ressourcen zählen

Ein binärer Semaphor kann einen einzelnen kritischen Abschnitt schützen. Ein zählender Semaphor erlaubt dagegen bis zu einer festgelegten Anzahl gleichzeitiger Nutzungen. Bei einem Anfangswert von 3 könnten beispielsweise höchstens drei Prozesse gleichzeitig drei gleichartige verfügbare Ressourcen belegen.

Die Warteoperation wird oft P(), wait() oder down() genannt. Die Freigabe heißt unter anderem V(), signal() oder up(). Ist kein Eintritt möglich, kann der wartende Prozess blockiert werden, sodass ein anderer Prozess Rechenzeit erhält.

Spinlock: aktiv auf eine kurze Freigabe warten

Ein Spinlock prüft die Sperre fortlaufend. Dieses aktive Warten verbraucht Rechenzeit, während der Prozess keinen fachlichen Fortschritt macht. Das atomare Setzen der Sperre benötigt Hardwareunterstützung; getrenntes Prüfen und anschließendes Setzen wäre erneut durch eine Race Condition gefährdet.

In der zugrunde liegenden Betriebssystemdarstellung sind Spinlocks für sehr kurze Abschnitte im Kernel vorgesehen. Für längere oder unbekannt lange Wartezeiten sind blockierende Mechanismen geeigneter.

Gegenseitiger Ausschluss allein genügt nicht. Prozesse müssen auch weiterkommen können.

Ein typisches Muster ist eine zyklische Wartebeziehung: Prozess A hält Ressource 1 und wartet auf Ressource 2. Prozess B hält Ressource 2 und wartet auf Ressource 1. Keiner kann fortfahren.

Das kann passieren, wenn zwei Prozesse bei jedem Konflikt gleichzeitig zurückweichen und es anschließend wieder gleichzeitig versuchen. Im Unterschied zum Deadlock wird weiter gerechnet, aber die eigentliche Aufgabe bleibt unerledigt.

Verhungern bedeutet: Ein bestimmter wartender Prozess kommt dauerhaft nicht zum Zug, obwohl andere Prozesse weiterhin Fortschritt machen. Eine Leserbevorzugung kann beispielsweise einen Schreiber immer wieder zurückstellen, wenn fortlaufend neue Leser eintreffen.

Du beherrschst das Thema, wenn du bei einem verschachtelten Ablauf zuerst den gemeinsamen Zustand und den kritischen Abschnitt markierst, danach einen passenden Schutz auswählst und schließlich prüfst, ob alle wartenden Prozesse noch Fortschritt machen können.