Although semaphores can solve any synchronization problems don't get the impression that semaphores don't introduce problems of their own. As you've already seen the improper use of semaphores can result in the indefinite suspension of processes waiting on the semaphore queue. However even if you correctly wait and signal individual semaphores it is quite possible for correct operations on combinations of semaphores to produce this same effect. Indefinite suspension of a process because of semaphore problems is a serious issue. This degenerate situation is known as deadlock or deadly embrace.

Deadlock occurs when one process holds one resource and is waiting for another while a second process is holding that other resource and waiting for the first. To see how deadlock can occur consider the following code:

; Process one:

lesi    Semaph1
WaitSemaph

// Assume interrupt occurs here //

lesi    Semaph2
WaitSemaph
.
.
.

; Process two:

lesi    Semaph2
WaitSemaph
lesi    Semaph1
WaitSemaph
.
.
.

Process one grabs the semaphore associated with Semaph1. Then a timer interrupt comes along which causes a context switch to process two. Process two grabs the semaphore associated with Semaph2 and then tries to get Semaph1. However process one is already holding Semaph1 so process two blocks and waits for process one to release this semaphore. This returns control (eventually) to process one. Process one then tries to graph Semaph2. Unfortunately process two is already holding Semaph2 so process one blocks waiting for Semaph2. Now both processes are blocked waiting for the other. Since neither process can run neither process can release the semaphore the other needs. Both processes are deadlocked.

One easy way to prevent deadlock from occurring is to never allow a process to hold more than one semaphore at a time. Unfortunately this is not a practical solution; many processes may need to have exclusive access to several resources at one time. However we can devise another solution by observing the pattern that resulted in deadlock in the previous example. Deadlock came about because the two processes grabbed different semaphores and then tried to grab the semaphore that the other was holding. In other words they grabbed the two semaphores in a different order (process one grabbed Semaph1 first and Semaph2 second process two grabbed Semaph2 first and Semaph1 second). It turns out that two process will never deadlock if they wait on common semaphores in the same order. We could modify the previous example to eliminate the possibility of deadlock thusly:

; Process one:

lesi    Semaph1
WaitSemaph
lesi    Semaph2
WaitSemaph
.
.
.

; Process two:

lesi    Semaph1
WaitSemaph
lesi    Semaph2
WaitSemaph
.
.
.

Now it doesn't matter where the interrupt occurs above deadlock cannot occur. If the interrupt occurs between the two WaitSemaph calls in process one (as before) when process two attempts to wait on Semaph1 it will block and process one will continue with Semaph2 available.

An easy way to keep out of trouble with deadlock is to number all your semaphore variables and make sure that all processes acquire (wait on) semaphores from the smallest numbered semaphore to the highest. This ensures that all processes acquire the semaphores in the same order and that ensures that deadlock cannot occurs.

Note that this policy of acquiring semaphores only applies to semaphores that a process holds concurrently. If a process needs semaphore six for a while and then it needs semaphore two after it has released semaphore six there is no problem acquiring semaphore two after releasing semaphore six. However if at any point the process needs to hold both semaphores it must acquire semaphore two first.

Processes may release the semaphores in any order. The order that a process releases semaphores does not affect whether deadlock can occur. Of course processes should always release a semaphore as soon as the process is done with the resource guarded by that semaphore; there may be other processes waiting on that semaphore.

While the above scheme works and is easy to implement it is by no means the only way to handle deadlock nor is it always the most efficient. However it is simple to implement and it always works. For more information on deadlocks see a good operating systems text.

Chapter Nineteen: Processes Coroutines and Concurrency (Part 15)
29 SEP 1996