Semaphores

The mother and father of all IPC primitives is the Semaphore. Invented by Dijkstra, who is Dutch. A semaphore is an object which contains an integer counter. The counter can be 0 or positive, but never negative. There are two operations on the semaphore, one of which increments the variable, the other of which decrements it. They are called UP and DOWN in the book, but the names SIGNAL and WAIT are rather more descriptive.

Dijkstra originally called the operations 'P' (instead of DOWN) and 'V' (instead of UP). This apparently makes sense if you're Dutch. One of the lift call buttons on the 13th (or was it the 12th?) floor of the Livvy tower used to be engraved with a 'P' instead of an arrow. This may have been an obscure computer science joke. Or it may have been a pointless coincidence.

WAIT decrements the semaphore's counter. If the counter is 0 already, the process blocks until the counter is > 0.
SIGNAL increments the counter. We call it SIGNAL, because if another process is WAITing on the semaphore, SIGNAL will wake it up (and the other process may decrement the semaphore).

Typically the semaphore provides a way to initialise it to a starting value when it is created.

The vital thing about semaphores is that WAIT and SIGNAL are atomic. Unlike the case we looked with the race condition, where two processes cause an awful mess by attempting to both access the same integer variable, access to the semaphore's counter is guaranteed protected against race conditions. (Typically a semaphore is implemented using one of the lower-level mutual exclusion primitives we looked at.)

Who to wake up?

There may be more than one process WAITing on a particular semaphore at any instant of time. When another task performs a SIGNAL on the semaphore, one of the WAITing tasks must be woken up. Which should it be?

One solution is to use a wait queue to hold the list of WAITing processes. A queue is good, because it is 'fair': the first process to block while waiting on the semaphore is the first to be woken when the matching signal is performed. First come, first served. The definition of the semaphore says nothing about being fair, though and the semaphore need not maintain the waiting processes in a queue. There may be other reasonable implementations which do not use a first-in-first-out policy. For example, an implementation might wake the first process with the highest priority. Or it might wake the processes in reverse order---first-in-last-out.

It's implementation-dependent.

Binary semaphores

Semaphores can be used to ensure mutual exclusion between processes.

The example above makes use of a 'binary semaphore'. It only ever has the values 0 and 1 (can you see why). Binary semaphores are ideal for mutual exclusion because we want to ensure that only one process is ever in a critical section.

Other uses of semaphores

But that's not all you can do with semaphores! One can also use semaphores to let one task signal another on a particular event. For example, a semaphore solution to the producer-consumer problem uses semaphores in this way, as does a solution to the readers & writers problem. (These examples also makes use of semaphores for mutual exclusion, as described above.)

The very complicated mathematics of semaphores

Drag over a blackboard and follow the theory.

last updated 13 February 1998