Synchronisation: Nebenläufige Prozesse sicher steuern

Eine Race Condition liegt hier vor, wenn die zeitliche Reihenfolge konkurrierender Zugriffe darüber entscheidet, ob das beabsichtigte Ergebnis entsteht. Konkurrierend bedeutet hier: Mehrere Threads greifen auf dieselben Daten zu, und mindestens einer verändert sie.

Im betrachteten Modell besteht eine Änderung aus drei Schritten: Lesen, Rechnen und Zurückschreiben. Jeder Thread rechnet mit seiner eigenen gelesenen Kopie. Beim Zurückschreiben ersetzt sein Ergebnis den gerade gespeicherten Wert. Dieses Modell zeigt eine mögliche Zerlegung; es legt keine genaue Schrittfolge für jede echte Programmanweisung fest.

Verschränkt heißt: Schritte eines anderen Ablaufs liegen zwischen den Schritten einer noch nicht abgeschlossenen Änderung. Lesen zwei Threads denselben Ausgangswert, kann der spätere Schreibzugriff eine bereits gespeicherte Änderung überschreiben. Man spricht dann von einem verlorenen Update, also einer verlorenen Änderung.

Nicht jede Verschränkung führt zu einem Fehler. Schließt ein Thread seine Änderung ab, bevor der andere liest, kann der zweite mit dem neuen Wert weiterrechnen. Ein richtiger Endwert in einem Durchlauf beweist deshalb nicht, dass andere mögliche Abläufe ebenfalls richtig enden.

Ein kritischer Abschnitt greift auf gemeinsame veränderliche Daten zu und braucht Schutz, wenn sich konkurrierende Zugriffe stören können. Gehören mehrere Änderungen zusammen, muss der Schutz die gesamte Änderung umfassen. Dazu gehören auch die Lesezugriffe, deren Ergebnisse für die Änderung gebraucht werden.

Mutex steht für englisch „mutual exclusion“, auf Deutsch „gegenseitiger Ausschluss“. Ein Mutex ist eine Sperre: Ein Thread erwirbt sie vor dem kritischen Abschnitt und gibt sie danach frei. Nur ein Thread kann denselben Mutex gleichzeitig besitzen. Andere Threads, die ihn erwerben wollen, müssen warten. Verschiedene Mutexe schließen ihre Besitzer dagegen nicht gegenseitig aus.

Als konkretes Beispiel betrachten wir die eingebaute Objektsperre der Programmiersprache Java. Sie heißt auch Monitor und verwirklicht das Mutex-Prinzip. Beim Versuch, eine bereits belegte solche Sperre zu erwerben, blockiert ein anderer Thread: Er kann an dieser Stelle erst weiterarbeiten, wenn er sie erhält. Gibt ein Thread die Sperre frei und erwirbt danach ein anderer dieselbe Sperre, werden dem zweiten die vorherigen Änderungen des ersten sichtbar.

Zusammengehörige Änderungen sind damit gegenüber Zugriffen geschützt, die denselben Mutex passend verwenden. Ein Thread, der ein zusammengehöriges Wertepaar liest, muss ihn ebenfalls während des gesamten Lesens halten. Ein Zugriff ohne diese Sperre erhält durch sie weder gegenseitigen Ausschluss noch die genannte Sichtbarkeitsgarantie. Eine Sperre um nur einen Teil der zusammengehörigen Änderung reicht ebenfalls nicht.

Beim bisher betrachteten Java-Monitor blockiert der Erwerb, wenn ein anderer Thread die Sperre besitzt. Ein Spinlock ist dagegen eine Sperre mit aktivem Warten: Der Thread prüft die belegte Sperre wiederholt selbst und verbraucht dabei Rechenzeit. Diese Unterscheidung beschreibt das betrachtete Warteverhalten. Sie behauptet keine einheitliche interne Umsetzung aller Mutexe.

