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 condition when two processes are each waiting for the other to release a resource, or more than two processes are waiting for resources in a circular chain (see Necessary conditions). 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.
This situation can be likened to two people who are drawing diagrams, with only one pencil and one ruler between them. If one person takes the pencil, the other takes the ruler, a deadlock occurs when the person with the pencil needs the ruler and the person with the ruler needs the pencil. Both requests can't be satisfied, so a deadlock occurs.
An example of a deadlock occurs frequently in database products. Client applications using the database may require exclusive access to a table, and in order to gain exclusive access they ask for a lock. If one client application holds a lock on a table and attempts to obtain the lock on a second table that is held by another client application, this may lead to deadlock if the other application attempts to obtain the lock that is held by the first application.
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.
| Contents |
Necessary conditions
Also known as Coffman conditions from their first description in a 1971 article by E. G. Coffman.
- 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 requiring processes to request all the resources they will need before starting up; this advance knowledge is again impossible 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 circular wait condition is the easiest to remove. A process may be allowed to possess only one resource at a time, or a ranking may be imposed such that no waiting cycles are possible. A hierarchy is typically used to determine a partial order between resources, but where no obvious hierarchy exists even the memory address of resources has been used to determine ordering between resources.
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 the deadlock is removed. It should be noted that this problem is undecidable in general, because the halting problem can be rephrased as a deadlock scenario. In specific environments, using specific means of locking resources, deadlock detection may be decidable; in the general case, however, it is not possible to distinguish between algorithms that are merely waiting for a very unlikely set of circumstances to occur and algorithms that will never finish due to deadlock.
Distributed deadlocks
Distributed deadlocks can occur in distributed systems when distributed transactions or concurrency control is being used. Distributed deadlocks can be detected either by constructing a global wait-for graph from local wait-for graphs at a deadlock detector or by a distributed algorithm like edge chasing.
Phantom deadlocks are deadlocks that are detected in a distributed system but don't actually exist - they have either been already resolved or no longer exist due to transactions aborting.
Livelock
A livelock is similar to a deadlock, except that the state of the two processes involved in the livelock constantly changes with regards to the other process. As a real world example, livelock occurs when two people meet in a narrow corridor, and each tries to be polite by moving aside to let the other pass, but they end up swaying from side to side without making any progress because they always both move the same way at the same time.
See also
External links
- Deadlock Detection Agents (http://dodgers.fmi.uni-passau.de/projects/dda.html)
- Paper "Deadlock Detection in Distributed Object Systems (http://www.cs.ucl.ac.uk/staff/w.emmerich/publications/ESEC01/ModelChecking/)" by Nima Kaveh and Wolfgang Emmerich
- Article "Distributed Deadlock Detection (http://www.cse.scu.edu/~jholliday/dd_9_16.htm)" by JoAnne L. Holliday and Amr El Abbadi
- Article "Deadlock detection in distributed databases (http://doi.acm.org/10.1145/45075.46163)" by Edgar Knapp
- Article "Advanced Synchronization in Java Threads (http://www.onjava.com/pub/a/onjava/2004/10/20/threads2.html)" by Scott Oaks and Henry Wong
- Citations by CiteSeer (http://citeseer.ist.psu.edu/cis?q=deadlock+and+detection)
- Coffman, E.G., M.J. Elphick, and A. Shoshani, System Deadlocks, ACM Computing Surveys, 3, 2, 67-78 (1971) (http://www.cs.umass.edu/~mcorner/courses/691J/papers/TS/coffman_deadlocks/coffman_deadlocks.pdf).ca:Abraçada mortal