Homework 7

22C:116, Fall 1997

Due Monday Nov. 3, 1997, in class

1. Background Consider the possibility of implementing a synchronization server in a network. This service would have four operations, all of which can be abstractly described as procedure calls:

   createsem(out s)

   returns s, the identity of a newly created semaphore.

   p(in s)

   v(in s)

   given s, the identity of a semaphore, perform the standard semaphore operations.

   destroysem(in s)

   given s, the identity of a semaphore, deallocate that semaphore.

   The Problem, part A: Describe how you would implement this server under the DEMOS message passing primitives. In answering this question, your first priority will be to identify the type of s, the handle on a semaphore! Your second priority will be to identify how you use the various incoming message queues and links that the server may have. Finally, you can round out your description of the top-level design for the server by describing the formats of the messages between client and server.

   The Problem, part B: Describe how you would implement this server if you were required to use the following set of message passing primitives. Your description should be at the same level as the description you gave above; you may assume that each process knows its own address and that each client process knows the address of the synchronization server.

   send( addr, msg, len )

   Sends msg, a message of length len, to the process designated by addr.

   receive( buf, size, len )

   await any message addressed to this process, on receipt, put it in buf a buffer of size bytes, and report the actual message size in len. If, after the call, len is larger than size, some bytes of the received message were discarded.

2. Background: Consider the problem of implementing barrier synchronization using message passing, with the send and receive primitives given above. Each process meeting at the barrier knows the identity of all of the others, and no centeral barrier server is used.

   Part A: Describe a simple solution to this problem, assuming that the only message exchanges between the processes are involved in implementing a single barrier, and assuming that message transmission is reliable.

   Part B: Describe how you would modify the above solution to allow for other message traffic addressed to processes that are waiting for the barrier.

   Part C: Describe how you would modify the above solution to allow for the possibility of lost messages.

3. Background: Consider a network with a diameter of 10 -- that is, the longest shortest-path in the network involves 10 machine-to-machine links. In this network, each machine has a local clock, where each clock is guaranteed to run at a speed no more than 10% faster or slower than the real time. In addition, each machine synchronizes itself with its neighbors every 10 seconds -- averaging the times reported and setting itself to the average.

   Part A: What is the maximum difference you could observe between any pair of clocks in this network? An approximate answer based on sound reasoning is acceptable here!

   Part B: What is the maximum difference you could observe between any two clocks in this network? Why isn't it (or why is it) 10 times the error you gave in part A?