% -*- Mode:TeX -*-

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

\section{Managers} 

The Id programming construct for shared resources is the {\em manager}.
Conceptually, a manager is a high-level interface to a {\em state
variable}, which is shared by an arbitrary number of processes.  A
manager defines functions for creating, accessing, and modifying the
state variable.  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 other 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 bank account program.
An account is created with an initial deposit, against which credits and
debits may be issued.  If a credit is issued, the balance is updated and
acknowledged with an {\cf Ok} response.  If a debit is issued, the
balance is checked and updated if it is sufficient, and {\cf Ok} is returned.
If the balance is
insufficient, it is not updated and {\cf No} is returned.  This example is
shown in Figure \ref{sba}.

\begin{figure}[htbp]

\beginid

% typeof ack = Ok | No ;
% \null
% MANAGER simple_account = create_account N
%  typeof credit = simple_account -> n -> ack ;
%  typeof debit  = simple_account -> n -> ack ;
%  typeof query  = simple_account -> n
%  rep (N)
%  { def create_account init_bal = init_bal;
%    def_handler credit bal amt = bal+amt,Ok;
%    def_handler debit  bal amt = if (bal >= amt) then
% 				  bal-amt, Ok
%                                 else
%                                   bal,No ;
%    def_handler query  bal     = bal, bal
%  } ;          


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

\caption{A Simple Bank Account}
\label{sba}
\end{figure}

As with abstract types, the manager construct has two components: the {\em
interface} definition (the first four lines), and the {\em body} (everything
following {\cf rep}).  The interface defines the types of the request
handlers and the arguments to the constructor.  These definitions make no
reference to the associated state.  The interface to {\cf simple\_account}
consists of the three request handlers, {\cf credit}, {\cf debit}, and {\cf
query}, and the account constructor, called {\cf create\_account}.  
The request handlers take an account instance and other arguments (if any)
and return a response (either a balance or an acknowledgement).  The
constructor takes an initial balance and returns an account instance.

The manager body defines the request handlers and constructor of
the manager instance.  Here, the request handlers are written as
functions from the account balance and other arguments to a pair of
values: the new balance, and the response.  The constructor creates a new
manager instance, and computes its initial state from the given expression.
The manager body may also contain local values or function definitions.   

Note that the internal and external type signatures of the request handlers
are different.  This reflects the implicit support for mutual exclusion.
Externally, handlers are simply passed the shared resource and return a
result; the state of the resource is hidden.  Internally, the handler
is given the state of the resource and computes a new state, along with
the response for the caller.  This distinction only applies to a handler's
first argument; other arguments (even those referring to managers) pass in unchanged.

The code template below illustrates the use of this manager:

\beginid
   {my_accout = create_account 0;
\null
    ... (debit my_account 5) ...
\null
    ... (credit my_account 7) ...
\null
    ... (query my_account) ... }
\endid

Here, the {\cf create\_account} constructor creates the instance {\cf
my\_account} with a balance of 0.  Three requests
are made on the account, a debit of 5, a credit of 7, and a balance
query, which is returned.  Id is an implicitly parallel language, which
serializes requests based only on data dependencies.  Assuming there are
no dependencies between these requests, they may execute in
parallel.  The order in which they are processed is indeterminate, but
the manager construct guarantees
serializability\cite{LamportSerializable}.  That is, the value of the
state variable following the processing of these two requests will be
the same as some serial order of these requests.  In this example, the
result of the query request will be either 0, 7, or 2, which correspond
exactly to the possible balances.


% \subsection{Types}


% The manager construct defines an abstract type $T$ (possibly polymorphic).
% The name and signature of the constructor follows the manager name,
% which of course must return an object of type $T$.  Each request
% handler has two type definitions, internal and external, to allow the
% state variable to be hidden from requestors.  The external type of each
% handler is given its interface type declaration, of the form:

% \begin{equation}
% T\rightarrow T_{1} \rightarrow ...\rightarrow T_{n}\rightarrow T_{r}
% \end{equation}

% Therefore, users see each handler as
% a function call, taking the manager instance and other arguments and
% returning a result of type $T_{r}$.

