Assignment 10, Solutions

Part of the homework for 22C:116, fall 2002
by Douglas W. Jones
THE UNIVERSITY OF IOWA Department of Computer Science

  1. Background: Here is a specification for a Demos-like model of interprocess communication that can be implemented under our example thread manager:
    s = send( dst, buf, len );
    send to dst (of type link) the contents of the buffer buf (of type void*) with a length in bytes of len (of type int). Variables of type link may be directly included in the buffer. This blocks until the message has been delivered and returns the number of bytes actually copied to the receiver. If dst is an invalid link

    s = receive( queuetab, number, buf, len );
    receive a message from the indicated queue number (an integer) in the queue table queuetab (of type queuetable*) into the buffer buf (of type void*) with a length in bytes of len (of type int). This blocks until a message has been delivered and returns the number of bytes actually copied from the sender.

    number = queueselect( queuetab, numbers, len );
    given numbers (of type int*), an array of len (of type int) integers, each interpreted as a queue number, and given queuetab (of type queurtable*), block until one of the queues indexed in numbers contains a message, and return the queue number. If more than one of the queues mentioned in numbers contains a message, the number returned may refer to any one of them.

    queuetab = newqueuetable( slots );
    allocate a queue table with a capacity of slots queues (an integer), returning a pointer to that table in queuetab (of type queuetable*). All the queues in the table are initially empty.

    link = newlink( queuetab, number );
    return a link allowing sending of messages to the indicated queue number (an integer) in the indicated queue table.

    Note that this set of primitives doesn't require the use of a link table because we allow links to be stored intermixed with normal variables. Note also that the queue table is not necessarily implemented as an array of queues! It is an abstraction which may have additional complexity.

    Part A: If it were not for the queueselect service, there would be many ways to implement this set of primitives. Therefore, you must begin your implementation by working out a feasible implementation for queueselect, using semaphore operations for synchronization, plus whatever other data structures are required to make it work. Propose a solution.

    Because queueselect blocks until a message is delivered to any subset of the queues in a queue table, delivery of a message to any such queue must signal the same semaphore. Therefore, all messages sent over a link to a queue in a particular queue table must actually be enqueued in the same master queue. When the receiver blocks, it will always block awaiting a message in this master queue. If the message is addressed to the wrong specific queue, the receiver will put the message in the specific queue and try again. In a bit more detail, this gives us something like this for the select operation:

                    queueselect( q, n, l ):
                        -- first see if the message is already available
                        for i in 0..l-1 do
                            if not empty( q.queues[n[i]] ) return n[i]
                        endloop
                        -- the message not already received
                        loop
                            threadwait(q.mastersem)
                            m = dequeue(q.masterq)
                            enqueue( m, q.queues[m.queuenumber] )
                            for i in 0..l-1 do
                                if m.queuenumber = n[i] return n[i]
                            endloop
                        endloop
    

    Part B: Give the header file that gives the interface specification for this package. This should conform to the style guidelines referenced from the class web page, and it need not attempt to hide the implementation of the data structures from the reader.

              /* demos.h */
    
              /******************************************************
               * Demos like message passing interface specification *
               ******************************************************/
    
              /******************************************************
               * Prerequisites for use                              *
               *   The user must include "threads.h"                *
               ******************************************************/
    
              /******************************************************
               * Private types that users really shouldn't see      *
               ******************************************************/
    
              struct msg {
                      struct msg * next; /* next message in queue */
    
                      /* description of the message itself */
                      void * buf;
                      int len;
    
                      /* needed to inform the sender of message delivery */
                      thread_semaphore * sem;
                      void * returnval;
              };
    
              struct queuetab;
    
              struct msgqueue {
                      /* standard linked-list FIFO queue implementation */
                      struct msg * head;
                      struct msg * tail;
    
                      /* you may need to add something here */
              };
    
              /******************************************************
               * Types required for the interface                   *
               ******************************************************/
    
              struct queuetab {
                      thread_semaphore mastersem;
                      struct msgqueue masterqueue;
                      int queues;
                      struct msgqueue[ 1 /* see note below */ ];
                      /* actual array size will be queues elements */
              };
    
              typedef link; /* details depend on your implementation */
    
              /******************************************************
               * The Interface                                      *
               ******************************************************/
    
              int send( link dst, void * buf, int len );
              /* send a message
                 given:  dst, the link over which the message is sent
                         buf, a pointer to the buffer to send
                         len, the length of the buffer, in bytes
                 returns:  the number of bytes actually delivered
                 note:  returns -1 if the message cannot be delivered
              */
    
              int receive( struct queuetab * t, int num, void * buf, int len );
              /* receive a message
                 given:  t, the queue table context to use
                         num, the queue number in that context
                         buf, a pointer to the buffer to receive into
                         len, the length of the buffer, in bytes
                 returns:  the size of the sender's buffer
                 note:  returns -1 if the message cannot be delivered
              */
    
              int queueselect( struct queuetab * t, int * num, int len );
              /* block until a message can be received
                 given:  t, the queue table context to use
                         num, pointer to first element of array of queue numbers
                         len, the number of queue numbers in the array
                 returns:  the queue number in which a message is waiting
                 note:  what if none of the queue numbers are valid?
              */
    
              struct queuetab * newqueuetable( int len );
              /* allocate a new queue table
                 given:  len, the number of queue numbers in the table
                 returns:  a pointer to the new table
              */
    
              link newlink( struct queuetab * t, int num );
              /* make a new link
                 given:  t, the queue table context to use
                         num, queue number in that table the link should reference
                 returns:  a link to that queue
                 note:  an invalid link will be returned if num is out of bounds
              */
    

    Notice: The complete implementation of these functions will be assigned in next week's homework.

  2. A problem: The set of primitives outlined in the previous problem is at the session level in the ISO OSI protocol hierarchy! Why?

    The send and receive primitives establish a short-lasting session as they exchange a message. This is a necessary consequence of the non-blocking semantics of message passing in this system.

  3. A problem: The notes for lecture 26 contains an algorithm for synchronizing one clock to another. This algorithm ignores the results of any query of the remote clock that takes more than mintriptime time units, but mintriptime is not a constant! Under what circumstances does it decrease, under what circumstances does it increase, and most of important of all, why?

    If mintriptime had been constant, it would need to be carefully tuned. The algorithm presented is adaptive, learning the best trip time by observation and then using it. The mintriptime variable decreases whenever a new shorter trip time is encountered. It increases slightly each time a new minimum is not encountered. If it were not increased slightly, the clocks would only be synchronized when a new minimum is encountered, and after the first few tries, new minima would probably be very rare.

  4. A problem: Consider the use of a synchronization agent, as outlined in lecture 27. What if the agent is an interrupt service routine (or alternately, a signal handler). In this case, the agent can't wait on a semaphore for the user to do something. Taking into account the synchronization between agent and application required by these distributed mutual exclusion algorithms, explain how you would handle the agent-application synchronization in this case.

    When the user wants to unblock the agent, the user enables the interrupt or enables the signal handler. When the user wants to block the agent, it disables that interrupt or signal handler. The agent can signal the user using a normal semaphore mechanism, but the thread-signal operation from a signal handler or the kernel-level signal from an interrupt service routine must not do any context switching (our thread package has this property, but if the signal operation did a relinquish, it would not be safe for this application).