And now for something completely different

I'm taking the basic or introductory course on operating systems which pretty much means reading about 600 pages of Tanenbaum's Modern Operating Systems and then going to the final exam.

Some of things in the book like solving the classical IPC (InterProcess Communication) problems using the different IPC primitives (semaphores, monitors etc.) that include writing pseudocode. I think I'll understand and remember them better by writing them down as blog entries with possibly illustrations.

This is pretty much straight from the book but if there are errors, feel free to correct them.

So I'll begin with the classical IPC problems.

First a little introduction to semaphores:

I'm not planning to explain everything, that's what the books are for, but problems in interprocess communication revolve around situations where simultaneously (well in the multiprogramming sense) running processes must not be allowed to for example access certain variables simultaneously.

Different primitives have been invented to answer these issues of mutual exclusion, race conditions and synchronization.

A semaphore is basically an integer variable that keeps track of sleeping processes.

If a semaphores value is 0, there are no pending wake-ups on it and conversely if it has a value larger than 0, there are processes sleeping on it.

A process can perform two operations on a semaphore:
- DOWN: The process checks if the semaphore has a value greater than zero.
- If the value was larger than zero, the value is decremented by one and the process can continue to do whatever it was going to do.
- If the value is zero, the process is forced to sleep on the semaphore.

- UP: The semaphore is incremented and if there were processes sleeping on it, one of them is allowed to wake up and perform it's pending DOWN and let it do what it was originally planning to.

They key point here is that the UP and DOWN operations are atomic, that is no other process can interfere during an UP or DOWN operation and alter the semaphore's value. This atomicity makes it possible to use semaphores in synchronization and avoiding race conditions.

The Producer-Consumer problem

One of the classic problems is the Producer-Consumer problem. It involves two processes that share a common, fixed-size buffer. The Producer inserts information into the buffer and the consumer takes information out of it.

The basic problem is what to do when
a) The producer wants to put information into a full buffer
b) The consumer wants to take information from an empty buffer

A simple idea is to have the producer / consumer go to sleep and wait for its counterpart to make room or fill the buffer and then have it wake the sleeping process. This can however lead to a race condition as follows:

There's a variable count that keeps track of the number of items in the buffer. The producer checks if it's less than N (the size of the buffer) and the consumer checks if it's greater than 0.

Since there is no protection on the count variable the following could happen:
- The buffer is full and the producer checks the count and finds out that it's N. Now since this is a multiprogramming system, the scheduler decides the producer process has ran long enough and gives the turn to the consumer.
- The consumer takes one item from the buffer. It's been code to check if it is actually making room to a previously full buffer which is now the case. This means there has to be a sleeping producer there. (Actually I'm not sure why this is presumed.. ?) Anyway the consumer then sends a wake-up signal which is lost because the producer hasn't actually went to sleep
yet.
- Now when producer runs again, it tests the value of count which it previously read to its local variable and finds it N even though there in reality is room in the buffer. So the Producer goes to sleep and the consumer keeps running until the buffer runs out. Now the producer also goes to sleep.
- We have a situation where both processes are asleep waiting for each other to wake them up which will never happen.

The problem is easily solved with semaphores. The book's example uses three of them: full for counting the number of used slots, empty for counting the empty slots and mutex for making sure there's only one process at the buffer at any given time.

The buffer is initially empty to the full-semaphore is initialized to 0, empty is N and mutex is 1. Semaphores that are initially 1 and used by processes to ensure mutual exclusion in critical areas are called mutexes or binary semaphores. If each process does a down on a mutex before entering its critical region and up just after leaving it, mutual exclusion
is guaranteed.

Here's the code for the producer-consumer with semaphores:

#define N 100    /* Size of the buffer */
typedef int semaphore;
semaphore mutex = 1;
semaphore empty = N;
semaphore full = 0;

void producer()
{
    int item;

    while (TRUE) {
       item = produce_item();    /* generate an item */
       down(&empty);        /* make sure there is room in the buffer */
       down(&mutex);        /* enter critical region */
       insert_item(item);    /* insert the item */
       up(&mutes);        /* leave critical region */
       up(&full);        /* increment the count of full slots */
    }
}

void consumer()
{
    int item;

    while (TRUE) {
        down(&full);    /* decrement full count making sure there's stuff*/
        down(&mutex);    /* enter critical region */
        item = remove_item();     /* take item from the buffer */
        up(&mutex);         /* leave the critical region */
        up(&empty);         /* increase the number of empty slots */
        consume_item(item);     /* do whatever you want with the item */
    }
}

The semaphores are used in two ways. The mutex for mutual exclusion and the empty/full semaphores to synchronize the processes in other words to stop the consumer from trying to take from an empty buffer and vice versa.

So there. That's enough for now. Coming soon: The Dining Philosophers.

Sources: Tanenbaum, A.S. (2001) Modern Operating Systems, 2nd ed. Upper Saddle River, New Jersey: Prentice Hall