Information Technology Reference
In-Depth Information
Deadlock
Unsafe
Safe
Figure6.8: A process can be in asafe,unsafe, ordeadlockedstate. The
dashed line illustrates a sequence of states visited by a thread|some are safe,
some are unsafe, and the final state is a deadlock.
versions of the algorithm can be useful and because it sheds light on some un-
derlying principles for understanding deadlocks such as the distinction between
safe and unsafe states and how the occurrence of deadlocks often depends on a
system's workload and sequence of operations.
Dijkstra dened the Banker's Algorithm as an approach that improves upon
the atomically acquire all resources approach. A thread still states its maximum
resource requirements when it begins a task, but it then acquires and releases
those resources incrementally as the task runs. The runtime system delays
granting some requests in a way that ensures the system never deadlocks.
The key idea behind the algorithm is that just because a system is capable
of deadlock doesn't mean that it must always deadlock: for some interleavings
of requests it will deadlock, but for others it won't. By delaying when some
resource requests are processed, a system can avoid interleavings that could
lead to deadlock.
A deadlock-prone system can be in one of three states: a safe state, an unsafe
state, and a deadlocked state (see Figure 6.8.)
In a safe state, for any possible sequence of resource requests, there ex-
Denition: safe state
ists at least one safe sequence of processing the requests that eventually
succeeds in granting all pending and future requests.
In an unsafe state, there exists at least one sequence of pending and future
Denition: unsafe state
resource requests that leads to deadlock no mater what processing order
is tried.
