Homework 8 Solutions

22C:116, Spring 1995

1. The problem: Is the following equivalent to a semaphore?

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

   The answer: Yes, it is equivalent to a binary semaphore, if the semaphore is used for mutual exclusion only, after initialization with exactly one call to V. Attempts to use this code to implement more generalized semaphores will quickly run into strange behavior because the V operation can block.

2. The problem: Write the code for a real-time-clock interrupt service routine that is called every 10 milliseconds and includes provisions for correcting errors in the time by adjusting the variable error.

   The answer:

         procedure tick;
           critical-section-begin
             if error > 200 then begin
               time := time + 10200;
               error := error - 200;
             end else if error < -200 then begin
               time := time +  9800;
               error := error + 200;
             end else begin
               time := time + error;
               error := 0;
             end;
           critical-section-end;
   

   Since this is an interrupt service routine, on a uniprocessor, the critical section can be guarded by disabling interrupts. On a multiprocessor, a spin-lock should also be added to lock out changes to error made by other procesors between the time it is inspected in the if statement and the time it is changed.
3. The problem: Write code to synchronize clocks as implemented above, using message passing between clock servers.

   The answer:

           procedure compute_error;
             const
               minute = 60000000; { times in usec }
             var
               i, count: integer;
   
               { clock values }
               reply_t, start_t, end_t, estimate_t: usec;
   
               { time intervals }
               trip_t, one_error, sum: usec;
           begin
             repeat
               wait(10 * minute);
               sum := 0;
               count := 0;
               for i := 1 to mum_servers do begin
                 start_t := time;
                 send(request_time,server_address[i]);
                 await(reply_t);
                 end_t := time;
                 trip_t := end_t - start_t;
                 if OK(trip_t) then begin
                   estimate_t := start_t + trip_t div 2;
                   one_error := reply_t - estimate_t;
                   count := count + 1;
                   sum := sum + one_error;
                 end;
               end;
               begin_critical_section;
               error := sum div count;
               end_critical_section;
             forever;
           end;