Erzeuger-Verbraucher-Problem

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

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 Verbrauchprozess 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 Element 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 werden und wieder aufgeweckt werden, wenn sich der Zustand der Datenstruktur verändert hat (Prozesskooperation).

Problemlösung

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.

Siehe auch

• Philosophenproblem
• Leser-Schreiber-Problem
• Raucherproblem
• Mutex
• Verklemmung