Session 9: Semaphores

Textbook: Sections 2.2 and 2.3

Semaphores

Applications

Producers and consumers
Readers and writers

Semaphores

The final solution involves adding two system calls to the OS called down() and up(). They take as their parameter an object called a semaphore, which simply holds a single integer.

void down(semaphore sema) {        void up(semaphore sema) {
    while(sema == 0) block(sema);      if(sema == 0) wake(sema);
    --sema;                            ++sema;
}                                  }

It's important that both of these functions operate atomically - that is, the operating system needs to make sure that the OS doesn't switch the process off the CPU while still running down() or up() (unless, of course, the process has entered the block() function). The semaphores are implemented as part of the OS, so the OS can of course ensure that down() and up() complete before it interrupts the process.

This takes advantage of two functions: block() inserts the currently running process into the semaphore's waiting queue, and puts the process into the blocked state. The wake() function removes a process from the semaphore's waiting queue, and places it into the ready state, so that it can later attempt to seize the semaphore.

One nice thing about semaphores is that they can be relatively general: For a critical section, you would start the semaphore at 1, allowing only 1 process into a critical section at a time. But by using larger values, you can do more creative things. This will be illustrated in our solution to the producer-consumer problem.

Applications

Now we're going to look at a few classic synchronization problems, and how we can solve them using semaphores. This will give us a better feel of both the types of problems where synchronization pops up and the ways in which semaphores can be used.

Producers and consumers

In the producer-consumer problem, we have a set of processes that generate items, and we have a set of processes that consume items. There is a buffer that can hold N items that have been produced but not yet consumed. We want to synchronize the processes to manipulate this buffer safely.

We'll actually use three semaphores to accomplish this. The empty semaphore holds the number of empty slots of the buffer. The full semaphore holds the number of full slots of the buffer. And the mutex semaphore controls things so only one process can manipulate the buffer at a time.

Here are two functions that the producer and consumer can use.

void add_item(item what) {      item remove_item() {
    down(empty);                    down(full);
    down(mutex);                    down(mutex);
    add_to_buffer(what);            item ret = remove_from_buffer();
    up(mutex);                      up(mutex);
    up(full);                       up(empty);
                                    return ret;
}                               }

In this solution, the producer first decrements the number of empty slots of the buffer (and if there are no empty slots, it waits until there is one), effectively reserving an empty slot for itself. Then it gets the lock on the buffer, adds to the buffer, and unlocks the buffer. Finally, it increments the number of full slots of the buffer. The consumer works in the reverse: It decrements the number of full slots to reserve the slot it consumes, then it gets the lock, consumes it, releases the lock, and increments the number of empty slots.