Deadlock

related topics
{math, number, function}
{law, state, case}
{system, computer, user}
{@card@, make, design}
{war, force, army}
{company, market, business}
{food, make, wine}

A deadlock is a situation where in two or more competing actions are each waiting for the other to finish, and thus neither ever does. It is often seen in a paradox like the "chicken or the egg". The concept of a Catch 22 is similar.

In computer science, Coffman deadlock refers to a specific condition when two or more processes are each waiting for each other 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 lock or soft lock. Computers intended for the time-sharing and/or real-time markets are often equipped with a hardware lock (or hard lock) which guarantees exclusive access to processes, forcing serialized access. 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 to finish his work with the ruler. Neither request can be satisfied, so a deadlock occurs.

The telecommunications description of deadlock is weaker than Coffman deadlock because processes can wait for messages instead of resources. Deadlock can be the result of corrupted messages or signals rather than merely waiting for resources. For example, a dataflow element that has been directed to receive input on the wrong link will never proceed even though that link is not involved in a Coffman cycle.

Contents

Examples

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.)

Full article ▸

related documents
Bourne shell
Flyweight pattern
Bookmarklet
XML-RPC
World file
Initialization vector
Serial number
Specification language
Normal morphism
Best-first search
Hamiltonian path problem
Column vector
Sum rule in differentiation
Inverse functions and differentiation
Inequation
Additive function
Connectedness
Denormal number
Row and column spaces
Regular graph
Linear function
Parse tree
Babylonian numerals
Church–Rosser theorem
Unitary matrix
Scilab
Hilbert's third problem
Chart parser
Sorting
Data type