Bounded buffer

Mandatory assignment

Introduction

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.

  • Producers must block if the buffer is full.
  • Consumers must block if the buffer is empty.

Preparations

Before you continue, make sure to go through the module 4 self study material regarding bounded buffer.

Synchronization

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.

  • The producers doesn’t block when the buffer is full.
  • A Consumer consumes an empty slot in the buffer.
  • A consumer attempts to consume a slot that is only half-filled by a producer.
  • Two producers writes into the same slot.
  • Two consumers reads the same slot.
  • And possibly more …

Provided source code

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.

Implementation

To implement the bounded buffer a finite size array in memory is shared by a number for producer and consumer threads.

  • Producer threads “produce” an item and place the item in the array.
  • Consumer threads remove an item from the array and “consume” it.

In addition to the shared array, information about the state of the buffer must also be shared.

  • Which slots in buffer are free?
  • To which slot should the next data item be stored?
  • Which parts of the buffer are filled?
  • From which slot should the next data item be read?

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.

Critical sections and mutual exclusion

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:

  • A producer writing to a buffer slot and updating next_in.
  • A consumer reading from a buffer slot and updating next_out.

A binary semaphore can be used to protect access to the critical sections.

Synchronize producers and consumers

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.

  • Initialise this semaphore to N.
  • A producer must wait on this semaphore before writing to the buffer.
  • A consumer will signal this semaphore after reading from the buffer.

Use one semaphore named data to count the number of data items in the buffer.

  • Initialise this semaphore to 0.
  • A consumer must wait on this semaphore before reading from the buffer.
  • A producer will signal this semaphore after writing to the buffer.

Implementation overview

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.

Posix semaphores

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.

Compile and run

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

Testing

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!).

Questions

  • Change the order of wait operations to see what happens. Does deadlock or starvation appear?
  • Put back the wait operations in the right order. Change the order of the signal operations to see what happens. Does deadlock appear or starvation?