G53OPS - Operating Systems

This course is run at the The University of Nottingham within the School of Computer Science & IT. The course is run by Graham Kendall (EMAIL : gxk@cs.nott.ac.uk)

Semaphores

In (Dijkstra, 1965) the suggestion was made that an integer variable be used that recorded how many wakeups had been saved. Dijkstra called this variable a semaphore. If it was equal to zero it indicated that no wakeup's were saved. A positive value shows that one or more wakeup's are pending.

Now the sleep operation (which Dijkstra called DOWN) checks the semaphore to see if it is greater than zero. If it is, it decrements the value (using up a stored wakeup) and continues. If the semaphore is zero the process sleeps.

The wakeup operation (which Dijkstra called UP) increments the value of the semaphore. If one or more processes were sleeping on that semaphore then one of the processes is chosen and allowed to complete its DOWN.

Checking and updating the semaphore must be done as an atomic action to avoid race conditions.

Here is an example of a series of Down and Up's. We are assuming we have a semaphore called mutex (for mutual exclusion). It is initially set to 1. The subscript figure, in this example, represents the process, p, that is issuing the Down.

Down1(mutex) // p1 enters critical section (mutex = 0)

Down2(mutex) // p2 sleeps (mutex = 0)

Down3(mutex) // p3 sleeps (mutex = 0)

Down4(mutex) // p4 sleeps (mutex = 0)

Up(mutex) // mutex = 1 and chooses p3

Down3(mutex) // p3 completes its down (mutex = 0)

Up(mutex) // mutex = 1 and chooses p2

Down2(mutex) // p2 completes its down (mutex = 0)

Up(mutex) // mutex = 1 and chooses p2

Down1(mutex) // p1 completes its down (mutex = 0)

Up(mutex) // mutex = 1 and chooses p4

Down4(mutex) // p4 completes its down (mutex = 0)

From this example, you can see that we can use semaphores to ensure that only one process is in its critical section at any one time, i.e. the principle of mutual exclusion.

We can also use semaphores to synchronise processes. For example, the produce and consume functions in the producer-consumer problem. Take a look at this program fragment.

int BUFFER_SIZE = 100;
typedef int semaphore;

semaphore mutex = 1;
semaphore empty = BUFFER_SIZE;
semaphore full = 0;

void producer(void) {
int item;
while(TRUE) {
produce_item(&item); // generate next item
down(&empty); // decrement empty count
down(&mutex); // enter critical region
enter_item(item); // put item in buffer
up(&mutex); // leave critical region
up(&full); // increment count of full slots
}
}

void consumer(void) {
int item;
while(TRUE) {
down(&full); // decrement full count
down(&mutex); // enter critical region
remove_item(&item); // remove item from buffer
up(&mutex); // leave critical region
up(&empty); // increment count of empty slots
consume_item(&item); // print item
}
}

The mutex semaphore (given the above example) should be self-explanatory.

The empty and full semaphore provide a method of synchronising adding and removing items to the buffer. Each time an item is removed from the buffer a down is done on full. This decrements the semaphore and, should it reach zero the consumer will sleep until the producer adds another item. The consumer also does an up an empty. This is so that, should the producer try to add an item to a full buffer it will sleep (via the down on empty) until the consumer has removed an item.

 Last Updated : 13/01/2002