-
Background:
Consider the universal graph meta-algorithm presented in
lecture 17. This is presented in non-recursive
form, using an auxiliary data structure, the set S. In contrast, the
first presentation of the marking algorithm given in
lecture 19 is recursive and uses no auxiliary
data structure.
A Problem:
Express the marking algorithm as a variation on the universal graph
meta-algorithm. Then, explain where the recursive version stores the
set S during its computation and explain what queueing discipline is
used (fifo, lifo) and whether the graph is traversed in breadth-first
or depth first order.
-
Background:
The example thread manager will halt with the message
"possible deadlock" under certain circumstances.
A Problem:
Give an example of a programming error that could lead to this
message even when a deadlock is not possible under the formal
definition of a deadlock. Also describe how a deadlock could
exist under the example thread manager and yet not be detected
by the code as it currently stands.
-
Background:
Imagine that this assignment said: "Next week, you will be required
to modify the example thread manager so it incorporates a general purpose
deadlock detection mechanism. In preparation for that assignment,
describe the algorithm you would use and describe how you would incorporate
this into the code."
A Problem:
Explain why this is an entirely unreasonable
assignment! (Hint: The problem is not a lack of time.)
-
Problems from the Text:
Problem 1 on page 578.
Problem 20 on page 580.