FACTOID # 1: Idaho produces more milk than Iowa, Indiana and Illinois combined.
 
 Home   Encyclopedia   Statistics   States A-Z   Flags   Maps   FAQ   About 
   
 
WHAT'S NEW
RELATED ARTICLES
People who viewed "Deadlock" also viewed:
 

SEARCH ALL

FACTS & STATISTICS    Advanced view

Search encyclopedia, statistics and forums:

 

 

(* = Graphable)

 

 


Encyclopedia > Deadlock

A deadlock is a situation wherein two or more competing actions are waiting for the other to finish, and thus neither ever does. It is often seen in a paradox like 'the chicken or the egg'. Deadlock can refer to: Deadlock - a situation in computing Deadlock (game) - a game in the game theory Deadlock: Planetary Conquest - a computer game by Accolade, or its sequel, Deadlock 2: Shrine Wars This is a disambiguation page: a list of articles associated with the same title. ... Look up paradox in Wiktionary, the free dictionary. ... The chicken or the egg is a reference to the causality dilemma which arises from the expression which came first, the chicken or the egg? Since the chicken emerges from an egg, and the egg is laid by a chicken, it is ambiguous which originally gave rise to the other. ...

“When two trains approach each other at a crossing, both shall come to a full stop and neither shall start up again until the other has gone”


-Statute passed by the Kansas State Legislature, early in the 20th century

In the computing world deadlock refers to a specific condition when two or more processes are each waiting for another 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, 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 serialization. Deadlocks are particularly troubling because there is no general solution to avoid (soft) deadlocks. This article is about deadlock in computing. ... Multiprocessing is traditionally known as the use of multiple concurrent processes in a system as opposed to a single process at any one instant. ... In computer science, a lock is a synchronization mechanism for enforcing limits on access to a resource in an environment where there are many threads of execution. ... Alternate uses: see Timesharing Time-sharing is an approach to interactive computing in which a single computer is used to provide apparently simultaneous interactive general-purpose computing to multiple users by sharing processor time. ... Realtime redirects here. ... A software design pattern, read/write lock pattern is used for computer programming. ... In computer science, in the context of data storage and transmission, serialization is the process of saving an object onto a storage medium (such as a file, or a memory buffer) or to transmit it across a network connection link, either in binary form, or in some human-readable text...


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, before he can give up the ruler. Both requests can't be satisfied, so a deadlock occurs.


The telecommunications description of deadlock is a little stronger: deadlock occurs when none of the processes meet the condition to move to another state (as described in the process's finite state machine) and all the communication channels are empty. The second condition is often left out on other systems but is important in the telecommunication context. Fig. ...

Contents

Necessary conditions

There are four necessary conditions for a deadlock to occur, known as the Coffman conditions from their first description in a 1971 article by E. G. Coffman. Year 1971 (MCMLXXI) was a common year starting on Friday (link will display full calendar) of the 1971 Gregorian calendar. ... E.G. Coffman is a computer science professor at the Columbia University He firstly described the four conditions necessary for a deadlock to exist in 1971. ...

  1. Mutual exclusion condition: a resource is either assigned to one process or it is available
  2. Hold and wait condition: processes already holding resources may request new resources
  3. No preemption condition: only a process holding a resource may release it
  4. Circular wait condition: two or more processes form a circular chain where each process waits for a resource that the next process in the chain holds

Deadlock only occurs in systems where all 4 conditions happen. Mutual exclusion (often abbreviated to mutex) algorithms are used in concurrent programming to avoid the simultaneous use of un-shareable resources by pieces of computer code called critical sections. ... Pre-emption as used with respect to operating systems means the ability of the operating system to preempt or stop a currently scheduled task in favour of a higher priority task. ...


Circular wait prevention

Circular wait prevention consists of allowing processes to wait for resources, but ensure that the waiting can't be circular. One approach might be to assign a precedence to each resource and force processes to allocate resources in order of increasing precedence. That is to say that if a process holds some resources, and the highest precedence of these resources is m, then this process cannot request any resource with precedence smaller than m. This forces resource allocation to follow a particular and non-circular ordering, so circular wait cannot occur. Another approach is to allow holding only one resource per process; if a process requests another resource, it must first free the one it's currently holding (or hold-and-wait). Precedence is a simple ordering, based on either importance or sequence. ...


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.) This article is about computing. ...


Another example might be a text formatting 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 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. Look up format in Wiktionary, the free dictionary. ... Notepad is the standard text editor for Microsoft Windows A text editor is a piece of computer software for editing plain text. ... In computer science, starvation is a multitasking-related problem, where a process is perpetually denied necessary resources. ...


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 a time (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)


Avoidance

