Practical 5: Process Synchronisation and the Bounded Buffer

They need #include <semaphore.h> and no union semun, nothing survives the program, and there is nothing to clean up with ipcrm. The middle argument of sem_init is a flag: 0 for threads of one process, non-zero for a semaphore in shared memory that other processes can see.

The circular queue, which is how a bounded buffer is managed

MU's third bullet. A bounded buffer is an array of fixed size used as a queue, and the trick is how the two ends move.

An ordinary array queue takes items at the front and adds them at the back, and after a while both indices have walked off the end even though the array is nearly empty. A circular queue brings them back round with one operator:

in  = (in  + 1) % SIZE;      /* the producer's index */
out = (out + 1) % SIZE;      /* the consumer's index */

% SIZE is the whole idea. With SIZE of 4, in runs 0, 1, 2, 3, 0, 1, 2, 3 for ever, and the array is reused round and round with no copying and no wasted space.

Here is a buffer of four slots with two items in it, and the two indices in their places:

out points at the next item to be taken. in points at the next free slot to be filled. When in reaches 3 and the producer fills it, (3 + 1) % 4 is 0 and in is back at the beginning; by then slot 0 has long since been emptied.

The indices alone cannot tell you whether the buffer is full or empty. When in equals out, the buffer is either completely empty or completely full and the two cases look identical. There are three standard cures, and this chapter uses the first because MU asks for semaphores:

1. Let the semaphores count. empty and full know how many slots are which, so the indices

never have to be compared at all. This is the cleanest answer.

1. Keep a separate count of items. One more variable, incremented and decremented under the

mutex.

1. Leave one slot always empty, so full is (in + 1) % SIZE == out. This wastes one slot and

is what a queue with no semaphores does. It comes back in [Practical 16: Queues and Circular Queues], where it is the standard answer.

The program: two producers, three consumers, four slots

#include <stdio.h>
#include <pthread.h>
#include <semaphore.h>

#define SIZE      4
#define PRODUCERS 2
#define CONSUMERS 3
#define PER       10                   /* items each producer makes */

static int  buffer[SIZE];
static int  in, out;                   /* the circular queue's two indices */
static long produced_total, consumed_total;

static sem_t empty, full;
static pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;

static void *producer(void *arg)
{
    long id = (long) arg;

    for (int i = 1; i <= PER; i++) {
        int item = (int) (id * 100 + i);      /* 101..110, then 201..210 */

        sem_wait(&empty);                     /* 1. wait for a free slot */
        pthread_mutex_lock(&lock);            /* 2. then take the lock */

        buffer[in] = item;
        in = (in + 1) % SIZE;
        produced_total = produced_total + item;

        pthread_mutex_unlock(&lock);          /* release in the opposite order */
        sem_post(&full);                      /* one more filled slot */
    }
    return NULL;
}

static void *consumer(void *arg)
{
    long want = (long) arg;                   /* how many this one must take */

    for (long i = 0; i < want; i++) {
        sem_wait(&full);                      /* 1. wait for a filled slot */
        pthread_mutex_lock(&lock);            /* 2. then take the lock */

        int item = buffer[out];
        out = (out + 1) % SIZE;
        consumed_total = consumed_total + item;

        pthread_mutex_unlock(&lock);
        sem_post(&empty);                     /* one more free slot */
    }
    return NULL;
}

int main(void)
{
    if (sem_init(&empty, 0, SIZE) == -1 || sem_init(&full, 0, 0) == -1) {
        perror("sem_init");
        return 1;
    }

    pthread_t p[PRODUCERS], c[CONSUMERS];
    long total = (long) PRODUCERS * PER;

    /* the work is shared out so that the consumers between them take
       exactly as many items as the producers make, and nobody is left
       waiting at the end for an item that will never come */
    long share = total / CONSUMERS;
    long extra = total % CONSUMERS;

    for (long i = 0; i < PRODUCERS; i++)
        if (pthread_create(&p[i], NULL, producer, (void *) (i + 1)) != 0)
            return 1;

    for (long i = 0; i < CONSUMERS; i++) {
        long want = share + (i < extra ? 1 : 0);
        if (pthread_create(&c[i], NULL, consumer, (void *) want) != 0)
            return 1;
    }

    for (int i = 0; i < PRODUCERS; i++)
        pthread_join(p[i], NULL);
    for (int i = 0; i < CONSUMERS; i++)
        pthread_join(c[i], NULL);

    printf("items produced by %d producers : %ld\n", PRODUCERS, total);
    printf("the sum of everything produced : %ld\n", produced_total);
    printf("the sum of everything consumed : %ld\n", consumed_total);
    printf("nothing lost, nothing doubled  : %s\n",
           produced_total == consumed_total ? "yes" : "NO");

    sem_destroy(&empty);
    sem_destroy(&full);
    return 0;
}

