Deadlock

In the computing world deadlock refers to a specific problem when two or more processes are waiting on the same shared resource. Deadlocks are a common problem in multiprocessing where many processes share a specific type of mutially exclusive resource known as a lock. They are particularly troubling because there is no general solution to avoiding deadlocks.

An example of a deadlock occurs frequently in database products. Client applications using the database may require exclusive access to a given table, and in order to gain exclusive access they ask for a lock. If two client applications both attempt to lock the same table at the same time, neither will receive it, there's no general way to decide who to give the lock to. In this case both clients will wait for the lock forever.

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 – say 1k. 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 doesn't have an entire 1k 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.

Four conditions are necessary for deadlocks to occur.

• hold and wait strategy for shared resources
• mutual exclusion
• no preemption of resources
• cyclic dependency chains

Deadlock prevention or avoidance can be achieved by preventing any one of the necessary conditions, though this may require special strategies (e.g priority ceiling protocol[?] in real time systems). Often deadlock prevention is not used, and instead deadlock detection is used, followed by a form of clean up operation to release any deadlock once it has happened.

Links

Deadlocks (http://www.cs.umanitoba.ca/~cs343/notes/6deadlock.pdf)