% -*- Mode:TeX -*-

\section{Discussion}

\label{discussion}

\subsection{Experience with Managers}

We have used managers in a variety of Id application
and systems programs.  Our experience shows three things:
encapsulation is critical to correct, modular programs;
separate state and result threads do increase parallelism
and resource availability; and a low-overhead implementation
encourages the use of many, local managers in composite
structures.

In an implicitly parallel language like Id, execution order
is often hard to predict or control.  Manager encapsulation
and implicit mutual exclusion greatly simplify control issues
without unnecessarily restricting parallelism.  For example,
when the buddy system was initially implemented with locks,
the early release of a lock caused coelescing to intermittently
fail.  When recast as managers, the recursive call structure
ensured exclusion when the buddy was checked, eliminating
the error. 

Of course, encapsulation does not eliminate
deadlock.  An initial version of the union-find algorithm
for an image analysis program deadlocked when attempting
to union two elements already in the same set.  This was
remedied by locking elements in a canonical order.
Such considerations will always be present in parallel,
shared resource programs.

Modularity was improved by distinguishing between interface
operators and request handlers as suggested in \cite{Mesa}.
The union operation cited above tested its elements before
locking one by calling a request handler; therefore, union was
an interface operator but {\em not} a request handler. 
The parallel priority queue demonstrated the converse:
the tree balancing function was a completely local handler,
called by the interface operators but not visible at the interface.
A corallary of this distinction is that request handlers can be
made short, by moving  state
insensitive computations and checks outside the handler.
This increases resource availability, as suggested by
\cite{CLUMonitors}.  

Experience with the buddy system, parallel priority queue, and image
analysis programs indicates that parallel state and result threads do
increase resource availability.  Although all of these perform several
hundred instructions per operation to reorganize the structure, they
release their resources before completing execution.  The parallel
priority queue has the highest availability, releasing after a single
function call (a few dozen instructions).  The buddy system has good
amortized availability, since two memory blocks are retrieved whenever a
queue runs empty.  When there are many, distinct sets, union-find is
also highly available.  However, in the presence of a few, large sets,
union-find suffers from contention at the roots.

Parallel state and result threads allowed scheduling managers
to be more modular.  In a priority printer scheduler, small 
files are printed before  large files, even if the large file
arrives first.   The manager for this includes a separate
scheduling manager, so the policy can be altered independently
from the rest of the program.  

Finally, low overhead is central to successful use of managers.
Since managers are implemented as lock operations,
there is no temptation to use locks directly to improve performance.
Further, low overhead encourages composite manager structures, 
as experienced in the three examples cited above.
The image analysis program was originally a highly sequential algorithm
using one centralized data structure.  When recast as
a distributed, union-find structure, much more parallelism was
exposed.


\section{Conclusion}
\label{conclusion}

Managers are an effective construct for managing shared resources in a 
parallel system.  Like monitors, managers encapsulate operations on 
a shared resource.  Managers extend the monitor paradigm to
allow the succinct expression of concurrent
state-sensitive computations, yet provide control and flexibility in their
use.  They have been used for a variety of applications, and provide a
foundation for correct, efficient parallel algorithms on shared resources.

\vspace{1cm}

{\bf Acknowledgements}:  The authors are indebted to the members of the
Computation Structures Group at M.I.T. for their technical comments
and suggestions.  Arvind has been instrumental in the inception and
development of these concepts.  Richard Soley and Ken Steele developed
locked storage cells, which are instrumental to efficient implementation.
Numerous discussions with Ken Traub, Steve Heller, 
Jonathan Young, Jamey Hicks, Steven Brobst, Greg Papadopoulos,
Arthur Altman, and David Culler significantly improved these ideas.