items produced by 2 producers : 20
the sum of everything produced : 3110
the sum of everything consumed : 3110
nothing lost, nothing doubled  : yes

Why the totals are the proof

Twenty items went through a buffer of four slots, driven by five threads, and the two sums are equal on every run.

The numbers are chosen so that the sum is worth checking by hand. Producer 1 makes 101 to 110, which adds up to 1055; producer 2 makes 201 to 210, which adds up to 2055; 1055 plus 2055 is 3110. Each item is distinct, so an item consumed twice or missed altogether would change the consumed total, and a wrong index would read a slot that had not been written and add the wrong number. The equality of the two sums is a much stronger check than printing the items, because the items come out in a different order every run and their sum does not.

That is the general lesson about testing concurrent programs: find a quantity that is invariant whatever the scheduling does, and check that.

The order of the two waits

Look at the producer again:

sem_wait(&empty);            /* first the resource  */
pthread_mutex_lock(&lock);   /* then the lock       */
   ...
pthread_mutex_unlock(&lock);
sem_post(&full);             /* release in the opposite order */

The resource first, the lock second, and release in the opposite order. That rule was stated at the end of Practical 1. The next section shows what breaking it costs, by running it.

The deadlock, run

The same program with the two waits swapped in both threads. Nothing else is different.

#include <stdio.h>
#include <pthread.h>
#include <semaphore.h>

#define SIZE 2

static int  buffer[SIZE];
static int  in, out;
static sem_t empty, full;
static pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;

static void *producer(void *arg)
{
    (void) arg;
    for (int i = 1; i <= 10; i++) {
        pthread_mutex_lock(&lock);       /* THE WRONG WAY ROUND */
        sem_wait(&empty);
        buffer[in] = i;
        in = (in + 1) % SIZE;
        sem_post(&full);
        pthread_mutex_unlock(&lock);
    }
    return NULL;
}

static void *consumer(void *arg)
{
    (void) arg;
    for (int i = 1; i <= 10; i++) {
        pthread_mutex_lock(&lock);       /* THE WRONG WAY ROUND */
        sem_wait(&full);
        (void) buffer[out];
        out = (out + 1) % SIZE;
        sem_post(&empty);
        pthread_mutex_unlock(&lock);
    }
    return NULL;
}

int main(void)
{
    sem_init(&empty, 0, SIZE);
    sem_init(&full, 0, 0);

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

    printf("this line is never reached\n");
    return 0;
}

That program prints nothing and never ends. Run it with a stopwatch and it will still be there:

$ gcc -Wall -Wextra -pthread -o deadlock deadlock.c
$ timeout 3 ./deadlock
$ echo $?
124

timeout returns 124 when it has to kill the program, and that is what the checker for this book demanded: the listing is marked as a program that never finishes, and a version that finished would have been reported as a failure. The deadlock on this page is a measured fact, not a prediction.

Why it deadlocks

The buffer holds two slots, so after two items the empty semaphore is 0. Then:

Each holds what the other needs, and neither can move. That is a deadlock, and it is the exact picture of the four conditions Coffman set out, all of which must hold at once for one to be possible:

Break any one of the four and a deadlock is impossible. Putting sem_wait(&empty) before pthread_mutex_lock breaks hold and wait: the producer waits for the slot while holding nothing, so the consumer can always get the mutex and free a slot. That is why the rule is the rule.

This program has a second symptom, and it is worth noticing as well: it also holds the mutex while blocked, so the whole buffer is locked by a thread that is asleep. Even without the deadlock, never block while holding a lock is a rule in its own right.

Watching the buffer fill and empty

The last program prints the state after each operation, so the circular queue can be seen going round. One producer, one consumer, the consumer deliberately slower, and the buffer's occupancy read out of the semaphores.

