Homework 7

22C:116, Fall 1995

Due Friday Oct. 6, 1995, in class

1. The problem: Solve the mutual suspicion problem in Pascal. Assume that there is a single abstraction to be protected from its users. For example, assume you have a stack, with operations push and pop, where the representation is to be hidden from the users and the users are to be protected from improper implementation.

   The hint: Solving this requires that the user code be placed in one procedure and that the data structures for the stack be placed in another procedure at the same nesting level as the first. Only by doing this are the two protected from each other. The problem, then, is to figure out how to make the push and pop routines for the stack accessible to the user code. The solution to this problem involves procedure parameters.

2. The problem: With reference to the CAP system described in the notes, describe how you would construct a stack abstract data type, with the fundamental operations create_stack, push and pop. As in programming language support of abstract data types, the representation of this type should be protected from users of the type.

3. The problem: Describe, in some detail, an algorithm for detecting a cycle in a graph.

4. The problem: Given a UNIX system, could you automatically detect deadlocks? What problems stand in the way of doing so?