Homework 9

22C:116, Fall 2001

Due Monday Nov 16, 2001, in class

Always, on every assignment, please write your name legibly as it appears on your University ID and on the class list!

1. Programming Pre-Assignment: You will be required to write an interprocess communication package for the next homework assignment. This package will be required to maintain, for each process, a set of mailboxes for incoming messages. Messages will be addressed to a particular mailbox of a particular process. Ideally, you will be able to implement this semantics as a layer on top of the software you implemented for the previous assignment.

   In implementing this assignment, you face several design choices. A critical choice has to do with how the list of incoming boxes for each process is arranged. There are two obvious alternatives:

   • The list of boxes for a process is an explicit data structure in the address space of that process. When a process wants a message addressed to a particular box, it checks to see if such a message has already arrived and if not, waits for messages until the desired message arrives. All undesired messages received while in this phase are dispersed to their appropriate local lists.

   • The channel naming scheme you used for the previous assignment is generalized to use more complex channel names, so that no new data structures are created in the process address space, and instead, the new channels are accomodated in the name-space used for channel names.

   Prior to writing any code, this assignment asks you to discuss the tradeoffs between these two alternatives:

   Part a: The underlying channels you are to use, as implemented in the previous assignment, have a semisynchronous characteristic -- each interprocess channel can buffer exactly one message. The two approaches to using the code from the previous assignment to implement the new required semantics will produce interprocess channels with distinctly different semantics. Identify the differences!

   Part b: Suppose you wanted a multiwait primitive -- that is, the ability to await input from any one of a specific list of incoming message channels. Discuss how you would do this under each of the above implementation alternatives.

2. Background: The original DEMOS interprocess communication mechanism used unbuffered synchronous message transmission. That is, the sender was blocked until the receiver was ready to accept a message from a particular incoming message box, and the receiver was blocked until some sender tried to send to a particular incoming message box. This did not eliminate the need for queues in the interprocess communication mechanis, but these queues were no longer queues of data.

   A Problem: What goes in the interprocess communication queues?

3. Background: A name server offers two services to the outside world, register(name,value) stores the name in the server and associates a value with it. Lookup(name) returns the value associated with some name. Obviously, these can be implemented using a classical symbol table data structure, so you can take for granted that you have such a structure.

   A Problem: Outline the code of a name server process in a system that uses blocking synchronous interprocess message passing, as in the Demos system.