Homework 8 Solutions

22C:116, Spring 1999

1. Here is pseudocode for a DEMOS-based RPC protocol, ignoring issues of lost messages, but paying strict attention to protecting the client from servers that might try to send extra replies.

           client_stub( params )
              let s be a link to the RPC server
              let b be my mailbox nobody else uses
              create reply-link, a new link pointing to box b
              restrict the reply-link so it can only be used once
              send (params, reply-link) to s
              receive (results) in box b
              return results
   
           RPC server
              let s be the mailbox referenced by client links
              let r be an otherwise unused entry in the server's link list
              repeat
                 receive (params, r) in box s
                 results = the-remote-procedure( params )
                 send (results) to r
              forever
   

2. Part A: The basic DEMOS interprocess communications primitives (create a link, send a message over a link, and await a message in a specific mailbox) are not sufficient to allow implementation of time limits on an Ada rendezvous because the reply from the rendezvous must arrive in the same mailbox as the reply from the called task entry. Therefore, unless the message contents disambiguates timer replies from rendezvous replies, the calling task will be unable to tell if the rendezvous was successful or not!

   Part B: The DEMOS multiwait primitive solves this. Prior to sending the call message to a timed rendezvous, requesting a reply in box A, the caller would also request the time server to send to box B after a delay of time T. Then, the caller would do a multiwait until a reply arrives in either box A or B. If the reply was in box A, the rendezvous was successful, while if the reply came to box B, the time limit expired first.

3. Given a collection of n independent clocks, any synchronization algorithm that synchronizes the clocks to the simple average of all clocks will produce a composite that maintains the same long-term accuracy; more generally, any synchronization algorithms that compute weighted averages with the same weights will have the same long-term accuracy.

   The different clock synchronization algorithms will differ in maximum error they allow; that is, if you read the time on any two individual clocks, they may differ, and the maximum difference depends on how frequently each clock is reset to an estimate of the average for all n clocks, and the maximum difference depends on how the average for all n clocks is estimated.