Final Exam

22C:116, Fall 2001

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 very difficult to grade. Please leave margins around your answers!

This exam is open-book, open-notes, closed neighbor!

NOTE: Essentially all questions on this test can be answered in one short paragraph or less! There are no long essay questions here! Stop and think before writing at any length!

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

Background: The following documentation is reproduced from the study questions. Changes from or additions to the material in the study questions are given in italics.

The FinalOS operating system (invented for this exam) is based on a microkernel with the following services:

send( channelpub, buffer, length )
sends a message via the designated communication channel.

receive( channelpriv, buffer, length )
receives a message via the designated communication channel.

Messages are transmitted from the sender's buffer to the receiver's buffer. The number of bytes transmitted is the minimum of the two lengths specified. The remainder of the receiver's buffer beyond the data transferred will be set to zero.

Messages are delivered from sender to receiver when
channelpub = trapdoor( channelpriv )
Both channelpub and channelpriv are 64 bit integers, and trapdoor() is a specific trapdoor function. The identity of this function is published, so that any programmer may incorporate it into any program. Typically, a process will hold channelpriv as a private and tightly guarded value, and it will make channelpub available to processes it wishes to receive messages from.

The FinalOS operating system itself consists of a collection of servers that run on top of this kernel. The process manager server, for example, is specified as offering the following services:

create
Returns a handle for the process it creates. The new process is created with no code, data, or resources, and therefore the new process is started in the state stopped.

poke
Given a process handle, a starting address and a buffer of data, Stores that buffer starting at that address in the address space of the process. Note that the registers of a stopped process can be set by this service.

peek
Given a process handle, a starting address and a length, returns a buffer of data from the processes address space starting at the indicated location and continuing for the indicated length. Note that the registers of a stopped process can be inspected by this service.

start
Given a process handle, if that process is stopped, changes the state of the process to ready.

stop
Given a process handle, if that process is not stopped, changes the state of the process to stopped.

kill
Given a process handle, terminates that process and reclaims all memory resources of the process.

When a process raises an exception such as divide by zero or invalid memory address, the FinalOS kernel stops the process that raised the exception and then delivers an exception notice to a channel that has been designated as the exception handler channel for that process. The contains:

The complete FinalOS operating system includes lots of other servers, including a window manager, a directory manager, a file manager, disk drivers, etc. The FinalOS kernel handles all interrupts, but it does for each interrupt, all it does is deliver a message to a port associated with that interrupt. The meaningful activity associated with each interrupt is done by the processes that receive these messages.

  1. Background: All calls to FinalOS servers pass their first message using the following format:

    Part A: What problem posed by an inadequacy in the design of the FinalOS kernel is solved by starting each message with the message length in bytes? (2 points)

    Part B: If we reserve a different channelpub for each service provided by a server, we could eliminate the need for a field in the message used to identify the service requested. Why is this a bad idea in the context of the FinalOS kernel. (2 points)

    Part C: One approach to calling a FinalOS server is for the calling process to set aside a fixed channel (with associated public and private identifiers) to be used for all return messages from any server. An alternative is to allocate a new channel for one-time use prior to each call to a server; in this case, a a new channelpriv must be computed and a new channelpub must be derived from it prior to each call to a server. What problem does the second and more complex approach solve? (2 points)

    Part D: What problem does the handle or server-side authenticator solve when we are calling a service such as "create" that does not require the handle of a specific object as a parameter? (2 points)

  2. Background: Consider a multicomputer implementation of FinalOS. In this system, there is no change to the external specification of the system. A user process may still select any 64 bit integer to use as channelpriv on a call to receive(), regardless of where in the system that process currently resides, and the sender need not provide any location information with channelpub in order to guarantee message delivery.

    Part A: What should each kernel keep, in a local cache, in order to expedite message delivery? (2 points)

    Part B: Suggest an appropriate kernel action when there is a cache miss. (2 points)

    Part C: One approach to calling a FinalOS server is for the calling process to set aside a fixed channel (with associated public and private identifiers) to be used for all return messages from any server. An alternative is to allocate a new channel for one-time use prior to each call to a server; in this case, a a new channelpriv must be computed and a new channelpub must be derived from it prior to each call to a server. What problem does the second and more complex approach cause in the context of the cache scheme you outlined in parts A and B? (2 points)

    Part D: The FinalOS kernel may be implemented using synchronous message passing or asynchronous buffered message passing. Each of these poses problems for the kernel in a multicomputer implementation of FinalOS. Explain which approach is best, and justify your answer by explaining what problems are avoided by using this approach. (2 points)

  3. Background: Consider the problem of implementing the FinalOS process manager. Since the manager includes no primitives for describing the size of the memory segment associated with a process, we conclude that a poke operation to a location outside the previously defined memory segment must cause the memory segment to grow to include the indicated address.

    Part A: Explain the relative advantages and disadvantages of a paged memory management unit as a tool to use in implementing the FinalOS set or kernel and process management services. (2 points)

    Part B: If page-fault exceptions are just another kind of exception, handled by passing them to the designated exception handler, what minimal set of additional or process management services must there be in order to allow the exception handler to implement demand-paged virtual memory on behalf of a process? (focus on the bare minimum when answering this part, and assume the stupidest possible page-replacement policy!) (2 points)

    Part C: Assuming that we ask the exception handler to handle page faults, an intelligent page-replacement policy will require cooperation between the exception handler and lower-level parts of the system. Suppose you wanted to use a software implementation of the clock replacement algorithm -- this is about the best you can do without special hardware support from the memory management unit, what minimal set of additional or process management services must there be in addition to those you mentioned in part B. (2 points)

  4. Background: Consider a SCSI II disk I/O driver for FinalOS. On behalf of its clients, it supports the peek and poke services, allowing a client to treat the contents of a disk drive in exactly the same way that a client treats the memory address space of a process (this compatability allows many utilities to be used interchangably on processes or disks). The driver also accepts messages from the kernel indicating that a particular disk drive has requested an interrupt. The disk driver can support up to 15 SCSI disk drives, so users must provide a drive handle to specify what specific disk is to be read or written.

    Part A: There are two ways the disk driver could distinguish between messages from clients and messages from the kernel. First, it could use a different channelpriv for each purpose, and second, it could rely on the contents of the messages to distinguish between them. Explain why FinalOS requires one of these alternatives and forbids the other. (2 points)

    Part B: Assume that the disk driver supports multiple concurrently active independent clients, and assume that the driver is single-threaded. What data structures must be present inside the driver in order to support these specific needs. (Hint: Does the answer to this question depend in any great way on the fact that the driver is a FinalOS server and not just a bunch of classical functions and interrupt service routines?) (2 points)

    Part C: Explain the relationship between the client process, the FinalOS directory server, the FinalOS file server, and the FinalOS SCSI II disk server. (2 points)

    Part D: Could a user-level thread package be used with FinalOS in order to simplify the structure of the disk driver, for example, by allowing the disk driver to create a new thread for each active disk I/O request. Explain what features of the FinalOS specification allow for this or prevent this from being effective. (2 points)