Information Technology Reference
In-Depth Information
not modular, it is vital to have an overall structure that let's you reason about
how the pieces will interact. Often, it is helpful to strive for a strict layering or
hierarchy of modules. It is easier to make such programs deadlock free, and it
is easier to test them as well.
Performance is important, but it is usually easier to start with a clean,
simple, and correct design, measure it to identify its bottlenecks, and then
optimize the bottlenecks than to start with a complex design and try to tune
its performance (let alone fix its bugs.)
Problems
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.
5. Suppose you build a system using a staged architecture with some fixed
number of threads operating on stage. Assuming each stage is individually
deadlock free, describe two ways to guarantee that your system as a whole
can not deadlock. Each of the ways should eliminate a different one of the
4 necessary conditions for deadlock.
