Final Exam Study Questions

22C:116, Fall 2001

Douglas W. Jones

  1. Background: Consider an operating system based on a very small microkernel. The fundamental kernel operations are:

    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.

    Messages are delivered from sender to receiver when
    channelpub = trapdoor( channelpriv )
    Both channelpub and channelpriv are large 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.

    An issue to consider: On a uniprocessor, how can the kernel efficiently relate sender to receiver. For each solution you imagine, can it be generalized to a multiprocessor or to a multicomputer?

    An issue to consider: The kernel gives no error indication if the sender's message was longer than the receiver's buffer. What measures could you take, as a user of this kernel, to deal with this weakness. The measures you propose are likely to be in the form of protocols!

    An issue to consider: This set of primitives is not fully specified! The kernel could implement these using blocking synchronous message passing, or by buffered message passing. Speaking only as an implementor, what are the benefits and problems each of these poses? Speaking as a user, does it make a difference?

    An issue to consider: This set of primitives allows two different processes to use the same private channel identifier. If these processes are cooperating, this might allow multiple processes to implement the same server. If they are unrelated, this might cause serious problems! Suggest a protocol for selecting private channel identifiers that makes conflicts unlikely. Suggest a protocol that could be used to help a process detect that a message was intended for some other process that accidentally used the same identifier.

    An issue to consider: This set of primitives is at a very low level. Suggest an elementary client-server protocol for use under this kernel.

    An issue to consider: This set of primitives does not contain a way to await messages from one of several channels, nor does it include a way to check a channel to see if a message is pending. Is such a mechanism needed? What problem does such a mechanism solve? Could this problem be solved in some other way?

  2. Background: In addition to the kernel, a minimal operating system must include a set of servers that communicate with clients in order to perform the basic services of an operating system. One of these servers is the process manager.

    Obvious process management services are:

    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.

    An issue to consider: What is a process handle? Can the concept of a process handle be generalized to include access rights and can it be generalized in such a way that these rights are secure against tampering by the user of a process handle?

    An issue to consider: Given the kernel services previously outlined, which of these process management primitives can you call using the simple client-server protocol you worked out in response to the study questions above, and which pose new problems requiring a more complex protocol. What is the source of this complexity.

    An issue to consider: Given a convention that some area of the address space of each process is reserved for data that defines the process's standard environment, and given that you have a file handle and operations for reading data from a file, propose a protocol for starting a new process executing the code from some file in an environment determined by the creator of the process.

    An issue to consider: This process manager does not include any explicit synchronization mechanisms. Should they be added? Are they implicit in some other aspect of the system?

    An issue to consider: The process manager looks like a normal server process to the users of the system, but it must be tightly integrated with the kernel. One way to do this is to make the process manager process share the same address space as the kernel data structures. Another way to do this is to eliminate the process manager process and have the kernel interpret attempts to communicate with the process manager as a special class of kernel calls. What problems does each alternative pose? What is the advantage of each alternative?

  3. Background: What happens when a process raises an exception? Among the exceptions that are common are invalid memory addresses (bad pointers) and division by zero. The obvious default, for a process that has no exception handler, is to kill that process, but this is not interesting.

    One model for exception handling is to have the kernel stop the process when it raises an exception and then deliver an exception message to a channel that has been designated as the exception handler channel for that process. The notice might contain:

    An issue to consider: What changes to the process manager would you make to support this model of exception handling?

    An issue to consider: Think about writing an exception handler under this model that supports the UNIX model, where exceptions in a process cause a call to a function that runs as part of that process. This is a remarkably simple exercise.

    An issue to consider: What changes to the process manager would you need to make in order to allow the exception handler to handle page-fault exceptions, so that it is the exception handler and not the kernel that does demand-paged virtual memory for a process.

  4. Background: A useful operating system ought to include lots of other servers. A window manager, a directory manager, a file manager, disk drivers, etc. If we assume that the kernel intercepts all interrupts and responds to them by delivering messages to pre-designated ports,

    An issue to consider: How would you structure the servers for each of these?