The Bounded Buffer, Solved

Get access to whole semester resourcesSemester Pass

Chapter Thirty-Nine

Syllabus topic Module 1, "Process Synchronization - Classic Problems of Synchronization"; Computer Science Practical 3, Module 1, "Introduce circular queue techniques for managing shared buffers."

Pages 155 to 159 of 452

In one line

A producer puts items into a buffer of fixed size and a consumer takes them out, and neither may run ahead of the other.

The problem, stated

A buffer holds at most n items. The producer makes items and adds them. The consumer removes items and uses them. Three things must be true.

The producer must not add to a full buffer.
The consumer must not take from an empty buffer.
They must not both change the buffer at the same moment.

Those are three different requirements and they need three different things, which is exactly why this problem is the classic teaching example. The third is mutual exclusion, which Chapters thirty seven and thirty eight can do. The first two are counting, and only a counting semaphore does them.

The three semaphores

Name	Initialised to	Counts	Waited on by
`empty`	n	free slots	the producer, before adding
`full`	0	items waiting	the consumer, before taking
`mutex`	1	nothing: it is a lock	both, around the buffer itself

The pattern is worth memorising because every examination answer is this shape.

producer                                consumer
do {                                    do {
    produce an item                         wait(full);
    wait(empty);                            wait(mutex);
    wait(mutex);                            take an item from the buffer
    add the item to the buffer              signal(mutex);
    signal(mutex);                          signal(empty);
    signal(full);                           use the item
} while (true);                         } while (true);

The order of the two waits is not interchangeable, and this is the single most examinable point in the chapter. The producer must wait(empty) before wait(mutex). Reverse them and consider a full buffer: the producer takes the mutex, then waits for a free slot, which only the consumer can create, and the consumer cannot get the mutex to create it. Both wait for ever. That is a deadlock, and Chapter fifty six is its general form.

Dijkstra says the same thing about his own version of this program, in one line: "the order of the two P-operations in the consumer is essential".

The signals at the end may be in either order. A signal never blocks, so nothing can deadlock there.

The circular queue, which is the practical's own label

A buffer of n slots needs two indices, and the practical asks for the technique by name.


`in`	where the producer will put the next item
`out`	where the consumer will take the next item
Advance	`in = (in + 1) % n`, and the same for `out`

The remainder is the whole idea. When an index reaches the end of the array it wraps to 0, so the buffer is used for ever without anything being copied or moved. That is why it is called circular.

With n slots and the two indices alone, in == out means both empty and full, which cannot be told apart. There are three standard answers: keep a count, keep one slot permanently empty, or let the semaphores do the counting, which is what the solution below does and why it needs no test at all.

The Bounded Buffer, Solved

The solution, run

#define _POSIX_C_SOURCE 200809L
#include <stdio.h>
#include <semaphore.h>
#include <pthread.h>

#define SLOTS 5
#define ITEMS 50

static int   buffer[SLOTS];
static int   in, out;

static sem_t empty_slots;                 /* counts free slots */
static sem_t full_slots;                  /* counts items waiting */
static sem_t gate;                        /* the mutex */

static long  produced, consumed, total;
static int   most_in_buffer;

static void *producer(void *unused)
{
    (void)unused;
    for (int n = 1; n <= ITEMS; n++) {
        sem_wait(&empty_slots);           /* FIRST: is there room? */
        sem_wait(&gate);                  /* THEN: may I touch the buffer? */

        buffer[in] = n;
        in = (in + 1) % SLOTS;
        produced++;
        int held = (int)(produced - consumed);
        if (held > most_in_buffer) {
            most_in_buffer = held;
        }

        sem_post(&gate);
        sem_post(&full_slots);
    }
    return NULL;
}

static void *consumer(void *unused)
{
    (void)unused;
    for (int n = 0; n < ITEMS; n++) {
        sem_wait(&full_slots);            /* FIRST: is there an item? */
        sem_wait(&gate);                  /* THEN: may I touch the buffer? */

        int item = buffer[out];
        out = (out + 1) % SLOTS;
        consumed++;
        total += item;

        sem_post(&gate);
        sem_post(&empty_slots);
    }
    return NULL;
}

