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

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Paradox: A paradox is an apparently true statement or group of statements that seems to lead to a contradiction or to a situation that defies intuition. Typically, either the statements in question do not really imply the contradiction, the puzzling result is not really a contradiction, or the premises them...

The chicken or the egg: The dilemma of causality commonly posed as, "Which came first, the chicken or the egg?" is found earliest in writing in Plutarch's Moralia, in the books titled "Table Talk," a series of arguments based on questions posed to various people drinking around a table. Under the section entitled, "Whether...

Multiprocessing: Multiprocessing is traditionally known as the use of multiple concurrent processes in a system as opposed to a single process at any one instant. Like multitasking which allows multiple processes to share a single CPU, multiple CPUs may be used to execute multiple threads within a single process....