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.

Related Topics:
Paradox - 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 avoid deadlocks.

Related Topics:
Necessary conditions - Multiprocessing - Lock

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

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.

Related Topics:
Text editor - Formatter - Starvation

~ ~ ~ ~ ~ ~ ~ ~ ~ ~