int main(void)
{
    pthread_t p, c;

    sem_init(&empty_slots, 0, SLOTS);
    sem_init(&full_slots, 0, 0);
    sem_init(&gate, 0, 1);

    pthread_create(&p, NULL, producer, NULL);
    pthread_create(&c, NULL, consumer, NULL);
    pthread_join(p, NULL);
    pthread_join(c, NULL);

    long want = (long)ITEMS * (ITEMS + 1) / 2;
    printf("produced %ld, consumed %ld\n", produced, consumed);
    printf("the buffer holds %d slots and never held more than %d\n",
        SLOTS, most_in_buffer);
    printf("the sum of the items taken is %ld, and it should be %ld: %s\n",
        total, want, total == want ? "correct" : "WRONG");
    return 0;
}

$ gcc -std=c17 -Wall -Wextra -pthread -o bounded bounded.c
$ ./bounded
produced 50, consumed 50
the buffer holds 5 slots and never held more than 5
the sum of the items taken is 1275, and it should be 1275: correct
$ bad=$(for i in $(seq 10); do ./bounded; done | grep -c WRONG)
$ echo "ten runs, $bad wrong"
ten runs, 0 wrong

Three claims, all checked by the program.

Fifty produced and fifty consumed, with no item lost and none taken twice.
The buffer never held more than five, which is the semaphore doing the counting. Nothing

in the program tested whether the buffer was full.

The sum is 1275, which is 50 times 51 divided by 2, so every item arrived exactly once and

in one piece.

The deadlock, made to happen

The same program with the producer's two waits swapped, and nothing else changed.

The Bounded Buffer, Solved

#define _POSIX_C_SOURCE 200809L
#include <stdio.h>
#include <semaphore.h>
#include <pthread.h>
#include <time.h>

#define SLOTS 2
#define ITEMS 20

static int   buffer[SLOTS];
static int   in, out;
static sem_t empty_slots, full_slots, gate;
static long  produced, consumed;

static void *producer(void *unused)
{
    (void)unused;
    for (int n = 1; n <= ITEMS; n++) {
        sem_wait(&gate);                  /* WRONG WAY ROUND */
        sem_wait(&empty_slots);
        buffer[in] = n;
        in = (in + 1) % SLOTS;
        produced++;
        sem_post(&gate);
        sem_post(&full_slots);
    }
    return NULL;
}

static void *consumer(void *unused)
{
    (void)unused;
    for (int n = 0; n < ITEMS; n++) {
        sem_wait(&full_slots);
        sem_wait(&gate);
        out = (out + 1) % SLOTS;
        consumed++;
        sem_post(&gate);
        sem_post(&empty_slots);
    }
    return NULL;
}

int main(void)
{
    pthread_t p, c;
    struct timespec pause = {2, 0};

    sem_init(&empty_slots, 0, SLOTS);
    sem_init(&full_slots, 0, 0);
    sem_init(&gate, 0, 1);

    pthread_create(&p, NULL, producer, NULL);
    pthread_create(&c, NULL, consumer, NULL);
    nanosleep(&pause, NULL);              /* give them two whole seconds */

    printf("after two seconds: produced %ld of %d, consumed %ld of %d\n",
        produced, ITEMS, consumed, ITEMS);
    printf("%s\n", (produced < ITEMS || consumed < ITEMS)
        ? "both threads are stuck: this is a DEADLOCK"
        : "they finished, so nothing was proved");
    return 0;                             /* leave them stuck and exit */
}

$ gcc -std=c17 -Wall -Wextra -pthread -o deadlocked deadlocked.c
$ ./deadlocked
after two seconds: produced 2 of 20, consumed 0 of 20
both threads are stuck: this is a DEADLOCK
$ bad=$(for i in $(seq 5); do ./deadlocked | tail -1; done | grep -c DEADLOCK)
$ echo "five runs, $bad of them deadlocked"
five runs, 5 of them deadlocked

