Homework 8 Solutions

22C:116, Fall 1997

Due Monday Nov. 3, 1997, in class

Douglas W. Jones

    The Problem, part A: The handle s on a semaphore under DEMOS would be a port or mailbox number associated with the server process. To create a semaphore, ther server would allocate a port. To destroy the semaphore, the server would deallocate that port.

    The server would await requests for semaphore creation on some server port, perhaps port zero. All other messages concerning any given semaphore would be sent to that semaphore's port. On receiving a create request, the server would allocate a port and then send a link to that port as the reply message.

    Messages to a semaphore port would be distinguished by a few bits of data; only the p message would include a link, and that link would be a one-time link used only for reply.

    The server would maintain an integer counter and a queue of reply links for each semaphore. On receipt of a P message, if the counter is nonzero, the counter would be decremented and a reply sent immediately; If the counter is zero, the reply link would be enqueued in that semaphore's link queue.

    On receipt of a V message, the if the semaphore's queue is nonempty, a reply link would be dequeued and a message sent to that link. If the queue is empty, the semaphore's counter would be incremented.

    The data structure for the queues of reply links needed by the server's semaphores would be messy, since we have a link list (formally a capability list) quite distinct from the memory in which the processor can maintain data structures. What we'll do is allocate a parallel array, next[], so that next[i] and link[i] are viewed as a record in a linked list. For semaphore number s, head[s] and tail[s] point to the first and last links in the semaphore's queue. link[head[s]] is the first reply link in the queue of semaphore s, while link[next[head[s]]] is its successor.

    The Problem, part B: With messages addressed to processes, and not to ports of processes, the message body must contain not only the operation requested but the identity of the semaphore and the process ID of the sender. Therefore, the semaphore ID will be a simple integer.

    We might set up message formats as follows:

       type     operation   parameters
       ----     ---------   ----------
    
       request, create-sem, sender's-ID
       reply,   create-sem, semaphore number
    
       request, p,          semaphore number, sender's-ID
       reply,   p,
    
       request, v,          semaphore number
    
       request, delete-sem, semaphore number
    
    Aside from change of message formats, most of the other details of the server don't change. The data structures are simplified because of the elimination of anything resembling a capability list. The server needs only two basic data structures, an array of capability description records, indexed by capability number, and a storage space for list elements, each of which has a sender's ID numbers and a next field.

  1. Part A: If each process meeting at a barrier knows the identity of all of the others, and no centeral barrier server is used, the simple solution is to send messages to all the others and then await messages from all the others.

    Part B: If there is other message traffic addressed to processes that are waiting for the barrier, these barrier synchronization messages need clear identification. If all message bodies begin with a type field, the type field for these barrier messages should be a unique value indicating that this is a barrier synchronization message. The remainder of the body can uniquely identify the barrier. When a barrier synchronization message is expected, a process should either ignore or set aside all other messages it receives.

    Part C: If messages can be lost, a process waiting at a barrier must know which processes have yet to report reaching the barrier. So, each barrier synchronization message must include the process ID of the sender. On reaching a barrier, a process sends its messages to all of the processes it is synchronizing with, and then, if it has not heard from all of its peers after some interval, it sends a second inquiry to each peer it is still waiting to hear from.

    This is not enough! We also need barrier sequence numbers, so that a process that is waiting on its third visit to a barrier because of the loss of a message from a peer doesn't unblock that peer on its fourth visit to the barrier.

  2. 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: To obtain the maximum difference between any pair of clocks, one of the clocks should be running fast, and one of the clocks should be running slow, and each should be reinforced by a number of other clocks that are running equally fast or slow. Consider the following network topology:

    (+)--(+)--(+)--(+)            (-)--(-)--(-)--(-)
                       \        /
    (+)--(+)--(+)--(+)--(+)--(-)--(-)--(-)--(-)--(-)
                       / a    b \
    (+)--(+)--(+)--(+)            (-)--(-)--(-)--(-)
                  / c              d \
    (+)--(+)--(+)                      (-)--(-)--(-)
    
    Here, the clock on machine a is naturally fast and its time is being averaged with the times on many other fast clocks and only one slow clock, while the clock on machine b is being averaged with the times on many slow clocks and only one fast clock.

    If more fast clocks are attached behind a and more slow clocks are attached behind b, the effect can be drivien to its limit, and the number of clocks it takes to force this limit can be reduced by adding more clocks tree-fashion behind the second level clocks, as shown in rowd c and d. Adding these additional branches means that any clock averaging done at a and b will have a minimal effect on clocks c and d.

    Because there is no bound on the number of machines to which eacn machine may be linked, we can make the influence of the slow clocks on machine a arbitrarily low, and the influence of the fast clocks on machine b arbitrarily low. As a result, there is no bound!

    Part B: What is the maximum difference you could observe between any two clocks in this network? This also is unbounded!