Erzeuger-Verbraucher-Problem

Kernidee

Das Erzeuger-Verbraucher-Problem, englisch producer-consumer problem (PCP), ist eine klassische abstrakte Problemstellung der Prozesssynchronisation. Es beschreibt, wie mehrere Prozesse oder Threads geordnet auf eine gemeinsam genutzte Datenstruktur zugreifen, wenn einige Elemente erzeugen und hineinschreiben und andere Elemente entnehmen und lesen.

Das Problem ist auch aus Warenproduktion, Logistik und Supply Chain Management bekannt: Ein Zwischenlager dient als Puffer zwischen zwei Produktionsstationen. Hat der Puffer unbegrenzte Kapazitaet, spricht man von einem unbounded buffer; hat er begrenzte Kapazitaet, von einem bounded buffer. Ist das Zwischenlager voll, muss die vorgelagerte Station stoppen. Ist es leer, hat die nachgelagerte Station nichts zu tun.

Problemstellung

Betrachtet wird ein System mit mindestens einem Erzeugerprozess und mindestens einem Verbraucherprozess. Erzeugerprozesse erzeugen Elemente und legen sie in einer gemeinsamen Datenstruktur ab. Verbraucherprozesse entnehmen Elemente aus dieser Datenstruktur und verarbeiten sie.

Die Datenstruktur kann unbeschraenkt oder beschraenkt viele Elemente aufnehmen. Bei nahezu unbeschraenkter Kapazitaet kann sie als Liste oder Stapelspeicher organisiert sein, bei beschraenkter Kapazitaet zum Beispiel als Ringpuffer.

Synchronisation ist erforderlich, wenn Zugriffe auf die Datenstruktur kritische Abschnitte sind. Ein kritischer Abschnitt ist ein Teil des Programms, in dem eine gemeinsam genutzte Struktur veraendert wird und deshalb nicht gleichzeitig von anderen Prozessen veraendert werden darf. Wird ein Erzeuger oder Verbraucher waehrend des Ablegens oder Entfernens eines Elements unterbrochen, kann die Datenstruktur inkonsistent werden.

Synchronisation ist auch erforderlich, wenn ein Verbraucher ein Element entnehmen will, obwohl die Datenstruktur leer ist, oder wenn ein Erzeuger bei beschraenkter Kapazitaet ein Element ablegen will, obwohl die Datenstruktur voll ist. In solchen Faellen sollen die Prozesse blockiert und wieder aufgeweckt werden, wenn sich der Zustand der Datenstruktur geaendert hat. Diese Zusammenarbeit heisst Prozesskooperation.

Wann das Muster sinnvoll ist

Eine Loesung mit dem Erzeuger-Verbraucher-Muster ist nur dann sinnvoll, wenn eine solche Abstraktionsschicht systemisch notwendig ist, zum Beispiel als Sicherheits-Abstraktionsschicht oder bei einem Systemwechsel von Hardware zu Software, oder wenn die Anzahl von Verbrauchern und Erzeugern unterschiedlich beziehungsweise unbekannt ist.

Der Artikel erklaert den zweiten Punkt mit der Zeitrechnung fuer einen Vorgang N: Die Zeit Z_n eines Verbrauchers setzt sich aus der Zeit des Verbrauchers V_n, der Zeit des Erzeugers E_n und der Kommunikationszeit K ueber das Muster zusammen: Z_n = V_n + E_n + K.

Wenn es fuer jeden Verbraucher immer genau einen Produzenten gibt, koennte der Verbraucher die Produktion selbst uebernehmen. Dann waere die Zeit nur Z_n = V_n + E_n. Die Verwendung des Musters waere in diesem Fall um K langsamer.

Abstrakte Loesung mit Semaphoren

Das Problem wird mit Mechanismen der Prozesssynchronisation geloest. Haefig werden Semaphore verwendet. Ein Semaphor ist eine Synchronisationsvariable, mit der Prozesse warten oder fortfahren koennen. Die klassischen Operationen heissen P und V: P kann einen Prozess blockieren, wenn die benoetigte Bedingung nicht erfuellt ist; V gibt eine Ressource oder Information frei und kann wartende Prozesse wecken.

