Nebenläufigkeit in der Informatik verstehen

Stell dir einen Musikplayer vor: Er spielt Musik ab, reagiert auf deine Eingaben und lädt weitere Titel. Diese Tätigkeiten können sich zeitlich überlappen. Genau das ist die Grundidee der Nebenläufigkeit.

Parallelität bezeichnet in der engeren Bedeutung die echte gleichzeitige Ausführung auf mehreren Recheneinheiten. Nebenläufigkeit beschreibt dagegen vor allem die Organisation mehrerer möglicher Abläufe.

Ein Prozess ist ein laufendes Programm mit eigenen verwalteten Ressourcen. Ein Thread ist ein Ausführungsablauf innerhalb eines Prozesses. Mehrere Threads desselben Prozesses können gemeinsame Objekte und denselben Speicher nutzen.

Nicht jeder Ablauf lässt sich beliebig überlappen. Benötigt Schritt B das Ergebnis von Schritt A, muss A zuerst abgeschlossen sein. Unabhängige Schritte sind dagegen parallelisierbar, wenn ihre Reihenfolge das Ergebnis nicht verändert.

Gemeinsam genutzte Daten werden gefährlich, wenn mehrere Threads sie verändern. Eine scheinbar einfache Anweisung wie zaehler = zaehler + 1 kann intern aus drei Schritten bestehen:

1. Wert lesen.
2. Eins addieren.
3. Ergebnis zurückschreiben.

Diese zusammengehörenden Schritte sind nicht automatisch atomar. Atomar bedeutet, dass andere Threads keine Zwischenzustände beobachten oder dazwischen eingreifen können.

Die Reihenfolge zeigt den Fehler als einfache Ablaufspur. In einem Sequenzdiagramm würdest du dieselben Lese-, Rechen- und Schreibschritte zeitlich untereinander anordnen.

Der Teil eines Programms, in dem ein Thread auf gemeinsam genutzte Daten oder Betriebsmittel zugreift, heißt kritischer Abschnitt. Im Zählerbeispiel gehören Lesen, Erhöhen und Zurückschreiben gemeinsam in diesen Abschnitt.

Eine Sperre oder ein Lock sorgt typischerweise dafür, dass nur ein Thread gleichzeitig den geschützten Abschnitt ausführt. Dieser gegenseitige Ausschluss wird auch Mutex genannt.

Der sichere Ablauf lautet:

1. Sperre erwerben.
2. Gemeinsamen Wert lesen, verändern und zurückschreiben.
3. Sperre zuverlässig freigeben.

In Java kann eine synchronized-Methode den Zugriff auf ein Objekt gegenseitig ausschließen. Ein expliziter Lock wird mit lock() erworben und mit unlock() freigegeben. Die Freigabe sollte auch bei einem Fehler sichergestellt sein.

Weitere Mechanismen erfüllen verwandte Aufgaben:

• Ein Semaphor verwaltet mit einem Zähler, wie viele gleichzeitige Zugriffe erlaubt sind.
• Ein Monitor kapselt gemeinsame Daten und die synchronisierten Operationen darauf.
• Ein Read-Write-Lock kann mehrere gleichzeitige Lesezugriffe erlauben, während ein Schreibzugriff exklusiv bleibt.

Synchronisation garantiert nicht automatisch ein korrektes Gesamtsystem. Zu kleine kritische Abschnitte lassen Race Conditions zu. Zu große oder widersprüchlich geordnete Sperrbereiche können unnötige Wartezeiten oder Deadlocks erzeugen.

Eine Sperre lässt einen Thread warten, bis ein anderer sie freigibt. Problematisch wird es, wenn mehrere Threads in einem geschlossenen Kreis aufeinander warten.

Für einen Deadlock müssen die vier Coffman-Bedingungen gemeinsam vorliegen:

1. Exklusiver Zugriff: Eine Ressource kann nicht gleichzeitig von allen genutzt werden.
2. Halten und Warten: Ein Thread hält bereits eine Ressource und wartet auf eine weitere.
3. Kein Entzug: Eine Ressource wird nicht zwangsweise entzogen, sondern vom Besitzer freigegeben.
4. Zyklisches Warten: Es gibt eine geschlossene Kette wartender Threads.

Die vier Bedingungen zeigen, wann ein Deadlock möglich ist. Sie bedeuten nicht, dass jede Programmausführung tatsächlich in einem Deadlock endet.

Ein Betriebsmittelzuteilungsgraph stellt Threads, Ressourcen sowie Halte- und Anforderungsbeziehungen dar. Ein Kreis im Graphen macht zyklisches Warten sichtbar. Bei mehreren Exemplaren einer Ressource muss zusätzlich geprüft werden, ob der Kreis wirklich eine Verklemmung verursacht.

Eine häufige Gegenmaßnahme ist eine feste globale Sperrreihenfolge: Wenn alle Threads zuerst L1 und danach L2 erwerben, kann der gezeigte Wartekreis nicht entstehen. Auch kürzeres Halten, das gemeinsame Anfordern benötigter Ressourcen oder der Entwurf ohne eine der Coffman-Bedingungen kann Deadlocks verhindern.

Aktives Warten, auch Busy Waiting genannt, prüft eine Bedingung ständig in einer Schleife. Hält der wartende Thread dabei die benötigte Sperre, kann er gerade den Thread aussperren, der die Bedingung ändern müsste.

Beim Bankkonto wäre das fatal: withdraw wartet bei zu geringem Guthaben, behält aber die Kontosperre. deposit kann die Sperre nicht erhalten und deshalb kein Geld einzahlen.

Kontrolliertes Warten gibt die Sperre während der Wartezeit frei. In Java bewirkt wait(), dass der Thread wartet und die Objektsperre freigibt. Nach einer Zustandsänderung kann notifyAll() die wartenden Threads benachrichtigen. Anschließend konkurrieren sie erneut um die Sperre und prüfen die Bedingung nochmals. Deshalb wird die Bedingung mit einer Schleife geprüft, nicht nur einmal.

Zum Testen reicht ein einzelner erfolgreicher Durchlauf nicht. Sinnvolle Prüfungen umfassen verschiedene Ablaufreihenfolgen und kontrollierte Grenzfälle:

• Verbraucher startet bei leerer Queue und wartet.
• Erzeuger füllt die Queue vollständig und wartet vor dem nächsten Element.
• Nach einer Entnahme kann der Erzeuger fortfahren.
• Kein Element geht verloren und kein Element wird doppelt verarbeitet.

Die zentrale Entwurfsfrage lautet: Welche Schritte dürfen sich überlappen, und welche müssen als unteilbare oder geordnete Einheit behandelt werden? Erst wenn du gemeinsame Daten, Abhängigkeiten und Ressourcen erkennst, kannst du die passende Synchronisation wählen.

Wenn du einen neuen nebenläufigen Ablauf beurteilst, gehe in dieser Reihenfolge vor:

1. Markiere gemeinsam genutzte veränderliche Daten und Ressourcen.
2. Zerlege Zugriffe in ihre tatsächlichen Einzelschritte.
3. Suche nach fehlerhaften Verschachtelungen und Race Conditions.
4. Lege den kleinsten vollständigen kritischen Abschnitt fest.
5. Prüfe bei mehreren Sperren alle vier Coffman-Bedingungen.
6. Teste verschiedene Reihenfolgen sowie leere, volle und blockierte Zustände.