producer–consumer problem
   HOME

TheInfoList



OR:

In
computing Computing is any goal-oriented activity requiring, benefiting from, or creating computing machinery. It includes the study and experimentation of algorithmic processes, and development of both hardware and software. Computing has scientific, e ...
, the producer-consumer problem (also known as the bounded-buffer problem) is a family of problems described by
Edsger W. Dijkstra Edsger Wybe Dijkstra ( ; ; 11 May 1930 – 6 August 2002) was a Dutch computer scientist, programmer, software engineer, systems scientist, and science essayist. He received the 1972 Turing Award for fundamental contributions to developing progra ...
since 1965. Dijkstra found the solution for the producer-consumer problem as he worked as a consultant for the
Electrologica N.V. Electrologica was a pioneering Dutch computer manufacturer from 1956 to 1968, when it was taken over by Philips. It was started by A. van Wijngaarden, B.J. Loopstra and C.S. Scholten from the Mathematisch Centrum (Mathematical centre) in ...
X1 and X8 computers: "The first use of producer-consumer was partly software, partly hardware: The component taking care of the information transport between store and peripheral was called 'a channel' ... Synchronization was controlled by two counting semaphores in what we now know as the producer/consumer arrangement: the one semaphore indicating the length of the queue, was incremented (in a V) by the CPU and decremented (in a P) by the channel, the other one, counting the number of unacknowledged completions, was incremented by the channel and decremented by the CPU. he second semaphore being positive would raise the corresponding interrupt flag. Dijkstra wrote about the unbounded buffer case: "We consider two processes, which are called the 'producer' and the 'consumer' respectively. The producer is a cyclic process and each time it goes through its cycle it produces a certain portion of information, that has to be processed by the consumer. The consumer is also a cyclic process and each time it goes through its cycle, it can process the next portion of information, as has been produced by the producer ... We assume the two processes to be connected for this purpose via a buffer with unbounded capacity." He wrote about the bounded buffer case: "We have studied a producer and a consumer coupled via a buffer with unbounded capacity ... The relation becomes symmetric, if the two are coupled via a buffer of finite size, say N portions" And about the multiple producer-consumer case: "We consider a number of producer/consumer pairs, where pairi is coupled via an information stream containing ni portions. We assume ... the finite buffer that should contain all portions of all streams to have a capacity of 'tot' portions."
Per Brinch Hansen Per Brinch Hansen (13 November 1938 – 31 July 2007) was a Danish-American computer scientist known for his work in operating systems, concurrent programming and parallel and distributed computing. Biography Early life and education Per Br ...
and
Niklaus Wirth Niklaus Emil Wirth (born 15 February 1934) is a Swiss computer scientist. He has designed several programming languages, including Pascal (programming language), Pascal, and pioneered several classic topics in software engineering. In 1984, he w ...
saw soon the problem of semaphores: "I have come to the same conclusion with regard to semaphores, namely that they are not suitable for higher level languages. Instead, the natural synchronization events are exchanges of
message A message is a discrete unit of communication intended by the source for consumption by some recipient or group of recipients. A message may be delivered by various means, including courier, telegraphy, carrier pigeon and electronic bus. A ...
."


Dijkstra's bounded buffer solution

The original semaphore bounded buffer solution was written in
ALGOL ALGOL (; short for "Algorithmic Language") is a family of imperative computer programming languages originally developed in 1958. ALGOL heavily influenced many other languages and was the standard method for algorithm description used by the ...
style. The buffer can store N portions or elements. The "number of queueing portions"
semaphore Semaphore (; ) is the use of an apparatus to create a visual signal transmitted over distance. A semaphore can be performed with devices including: fire, lights, flags, sunlight, and moving arms. Semaphores can be used for telegraphy when arra ...
counts the filled locations in the buffer, the "number of empty positions" semaphore counts the empty locations in the buffer and the semaphore "buffer manipulation" works as
mutex In computer science, a lock or mutex (from mutual exclusion) is a synchronization primitive: a mechanism that enforces limits on access to a resource when there are many threads of execution. A lock is designed to enforce a mutual exclusion concu ...
for the buffer put and get operations. If the buffer is full, that is number of empty positions is zero, the producer thread will wait in the P(number of empty positions) operation. If the buffer is empty, that is the number of queueing portions is zero, the consumer thread will wait in the P(number of queueing portions) operation. The V() operations release the semaphores. As a side effect, a thread can move from the wait queue to the ready queue. The P() operation decreases the semaphore value down to zero. The V() operation increases the semaphore value. begin integer number of queueing portions, number of empty positions, buffer manipulation; number of queueing portions:= 0; number of empty positions:= N; buffer manipulation:= 1; parbegin producer: begin again 1: produce next portion; P(number of empty positions); P(buffer manipulation); add portion to buffer; V(buffer manipulation); V(number of queueing portions); goto again 1 end; consumer: begin again 2: P(number of queueing portions); P(buffer manipulation); take portion from buffer; V(buffer manipulation) ; V(number of empty positions); process portion taken; goto again 2 end parend end As of C++ 20, semaphores are part of the language. Dijkstra's solution can easily be written in modern C++. The variable buffer_manipulation is a mutex. The semaphore feature of acquiring in one thread and releasing in another thread is not needed. The lock_guard() statement instead of a lock() and unlock() pair is C++ RAII. The lock_guard destructor ensures lock release in case of an exception. This solution can handle multiple consumer threads and/or multiple producer threads. #include #include #include std::counting_semaphore number_of_queueing_portions; std::counting_semaphore number_of_empty_positions; std::mutex buffer_manipulation; void producer() void consumer() int main()


