Producer-consumer: semaphore and messages

Race condition

A race condition is a situation in which two or more processes read and write shared data, and the final result depends on the exact order in which they run (who "wins the race"). Example: two processes each do count = count + 1 on a shared variable; if both read the old value before either writes, one update is lost.

Requirements of mutual exclusion

1. No two processes can be in their critical regions at the same time.
2. No assumptions about the speed or number of CPUs.
3. No process outside its critical region may block another process.
4. No process waits forever to enter (bounded waiting).

Producer-consumer using semaphores

(The shared buffer has N slots; mutex = 1, empty = N, full = 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 */
    }
}

Producer-consumer using message passing

Processes communicate with the primitives send(destination, &message) and receive(source, &message), so no shared memory is needed. The consumer starts by sending N empty messages to the producer; each empty message represents an empty slot. The producer receives an empty message (blocking if none), fills it with an item and sends it back. The consumer receives the full message, extracts the item, returns an empty message and consumes the item. The number of messages in the system is fixed at N, so the buffer cannot overflow and no semaphores are needed.

#define N 100                        /* number of slots in the buffer */

void producer(void) {
    int item;
    message m;                       /* message buffer */
    while (TRUE) {
        item = produce_item();
        receive(consumer, &m);       /* wait for an empty message */
        build_message(&m, item);     /* construct a message with the item */
        send(consumer, &m);          /* send item to consumer */
    }
}

void consumer(void) {
    int item, i;
    message m;
    for (i = 0; i < N; i++)
        send(producer, &m);          /* send N empty messages */
    while (TRUE) {
        receive(producer, &m);       /* get a message with an item */
        item = extract_item(&m);     /* take the item out */
        send(producer, &m);          /* send back an empty reply */
        consume_item(item);
    }
}

Messages sent but not yet received are buffered by the OS. If the producer is faster, it blocks at receive until empty messages arrive; if the consumer is faster, it blocks at receive until full messages arrive. Message passing also works across machines (distributed systems), but it is slower than semaphores because of copying and communication.