Deadlock
A deadlock is
a situation in which two or more competing actions are each waiting for the
other to finish, and thus neither ever does.
In an operating system, a deadlock is a situation which occurs when a process or thread enters a waiting state because a resource requested is being held by another waiting process, which in
turn is waiting for another resource. If a process is unable to change its
state indefinitely because the resources requested by it are being used by
another waiting process, then the system is said to be in a deadlock.
Both processes need resources to continue
executing. P1 requires additional resource R1 and is in possession of resource
R2, P2 requires additional resource R2 and is in possession of R1; neither
process can continue.
Necessary condition
A deadlockers situation can arise
if all of the following conditions hold simultaneously in a system:
1. Mutual
Exclusion: At
least one resource must be held in a non-sharable mode. Only
one process can use the resource at any given instant of time.
2. Hold and Wait or Resource
Holding: A process is currently holding at least one resource and
requesting additional resources which are being held by other processes.
3. No Preemption: The operating system must
not de-allocate resources once they have been allocated; they must be released
by the holding process voluntarily.
4. Circular Wait: A process must be waiting
for a resource which is being held by another process, which in turn is waiting
for the first process to release the resource. In general, there is a set of
waiting processes, P = {P1, P2, ..., PN}, such
that P1 is waiting for a resource held by P2, P2 is
waiting for a resource held by P3 and so on until PN is
waiting for a resource held by P1.
These four conditions are known
as the Coffman conditions from their first description in a
1971 article by Edward G. Coffman, Jr. Unfulfillment
of any of these conditions is enough to preclude a deadlock from occurring.
Deadlock
can only occur in systems where all 4 conditions hold true.
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 request 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).
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
requests 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.
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.
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.
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.
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.
Phantom deadlocks are deadlocks that are detected in a
distributed system.
No comments:
Post a Comment