Using monitors

Per Brinch Hansen Per Brinch Hansen (13 November 1938 – 31 July 2007) was a Danish-American computer scientist known for his work in operating systems, concurrent programming and parallel and distributed computing. Biography Early life and education Per Br ...
defined the monitor: I will use the term monitor to denote a shared variable and the set of meaningful operations on it. The purpose of a monitor is to control the scheduling of resources among individual processes according to a certain policy.
Tony Hoare Sir Charles Antony Richard Hoare (Tony Hoare or C. A. R. Hoare) (born 11 January 1934) is a British computer scientist who has made foundational contributions to programming languages, algorithms, operating systems, formal verification, and c ...
laid a theoretical foundation for the monitor. bounded buffer: monitor begin buffer:array 0..N-1 of portion; head, tail: 0..N-1; count: 0..N; nonempty, nonfull: condition; procedure append(x: portion); begin if count = N then nonfull.wait; note 0 <= count < N; buffer
ail Ail or AIL may refer to: * Illness, a state of poor health * Ail (''Sailor Moon''), a character in the ''Sailor Moon'' anime series * Acceptance in lieu, an arrangement in the UK for accepting works of art etc. in lieu of tax * Agilus, a Frankis ...
:= x; tail := tail (+) 1; count := count + 1; nonempty.signal end append; procedure remove(result x: portion) ; begin if count = 0 then nonempty.wait; note 0 < count <= N; x := buffer ead head := head (+) 1; count := count - 1; nonfull.signal end remove; head := 0; tail := 0; count := 0; end bounded buffer;
The monitor is an object that contains variables buffer, head, tail and count to realize a
circular buffer In computer science, a circular buffer, circular queue, cyclic buffer or ring buffer is a data structure that uses a single, fixed-size buffer as if it were connected end-to-end. This structure lends itself easily to buffering data streams. Ther ...
, the condition variables nonempty and nonfull for synchronization and the methods append and remove to access the bounded buffer. The monitor operation wait corresponds to the semaphore operation P or acquire, signal corresponds to V or release. The circled operation (+) are taken modulo N. The presented Pascal style
pseudo code In computer science, pseudocode is a plain language description of the steps in an algorithm or another system. Pseudocode often uses structural conventions of a normal programming language, but is intended for human reading rather than machine re ...
shows a Hoare monitor. A
Mesa A mesa is an isolated, flat-topped elevation, ridge or hill, which is bounded from all sides by steep escarpments and stands distinctly above a surrounding plain. Mesas characteristically consist of flat-lying soft sedimentary rocks capped by ...
monitor uses while count instead of if count. A programming language C++ version is: class Bounded_buffer ; The C++ version needs an additional mutex for technical reasons. It uses assert to enforce the
precondition In computer programming, a precondition is a condition or predicate that must always be true just prior to the execution of some section of code or before an operation in a formal specification. If a precondition is violated, the effect of the s ...
s for the buffer add and remove operations.


Using channels

