Homework 8

22C:116, Spring 1995

Due Friday Apr. 7, 1995, in class.

1. Background: Consider the following fragment of Ada code, which serves as the body of an Ada task with two entries P and V and contains no code other than a loop and the accept statements for these entries:

      loop
         accept V;
         end accept;
         accept P;
         end accept;
      end loop;
   

   The problem: Is this equivalent to a semaphore? If not, describe a behavior you would expect of calls to the P and V entries of this task that is different from the behavior you would expect of a semaphore.

2. Background: Every ten milliseconds, the hardware clock interrupts our CPU, causing a call to be made to the realtime clock interrupt service routine; this routine is called tick. Tick maintains a global variable called time; this records the number of microseconds since the birth of John VonNeumann as a 64 bit quantity. In addition, there is a global variable, error. If you want to make the clock gain ten milliseconds, add 10000 to error. If you want to make the clock lose fifteen milliseconds, subtract 15000 from error. These changes to error must be done atomically. If error is zero, the clock is not being adjusted. If it is nonzero, the clock is being adjusted.

   Assignment: Write the code for the procedure tick. This routine should never allow the apparent clock speed to vary by more than two percent as it adjusts for errors reported to it through error.

3. Background: Consider a system with message transmission and reception using a conventional client server protocol, with the the client primitives send(request,server) and await(reply). Furthermore, this system has a number of clock servers, the network addresses of which are known, and each server is written as suggested in the previous problem, with an error variable that can be incremented or decremented to speed it up or slow it down. Additionally, each machine has a service called wait(interval) that delays the calling process by the indicated time interval (in microseconds), measured relative to the local clock.

   Assignment: Write code for a process you can run on each machine that has a clock server to keep that clock server running at the same speed as the other clocks on the net. This code should inspect all the other clocks on the net every ten minutes, reject those measurements that involved unusual trip times, and average the errors with regard to the others in order compute the amount by which the current clock should be adjusted.