% A handler's internal type is similar to the external, but makes the
% state variable (of type $T_{s}$) explicit:

% \begin{equation}
% T_{s}\rightarrow T_{1} \rightarrow ...\rightarrow T_{n}\rightarrow T_{s} \times T_{r}
% \end{equation}

% That is, the arguments are identical to the interface, except for the first, where the
% manager is replaced with the (current) value of the state variable.
% The expression returns a pair, the new state and the result.

% The dual types of request handlers indicate the implicit management of
% the state variable.  The first argument is transformed from a manager in
% the external interface to its associated state in the body.  Conversely,
% the pair returned by the body is partitioned into a new state and a
% result that is returned at the interface.  Note that the first argument
% is the only argument to go through such a transformation: other
% arguments, even those referring to managers, are passed directly into the
% body.  This allows networks of managers to be defined, as described
% below.

\subsection{Scheduling with Managers}

Managers defined thus far allow a wide range of state-sensitive
programs to be written, such as data bases and priority search
programs.  These programs channel information between computations
through the state variable.  However, some programs
require state-sensitive scheduling.

Scheduling reorders manager requests, deferring some while allowing later
ones to proceed.  This requires a facility for deferring 
the result of a request handler.  We call this facility a 
{\em mailbox}.  Every manager request has an associated return address for
its response;  this address can be referred to in a request handler with the
keyword {\cf MAILBOX}.  If the response computed by a request handler is the
keyword {\cf LATER}, the response is deferred until a {\cf send} operation
is performed on the mailbox.  This sends a value  to the mailbox, which is then
returned by the deferred request handler.
% For example, the body of the {\cf query} handler could be written

% \beginid
%     query bal = { send MAILBOX bal
%                 In
%                   bal,LATER}
% \endid

% Here, the mailbox is used explicitly to return the result of the query.
% Typically, however, the state variable is used to store the mailboxes of
% deferred requests until other request handlers send them results.

For example, consider a slight variation on the bank account.  In this
scenario, debits greater than the current balance are deferred until
sufficient credits are made.  Incoming credits are applied against deferred
debits, and the satisfied debits are processed.  Credits and debits return
acknowledgements, while queries return the balance.  The
manager in Figure \ref{nba} implements this example.

\begin{figure}[htbp]

\beginid

% MANAGER nice_account = create_nice_account N
%  typeof credit = nice_account -> n -> ack ;
%  typeof debit  = nice_account -> n -> ack ;
%  typeof query  = nice_account -> n
%  rep (n,(list (n,(MAILBOX ack))))
%   {\
% \null
%     % `\em the state is pair: (balance,list of deferred debits)'
%     def create_nice_account init_bal = (init_bal,nil);
% \null
%   \% `\em Here is a local function that runs down the list of pending debits,'
%   \% `\em discharging whatever it can, returns a new balance and remaining pending'
%   \% `\em debits.  It is not fair about the order of servicing debits.'
% \null
%     def discharge_debits bal Nil          ds  = bal,ds
%      |  discharge_debits bal ((amt,M):ds) ds1 = 
%                      if (bal >= amt) then
%                        { newbal = bal - amt ;
%                          call send M Ok
%                         In
%                           discharge_debits newbal ds ds1 }
%                      else
%                        discharge_debits bal ds ((amt,M):ds1) ;
% \null
%     def_handler credit (bal,ds) amt = (discharge_debits (bal+amt) ds Nil), Ok;
%     def_handler debit  (bal,ds) amt = if (bal >= amt) then
%                                        (bal-amt,ds),Ok
%                                       else
%                                        (bal,(amt,MAILBOX):ds),LATER;
%     def_handler query  (bal,ds)     = (bal,ds),bal
%   } ;



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

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