#include <stdio.h>
#include <time.h>
#include <pthread.h>
#include <semaphore.h>

#define SIZE  3
#define ITEMS 6

static int buffer[SIZE];
static int in, out;
static sem_t empty, full;
static pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;

static void nap(long millis)
{
    struct timespec t = { millis / 1000, (millis % 1000) * 1000000L };
    nanosleep(&t, NULL);
}

static void *producer(void *arg)
{
    (void) arg;
    for (int i = 1; i <= ITEMS; i++) {
        sem_wait(&empty);
        pthread_mutex_lock(&lock);
        buffer[in] = i * 11;
        printf("producer: put %2d at index %d\n", buffer[in], in);
        fflush(stdout);
        in = (in + 1) % SIZE;
        pthread_mutex_unlock(&lock);
        sem_post(&full);
        nap(20);
    }
    return NULL;
}

static void *consumer(void *arg)
{
    (void) arg;
    for (int i = 1; i <= ITEMS; i++) {
        sem_wait(&full);
        pthread_mutex_lock(&lock);
        printf("consumer: took %2d from index %d\n", buffer[out], out);
        fflush(stdout);
        out = (out + 1) % SIZE;
        pthread_mutex_unlock(&lock);
        sem_post(&empty);
        nap(60);                        /* three times slower than the producer */
    }
    return NULL;
}

int main(void)
{
    sem_init(&empty, 0, SIZE);
    sem_init(&full, 0, 0);

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

    printf("both finished, in is %d and out is %d\n", in, out);
    sem_destroy(&empty);
    sem_destroy(&full);
    return 0;
}

producer: put 11 at index 0
consumer: took 11 from index 0
producer: put 22 at index 1
producer: put 33 at index 2
producer: put 44 at index 0
consumer: took 22 from index 1
producer: put 55 at index 1
consumer: took 33 from index 2
producer: put 66 at index 2
consumer: took 44 from index 0
consumer: took 55 from index 1
consumer: took 66 from index 2
both finished, in is 0 and out is 0

Three things in that run, and all three are the point of the exercise.

The indices wrap. Index 0 is used twice, once for item 11 and again for item 44, because (2 + 1) % 3 is 0. The array of three slots carried six items.

The producer got ahead and then had to stop. It put 11, 22, 33 and 44 in before the consumer had taken much, and then it had to wait: with three slots and three items outstanding, empty was

1. That is buffer control working.

Both indices end at 0. Six items through a buffer of three slots means each index went round exactly twice, so both are back where they started. That is a small invariant worth checking in your own run: after N items through a buffer of size S, both indices are at N modulo S.

The interleaving of the lines is not the same on every run, so the checker compares them as a set; the line above is a real run. What is fixed, and what the program guarantees, is that each item is put exactly once and taken exactly once, and that no took line ever names a slot that has not been filled since it was last emptied.

Procedure

1. Write the first program. Compile with gcc -Wall -Wextra -pthread -o bb bb.c and run it five

times. Confirm the two sums are equal each time.

1. Comment out the pthread_mutex_lock and pthread_mutex_unlock lines and run it twenty times.

Note how often the two sums differ.

1. Put the mutex back. Change SIZE to 1 and confirm it still works but that the threads now

alternate strictly.

1. Write the deadlock version. Run it with timeout 3 ./deadlock; echo $? and record the 124.
2. Draw the four Coffman conditions against that program in your journal.
3. Write the watching program. Follow the indices round and check that both end at ITEMS modulo

SIZE.

1. Make the producer the slower of the two instead and run it again. The buffer now stays nearly

empty, and the consumer waits.

Result

A bounded buffer of four slots, managed as a circular queue with the modulo operator, was driven by two producer threads and three consumer threads using two counting semaphores and one mutex. Twenty distinct items were passed through it and the sum produced equalled the sum consumed on every run, which proves nothing was lost or duplicated. Swapping the semaphore wait with the mutex lock produced a deadlock, confirmed by the program being killed by a three-second timeout with status 124.

Where marks are lost

• Only two semaphores and no mutex. With more than one slot the two indices are a shared

variable and they race. The one-slot version in Practical 1 is the only case where two are enough.

• Taking the mutex before waiting on the semaphore. The deadlock above, and it is a guaranteed

