Final Review Questions

22C:116, Spring 1997

Douglas W. Jones

These review questions are intended to spur study and will not appear literally on the final. The final will contain some questions that will be far easier to answer if you have worked through these review questions.

  1. Garbage Collection and related topics: Amoeba servers could delete objects only on command, but in practice, the ability to automatically reclaim garbage (unreferencablei) objects is useful.

    Part A: What mechanism does Amoeba's standard server interface provide for reclamation of garbage.

    Part B: Is this mechanism formally correct and leak free? Formal correctness requires that it never reclaim an object for which some running program still has a capability. To state that a resource management system is leak free means that all garbage will eventually be reclaimed. If not, why not?!

    Part C: Given what you know about Amoeba, Demos and Mach, on which of these could you imagine implementing a classical mark-sweep garbage collection algorithm.

  2. Capability-Based Addressing: Consider a hypothetical system based on a standard off-the-shelf CPU and a standard off-the-shelf memory management unit. Assume that the operating system for this machine uses a page table (memory map) to represent each virtual address space, with some mixture of hardware and software fields associated with each page. Such a page table can be viewed as a capability list, where each capability names one physical page and gives the access rights for that page. For the purpose of this problem, it does not matter whether an address space is single or multithreaded.

    How can the operating system allow capabilities for objects that are not pages to be placed in the capability list for an address space? To answer this question, consider you must divide the issue in two:

    Part A: How can your system prevent capabilities for non-page-objects from being mistaken for memory capabilities by the memory management unit?

    Part B: How can your system implement operations on non-page-objects

    Hint: It might help to have an example of a non-page-object, so consider allowing Demos style links -- capabilities for communication channels -- to to be mixed into the capability list, where the operations on links are, obviously, sending messages.

    Background: The motivation for this comes from systems like UNIX where each process has an ad-hoc collection of different resources. The address space holds code, stack, static and possibly shared data segments, and can be modeled as a capability list of page or segment capabilities. The open-file space consists of a short (16 or 32 entry) capability list for open files. Each process also has exactly three timers, user and group ID's and an assortment of other miscelaney. Each resource type is addressed in an unrelated way, and, as implementors of Java have found to their dismay, this nonuniformity makes garbage collection quite difficult. The proposal outlined above allows the application program to view all resources as memory resources!

  3. Deadlock Detection: Consider the problem of deadlock detection in a distributed system. No machine in the system has global information about processes states, but the kernel on each machine knows the states of each process running locally. Devise a deadlock detection protocol for each of the following interprocess communication models, or if this cannot be done, explain why:

    Part A: The default model: Processes send messages to other processes. The send primitive requires an explicit address for the recipient and does not block. The receive primitive blocks until any process sends a message, and returns the sender's process ID with the message.

    Part B: The non buffered model: Processes send messages to other processes. The sender blocks until and receiver is ready for the data, and the receiver blocks until a process is ready to send. As above, the sender explicitly names the receiver, and the receiver learns who sent a message only after receipt.

    Part C: The capability model: Processes send messages to other processes, with the exact same semantics as in part A, except that messages are addressed using a capability list. The kernel maintains a capability list on behalf of each process, listing the addresses to which that process may send messages. On receipt of a message, a return address capability for the sender is delivered to the recipient, to be used as needed.

    Part D: The access control list model: Processes send messages to other processes, with the exact same semantics as in part A, except that messages may only be received from the senders listed in the recipient's access control list.

    Note: This is a study question. Therefore, there is no answer to the question "how much detail should I give" or "do you want pseudocode or some other kind of documentation for the protocol."