Assignment 11, due Apr. 29

On every assignment, write your name and the course number legibly. Exceptions will be by advance arrangement unless there is what insurance companies call "an act of God" (something outside your control). Homework must be turned in on paper, either in class or in the teaching assistant's mailbox. Never push late work under someone's door!

1. Background Here is an Ada implementation of semaphores:

   task type Semaphore is -- Interface specification
      entry Wait;
      entry Signal;
   end Semaphore;
   
   task body Semaphore is -- Implementation of the specs
      Count: Integer;
   begin
      Count := 0;  -- Initialization
      loop
         if count > 0 then
            select
               accept Wait do -- Entry point of a rendezvous
                  Count := Count - 1;
               end Wait;      -- Exit point of the rendezvous
            or
               accept Signal do
                  Count := Count + 1; -- body of a rendezvous
               end Signal;
            end select;
         else
            accept Signal do
               Count := Count + 1;
            end Signal;
         end if;
      end loop;
   end Semaphore;
   

   In this context, a user of semaphores can create a new semaphore by a declaration such as Mutex:Semaphore. Having created this, the operations Mutex.Wait and Mutex.Signal work this implementation of semaphores.

   A classic implementation for the Ada rendezvous involves one queue per rendezvous. The queue for each rendezvous holds entries that include the parameters to that rendezvous plus a semaphore that will be signalled when the rendezvous is completed -- a low level semaphore implemented as a thread primitive, not one of the Ada semaphore given above! To call a rendezvous, a user enqueues such a record then waits on the semaphore for the rendezvous to complete.

   a) For this to work, the Ada select operator must be able to wait for any of a number of rendezvous calls and then continue when someone attempts to rendezvous with any of them. Discuss the options for implementing select. In theory, this can be done using the wait and signal operations on low-level semaphores, but it is not straightforward. (1 point)

   b) The Unix kernel call select() is at a completely different level of abstraction from the Ada select-rendezvous primitive. Nonetheless, it does something similar. Explain the similarity. (1 point)

2. A question: What is it about the machine on which Demos was implemented that forced the designers to abandon all support for memory sharing between processes and focus exclusively on a message passing architecture? (0.5 points)

   A question: What part of a Demos process resembles the open file table of a Unix process? How is it different? (0.5 points)