Ein Semaphor verwaltet eine Anzahl von Erlaubnissen. Wir betrachten das Zählmodell des Java-Semaphors und Anfragen nach jeweils einer Erlaubnis. Ein erfolgreicher Erwerb nimmt eine Erlaubnis weg, eine Freigabe fügt eine hinzu. Ist keine verfügbar, blockiert der anfordernde Thread bis zum Erwerb. Die Erlaubnisse werden gezählt; sie sind keine eigenen Gegenstände. Fordert jeder Nutzer vor dem Zugang eine Erlaubnis an und gibt sie nach dem Verlassen genau einmal zurück, begrenzt die Anfangszahl die gleichzeitigen Nutzer.

Eine Ressource ist ein benötigtes Mittel, etwa ein verfügbarer Geräteplatz. Ein Semaphor mit mehreren Erlaubnissen kann den Zugang zu solchen Mitteln begrenzen. Er schützt gemeinsam veränderte Verwaltungsdaten aber nicht von selbst vor störenden Zugriffen. Dafür ist zusätzlicher passender Schutz nötig. Im betrachteten Semaphor-Modell gibt es keinen Besitzer wie beim Mutex; auch ein anderer Thread kann eine Erlaubnis freigeben.

Die folgenden Einsatzgrenzen für Spinlocks beziehen sich auf POSIX-Sperren im Benutzerbereich. POSIX steht für „Portable Operating System Interface“ und bezeichnet einen Standard für Schnittstellen zum Betriebssystem. Das Betriebssystem ist die Grundsoftware, die unter anderem Rechenzeit verteilt. Benutzerbereich meint normalen Programmcode außerhalb des zentralen Betriebssystemteils.

In diesem Kontext sollen die meisten Programme einen Mutex verwenden. Spinlocks sind vor allem für besonders abgestimmte Programme mit geeigneten Echtzeitregeln vorgesehen. Das sind besondere Regeln des Betriebssystems für die Zuteilung von Rechenzeit. Erhält der Besitzer einer Sperre vorübergehend keine Rechenzeit, können andere Threads ihre Zeit mit erfolglosem Prüfen verbrauchen. Eine feste Obergrenze der Wartezeit ist nicht zugesichert. Auch ein Thread mit höherem Vorrang kann auf einen Besitzer mit niedrigerem Vorrang warten. Kurze kritische Abschnitte allein sind deshalb kein ausreichender Grund für einen Spinlock.

Bei einem Deadlock warten mindestens zwei Threads dauerhaft aufeinander. Unter den gegebenen Regeln kann keiner den nächsten nötigen Schritt ausführen. Beispielsweise kann jeder eine Sperre behalten und auf eine zweite warten, die der andere besitzt. Ohne einen Eingriff von außen endet dieses gegenseitige Warten dann nicht.

Ein Deadlock kann mit blockierendem Warten auftreten. Bei Spinlocks ist aber auch dauerhaftes aktives Prüfen möglich: Die Threads verbrauchen Rechenzeit und warten trotzdem erfolglos aufeinander. Rechenaktivität allein schließt einen Deadlock deshalb nicht aus.

Bei einem Livelock reagieren Threads fortwährend aufeinander und führen dabei weitere Aktionen aus. Gerade diese gegenseitigen Reaktionen verhindern den angestrebten Fortschritt. Sie warten also nicht bloß dauerhaft auf die nächste nötige Handlung des jeweils anderen.

Verhungern bedeutet hier: Ein Thread bekommt über lange Zeit keinen ausreichenden Zugang zu einer benötigten Ressource und kommt deshalb nicht voran. Andere nutzen diese Ressource weiter. Eine kurze Wartezeit allein ist noch kein Verhungern. Gegenseitiger Ausschluss garantiert für sich genommen keinen regelmäßigen Zugang für jeden Thread.

Prüfe deshalb die Ursache des fehlenden Fortschritts: Besteht dauerhaftes gegenseitiges Warten, fortgesetztes gegenseitiges Reagieren oder ausbleibender Ressourcenzugang für einen Thread?