% -*- Mode:TeX -*-

\def\floatingfigure#1#2#3{
   \begin{figure}[htbp]
\fbox{
   \parbox
       {\illuswidth}
       {\illustration{#1}{#2}
          \caption{\label{#1}
               #3}
        }
     }
    \end{figure}
}

\section{Managers} 

A manager is a high-level interface to a single {\em state variable},
which is shared by an arbitrary number of processes.  The state variable
may be a simple value or a data structure, such as a list, array, or
tuple.  Managers define functions for creating, accessing, and modifying
state variables.  Processes request a resource by calling these
functions; the manager synchronizes incoming requests to ensure
exclusive access to the state variable.  Processing a request updates
the state variable and returns a result to the caller.  Figure
\ref{managers} illustrates this view of managers.

\floatingfigure{managers}{2.7 true in}{System View of a Manager}

\subsection{Encapsulating Operations on Shared Resources}

Managers encapsulate the state variable like abstract data types.
Specifically, each manager defines an abstract
type for the state variable, with a set of query and 
update operations (called {\em request handlers}), and a constructor
for creating instances of the type.
State variables can be accessed only through this interface.
In addition to defining the interface functions, the abstraction
hides the synchronization and updates on the state variable,
so that request handlers can be written functionally.
The program interface to managers is similar to  abstract types:
manager instances are created (with some initial state) and
passed to functions who may make requests on the instance.
Manager requests return a result, just like other function calls.
The synchronization and state update is entirely hidden from the caller.

As an example, consider a simple memory manager.
A list of free memory blocks is created from a section of memory.  An allocate
request pops the first block off the free list; if the list is
empty the response ``no'' is returned.  Deallocate requests
push a memory block onto the free list and receive an acknowledgement.
Query requests return the number of blocks on the free list.
The manager
for this example is shown in Figure \ref{smm}.\footnote{Some syntactic notes: The infix colon
({\cf :}) is the cons operator; comma ({\cf ,}) is the infix
tupling operator.  A multi-line function ({\em e.g.,} {\cf alloc})
uses pattern-matching on the structure of its argument in
lieu of conditionals to select the result expression.
Note that this manager relies on a more primitive manager
for the cons operation.}

\begin{figure}[htbp]

\beginid

type response = block | no ;
type ack      = ok;

\null
MANAGER free_list = create_free_list block
 typeof alloc    = free_list -> response;
 typeof dealloc  = free_list -> block -> ack;
 typeof query    = free_list -> num
 rep (list block)
 { def create_free_list mem = break_up_mem mem;
        
   def_handler alloc   nil      = nil,no
        |      alloc   blk:rest = rest,blk;
        
   def_handler dealloc lst blk  = (blk:lst),ok;
        
   def_handler query   lst      = lst,(length lst);
 } ;          
\endid

\caption{A Simple Memory Manager}
\label{smm}
\end{figure}



As with abstract types, the manager construct has two components: the {\em
interface} definition (the first four lines), and the {\em representation} (everything
following {\cf rep}).  The interface gives the type signature of the constructor
and the operators.  The constructor {\cf create\_free\_list}
takes a block and creates an instance of the type {\cf free\_list}.
The operators {\cf alloc, dealloc,} and {\cf query}, take
a free list instance (and any other arguments) and return a result.
Note that the interface definition hides the access and update of the 
contents of the free list.

The representation gives the type of state variable, and defines the
constructor and operators.  Here the type of a free list is a list of
memory blocks.  The constructor computes the initial state of the
instance; in this case, it breaks the section of memory provided into a
list of blocks.  In the representation, functions that access or change
the state variable are defined with the {\cf def\_handler} construct,
which provides mutual exclusion on the state.  (These are analagous to
monitor entry procedures.) Handlers are written as functions from the
old state (and other arguments) to a {\em pair} of values: the new state
and the result.  Note that the type signature of a function defined with
{\cf def\_handler} hides the state and its update.  For example, the
{\cf dealloc} function takes a free list and block as arguments, and returns
an acknowledgement, as declared in the interface.  However, the
expression that computes the result is given the state of the free list
(a list of free blocks) and returns the new state (adding the block to
the list) and the acknowledgement ({\cf Ok}).  Thus, {\cf def\_handler}
provides an important abstraction: handlers are {\em defined} as state
transformations that assume exclusive access; but handlers are {\em
used} as functions without reference to the state.  This distinction
only applies to a handler's first argument; other arguments (even those
referring to managers) pass in unchanged.  Interface functions may be
handlers, as in this example, or not; conversely handlers may be
exported or strictly local.  The manager body may also contain local
values or function definitions.



\subsection{Concurrency and Request Handlers}

The {\cf def\_handler} construct has an important impact on parallelism.
Each handler computes a pair of values, the new state and the result.
Corresponding to each of these values is a thread of computation; to the
extent that these threads are independent,\footnote{
In Id, threads are defined by data dependencies.   Two threads
with no data dependencies are independent, and may execute in parallel.}
they may be executed in
parallel.  These threads asynchronously update the state (thus unlocking
it) and return the result to the caller.  This asynchrony may increase
availability of the resource, or lower the latency in responding to a
request.  For example, a {\cf query} request can return the state
immediately, making it available while it is computing the length.
Alternatively, the acknowledgement of a {\cf dealloc} request may be
returned before the state is updated.

Beyond efficiency, independent threads within a request handler
can be stopped and resumed independently, allowing managers
to schedule and reorder requests, as described in the next
section.  This generalizes to support recursive and cyclic structures,
beyond the capabilities of monitors.


\subsection{Scheduling with Managers}

Scheduling reorders manager requests, deferring some while allowing later
ones to proceed.  This requires a facility for suspending and resuming a 
thread, which we call a 
{\em mailbox}.  Associated with every request handler is synchronization variable
referred to with the keyword {\cf MAILBOX}.  The mailbox is a first-class
value that may be passed to functions and stored in data strucutres.
The keyword {\cf LATER} suspends an execution thread, awaiting  a {\cf send} operation
on the mailbox.  This sends a value  to the mailbox, which resumes the
suspended thread.

For example, consider a slight variation on the free list.  In this
scenario, allocate requests to an empty list are deferred until
memory is deallocated.  Deallocate forwards its block to a deferred
allocate, if any.  The manager in Figure \ref{nmm} implements this example.

\begin{figure}[htbp]

\beginid


MANAGER patient_free_list = create_patient_free_list block
 typeof alloc    = patient_free_list -> block;
 typeof dealloc  = patient_free_list -> block -> ack ;
 typeof query    = patient_free_list -> num;
 rep ((list block),(list (MAILBOX block)))
  {\
\null
    % `\em the state is pair: (free_list,list of deferred allocs)'
    def create_patient_free_list block = (break_up_mem block),nil;
\null
    def_handler alloc (nil        ,allocs)   = (nil,MAILBOX:allocs),LATER
        |       alloc ((block:lst),nil   )   = (lst,nil)           ,block;

\null        
    def_handler dealloc (lst,nil)      block = ((block:lst),nil),ok
        |       dealloc (nil,M:allocs) block = {send M block
                                                In
                                                  (nil,allocs),ok};
\null
    def_handler query   (lst,allocs)         = (lst,allocs),(length lst)
  } 

\endid

\caption{The Patient Memory Manager}
\label{nmm}
\end{figure}

The interface to this memory manager is identical to the previous one.
However, the representation is significantly different.  The state
variable contains two items: the list of free blocks, and a list of deferred
allocate requests.  The {\cf alloc} request handler shows how they are deferred.  If
there is a block on the free list, it is returned as usual.
If not, the state is updated by adding {\cf alloc}'s mailbox to
list of deferred allocates, while leaving the free list empty.  The
response part of the result is {\cf LATER}, indicating that the response
will be determined later by a {\cf send} operation on the mailbox.

Deallocate requests proceed as before when there are no deferred allocates.
Otherwise, the block is sent to the first mailbox on the list, which
allows the suspended alloc request to return its result.  The new
state has the mailbox removed from the deferred allocate list, and
an acknowledgement is returned.

\subsection{Mailboxes, Signal, and Wait}
  
Although mailboxes are very powerful, they open the door to a new class
of programming errors.  Mailboxes could be sent multiple values or lost,
or a request handler could release its mailbox {\em and} return a
result.  Type-checking may uncover some of these errors at compile-time,
but most can only be detected at run-time, if ever.
Further, this use of mailboxes makes {\cf alloc} and {\cf dealloc} responsible for
scheduling, as well as memory management, which is clearly not
modular.

One way to reduce these errors is to encapsulate scheduling operations
in a manager.  For example, consider the {\cf wait} and {\cf signal}
monitor operations.  These allow a condition on the state to be
established before a handler is executed.  If the condition
is false, {\cf wait} suspends the result of the request and
releases the state, unchanged.  When the state is modified, the
{\cf signal} operation resumes the handler which returns its result.


\begin{figure}[htbp]

\beginid

manager waiting_q = create_waiting_q num
  typeof wait   = waiting_q -> block;
  typeof signal = waiting_q -> (list block) -> (list block)
  rep (list (MAILBOX block))
  { def create_waiting_q n = nil;

    def_handler wait q = (mailbox:q),later;

    def_handler signal nil   lst         = nil,lst
       |        signal (m:q) (block:lst) = {send m block;
                                            In
                                              q,lst};
   };


MANAGER patient_free_list = create_patient_free_list block
 typeof alloc    = patient_free_list -> response;
 typeof dealloc  = patient_free_list -> block -> ack ;
 typeof query    = patient_free_list -> n;
 rep ((list block),waiting_q)
  {\
    def create_patient_free_list block = (break_up_mem block),nil;
\null
    def_handler alloc (nil,      q)   = (nil,q),wait q 
        |       alloc ((block:lst),q) = (lst,q),block;

\null        
    def_handler dealloc (lst,q) block = ((signal q (block:lst)),q),ack;
\null
    def_handler query   (lst,q)  = (lst,q),(length lst)
  };


\endid

\caption{A Wait and Signal Manager}
\label{waitingq}
\end{figure}

Figure \ref{waitingq} shows how simple versions of {\cf wait} and {\cf
signal} can be encapsulated in a manager for the patient free list.
Calling {\cf wait} simply enqueues the mailbox on the queue of waiting processes
and suspends its result with {\cf LATER}.
{\cf Signal} takes a new free list as an argument: if there are no waiting allocs, it
simply returns it for the new state. Otherwise, it sends the head of the free list to
the first mailbox, pops the mailbox, and returns the remainder as the new
state.

Although this version of a waiting queue is specific to the
problem at hand, more general versions can be constructed similarly.
This illustrates an important point:  managers allow queuing to
be incorporated in a modular, programmatic way.  Because waiting
queues are managers, different algorithms can employ different
paradigms.  These include FIFO (first-in, first-out), priority,
and predicate-based scheduling.  It can be extended to also include
a ``notify'' paradigm\cite{Mesa}, where the state is returned 
immediately and the signal is requeues the request.

Note that type of composition and modularity cannot be achieved with
monitors; wait and signal operations implicitly modify the resource
lock.  This has several ill-effects, as amply described in the
literature\cite{CLUMonitors,Mesa,NestedMonitors}.  Simple monitor
nesting, as illustrated above, traditionally presents problems when the
nested monitor suspends.  Managers allow issues like this to be resolved
explicitly and programmatically, as appropriate to the algorithm.

        
\subsection{Composition} 

Individual managers can support a wide range of programs.
However, many applications may require several managers working
in concert.   The example above illustrates a simple nested 
manager structure.  Since managers as first-class objects,
networks of managers can be defined using standard
data structures such as lists and arrays.
Furthermore, managers can form arbitrary graph
structures by storing manager references in the state
variable.  These structures can be made dynamic by operations
that alter the references during execution.
This section gives examples of these types of composition.

\subsubsection{The Buddy System}

Consider a buddy system memory manager, structured as follows.
Let there be a vector $v$ of free lists, where element $i$ is a
manager for memory blocks of size $2^i$.  Allocate and
deallocate requests are directed to the appropriate manager.
Allocation removes the head of the list and returns it; however, if
the list is empty, an allocation request is issued to the manager
of the next larger size block.  This recurs until a block is found
or the end of the vector is reached.  When the block is returned,
it is split: half is returned as the result, and half is placed on
free list.  Deallocate requests coalesce blocks in a similar,
recursive fashion, forwarding successively larger blocks until
no buddy is found.  The free list manager (without boundary conditions)
is given in Figure \ref{buddy}.

% manager buddy_list = make_buddy_list block i a
%   typeof alloc = buddy_list -> i -> block;
%   typeof dealloc = buddy_list -> block -> i -> void
%   rep (list block)		      % note reference to buddy list
%      {
%       def make_buddy_list mem = break_up_mem mem;

%       def_handler alloc block:mem_q i = mem_q,block
%         |         alloc nil       i  =				        
%                     if i==MAXINDEX then   
% 	              error "Out of Memory"
% 	            else			% alloc larger block and split
% 	              {big_block = alloc memory[i+1] i;
%                        top,bottom = split big_block i;
%                        In
% 		       (top:mem_q),bottom};

%       def_handler dealloc mem_q block i =
% 	if i==MAXINDEX then	% no coalescing last element
% 	  (block:mem_q),ack
% 	else
%           if (free_buddy? block) then
%             {big_block = (coalesce block i);  % join memory and deallocate
% 	     In
% 	       mem_q,(dealloc memory[i+1] big_block (i+1))}
%           else (block:mem_q),ack
%        };


\begin{figure}[htbp]

\beginid

manager buddy_list = make_buddy_list block
  typeof alloc   = buddy_list -> num -> block;
  typeof dealloc = buddy_list -> block -> num -> ack
  rep (list block)
     {
      def make_buddy_list mem = break_up_mem mem;

      def_handler alloc block:mem_q i = mem_q,block
        |         alloc nil       i  =                                        
                      {big_block = alloc v[i+1] i;
                       top,bottom = split big_block i;
                       In
                       (top:mem_q),bottom};

      def_handler dealloc mem_q block i =
          if (free_buddy? block) then
            {new_q     = remove_buddy block mem_q;
             big_block = (coalesce block i);  % join memory and deallocate
             In
               new_q,(dealloc v[i+1] big_block (i+1))}
          else (block:mem_q),ok
       };

\endid

\caption{The Buddy System}
\label{buddy}
\end{figure}

Note that although both {\cf alloc} and {\cf dealloc} are recursive, they 
have different locking behavior.  In {\cf alloc}, both
the state and result depend on the result of the recursive call.
Therefore, free list $i$ is locked until the recursive call to 
free list $i+1$ returns.\footnote{This is appropriate, since another allocate
request would simply duplicate the work currently outstanding.}
{\cf dealloc}, on the other hand, releases its state immediately.
The recursive call only delays the result, an acknowledgement indicating
the deallocate has completed.  Monitors only support the first type
of locking scheme; a monitor implementation of the above would
delay the state until coalescing completes.\footnote{
Alternatively, the recursive call could be moved outside the entry procedure,
but this results in fragmented control flow.}

\subsubsection{Manager Graphs}

\paragraph{Trees}

Managers have been structured as trees to implement union-find\cite{unionfind}
and parallel priority queue\cite{ppq} algorithms.  In manager trees,
the state contains pointers to other managers.  These pointers are 
traversed and modified by manager operations, allowing the structure
of the trees to dynamically change.  In the union-find algorithm, this
enables path compression, a technique that drastically reduces the cost
of set membership (find) operations.  In the parallel priority queue,
tree balancing is done by recursive calls on the manager links.
Therefore, both of these algorithms demonstrate good amortized
time complexity.  In addition, the latency of individual operations
is low, because the state is available before the recursion has
terminated.  Trees also improve availability of the resource, since
locking is localized to the subtree being modified.

\paragraph{Cyclic Graphs}

As a final example, consider a simple, recursive algorithm on
a directed graph.  The problem is to count the number of distinct
nodes reachable from a node.  One natural solution is as follows:
at each node, leave a mark and recursively count all neighbors of the
node.  Add one to the sum of the counts returned.  Whenever a mark
is reached, return zero.

\beginid

manager node = make_node (list node)
  typeof count = node -> num
  rep (bool,(list node))
  {make_node neighbors = (false,neighbors);
   
   def_handler count (true,neighbors)  = (true,neighbors),0
       |       count (false,neighbors) = (false,neighbors),
                                         1+(sum (map count neighbors))
   };

\endid

This simple manager cannot be written as a monitor without
potential deadlock, since the lock is held until the result is returned.
A monitor solution requires the recursion to be moved to an external
procedure, and reduces the monitor to a test-and-set operation.  In
the process, abstraction and modularity are destroyed.

\subsection{Programming Paradigms}

These examples illustrate the variety of concurrent programming
paradigms managers support.  The separate, parallel computation threads
within a manager operation can be controlled to support a broad class of
algorithms.  In the simplest case, both threads return immediately.  In
this case, managers provide mutual exclusion, while parallelism improves
efficiency and availability.  Including mailboxes that suspend one of
the threads\footnote{Suspending both threads results in deadlock.}
presents two additional cases:

\begin{enumerate}
\item {\bf Suspended Result:} requests can be reordered.  Examples
include the patient free list, and any type of scheduler.

\item {\bf Suspended State:} resource locked when result returned.
Presumably the result contains a mailbox so the state thread 
can be resumed.  This allows mutual exclusion over a set of resources,
but in general breaks the abstraction.
\end{enumerate}

Composite managers allow recursive structures with distributed locks.
Recursive calls on these structures can delay one or both of the threads,
resulting in the following three cases:

\begin{enumerate}
\item {\bf Recursive State, Immediate Result:} the result is returned immediately
while the structure is recursively updated.  Note that the new state will be
returned immediately by the recursive call, so the resource will only be locked
for one recursive call, even if the call chain is deep.  This implements
a technique called {\em lock-coupling}, where a resource lock is not released until
the next is acquired.

\item {\bf Immediate State, Recursive Result:} Here the resource is
available while the result is being recursively computed.  Examples are
the {\cf dealloc} handler in the buddy system, and the cyclic graph manager.

\item {\bf Recursive State and Result:} Resource and result are unavailable
until the end of the recursive call.  Unlike the first case,
resources are locked all along the call chain.  This is useful for
excluding entry into the chain until the recursion finishes, as in
the buddy system example.  Note that this is the only form of recursion
supported by monitors.

\end{enumerate}

\subsection{Summary}

Like monitors, managers provide encapsulation.  The state variable and its
associated operations are defined in a single construct.  The external
interface to a manager is clearly defined, and request handlers
can be written as as state transition functions.  Further, the state
variable is completely hidden from the interface.

Managers are more expressive than monitors.
Mailboxes allow requests to be deferred and reordered
with the addition of simple queueing operations.
Managers can be composed into networks of asynchronous
processes in an abstract and modular way.
Recursive operations on such structures can explicitly control
resource availability and deadlock avoidance.  


