Homework 8

22C:116, Spring 1997

Due Friday Apr. 4, 1997, in class

Douglas W. Jones

Background: Here is a simplified model of the DEMOS message passing primitives:

create a new link and store it in entry n of the calling process's link table. The created link has all access rights, and messages sent to the link will be received on queue q in the calling processes list of incoming queues.

send a message containing len bytes of data from buf, a buffer in the caller's address space, and containing link lnk from the caller's link table, with the rights restricted by mask r. The message will be sent using dst, an entry in the caller's link table.

await a message in the calling process's queue q; put the data it contains in the caller's address space at buf storing no more than len bytes, and report the number of bytes stored in count. Put the link from the incoming message in entry lnk of the calling process's link table.
The rights attached to each link are:
Allows reuse of a link. If not set, the link self-destructs after use in the dst field of the send() operation.

Allows a process to include a link in a message by passing it as the lnk operand on a send() operation; the presence of this right is tested prior to applying the rights mask. in the dst field of the send() operation.

Allows a process to keep a copy of a link when that link is included in a message by passing it as the lnk operand on a send() operation; if not present, the link will be removed from the sender's link table when it is transmitted in a message.
Most of the following problems rest on these DEMOS services:
  1. The Problem, part A: Write a simple remote procedure call stub and client using this simplified set of DEMOS message passing primitives. Assume that, initially, the caller has a link remote to the RPC server's client message queue, and that the client has set aside the incoming message queue numbered reply to hold replies. The caller's link to the server allows all access rights. Your code should use the access rights to assure that the server does not misuse any links it receives from the client. Your code should assume that the parameters and results for the RPC are all simple data and can be easily included in one message.

    The Problem, part B: Write a more complex pair of RPC stubs that allows the client to pass n links to and receive m links from the server.

  2. Background: Assume that the standard DEMOS environment includes a link in slot timer of each process's link table that allows processes to send messages to a time-server. A message to a time server includes the integer d and the link r. The integer d gives the delay the time server should wait between receipt of a request and the sending of a reply to the link r. Time-server replies contain an invalid link and no bytes of data.

    Assume also that each process has, available to it, a unique process id, the integer id.

    The Problem: Write simplified DEMOS code for a set of fault tolerant client and server stubs. Assume that no links are among the parameters passed to and returned from the remote procedure.

  3. Background: DEMOS provided a second receive primitive, allowing a process to specify a list of its incoming message queues and wait for a message from any of the queues in that list. In addition to the information returned by the normal receive primitive, this multi-receive primitive returned the queue number of the queue in which it found the message.

    As a result, there were 3 ways to implement a collection of remote procedures on DEMOS. First, each remote procedure could be encapsulated in a separate process. Second, a group of remote procedures could be encapsulated in the same process, with a server stub that waited for messages on a single incoming message queue and used the first data item in the message to decide which remote procedure to call; and third, each remote procedure in the same server process could use a separate incoming message queue.

    The Problem: Give clear advice about when to use each of these approaches to supporting remote procedures. Consider the problems of data sharing between procedures, and consider the possibility that the procedures represent methods of an object, or methods of a class of objects.

  4. Background: A thunk is a procedure used to implement a parameter passing mode. Thunks were invented in the late 1950's to support call-by-name parameter passing in Algol 60. For a call of the form a(b), where b could be a variable or expression, call-by-name semantics requires that each reference to the formal parameter involve re-evaluating the expression passed as the actual parameter. To implement this efficiently, Algol 60 compilers would implement the actual parameter b as a pair of procedures, b_set(v) and b_get(). If the formal parameter occured on the left of an assignment statement, b_set(v) would be called with v as the value to assign to b. If the formal parameter occured in an expression, b_get() would be called to get the value of b.

    The Problem: Describe how thunks can be used in the context of remote procedure calls in order to implement parameters that are passed by name or by reference.