Homework 11

22C:116, Fall 1997

Due Monday Dec. 1, 1997, in class

Background Consider the following variant on the naive message passing model:

send(m,p)

sends the message m to process p. If p is not ready to receive the message, the sender is blocked.

receive(m,p)

awaits a message, then places that message in m and places the process id of the sender in p. If a sender is not waiting, the receiver blocks until a sender is ready to send.

1. General questions about this model:

   Part A: How many low-level messages between sender and receiver are necessary in order to implement the synchronization requirements of this protocol? Assume that the actual message being sent occupies only a few bytes and that a process ID is comparably small.

   Part B: How many additional messages must you add to your answer above in order to assure reliable message delivery in the face of transmission errors.

   Part C: Describe (briefly) a failure scenerio that demonstrates that reliable delivery is not sufficient to guarantee fault tolerance in a set of applications.

2. Describe, in about as much detail as was given for the Demos MP system, how the steps involved in process migration for this system. Note, emphatically, that the answer will not be the same as the answer for Demos!

3. How would you implement a set of DEMOS-like message passing primitives on top of this system? That is, how would you go about adding a software layer that provides a nonblocking send primitive where messages are addressed a particular queue of a process, and where processes may block awaiting a message in a particular queue or set of queues. Please give pseudocode for the DEMOS-style send and receive primitives, and give brief descriptions of the data structures on which they rely.

   Note: You may rely on thread creation primitives, heap management primitives and other tools in solving this problem.

4. Background: Consider a system based on multiple geographically distributed servers, where files, indexed by globally unique but meaningless file numbers, may be stored on any server, and servers may move files around whenever needed. This problem does not rest on the above discussion of interprocess communication primitives!

   Assume that there is some kind of multicast channel is available so that a client may ask "has anyone got file x". Assume also that this is expensive and you intend to minimize its use.

   Part A: Propose a structure appropriate for UNIX style directories on this system. Assume that the directory server(s) use(s) file servers to store directories. Also! What would the open() service for this system return as the representation of a file descriptor.

   Part B: Give quick-and-dirty pseudocode in terms of your answers above for the user's read() operation that communicates with file servers. Emphasize how you account for the possible migration of a file between the time it is opened and the time you read it, while still allowing efficient reading.

   Part C: Give quick-and-dirty pseudocode for the implementation of the open() operation in the directory server, in terms of your answers to parts A and B. Assume that all file names are global -- that is, that there is no notion of a current working directory.