Producer-consumer, readers-writers, dining philosophers

Why it exists

A handful of problems capture the typical ways in which processes must coordinate, and they recur in textbooks, in system code and in GATE questions. Each is a small puzzle in using semaphores correctly: producer-consumer (the bounded buffer: processes that hand data to each other through a queue), readers-writers (many readers or one writer on shared data), and dining philosophers (processes that each need two shared resources at once). Learning their solutions teaches what can go wrong: lost updates, deadlock and starvation.

Prerequisites

You need wait, signal, the value arithmetic and the three uses of a semaphore from semaphores.

Precise definitions

Producer-consumer (bounded buffer)

A producer puts items into a buffer of $N$ slots and a consumer takes them out. Requirements: the producer must wait if the buffer is full, the consumer must wait if it is empty, and the buffer's data structure must be updated by one process at a time.

Three semaphores: mutex = 1 (exclusive access to the buffer), empty = N (number of free slots), full = 0 (number of items).

Producer:                      Consumer:
  repeat                         repeat
    produce an item                wait(full)
    wait(empty)                    wait(mutex)
    wait(mutex)                    remove an item
    insert the item                signal(mutex)
    signal(mutex)                  signal(empty)
    signal(full)                   consume the item
  forever                        forever

At every moment $0 \le \text{count} \le N$, and $\text{empty} + \text{full} = N$ when nobody is inside (the semaphores are counting the slots). The order of the two waits matters: taking mutex before empty (or full) can deadlock. If the buffer is full, the producer holds the mutex and waits for empty; the consumer needs the mutex to make room: neither can proceed.

Readers-writers

A shared data set. Any number of readers may read at the same time; a writer needs exclusive access (no reader and no other writer).

First readers-writers problem (readers preference: no reader waits unless a writer already holds the data). Shared: rc = 0 (number of readers), mutex = 1 (protects rc), wrt = 1 (exclusive access for writers).

Writer:                        Reader:
  wait(wrt)                      wait(mutex); rc++;
  write                          if (rc == 1) wait(wrt);      // the first reader locks out writers
  signal(wrt)                    signal(mutex)
                                 read
                                 wait(mutex); rc--;
                                 if (rc == 0) signal(wrt);    // the last reader lets writers in
                                 signal(mutex)

Readers share, a writer is alone. But a writer can starve: while any reader is active, new readers keep entering (they only wait if a writer is already writing), so a waiting writer can be overtaken without bound.

Second readers-writers problem gives priority to writers: once a writer is waiting, no new reader may start. Now readers can starve. A fair solution (a third version) queues requests in arrival order, so neither starves, at some cost in concurrency.

Dining philosophers

Five philosophers sit at a round table with a fork between each pair (five forks). A philosopher thinks, then needs both the left and the right fork to eat, then puts them down. Each fork is a semaphore with value 1.

Naive solution (each takes the left fork, then the right):

Philosopher i:
  repeat
    think
    wait(fork[i]); wait(fork[(i + 1) % 5]);
    eat
    signal(fork[i]); signal(fork[(i + 1) % 5])
  forever

Neighbours never eat together, but it can deadlock: if all five take their left fork at the same moment, each holds one fork and waits for the next, which is held by the neighbour: a circular wait.

Deadlock-free fixes.

• Limit the number at the table: allow at most $n - 1$ philosophers to try to eat at once (a semaphore room initialised to $n - 1$). With one fewer than forks, some philosopher can always take both.
• Asymmetric / ordered pick-up: number the forks and always take the lower-numbered fork first (a similar fix: an odd philosopher takes the left fork first and an even one the right fork first; either way the circular wait is broken). This breaks the circular wait.
• Pick up both forks atomically (inside a critical section, or only if both are free). A monitor-based solution does this.

Avoiding deadlock does not by itself avoid starvation: a philosopher could be bypassed for ever by unlucky timing; extra care (such as fairness in the waiting queues) is needed.

How it works

The animations are real schedules found by exploring every interleaving.

Producer-consumer with a buffer of 2 slots. The producer runs ahead until the buffer is full (empty = 0); it then blocks on wait(empty). The consumer's signal(empty) wakes it. At all times count is between 0 and 2.

▶wait(empty)
wait(mutex)
buffer[in] = item; count = count + 1
signal(mutex)
signal(full)
produce next item

▶wait(full)
wait(mutex)
item = buffer[out]; count = count - 1
signal(mutex)
signal(empty)
consume item

The same buffer with the waits in the wrong order (mutex first). This is the shortest schedule that deadlocks: one thread holds mutex and waits for a slot or an item that the other can only provide by taking mutex.

▶wait(mutex)
wait(empty)
buffer[in] = item; count = count + 1
signal(mutex)
signal(full)
produce next item

▶wait(mutex)
wait(full)
item = buffer[out]; count = count - 1
signal(mutex)
signal(empty)
consume item

Readers-writers (readers preference). Reader R1 is reading when the writer W arrives and blocks on wrt; reader R2 then arrives and starts reading although W has been waiting longer. Repeated for ever, W never gets in.

▶wait(mutex)
rc = rc + 1
if (rc == 1)
wait(wrt)
signal(mutex)
reading
wait(mutex)
rc = rc - 1
if (rc == 0)
signal(wrt)
signal(mutex)
other work

▶wait(mutex)
rc = rc + 1
if (rc == 1)
wait(wrt)
signal(mutex)
reading
wait(mutex)
rc = rc - 1
if (rc == 0)
signal(wrt)
signal(mutex)
other work

▶wait(wrt)
writing
signal(wrt)
other work

Dining philosophers, left fork first. This is the shortest schedule that ends in deadlock: every philosopher holds one fork and is queued on the next.

