Producer–consumer problem

The producer-consumer problem (English: the producer-consumer problem, PCP ) is a classic, abstractly formulated problem of process synchronization, which focuses on regulating the order of access to a data structure by element- generating ( writing ) and element- consuming ( read ) processes or threads. The access control is to prevent a consuming process accesses the data structure when the data structure does not contain elements and a removal of an element from the data structure is therefore not possible. Is the capacity of the data structure is limited, the access control should also prevent a generating process accesses the data structure when the capacity of the data structure is already exhausted.

Problem formulation

Consider a system with processes that behave either as a producer or as a consumer, and a data structure that is used by the processes to communicate with each other together. There are at least a producer process and at least one consumer process in the system. Producer processes generate any elements and place them in the shared data structure. Consumer processes refer to the data structure elements and process them. The data structure can accommodate unlimited or limited number of elements. It can be organized at ( almost ) unlimited capacity as a list or stack and limited capacity, for example as a ring buffer.

A sequence control ( synchronization) is required when

  • Accesses to the data structure critical sections are If a producer process just one element in the data structure or removes a consumer process just one element, it must be prevented that another producer or consumer process this operation interrupts to access altering on the data structure. Otherwise, it may result in an inconsistent state of the data structure.
  • A consumer process, the data structure will refer to an element, even though the data structure does not contain elements.
  • The data structure has a limited capacity and a producer process will drop an element in fully occupied data structure.

Accesses a consumer process to an empty data structure or a producer process to a fully populated data structure, the processes are blocked and be woken up again when the state of the data structure has changed ( process collaboration ).

A solution using the consumer - producer pattern ( engl: Producer-Consumer Pattern) is only meaningful if either

  • Such an abstraction layer is needed systemically related. For example, as a security abstraction layer, or because of a system - change has taken place (hardware to software).
  • The number of consumers and producers is different or unknown.

The second point is easily explained if one considers that the time a consumer for an operation needs, obviously from the time of the consumer and the producer ( to which the consumer must wait mandatory) for this operation, as the time for communication over the pattern together used as:

Is there now but for every consumer always always exactly one producer, the consumer could include these, so the " production " make itself without applying the pattern, because otherwise it would have anyway just waiting for the producer. The time for this trivial solution is only but:

They would be smaller by a factor of an application of the pattern in this case a deceleration.

Troubleshooting

Abstract

The producer-consumer problem is solved with mechanisms of process synchronization. In most descriptions solution semaphores are used, as they also support the previously demanded cooperation between processes except the mutual exclusion during the execution of critical sections.

There are the following, by all processes shared semaphores required ( for the sake of generality, the Originalbezeichner P and V are for the semaphore is used):

  • A binary semaphore mutex to protect accesses to modifying the data structure Will a producer or consumer process P2 modify the data structure, it indicates this by a P operation of the semaphore. Should just another process P1 modify the data structure, the process P2 is blocked until the process P1 calls the V- operation of the semaphore.
  • A counting semaphore sem_read, with a read access, the availability of elements is detected in the data structure If no element found in the data structure, so a call to the P operation of the semaphore results in blocking of the calling user process. A deblocking of the process is carried out by a producer process that calls the V- operation of the semaphore. Contains the data structure elements, a P- operation of the semaphore the invoking user process is allowed to proceed with his actions (ie, the removal of an element ).
  • A counting semaphore sem_write, which for a write access the available recording capacity is measured If there is no storage space available in the data structure, so a call to the P operation of the semaphore results in blocking of the calling process producer. A deblocking of the process is carried out by a consumer process that calls the V- operation of the semaphore. Contains the data structure storage spaces, a P- operation of the invoking semaphore producer process is allowed to proceed with his actions (ie, the filing of an element ).

/ / Capacity of the data structure const N = 4; / / Declaration of the semaphore semaphore mutex; semaphore sem_read; semaphore sem_write; / / Initialize the semaphore init ( mutex, 1); / / Exactly one process is the modification of the data structure allows init ( sem_read, 0); / / No element is located in the data structure init ( sem_write, N); / / There are N free storage locations for items available / / Producer process while (1 ) {     P ( sem_write ); / / Show store activities to     P ( mutex ); / / Save the data structure from attacks from other processes     write ( element ); / / Write access to the data structure     V ( mutex ); / / Raise the data structure protection on     V ( sem_read ); / / Find a possibly blocked consumer process on the filing of an element } / / Consumer process while (1 ) {     P ( sem_read ); / / Show taking action to     P ( mutex ); / / Save the data structure from attacks from other processes     read ( element ); / / Read access to the data structure     V ( mutex ); / / Raise the data structure protection on     V ( sem_write ); / / Find a possibly blocked producer process on the removal of an element } If the modification of the data structure is not a critical action, it can be dispensed to the mutex semaphore. If the data structure is of unlimited capacity, the semaphore is sem_write not required.

Java

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

/ * The queue for communication between producer and consumer * / final LinkedBlockingQueue queue = new LinkedBlockingQueue <> ();   / / Producer: queue.put (product ); / / Make a finished product ready for consumer, waiting if necessary until another can be added   / / Consumer: final product my product queue.take = (); / / Fetch a finished product, waiting if necessary until one was produced The queue used ensures this automatically for synchronization between consumers and producers.

There are many examples of an own implementation of consumer - producer pattern in Java. However, to implement this thread sure is not trivial because the following problems must be addressed:

  • A solution using the language elements synchronized as wait ( ) and notify () leads exactly to a possible deadlock when a producer using notify () will wake up a consumer, this however is not waiting ( wait () is not called ). To solve this problem more classes like locks can be used.
  • The LinkedBlockingQueue scaled as a class of concurrent packages much better with increasing number of threads than would be possible with a simple synchronized solution, as is used when accessing existing products in the list, a non- blocking synchronization.
315772
de