% -*- Mode:TeX -*-
\section{Introduction}  

Managing shared resources in a highly parallel system is difficult.
One well-known construct for encapsulating operations on shared
resources is Hoare's monitors\cite{Monitors}, which encapsulate
the shared data, operations on it, and synchronization between 
operations.  This encapsulation allows invariants to be established
between operations on the shared data, which are useful in correctness
proofs.  


This paper describes {\em managers\/}, a version of monitors for the
declarative language Id\cite{Nikhil88c}.  Id allows fine-grained, parallel
execution and non-strict function evaluation.  Like monitors, managers
provide encapsulation; however, managers make two key improvements
critical to parallel execution. 

First, operations on a shared resource have internal concurrency.
Specifically, two parallel execution threads are used to update the
resource and return the result to the caller.  This separation allows
difficult locking issues encountered in monitors, such
as nested monitors, recursive monitors, and the precise semantics of
{\cf wait} and {\cf signal}, to be resolved programmatically without
losing abstraction.  Although managers are implemented in Id, this
technique is effective in other languages supporting multiple, dynamic
threads of control.

Second, the implementation uses non-busy-waiting locks for mutual
exclusion.  On a dataflow machine such as Monsoon\cite{Papadopoulos88a}, process
suspension and synchronization take just a few machine instructions,
giving manager operations efficiency on par with primitive operations
such as test-and-set.  This low overhead increases the availability of
shared resources, and encourages composite manager structures which
reduce bottlenecks.  Other implementations with low-cost synchronization can
also benefit from this technique.

The next section describes the manager construct and gives several
examples, ranging from a simple memory manager to graph algorithms.
Section \ref{implementation} describes the implementation of the manager
construct on a dataflow machine.  In Section \ref{discussion} we
describe our experiences using managers in several application.
Section \ref{conclusion} contains concluding remarks.



% a declarative language supporting non-strict evaluation and
% fine-grained, implicit parallelism.  Managers are akin to abstract data
% types, providing controlled, highly concurrent access to
% shared resources.  We also describe the compilation of managers for a
% dataflow machine.  Our approach satisfies three broad goals:
% \begin{enumerate}

% \item {\bf Encapsulation:} For each type of shared resource, the construct
% clearly defines the operations that access or alter the resource.
% The synchronization and mutual exclusion between these operations due to concurrent access
% are implicit.  This allows operations to be written as state transition functions.
% Encapsulation allows shared resources and their clients to be type-checked.

% \item {\bf Expressiveness:} Managers are first-class objects that can be
% dynamically created and manipulated.  They may be composed to create
% more complex structures with shared subcomponents.  Managers permit
% nontrivial scheduling of operations, such as responding to requests out
% of order.

% \item {\bf Parallelism and Efficiency:} The dataflow implementation
% provides inexpensive synchronization and mutual exclusion, giving
% manager operations a low overhead (a few machine instructions) with no
% busy waiting.  This increases the availability of shared resources for
% parallel access.  Further, low overhead encourages composite data
% structures which can reduce bottlenecks.  A manager operation can have
% internal concurrency, further improving performance.

% \end{enumerate}
