Erzeuger-Verbraucher-Problem

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Das Erzeuger-Verbraucher-Problem (englisch: Producer-Consumer Problem, PCP) ist eine klassische, abstrakt formulierte Problemstellung der Prozesssynchronisation, welche eine Regelung der Zugriffsreihenfolge auf eine Datenstruktur durch elementerzeugende (schreibende) und elementverbrauchende (lesende) Prozesse bzw. Threads thematisiert. Die Zugriffsregelung soll verhindern, dass ein verbrauchender Prozess auf die Datenstruktur zugreift, wenn die Datenstruktur keine Elemente enthält und eine Entnahme eines Elements aus der Datenstruktur somit nicht möglich ist. Ist die Aufnahmekapazität der Datenstruktur beschränkt, so soll die Zugriffsregelung ferner verhindern, dass ein erzeugender Prozess auf die Datenstruktur zugreift, wenn die Aufnahmekapazität der Datenstruktur bereits ausgeschöpft ist.

Problemformulierung[Bearbeiten]

Betrachtet wird ein System mit Prozessen, die sich entweder als Erzeuger oder als Verbraucher verhalten, und einer Datenstruktur, die von den Prozessen für die Kommunikation untereinander gemeinsam genutzt wird. Es gibt mindestens einen Erzeugerprozess und mindestens einen Verbraucherprozess im System. Erzeugerprozesse erzeugen irgendwelche Elemente und legen sie in der gemeinsamen Datenstruktur ab. Verbraucherprozesse entnehmen der Datenstruktur Elemente und verarbeiten sie. Die Datenstruktur kann unbeschränkt oder beschränkt viele Elemente aufnehmen. Sie kann bei (nahezu) unbeschränkter Kapazität als Liste oder Stapelspeicher und bei beschränkter Kapazität z. B. als Ringpuffer organisiert sein.

Eine Reihenfolgeregelung (Synchronisation) ist dann erforderlich, wenn

  • Zugriffe auf die Datenstruktur kritische Abschnitte sind
    Legt ein Erzeugerprozess gerade ein Element in die Datenstruktur oder entfernt ein Verbraucherprozess gerade ein Element, so muss verhindert werden, dass ein anderer Erzeuger- oder Verbraucherprozess diesen Vorgang unterbricht um auch auf die Datenstruktur verändernd zuzugreifen. Andernfalls kann es zu einem inkonsistenten Zustand der Datenstruktur kommen.
  • ein Verbraucherprozess der Datenstruktur ein Element entnehmen will, obwohl die Datenstruktur keine Elemente enthält.
  • die Datenstruktur eine beschränkte Aufnahmekapazität besitzt und ein Erzeugerprozess bei voll belegter Datenstruktur ein Element ablegen will.

Greift ein Verbraucherprozess auf eine leere Datenstruktur zu bzw. ein Erzeugerprozess auf eine voll belegte Datenstruktur, so sollen die Prozesse blockiert und wieder aufgeweckt werden, wenn sich der Zustand der Datenstruktur verändert hat (Prozesskooperation).

Eine Lösung unter Verwendung des Verbraucher-Erzeuger Musters (engl: Producer-Consumer-Pattern) ist nur dann sinnvoll, wenn entweder

  • eine solche Abstraktions-Schicht systemisch bedingt notwendig ist. Beispielsweise als Sicherheits-Abstraktionsschicht, oder weil ein System-Wechsel (Hardware zu Software) vorliegt.
  • die Anzahl von Verbrauchern und Erzeugern unterschiedlich bzw. unbekannt ist.

Der zweite Punkt lässt sich leicht erklären, wenn man beachtet, dass die Zeit Z_n die ein Verbraucher für einen Vorgang N braucht, sich offensichtlich aus der Zeit des Verbrauchers V_n und des Erzeugers E_n (auf den der Verbraucher zwingend warten muss) für diesen Vorgang, so wie der Zeit K für die Kommunikation über das Muster zusammen setzt als:

   Z_n = V_n + E_n + K

Existiert nun aber für jeden Verbraucher stets immer genau ein Produzent, so könnte der Verbraucher diesen beinhalten, also die "Produktion" selbst vornehmen ohne dabei das Muster anzuwenden, da er ansonsten sowieso nur auf den Produzent warten müsste. Die Zeit für diese triviale Lösung beträgt aber nur:

   Z_n = V_n + E_n

Sie wäre also um den Faktor K geringer, eine Anwendung des Musters in diesem Fall also eine Verlangsamung.

Problemlösung[Bearbeiten]

Abstrakt[Bearbeiten]

Das Erzeuger-Verbraucher-Problem wird mit Mechanismen der Prozesssynchronisation gelöst. In den meisten Lösungsbeschreibungen werden Semaphore verwendet, da diese außer dem wechselseitigen Ausschluss bei der Ausführung kritischer Abschnitte auch die zuvor verlangte Kooperation zwischen Prozessen unterstützen.

