\section{Implementation}

\label{implementation}

The implementation of managers needs to be very efficient because we use them
for frequently accessed, critical resources (for example, the memory manager
in Id's own runtime system).  There are two key issues:

\begin{itemize}

\item ensuring mutual exclusion, i.e., two requests to the same manager must
acquire the manager state serially, and

\item the implementation of {\cf MAILBOXes}, {\cf LATER}, {\cf SENDs}, etc.,
for scheduling managers.

\end{itemize}

It is clear that we need some notion of a {\em locked cell\/} for mutual
exclusion.  Further, to avoid busy-waiting, we need some way of queuing
waiting processes on locked cells and awakening a waiting process when the
cell is unlocked.  Also, because of fine-grained concurrency, these
operations must be very efficient.  All this is standard; what is novel is
the way these things blend in naturally with existing dataflow architectures
\cite{Arvind89a}.  The key features of a dataflow architecture are these:
 \begin{itemize}

\item A dataflow processor is capable of supporting thousands of threads
simultaneously, each of which is described completely by a {\em tag\/} (or
{\em continuation\/}).  The processor can switch between threads on every
instruction.

\item Memory reads are done using split-phase transactions.  Each read is
accompanied by a tag describing the continuation that expects the datum.
Meanwhile, the processor executes other threads.  The memory responds with a
datum {\em and the tag\/}, so that when it arrives, the processor knows
exactly what to do with it.

\item In the memory, every location has extra ``presence'' bits designating
it as {\em empty\/} or {\em full\/}.  When reads arrive at an empty location,
the memory controller queues the accompanying tags at that location.  When
the location is written later (making it full), the controller also
dispatches the datum to all the tags that were waiting there for it.  The
space for the deferred lists is managed locally by the memory controller.
This behavior is referred to as {\em I-structure\/} semantics.

\end{itemize}

With this basis, a small extension is sufficient to implement managers.
Instead of just reads and writes, the memory controller also accepts {\cf
read\_and\_lock} and {\cf write\_and\_unlock} requests.  As in an ordinary
read, a {\cf read\_and\_lock} request is accompanied by a tag, and if the
cell is empty, the tag is queued there.  However, if the cell is full,
instead of just returning the datum with the tag, the cell is also
redesignated as empty.  If an empty cell has no deferred readers, a {\cf
write\_and\_unlock} simply writes the datum there and marks it full.  If
there are deferred readers, however, it leaves the cell empty; instead, it
dequeues one of the waiting tags and sends it the datum.

Figure \ref{lock-memory} summarizes lock operations on I-structure memory
units, showing the contents of three cells:  the first is unlocked, the
second is locked with no waiting tags, and the third is locked with a
deferred list.
 %
\begin{figure}[htbp]
\fbox{%
  \parbox%
    {\illuswidth}
    {\illustration{lock-memory}{3.5 true in}
     \caption{%
        \label{lock-memory}
        I-structure memory
             }
    }}
\end{figure}
 %
 Note that there is no busy-waiting at all.  The thread that requires the
result of the {\cf read\_and\_lock} travels to remote memory, waits there in
a deferred queue, and comes back to the processor to resume executing---
there is no polling.  Meanwhile, the processor executes other threads.

{\bf Implementing Managers and Simple Request Handlers}

A manager is implemented as a single locked cell containing the object that
represents its state.  Scalar objects may be stored directly while non-scalar
objects may be represented by pointers.  Consider the simple memory manager,
repeated here in outline:
 \beginid
MANAGER free_list = create_free_list block
 ...
 { def create_free_list mem = break_up_mem mem;

   def_handler dealloc lst blk  = (blk:lst),ok;
   ...
 } ;          
 \endid
 The constructor simply allocates a locked cell containing the initial state:
 \beginid
create_free_list mem = allocate_locked_cell (break_up_mem mem);
 \endid

The {\cf dealloc} handler is desugared into:
 \beginid                
def dealloc cell blk = {  lst = read_and_lock cell ;
                          new_state,result = blk:lst, ok ;
                          write_and_unlock cell new_state ;
                        In
                          result } ;
 \endid
 The first argument is the manager, i.e., the locked cell.  We extract the
free list from the cell, thereby locking it;  we compute the new state ({\cf
blk:lst}), and place it back in the state cell, thereby unlocking it.
Independently, we compute the result ({\cf ok}) and return it.  If two
threads invoke handlers on the same manager at the same time, only one of
them succeeds at the {\cf read\_and\_lock}; the other one gets deferred.  The
winner computes the new state and, when replacing it in the cell using {\cf
write\_and\_unlock}, the new state is passed on to the second thread.  Thus,
we achieve the goal of mutual exclusion and serialization on the state
variable.

With this implementation, the body of {\cf dealloc} is very efficient,
amounting to as few as three or four instructions.  The only remaining
overhead is function call overhead, which is often eliminated by the inline
substitution optimization.

{\bf Implementing Scheduling Request Handlers}

{\cf MAILBOXes} are implemented using cells with standard I-structure
semantics.  A mailbox is an empty cell. The {\cf LATER} construct is simply a
read against this cell, which therefore gets deferred as explained earlier.
The {\cf SEND} construct is simply a write to the cell, which therefore frees
the deferred thread waiting there.  Thus, the cost of a mailbox is one
storage cell.  A mailbox is passed around by passing a pointer to this cell.
