Assignment 11, due Apr. 29

Part of the homework for 22C:112, Spring 2011
by Douglas W. Jones
THE UNIVERSITY OF IOWA Department of Computer Science

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;
       Count := 0;  -- Initialization
          if count > 0 then
                accept Wait do -- Entry point of a rendezvous
                   Count := Count - 1;
                end Wait;      -- Exit point of the rendezvous
                accept Signal do
                   Count := Count + 1; -- body of a rendezvous
                end Signal;
             end select;
             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)