Final Solutions and Comments

22C:116, Fall 1999

Douglas W. Jones

Distribution


Mean   = 14.6         X             X
Median = 14.0         X X   X       X
                    X X X X X X   X X X X
  ______X___X___X___X_X_X_X_X_X___X_X_X_X_X_X_____
   2 . 4 . 6 . 8 . 10. 12. 14. 16. 18. 20. 22. 24
A grade scale   C C + - B B B B + - A A A A +

Solutions

  1. Part A: In the above client-side remote method invocation stub that was given, why did we need to create a new value of trans-id for each invocation?
    The server uses the return capability as a unique transaction identifier, so we must manufacture a unique new capability for each client-server transaction. The server recognizes reuse of a return capability as an indication that a reply was lost, in which case it resends the reply. The client only accepts replies issued using the return capability for the current transaction and ignores all others. This question was fairly easy, being based, in effect, on a solution to the second study question that was distributed prior to the final.

    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?

    We do not need the full generality of a table because, during a transaction, we are only looking for one specific message, the reply to that transaction. The random trans-key plus the sequentially computed trans-ID make it infeasible to forge this reply message.

    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 can safely discard any message in this system so long as we guarantee that, eventually, our process will be in a state where it will accept that message. This is because the system itself offers no delivery guarantee, and therefore, all applications will have to be fault tolerant. Thus, instead of saving messages in separate incoming message queues, sorted by the capability that was used, we simply rely on the sender to retransmit those messages.

    Part D: Suppose we added the queueing mechanism that we showed, in part C, to be unnecessary. What benefit would we gain?

    Queueing incoming messages, sorted by the capability that was used to send them, will generally result in far better performance than discarding them and requiring the sender to retransmit. The network load is reduced by the elimination of redundant transmissions, the load on application processes is reduced by eliminating redundant calls to receive, and the application will be able to process queued messages promptly instead of having to wait for them to be resent.

  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?
    To receive a reply from the registration server, a process must already have a valid destination ID. This ID need not be registered yet, but the first thing the process must do when it starts is register this ID so it can receive replies from RPCs it issues. Once the process has registered the first destination ID, it may create and register others with no problems.

  3. Part A: What is the minimal set of servers that must be loaded by the bootstrap loader?
    The process manager, so the root process can start other processes.

    The registration server, to allow interprocess communication.

    A disk server, so the root process can read the startup script.

    It may be that process management requires other servers, such as a segment manager. Since no details were given, a specific listing of these secondary servers cannot be given, but if any exist, they must, of course, be included.

    Many students engaged in minor excess, throwing in a full file system. This is not strictly necessary, as the startup script need not be a normal file.

    Many students engaged in serious overkill, throwing in drivers for all the devices on the system and for many devices that were never mentioned. Among these, a display driver can barely be justified -- to display an on-screen log of startup actions.

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

    A file server and a directory server, so we can make use of the disk.

    A keyboard server, so we can handle input

    A display server, so we can do rudimentary output

    A window manager, so we can make good use of the high-res display.

    No mention was made in the problem statement of a real-time clock, and network connections were explicitly excluded.

    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.

    My reply capability -- see question 2
    The registration server's public entrypoint
    The process manager's public entrypoint
    The root directory of the file system
    Optionally, the current directory, if that concept is useful
    Standard input -- typically the keyboard or a window
    Standard output -- typically the display, a file, or a window

    The directory manager can, in theory, give access to all the other capbilities a process might want, assuming those are entered in some directory accessible from the root. Nonetheless, we might want to put capabilties for the public entry points of the window manager and the file manager in the standard environment.

  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?
    No, nothing precludes the use of Amoeba-style authentication. The Amoeba capability structure may be used by any application that wishes to use it. The obvious thing to do is to steal, perhaps, 8 bits from the index field and use these for access rights. Nothing prevents bits being borrowed from the key field for this purpose, but doing so directly reduces security.

    This question was a variation on the third study question.

  5. Part A: Give top-level pseudocode for the kernel's cache fault handler.
    	cache fault:
    	  given dst-ID, the destination ID that was requested
    	  if there is a vacant cache slot,
    	    slot = vacant cache slot
    	  else
    	    slot = cache slot selected by replacement policy
    	  endif
    	  invoke( registration-server, lookup-destination-ID, dst-id, res )
    	  get machine-ID and process-ID from res
    	  put [dst-ID, machine-ID, process-ID] in slot
    

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

    No, all message addressing is done with destination ID information, so processes cannot make any dangerous use of machine or process ID information.

    Part C: Suggest a change to the specifications for the kernel that would allow the registration server to find out the process ID and machine ID of a process registering a destination ID.

    If the kernel on the machine that sends a message attaches the sender's process and machine ID to the message, the receive service can have parameters added to return this information to any recipient. The registration server needs this information, others may simply discard it.

    This question was essentially the same as the first study question.

    Many suggested that the sending process should be required to provide this information. That is dangerous, because then a sender could provide incorrect information, registering an ID on behalf of another process.

    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.

    We need at least 2 processes, each able to act as registration server. A low performance but simple solution would have one acting as the registration server at each instant, while the other(s) acted as backups. Each registration service would be implemented as an atomic transaction, so that all servers are updated identically by each. The backups periodically check to see that the primary server is alive; if it fails, the backups hold an election among themselves, and the winner registers itself as the new registration server.

    More complex solutions would divide the load between multiple active registration servers so that the system scales better.

  6. The Question: What operations must the owner capability for a process permit?
    The owner of a process must:

    Be able to insert one or more segments into the address space of that process, since a process with no segments cannot possibly execute any code or manipulate any variables!

    Be able to start the process, since it was created in a stopped state.

    Of course, if we can start a process, we ought to be able to stop it, and if we created it, we probably ought to be able to destroy it, but strictly speaking, these additional operations aren't required by anything that was said.

    A dismaying number of students listed segment manager operations such as create segment, load data in segment, etc. These are nice, but they aren't, strictly speaking, operations that the owner of a process performs on that process.

  7. Part A: Give a top-level outline of the structure of a disk driver.
    The disk driver would consist of a disk server process and a disk interrupt handler, communicating through a queue of disk I/O requests in a segment shared by both. The server and the handler must, of course, reside on the same machine.

    The disk server is entirely message driven, waiting for messages from clients and placing disk I/O requests in the queue.

    The disk interrupt handler is entirely interrupt driven. Each time it is activated, it may signal completion of a previous disk I/O request, or it may start the next, or both.

    Some disk cache functions are easily handled by the disk server. The queue management discipline, half embedded in the enqueue code and half in the dequeue code, does the disk scheduling.

    Part B: How should the interrupt handler signal the server when it completes one of the requested disk I/O transfers.

    Since the server is purely message driven, the handler should send a message to the server. The server can have a special destination ID known only to the handler, and the message should probably indicate which queue entry has been completed.

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

    	Transfer direction
    	Disk address
    	Return capability
    	Buffer
    
    Note that, unlike the example disk drivers mentioned in the first half of the semester, we don't need to use the buffer address, we can put the entire buffer in the queue. The server can receive messages directly into a queue entry, including the data to be written to disk, and it can send results directly from the queue entry immediately before freeing the space.

    This design then requires that the return capbility be included in the queue entry, simply because there is no other good place to put it.

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

    If the disk server's queue is full and it receives a request for more disk I/O, it must discard that request. As in problem 1, parts C and D, this solution exploits the fact that our system makes no delivery guarantees, and thus, requires all applications to tolerate occasional faults.

    A surprising number made an odd reading of this question, and assumed that the problem in question had to do with buffers that were too small to hold one quantum of disk I/O (sector, track, whatever the unit might be).