Two items through a two slot buffer and then nothing, five times out of five. The producer holds the mutex and waits for a slot. The consumer needs the mutex to free a slot. Neither can move, and the program will sit there until it is killed. That is what swapping two lines costs, and it is why the order is stated as a rule rather than left to taste.

Worked example: the states of a two slot buffer

A buffer of 2. The producer is fast and the consumer is slow. Follow the three semaphores.

Step	Action	`empty`	`full`	`mutex`	In the buffer
0	start	2	0	1	0
1	producer adds	1	1	1	1
2	producer adds	0	2	1	2
3	producer tries to add: waits on `empty`	0	2	1	2
4	consumer takes	1	1	1	1
5	the waiting producer is released, and adds	0	2	1	2

Notice empty + full = 2 at every step where nobody is inside: the two semaphores between them always account for all n slots. That is the invariant, and it is the cleanest way to check an answer.

The Bounded Buffer, Solved

Distinctions that carry marks

	`empty`	`full`	`mutex`
Initial value	n	0	1
Waited on by	the producer	the consumer	both
Signalled by	the consumer	the producer	whoever waited
Counts	free slots	items	nothing

	Producer waits in the order `empty` then `mutex`	`mutex` then `empty`
Full buffer	the producer waits outside the lock, the consumer can work	the producer holds the lock and waits; the consumer cannot get in
Result	correct	deadlock

What it does not mean

The mutex is not enough on its own. It gives mutual exclusion and says nothing about full or empty. A solution with only a mutex either loses items or spins.

The two counting semaphores are not interchangeable. empty starts at n and full at 0, and swapping them lets the consumer take from an empty buffer immediately.

A circular queue does not make the buffer unbounded. It reuses the slots; there are still n of them.

"Bounded" is not a limitation to be worked around. It is what gives flow control: a producer faster than its consumer is made to wait, exactly as Chapter twenty three's pipe made the writer wait.

Quick revision

The bounded buffer, or producer and consumer, problem: the producer must not add to a full

buffer, the consumer must not take from an empty one, and they must not both change it at once.

Three semaphores: empty initialised to n, full to 0, mutex to 1.
The producer waits on empty then mutex, and signals mutex then full. The consumer waits

on full then mutex, and signals mutex then empty.

The waits must be in that order. mutex first means the producer holds the lock while

waiting for a slot only the consumer can free: a deadlock, shown here five times out of five.

The signals may be in either order, because a signal never blocks.
A circular queue advances its indices with (i + 1) % n, so the array is reused for ever.

With the semaphores counting, no full or empty test is needed at all.

The invariant to check an answer with: empty + full equals n whenever nobody is inside.

Test yourself

State the bounded buffer problem. A producer adds items to a buffer of n slots and a

consumer removes them; the producer must not add when it is full, the consumer must not remove when it is empty, and they must not both change the buffer at the same time.

Name the three semaphores, their initial values and what each counts. empty, initialised

to n, counts free slots; full, initialised to 0, counts items waiting; mutex, initialised to 1, is the lock on the buffer.

The Bounded Buffer, Solved

Write the producer's four semaphore operations in order. wait(empty), wait(mutex),

then signal(mutex), signal(full).

What happens if the producer waits on the mutex before empty? With a full buffer it

holds the mutex and waits for a free slot, which only the consumer can create, and the consumer cannot get the mutex to do so. Both wait for ever: a deadlock.

Does the order of the two signals matter? No. A signal never blocks, so nothing can be

held up by it.

How does a circular queue reuse the array? Each index is advanced with the remainder

operation, so on reaching the end it wraps round to the beginning.

With only in and out, why can a circular buffer not tell full from empty? Because both

states have in equal to out. Either keep a count, leave one slot always empty, or let counting semaphores do the counting.

The rest of this subject

These notes are cut from the University's printed syllabus. Open the syllabus itself, or the past papers, for the same subject.

Issue