Es werden folgende, von allen Prozessen gemeinsam genutzte Semaphore benötigt (aus Gründen der Allgemeingültigkeit werden für die Semaphoroperationen die Originalbezeichner P und V verwendet):

  • ein binärer Semaphor mutex zum Schutz modifizierender Zugriffe auf die Datenstruktur
    Will ein Erzeuger- oder Verbraucherprozess P2 die Datenstruktur modifizieren, so zeigt er dies durch eine P-Operation des Semaphors an. Sollte gerade ein anderer Prozess P1 die Datenstruktur modifizieren, so wird der Prozess P2 blockiert, bis der Prozess P1 die V-Operation des Semaphors aufruft.
  • ein zählender Semaphor sem_read, mit dem für einen Lesezugriff die Verfügbarkeit von Elementen in der Datenstruktur erfasst wird
    Sollte sich kein Element in der Datenstruktur befinden, so bewirkt ein Aufruf der P-Operation des Semaphors die Blockade des aufrufenden Verbraucherprozesses. Ein Deblockieren des Prozesses erfolgt durch einen Erzeugerprozess, der die V-Operation des Semaphors aufruft. Enthält die Datenstruktur Elemente, so darf ein die P-Operation des Semaphors aufrufender Verbraucherprozess mit seinen Aktionen (d.h. mit der Entnahme eines Elements) fortfahren.
  • ein zählender Semaphor sem_write, mit dem für einen Schreibzugriff die verfügbare Aufnahmekapazität erfasst wird
    Sollte sich kein Ablageplatz in der Datenstruktur finden, so bewirkt ein Aufruf der P-Operation des Semaphors die Blockade des aufrufenden Erzeugerprozesses. Ein Deblockieren des Prozesses erfolgt durch einen Verbraucherprozess, der die V-Operation des Semaphors aufruft. Enthält die Datenstruktur Ablageplätze, so darf ein die P-Operation des Semaphors aufrufender Erzeugerprozess mit seinen Aktionen (d.h. mit der Ablage eines Elements) fortfahren.
// Aufnahmekapazität der Datenstruktur
const N=4;
// Deklaration der Semaphore
semaphor mutex;
semaphor sem_read;
semaphor sem_write;
// Initialisierung der Semaphore
init (mutex, 1);      // genau einem Prozess wird die Modifikation der Datenstruktur ermöglicht
init (sem_read, 0);   // kein Element befindet sich in der Datenstruktur
init (sem_write, N);  // es sind N freie Ablageplätze für Elemente vorhanden

// Erzeugerprozess
while (1) {
   P (sem_write);     // Zeige Ablageaktion an
   P (mutex);         // Schütze die Datenstruktur vor Zugriffen anderer Prozesse 
   write (element);   // Schreibzugriff auf die Datenstruktur
   V (mutex);         // Hebe den Datenstrukturschutz auf
   V (sem_read);      // Informiere einen evtl. blockierten Verbraucherprozess über die Ablage eines Elements
}

// Verbraucherprozess
while (1) {
   P (sem_read);      // Zeige Entnahmeaktion an
   P (mutex);         // Schütze die Datenstruktur vor Zugriffen anderer Prozesse 
   read (element);    // Lesezugriff auf die Datenstruktur
   V (mutex);         // Hebe den Datenstrukturschutz auf
   V (sem_write);     // Informiere einen evtl. blockierten Erzeugerprozess über die Entnahme eines Elements
}

Wenn die Modifikation der Datenstruktur keine kritische Aktion ist, dann kann auf den Semaphor mutex verzichtet werden. Wenn die Datenstruktur von unbeschränkter Kapazität ist, so wird der Semaphor sem_write nicht benötigt.

Java[Bearbeiten]

Die Programmiersprache Java stellt bereits vorgefertigte Klassen bereit um dieses Problem Thread sicher zu lösen. Eine simple Implementation unter Verwendung einer LinkedBlockingQueue[1] wäre zum Beispiel in dieser Form möglich:

/* Die Queue zur Kommunikation zwischen Erzeuger und Verbraucher */
final LinkedBlockingQueue<Produkt> queue = new LinkedBlockingQueue<>();
 
// Produzent:
queue.put(produkt); // stelle ein fertiges Produkt für Verbraucher bereit, warte notfalls, bis ein weiteres aufgenommen werden kann
 
// Verbraucher:
final Produkt meinProdukt = queue.take(); // hole ein fertiges Produkt, warte notfalls bis eines produziert wurde

Die verwendete Queue sorgt hierbei automatisch für die Synchronisation zwischen Verbraucher und Erzeuger.

Es gibt viele Beispiele einer eigenen Implementierung des Verbraucher-Erzeuger Musters in Java. Dieses Thread sicher zu implementieren ist allerdings nicht trivial, da folgende Probleme behandelt werden müssen:

  • Eine Lösung unter Verwendung der Sprachelemente synchronized so wie wait() bzw. notify() führt genau dann zu einem möglichen Deadlock, wenn ein Produzent mittels notify() einen Verbraucher aufwecken will, dieser allerdings noch nicht wartet (wait() noch nicht aufgerufen wurde)[2].
    Zur Lösung dieses Problems können weitere Klassen wie Locks[3] verwendet werden.
  • Die LinkedBlockingQueue skaliert als Klasse des Concurrent-Packages deutlich besser mit steigender Anzahl Threads, als dies mit einer simplen synchronized Lösung möglich wäre, da, beim Zugriff auf vorhandene Produkte in der Liste, eine Nicht-blockierende Synchronisation verwendet wird[4].

Siehe auch[Bearbeiten]

Einzelnachweise[Bearbeiten]

  1. http://docs.oracle.com/javase/7/docs/api/java/util/concurrent/LinkedBlockingQueue.html
  2. http://www.mudraservices.com/waitnotify.html Wait/Notify Pitfalls
  3. http://docs.oracle.com/javase/7/docs/api/java/util/concurrent/locks/Lock.html
  4. http://docs.oracle.com/javase/7/docs/api/java/util/concurrent/package-summary.html#package_description Java Concurrent Package