Deadlock

Encyclopedia : D : DE : DEA : Deadlock

It has been suggested that Preemption (computing) and Circular wait be [Merging and moving pagesmerged] into this article or section. (:Wikipedia talk:}}})

A deadlock is a situation wherein two or more competing actions are waiting for the other to finish, and thus 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 or more processes are each waiting for another to release a resource, or more than two processes are waiting for resources in a circular chain (see Necessary conditions). Deadlock is a common problem in multiprocessing where many processes share a specific type of mutually exclusive resource known as a software, or soft, lock. Computers intended for the time-sharing and/or real-time markets are often equipped with a hardware, or hard, lock which guarantees exclusive access to processes, forcing serialization. Deadlocks are particularly troubling because there is no general solution to avoid (soft) deadlocks.

This situation may be likened to two people who are drawing diagrams, with only one pencil and one ruler between them. If one person takes the pencil and 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 which may occur in database products is the following. 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 already held by a second client application, this may lead to deadlock if the second application then attempts to obtain the lock that is held by the first application. (But this particular type of deadlock is easily prevented, e.g., by using an all-or-none resource allocation algorithm.)

Another example might be a text formatting program that accepts text sent to it to be processed and then returns the results, but does so only after receiving "enough" text to work on (e.g. 1KB). A text editor program is written that messages the formatter with text and then waits for the results. In this case a deadlock may occur on the last block of text. Since the formatter may not have sufficient text for processing, it will suspend itself while waiting for the additional text, which will never arrive since the text editor has sent it all of the text it has. Meanwhile, the text editor is itself suspended waiting for the last output from the formatter. This type of deadlock is sometimes referred to as a deadly embrace (properly used only when only two applications are involved) or starvation. However, this situation, too, is easily prevented by having the text editor send a forcing message with its last (partial) block of text, which message will force the formatter to return the last (partial) block after formatting, and not wait for additional text.

Nevertheless, since there is no general solution for deadlock prevention, each type of deadlock must be anticipated and specially prevented. But general algorithms exist in the operating system so that if one or more applications becomes blocked, it will usually be terminated after a time (and, in the meantime, is allowed no other resources and may need to surrender those it already has, rolled back to a state prior to being obtained by the application).

Necessary conditions

Also known as Coffman conditions from their first description in a 1971 article by E. G. Coffman.

1. Mutual exclusion condition: a resource is either assigned to one process or it is available
2. Hold and wait condition: processes already holding resources may request new resources
3. No preemption condition: only a process holding a resource may release it
4. 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 prevention

• 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 (or before embarking upon a particular set of operations); this advance knowledge is frequently difficult to satisfy and, in any case, is an inefficient use of resources. Another way is to require processes to release all their resources before requesting all the resources they will need. This too is often impractical. (Such algorithms are known as the all-or-none algorithms.)
• A "no preemption" (lockout) condition may also be difficult or impossible to avoid as a process has to be able to have a resource for a certain amount of time, or the processing outcome may be inconsistent or thrashing may occur. However, inability to enforce preemption may interfere with a priority algorithm. (Note: Preemption of a "locked out" resource generally implies a rollback, and is to be avoided, since it is very costly in overhead.)
• The circular wait condition: A process ranking may be imposed such that the highest ranking process will always obtain its resources, by preemption if necessary. A hierarchy may be used to determine a partial ordering of resources; where no obvious hierarchy exists, even the memory address of resources has been used to determine ordering.

Deadlock detection

Detecting the possibility of a deadlock before it occurs is much more difficult and is, in fact, generally undecidable, because the halting problem can be rephrased as a deadlock scenario. However, in specific environments, using specific means of locking resources, deadlock detection may be decidable. In the general case, 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 because of 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

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

• Dining philosophers problem
• Banker's algorithm
• Hang
• Infinite loop
• Mamihlapinatapai
• Stalemate
• Synchronization

External links

• [Deadlock Detection Agents]
• Paper "[Deadlock Detection in Distributed Object Systems]" by Nima Kaveh and Wolfgang Emmerich
• Article "[Distributed Deadlock Detection]" by JoAnne L. Holliday and Amr El Abbadi
• Article "[Deadlock detection in distributed databases]" by Edgar Knapp
• Article "[Advanced Synchronization in Java Threads]" by Scott Oaks and Henry Wong
• [Citations by CiteSeer]
• [Coffman, E.G., M.J. Elphick, and A. Shoshani, System Deadlocks, ACM Computing Surveys, 3, 2, 67-78 (1971)].
• Paper [Eliminating Receive Livelock in an Interrupt-driven Kernel] by Jeffrey C. Mogul, K. K. Ramakrishnan

From Wikipedia, the Free Encyclopedia. Original article here. Support Wikipedia by contributing or donating.
All text is available under the terms of the GNU Free Documentation License See Wikipedia Copyrights for details.