loss of marks because the examiner's program hangs.

• Not releasing in the opposite order. Signal the semaphore after unlocking, not before.
• sem_init(&empty, 0, 0). The empty semaphore starts at SIZE, not at 0. This is the

commonest arithmetic mistake in the exercise and it makes the producer block immediately.

• Forgetting % SIZE. The index walks off the end of the array, which is a segmentation fault

or, worse, silent corruption.

• Comparing in with out to test for full or empty while also using semaphores. Pick one

mechanism; the semaphores already know.

• Consumers waiting for items that will never come. If the consumers between them expect more

items than the producers make, the extra consumers block for ever and the program never ends. The share-out in main is there for that reason.

• Doing input or output inside the critical section in a real program. It is done in the

watching program above only so that the reader can see the order, and it is noted as a deliberate exception.

For the journal

Write the aim, MU's own wording, the table of the three semaphores with their starting values, and the first program in full with its output. Write the two sums out and add the hand calculation that 1055 plus 2055 is 3110, because that is what shows you checked. Then the deadlock version, the timeout 3 command, the 124, and the four Coffman conditions written against it. The conclusion: a bounded buffer needs two counting semaphores for the slots and one mutex for the indices, the resource must be waited for before the lock is taken, and the circular queue is what lets a fixed array be reused for ever.

Quick revision

• A bounded buffer lets the producer run ahead of the consumer by up to SIZE items. One slot is

the special case where the two must alternate.

• Three mechanisms: empty starting at SIZE counts free slots, full starting at 0 counts filled

slots, and a mutex protects the two indices.

• The mutex is needed as soon as there is more than one slot, because two threads may then be

inside the buffer at once at different positions.

• POSIX semaphores for threads: sem_init, sem_wait, sem_post, sem_destroy, in

semaphore.h. No union semun, and nothing to remove with ipcrm.

• A circular queue is in = (in + 1) % SIZE. The indices alone cannot distinguish full from

empty; let the semaphores count, or keep a separate count, or leave one slot free.

• The order is: wait for the resource, then take the lock, then release the lock, then signal.
• Swap the first two and the program deadlocks: the producer holds the mutex while waiting for a

slot that only the consumer can free, and the consumer needs the mutex.

• Coffman's four conditions, all needed at once: mutual exclusion, hold and wait, no preemption,

circular wait. Waiting for the resource before the lock breaks hold and wait.

• Never block while holding a lock.
• Test a concurrent program by an invariant that the scheduling cannot change, such as the total

produced against the total consumed.

Questions you should be able to answer

1. Why does a bounded buffer need a mutex when the one-slot version did not? Because with several slots a producer and a consumer can legitimately be inside the buffer at the same time at different positions, and then the in and out indices are shared variables that race. With one slot the two semaphores already made simultaneous access impossible.

2. What does each of the three semaphores count, and what does each start at? empty counts free slots and starts at SIZE; full counts filled slots and starts at 0; the mutex grants the right to touch the indices and starts at 1.

3. What is the correct order of the two waits in the producer, and why? Wait on empty first, then take the mutex. A producer that holds the mutex while waiting for a slot prevents the consumer from freeing one, which is a deadlock.

4. State the four conditions for a deadlock and point to each of them in the broken program. Mutual exclusion, which is the mutex; hold and wait, which is the producer holding the mutex while waiting on empty; no preemption, since nothing can take the mutex away; and circular wait, since the producer waits for the consumer and the consumer for the producer.

5. How does the circular queue reuse the array, and what does the modulo do? in = (in + 1) % SIZE brings the index back to 0 after the last slot, so the array is used round and round with no copying. With SIZE of 3, the indices run 0, 1, 2, 0, 1, 2.

6. When in equals out, is the buffer full or empty? It cannot be told from the indices alone. The semaphores know, or a separate count of items can be kept, or one slot can be left permanently empty so that full is (in + 1) % SIZE == out.

7. How do you know that no item was lost or consumed twice? Because each item is a distinct number and the sum of what was produced equals the sum of what was consumed. The order changes on every run and the sum does not, which is what makes it a usable test.

8. Six items pass through a buffer of three slots. Where do the indices end up? Both at 0. Six modulo three is nought, so each index has gone round exactly twice.