Information Technology Reference
In-Depth Information
a variation of the
isSafe()
method shown in Figure 6.11 for the Banker's
Algorithm. We leave the state variables and high level interface (Figures 6.9
and 6.10) as an exercise for the reader.
One might hope that we could avoid deadlock by asking \Will satisfying the
current request put us in a deadlocked state?" and then blocking requests that
do, but as this algorithm highlights, deadlock is determined not just by what
requests we grant but also by what requests are waiting. The request that puts
us into a deadlocked state (\circular wait") will be a request that waits, not a
request that is granted.
Taking a step back, it is the the lack of knowledge about possible future
requests prevents us from using this algorithm to avoid deadlock. As Figure 6.8
illustrates, we can be in an unsafe state long before we reach a deadlock state,
and once we reach an unsafe state, there are request sequences that will force
us to deadlock.
For example, recall the ACB/BCA example on page 265. Even though we
are not yet deadlocked after thread 1 acquires A and thread 2 acquires B, once
these two actions occur, deadlock is inevitable given the requests that will arrive
in the future.
Exercises
1. Figure 6.2 shows an execution that executes some requests in parallel,
and it shows an equivalent sequential execution|request 1 then request 2
then request 3|. There are two other sequential executions that are also
equivalent to the parallel execution shown in the figure. What are these
other equivalent sequential executions?
2. Generalize the rules for two phase locking to include both mutual exclusion
locks and readers-writers locks. What can be done in the expanding phase?
What can be done in the contracting phase?
3. Consider the variation of the Dining Philosophers problem shown in Fig-
ure 6.7 where all unused chopsticks are placed in the center of the table
and any philosopher can eat with any two chopsticks.
One way to prevent deadlock in this system is to provide sucient re-
sources. For a system with n philosophers, what is the minimum number
of chopsticks that ensures deadlock freedom? Why?
4. If the queues between stages are finite, Is it possible for a staged architec-
ture to deadlock even if each individual stage is internally deadlock free?
If so, give an example. If not, prove it.
