% File:    sect4.tex
% Author:  Florian Matthes
% Date:    23-FEB-1994 
% Purpose: Paper on Persistent Threads

\section{Activity-oriented programming with persistent threads}
\label{Sec:Activity}

Based on the discussion of the previous section we propose a next step
in the evolution of database languages by introducing the concept of
first-class bindings to threads.  The concept of threads (continuations,
sessions, running transactions) is either non-existent or only
implicitly available in today's database systems.  We argue that an
explicit and orthogonal handling of threads naturally leads to the
concept of persistent threads, a systems abstraction suitable for novel
high-level models for long-term activity management.

In a nutshell, we propose to repeat the successful ``trick'' of
object-oriented DBMSs, namely to adapt an existing, well-understood
programming language concept to the specific requirements of long-lived
data-intensive applications and to develop its supporting system
technology based on clean semantic foundations.


\subsection{Threads in persistent systems}

As mentioned in section~\ref{Sec:Bindings} (see also
figure~\ref{Fig:Patterns}), threads and T{\r}C bindings already exist
implicitly in transactional multi-user DBMSs.  For example, running
transactions in a DBMS correspond to isolated threads (bound to
transaction code) that are activated, suspended or aborted under the
control of a centralized scheduling ``master thread'' that gains control
whenever these threads access shared database entities.  On an
implementation-level, a transaction descriptor in the scheduling
subsystem is a record that aggregates bindings to a (suspended or
running) thread with additional information relevant for synchronization
purposes, like the shared (read-only) bindings and the exclusive
(updated) bindings held by the thread, bindings to other threads waiting
for resources of this thread, or the cost of the operations executed by
the thread so far.  Database systems (like Ingres) that support named
checkpoints inside transactions provide an additional mechanism to store
multiple ``frozen'' thread states that can be reactivated at the user's
discretion.

Novel transaction models (see, e.g., \cite{BaKa91,GrRe93}) propose to
give ``power users'' the ability to extend the semantics of the ``master
thread'' by introducing additional scheduling concepts like lock modes
and by triggering the execution of user-defined code fragments whenever
two threads access a shared persistent object concurrently.  This code
can use an algorithmically-complete language to decide when to abort,
suspend or notify the conflicting threads.

While threads managed by a DBMS scheduler are volatile (they are limited
to the lifetime of their corresponding operating system processes), a
limited form of persistent threads can be found in the (single-user)
persistent higher-order systems Napier88 \cite{DCBM89} and PQuest
\cite{MMS92} that have an atomic \p{stabilize} operation.  This
operation can be called anywhere inside a program to define a consistent
persistent system state.  This state not only consists of the global
database state variables but also includes the state of the program
evaluator.  If a system crash occurs during program execution, the
execution can be resumed in the state valid at the last \p{stabilize}
operation.

\begin{xple}
\k{procedure} p(x:Int) = \k{begin} stabilize(), print("leave p, x=", x) \k{end}
\k{procedure} main() = \k{begin} print("call p"), p(3), print("; return from p") \k{end}
\end{xple}

For example, assuming that during the execution of \p{main} the system 
crashes after returning from \p{p}. On system restart, program execution 
would resume with the first statement after the \p{stabilize} operation, 
and the output would be \p{leave p, x=3; return from p}. 

To summarize, these systems already have a hidden persistent thread 
functionality that is, however, severely limited to a single top level thread.

\subsection{Threads as first-class persistent entities}
\label{Sec:FC-Bindings}

In this section we illustrate how threads fit as first-class
computational entities into persistent object systems. Our presentation
is based on the thread abstraction available in the Tycoon system, a
polymorphic persistent programming environment developed in the FIDE
project by our group at Hamburg University \cite{MaSc93b,Matt93}.

In Tycoon, computational entities (data, code, threads) are either bound
in the scope of individual programs or in the scope of persistent
modules.  The execution of a Tycoon program code \p{c} invoked from an
operating-system shell leads to the creation and execution of a Tycoon
thread bound to \p{c} in an initial environment that contains C{\r}D
bindings from all module names imported by \p{c} to corresponding linked
persistent module values.

Users or applications at the operating-system level can create
independent Tycoon threads running against a shared set of persistent
modules.  Conceptually, the computational entities of all Tycoon threads
and modules reside in a common persistent object store.  This seamless
integration of volatile and persistent store simplifies the access to
databases represented as persistent modules.  Furthermore, it
facilitates the exchange of data, code and threads between threads via
shared variables.  These variables are bound in the scope of persistent
modules and are typically protected by synchronization mechanisms like
transactional locks, semaphores, monitors, or message queues.

