Home » NO IDEA » producer consumer wikipedia material

producer consumer wikipedia material

Blog Stats

  • 14,863 hits
April 2013
M T W T F S S
« Mar   Oct »
1234567
891011121314
15161718192021
22232425262728
2930  

WIKIPEDIA VERSION
Using semaphores
Semaphores solve the problem of lost wakeup calls. In the solution below we use two semaphores,
fillCount and emptyCount, to solve the problem. fillCount is the number of items already in the
buffer and available to be read, while emptyCount is the number of available spaces in the buffer
where items could be written. fillCount is incremented and emptyCount decremented when a new
item is put into the buffer. If the producer tries to decrement emptyCount when its value is zero, the
producer is put to sleep. The next time an item is consumed, emptyCount is incremented and the
producer wakes up. The consumer works analogously.
semaphore fillCount = 0; // items produced
semaphore emptyCount = BUFFER_SIZE; // remaining space
procedure producer() {
while (true) {
item = produceItem();
down(emptyCount);
putItemIntoBuffer(item);
up(fillCount);
}
}
procedure consumer() {
while (true) {
down(fillCount);
item = removeItemFromBuffer();
up(emptyCount);
consumeItem(item);
}
}
The solution above works fine when there is only one producer and consumer. With multiple producers
sharing the same memory space for the item buffer, or multiple consumers sharing the same memory
space, this solution contains a serious race condition that could result in two or more processes reading
or writing into the same slot at the same time. To understand how this is possible, imagine how the
procedure putItemIntoBuffer() can be implemented. It could contain two actions, one determining the
next available slot and the other writing into it. If the procedure can be executed concurrently by
multiple producers, then the following scenario is possible:
1.
2.
3.
4.
Two producers decrement emptyCount
One of the producers determines the next empty slot in the buffer
Second producer determines the next empty slot and gets the same result as the first producer
Both producers write into the same slot
To overcome this problem, we need a way to make sure that only one producer is executing
putItemIntoBuffer() at a time. In other words we need a way to execute a critical section with mutual
exclusion. To accomplish this we use a binary semaphore called mutex. Since the value of a binary
semaphore can be only either one or zero, only one process can be executing between down(mutex)
and up(mutex). The solution for multiple producers and consumers is shown below.
semaphore mutex = 1;
semaphore fillCount = 0;
semaphore emptyCount = BUFFER_SIZE;
procedure producer() {
while (true) {
item = produceItem();
down(emptyCount);
down(mutex);
putItemIntoBuffer(item);
up(mutex);
up(fillCount);
}
}
procedure consumer() {
while (true) {
}
down(fillCount);
down(mutex);
item = removeItemFromBuffer();
up(mutex);
up(emptyCount);
consumeItem(item);
}

Notice that the order in which different semaphores are incremented or decremented is essential:
changing the order might result in a deadlock.
PRODUCER CONSUMER (CIRCULAR/CYCLIC BUFFER)
1. The Producer-Consumer Problem
In the producer-consumer problem, a producer thread produces messages that are consumed by a
consumer In order to correctly implement the thread. One solution to the producer-consumer problem
uses shared memory. To allow producer and consumer threads to run concurrently, we must have a
buffer of items that can be filled by the producer and emptied by the consumer. In this exercise, the
bounded buffer is implemented as a ring with the fixed buffer size. In order to implement the producer-
consumer problem correctly, the following constraints should be satisfied:
• Consumer must wait for producer to fill the shared buffer, if none in the buffer (scheduling
constraint);
• Producer must wait for consumer to empty the buffer, if the buffer is full (scheduling
constraint);
• Only one thread can manipulate the buffer queue at a time (mutual exclusion)
Use a separate semaphore for each constraint; note semaphores being used in multiple ways:
• Semaphore fullBuffers;
//consumer’s constraint, if 0, no coke in machine
• Semaphore emptyBuffers; // producer’s constraint, if 0, nowhere to put more coke
• Semaphore mutex;
// mutual exclusion
Algorithms for producer and consumer:
Semaphore fullBuffers(“full”,0) // initially, no messages
Semaphore emptyBuffers(“empty”, BUFF_SIZE); // the size of the round
buffer
Semaphore mutex(“ring”,1);
// no one accesses the ring buffer
Producer() {
emptyBuffers.P();
mutex.P();
put one message in the ring buffer
// check if there’s slot for more messages
// make sure no one else is accessing the ring buffer
mutex.V();
fullBuffers.V();
buffer
}
Consumer() {
fullBuffers.P();
mutex.P();
// ok for others to use the ring buffer
// tell consumers there’s a new message in the ring
// check if there’s a message in the ring buffer
// make sure no one else is accessing the ring buffer
take one message out
mutex.V(); // others’ turn to use the ring buffer
emptyBuffers.V(); // tell producer more messages are needed
}
ANOTHER VERSION
Using a Circular Buffer
Producer:
while (true) {
/*produce item v */
while ((in + 1) % n == out) /* do nothing */;
b [in] = v;
in = (in + 1) % n;
}
Consumer:
while (true) {
while (in == out) /* do nothing */;
w = b [out];
out = (out + 1) % n;
/*consume item w */
}
Finite (Circular) Buffer

