Nebenläufigkeit in der Informatik verstehen

Ein Prozessor führt die Arbeitsschritte eines Programms aus. Ein Rechenkern ist eine Ausführungseinheit des Prozessors; ein Prozessor kann mehrere Kerne besitzen. In unserem Ablaufmodell führt ein einzelner Kern zu einem Zeitpunkt einen Schritt eines Threads aus. Er kann zwischen Threads wechseln, bevor deren Aufgaben abgeschlossen sind. Das wirkt gleichzeitig und heißt hier scheinbare Nebenläufigkeit. Auf mehreren Kernen können Schritte verschiedener Threads tatsächlich gleichzeitig ausgeführt werden. Dafür wird auch die Bezeichnung echte Nebenläufigkeit verwendet.

Die Begriffe werden unterschiedlich weit gebraucht: Im engeren Sprachgebrauch bezeichnet Nebenläufigkeit die Organisation überlappender Abläufe. Parallelität bezeichnet dann deren tatsächlich gleichzeitige Ausführung. Nebenläufigkeit setzt nach diesem Verständnis keine mehreren Kerne voraus.

Ein Zugriff auf einen gemeinsamen Wert kann mehrere Schritte umfassen: den Wert lesen, eine eigene Kopie verändern und das Ergebnis zurückschreiben. Zurückschreiben ersetzt den bisherigen gemeinsamen Wert; es addiert ihn nicht zum neuen Wert. Zwei Threads können denselben alten Wert lesen und anschließend mit getrennten Kopien weiterrechnen. Schreibt einer später sein Ergebnis zurück, kann er das Ergebnis des anderen überschreiben. Dafür genügt ein Wechsel zwischen Threads auf einem einzigen Kern.

Die folgenden Abläufe sind ausdrücklich vereinfachte Modelle mit vollständig angegebenen Schritten. Sie beschreiben keine bestimmte Programmiersprache. Der gezeigte fehlerhafte Ablauf ist eine Möglichkeit: Bei anderer Reihenfolge können dieselben Änderungen auch ohne verlorenen Beitrag enden.

Ein kritischer Abschnitt ist ein Teil eines Ablaufs, in dem ein ungeschützter Zugriff auf gemeinsame Daten zu einem fehlerhaften Zustand führen kann. Beim Lesen, Verändern und Zurückschreiben eines gemeinsamen Wertes gehört der gesamte zusammenhängende Ablauf zum Schutzbereich. Wird bloß das Lesen oder bloß das Schreiben geschützt, können zwei Threads weiterhin mit demselben alten Wert rechnen.

Ein Mutex ist eine Sperre für wechselseitigen Ausschluss: Unter den Threads, die dieselbe Sperre verwenden, darf jeweils ein Thread den geschützten Abschnitt ausführen. Ein anderer Thread muss auf die Freigabe warten. Blockiert zu sein bedeutet hier, an dieser Stelle nicht weiterarbeiten zu können, bis die benötigte Freigabe vorliegt. Alle beteiligten Zugriffe müssen dieselbe Schutzregel beachten. Der Mutex verhindert keinen Wechsel des laufenden Threads. Er verhindert, dass ein anderer Thread inzwischen denselben geschützten Abschnitt betritt.

Ein Semaphor verwaltet Freigaben. Wir verwenden dafür die Operationen P und V. P reserviert eine verfügbare Freigabe; ist keine verfügbar, blockiert der Aufrufer. V gibt eine Freigabe hinzu und kann dadurch einen Wartenden wieder bereit machen. Die Prüfung und Reservierung bei P werden als unteilbarer Schritt behandelt: Zwei Threads können nicht dieselbe Freigabe erhalten.

Zum Schutz eines kritischen Abschnitts kann ein binärer Semaphor verwendet werden. Binär bedeutet hier, dass für den Schutz höchstens eine Freigabe vorhanden ist. Er startet mit einer Freigabe. Jeder Thread führt vor dem gesamten Abschnitt P und danach genau einmal V aus. Mit zwei anfänglichen Freigaben könnten zwei Threads eintreten; damit wäre dieser wechselseitige Ausschluss nicht erreicht. Unsere Modelle setzen voraus, dass ein eingetretener Thread seinen Abschnitt beendet und die Sperre anschließend freigibt.

Ein Deadlock, auch Verklemmung genannt, ist eine festgefahrene zyklische Wartesituation. Zyklisch bedeutet: Die Abhängigkeiten bilden einen geschlossenen Kreis. Jeder beteiligte Thread wartet auf eine Ressource, die ein anderer beteiligter Thread festhält. Eine Ressource, auch Betriebsmittel genannt, ist etwas, das ein Thread für seine Arbeit benötigt. In unserem Modell sind das exklusiv gehaltene Sperren. Exklusiv bedeutet, dass eine Sperre jeweils einem Besitzer zugeteilt ist.

