Assignment 8, due Oct 25

Part of the homework for 22C:116, fall 2002
by Douglas W. Jones
THE UNIVERSITY OF IOWA Department of Computer Science

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.