Deadlock

A deadlock is a situation wherein two or more competing actions are waiting for the other to finish, so neither ever does. It is often seen in a paradox, like the chicken or the egg.

In the computing world deadlock refers to a specific problem when two or more processes are waiting on the same shared resource. Deadlocks are a common problem in multiprocessing where many processes share a specific type of mutually exclusive resource known as a lock. They are particularly troubling because there is no general solution to avoiding deadlocks.

An example of a deadlock occurs frequently in database products. Client applications using the database may require exclusive access to a given table, and in order to gain exclusive access they ask for a lock. If two client applications both attempt to lock the same table at the same time, neither will receive it, there is no general way to decide who to give the lock to. In this case both clients will wait for the lock forever.

Another example would be a text formatting program that expects text to be sent to it and then outputs the results, but does so only after receiving "enough" text to work on (e.g. 1KB). A text editor program is written that talks to the formatter and then waits for the results. In this case a deadlock often occurs on the last block of text. The client program does not have an entire 1KB to send, so it sends the last 234 Bytes (all it has left) and waits. Meanwhile the formatter also waits for the client to finish sending the rest of that 1k block. Both will wait forever. This type of deadlock is sometimes referred to as deadly embrace (properly when only two applications are involved) or starvation.

Table of contents

1 Necessary conditions
2 Deadlock avoidance
3 Deadlock prevention
4 Deadlock detection

Necessary conditions

Mutual exclusion condition: a resource is either assigned to one process or it is available
Hold and wait condition: processes already holding resources may request new resources
No preemption condition: only a process holding a resource may release it
Circular wait condition: two or more processes form a circular chain where each process waits for a resource that the next process in the chain holds

Deadlock avoidance

Deadlock can be avoided if certain information about processes is available in advance of resource allocation. For every resource request, the system sees if granting the request will mean that the system will enter an unsafe state, meaning a state that could result in deadlock. The system then only grants request that will lead to safe states. In order for the system to be able to figure out whether the next state will be safe or unsafe, it must know in advance at any time the number and type of all resources in existence, available, and requested. One known algorithm that is used for deadlock avoidance is the Banker's algorithm. However, for many systems it is impossible to know in advance what every process will request. This means that deadlock avoidance is often impossible.

Deadlock prevention

Deadlocks can be prevented by ensuring that one of the above four conditions does not occur. Removing the mutual exclusion condition means that no one process may have exclusive access to a resource. This proves impossible for resources that cannot be spooled, and even with spooled resources deadlock could still occur. The hold and wait conditions may be removed by requiering processes to request all the resources they will need before starting up; this advance knowledge is again impossible for in many cases. Another way is to require processes to release all their resources before requesting all the resources they will need. This is also often impractical. The no preemption condition may also be impossible to remove as a process has to be able to have a resource for a certain amount of time or the processing outcome may be inconsistent. The easiest condition to remove is the circular wait one. A process may be allowed to posses only one resource at a time, or a numerically ordering may be imposed such that no waiting cycles are possible. For example the priority ceiling protocol is used in real time systems.

Deadlock detection

Often neither deadlock avoidance nor deadlock prevention may be used. Instead deadlock detection and clean up is used by employing an algorithm that tracks the circular waiting and kills one or more of the processes such that deadlock is removed.