Final

22C:116, Fall 1997

Douglas W. Jones
Please write your answers on the paper provided. Make sure your name is on the front page, in the same form as it appears in the official class list! Illegible and overly long answers are difficult to grade. Please leave margins around your answers!

NOTE: Most questions on this test can be answered in one short paragraph or less! Exceptions are noted explicitly.

This exam is worth 3/10 of the final grade (30 points; allocate 4 minutes per point).

  1. Background: Amoeba provides for reclamation of unreferencable objects with the AGE and TOUCH operations on objects. On page 598, Tannenbaum says that "... servers run a garbage collector periodically, removing objects that have not been used in n garbage collection cycles. The AGE call starts a new garbage collection cycle. The TOUCH call tells the server that the object touched is still in use. When objects are entered into the directory server, they are touched periodically, to keep the garbage collector at bay." This discussion is expanded on in the middle of page 626, on the Bullet file server's use of these services.

    Part A: Is this mechanism formally correct in the sense that it will never reclaim an object for which some running program still has a capability? If not, why not? (2.0 points)

    Part B: Is this mechanism leak free in the sense that all garbage will eventually be reclaimed? If not, why not?! (2.0 points)

  2. The UNIX file system maintains, in the I-node of every file, a count of the number of links (pointers) to that file from various directories. The file will be retained so long as this reference count field is greater than zero, and it will be deleted as soon as the reference count reaches zero. This rule guarantees formal correctness, but it does not guarantee that the UNIX file system is leak free.

    Recall that the UNIX command "ln x y" creates a new link named "y" for a preexisting file reached by the name "x", and that the UNIX command "rm x" deletes the link named "x". Recall also that each directory contains a link to itself, named "." and a link to its parent, named ".."; the "mkdir" and "rmdir" commands maintain these structures.

    Part A: Why, under UNIX, must "rm" and "ln" be restricted, so that "rm" may not be used to delete the link to a directory, and "ln" may not be used to create a link to a directory? (2.0 points)

    Part B: If UNIX used a mark-sweep garbage collector to reclaim unreachable files instead of the reference count algorithm outlined above, would your answer to part A be different? Why? (2.0 points)

  3. Access control lists and capability lists are two enforcement mechanisms for secure systems. Each of these is equally applicable to the control of message passing in a distributed system. If your primary concern is efficient implementation of deadlock detection algorithms, which enforcement mechanism would be preferable, and why? (2.0 points)

  4. Background: Consider a system that uses distributed atomic transactions. The basic services offered by servers to clients in this system are begin-transaction, read, write, ready-to-commit and commit. The read and write services implicitly attach read and read-write locks to the records inspected or changed, and all changes are committed with a two-phase commit. Transactions may be distributed across multiple servers!

    This question deals with deadlock detection in the context of this system. The applicable deadlock model is clearly a single resource model. A deadlock detection protocol in this system can be initiated when a process detects that it has been blocked for too long.

    Part A: Describe a deadlock detection protocol appropriate for this system. What messages are sent, when, by whom, in response to what, and to whom? How does the protocol terminate if there is a deadlock? How does it terminate if there isn't? (4.0 points)

    Part B: There are three practical candidates for the participants in your deadlock detection protocol. Messages could be addressed to:

    Recall that the notion of an agent was introduced in the discussion of some of the distributed mutual exclusion algorithms. In these algorithms, each process had an agent that represented that process, taking its part the mutual exclusion algorithm when the process was busy doing other things.

    In the context of your answer to A, would all communication be directly between the involved processes, or would some of the messages you described be addressed to the kernels or the agent associated with some process. Which messages are involved, would the be better addressed to a kernel or to an agent, and why? (3.0 points)

  5. Background: Consider a system where the virtual address space contains page objects and non-page objects, mixed freely. There is a software field in each entry in the page table that distinguishes the object type (page or some other object type), and the hardware access rights fields for non-page objects are always set to "no access permitted" so that the MMU will trap all references to such addresses that fall in such pages.

    Operations on all non-page objects are implemented by the kernel, and they are implemented by imposing new semantics on load and store instructions that address non-page objects. If the object is at address A in the virtual address space, load(A) is one operation, store(A) is another, load(A+1) is another, and so on.
    As an example of a non-page object, consider the data type "double ended queue" or dequeue. The following operations are allowed on a dequeue, all others are errors:

    Part A: Outline the structure of the fault handler, with an emphasis on how it distinguishes between page and non-page faults, and for non-page faults, how it determines object type, and how it emulates the load and store instructions to achieve selected operations on dequeues. (3.0 points)

    Part B: Consider the object type "capability list", added to this environment. All operations on capability lists must be encoded as load and store instructions, interpreted by mechanisms similar to those you outlined in part A. Propose a reasonable set of operations that would allow users to manipulate capability lists in a secure way. (This is related to problem 3 on the midterm!) (3.0 points)

    Part C: Every capability list is, potentially, an execution domain. Discuss appropriate primitive operations you could add to your answer to part B that would transfer control from the current domain to a new domain, with emphasis on solving the mutual suspicion problem. (3.0 points)

  6. What services would you expect from a minimal process manager? For each, give a brief description of what it does and of the object types it manipulates. (4.0 points)