% -*- Mode:TeX -*-

% Source file for ``Supporting State-Sensitive Computation in a Dataflow System''
% Paul Barth and Rishiyur Nikhil
% March, 1989

\documentstyle[11pt]{article}

% HORIZONTAL MARGINS
% Left margin 1 inch (0 + 1)
\setlength{\oddsidemargin}{0in}
% Text width 6.5 inch (so right margin 1 inch).
\setlength{\textwidth}{6.5in}
% ----------------
% VERTICAL MARGINS
% Top margin 0.5 inch (-0.5 + 1)
\setlength{\topmargin}{-0.5in}
% Head height 0.25 inch (where page headers go)
\setlength{\headheight}{0.25in}
% Head separation 0.25 inch (between header and top line of text)
\setlength{\headsep}{0.25in}
% Text height 9 inch (so bottom margin 1 in)
\setlength{\textheight}{9in}
% ----------------
% PARAGRAPH INDENTATION
\setlength{\parindent}{0in}
% SPACE BETWEEN PARAGRAPHS
\setlength{\parskip}{\medskipamount}
% ----------------
% VARIOUS CONVENIENT WIDTHS RELATIVE TO THE TEXT WIDTH, FOR BOXES.
\newlength{\hlessmm}
\setlength{\hlessmm}{\textwidth}
\addtolength{\hlessmm}{-2em}

\newlength{\hlessmmmm}
\setlength{\hlessmmmm}{\textwidth}
\addtolength{\hlessmmmm}{-4em}
% ----------------
% CODE FONT (e.g. {\cf x := 0}).
\newcommand{\cf}{\footnotesize\tt}
% ----------------------------------------------------------------
% ID CODE DISPLAYS.
% Id code displays are enclosed between \bid and \eid.
% Most characters are taken verbatim, in typewriter font,
% Except:
%  Commands are still available (beginning with \)
%    but use ` and ' instead of { and }
%  Math mode is still available (beginning with $)
%    but use ~ and ! for ^ and _

\outer\def\beginid{%
  \begin{list}{$\bullet$}{%
    \setlength{\topsep}{0in}
    \setlength{\partopsep}{0in}
    \setlength{\itemsep}{0in}
    \setlength{\parsep}{0in}
    \setlength{\leftmargin}{1.5em}
    \setlength{\rightmargin}{0in}
    \setlength{\itemindent}{0in}
  }\item[]
  \catcode`\{=12
  \catcode`\}=12
  \catcode`\&=12
  \catcode`\#=12
  \catcode`\%=12
  \catcode`\~=12
  \catcode`\_=12
  \catcode`\^=12
  \catcode`\~=7
  \catcode`\!=8
  \catcode`\'=2
  \catcode`\`=1
  \obeyspaces
  \obeylines \footnotesize\tt}

\outer\def\endid{%
  \end{list}
  }

{\obeyspaces\gdef {\ }}

% ----------------
% ILLUSTRATIONS
% This command should specify a JJ directory for ps files for illustrations.
%\def\psfileprefix{/jj/barth/tex/popl/}
\def\psfileprefix{/home/www/csg-memos/CSG-294/images/}
\def\illustration#1#2{
\vbox to #2{\vfill\special{psfile=\psfileprefix#1.ps hoffset=-72 voffset=-45}}} 

% \illuswidth is used to set up boxes around illustrations.
\newlength{\illuswidth}
\setlength{\illuswidth}{\textwidth}
\addtolength{\illuswidth}{-7pt}

% ----------------------------------------------------------------
% ----------------------------------------------------------------

\typein{Include which sections? (intro,manage,impl,comparison,disc):}

% ----------------------------------------------------------------

\begin{document}

\begin{center}

{\Large Managing Shared Resources in a Parallel System}

Paul S. Barth \\
Rishiyur S. Nikhil

\renewcommand{\thefootnote}{\fnsymbol{footnote}}
\footnotetext[2]{
 This report was supported in part by the Advanced Research Projects Agency
of the Department of Defense under the Office of Naval Research contract
N00014-84-K-0099.
Paul Barth was supported by a fellowship from Schlumberger Technology
Corporation.
}
\renewcommand{\thefootnote}{\arabic{footnote}}

Massachusetts Institute of Technology \\
Laboratory for Computer Science \\
{\footnotesize
545 Technology Square, Cambridge, MA 02139, USA

\begin{tabular}{ll}
barth@juicy-juice.lcs.mit.edu    & (617)-253-3219 \\
nikhil@juicy-juice.lcs.mit.edu   & (617)-253-0237
\end{tabular}
}

\vspace{1cm}

{\bf Abstract}

\begin{minipage}{\hlessmmmm}

One well-known construct for managing shared resources in a parallel
system is Hoare's monitors\cite{Monitors}, which encapsulate the shared
data, operations on it, and synchronization between operations.  This
paper describes {\em managers\/}, a version of monitors for the
declarative language Id\cite{Nikhil88c}.  Like monitors, managers
provide encapsulation; however, managers make two key improvements
critical to parallel execution.  First, operations on a shared resource
have internal concurrency.  This concurrency 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.  Second, the
implementation uses low overhead, non-busy-waiting locks for mutual
exclusion.  This low overhead increases the availability of shared
resources, and encourages composite manager structures which reduce
bottlenecks.  The construct is described in detail, and our experience
with applications using managers is described.  This experience
indicates that managers are effective programming construct for systems
with multiple, dynamic threads of control and efficient context
switching.

\end{minipage}

\end{center}

\vspace{1.5cm}

% ----------------

\input{intro}
\input{manage}
\input{impl}
\input{disc}


\bibliographystyle{abbrv}
\bibliography{popl}

\end{document}
