Final Exam, Fall 2002

Note: This is an open-book, open-notes exam. Please write your answers in the exam booklet supplied. Leave blank lines between your answers to different questions, and leave a margin down the side of each page. Please write your name in the form it appears on your university ID card; write your name in the blank provided on the front cover. This exam is worth 30 points and has 15 parts! Allocate about 8 minutes per part.

General Background: Several problems on this exam refer to ECOS, the Excessively Complex Operating System introduced in the study questions distributed for this exam and with the midterm. Here are the relevant parts of the ECOS spec from the final study questions:

The ECOS interprocess communication primitives are nonblocking, with asynchronous message transfer and signals delivered to sender and receiver when transmission is complete. The primitives are:

send(c,buf,len,sem)

receive(c,buf,len,sem)

These initiate communication via the channel c, using the buffer buf and transferring len bytes (eventually). Each time a byte or group of bytes is transferred, the semaphore sem may be signalled, incrementing its count by the number of bytes already transferred; if the count has been incremented by n, this always means that the first n bytes of the buffer have been transferred. Users may block on the semaphore to wait for the completion of the entire transfer or for the completion of some part of the transfer.

Channel identifiers are 128 bit integers, and the system imposes no constraint about how processes that wish to communicate should go about selecting the channel number they will use. Channels have semantics similar to a FIFO queue or Unix pipe; that is, the sender's and receiver's buffers need not be the same length. If a sender has a large buffer, multiple receivers with small buffers may read from it to complete the send operation, and if the receiver has a large buffer, it may accumulate multiple messages sent by senders with small buffers. Note that if there are two senders and two receivers on a channel, data from one sender will not mingle with data from the other sender; even if the transfers actually occur in parallel, the outcome will be as if one sender's data was transferred and then the data from the other sender was transferred.

Here are older parts of the ECOS spec from the midterm study questions:

The ECOS process manager supports a generalization on semaphores where both wait and signal take extra parameters. These are described as follows in the official documentation.

wait(s,n)

Wait until the count in the semaphore s is greater than n and then atomically decrement the count by n.

signal(s,n)

Atomically increment the count in the semaphore s by n.

The Exam

1. Background: We have discussed two general approaches to input/output on a networked multicomputer:
   • Remote I/O drivers translate requests for I/O to messages on the network, addressed to servers that perform the required I/O using the local services of a remote machine. In this case, I/O to a local device requires no client-server interaction; instead, this is done by conventional function calls (or system calls) to the interface functions of the local I/O driver.

   • Pure client-server systems require that all application level I/O be done by contacting a server using a general purpose client-server communication protocol. Some servers are local, while others are remote; the servers themselves will typically have privileged access to the I/O devices.

   It is important to remember that layers of middleware can hide the difference between these models. Assume no such layers are present!

   A Problem: Each of these models will lead to better performance under some set of assumptions about the costs of interprocess communication and calls to device driver interface functions. What assumptions would favor the use of remote I/O drivers? What assumptions would favor the use of a pure client-server model of I/O?

2. Background: The ECOS intrprocess communication mechanism will transfer a message from sender to receiver if the channel ID used with the send operation matches the channel ID used with the receive operation.

   The focus of this problem is on matching the sender with the receiver; once each knows of the other, the remainder of the implementation of the communication from send to receive is straightforward.

   A registry is a data structure in which a process registers its interest. Assume the ECOS kernel maintains a communications registry; entries in this give channel ID, buffer address, buffer size, and semaphore address, along with whether the registered buffer is for sending or receiving. This registry is designed for efficient searching by channel ID.

   Part A: On a uniprocessor, either send or receive will register, but not both. Under what circumstances do send or recive register, and under what circumstances do they not register?

   Part B: On a uniprocessor, either send will copy the data and send the completion signals or receive will copy the data and send the completion signals. What determines which primitive goes first? Hint: This is very closely related to part A.

   Part C: Suppose the sender's and receiver's buffers are not the same size. What happens at the end of the transfer. Specifically, what hapens to the registration record?

   Part D: When should the registration records of a process be removed from the registry? Hint: There is a normal case and an abnormal case you must consider.

   Part E: In a multicomputer, where each machine's kernel maintains a local registry, what events cause a broadcast from one machine to the others on the network and how does this lead to a priority relationship between local and remote communications? Hint: Not all communication requires a broadcast!

3. Background: A malicious programmer finds the channel ID used by a publically available server under ECOS, for example, the channel that the process manager listens to waiting for requests for process creation. The programmer launches a process that sends a one byte buffer of random data to this channel every second.

   Part A: What are the consequences of this attack? Does ECOS (as documented) allow any defense against this attack or recovery from it?

   Part B: Would your answer have been different if the ECOS send and receive primitives matched each send to exactly one receive, instead of having pipe-like byte serial FIFO semantics?

   Part C: In later Unix systems (POSIX), the mkfifo command creates a named pipe (a file of type FIFO) attached to the directory tree. Given your answer to problem 1, comment on the utility of named pipes as public gateways to servers.

4. Background: Your employer suggests that you use ECOS to build a server, using a server-side protection model, using one randomly selected channel ID per object. When the server finds a message waiting on one of these channels, it interprets that message as a request to perform an operaton on the corresponding object.

   A Problem The ECOS interprocess communication and synchronization primitives given with this exam do not permit this! What is the problem? (Alternatively, what essential mechanism is missing? You may find reference to analogous mechanisms of other systems useful in answering this.)

5. Background: Consider a logical client-server relationship where the client must pass a number of logically distinct arguments to the server, where both the sizes and numbers of some of the arguments vary from call to call. In addition, the server must return a number of results of various sizes that the server will determine only after getting the arguments from the client.

   Do not forget to think about multiple clients all attempting to use this server by sending messages to the channel used by the server to initiate contacts with its clients.

   The focus of this quesiton is on the RPC protocols that could be implemented on top of the ECOS message passing primitives.

   Part A: Describe the contents of the initial message from client to server, explaining the necessary fields.

   Part B: Why is it necessary to send the arguments in a separate message and using a different channel from the initial message you described in part A?

   Part C: What channel(s) should be used for the reply, and how many distinct receives are required to capture the reply?

6. Background: You have been asked to extend the ECOS kernel to support process migration. You look at Demos MP for inspiration, and note the need to add tools so the process management server can stop a process, copy it to a different machine, and start it again.

   Part A: The developers of Demos MP had to invent a complex and interesting mechanism to support process migration; this is not needed under ECOS. Identify the mechanism and explain what it is about ECOS that eliminates the need for this.

   Part B: An ECOS process registers to receive a buffer of data on some channel. Then, the process is frozen so it can be moved to a different machine. What problems does this cause, and why were there no similar problems in Demos MP?