Die vier Coffman-Bedingungen beschreiben Voraussetzungen für eine solche Verklemmung. Erstens gilt wechselseitiger Ausschluss: Eine benötigte Ressource kann nicht gleichzeitig von mehreren Threads genutzt werden. Zweitens gilt Halten und Warten: Ein Thread behält eine Ressource, während er auf eine weitere wartet. Drittens gibt es keinen erzwungenen Entzug: Eine gehaltene Ressource wird ihrem Besitzer nicht gegen dessen Willen weggenommen. Viertens besteht kreisförmiges Warten: Die Warteabhängigkeiten schließen sich zu einem Kreis.

Ausgedachtes Modell: Thread M hält die Sperre für eine Bilddatei und wartet auf die Sperre für eine Tondatei. Thread N hält die Tonsperre und wartet auf die Bildsperre. Beide geben ihre Sperren erst frei, nachdem sie beide Dateien bearbeiten konnten. Die Sperren sind exklusiv und werden nicht entzogen. Damit stehen beide fest. Ein bloßer Wechsel der Rechenzeit löst die Sperren nicht und unterbricht diesen Wartekreis nicht.

Die Bedingungen beschreiben die Möglichkeit einer Verklemmung; eine gefährliche Anforderungsweise führt nicht bei jeder zeitlichen Anordnung dazu. Bearbeitet M beide Dateien und gibt die Sperren frei, bevor N beginnt, entsteht dieser Kreis nicht. Für das Modell mit diesen beiden Sperren verhindert eine einheitliche Anforderungsreihenfolge den Kreis: Beide Threads fordern zuerst die Bildsperre und danach die Tonsperre an. Auch das Freigeben einer gehaltenen Sperre vor dem Warten kann einen vorhandenen Wartekreis durchbrechen. Zusätzliche Anforderungen geben dagegen keine schon gehaltene Sperre frei.

Ein Erzeuger stellt Elemente bereit, ein Verbraucher entnimmt sie zur weiteren Verarbeitung. Beide nutzen einen gemeinsamen Puffer. Ein Puffer ist hier eine Datenstruktur, also eine geordnete Sammlung von Daten, mit einer begrenzten Zahl von Ablageplätzen. Ein Verbraucher darf kein Element aus einem leeren Puffer entnehmen. Ein Erzeuger darf kein Element in einen vollen Puffer einfügen. In diesen Fällen sollen die Threads blockieren, statt mit einem ungültigen Zugriff fortzufahren.

Wir verwenden drei gemeinsame Semaphore. frei verwaltet Freigaben für freie Plätze, belegt Freigaben für verfügbare Elemente und schutz den wechselseitigen Ausschluss beim Verändern des Puffers. Für einen anfangs leeren Puffer mit drei Plätzen startet frei mit drei Freigaben, belegt mit null und schutz mit einer. P reserviert die jeweilige Freigabe. Während eine Operation noch läuft, können Freigaben bereits reserviert sein; die Zähler müssen dann nicht genau der sichtbaren Belegung entsprechen.

Der Erzeuger reserviert zuerst mit P(frei) einen Platz. Erst danach erwirbt er mit P(schutz) den Schutz, fügt sein Element ein, gibt schutz frei und meldet mit V(belegt) ein verfügbares Element. Der Verbraucher reserviert zuerst mit P(belegt) ein Element. Danach erwirbt er schutz, entnimmt das Element, gibt schutz frei und meldet mit V(frei) einen freien Platz. Das Einfügen meldet somit ein Element, das Entnehmen einen freien Platz.

Auf ein Element oder einen freien Platz wird vor dem Erwerb von schutz gewartet. Hielte ein Verbraucher beim Warten auf ein Element bereits schutz fest, könnte ein Erzeuger den Schutz zum Einfügen nicht erhalten. Ein Signal kann einen passenden Wartenden wieder bereit machen. Aufwecken garantiert aber keine sofortige Ausführung: Der Thread braucht anschließend Rechenzeit und muss weitere benötigte Sperren erwerben.

Bei unbegrenzter Pufferkapazität entfällt das Warten auf freie Plätze; der Semaphor frei wird dann nicht benötigt. Sind die Änderungen der Datenstruktur tatsächlich keine kritischen Aktionen, kann schutz entfallen. In unserem mehrschrittigen Änderungsmodell ist dieser Schutz erforderlich. Auch ein unbegrenzter Puffer kann leer sein, sodass Verbraucher weiterhin auf Elemente warten müssen.