Deadlock (computer science): Difference between revisions

Revision as of 09:07, 20 March 2010

Revision as of 18:13, 23 March 2010

Line 5:

|Illogical [[statute]] passed by the [[Kansas Legislature]]<ref>A Treasury of Railroad Folklore, B.A. Botkin & A.F. Harlow, p. 381</ref>}}

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 reference|circular chain]] (see ''[[Deadlock#Necessary conditions|Necessary conditions]]''). Deadlock is a common problem in [[multiprocessing]] where many processes share a specific type of mutually exclusive resource known as a ''[[lock (computer science)|software lock]]'' or ''soft lock''. Computers intended for the ''[[time-sharing]]'' and/or ''[[real-time computing|real-time]]'' markets are often equipped with a ''hardware lock'' (or ''hard lock'') which guarantees ''[[Read/write lock pattern|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. Both requests can't be satisfied, so a deadlock occurs.

The telecommunications description of deadlock is slightlyweaker stronger:than Coffman deadlock occurs when none of thebecause processes meetcan thewait conditionfor tomessages moveinstead toof anotherresources. stateDeadlock (ascan described inbe the process'sresult [[finiteof statecorrupted machine]])messages ''and''or allsignals therather communicationthan channelsmerely are empty. The second condition is often left out on other systems but is important in thewaiting telecommunicationfor contextresources.

== Examples ==

Line 16 ⟶ 17:

Another example might be a text [[format]]ting 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 sends the formatter with some 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 ''[[Resource starvation|starvation]]''. However, this situation, too, is easily prevented by having the text editor send a ''forcing'' message (eg. EOF) with its last (partial) block of text, which will ''force'' the formatter to return the last (partial) block after formatting, and not wait for additional text.

In communications, corrupted messages may cause computers to go into bad states where they are not communicating properly. The network may be said to be deadlocked even though no computer is waiting for a resource. This is in contrast to Coffman deadlock.

Nevertheless, since there is no ''general'' solution for deadlock prevention, each type of deadlock must be anticipated and specially prevented. But ''general'' algorithms can be implemented within the operating system so that if one or more applications becomes blocked, it will usually be terminated after (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).

Line 22 ⟶ 25:

=== Necessary conditions ===

There are four necessary and sufficient conditions for a Coffman deadlock to occur, known as the ''Coffman conditions'' from their first description in a 1971 article by [[E. G. Coffman]].

#[[Mutual exclusion]] condition: a resource that cannot be used by more than one process at a time