Deadlock
| Depends on | Processes • Multi Threading • Resources • Starvation |
|---|
Deadlock is a situation where progress cannot be made … ever again. In the context of operating systems we are probably talking about a process but deadlock can occur in any ‘state machine’: network deadlock is a common example, as illustrated below!
A process can deadlock if it competes for resources with another process (or processes).
Scenario 1
| Process 1 | Process 2 | |
|---|---|---|
get(A)
|
get(A)
| |
get(B)
|
get(B)
| |
put(B)
|
put(B)
| |
put(A)
|
put(A)
|
The accessible states are:
Scenario 2
| Process 1 | Process 2 | |
|---|---|---|
get(A)
|
get(B)
| |
get(B)
|
get(A)
| |
put(B)
|
put(A)
| |
put(A)
|
put(B)
|
The accessible states are:
In this case it is possible (though not certain) to reach a state where neither process can proceed and the processes will wait forever.
A more picturesque illustration of deadlock – in a system which has more states – is the Dining Philosophers Problem; this is a classic example!
Deadlock prevention
There are several ways to combat potential deadlocks – too many to delve into here! In brief, there are solutions but they all have a cost.
To prevent you feeling too disappointed, a couple of outlines are given below.
Consider the situation where two processes – X and Y – both want resources A and B.
X: get A; get B;
Y: get B; get A;
This will deadlock if Y gets B after X has got A. Or vice versa.
Ordering claims
If all processes make requests in the same order then the one which has progressed ‘furthest’ will not be blocked, will continue to completion and will release the resources for others to use.
X: get A; get B;
Y: get A; get B;
This sounds simple but may be difficult to achieve when X and Y (and Z) are complex programs from different sources.
Back off!
If a request is denied, give up and start again from ‘scratch’.
X: get A; if (!get B) put A; repeat;
Y: get B; if (!get A) put B; repeat;
This prevents deadlock. However, if the timing of the operations is ‘unfortunate’ it is possible for the processes to interfere so they loop continuously, a situation known as “livelock”, which still prevents progress.
Central arbiter
Instead of a process claiming a resource directly, ask a ‘servant’ for it. This centralised arbiter can decide if a deadlock might occur and avoid the situation by denying the resource (even if it’s currently potentially available)
X: Jeeves(get A); Jeeves(get B);
Y: Jeeves(get B); Jeeves(get A);
Jeeves: Give the first requester what it wants but then check who is asking for what and delay or deny this if it could cause a problem ...
E.g. if X has A then Y can’t have B because X might want it,
This will work: it also relies on a centralised control system which is liable to be a processing or communications bottleneck.
See also: transaction processing.
Note that the phenomenon of deadlock is not uniquely an operating systems’ issue. It is commonly associated with operating systems, presumably because it is most likely to occur in situations where there are complex, non-deterministic interactions.
| Also refer to: | Operating System Concepts, 10th Edition: Chapter 8, pages 318-343 |
|---|
