Final Study Questions, Fall 2002

Part of the homework for 22C:116, fall 2002
by Douglas W. Jones
THE UNIVERSITY OF IOWA Department of Computer Science

Warning: These questions are not intended to exhaustively cover everything that might be on the final. Their only purpose is to focus some of your study time on specific problems in order to allow some of the exam questions to be more focused than would be possible on a purely in-class exam. This allows the exam to have some of the character of a take-home exam.

  1. Background: After your success working on the memory management components of ECOS, the Excessively Complex Operating System, your boss asks you to work on a new model of interprocess communication for ECOS. In the spirit of the ECOS I/O primitives, the new 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.

    A problem: How would you implement the ECOS communications model on a uniprocessor, a shared memory multiprocessor and on a multicomputer. In each context, think about getting the semantics right first, and then worry about the optimizations you could use to gain efficiency.

    A problem: Consider implementing the ECOS API on top of a conventional blocking message passing mechanism. Consider launching a thread to complete each send and another thread to do each receive. Outline the code for these threads.

    A problem: Outline the code you'd use to implement an RPC under ECOS.

    A problem: Assume you've been asked to write a widget server for ECOS. Outline the different channels your server would use, and describe how your server's clients would (or could, or should) find the channels they needed.

    A problem: How do you select channel numbers for communication between processes that are concerned with security? How can processes defend themselves against the possibility of interference from outsiders on what they hoped was a private channel? Think of this in the context of the widget server mentioned above. Is there a server-side solution?

    A problem: Note that the ECOS interprocess communications primitives are very similar to the ECOS primitives for input/output described in the midterm study questions. The only real difference is that I/O is directed via device descriptors instead of channel identifiers. How can this be exploited in order to simplify the implementation.