Benutzt werden drei gemeinsam genutzte Semaphore. Der binaere Semaphor mutex schuetzt veraendernde Zugriffe auf die Datenstruktur, sodass nur ein Prozess gleichzeitig schreibt oder entnimmt. Der zaehlende Semaphor sem_read erfasst fuer Lesezugriffe, wie viele Elemente verfuegbar sind. Ist kein Element vorhanden, blockiert P(sem_read) den Verbraucher; ein Erzeuger weckt ihn durch V(sem_read), nachdem ein Element abgelegt wurde. Der zaehlende Semaphor sem_write erfasst fuer Schreibzugriffe, wie viel Aufnahmekapazitaet noch frei ist. Ist kein Platz frei, blockiert P(sem_write) den Erzeuger; ein Verbraucher weckt ihn durch V(sem_write), nachdem ein Element entnommen wurde.

Bei einer Aufnahmekapazitaet N = 4 wird mutex mit 1 initialisiert, sem_read mit 0 und sem_write mit N. Ein Erzeuger fuehrt zuerst P(sem_write) aus, sperrt dann mit P(mutex) die Datenstruktur, schreibt ein Element, gibt mit V(mutex) die Sperre frei und meldet mit V(sem_read), dass ein Element vorhanden ist. Ein Verbraucher fuehrt zuerst P(sem_read) aus, sperrt mit P(mutex), liest ein Element, gibt mit V(mutex) frei und meldet mit V(sem_write), dass wieder ein Platz frei ist.

Wenn die Modifikation der Datenstruktur keine kritische Aktion ist, kann auf mutex verzichtet werden. Wenn die Datenstruktur unbeschraenkte Kapazitaet hat, wird sem_write nicht benoetigt.

Umsetzung in C++

Ab C++20 sind Semaphore Teil der Sprache. Die im Artikel beschriebene C++-Loesung bildet die Dijkstra-Loesung direkt nach. Der Puffer kann N Teile oder Elemente speichern.

Das Semaphor number_of_queuing_portions zaehlt die gefuellten Plaetze im Puffer. Das Semaphor number_of_empty_positions zaehlt die leeren Plaetze. buffer_manipulation ist ein Mutex fuer die Put- und Get-Operationen des Puffers.

Ist der Puffer voll, also number_of_empty_positions gleich null, wartet der Producer-Thread in number_of_empty_positions.acquire(). Ist der Puffer leer, also number_of_queuing_portions gleich null, wartet der Consumer-Thread in number_of_queuing_portions.acquire(). acquire() verringert den Semaphorwert bis auf null; release() erhoeht den Semaphorwert und kann als Nebeneffekt einen Thread aus der wait Queue in die ready Queue bewegen.

Fuer den Mutex wird lock_guard() verwendet. Das ist C++ RAII: Der Destruktor von lock_guard gibt die Sperre auch bei einer Exception wieder frei. Die Loesung kann mehrere Consumer-Threads und/oder mehrere Producer-Threads verarbeiten.

Umsetzung in Java

Java stellt fertige Klassen bereit, um das Problem thread-sicher zu loesen. Der Artikel zeigt als einfache Umsetzung eine BlockingQueue<Integer> mit LinkedBlockingQueue<>(3). Der Producer-Thread erzeugt fortlaufend Werte, wartet jeweils 400 Millisekunden und legt sie mit blockingQueue.put(value) ab. Der Consumer-Thread entnimmt Werte mit blockingQueue.take() und wartet danach zufaellig zwischen 200 und 800 Millisekunden.

Die Queue sorgt dabei automatisch fuer die Synchronisation zwischen Verbraucher und Erzeuger. put() wartet, wenn die begrenzte Queue voll ist; take() wartet, wenn sie leer ist.

Eigene Implementierungen des Verbraucher-Erzeuger-Musters in Java sind moeglich, aber nicht trivial. Eine Loesung mit synchronized sowie wait() beziehungsweise notify() kann zu einem Deadlock fuehren, wenn ein Produzent mit notify() einen Verbraucher wecken will, dieser aber noch nicht wartet, also wait() noch nicht aufgerufen hat. Zur Loesung koennen weitere Klassen wie Locks verwendet werden. Die LinkedBlockingQueue aus dem Concurrent-Package skaliert bei steigender Threadzahl deutlich besser als eine einfache synchronized-Loesung, weil beim Zugriff auf vorhandene Produkte in der Liste eine nicht-blockierende Synchronisation verwendet wird.