Chapter 1.5.2 Persistent Threads

Florian Matthes and Joachim W. Schmidt

Technical University Hamburg-Harburg Harburger Schloßstraße 20 D-21071 Hamburg, Germany

Summary This text is a synopsis of [6].

1. Introduction

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 objectoriented 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 [5, 3] (see Chapter 2.1.4) where it serves as an abstract model to shield programmers and applicationoriented 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.

Florian Matthes, Joachim W. Schmidt

2. Bindings in persistent systems

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.

Conceptual Model Language Model Implementation Model
entity  variable  data
behaviour  function  code
activity  continuation  thread
relationship  name  binding

Fig. 2.1. Corresponding notions at different levels of conceptualization

The following three categories of structured entities are of particular interest in extended (higher-order) database modelling (see Fig. 2.1):

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.

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 Thread (T) is a representation of code 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.

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.

Persistent Threads

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.

3. Programming with persistent threads

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.

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 [4] that have an atomic 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 stabilize operation.

procedure p(x:Int) = begin stabilize(), print(”leave p, x=”, x) end procedure main() = begin print(”call p”), p(3), print(”; end”) end

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

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 c invoked from an operatingsystem shell leads to the creation and execution of a Tycoon thread bound to c in an initial environment that contains C→D bindings from all module names imported by 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.

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 2 has to be extended to also include T→C, T→D and T→T bindings. Having threads as computational entities in a database language, programmers can benefit from the potential of multi-threaded programming [7]. 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.

4. On thread implementation and formalization

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

– 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).

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

– 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.

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

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 [3].

5. 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 [2, 8, 1] 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.

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 (bulk data classification, I-183 060).

References

1. Y. Breibart, A. Deacon, H.-J. Schek, A. Sheth, and G. Weikum. Merging application-centric and data-centric approaches to support transaction-oriented multi-system workflows. ACM SIGMOD Record, 12(3):23–30, September 1993.

2. H. Garcia-Molina and K. Salem. Sagas. In Proceedings of the ACM-SIGMOD International Conference on Management of Data, San Francisco, California, pages 249–259, May 1987.

3. F. Matthes. Persistente Objektsysteme: Integrierte Datenbankentwicklung und Programmerstellung. Springer-Verlag, 1993. (In German).

4. F. Matthes, R. Müller, and J.W. Schmidt. Object stores as servers in persistent programming environments – the P-Quest experience. FIDE Technical Report Series FIDE/92/48, FIDE Project Coordinator, Department of Computing Sciences, University of Glasgow, Glasgow G128QQ, July 1992.

5. F. Matthes and J.W. Schmidt. System construction in the Tycoon environment: Architectures, interfaces and gateways. In P.P. Spies, editor, Proceedings of Euro-Arch’93 Congress, pages 301–317. Springer-Verlag, October 1993.

6. F. Matthes and J.W. Schmidt. Persistent threads. In Proceedings of the Twentieth International Conference on Very Large Data Bases, VLDB, pages 403–414, Santiago, Chile, September 1994.

7. G. Nelson, editor. Systems programming with Modula-3. Series in innovative technology. Prentice Hall, Englewood Cliffs, New Jersey, 1991.

8. A. Reuter. ConTracts: A means for extending control beyond transaction boundaries. In Third International Workshop on High Performance Transaction Systems, 1989.