Deadlock can be avoided if certain information about processes is available in advance of resource allocation. For every resource request, the system sees if granting the request will mean that the system will enter an unsafe state, meaning a state that could result in deadlock. The system then only grants request that will lead to safe states. In order for the system to be able to figure out whether the next state will be safe or unsafe, it must know in advance at any time the number and type of all resources in existence, available, and requested. One known algorithm that is used for deadlock avoidance is the Banker's algorithm, which requires resource usage limit to be known in advance. However, for many systems it is impossible to know in advance what every process will request. This means that deadlock avoidance is often impossible. The Bankers algorithm is a resource allocation and deadlock avoidance algorithm developed by Edsger Dijkstra that tests for safety by simulating the allocation of pre-determined maximum possible amounts of all resources, and then makes a safe-state check to test for possible deadlock conditions for all other pending...


Two other algorithms are Wait/Die and Wound/Wait, each of which uses a symmetry-breaking technique. In both these algorithms there exists an older process (O) and a younger process (Y). Process age can be determined by a time stamp at process creation time. Smaller time stamps are older processes, while larger timestamps represent younger processes. Promotional picture Symmetry Breaking is a rock band from Northern New Jersey, in the United States. ...

Wait/Die Wound/Wait
O needs a resource held by Y O waits Y dies
Y needs a resource held by O Y dies Y waits


It is important to note that a process may be in unsafe state but would not result in a deadlock. The notion of safe/unsafe state only refers to the ability of the system to enter a deadlock state or not. For example, if a process requests A which would result in an unsafe state, but releases B which would prevent circular wait, then the state is unsafe but the system is not in deadlock


Prevention

Deadlocks can be prevented by ensuring that at least one of the following four conditions occur:

  • Removing the mutual exclusion condition means that no process may have exclusive access to a resource. This proves impossible for resources that cannot be spooled, and even with spooled resources deadlock could still occur. Algorithms that avoid mutual exclusion are called non-blocking synchronization algorithms.
  • The "hold and wait" conditions may be removed by requiring processes to request all the resources they will need before starting up (or before embarking upon a particular set of operations); this advance knowledge is frequently difficult to satisfy and, in any case, is an inefficient use of resources. Another way is to require processes to release all their resources before requesting all the resources they will need. This too is often impractical. (Such algorithms, such as serializing tokens, are known as the all-or-none algorithms.)
  • A "no preemption" (lockout) condition may also be difficult or impossible to avoid as a process has to be able to have a resource for a certain amount of time, or the processing outcome may be inconsistent or thrashing may occur. However, inability to enforce preemption may interfere with a priority algorithm. (Note: Preemption of a "locked out" resource generally implies a rollback, and is to be avoided, since it is very costly in overhead.) Algorithms that allow preemption include lock-free and wait-free algorithms and optimistic concurrency control.
  • The circular wait condition: Algorithms that avoid circular waits include "disable interrupts during critical sections" , and "use a hierarchy to determine a partial ordering of resources" (where no obvious hierarchy exists, even the memory address of resources has been used to determine ordering) and Dijkstra's solution.

Mutual exclusion (often abbreviated to mutex) algorithms are used in concurrent programming to avoid the simultaneous use of un-shareable resources by pieces of computer code called critical sections. ... In computer science, spooling refers to process of communicating data to another program by placing it in a temporary working area, where the other program can access it at some later point in time. ... In computer science, non-blocking synchronization ensures that threads competing for a shared resource do not have their execution indefinitely postponed by mutual exclusion. ... Serializing tokens are a new concept in concurrency control arising from the ongoing development of DragonFly BSD. According to Matt Dillon, they are most akin to SPLs, except a token works across multiple CPUs while SPLs only work within a single CPUs domain. ... Pre-emption as used with respect to operating systems means the ability of the operating system to preempt or stop a currently scheduled task in favour of a higher priority task. ... In computer science, thrash is the poor performance of a virtual memory (or paging) system, when the same pages are being loaded repeatedly due to a lack of main memory. ... In contrast to algorithms that protect access to shared data with locks, lock-free and wait-free algorithms are specially designed to allow multiple threads to read and write shared data concurrently without corrupting it. ... In computer science, in the field of databases, optimistic concurrency control, (OCC) is a concurrency control method used in relational databases without using locking. ... In computer science circular wait is one of the four conditions necessary for deadlock to occur. ... In mathematics, a partially ordered set (or poset for short) is a set equipped with a special binary relation which formalizes the intuitive concept of an ordering. ... In computer science, the dining philosophers problem is an illustrative example of a common computing problem in concurrency. ...

Detection

Often neither deadlock avoidance nor deadlock prevention may be used. Instead deadlock detection and process restart are used by employing an algorithm that tracks resource allocation and process states, and rolls back and restarts one or more of the processes in order to remove the deadlock. Detecting a deadlock that has already occurred is easily possible since the resources that each process has locked and/or currently requested are known to the resource scheduler or OS.


Detecting the possibility of a deadlock before it occurs is much more difficult and is, in fact, generally undecidable, because the halting problem can be rephrased as a deadlock scenario. However, in specific environments, using specific means of locking resources, deadlock detection may be decidable. In the general case, it is not possible to distinguish between algorithms that are merely waiting for a very unlikely set of circumstances to occur and algorithms that will never finish because of deadlock. Undecidable has more than one meaning: In mathematical logic: A decision problem is undecidable if there is no known algorithm that decides it. ... In computability theory the halting problem is a decision problem which can be stated as follows: Given a description of a program and a finite input, decide whether the program finishes running or will run forever, given that input. ...


