Producer-consumer using semaphore

Conditions for mutual exclusion

For a correct solution to the critical-section (mutual exclusion) problem, four conditions must hold (Tanenbaum):

1. No two processes may be inside their critical regions at the same time.
2. No assumptions may be made about speeds or the number of CPUs.
3. No process running outside its critical region may block other processes.
4. No process should have to wait forever to enter its critical region (no starvation, i.e. bounded waiting).

Semaphore

A semaphore is an integer variable (introduced by Dijkstra) that can be accessed only through two atomic operations, down (P / wait) and up (V / signal). It is used for mutual exclusion and for synchronization of processes.

down(S):  if (S > 0) S = S - 1;
          else block the calling process (put it on S's queue);
up(S):    if (some process is blocked on S) wake up one of them;
          else S = S + 1;

Both operations are indivisible: once started, no other process can access S until the operation finishes or blocks.

A semaphore initialised to 1 is a binary semaphore (mutex); one initialised to n counts resources.

Producer-consumer (bounded buffer) problem

A producer puts items into a shared buffer of N slots; a consumer removes them. The producer must wait when the buffer is full and the consumer must wait when it is empty, and they must not touch the buffer at the same time.

Three semaphores are used:

• mutex = 1: mutual exclusion on the buffer.
• empty = N: counts empty slots (blocks producer when 0).
• full = 0: counts filled slots (blocks consumer when 0).

#define N 100                 /* number of slots in the buffer */
typedef int semaphore;
semaphore mutex = 1;          /* controls access to the buffer */
semaphore empty = N;          /* counts empty slots */
semaphore full  = 0;          /* counts full slots */

void producer(void) {
    int item;
    while (TRUE) {
        item = produce_item();    /* make an item */
        down(&empty);             /* wait for an empty slot */
        down(&mutex);             /* enter critical region */
        insert_item(item);        /* put item in buffer */
        up(&mutex);               /* leave critical region */
        up(&full);                /* one more full slot */
    }
}

void consumer(void) {
    int item;
    while (TRUE) {
        down(&full);              /* wait for a full slot */
        down(&mutex);             /* enter critical region */
        item = remove_item();     /* take item from buffer */
        up(&mutex);               /* leave critical region */
        up(&empty);               /* one more empty slot */
        consume_item(item);       /* use the item */
    }
}

Working: the producer does down(empty) first, so it sleeps if there is no room; then down(mutex) to access the buffer. The consumer does down(full) and sleeps if the buffer is empty. up(full)/up(empty) wake the other process. Doing down(mutex) before down(empty) would cause deadlock (the producer holding the mutex while sleeping on a full buffer), so the order matters.