Producer-consumer problem

The producer-consumer problem ( English producer-consumer problem- , PCP ) is a classic, abstractly formulated problem of process synchronization , which is a regulation of the order of access to a data structure by element-producing (writing) and element-consuming (read) processes or threads discussed. The access regulation is intended to prevent a consuming process from accessing the data structure if the data structure does not contain any elements and it is therefore not possible to remove an element from the data structure. If the storage capacity of the data structure is limited, the access control should also prevent a generating process from accessing the data structure when the storage capacity of the data structure has already been exhausted.

Problem formulation

A system is considered with processes that behave either as producers or consumers, and a data structure that is shared by the processes for communication with one another. There is at least one producer process and at least one consumer process in the system. Creation processes create any elements and store them in the common data structure. Consumer processes take elements from the data structure and process them. The data structure can accommodate an unlimited or a limited number of elements. With (almost) unlimited capacity it can be used as a list or stack memory and with limited capacity e.g. B. be organized as a ring buffer .

A sequence control (synchronization) is required if

Access to the data structure are critical sections .
If a producer process is currently inserting an element into the data structure or a consumer process is currently removing an element, it must be prevented that another producer or consumer process interrupts this process in order to also access the data structure in a modified manner. Otherwise the data structure may be in an inconsistent state.
a consumer process wants to extract an element from the data structure even though the data structure does not contain any elements.
the data structure has a limited storage capacity and a generation process wants to store an element when the data structure is fully occupied.

If a consumer process accesses an empty data structure or a producer process accesses a fully occupied data structure, the processes should be blocked and woken up again when the state of the data structure has changed (process cooperation).

A solution using the consumer- consumer pattern is only useful if either

such an abstraction layer is necessary for systemic reasons. For example, as a security abstraction layer, or because there is a system change (hardware to software).
the number of consumers and producers is different or unknown.

The second point can be easily explained if one takes into account that the time a consumer needs for a process is obviously derived from the time of the consumer and the producer (which the consumer must necessarily wait for) for this process, as well as the time for communication about the pattern is composed as: ${\ displaystyle Z_ {n}}$ ${\ displaystyle N}$ ${\ displaystyle V_ {n}}$ ${\ displaystyle E_ {n}}$ ${\ displaystyle K}$ ${\ displaystyle Z_ {n} = V_ {n} + E_ {n} + K}$

If, however, there is always exactly one producer for each consumer, the consumer could include this, that is, carry out the "production" himself without using the sample, since otherwise he would only have to wait for the producer anyway. The time for this trivial solution is only: ${\ displaystyle Z_ {n} = V_ {n} + E_ {n}}$

So it would be less, so an application of the pattern in this case would be a slowdown. ${\ displaystyle K}$

Troubleshooting

abstract

The producer-consumer problem is solved with mechanisms of process synchronization . In most of the solution descriptions, semaphores are used because, in addition to mutual exclusion when executing critical sections, they also support the previously required cooperation between processes.

The following semaphores are required that are shared by all processes (for reasons of general validity, the original identifiers P and V are used for the semaphore operations):

a binary semaphore mutex to protect modifying access to the data structure.
If a producer or consumer process P2 wants to modify the data structure, it indicates this by means of a P operation of the semaphore. If another process P1 is currently modifying the data structure, process P2 is blocked until process P1 calls the V operation of the semaphore.
a counting semaphore sem_read , with which the availability of elements in the data structure is recorded for read access.
If there is no element in the data structure, calling the P operation of the semaphore will block the calling consumer process. The process is unblocked by a producer process which calls the V operation of the semaphore. If the data structure contains elements, then a consumer process calling the P operation of the semaphore is allowed to continue with its actions (i.e. with the removal of an element).
a counting semaphore sem_write , with which the available recording capacity is recorded for a write access.
If there is no storage space in the data structure, then calling the P operation of the semaphore blocks the calling generation process. The process is unblocked by a consumer process that calls the semaphore's V operation. If the data structure contains storage locations, a producer process calling the P operation of the semaphore is allowed to continue with its actions (i.e. with the storage of an element).

// 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
}

If the modification of the data structure is not a critical action, the mutex semaphore can be omitted. If the data structure has unlimited capacity, the semaphore sem_write is not required.

Java

The Java programming language provides ready-made classes to solve this problem thread-safe . A simple implementation using a LinkedBlockingQueue would be possible in this form, for example:

/* 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

The queue used automatically ensures synchronization between consumer and producer.

There are many examples of a custom implementation of the consumer-producer pattern in Java. Implementing this thread-safe, however, is not trivial, since the following problems must be dealt with:

A solution using the language elements synchronizedand wait()/ or notify()leads to a possible deadlock if a producer notify()wants to wake up a consumer, but the consumer is not yet waiting ( wait()has not yet been called).
Other classes such as locks can be used to solve this problem.
As a class of the concurrent package, the LinkedBlockingQueue scales significantly better with an increasing number of threads than would be possible with a simple synchronizedsolution, since non-blocking synchronization is used when accessing existing products in the list .

Individual evidence

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

[1] ttp://docs.oracle.com/javase/7/docs/api/java/util/concurrent/LinkedBlockingQueue.html

[2] ttp://www.mudraservices.com/waitnotify.html Wait / Notify Pitfalls

[3] ttp://docs.oracle.com/javase/7/docs/api/java/util/concurrent/locks/Lock.html

[4] ttp://docs.oracle.com/javase/7/docs/api/java/util/concurrent/package-summary.html#package_description Java Concurrent Package