Final

22C:116, Fall 1999

NOTE: Essentially all questions on this test can be answered briefly. There are no long essay questions here!

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

Background: Several questions on this exam relate to the example distributed kernel distributed with the study questions. The following text is lifted verbatim from the study questions:

Consider an operating system similar to Demos and Amoeba. Like Demos, it supports unconstrained message passing between processes. Like Amoeba, it is based on server side authentication. Capabilities have the following form:

         _______________________________
	|  destination ID | index | key |
        |_________________|_______|_____|

The kernel uses destination ID to route messages to their recipients. The kernel makes no use of the index or key fields. Typically, servers will use the index field to identify an object, and will use the key field to validate the capability for the object.

Typically, user processes will validate capabilities by checking to see that table[index]=key, where the index and key are taken from the capability presented with a message, and where table is local to the process that is checking the validity. Note that no trapdoor function is involved here.

The destination ID is not a process id. The right of a process to receive messages addressed to a particular destination is controlled as follows: The kernel cooperates with a special server, the registration server. The registration server supports the following operations:

create destination ID

any process can do this at any time

Returns a new capability for a newly allocated destination ID. The index field is the new destination ID The key field is used to validate the right to accept messages addressed to that destination.

register destination ID

legal only if the key is the correct key for the destination.

The most recent process to register some destination ID will receive all messages addressed to that destination. The registration server distributes destination ID information to the kernels of all member computers.

The following message passing primitives are provided:

send( cap, buf, len )

uses the destination ID of cap to send a len-byte message from the buffer given to the most recent process that registered that destination ID. Message delivery is not guaranteed. Message loss may be caused by network problems, lack of buffer capacity, etc.

receive( &cap, buf, len, &reallen, time )

await any message addressed to the current process, and place it in buf, up to len bytes. Returns the number of bytes in reallen, and returns the capability for the sender in cap. Time gives the maximum time to wait before returning. This may be zero, in which case, this service returns immediately, giving a message only if one was already enqueued, and it may be infinity, giving the usual semantics for a blocking receive.

In addition to the previously distributed study questions, consider the following outline of a client-side remote method invocation stub for this system:

    global variables within client
       trans-id   -- an integer, initially zero
       return-ID  -- a destination ID registered for this process

    invoke( object-cap, method, params, result )
       trans-id = trans-id + 1
       trans-key = random
       return-cap = make-capability(
          destination-ID = return-ID
          index = trans-id
          key = trans-key
       )
       send-buf = [ method | return-cap | params ]
       repeat
          send( object-cap, send-buf, length[send-buf] )
          receive( &reply-cap, reply-buf, reply-buf-len, &reallen, delay )
       until all of the following are true
          not timeout
          reply-cap.destination-ID = return-ID
          reply-cap.index = trans-id
          reply-cap.key = trans-key
       result = reply-buf

1. Part A: In the above client-side remote method invocation stub, why do we need to create a new value of trans-id for each invocation. (1 point)

   Part B: In the above client-side stub, why is the random trans-key sufficient for reply capability validation without the need for the full generality of the table a server would use to validate requests? (2 points)

   Part C: Assume this client-side stub is used within one server to call on the services of a secondary server. Why is there no need to save and enqueue incoming messages that have some other destination-ID, or some other index than the expected values? (We devoted half a lecture to the subject of how to build such a system of queues, and each Demos mailbox represented such a queue!) (2 points)

   Part D: Suppose we added the queueing mechanism that we showed, in part C, to be unnecessary. What benefit would we gain? (Hint: The benefit would be great enough that we would be stupid to omit this mechanism.) (1 point)

2. A problem: Suppose we use the remote object invocation code outlined in the background section for invocation of the services of the registration server. What does this imply about the information a process must have, when it is created, in order to allow that process to create or register a new destination ID? (2 points)

3. Background: Immediately after a classical operating system like UNIX is loaded by the bootstrap loader, main memory is occupied by a single process, the root process of the sytem, plus the set of interrupt and trap handlers that make up the system kernel. The root process then proceeds to use kernel services to load and launch a shell (command interpreter) that reads a startup script that contains instructions for launching other system processes such as the background process, line printer daemon, network daemons, window managers etc. At the completion of the interpretation of this startup script, the system is up and running.

   For our example system, the bootstrap loader will also load a single root process, some interrupt and trap handlers, and a small set of servers. Most servers, however, will be launched by the root process as it reads and interprets the startup script.

   For this problem, assume that your system has a keyboard, a high resolution video display and a local boot disk, but that it is not attached to any network.

   Part A: What is the minimal set of servers that must be loaded by the bootstrap loader. For each server you list, give a sentence that justifies its inclusion in boot image. (2 points)

   Part B: List several of the more important servers that you would expect the root process to launch as it reads the startup script. (2 points)

   Part C: Taken together, the servers listed in parts A and B provide the foundation for the standard environment that user processes must be given by their creators at startup. Give a reasonable list of capabilities that should be in this environment. (Hint: Check your answer to question 2!) (2 points)

4. A Question: Is there anything in this description that would preclude the use of Amoeba-style access rights and authentication, using a trapdoor function? If so, clearly state the reason. If not, outline how the fields of the example capability would be subdivided to hold a rights field, and indicate how the modified fields would be checked for validity. (1 point)

5. Background: Consider a distributed version of the example system. The local kernel on each member machine has an addressing cache relating destination ID to machine ID and local process ID. There registration server is a single process somewhere in the network that maintains a global list of destination ID associations. In addition to the public services offered by the registration server, it also offers a "lookup destination ID" service to all local kernels that returns the network address information needed by a kernel to handle a local cache fault.

   Part A: Give top-level pseudocode for the kernel's cache fault handler. (2 points)

   Part B: Would allowing the general public to use the "lookup destination ID" service cause any security problems? (1 point)

   Part C: There is a serious shortcoming of the kernel defined in the study questions! The registration server cannot find out the process ID and machine ID of the process attempting to register a destination ID. Suggest a change to the specifications for the kernel that would fix this. For full credit, your fix must not compromize the security of the system. (2 points)

   Part D: A single registration server could lead to total system failure in the event of a single local failure. Outline the architecture of a fault tolerant registration server. (2 points)

6. Background: Nothing was said in the definition of this system about the memory model of each user process. Assume that we have some kind of segment manager server running on each machine, and that it creates and understands capabilities for segments; segments may be shared.

   When a user calls the "create process" service of the process manager, the process manager creates a process that is stopped and has no segments in its address space. It returns an owner capability for that process.

   The Question: What operations must the owner capability for a process permit? (2 points)

7. Background: Consider the problem of writing a disk I/O driver to run under the example architecture. The user interface to this driver consists of a server offering the services read-sector and write-sector, and assuming the remote method invocation code given with this exam is used to communicate with these services.

   Part A: Give a top-level outline of the structure of such a driver, clearly indicating which parts of the driver handle disk scheduling, which parts respond to what interrupts, where what queues are placed, and so on. (2 points)

   Part B: How should the interrupt handler signal the server when it completes one of the requested disk I/O transfers. You cannot answer this question without reference to the specifics of the example system! (1 point)

   Part C: Give details of the structure of each entry in the queue that is central to your solution to this question. (1 point)

   Part D: The disk server has a fixed finite buffer capacity. What are the consequences of this, as seen by users? (2 points)