The following simplified excerpt of the Tycoon system library interface 
\p{Thread} defines the basic functionality of a corresponding module
\p{thread} which exports a parameterized abstract data type \p{thread.T}
and operations to inspect, create and execute multiple threads from
within Tycoon programs.

\newcommand{\cmm}[1]{{\rm(* #1 *)}}

{\small
\begin{xple}\k{interface} Thread \k{export}
   T(R $<$:\k{Ok}) $<$:\k{Ok}
       \cmm{T(R) is the type of threads that on termination return values of type R.}
   \k{Let} State = \k{Tuple case} suspended, running, terminated, aborted, blocked \k{end}
      \cmm{An enumeration type that describes the possible thread states.}
   new(I,R $<$:\k{Ok}  code :\k{Fun}(:I):R  input :I) :T(R)
      \cmm{Return a new, suspended thread to execute \p{code(input)}.}
   self(R $<$:\k{Ok}) :T(R)
      \cmm{Return a descriptor for the thread that executes \p{thread.self()}.}
   copy(R $<$:\k{Ok}  thread :T(R)) :T(R)
      \cmm{Return a shallow copy of \p{thread}. The execution of thread does not affect \p{copy(thread)}.
          However, entities bound in the code executed by \p{thread} and \p{copy(thread)} are shared.}
   run(R $<$:\k{Ok}  thread :T(R)) :\k{Ok}
      \cmm{If \p{thread} is suspended then resume execution until execution terminates,  aborts with
         an exception, is suspended or blocked. \p{thread} and \p{self()} execute concurrently.}
   state(R $<$:\k{Ok}  thread :T(R)) :State
      \cmm{Return the state of \p{thread} that may change dynamically if \p{running} or \p{suspended}.}
   join(R $<$:\k{Ok} thread :T(R)) :R
      \cmm{Block until \p{thread} terminates or aborts. Return the result or propagate its exception.}
\k{end}\end{xple}
}

The module \p{thread} encapsulates the representation of threads, the
semantics of the Tycoon evaluator (\p{thread.run}, see
section~\ref{Sec:Semantics}) and the details of the mapping from threads
to physical processing units.  Since some versions of the Tycoon system
are based on persistent object stores which allow multiple workstations
to access a Tycoon object store concurrently, multiple physical
processing units (workstations) may be involved in thread
execution.\footnote{Currently, a call \p{thread.run(:R t)} executes
\p{t} and \p{self()} on the same processing unit.}

The type \p{thread.T} and all functions exported from the interface
above are polymorphic, i.e. they have an explicit type parameter \p{R}
that has to be instantiated with a subtype of the trivial ``top type''
\k{Ok} \cite{MaSc92a}. Threads are polymorphic data structures since they 
can describe the execution of code that returns values of an arbitrary
result type \p{R}. This type \p{R} has to match the return type of the
\p{code} function passed as an argument to the \p{thread.new} function. 

As a minimal example of (volatile) thread programming, the following Tycoon 
program creates a thread \p{t} to evaluate the function \p{code} that 
returns a value of type \p{Int}.  This result is computed by adding the 
statically-bound \p{data} value and the dynamically-bound \p{parameter} 
value.

\begin{xple}\k{import} thread :Thread
\k{let} data :Int = 3
\k{let} code(parameter :Int) :Int = data + parameter
\k{let} t :thread.T(Int) = thread.new(:Int :Int code 4)
thread.run(:Int t)
\k{let} result :Int = thread.join(t)   (* $\Rightarrow 7$ *)\end{xple}

Remember that the thread bound to \p{t} is a first-class entity in
Tycoon -- it can be passed as a function argument, returned from a
function, bound to a name in the scope of a persistent module, exported
to a portable data file, or sent across a communication channel.

The generalization of first-class threads from volatile to persistent
has the following semantic implications:

\begin{itemize}

\item The definition of persistence has to be revised.  In addition to all 
persistent modules also all active threads act as ``roots of
persistence''.  Moreover, the transitive reachability rule introduced in
section~\ref{Sec:Bindings} has to be extended to also include T{\r}C,
T{\r}D and T{\r}T bindings.

\item The semantics of the shallow and deep copy operation has to be
extended properly to values of type \p{thread.T}. 

\item In activity-intensive applications, it is desirable to be able to 
attach additional information to thread values (user id, transaction group 
id, access rights, authentication key, parent thread, \ldots).  This 
extensibility is achieved in Tycoon by adding a second type parameter \p{D} 
to the thread signature.  A value of type \p{thread.T(D R)} is a thread 
that computes a value of type \p{R} and that has a descriptor attribute of 
type \p{D}.  Descriptors are exploited heavily by higher-level scheduling 
and activity-management algorithms but can also be made visible to 
application-level code.  \end{itemize}


\subsection{Programming with persistent threads}
\label{Sec:Programming}

Having threads as computational entities in a database language,
programmers can benefit from the potential of multi-threaded programming
\cite{Nels91}, like

\begin{itemize}
\item a better exploitation of existing processing resources (e.g.,
workstation clusters or multi-processor workstations);

\item a better support for multiple activities of human users within a single
application (e.g., a database query tool can process multiple
independent queries);

\item a reduced latency of operations by deferring re-organization tasks
(e.g., an insertion into an index structure returns control to the
caller immediately and spawns a separate thread to perform the index
reorganization if necessary);

\item a better responsiveness of servers in distributed systems by
allocating multiple server threads to handle client requests.
\end{itemize}

By making a thread reachable from persistent data (persistent modules)
and by checkpointing the state of the persistent store it becomes
possible to protect long-running activities from system failures. After a
crash, the thread can be restarted explicitly in the state that was
valid at the last checkpoint.

More importantly, persistent threads support directly an
activity-oriented style of information system modeling as promoted by
scripts in Taxis \cite{BMS93}, by process-centered specifications in
Estelle, Lotos or SDL \cite{Turn93}, or by (visual) process languages of
work flow management tools like Regatta \cite{Swen93}.

As a highly simplified example, a paper submitted to a workshop can be
represented by the following data type that contains a (persistent)
thread attribute:

\begin{xple}\k{Let} Paper = \k{Tuple} title, authors, abstract, text :String
     reviewer :Person  rating :Rating  refereeActivity :thread.T(\k{Ok})
\k{end}\end{xple}

From the viewpoint of the PC chair, each paper has to be reviewed
individually, and the set of submitted papers has to undergo the
following reviewing activity.


\begin{xple}\k{for each} p \k{in} db.submittedPapers \k{do}
    p.refereeActivity:= thread.new(:Paper :\k{Ok} reviewPaper p)
    thread.run(:\k{Ok} p.refereeActivity)
\k{end}
joinAll(\k{select} p.refereeActivity \k{of each} p \k{in} db.submittedPapers)
\end{xple}

Reviewing the set of all submitted papers is modeled by creating and
executing one \p{p.refereeActivity} per paper \p{p} which can then run
concurrently without interference.  Standard query language notations
can be used to perform bulk operations on sets of threads, for example,
to wait until all threads attached to \p{db.submittedPapers} have
terminated. The user-defined function \p{joinAll} takes a sets of
threads and blocks the current thread until all of the threads have
terminated.

\begin{xple}\k{let} joinAll(threads :set.T(thread.T(\k{Ok}))) :\k{Ok} =
   \k{for each} t \k{in} threads \k{do} thread.join(:\k{Ok} t)
\k{end}\end{xple}

The activity of individual reviewer assignment and review recording is
modeled by the following code:

\begin{xple}\k{let} reviewPaper(p :Paper) :\k{Ok} = \k{begin}
      \k{repeat} p.reviewer:= chooseReviewer(availableReviewers)
      \k{until} acceptedByReviewer(p.reviewer p)
      sendPaperToReviewer(p.reviewer p)
      \k{try} p.rating:= waitForReview(p.reviewer)
      \k{when} reviewerNotAvailableException \k{then} reviewPaper(p)
      \k{end}
\k{end}\end{xple}

Contrary to current database practice, the progress of the reviewing
process is not captured by a passive relational table that stores a
\p{state} attribute for each paper which is then updated by separate
transactions to values like \p{unassigned, assigned, sentOut, returned,
\ldots}. Instead of this, an activity- and goal-oriented script modeled by
database language code describes directly the possible states and state
transitions. This example makes use of several control structures (loop,
recursion, exception handling) for sequential activities and uses thread
for long-term concurrent activites. Note that the thread above depends
crucially on global bindings (to parameter values, global data, and
global code).

In this example, thread synchronization has to be employed to coordinate
parallel activities (the assignment of reviewers to individual papers
that implies access to the shared variable
\p{availableReviewers}) and to wait for the termination of
subactivities.

Persistent threads do not lead necessarily to an imperative,
deterministic style of activity management. Instead of this,
higher-level activity models can be supported directly by factoring-out
synchronization tasks (\p{parallelDo, tryOneOf, atomicDo,
compensatingDo}) from applications into higher-order thread libraries.
