Erzeuger-Verbraucher-Problem einfach erklärt

Stell dir eine Druckwarteschlange vor: Programme erzeugen Druckaufträge und legen sie in einer gemeinsamen Warteschlange ab. Ein Druckdienst entnimmt die Aufträge und verarbeitet sie. Die Warteschlange bildet den Puffer zwischen beiden Seiten.

Der Puffer entkoppelt die Geschwindigkeiten: Ein Erzeuger darf zeitweise schneller arbeiten als ein Verbraucher, solange noch Platz vorhanden ist.

Ein unbeschränkter Puffer wird im Modell als unbegrenzt groß betrachtet. Ein beschränkter Puffer besitzt dagegen eine feste Kapazität:

• Ist er leer, muss ein Verbraucher auf ein Element warten.
• Ist er voll, muss ein Erzeuger auf einen freien Platz warten.
• Bei jeder Änderung muss der Zugriff auf die gemeinsame Datenstruktur geschützt sein.

Eine korrekte Lösung verbindet Sicherheit und Lebendigkeit. Sicherheit bedeutet hier: Der Puffer gerät nicht in einen ungültigen Zustand. Lebendigkeit bedeutet: Ein wartender Thread kann weiterarbeiten, sobald seine Bedingung erfüllt ist.

1. Verändernde Zugriffe dürfen sich nicht überschneiden

Das Einfügen oder Entnehmen besteht meist aus mehreren Teilschritten. Würden zwei Threads diese Schritte unkontrolliert verschachteln, könnten Zähler, Elemente oder Zeiger nicht mehr zusammenpassen.

Eine Sperre sorgt für gegenseitigen Ausschluss: Höchstens ein Thread verändert den Puffer zur selben Zeit.

2. Ein Verbraucher braucht ein vorhandenes Element

Ein leerer Puffer enthält nichts, das entnommen werden könnte. Der Verbraucher muss warten, ohne dabei die Sperre dauerhaft festzuhalten.

3. Ein Erzeuger braucht einen freien Platz

Bei einem beschränkten Puffer darf der Erzeuger nicht über dessen Kapazität hinaus schreiben. Auch er muss warten können, ohne die Gegenseite auszusperren.

Ein Semaphor verwaltet eine Anzahl verfügbarer Ressourcen. Die Operation P(s) reserviert eine Ressource und verringert den Zähler. Ist keine Ressource verfügbar, wird der Thread blockiert. V(s) gibt eine Ressource frei, erhöht den Zähler und kann einen wartenden Thread wecken.

Für einen beschränkten Puffer der Kapazität N werden drei Semaphore verwendet:

Nach jeder vollständig abgeschlossenen Operation gilt:

$belegt + frei = N$

Für einen anfangs leeren Puffer mit N = 4 entwickeln sich die Zähler so:

Ablauf eines Erzeugers

1. Das Element außerhalb des kritischen Abschnitts erzeugen.
2. Mit P(sem_write) einen freien Platz reservieren.
3. Mit P(mutex) den exklusiven Zugriff erwerben.
4. Das Element ablegen und den Pufferzustand ändern.
5. Mit V(mutex) den Zugriff freigeben.
6. Mit V(sem_read) ein entnehmbares Element melden.

Ablauf eines Verbrauchers

1. Mit P(sem_read) ein vorhandenes Element reservieren.
2. Mit P(mutex) den exklusiven Zugriff erwerben.
3. Das Element entnehmen und den Pufferzustand ändern.
4. Mit V(mutex) den Zugriff freigeben.
5. Mit V(sem_write) einen freien Platz melden.
6. Das Element außerhalb des kritischen Abschnitts verarbeiten.

Bei einem unbeschränkten Puffer wird kein Semaphor für freie Plätze benötigt. Falls die verwendete Datenstruktur verändernde Zugriffe selbst sicher koordiniert, kann außerdem ein eigener mutex entfallen.

Eine synchronisierte Java-Methode verbindet den geschützten Zugriff mit dem Monitor des Objekts. Zustände wie valueSet oder usedSlots zeigen an, ob die fachliche Bedingung erfüllt ist.

wait() bewirkt drei wichtige Dinge:

1. Der aktuelle Thread wartet am Monitorobjekt.
2. Er gibt dessen Sperre atomar frei.
3. Nach einer Benachrichtigung muss er die Sperre erneut erwerben, bevor er fortfährt.

notifyAll() weckt alle Threads, die an diesem Monitor warten. Die Benachrichtigung bedeutet nur: Ein relevanter Zustand hat sich geändert. Sie garantiert nicht, dass ein bestimmter Thread seine Arbeit sofort fortsetzen darf.

Warum steht wait() in einer while-Schleife?

Angenommen, ein einelementiger Puffer ist voll und zwei Erzeuger möchten schreiben:

1. Erzeuger A findet den Puffer voll und wartet.
2. Ein Verbraucher entnimmt das Element und ruft notifyAll() auf.
3. Erzeuger A und Erzeuger B können nun um den Monitor konkurrieren.
4. Erzeuger B erhält ihn zuerst und füllt den Puffer wieder.
5. Erzeuger A erhält den Monitor erst danach.

Mit if würde A nach dem Aufwachen ohne erneute Prüfung weitermachen. Mit while erkennt A, dass der Puffer inzwischen wieder voll ist, und wartet erneut.

Polling oder blockierendes Warten?

Beim Polling fragt ein Thread denselben Zustand ständig erneut ab. Das kann Rechenzeit verbrauchen. Wartet er dabei sogar mit gehaltener Sperre, verhindert er möglicherweise die Zustandsänderung selbst.

Blockierendes Warten setzt den Thread dagegen aus, bis eine Benachrichtigung erfolgt. Vorgefertigte Klassen wie eine beschränkte BlockingQueue kapseln diese Koordination: put wartet bei einer vollen Queue, take bei einer leeren.

Wenn du alle drei Fragen begründen kannst, kannst du die beiden Ebenen einer Lösung auseinanderhalten: Zähl- oder Wartebedingungen regeln, wann eine Operation erlaubt ist; der gegenseitige Ausschluss schützt, wie der Puffer verändert wird.