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

Among the slides you find self study material about classic synchronization problems. In these slides the bounded buffer problem is described. Before you continue, make sure to read the self study slides about the bounded buffer problem.

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.

Supported platforms

You will only be able to work on this assignment using one of the supported platforms.

The department Linux system

The provided code has been developed and tested on the department Linux system but will most likely work on any Linux system.

If you use macOS you can use the provided platform independent semaphore library, see this post on Piazza for more information.

If you use Windows you must use the department Linux system for this assignment. You may still use your private computer to access the department Linux system using SSH but make sure to log in to one of the Linux hosts.

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?