Homework 10

22C:116, Fall 1995

Due Friday Nov. 3, 1995, in class

1. Background: The local clock software on a typical modern operating system will offer a get time-of-day service and a service to correct the clock (for example, to instruct the clock to monotonically gain or lose a few seconds).

   Part A: Outline the structure of a decentralized clock synchronization protocol using these local operating system features.

   Part B: Consider the problem of running your clock synchronization protocol on a ring network. On such a network, the time required to send a message from A to B may be quite different from the time taken to send a message from B to A. Would you expect this assymetry to introduce any systematic error using your protocol?

2. Background: A "classical" Ada implementation of binary semaphores used for mutual exclusion rests on a piece of code with the following structure:

   task SEMAPHORE is
      entry WAIT;
      entry SIGNAL;
   end task;
   task body SEMAPHORE is
   begin
      loop
         accept WAIT;
            -- rendezvous had empty body
         end accept;
         accept SIGNAL;
            -- rendezvous had empty body
         end accept;
      end loop;
   end task body;
   

   The problem: Which of Tannenbaum's distributed mutual exclusion algorithms does this exploit?

3. Background: The solution given to problem 4 of the midterm exam uses three semaphores, one for mutual exclusion.

   The problem: Why is the mutual exclusion semaphore needed, and what small change to client and server code allows the elimination of this mutual exclusion semaphore. The Ada example given above may actually suggest a solution to this problem.

4. Background: Token ring mutual exclusion is vulnerable to problems with lost tokens.

   The problem, part A: Propose a centralized solution to this problem, where a designated station on the ring is responsible for regenerating lost tokens.

   The problem, part B: Propose a decentralized solution to this problem, where any station on the ring can regenerate a lost token, and yet, where mutual exclusion is still guaranteed even when two stations independently recognize the loss of a token and independently begin the token regeneration process.