The very first producer-consumer solution in the Electrologica computers used 'channels'. Hoare defined
channels Channel, channels, channeling, etc., may refer to: Geography * Channel (geography), in physical geography, a landform consisting of the outline (banks) of the path of a narrow body of water. Australia * Channel Country, region of outback Austral ...
: An alternative to explicit naming of source and destination would be to name a port through which communication is to take place. The port names would be local to the processes, and the manner in which pairs of ports are to be connected by channels could be declared in the head of a parallel command. Brinch Hansen implemented channels in the programming languages Joyce and
Super Pascal SuperPascal is an imperative, concurrent computing programming language developed by Per Brinch Hansen. It was designed as a ''publication language'': a thinking tool to enable the clear and concise expression of concepts in parallel programming ...
. The Plan 9 operating system programming language
Alef Aleph (or alef or alif, transliterated ʾ) is the first letter of the Semitic abjads, including Phoenician , Hebrew , Aramaic , Syriac , Arabic ʾ and North Arabian 𐪑. It also appears as South Arabian 𐩱 and Ge'ez . These letter ...
, the Inferno operating system programming language
Limbo In Catholic theology, Limbo (Latin '' limbus'', edge or boundary, referring to the edge of Hell) is the afterlife condition of those who die in original sin without being assigned to the Hell of the Damned. Medieval theologians of Western Euro ...
have channels. The following C source code compiles on
Plan 9 from User Space Plan 9 from User Space (also plan9port or p9p) is a port of many Plan 9 from Bell Labs libraries and applications to Unix-like operating systems. Currently it has been tested on a variety of operating systems including: Linux, macOS, FreeBSD, Net ...
: #include "u.h" #include "libc.h" #include "thread.h" enum ; void producer(void *v) void consumer(void *v) void threadmain(int argc, char **argv) The program entry point is at function threadmain. The function call ch = chancreate(sizeof(ulong), 1) creates the channel, the function call sendul(ch, i) sends a value into the channel and the function call p = recvul(ch) receives a value from the channel. The programming language Go has channels, too. A Go example: package main import ( "fmt" "math/rand" "time" ) var sendMsg = 0 func produceMessage() int func consumeMessage(recvMsg int) func main() The Go producer-consumer solution uses the main Go routine for consumer and creates a new, unnamed Go routine for the producer. The two Go routines are connected with channel ch. This channel can queue up to three int values. The statement ch := make(chan int, 3) creates the channel, the statement ch <- produceMessage() sends a value into the channel and the statement recvMsg := range ch receives a value from the channel. The allocation of memory resources, the allocation of processing resources, and the synchronization of resources are done by the programming language automatically.


Without semaphores or monitors

Leslie Lamport Leslie B. Lamport (born February 7, 1941 in Brooklyn) is an American computer scientist and mathematician. Lamport is best known for his seminal work in distributed systems, and as the initial developer of the document preparation system LaTeX and ...
documented a bounded buffer producer-consumer solution for one producer and one consumer: We assume that the buffer can hold at most b messages, b >= 1. In our solution, we let k be a constant greater than b, and let s and r be integer variables assuming values between 0 and k-1. We assume that initially s=r and the buffer is empty. By choosing k to be a multiple of b, the buffer can be implemented as an array B : b - 1 The producer simply puts each new message into B mod b and the consumer takes each message from B mod bLamport, Leslie; 1977; Proving the Correctness of Multiprocess Programs, The Producer/Consumer Example Producer: L: if (s - r) mod k = b then goto L fi; put message in buffer; s := (s + 1) mod k; goto L; Consumer: L: if (s - r) mod k = 0 then goto L fi; take message from buffer; r := (r + 1) mod k; goto L; The Lamport solution uses busy waiting in the thread instead of waiting in the scheduler. This solution neglects the impact of scheduler thread switch at inconvenient times. If the first thread has read a variable value from memory, the scheduler switches to the second thread that changes the variable value, and the scheduler switches back to the first thread then the first thread uses the old value of the variable, not the current value. Atomic read-modify-write solves this problem. Modern C++ offers atomic variables and operations for multi-thread programming. The following busy waiting C++11 solution for one producer and one consumer uses atomic read-modify-write operations fetch_add and fetch_sub on the atomic variable count. enum ; Message buffer std::atomic count ; void producer() void consumer() int main() The circular buffer index variables head and tail are thread-local and therefore not relevant for memory consistency. The variable count controls the busy waiting of the producer and consumer thread.


See also

*
Atomic operation In concurrent programming, an operation (or set of operations) is linearizable if it consists of an ordered list of invocation and response events (event), that may be extended by adding response events such that: # The extended list can be re-e ...
*
Design pattern A design pattern is the re-usable form of a solution to a design problem. The idea was introduced by the architect Christopher Alexander and has been adapted for various other disciplines, particularly software engineering. The " Gang of Four" b ...
* FIFO *
Pipeline Pipeline may refer to: Electronics, computers and computing * Pipeline (computing), a chain of data-processing stages or a CPU optimization found on ** Instruction pipelining, a technique for implementing instruction-level parallelism within a s ...
*
Channel Channel, channels, channeling, etc., may refer to: Geography * Channel (geography), in physical geography, a landform consisting of the outline (banks) of the path of a narrow body of water. Australia * Channel Country, region of outback Austral ...
* Implementation in Java:
Java Message Service The Jakarta Messaging API (formerly Java Message Service or JMS API) is a Java application programming interface (API) for message-oriented middleware. It provides generic messaging models, able to handle the producer–consumer problem, that can ...


References


Further reading

* Mark Grand
Patterns in Java, Volume 1, A Catalog of Reusable Design Patterns Illustrated with UML
' * C/C++ Users Journal (Dr.Dobb's) January 2004
"A C++ Producer-Consumer Concurrency Template Library"
by Ted Yuan, is a ready-to-use C++ template library
The small template library source code
and examples can be foun
here
* Ioan Tinca,
The Evolution of the Producer-Consumer Problem in Java
' {{DEFAULTSORT:Producer-Consumer Problem Articles with example Java code Concurrency (computer science) Edsger W. Dijkstra Problems in computer science