% File:    pthreads.tex
% Author:  Florian Matthes
% Date:    19-MAY-1994 
% Purpose: Paper on Persistent Threads

\documentstyle[xple_sl,epsf]{clmult01}

\pagestyle{myheadings}

\def\descriptionlabel#1{\hspace\labelsep \bf #1\hfil}

% -- Macros:
\newcommand{\figsep}{\noindent\rule{\textwidth}{0.5pt}}
\newcommand{\e}[1]{{\em #1\/}}
\newcommand{\p}[1]{{\sl{}#1}}
\newcommand{\k}[1]{{\bf{}#1}}
\newcommand{\R}{$\Rightarrow$}
\newcommand{\r}{$\rightarrow$}
\newcommand{\comment}[1]{ [[ #1 ]] }

\title{Chapter 1.5.2\\Persistent Threads}

\author{Florian Matthes \and Joachim~W.~Schmidt}

\institute{Technical University Hamburg-Harburg\\Harburger Schlo{\ss}stra{\ss}e 20\\D-21071 Hamburg, Germany}

\begin{document}

\authorrunning{Florian~Matthes \and Joachim~W.~Schmidt}
\titlerunning{Persistent Threads}

\maketitle

\abstract{This text is a synopsis of \cite{MaSc94}.}

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

\section{Introduction}
\label{Sec:Intro}

A noticeable trend in database research and database system development
is an increased interest in behavioural and procedural aspects of
information systems.  Data models that describe dynamic processes in
addition to static data structures are capable of capturing more of the
application semantics as exemplified by object-oriented models like
Taxis, ADAPLEX, Galileo or Fibonacci.  Similarly, database systems that
support procedures, methods, rules or triggers in addition to persistent
data values are capable of factoring-out procedural code from individual
application programs into shared databases. 

In this paper we focus on the intricate binding issues on the borderline 
between ``active code'' and ``passive data'' that arise in persistent 
object systems as soon as one gives up the classical separation between 
short-lived transactions expressed in a host language and long-lived data 
stored in a database.  More specifically, we provide a classification 
scheme for bindings from code to persistent data and vice versa and we 
investigate bindings from persistent data and code to threads, which 
exhibit an interesting duality.  On the one hand, threads can be viewed 
as activities that can be created, executed, synchronized, suspended, 
terminated, etc.  Alternatively, they can be viewed as passive data that 
can be stored persistently, annotated with attributes, associated with 
other persistent data structures, moved between nodes in a network, and 
manipulated by computations.

This duality makes persistent threads a key technology for future
persistent object systems and for applications that manage long-term,
distributed or cooperative activities like computer-aided design,
workgroup communication and workflow management.  Unfortunately, this
duality also invalidates many design assumptions on which today's
volatile thread implementations are based.  Therefore, we also discuss
in some detail implementation aspects of persistent thread bindings.

The specific persistent thread model presented here has been developed
within the context of the persistent programming environment
Tycoon \cite{MaSc93b,Matt93} (see Chapter 2.1.4) where it serves as an abstract
model to shield programmers and application-oriented tools from details
of the underlying system implementation (object store, database language
evaluator, scheduler, recovery subsystem) while being sufficiently
low-level to support a variety of (possibly application-defined)
scheduling and activity management strategies.

\section{Bindings in persistent systems}
\label{Sec:Bindings}

A binding is an association between a name and a computational entity
from a specific semantic domain.  We also say that a name
is bound to a computational entity.  Different names can be bound to the same entity
(sharing, aliasing).
Entities can be flat (like records) or nested (like functions in
Algol-like languages).   As is shown in the full paper, the semantics of bindings from and to
(dynamically) nested entities requires particular attention.

Entities can be transient (like local program variables) or persistent
(like database tables).  Virtually all database systems restrict persistent entities to contain only bindings to other
persistent entities since bindings to volatile entities would lead to
``dangling references''.  Such constraint violations are avoided in many
systems by a transitive reachability rule: Every entity reachable from a
persistent entity becomes persistent, too.  In reachability-based
systems, there is a so-called ``persistent root''. 
 An entity is made persistent by making it reachable
through chains of bindings (e.g., database definition, class extent)
starting from this persistent root.

\begin{figure*}
\begin{center}
\begin{tabular}{|l|l|l|}
\hline
\k{Conceptual Model} & \k{Language Model} & \k{Implementation Model} \\
\hline
entity               & variable         & data      \\
behaviour             & function         & code      \\ 
activity             & continuation     & thread    \\
\hline
relationship         & name             & binding   \\
\hline
\end{tabular}
\end{center}
\caption{Corresponding notions at different levels of conceptualization}
\label{Fig:Notions}
\end{figure*}

\noindent
The following three categories of structured entities are of particular 
interest in extended (higher-order) database modelling (see Fig.~\ref{Fig:Notions}): 

\k{Persistent Data (D)} describe the persistent state of an information 
system by a collection of computational entities related through bindings.  
The structure (types) of the persistent entities and their bindings are 
described by a database schema.

% changed paragraph
\k{Code (C)} is a description of operation sequences that query and update 
volatile or persistent entities and bindings.
Code involves names to describe bindings to other code, bindings to persistent data, and bindings to volatile data. 

A \k{Thread (T)} is a representation of code \e{in the process of being
executed}.  A thread describes a single sequential flow of control in a
program.  Having multiple threads in a program means that at any instant
the program has multiple points of execution, one in each of its
threads.  Unlike operating system processes, multiple threads can
execute within a single (persistent) address space, permitting multiple
threads to access shared variables in addition to local variables.

% changed para
A thread is created by submitting a parameterless code fragment and (persistent) data to an evaluator.  The semantics of the evaluator
can be defined inductively by rules that map thread states to thread
states and that perform side-effects on data.  A thread state subsumes
bindings to the code fragments currently being executed and a dynamic
environment that records the current bindings from names occurring in
the code to local and global entities.  


Since entities of each of the three categories above -- data, code and 
threads -- may contain bindings, there are nine possible binding patterns 
between computational entities in fully orthogonal object systems.  In 
the full paper we list the binding patterns which we 
regard as ``historic'' milestones in the development of persistent system 
models.We review briefly the evolution of database languages in 
terms of their binding patterns.  We argue that the expressiveness and 
usability of a database system model is related directly to the 
orthogonality of its binding patterns and that, in retrospect, many ad-hoc 
binding restrictions found in database systems are simply based on the 
choice of an improper implementation technology.

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

\section{Programming with persistent threads}
\label{Sec:Activity}

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.

%\subsection{Threads in persistent systems}

%changed
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 (see Chapter 1.1.3) 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}\small%
  \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("; end") \k{end}
\end{xple}
%
\noindent
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; end}. 


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

We illustrate how threads fit as first-class
computational entities into the persistent object system Tycoon.
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.

A thread 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.
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.

% changed
The definition of persistence has to be revised because first-class threads are generalized from volatile to persistent.  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.


%\subsection{Activity-oriented Programming}
%\label{Sec:Programming}

\noindent
Having threads as computational entities in a database language,
programmers can benefit from the potential of multi-threaded programming
\cite{Nels91}. 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 modelling as promoted by
scripts, by process-centered specifications, or by (visual) process languages of
work flow management tools. The full paper shows a programming example using the Tycoon Language (see Chapter 1.1.1) that exploits persistent threads.

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

\section{On thread implementation and formalization}
\label{Sec:Semantics}

Several important requirements on persistent thread implementations
differ substantially from volatile thread implementations, for example:

\begin{itemize}

\item Thread state representations have to be made relocatable and
portable in the sense that states need to be abstractly interpretable
without reference to a specific machine architecture (e.g., SPARC
register files).

\item It is desirable to have automatic garbage collection that reclaims the 
storage of terminated or orphaned threads.

\item It is necessary to formalize in sufficient detail the effects of thread
execution on shared entities in the persistent store, in particular, if
these entities have a complex structure. Only then reliable support can
be provided for concurrency, recovery, or garbage collection.

\item Store access in distributed persistent memory has different 
performance characteristics than store access in centralized
shared-memory architectures.
 

\end{itemize}
%
% changed
In the full paper we first report on our implementation of persistent
threads.  We then sketch
thread formalization with a clear emphasis on abstract representations
of machine code (Tycoon Machine Language, TML, see Chapter 2.3.5), machine states and on
explicit modelling of machine-store interactions (Tycoon Store Protocol,
TSP, see Chapter 2.2.4). A complete definition of the Tycoon thread evaluation semantics is given in \cite{Matt93}.

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

\section{Concluding remarks}

It should be noted that persistent threads are an expressive
and efficient, but rather low-level concept for the management of
cooperative activities.  Therefore, we are currently investigating
related database synchronization and communication models that have been
proposed in the literature \cite{GMS87,Reut89,BDSSW93} and how such
models can be realized as polymorphic libraries encapsulating Tycoon's
persistent threads.  This approach to a flexible
reconciliation of system and user needs has proved to be highly
successful in modern programming and operating environments which
offer several higher-level models like monitors, ACID transactions,
transactional RPCs and communicating processes on a common, standardized
thread abstraction available on multiple system platforms.

\begin{acknowledgement}
This research is supported by ESPRIT Basic Research, Project FIDE,
\#6309 and by a grant from the German Israeli Foundation for Research
and Development (\e{bulk data classification}, I-183 060).
\end{acknowledgement}


\small
\bibliographystyle{plain}
\bibliography{../dbis-macros,../florian}

\end{document}