Distributed deadlock

Distributed deadlocks can occur in distributed systems when distributed transactions or concurrency control is being used. Distributed deadlocks can be detected either by constructing a global wait-for graph from local wait-for graphs at a deadlock detector or by a distributed algorithm like edge chasing. This article or section should include material from Distributed programming This article or section should include material from Distributed system Distributed computing is the process of aggregating the power of several computing entities to collaboratively run a single computational task in a transparent and coherent way, so that they appear... A distributed transaction is an operations bundle, in which two or more network hosts are involved. ... In computer science -- more specifically, in the field of databases -- concurrency control is a method used to ensure that database transactions are executed in a safe manner (i. ... An algorithm that executes on more then 1 machine, processor, ... Actually, there will be separate, different code running on each machine, but all of these pieces of code communicate with each other. ... Edge-chasing is an algorithm for deadlock detection in distributed systems. ...


Phantom deadlocks are deadlocks that are detected in a distributed system but don't actually exist - they have either been already resolved or no longer exist due to transactions aborting.


Livelock

A livelock is similar to a deadlock, except that the states of the processes involved in the livelock constantly change with regard to one another, none progressing. [1] Livelock is a special case of resource starvation; the general definition only states that a specific process is not progressing. [2] In computer science, starvation is a multitasking-related problem, where a process is perpetually denied necessary resources. ...


As a real-world example, livelock occurs when two people meet in a narrow corridor, and each tries to be polite by moving aside to let the other pass, but they end up swaying from side to side without making any progress because they always both move the same way at the same time.


Livelock is a risk with some algorithms that detect and recover from deadlock. If more than one process takes action, the deadlock detection algorithm can repeatedly trigger. This can be avoided by ensuring that only one process (chosen randomly or by priority) takes action. [3]


See also

In computer science, the ostrich algorithm is a strategy of ignoring potential problems on the basis that they may be exceedingly rare - to stick your head in the sand and pretend that there is no problem. This assumes that it is more cost-effective to allow the problem to occur... The Bankers algorithm is a resource allocation and deadlock avoidance algorithm developed by Edsger Dijkstra that tests for safety by simulating the allocation of pre-determined maximum possible amounts of all resources, and then makes a safe-state check to test for possible deadlock conditions for all other pending... A computer bought the farm message is an error message displayed on GNU Hurd when one of the servers that provide kernel-like functions reaches a hopeless situation (after which it is usually terminated). ... A deadlock provision, or deadlock resolution clause, is a contractual clause or series of clauses in a shareholders agreement or other form of joint venture agreement which determines how disagreements on key issues are to be resolved in relation to the management of the enterprise. ... In computer science, the dining philosophers problem is an illustrative example of a common computing problem in concurrency. ... Gridlock is a term describing an inability to move on a transport network. ... Look up hang in Wiktionary, the free dictionary. ... An infinite loop is a sequence of instructions in a computer program which loops endlessly, either due to the loop having no terminating condition or having one that can never be met. ... Mamihlapinatapai (sometimes erroneously spelled mamihlapinatapei) is a word from the Yaghan (Yámana) language of Tierra del Fuego, listed in The Guinness Book of World Records as the most succinct word. It describes a look shared by two people with each wishing that the other will initiate something that both... A race condition or race hazard is a flaw in a system or process whereby the output of the process is unexpectedly and critically dependent on the sequence or timing of other events. ... In computer science, the sleeping barber problem is a classic inter-process communication and synchronization problem between multiple operating system processes. ... Stalemate is a situation in chess where the player whose turn it is to move has no legal moves but is not in check. ... In computer science, especially parallel computing, synchronization means the coordination of simultaneous threads or processes to complete a task in order to get correct runtime order and avoid unexpected race conditions. ... Spin is a tool for software model checking. ...

External links


  Results from FactBites:
 
Art Of Business Web Site Promotion (352 words)
Just sign up as a deadlock referral partner, it'll take you five minutes to do and cost you nothing.
given out over the years by deadlock disciples, or post a question of your own to get help from other webmasters like yourself.
This means you may act on the advice, print the info for your own reference and link to this site as much as you like, but you may not copy any part of the text itself on your Web site / newsletter / book / magazine or any other commercial media.
Deadlock - Wikipedia, the free encyclopedia (1467 words)
Deadlock is a common problem in multiprocessing where many processes share a specific type of mutually exclusive resource known as a software, or soft, lock.
Instead deadlock detection and process restart are used by employing an algorithm that tracks resource allocation and process states, and rollsback and restarts one or more of the processes in order to remove the deadlock.
Distributed deadlocks can be detected either by constructing a global wait-for graph from local wait-for graphs at a deadlock detector or by a distributed algorithm like edge chasing.
  More results at FactBites »

 
 

COMMENTARY     


Share your thoughts, questions and commentary here
Your name
Your comments

Want to know more?
Search encyclopedia, statistics and forums:

 


Press Releases |  Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms, 1022, m