Semaphores
| Depends on | Mutual exclusion • Synchronisation • Locks |
|---|
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 thought 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).
In Linux
The Linux kernel implements semaphores, providing system calls for processes running under to kernel to create and make use of semaphores. The command ipcs -s can be used to list all currently active semaphores.
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 |
|---|
