Erzeuger-Verbraucher-Problem einfach erklärt

Erzeuger legen Elemente in eine gemeinsame Datenstruktur, den Puffer. Verbraucher entnehmen Elemente und verarbeiten sie. Bei beschränkter Kapazität kann der Puffer zum Beispiel ein Ringpuffer sein. Es gibt mindestens einen Erzeuger und mindestens einen Verbraucher.

Der Zugriff auf den Puffer ist ein kritischer Abschnitt. Legt ein Erzeuger gerade ein Element ab oder entfernt ein Verbraucher gerade eines, darf kein anderer Prozess diesen Vorgang unterbrechen und ebenfalls den Puffer ändern. Sonst kann der Puffer in einen inkonsistenten Zustand geraten. Das zeigt schon ein einfacher Zähler: Wenn zwei Threads zeitlich verschränkt arbeiten und beide denselben alten Wert lesen, geht ein Erhöhen verloren. Dabei nehmen wir an, dass das Erhöhen nicht in einem einzigen unteilbaren Schritt möglich ist.

Zusätzlich müssen Prozesse manchmal warten. Ist der Puffer voll, darf ein Erzeuger nichts ablegen. Ist er leer, kann ein Verbraucher nichts entnehmen. Solche Prozesse werden blockiert und wieder aufgeweckt, wenn sich der Zustand des Puffers geändert hat. Ein Vergleich aus der Fabrik: Ist das Zwischenlager voll, muss die vorgelagerte Produktionsstation stoppen.

Ein Semaphor besteht aus einer Ganzzahl und zwei unteilbaren Operationen: „Reservieren/Probieren“ heißt P, „Freigeben“ heißt V. Bei P wird der Zähler um 1 verringert, bei V um 1 erhöht. Der Zähler darf nicht unter 0 fallen: Wer bei Zählerstand 0 reserviert, wartet, bis ein anderer Prozess freigibt. Es gibt auch Implementierungen, die ins Negative zählen.

In den meisten Lösungsbeschreibungen des Erzeuger-Verbraucher-Problems werden Semaphore verwendet. Sie schützen den kritischen Abschnitt und lassen die Prozesse zusammenarbeiten. Alle drei Semaphore werden von allen Prozessen gemeinsam genutzt.

Der binäre Semaphor mutex schützt Änderungen am Puffer. Der zählende Semaphor sem_read erfasst, ob Elemente da sind. Ist keines da, wird der Verbraucher blockiert. Der zählende Semaphor sem_write erfasst die freie Aufnahmekapazität. Ist kein Platz frei, wird der Erzeuger blockiert. Ein wartender Prozess wird blockiert und rechnet nicht ständig weiter. Das vermeidet das aktive Warten, also das fortwährende Abfragen.

Beide Prozesse laufen in einer Schleife und haben fünf Schritte. Der Erzeuger ruft zuerst P(sem_write) auf. Gibt es keinen freien Platz, wartet er hier. Danach ruft er P(mutex) auf, um den Puffer zu schützen. Er schreibt sein Element und ruft V(mutex) auf. Zum Schluss ruft er V(sem_read) auf, um einen vielleicht wartenden Verbraucher zu informieren.

Der Verbraucher geht genauso vor, nur mit vertauschten Rollen: P(sem_read), P(mutex), Element lesen, V(mutex) und zuletzt V(sem_write). So erfährt ein vielleicht wartender Erzeuger, dass ein Platz frei geworden ist.

Merke dir das Muster: Zuerst kommt die Prüfung, ob Element oder Platz da ist. Dann wird der Puffer geschützt und verändert. Danach wird der Schutz aufgehoben. Zuletzt wird dem anderen Prozess Bescheid gegeben.

Ein Monitor ist ein Konzept, das Zugriffe von Threads auf gemeinsame Daten ordnet. Man kann ihn sich als Raum vorstellen, in dem nur ein Akteur Platz hat. Die anderen warten draußen. In Java kann jedes Objekt als Monitor dienen. Methoden mit dem Schlüsselwort synchronized laufen unter wechselseitigem Ausschluss.

Man braucht zusätzlich Kooperation: Ein Verbraucher, der im Monitor einen leeren Puffer findet, soll warten. Java hat dafür keine Bedingungsvariablen. Stattdessen gibt es in der Klasse Object die Methoden wait(), notify() und notifyAll().

Wegen der fehlenden Bedingungsvariablen muss ein aufgeweckter Thread die Bedingung, auf die er wartet, erneut prüfen. Sie könnte noch nicht gültig sein. Oder schnellere Threads haben sie schon wieder ungültig gemacht. Beispiel: Ein Element liegt im Puffer, aber ein anderer Verbraucher war schneller und hat es schon genommen.