Assignment 11 Solutions

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)

First, it makes sense that the caller of an entry would enqueue a message on a queue associated with that entry. In detail, the caller would claim a mutual exclusion lock (wait on a semaphore used for mutual exclusion), enqueue the message, and then signal (on another semaphore) that the queue had data in it bedore releasing the mutual exclusion lock (signalling that semaphore). The message enqueued would include all of the parameters to the entry, plus a semaphore that would be signalled when the rendezvous is completed. That means that the final step in the entry call is a wait on the semaphore that was included in the message.

To accept a particular entry, a task would wait on the semaphore indicating that there is data in the queue, and then claim the mutual exclusion lock, dequeue the data, and release the lock. After the body of the entry completes, the process would signal the semaphore that was included with the parameters.

The above is just a prologue to the real answer to this question: The select mechanism must do something like "wait for any of these semaphores to be nonzero," or "wait for the sum of the semaphores to be nonzero." We could implement this as a new semaphore service, so we have wait(), signal() and multiwait() as semaphore primitives.

That's just pushing off the problem onto lower-level services. Or, we could try to live with the standard semaphore model. In that case, we need to do something like the following:

First, instead of one mututal exclusion semaphore per queue, we have one mututal exclusion semaphore per task. It protects all of the queues associated with any entry of that task. Now, the select statement could operate by claiming the queue lock, then checking to see if any of the queues involved was not empty. It would then accept the entry on the non-empty queue. If they were all empty, it would set a switch (perhaps a pointer to the semaphore) telling anyone trying to call one of the entries to signal a special semaphore associated with that select statement instead of signalling the default semaphore for that queue. Then it would release the mutual exclusion lock and wait on that special semaphore.

Full credit was given to anyone who tried to think the problem through.

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)

The Ada select rendezvous mechanism allows an Ada task to wait for a pending rendezvous on any of a number of entries. The Unix kernel call allows a Unix process to wait for I/O to complete on any of a number of open files (open files include pipes and network sockets). Thus, both involve "wait for any of several" semantics.

The Cray 1 had no real MMU. The only memory protection it offered was a base register added to all user-mode addresses and a bound register setting the upper limit on user mode addresses.

The Demos link table resembles an open file table. Some links give access to open file objects, and conventions such as link zero is standard input, link 1 is standard output, etc, could easily be used. However, in Demos, one link would be to the current directory and another is to the root of the whole file system. This is handled quite differently in Unix, although similar pointers exist in the process description, outside the open file table. And then, in Demos, each process that is allowed to create other processes would have a link to the process manager (or at least, to a process manager). In Unix, there is nothing analogous to this.