Deadlock
Encyclopedia
A deadlock is a situation where in two or more competing actions are each waiting for the other to finish, and thus neither ever does. It is often seen in a paradox
like the "chicken or the egg". The concept of a Catch-22
is similar.
In computer science, Coffman deadlock refers to a specific condition when two or more 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). Deadlock is a common problem in multiprocessing
where many processes share a specific type of mutually exclusive resource known as a software lock
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 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. Neither request can be satisfied, so a deadlock occurs.
The telecommunications description of deadlock is weaker than Coffman deadlock because processes can wait for messages instead of resources. A deadlock can be the result of corrupted messages or signals rather than merely waiting for resources. For example, a dataflow element that has been directed to receive input on the wrong link will never proceed even though that link is not involved in a Coffman cycle.
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. (This particular type of deadlock could be prevented, by using an all-or-none resource allocation algorithm.)
Unfulfillment of any of these conditions is enough to preclude Coffman deadlock from ever occurring. However, since the conditions are not sufficient, their mere presence does not itself imply a deadlock.
deadlock is computer hardware dependent.
, 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.
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 timestamp at process creation time. Smaller time stamps are older processes, while larger timestamps represent younger processes.
It is important to note that a process may be in an unsafe state but would not result in a deadlock. The notion of safe/unsafe states 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.
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.
Deadlock detection techniques include, but is not limited to model checking
. This approach constructs a finite state-model on which it performs a progress analysis and finds all possible terminal sets in the model. These then each represent a deadlock.
s 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
.
In a commitment ordering
-based distributed environment (including the strong strict two-phase locking (SS2PL, or rigorous) special case) distributed deadlocks are resolved automatically by the atomic commit
ment protocol (e.g. two-phase commit (2PC)), and no global wait-for graph or other resolution mechanism is needed. Similar automatic global deadlock resolution occurs also in environments that employ 2PL
that is not SS2PL (and typically not CO; see Deadlocks in 2PL). However, 2PL that is not SS2PL is rarely utilized in practice.
Phantom deadlocks are deadlocks that are detected in a distributed system due to system internal delays, but no longer actually exist at the time of detection.
Before we look into threads using just-in-time prevention, let's look into the conditions which already exist for regular locking.
So the issue with the first one is it does no deadlock prevention at all. The second doesn't do distributed deadlock prevention. But the 2nd one is redefined to prevent a deadlock scenario the first one doesn't address. And the only other scenario I am aware of that may cause deadlocks is when two or more lockers lock on each other. So why not expand the definition above one more time?
Well, we can, if we use add a variable to the recursive lock condition which guarantees that at least one thread runs among all locks—distributed deadlock prevention. And just like having a super track in the train example, I use "super thread" in this locking example.
After a super-thread is finished, the condition changes back to using the logic from the recursive lock, and the exiting super-thread
If a deadlock scenario exists, set a new super-thread and follow that logic. Otherwise, resume regular locking.
Issues not addressed above
A lot of confusion revolves around the halting problem. But this logic in-no-way solves the halting problem. This is because we know and control the conditions in which locking occurs, giving us a specific solution (instead of the otherwise required general solution the halting problem requires). Still this locker prevents all deadlocked!
Well, it does when only considering locks using this logic. But if it is used with other locking mechanisms, a lock that is started never unlocks (e.g. exception thrown jumping out without unlocking, looping indefinitely within a lock, or coding error forgetting to call unlock), deadlocking is very much possible. And to increase our condition to include these would require solving the halting issue, since we would be dealing with conditions we know nothing about and are unable to change.
Another issue is that this doesn't address the temporary deadlocking issue (not really a deadlock, but a performance killer), where two or more threads lock on each other while another unrelated threads is running. These temporary deadlocks could have a thread running exclusively within them, increasing parallelism. But because of how the distributed deadlock detection works for all locks, and not subsets therein, the unrelated running thread must complete before performing the super-thread logic to remove the temporary deadlock.
I hope you see the temporary live-lock scenario in the above. If another unrelated running thread begins before the first unrelated thread exits, another duration of temporary deadlocking will occur. And if this happens continuously (extremely rare), the temporary deadlock can be extended until right before the program exits, when the other unrelated threads are guaranteed to finish (because of the guarantee that one thread will always run to completion).
Further expansion
This can be further expanded to involve additional logic to increase parallelism where temporary deadlocks might otherwise occur. But for each step of adding more logic, we add more overhead.
A couple of examples include: expanding distributed super-thread locking mechanism to consider each subset of existing locks; Wait-For-Graph (WFG) http://www.cse.scu.edu/~jholliday/dd_9_16.htm algorithms, which track all cycles that cause deadlocks (including temporary deadlocks); and heuristics algorithms which don't necessarily increase parallelism in 100% of the places that temporary deadlocks are possible, but instead compromise by solving them in enough places that performance/overhead vs parallelism is acceptable (e.g. for each processor available, work towards finding deadlock cycles less than the number of processors + 1 deep).
; the general definition only states that a specific process is not progressing.
A real-world example of 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 both repeatedly 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 be repeatedly triggered. This can be avoided by ensuring that only one process (chosen randomly or by priority) takes action.
Paradox
Similar to Circular reasoning, A paradox is a seemingly true statement or group of statements that lead to a contradiction or a situation which seems to defy logic or intuition...
like the "chicken or the egg". The concept of a Catch-22
Catch-22 (logic)
A Catch-22, coined by Joseph Heller in his novel Catch-22, is a logical paradox arising from a situation in which an individual needs something that can only be acquired with an action that will lead him to that very situation he is already in; therefore, the acquisition of this thing becomes...
is similar.
In computer science, Coffman deadlock refers to a specific condition when two or more processes are each waiting for the other to release a resource, or more than two processes are waiting for resources in a circular chain
Circular reference
A circular reference is a series of references where the last object references the first, resulting in a closed loop.-In language:A circular reference is not to be confused with the logical fallacy of a circular argument...
(see Necessary conditions). Deadlock is a common problem in multiprocessing
Multiprocessing
Multiprocessing is the use of two or more central processing units within a single computer system. The term also refers to the ability of a system to support more than one processor and/or the ability to allocate tasks between them...
where many processes share a specific type of mutually exclusive resource known as a software lock
Lock (computer science)
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. Locks are one way of enforcing concurrency control policies.-Types:...
or soft lock. Computers intended for the time-sharing
Time-sharing
Time-sharing is the sharing of a computing resource among many users by means of multiprogramming and multi-tasking. Its introduction in the 1960s, and emergence as the prominent model of computing in the 1970s, represents a major technological shift in the history of computing.By allowing a large...
and/or real-time
Real-time computing
In computer science, real-time computing , or reactive computing, is the study of hardware and software systems that are subject to a "real-time constraint"— e.g. operational deadlines from event to system response. Real-time programs must guarantee response within strict time constraints...
markets are often equipped with a hardware lock (or hard lock) which guarantees 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. Neither request can be satisfied, so a deadlock occurs.
The telecommunications description of deadlock is weaker than Coffman deadlock because processes can wait for messages instead of resources. A deadlock can be the result of corrupted messages or signals rather than merely waiting for resources. For example, a dataflow element that has been directed to receive input on the wrong link will never proceed even though that link is not involved in a Coffman cycle.
Examples
An example of a deadlock which may occur in databaseDatabase
A database is an organized collection of data for one or more purposes, usually in digital form. The data are typically organized to model relevant aspects of reality , in a way that supports processes requiring this information...
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. (This particular type of deadlock could be prevented, by using an all-or-none resource allocation algorithm.)
Necessary conditions
There are four necessary conditions for a Coffman deadlock to occur, known as the Coffman conditions from their first description in a 1971 article by Edward G. Coffman, Jr.:- Mutual Exclusion: a resource that cannot be used by more than one process at a time
- Hold and Wait: processes already holding resources may request new resources held by other processes
- No PreemptionPreemption (computing)In computing, preemption is the act of temporarily interrupting a task being carried out by a computer system, without requiring its cooperation, and with the intention of resuming the task at a later time. Such a change is known as a context switch...
: No resource can be forcibly removed from a process holding it, resources can be released only by the explicit action of the process. - Circular Wait: two or more processes form a circular chain where each process waits for a resource that the next process in the chain holds. When circular waiting is triggered by mutual exclusion operations it is sometimes called lock inversion.
Unfulfillment of any of these conditions is enough to preclude Coffman deadlock from ever occurring. However, since the conditions are not sufficient, their mere presence does not itself imply a deadlock.
deadlock is computer hardware dependent.
Prevention
- Removing the mutual exclusion condition means that no process may have exclusive access to a resource. This proves impossible for resources that cannot be spooledSpoolingIn computer science, spool refers to the process of placing data in a temporary working area for another program to process. The most common use is in writing files on a magnetic tape or disk and entering them in the work queue for another process. Spooling is useful because devices access data at...
, and even with spooled resources deadlock could still occur. Algorithms that avoid mutual exclusion are called non-blocking synchronizationNon-blocking synchronizationIn computer science, a non-blocking algorithm ensures that threads competing for a shared resource do not have their execution indefinitely postponed by mutual exclusion...
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 tokensSerializing tokensIn computer science, serializing tokens are a concept in concurrency control arising from the ongoing development of DragonFly BSD. According to Matthew Dillon, they are most akin to SPLs, except a token works across multiple CPUs while SPLs only work within a single CPU's domain.Serializing...
, are known as the all-or-none algorithms.) - A "no preemptionPreemption (computing)In computing, preemption is the act of temporarily interrupting a task being carried out by a computer system, without requiring its cooperation, and with the intention of resuming the task at a later time. Such a change is known as a context switch...
" (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 rollbackRollback (data management)In database technologies, a rollback is an operation which returns the database to some previous state. Rollbacks are important for database integrity, because they mean that the database can be restored to a clean copy even after erroneous operations are performed...
, 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 controlOptimistic concurrency controlIn the field of relational database management systems, optimistic concurrency control is a concurrency control method that assumes that multiple transactions can complete without affecting each other, and that therefore transactions can proceed without locking the data resources that they affect...
. - 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.
Avoidance
Deadlock can be avoided if certain information about processes are 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 requests that will lead to safe states. In order for the system to be able to determine 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 algorithmBanker's algorithm
The Banker's algorithm is a resource allocation & 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...
, 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.
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 timestamp at process creation time. Smaller time stamps are older processes, while larger timestamps represent younger processes.
| 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 an unsafe state but would not result in a deadlock. The notion of safe/unsafe states 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.
Detection
Often, neither 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
Undecidable
Undecidable may refer to:In mathematics and logic* Undecidable problem - a decision problem which no algorithm can decide* "Undecidable" is sometimes used as a synonym of "independent", where a formula in mathematical logic is independent of a logical theory if neither that formula nor its negation...
, because the halting problem
Halting problem
In computability theory, the halting problem can be stated as follows: Given a description of a computer program, decide whether the program finishes running or continues to run forever...
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.
Deadlock detection techniques include, but is not limited to model checking
Model checking
In computer science, model checking refers to the following problem:Given a model of a system, test automatically whether this model meets a given specification....
. This approach constructs a finite state-model on which it performs a progress analysis and finds all possible terminal sets in the model. These then each represent a deadlock.
Distributed deadlock
Distributed deadlocks can occur in distributed systems when distributed transactionDistributed transaction
A distributed transaction is an operations bundle, in which two or more network hosts are involved. Usually, hosts provide transactional resources, while the transaction manager is responsible for creating and managing a global transaction that encompasses all operations against such resources...
s or concurrency control
Concurrency control
In information technology and computer science, especially in the fields of computer programming , operating systems , multiprocessors, and databases, concurrency control ensures that correct results for concurrent operations are generated, while getting those results as quickly as possible.Computer...
is being used. Distributed deadlocks can be detected either by constructing a global wait-for graph
Wait-For Graph
A Wait-For Graph in computer science is a directed graph used for deadlock detection in operating systems and relational database systems.In Computer Science, a system that allows concurrent operation of multiple processes and locking of resources and which does not provide mechanisms to avoid or...
, from local wait-for graphs at a deadlock detector or by a distributed algorithm like edge chasing
Edge chasing
In computer science, edge-chasing is an algorithm for deadlock detection in distributed systems.Whenever a process A is blocked for some resource, a probe message is sent to all processes A may depend on. The probe message contains the process id of A along with the path that the message has...
.
In a commitment ordering
Commitment ordering
In concurrency control of databases, transaction processing , and related applications, Commitment ordering is a class of interoperable Serializability techniques, both centralized and distributed. It allows optimistic implementations...
-based distributed environment (including the strong strict two-phase locking (SS2PL, or rigorous) special case) distributed deadlocks are resolved automatically by the atomic commit
Atomic commit
An atomic commit is an operation in which a set of distinct changes is applied as a single operation. If the changes are applied then the atomic commit is said to have succeeded. If there is a failure before the atomic commit can be completed then all of the changes completed in the atomic commit...
ment protocol (e.g. two-phase commit (2PC)), and no global wait-for graph or other resolution mechanism is needed. Similar automatic global deadlock resolution occurs also in environments that employ 2PL
Two-phase locking
In databases and transaction processing two-phase locking, is a concurrency control method that guarantees serializability.It is also the name of the resulting set of database transaction schedules...
that is not SS2PL (and typically not CO; see Deadlocks in 2PL). However, 2PL that is not SS2PL is rarely utilized in practice.
Phantom deadlocks are deadlocks that are detected in a distributed system due to system internal delays, but no longer actually exist at the time of detection.
Distributed deadlock prevention
Let's consider the "when two trains approach each other at a crossing" example defined above. Just-in-time prevention works like having a person standing at the crossing (the crossing guard) with a switch that will let only one train onto "super tracks" which runs above and over the other waiting train(s).Before we look into threads using just-in-time prevention, let's look into the conditions which already exist for regular locking.
- For non-recursive locks, a lock may be entered only once (where a single thread entering twice without unlocking will cause a deadlock, or throw an exception to enforce circular wait prevention).
- For recursive locks, only one thread is allowed to pass through a lock. If any other threads enter the lock, they must wait until the initial thread that passed through completes n number of times it has entered.
So the issue with the first one is it does no deadlock prevention at all. The second doesn't do distributed deadlock prevention. But the 2nd one is redefined to prevent a deadlock scenario the first one doesn't address. And the only other scenario I am aware of that may cause deadlocks is when two or more lockers lock on each other. So why not expand the definition above one more time?
Well, we can, if we use add a variable to the recursive lock condition which guarantees that at least one thread runs among all locks—distributed deadlock prevention. And just like having a super track in the train example, I use "super thread" in this locking example.
- Recursively, only one thread is allowed to pass through a lock. If other threads enter the lock, they must wait until the initial thread that passed through completes n number of times. But if the number of threads that enter locking equal the number that are locked, assign one thread as the super-thread, and only allow it to run (tracking the number of times it enters/exits locking) until it completes.
After a super-thread is finished, the condition changes back to using the logic from the recursive lock, and the exiting super-thread
- sets itself as not being a super-thread
- notifies the locker that other locked, waiting threads need to re-check this condition
If a deadlock scenario exists, set a new super-thread and follow that logic. Otherwise, resume regular locking.
Issues not addressed above
A lot of confusion revolves around the halting problem. But this logic in-no-way solves the halting problem. This is because we know and control the conditions in which locking occurs, giving us a specific solution (instead of the otherwise required general solution the halting problem requires). Still this locker prevents all deadlocked!
Well, it does when only considering locks using this logic. But if it is used with other locking mechanisms, a lock that is started never unlocks (e.g. exception thrown jumping out without unlocking, looping indefinitely within a lock, or coding error forgetting to call unlock), deadlocking is very much possible. And to increase our condition to include these would require solving the halting issue, since we would be dealing with conditions we know nothing about and are unable to change.
Another issue is that this doesn't address the temporary deadlocking issue (not really a deadlock, but a performance killer), where two or more threads lock on each other while another unrelated threads is running. These temporary deadlocks could have a thread running exclusively within them, increasing parallelism. But because of how the distributed deadlock detection works for all locks, and not subsets therein, the unrelated running thread must complete before performing the super-thread logic to remove the temporary deadlock.
I hope you see the temporary live-lock scenario in the above. If another unrelated running thread begins before the first unrelated thread exits, another duration of temporary deadlocking will occur. And if this happens continuously (extremely rare), the temporary deadlock can be extended until right before the program exits, when the other unrelated threads are guaranteed to finish (because of the guarantee that one thread will always run to completion).
Further expansion
This can be further expanded to involve additional logic to increase parallelism where temporary deadlocks might otherwise occur. But for each step of adding more logic, we add more overhead.
A couple of examples include: expanding distributed super-thread locking mechanism to consider each subset of existing locks; Wait-For-Graph (WFG) http://www.cse.scu.edu/~jholliday/dd_9_16.htm algorithms, which track all cycles that cause deadlocks (including temporary deadlocks); and heuristics algorithms which don't necessarily increase parallelism in 100% of the places that temporary deadlocks are possible, but instead compromise by solving them in enough places that performance/overhead vs parallelism is acceptable (e.g. for each processor available, work towards finding deadlock cycles less than the number of processors + 1 deep).
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. Livelock is a special case of resource starvationResource starvation
In computer science, starvation is a multitasking-related problem, where a process is perpetually denied necessary resources. Without those resources, the program can never finish its task....
; the general definition only states that a specific process is not progressing.
A real-world example of 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 both repeatedly 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 be repeatedly triggered. This can be avoided by ensuring that only one process (chosen randomly or by priority) takes action.
See also
- Banker's algorithmBanker's algorithmThe Banker's algorithm is a resource allocation & 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...
- Catch 22Catch-22 (logic)A Catch-22, coined by Joseph Heller in his novel Catch-22, is a logical paradox arising from a situation in which an individual needs something that can only be acquired with an action that will lead him to that very situation he is already in; therefore, the acquisition of this thing becomes...
- Deadlock provisionDeadlock provisionA 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.Deadlock...
- Dining philosophers problemDining philosophers problemIn computer science, the dining philosophers problem is an example problem often used in concurrent algorithm design to illustrate synchronization issues and techniques for resolving them....
- File lockingFile lockingFile locking is a mechanism that restricts access to a computer file by allowing only one user or process access at any specific time. Systems implement locking to prevent the classic interceding update scenario ....
- Gridlock (in vehicular traffic)GridlockThe term gridlock is defined as "A state of severe road congestion arising when continuous queues of vehicles block an entire network of intersecting streets, bringing traffic in all directions to a complete standstill; a traffic jam of this kind." The term originates from a situation possible in...
- HangHang (computing)In computing, a hang or freeze occurs when either a single computer program, or the whole system ceases to respond to inputs. In the most commonly encountered scenario, a workstation with a graphical user interface, all windows belonging to the frozen program become static, and though the mouse...
- ImpasseImpasseA bargaining impasse occurs when the two sides negotiating an agreement are unable to reach an agreement and become deadlocked. An impasse is almost invariably mutually harmful, either as a result of direct action which may be taken such as a strike in employment negotiation or sanctions/military...
- Infinite loopInfinite loopAn infinite loop is a sequence of instructions in a computer program which loops endlessly, either due to the loop having no terminating condition, having one that can never be met, or one that causes the loop to start over...
- LinearizabilityLinearizabilityIn concurrent programming, an operation is atomic, linearizable, indivisible or uninterruptible if it appears to the rest of the system to occur instantaneously. Atomicity is a guarantee of isolation from concurrent processes...
- Model checker can be used to formally verify that a system will never enter a deadlock.
- Ostrich algorithmOstrich algorithmIn 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"...
- Priority inversionPriority inversionIn computer science, priority inversion is a problematic scenario in scheduling when a higher priority task is indirectly preempted by a lower priority task effectively "inverting" the relative priorities of the two tasks....
- Race conditionRace conditionA race condition or race hazard is a flaw in an electronic system or process whereby the output or result of the process is unexpectedly and critically dependent on the sequence or timing of other events...
- Sleeping barber problemSleeping barber problemIn computer science, the sleeping barber problem is a classic inter-process communication and synchronization problem between multiple operating system processes...
- StalemateStalemateStalemate is a situation in chess where the player whose turn it is to move is not in check but has no legal moves. A stalemate ends the game in a draw. Stalemate is covered in the rules of chess....
- Readers-writer lockReaders-writer lockIn computer science, a readers-writer or shared-exclusive lock In computer science, a readers-writer or shared-exclusive lock In computer science, a readers-writer or shared-exclusive lock (also known as the multiple readers / single-writer lock or the multi-reader lock,...
- SynchronizationSynchronization (computer science)In computer science, synchronization refers to one of two distinct but related concepts: synchronization of processes, and synchronization of data. Process synchronization refers to the idea that multiple processes are to join up or handshake at a certain point, so as to reach an agreement or...
External links
- "Advanced Synchronization in Java Threads" by Scott Oaks and Henry Wong
- Deadlock Detection Agents
- DeadLock at the Portland Pattern Repository
- Etymology of "Deadlock"
- ARCS - A Web Service approach to alleviating deadlock
- Non-Hard Locking Read-Write Locker