Complete Example Program using a Circular Buffer
/* example of single producer and multiple consumers
This uses a ring-buffer and no other means of mutual exclusion.
It works because the shared variables “in” and “out” each
have only a single writer. It is an excellent technique for
those situations where it is adequate.
If we want to go beyond this, e.g., to handle multiple producers
or multiple consumers, we need to use some more powerful means
of mutual exclusion and synchronization, such as mutexes and
condition variables.
*/
#define _XOPEN_SOURCE 500
#define _REENTRANT
#include <unistd.h>
#include <stdlib.h>
#include <string.h>
#include <pthread.h>
#include <stdio.h>
#include <values.h>
#include <errno.h>
#include <sched.h>
#define BUF_SIZE 10
int b[BUF_SIZE];
int in = 0, out = 0;
pthread_t consumer;
pthread_t producer;
void * consumer_body (void *arg) {
/* create one unit of data and put it in the buffer
Assumes arg points to an element of the array id_number,
identifying the current thread. */
int tmp;
int self = *((int *) arg);
}
fprintf(stderr, "consumer thread starts\n");
for (;;) {
/* wait for buffer to fill */
while (out == in);
/* take one unit of data from the buffer */
tmp = b[out];
out = (out + 1) % BUF_SIZE;
/* copy the data to stdout */
fprintf (stdout, "thread %d: %d\n", self, tmp);
}
fprintf(stderr, "consumer thread exits\n");
return NULL;
void * producer_body (void * arg) {
/* takes one unit of data from the buffer */
int i;
fprintf(stderr, "producer thread starts\n");
for (i = 0; i < MAXINT; i++) {
/* wait for space in buffer */
while (((in + 1) % BUF_SIZE) == out);
/* put value i into the buffer */
b[in] = i;
in = (in + 1) % BUF_SIZE;
}
return NULL;
}
int main () {
int result;
pthread_attr_t attrs;
/* use default attributes */
pthread_attr_init (&attrs);
/* create producer thread */
if ((result = pthread_create (
&producer, /* place to store the id of new thread */
&attrs,
producer_body,
NULL))) {
fprintf (stderr, "pthread_create: %d\n", result);
exit (-1);
}
fprintf(stderr, "producer thread created\n");
/* create consumer thread */
if ((result = pthread_create (
&consumer,
&attrs,
consumer_body,
NULL))) {
fprintf (stderr, "pthread_create: %d\n", result);
exit (-1);
}
fprintf(stderr, "consumer thread created\n");
}
/* give the other threads a chance to run */
sleep (10);
return 0;
PRODUCER CONSUMER Using an Infinite Buffer
Producer:
while (true) {
/*produce item v */
b [in] = v;
in++;
}
Consumer:
while (true) {
while (in <= out) /* do nothing */;
w = b [out];
out++;
/*consume item w */
}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: