\section{A best effort real-time service}
\label{sec:best_effort_rt}

To meet the responsiveness goals required by our model of interactive
applications (Section~\ref{sec:app_model}) on the kinds of common
computing environments encompassed by our machine model
(Section~\ref{sec:mach_model}), we propose to build a best effort real
time service that will let the application programmer place upper and
lower bounds (deadlines) on the execution time of an activation tree
rooted at a particular procedure call.  The form of this service will
be the \MAP primitive
\begin{center}
\MAP \texttt{procedure(inargs, outargs, inoutargs, state)} 
      \IN $[t_{min},t_{max}]$
\end{center}
which attempts to execute the activation tree rooted at the call to
\verb.procedure. such that it completes within $t_{max}$ seconds but
no sooner than $t_{min}$ seconds.  For interactive applications, the
call to the message handler would be performed using the \MAP
primitive.  Together, the upper and lower bounds serve as a way of
expressing a human perceptual range where broaching the bounds leads
to noticeably different delays.  For periodic mappings, the two bounds
also serve as a way to specify a jitter constraint.  

The service will attempt to achieve the upper and lower bounds by
dynamically mapping the nodes of the unfolding activation tree to the
hosts of the computing environment.  The activation tree is executed
sequentially, and when mapping a particular node, only the prior nodes
in the depth-first traversal of the tree and the structure they form
are known.  The successor nodes in the traversal and the overall
structure of the tree are unknown when mapping a given node.
Similarly, when mapping a node, the past behavior of the hosts and
network are known, but the future behavior is unknown.  It is the
service's job to succeed in meeting the bounds in the face of this
uncertainty.  In essence, the service will make use of the freedom it
has in choosing which host shall execute a node to ameliorate the
uncertainty it faces from the application and the computing
environment.

The remainder of this section describes the assumptions we make about
activation tree structures, what the bounds in the \MAP primitive
mean, and a simple model for the execution time of an activation tree
node.

\subsection{Assumptions}

We assume finite-size activation trees which are traversed in a
strictly depth-first manner - each node returns only to its parent.
In particular, this means that setjmp/longjump and exception-handling
mechanisms that behave in similar ways are not permitted.  Further,
each call (node) must be expressible in terms of data movement to the
selected call site, local execution on this data, which may include
further calls, and data movement away from the call site.  Data
movement includes not just the arguments to the call, but also any
static data or object state that the call will read or modify.
However, any call that requires access to data that may change due
external forces, such as C volatile variables, cannot be mapped. 

\subsection{Bounds}

At time $t_{now}$, executing 
\begin{center}
\MAP \verb.procedure(inargs,outargs,inoutargs,state). 
   \IN $[t_{min},t_{max}]$
\end{center}
begins a dynamic mapping process which attempts to execute the
activation tree rooted at \verb.procedure. such that the tree finishes
after $t_{min}$ seconds from $t_{now}$ and before $t_{max}$ seconds
from $t_{now}$.  $t_{now} + t_{min}$ is the ``later'' time - execution
should not complete before this time, while $t_{now}+ t_{max}$ is the
``sooner'' time - execution should complete before this time.  This is
illustrated in Figure~\ref{fig:timingconstraints}.

\begin{figure}
\epsfxsize=4in
\centerline{
\epsfbox{timing_constraints.epsf}
}
\caption{Upper and lower bounds.}
\label{fig:timingconstraints}
\end{figure}

\subsection{Node execution time model}
\label{sec:node_exec_model}

The execution time of an activation tree is the execution time of its
root node.  This section describes our model for the execution time of
a node, including the overheads associated with remote execution and
our best effort real time service.  Figure~\ref{fig:exectimenode}
graphically summarizes the discussion in this section.

The time to execute an activation tree node, $t_{exec}$, is the time to
execute the subtree rooted at the node and consists of the time to map
the node ($t_{map}$), transfer data to the host it will execute on
($t_{incomm}$), actually compute the node and its children
($t_{compute}$), transfer data back to the caller ($t_{outcomm}$), and
update the mapping algorithm ($t_{update}$).  If the node meets its
deadline, there is a slack time, $t_{slack}$, before the upper bound.

\begin{figure}
\epsfxsize=4in
\centerline{
\epsfbox{exec_time_node.epsf}
}
\caption{The execution time of an activation tree node.}
\label{fig:exectimenode}
\end{figure}

%\begin{figure}
%\epsfxsize=4in
%\centerline{
%\epsfbox{exec_time_leaf.epsf}
%}
%\caption{The execution time of an activation tree leaf node}
%\label{fig:exectimeleafnode}
%\end{figure}
 
Notice that this is a recursive definition, since we include the
execution time of each of a node's children in its execution time.
As indicated in Figure~\ref{fig:exectimenode}, a node's computation
time, $t_{compute}$, consists of alternating local computation and
execution of child nodes.  The sum of local computation times is
$t_{computelocal}$ and the sum of child node execution times is
$t_{execchildren}$.  Each child node execution time is modeled
precisely as its parent's.  For a leaf node, there is only local
computation, so $t_{compute} = t_{computelocal}$.