The bounded-buffer problems (aka the producer-consumer problem) is a classic example of concurrent access to a shared resource. A bounded buffer lets multiple producers and multiple consumers share a single buffer. Producers write data to the buffer and consumers read data from the buffer.
Before you continue, make sure to go through the module 4 self study material regarding bounded buffer.
A bounded buffer with capacity N has can store N data items. The places used to store the data items inside the bounded buffer are called slots. Without proper synchronization the following errors may occur.
In module-4/mandatory/src/bounded-buffer.c
you find an almost working
implementation of the bounded buffer and a number of producers and consumers.
To implement the bounded buffer a finite size array in memory is shared by a number for producer and consumer threads.
In addition to the shared array, information about the state of the buffer must also be shared.
The buffer is represented by the following C struct.
typedef struct {
int value[BUFFER_SIZE];
int next_in, next_out;
} buffer_t;
In the struct there is an array
value
used to store integer values in the buffer and two integer indexes
next_in
and next_out
. Index next_in
is used to keep track of where to
write the next data item to the buffer. Index next_out
is used to keep track
of from where to read the next data item from the buffer.
In the below example three data items B, C and D are currently in the buffer. On the next write data will be written to index next_in = 4
. On the next read data will be read from index next_out = 0
.
All updates to the buffer state must be done in a critical section. More specifically, mutual exclusion must be enforced between the following critical sections:
next_in
.next_out
.A binary semaphore can be used to protect access to the critical sections.
Producers must block if the buffer is full. Consumers must block if the buffer is empty. Two counting semaphores can be used for this.
Use one semaphore named empty to count the empty slots in the buffer.
Use one semaphore named data to count the number of data items in the buffer.
P producers and C consumers using a shared bounded buffer of size N. Producers writes to buffer at index next_in and consumer reads at index next_out.
Among the includes at the beginning of bounded-buffer.c
you find:
#include <semaphore.h> /* sem_... *
, which is the header file used for Posix semaphores. Use the operations provided by the Posix semaphores to implement your solution.
In the terminal, navigate to the module-4/mandatory
directory. Use make to compile the program.
$ make
The executable will be named bounded-buffer
and placed in the bin
sub directory. Run the program from the terminal.
$ ./bin/bounded-buffer
To increase the probability of data races, make threads sleep for a random amount of time inside the critical section and also outside the critical section (the threads produces or consumes the item while sleeping!).