Deadlock

Definition

A set of processes is deadlocked if each process in the set is waiting for an event that only another process in the set can cause. —Andrew Tanenbaum

In simpler terms, deadlock occurs when two or more processes are blocking each other, and none are willing to 'give ground' to allow other processes to progress - thus, all the processes will remain in deadlock indefinitely.

A typical example of this is in resource management, such as when two processes attempt to acquire exclusive access to a pair of files. If Process 1 has exclusive access to File A, and attempts to acquire exclusive access to File B, whilst Process 2 has exclusive access to File B, and wants exclusive access to File A, then both will block waiting for the other to finish and release it's lock.

For a deadlock to occur, certain conditions must hold:

1. A process must be able to acquire exclusive access to a given resource, such that it is the only process allowed access - otherwise, one process cannot impede the progress of another.
2. A process must also be able to acquire such access to one resource, wait for a given period of time (during which other processes may act and acquire locks of their own), then acquire access to another resource without losing the previous exclusive lock - "Hold and Wait". If this is not the case, then a process can have exclusive access and block other processes, or be blocked and waiting for access, but not both simultaneously.
3. A process' exclusive lock most also be immune to preemption. If an external agent is capable of removing the process' exclusive access to a resource, it becomes possible for another process to acquire that resource, and the deadlock ends.
4. A process will not stop from trying to acquire a lock once it has started doing so. If it can, it is able to continue doing other operations and consequently is no constituting to an deadlock (as it is not longer waiting)
5. It must also be the case, as stated above, that there exists a circle of processes that require access to a resource locked by the next process in the circle. Obviously, deadlock cannot occur where only one process exists, or where the resources accessible by different threads is otherwise controlled. For example, Process 1 can lock resources A and B, Process 2 can lock B and C, and Process 3 can lock C and D - no other access is allowed. In this case, it is not possible for a circle of blocking processes to form, and deadlock cannot occur.

Prevention

Preventing deadlock is possible by preventing at least one of the conditions above. The first is straightforward - if resources cannot be locked, deadlock is impossible, though this 'solution' is often not viable. Memory space, for example, must be exclusively assigned, to prevent processes corrupting each other's data. A more intelligent locking system can be employed in some cases, however - files may have an exclusive write lock, and still be readable, preventing many potential deadlocks. Wait-Free synchronization studies this kind of approach.

The second condition can be solved by requiring that a processes relinquish all locked resources before accessing more, allowing other processes an opportunity to acquire those resources and to proceed. This can either be implemented as limiting the number of simultaneous locks held by a resource to one (so it must release the last lock it held before acquiring another), or by requiring the process to declare all it's lock atomically - that is, rather than lock A, wait, then lock B, a process must lock A and B in a single call (or lock A, wait, release A and then lock A and B). Thus, if another process holds either resource, the requesting process gets no locks, and must wait until all resources become free, and it can proceed without impedance. However, this requires either knowledge of all required resources in advance, which is not always possible, or that the process keep requesting and releasing resources.

The viability of preventing the third condition depends on the resources in question, and whether it is possible to preempt a process' access to the resource, and later restore it to the state it was in before the preemption. For example, if two processes each occupy half of the available memory space and both request more, deadlock can occur. However, one process may be preempted by paging it into virtual memory, allowing the other process to continue, before paging the preempted process back into memory - in this case, preemption is transparent and the process never knows that it lost exclusive access. Alternately, preemption may simply inform the process that it has lost access and require the process to deal with the fallout. In some cases, though, preemption is not possible or safe - preempting a print job half way through is simply a waste of ink. Also, preemption requires a trigger - there must therefore be a means to detect deadlocks, even if this is as simple as causing locks held by a blocked process to timeout.

The fourth condition is similar to the third, in that processes can be notified of potential deadlocks. However, no locks are released which can make the situation easier to handle for the process in question.

The final condition requires careful planning of the resources that each process can lock. If each resource is only accessible by a single process, which mediates access by other threads (e.g. a print spooler) then deadlocks are prevented. However, this requires much more pre-planning, and is often more trouble than the risk of deadlocks - if 10 processes exist, and each may only use one tenth of the memory space, or may only run on one tenth of the processor time, then resource efficiency is seriously compromised to prevent deadlocks that will almost certainly never occur. Resource ordering is also a powerful means of preventing deadlocks. If locks can be numbered, and the program will only acquire them in increasing order, there can not be any deadlocks since a program will not be able to start waiting on any program that has only lower-numbered locks, and hence no waiting cycles can exist.