Semaphores

Semaphores are a means of implementing access control. They are a ‘classic’ mechanism and are employed in operating systems for various purposes. They can be though of as a count of the number of a particular resource which is currently available.

Here is a description of a ‘counting’ semaphore: this can easily be reduced to a binary semaphore (mutex) if desired.

The semaphore is initialised to a particular value. Service calls allow the semaphore to be decremented or incremented.

The original semaphores were named in Dutch and the etymology has become confused. For non-Dutch speakers here we will use English names with the Dutch abbreviations as the latter are widely used.

A process wanting a resource calls ‘wait’ (P). This uses an atomic operation to decrement the semaphore if it is non-zero. If the semaphore was already zero then the process is (somehow) suspended: let’s assume it is then blocked on that semaphore and some other process can be run.

An English mnemonic could be Procure and Vacate.

This mechanism allows a maximum number of processes into the critical section; that number could be ‘one’ or more, depending on the semaphore initialisation.

When a process leaves the critical section it must return its token by making a signal (V) call. This increments the semaphore; if the semaphore was 0 there may be a process already waiting, in which case the first waiting process can be unblocked. In principle there could be a queue of waiting processes, thus there needs to be a decision: is the queue on a first-come, first-served basis? is there some priority ordering? etc.

Semaphores provide a means of implementing mutexes although with a counting semaphore no track is being kept of which specific processes own tokens, only how many.

Practical example (sort of)

In principle a FIFO queue acts as a form of semaphore, albeit controlling data access rather than code. The input process can put in ‘so many’ elements § before the queue is full and the input is stalled. This is influenced by the output removing data elements (V).

---

It is customary to introduce the Dining Philosophers Problem at this point.

---

Deadlocks

Acquiring one semaphore is typically safe; acquiring more than one can lead to deadlock.

Imagine two processes, A and B which both want exclusive access to two resources, X and Y.

Process A: P(X); P(Y); <critical region>; V(Y); V(X);

Process B: P(Y); P(X); <critical region>; V(X); V(Y);

with a particular timing sequence, A can acquire X and B can acquire Y and then neither process can proceed.

This is an example of a process deadlock.

---

More details and puzzles

If you want to study this area in more depth – or just like some challenging puzzles – you could consult The Little Book of Semaphores (291 pp.); this goes somewhat beyond the scope of this site!

---

Also refer to:	Operating System Concepts, 10th Edition: Chapter 6.6, pages 272-276

Context Dependencies Dependants

Max. number:

Max. distance:

Next

Articles on Deadlock

Atomicity • Deadlock • File Locking • Locks • Multi Threading • Multiprocessors • Mutual exclusion • Operation Ordering • Race Conditions • Reentrancy • Semaphores • Starvation • Threads