MANAGER nice_free_list = create_nice_free_list ptr
 typeof alloc    = nice_free_list -> response;
 typeof dealloc  = nice_free_list -> ptr -> ack ;
 typeof query    = nice_free_list -> n;
 rep ((list ptr),waiting_q)
  {\
\null
    % `\em the state is pair: (free_list,list of deferred allocs)'

    manager waiting_q = create_waiting_q n
      typeof wait = waiting_q -> ;
      typeof signal = waiting_q -> ptr -> (list ptr) -> ((list ptr),waiting_q)
      rep (list (MAILBOX response))
      { def create_waiting_q n = nil;

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

        def_handler signal nil   ptr lst = nil,((ptr:lst),SELF)
           |        signal (m:q) ptr lst = {send m ptr;
                                            In
                                              q,(lst,SELF)}
        
    def create_nice_free_list ptr = (break_up_mem ptr),nil;
\null
    def_handler alloc (nil,      q) = (nil,q),  wait q 
        |       alloc ((ptr:lst),q) = (lst,nil),ptr;


    def_handler alloc (lst,q) = when (not (nil? lst)) q ((tl lst),q),(hd lst);  % when syntax


\null        
    def_handler dealloc (lst,q) ptr = (signal q ptr lst),ack;

\null
    def_handler query   (lst,allocs)       = (lst,allocs),(length lst)
  } 

\endid

\caption{The Nice Bank Account}
\label{nba}
\end{figure}

The interface to this account manager is identical to the previous one.
However, the body is significantly different.  The state
variable contains two items: the current balance, and a list of deferred
debits.  The debit request handler shows how debits are deferred.  If
the balance is sufficient to cover the debit, it is processed as usual.
If not, the state is updated by adding the debit's amount and mailbox to
the list of deferred debits, while leaving the balance the same.  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.

Credits return an {\cf Ok} response, and use the local function
{\cf discharge\_debits}\footnote{This is a multiline function definition that
uses pattern-matching to choose the appropriate clause.}
to apply the credit against any outstanding debits.
For each entry in the list of debits, this function tests if the 
balance is sufficient to cover the amount.  If so, the amount is subtracted
and the {\cf Ok} acknowledgement is sent to the associated mailbox.
The entry is removed from the list, and the function is called recursively
on the rest of the list with the remaining balance.  If the amount of the
entry exceeds the balance, the entry is saved and the rest of the list is
tested recursively.  When the entries are exhausted, the remaining entries
and balance are returned as the new state.

% Mailboxes fit naturally in the manager type discipline.  Recall that
% each request handler returns a result of type $T_{r}$.  The type of
% the mailbox associated with a request handler is {\cf (MAILBOX $T_{r}$)}.
% The type of the keyword {\cf LATER} is clearly $T_{r}$, while the
% signature of the {\cf send} function is
% {\cf (MAILBOX $T_{r}$)$\rightarrow T_{r} \rightarrow$void}.
% Id's normal type checking mechanism can therefore be applied to mailboxes.


Note the expressiveness of the manager construct
when extended with mailboxes. Requests can arrive, be reordered,
and processed with the addition of simple queuing operations.  
Although this paradigm is very flexible, it opens the door to a new
class of programming errors: sending multiple values to a mailbox.
Since mailboxes are first-class objects, they could be passed to several
functions that perform send operations.  Alternatively, a request
handler could release its mailbox {\em and} return a result, rather than
the keyword {\cf LATER}.  Also, if a mailbox is ever lost, the result of
the request handler is never returned.  Type-checking may uncover some
of these errors at compile-time, but most can only be detected at
run-time.  Of course, lost mailbox errors may never be detected.  The
potential for error seems inextricably intertwined with scheduling
flexibility: constraints on the uses of mailboxes would also constrain
the class of schedulers that could be written.

% \subsection{Manager Networks}

% Individual managers can support a wide range of programs.
% However, many applications may require several managers working
% in concert.  The treatment of managers as first-class objects
% allows networks of managers to be defined using standard
% data structures such as lists and arrays.

% As an example, consider Dijkstra's  problem of the dining philosophers
% \cite{DijkstraDining,ParlogDining}.  There are five philosophers who
% share a dining table.  Each philosopher is assigned a seat, and requires the
% forks on either side to eat the meal in the center.  There are
% five forks, one between each pair of plates.  Each philosopher lives a dreary
% existence of alternating between thinking and eating.  When a philosopher is ready to
% eat, he contends with his neighbors for the forks on his left and right.
% This contention can lead to deadlock, where
% each philosopher holds his left fork and is waiting for his right.
% A simple solution allows only four philosophers at the table at a time.
% In this model, there are four tickets at the center of the table.
% A philosopher takes a ticket, picks up his left
% and right forks, and eats.   When finished, the philosopher returns his
% forks and ticket.  This solution is given in Figure \ref{phil}.

% \begin{figure}[htbp]

% \beginid

% MANAGER limited_resource = create_limited_resource N
%   typeof take   = limited_resource -> ack ;
%   typeof return = limited_resource -> ack
%   rep (n,(list (mailbox n)))      
%   {
% \null
%     \% `\em state is a pair: (# resources left, list of mailboxes waiting for resource)'
%     def create_limited_resource n = (n,Nil) ;
% \null
%     def_handler take (n,Ms) =  if n == 0 then
%                                 (n,(MAILBOX:Ms)),LATER
%                                else
%                                 (n-1,Ms),Ack;
% \null
%     def_handler return (n,Nil)  = (n+1,Nil), Ack
%   |             return (n,M:Ms) = { call send M Ack
%                                     In
%                                       (n,Ms),Ack } ;
%   } ;
% \null
% \% `\em An array of five forks'
% def forks = {array (1,5)
%              | [j] = limited_resource 1 || j <- 1 to 5 } ;
% \null
% def ticket = limited_resource 4 ;
% \null
% def philosopher j = {while true do
%                          cogitate
%                         THEN take ticket
%                         THEN L = take forks[left  j] ;
%                              R = take forks[right j]
%                         THEN ingest L R         
%                         THEN return forks[left  j] ;
%                              return forks[right j]
%                         THEN return ticket} ;
% \endid

% \caption{The Dining Philosophers}
% \label{phil}
% \end{figure}

% The managers for the forks and refectory are special cases of a limited
% resource, which corresponds to a semaphore.\footnote{Although the manager
% definition is given here, semaphores are a degenerate case of a locked data
% cell, which has hardware support.  Such cells (described in the next section)
% could be directly used here.} Each philosopher is an infinite process that
% requests a ticket and access to his forks ({\cf left} and {\cf right} compute
% suitable indices).  After eating, the forks are relinquished and the
% philosopher leaves and returns to thinking.  The {\cf THEN} construct
% synchronizes these actions by delaying an operation until all the previous
% operations have finished.  The processes are initialized by calling the {\cf
% philosopher} function on the seat numbers, one through five.

        
\subsubsection{Composition} 

Individual managers can support a wide range of programs.
However, many applications may require several managers working
in concert.  The treatment of managers as first-class objects
allows networks of managers to be defined using standard
data structures such as lists and arrays.
Furthermore,  composition supports abstraction and
modularity, which is of particular importance to managers since, unlike
functions, the properties of a network of managers cannot be easily
determined by the properties of its members.

For example, consider a priority queue as defined in CACM.
Recursive structure yet releases locks early.
Shorter, simpler algorithm than that given.  Excellent efficiency.
No explicit locking.


\begin{figure}[htbp]

\beginid



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

      def_handler alloc ptr:mem_q i = mem_q,ptr
        |         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 ptr i =
	if i==MAXINDEX then	% no coalescing last element
	  (ptr:mem_q),ack
	else
          if (free_buddy? ptr) then
            {big_block = (coalesce ptr i);  % join memory and deallocate
	     In
	       mem_q,(dealloc memory[i+1] big_block (i+1))}
          else (ptr:mem_q),ack
       };

\endid

\caption{The Parallel Priority Queue}
\label{psched}
\end{figure}

Also union-find, print scheduler, memory manager.


\subsection{Programming Paradigms}

When programming systems that share resources, maintaining invariants
is central to determining correct execution.  One invariant that managers
provide is mutual exclusion on the state variable.  However, when managers
are composed, other invariants over the composition are desirable.
Several types of invariants can be established by controlling the
separate, parallel computations of the manager's new state and result.
Coarse control, corresponding to weak invariants, can be introduced
through mailboxes, which defer a computation.  The table below illustrates
the invariants introduced by deferring the state and result computations:


\begin{figure}[htbp]

\begin{tabular}{|c|c|c|c|}\hline
State & Result & Invariant after Request & Examples \\ \hline
Immediate & Immediate & Mutual Exclusion, Update Performed & Bank Account \\
Immediate & Deferred  & State Available & Nice Bank, Priority Schedulers \\
Deferred  & Immediate & State Locked & Rendezvous \\
Deferred  & Deferred  & Deadlock &\\\hline
\end{tabular}

\caption{Invariants for a Single Manager}
\label{Inv1}
\end{figure}


It should be noted that the first of these conditions, where the state and result are 
immediately computed, has interesting invariants based on the status of the state variable
when the result is returned.  These invariants allow a caller to a manager to use the
result to synchronize actions.  Within the bounds of mutual exclusion, three sub-cases
can occur:

\begin{figure}[htbp]

\begin{tabular}{|c|c|c|c|}\hline
State when  Result is Returned & Invariant & Examples \\ \hline
Waiting for Lock & State not Affected & Notification \\
Locked & State Being Computed & Serialized Requests \\
Updated and Unlocked  & State Updated & Serialized Requests \\\hline
\end{tabular}

\caption{Invariants Based on State Update}
\label{Inv2}
\end{figure}

In the first case, the lock has not been acquired when a result is
returned.  This yields no serialization information: a successive
manager call may acquire the state variable before this call acquires
and updates it (we are not assuming fifo).  This is useful for
calls to notify a manager of an event, where notification order
is unimportant;  it allows the caller to proceed without waiting
for the lock.

In the second case the lock has been acquired but not returned; in
the third case, the state has been updated and unlocked.  These two
cases have the same serialization invariant: a successive call to
the manager will necessarily see the effect of the current call.
Clearly the second case exposes more parallelism, and so is preferred.
In fact, additional parallelism exposed by the first case is incidental,
so the second case is always used.  This allows every manager call
to assume the invariant that the state is locked when the result is
returned. 

In a composite manager, the state of a manager may refer to other managers.
In this case, stronger invariants over the composite can be introduced by 
recursive manager calls.  Specifically, how the new state is computed by
recursive manager calls determines the invariant.

\begin{figure}[htbp]

\begin{tabular}{|c|c|c|c|}\hline
State & Result & Invariant after Request & Examples \\ \hline
Recursive & Immediate & State Locked Until Next Lock Taken & Parallel Priority Queue \\
Recursive & Recursive & State Locked Until All Locks Taken & Buddy System, Union Find \\\hline
\end{tabular}

\caption{Invariants for Recursive Managers}
\label{Inv3}
\end{figure}


\subsection{Summary}

Managers meet our goal of encapsulation.  The state variable and its
associated operations are defined in a single construct.  The external
interface to a manager is clearly defined by the request handlers, which
can be written as as state transition functions.  Further, the state
variable is completely hidden from the interface.  This interface
defines the scope of the nondeterminism in the program: any function
calling a request handler (or another nondeterministic procedure) is
potentially nondeterministic.

Managers also meet our goal of expressiveness.
Mailboxes allow requests to be deferred and reordered
with the addition of simple queuing operations.
Managers can be composed into networks of asynchronous
processes in an abstract and modular way.
The treatment of managers and mailboxes as first-class objects
increases their flexibility.  

It is important to note that managers employ nonstrict execution to realize
this expressiveness.  Request handlers compute the new state and response
independently;  nonstrictness allows them to be returned asynchronously.
This means that the state can be returned (and therefore relinquished for
other requests) before the response is computed.  Naturally, this supports
scheduling, where responses are deferred until some future request.
However, this generalizes to support mutually and self recursive managers.
Since the state is returned immediately, the response may be determined by
another request of the same manager.  The state will be available to the new
request, so deadlock will not result.  This differs from most abstractions
supporting mutual exclusion, such as monitors\cite{Monitors} and critical
sections\cite{BrinchHansen}.  Of course, request handlers must not use the
manager recursively while computing the new state.  The mutual exclusion
guarantee on the state variable would produce deadlock in this case.


Managers also meet our goal of efficiency, as described in the next section.

