Producer-Consumer-Problem

Producer-Consumer-Problem

Das Erzeuger-Verbraucher-Problem 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


Wikimedia Foundation.

Игры ⚽ Нужна курсовая?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Producer-consumer problem — In computer science, the producer consumer problem (also known as the bounded buffer problem) is a classical example of a multi process synchronization problem. The problem describes two processes, the producer and the consumer, who share a… …   Wikipedia

  • Consumer theory — is a theory of microeconomics that relates preferences to consumer demand curves. The link between personal preferences, consumption, and the demand curve is one of the most complex relations in economics. Implicitly, economists assume that… …   Wikipedia

  • 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… …   Deutsch Wikipedia

  • Consumer choice — Economics …   Wikipedia

  • Consumer price index — CPI redirects here. For other uses, see CPI (disambiguation). A consumer price index (CPI) measures changes in the price level of consumer goods and services purchased by households. The CPI, in the United States is defined by the Bureau of Labor …   Wikipedia

  • Semaphore (programming) — For other uses, see Semaphore (disambiguation). In computer science, a semaphore is a variable or abstract data type that provides a simple but useful abstraction for controlling access by multiple processes to a common resource in a parallel… …   Wikipedia

  • Communications protocol — For other senses of this word, see Protocol. A communications protocol is a system of digital message formats and rules for exchanging those messages in or between computing systems and in telecommunications. A protocol may have a formal… …   Wikipedia

  • Circular buffer — A ring showing, conceptually, a circular buffer. This visually shows that the buffer has no real end and it can loop around the buffer. However, since memory is never physically created as a ring, a linear representation is generally used as is… …   Wikipedia

  • PCP — Die Abkürzung PCP steht für: Flughafen Príncipe im Inselstaat São Tomé und Príncipe (IATA Code) Partido Comunista Português, die Kommunistische Partei Portugals Partido Comunista Paraguayo, die Kommunistische Partei Paraguays PC Powerplay, ein… …   Deutsch Wikipedia

  • Economic Affairs — ▪ 2006 Introduction In 2005 rising U.S. deficits, tight monetary policies, and higher oil prices triggered by hurricane damage in the Gulf of Mexico were moderating influences on the world economy and on U.S. stock markets, but some other… …   Universalium

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”