▶think
wait(fork0)
wait(fork1)
eat
signal(fork0)
signal(fork1)
done eating

▶think
wait(fork1)
wait(fork2)
eat
signal(fork1)
signal(fork2)
done eating

▶think
wait(fork2)
wait(fork0)
eat
signal(fork2)
signal(fork0)
done eating

Worked examples

#define _POSIX_C_SOURCE 200809L
#include <fcntl.h>
#include <pthread.h>
#include <semaphore.h>
#include <stdio.h>
#include <unistd.h>
 
#define SLOTS 4
#define ITEMS 1000
 
static int buffer[SLOTS];
static int in, out, count, max_count;
static sem_t *empty_s, *full_s, *mutex_s;
 
static sem_t *make(const char *tag, unsigned value) {
    char name[64];
    snprintf(name, sizeof name, "/gate_%s_%ld", tag, (long)getpid());
    sem_unlink(name);
    sem_t *s = sem_open(name, O_CREAT | O_EXCL, 0600, value);
    sem_unlink(name);                         /* the semaphore disappears when the program ends */
    return s;
}
 
static void *producer(void *arg) {
    (void)arg;
    for (int i = 1; i <= ITEMS; i++) {
        sem_wait(empty_s);                    /* wait for a free slot */
        sem_wait(mutex_s);                    /* exclusive access to the buffer */
        buffer[in] = i; in = (in + 1) % SLOTS;
        count++;
        if (count > max_count) max_count = count;
        sem_post(mutex_s);
        sem_post(full_s);                     /* one more item */
    }
    return NULL;
}
 
static void *consumer(void *arg) {
    long *sum = arg;
    for (int i = 1; i <= ITEMS; i++) {
        sem_wait(full_s);
        sem_wait(mutex_s);
        *sum += buffer[out]; out = (out + 1) % SLOTS;
        count--;
        sem_post(mutex_s);
        sem_post(empty_s);
    }
    return NULL;
}
 
int main(void) {
    empty_s = make("empty", SLOTS);
    full_s = make("full", 0);
    mutex_s = make("mutex", 1);
    if (empty_s == SEM_FAILED || full_s == SEM_FAILED || mutex_s == SEM_FAILED) { puts("cannot create semaphores"); return 1; }
    pthread_t p, c;
    long sum = 0;
    pthread_create(&p, NULL, producer, NULL);
    pthread_create(&c, NULL, consumer, &sum);
    pthread_join(p, NULL);
    pthread_join(c, NULL);
    printf("consumed %d items, sum %ld (expected %d)\n", ITEMS, sum, ITEMS * (ITEMS + 1) / 2);
    printf("buffer never held more than %d items: %d\n", SLOTS, max_count <= SLOTS);
    printf("items left in the buffer: %d\n", count);
    return 0;
}

consumed 1000 items, sum 500500 (expected 500500)
buffer never held more than 4 items: 1
items left in the buffer: 0

Cheat box

Traps and GATE patterns

Connections

The solutions use semaphores throughout; a monitor expresses the same patterns more safely. The deadlock in the naive philosophers and in the wrong-order buffer is the circular wait of deadlock conditions, and its cures are instances of what is generalized by deadlock avoidance. Starvation in readers-writers is the same phenomenon as the starvation of long jobs in CPU scheduling.

PYQs

Consider the following solution to the producer-
consumer synchronization problem. The shared
buffer size is N. Three semaphores empty,
full and mutex are defined with respective initial
values of 0, N and 1. Semaphore empty denotes the
number of available slots in the buffer, for the
consumer to read from. Semaphore full denotes the
number of available slots in the buffer, for the
producer to write to. The placeholder variables,
denoted by P, Q, R and S, in the code below can be
assigned either empty or full. The valid semaphore
operations are: wait () and signal ().
Producer
Consumer
do{
do {
wait (P);
wait (R);
wait (mutex);
wait mutex);
//Add item to buffer
//Consume item from
buffer
Signal (mutex);
Signal (mutex);
Signal (Q);
Signal (S);
} while (1);
} while (1);

Which one of the following assignments to P, Q, R
and S will yield the correct solution?

Consider the procedure below for the Producer-
Consumer problem which uses semaphores:

semaphore n = 0;
semaphore s = 1;
void producer() void consumer()
{
    while(true) while(true)
    {
        produce();
        semWait(s) ;
        addToBuffer();
        semSignal(s);
        semSignal(n);
    }
}
void consumer()
{
    while(true)
    {
        semWait(s);
        semWait(n);
        removeFromBuffer();
        semSignal(s);
        consume();
    }
}

OPERATING SYSTEMS

Which one of the following is TRUE?

Barrier is a synchronization construct where a set of
processes synchronize globally. Let the number of
processes be three and S be a binary semaphore.
Consider the following implementation:
void barrier(void) {
1:  P(S);
2:  process_arrived++;
3:  V(S);
4:  while (process_arrived != 3);
5:  P(S);
6:  process_left++;
7:  if (process_left == 3) {
8:      process_arrived = 0;
9:      process_left = 0;
10: }
11: V(S);
}
Variables process_arrived and process_left are
shared and initialized to 0.
Which one of the following is true?

Barrier is a synchronization construct where a set of
processes synchronize globally. Let the number of
processes be three and S be a binary semaphore.
Consider the following implementation:

void barrier(void) {

1:  P(S);

2:  process_arrived++;

3:  V(S);

4:  while (process_arrived != 3);

5:  P(S);

6:  process_left++;

7:  if (process_left == 3) {

8:  process_arrived = 0;

9: process_left = 0;

10: }

11: V(S);

}

The variables process_arrived and process_left are
shared and initialized to zero.

Which one of the following rectifies the problem in
the implementation?

Self-check

Revision card

References