Concurrent Programming In Java
© 1996 Doug Lea

Readings And Resources

Java

Other books in the Addison-Wesley Java Series describe Java programming techniques and the use of standard Java packages. The Java Language Specification should be consulted for the definitive, guaranteed semantics of Java, including those surrounding the properties of concurrency constructs summarized in this chapter. See:

Concurrent programming

Most applications and systems are concurrent in many senses. For example, a multithreaded Java program may be running concurrently with several other programs on a multitasking workstation. This book is not concerned with operating-system multitasking or other forms of concurrency that fall outside issues traditionally associated with concurrent programming: the use of constructs that allow multiple activities to execute within a single program running on a general-purpose computer -- not necessarily or even typically a parallel computer. While other aspects of concurrency are mentioned here and there, complete coverage falls outside the scope of this book. Some starting points for learning more about them are listed below.

Also, even though effective concurrent programming often requires a bit more rigor than is typical of everyday sequential programming, this book does not focus on theory or formalisms underlying concurrent and/or object-oriented programming. However, especially if you do a lot of concurrent programming or push hard on some of the more subtle constructions described in this book, you'll eventually want to find out more about these things by reading some of the listed sources.

Concurrent and OO programming have about equally long histories, going back to the 1960s. Hardly any of the designs presented in this book are very new (which is why many are organized around patterns -- recurring problems and solutions). On the other hand, many of the details of how to approach and implement them in Java are a bit novel. In some cases, particulars of the Java programming language lead to substantial differences between Java versions of design patterns and versions in other languages. For example, some constructions described here as patterns requiring particular combinations of Java mechanics are single built-in constructs in other languages, and vice versa. Keep this in mind when reading other sources on concurrent programming. Accounts of concurrency so often focus on isolated smart procedures operating on isolated dumb data that it is sometimes hard to see how the same ideas apply to object-oriented designs in general or Java in particular.

The standard general-purpose reference-quality text on most aspects of (non-object-oriented) concurrent programming is:

It presents several algorithms (for example, deadlock detection) mentioned but not described in this book. Other useful texts on concurrency include:

Attempts to control the intrinsic complexity of cooperative design problems underlie a large fraction of special-purpose algorithms described in the technical literature on concurrency. Texts and technical papers on concurrency often discuss notification-based solutions to textbook examples, for example the famous Dining Philosopher problem. Even if you never employ them directly, reading about different special-purpose notification design patterns for textbook problems can give you ideas about how to attack real problems.

Java waiting and notification constructs are derived from monitors , first described by C. A. R. Hoare. See

A survey of monitor policies and usage may be found in:

WWW starting points on general concurrency issues include:

Programming languages

Java is by no means the first OO language to support concurrency. In fact, the first concurrent OO language, Simula, was also the first OO language (circa 1966). Simula contained constructs that were more primitive than those found in Java. For example, concurrency was based around coroutines (thread-like constructs requiring that programmers explicitly hand off control from one task to another). But Java is closer to Simula than it is to many other OO languages. Java concurrency constructs (as well as several other features) also resemble those in Modula-3, Mesa, and Euclid. More information about these and other concurrent OO languages can be found in:

The object-oriented language Self is among the few that directly support a pure delegation style of programming without requiring explicit message forwarding. See:

More general accounts of reflection and meta-level programming can be found in books on Lisp, Scheme and CLOS (the Common Lisp Object System); for example:

SOM is an example of a framework that automates message representation and encoding chores in a way that simplifies definition and manipulation of meta-object methods. See:

Linda is an example of an entire programming framework based on a particular flow model built upon buffers serving as tuple spaces. See:

Threads

Most books, articles, and manuals on using threads concentrate on the details of implementations available on particular operating systems or thread packages. For example:

WWW starting points on thread-related topics include:

Most texts on operating systems and systems programming describe the construction of underlying support mechanisms for language-level thread and synchronization constructs. See, for example:

Most of these texts not only present in-depth accounts of different scheduling algorithms, but also present analytic and/or empirical characterizations of their behavior (for example, average throughput under various loads and kinds of tasks).

Parallelism

Parallel programming is concerned with techniques that improve efficiency by exploiting multiple CPUs, normally CPUs connected according to particular parallel machine architectures (for example, a hypercube). Parallel software design focuses more on parallelizing not-obviously-parallel problems, while concurrent software design focuses more on coping with intrinsic concurrency. This book occasionally addresses designs that make most sense in multi-CPU environments. But it does not explicitly deal with algorithms devised solely for use on particular configurations of parallel processors, or consider how to map out the placement of different processes on different processors. These issues are discussed in such sources as:

WWW starting points on parallel processing include:

Javar is an experimental tool for automatically parallelizing java programs.

Distribution

Distributed programming is concerned with communication among different self-standing programs and processes, usually residing on different machines. Distribution and concurrency have much in common. Many Java programs display some of each, and frameworks such as Java Remote Method Invocation (RMI) can make the differences between them seem even smaller. However, this book addresses only single-process Java concurrency. It includes designs that can make the use of distribution tools and packages possible, but not those explicitly using or supporting them. In particular, even though concurrency is often associated with network programming, this book does not describe designs based around Java network support classes such as Socket or other special-purpose networking packages.

In some ways, the kinds of concurrency seen in distributed programming are simpler to deal with than those seen in concurrent programming. For example each node in a distributed system is already an active process, so you do not always need to start new threads when sending asynchronous messages. On the other hand, distribution introduces new issues of its own -- naming, routing, message encoding and transport, security, persistence, crash recovery, fault tolerance, migration, lack of centralized control, and reliance on special infrastructure support. These have little to do with single-process concurrency, and require more extensive treatment than the fleeting discussions scattered throughout this book. General-purpose texts on distribution include:

For some forward-looking presentations and analyses of protocols among distributed objects, see:

WWW starting points on distributed systems include:

Distributed languages and tools

Distributed OO programming languages, tools and systems pioneered several structuring techniques and constructs now common in both sequential and concurrent OO programming. The use of interfaces in OO development was popularized by OMG CORBA-IDL, a mostly implementation-independent language for specifying functionality in distributed object systems. Most OMG and CORBA documents are available electronically from www.omg.org.

The distributed programming language Emerald was among the first to employ interfaces; see:

The interaction diagrams used in this book are based in part on a CORBA-IDL based specification framework described in:

Process Groups have been used in many contexts in distributed systems, most notably in Isis. Process Group frameworks differ from those based on Group Proxies described in this book by virtue of dealing with distributed process-level objects rather than threads. For more detailed discussions and additional control policies and algorithms, see:

The Hermes programming language pioneered several language constructs and techniques for structuring concurrent and distributed programs, including reference transfer as a primitive. See:

The Spring OO operating system interface definition language embedded similar reference-passing policies as argument qualifiers for methods. See:

Real-time programming

Real-time programming is concerned with the measurement and control of external phenomena and devices, as seen for example in aircraft navigation systems and factory process control. Nearly all real-time systems are concurrent. Many are also parallel and/or distributed. Some of the most central techniques employed in general-purposes concurrent programming are based on those first used in real-time systems.

These days, the main distinction of real-time methods lies in their focus on hard-real-time problems in which, for the sake of safety and/or correctness, certain activities must be performed within certain time constraints. In part because Java does not supply primitives that provide such guarantees, this book does not cover deadline scheduling and related real-time concerns. Sources on real-time design that take an OO perspective include:

WWW starting points include:

Database systems

Database systems are of course concerned with the storage, management, and retrieval of persistent data. Most database systems are both distributed and multithreaded. As with real-time systems, many general-purpose concurrency techniques have roots in database systems. However, the particular senses of ``concurrency control'' and ``transactions'' seen in accounts of database systems are more narrow and specialized, yet in some cases more extensively studied than those seen in the context of concurrent programming. See:

Concurrent systems

Several specialized fields of software development rely heavily on concurrency. For example, essentially all simulation systems, telecommunications systems, and multimedia systems are highly multithreaded. While basic concurrency techniques form much of the basis for the design of such systems, this book stops short of describing large-scale software architectures or specialized programming techniques associated with particular concurrent applications. See, for example:

Multithreaded safety is only one aspect of system safety. For a broader perspective, see:

Flow architectures are only one aspect of task coordination. For a wide-ranging survey, see:

Object-Oriented Concurrent software design

Accounts of high-level object-oriented software analysis and design that cover at least some concurrency issues include:

Extensions to some of the state-based techniques mentioned in chapter 4 are described in several recent technical papers and design patterns, including:

Open implementation designs that avoid extensibility and usability problems associated with pure black-box layering are described in:

Techniques based on unique references have played roles in OO design and analysis methods. See, for example:

A more extensive account of the Resource Exchange pattern may be found in Sane and Campbell's paper in the 1995 volume of Pattern Languages of Program Design.

Many of the above books and research papers discuss object models (See also papers by Peter Wegner). However, few discuss multiple layers or gradations of object models. The most notable exceptions lie outside the technical concurrency literature. See, for example:

WWW starting points on OO design topics include:

Non-OO Concurrent software design

Accounts of non-object-oriented approaches to concurrent software specification and design include:

Joint actions serve as a unifying framework for characterizing multiparticipant actions in DisCo (Jarvinen, Kurki-Suonio, and colleagues) and are further pursued in a slightly different context by Francez and Forman in IP:

WWW starting points on concurrent design methods include:

Patterns

There are many useful design patterns besides those that are special to concurrent Java programming, and surely many others relating to concurrency that are not included in this book. Other books presenting patterns and pattern-related aspects of software design include:

A list of concurrent, distributed, and parallel design patterns available on the WWW can be found at Doug Schmidts's List of Pattern URLs.

Software engineering

Technical issues form only one aspect of concurrent software development, which also entails testing, organization, management, human factors, maintenance, tools, and engineering discipline. For an introduction to basic engineering methods that can be applied to both everyday programming and larger efforts, see:

Research in concurrent OO languages and systems

The kinds of concurrency constructs found or easily emulated in Java are representative of those in most other concurrent OO languages. Some languages differ in that they contain constructs that implicitly create threads when executed. For example, some languages and tools support oneway qualifiers for requests and/or early reply constructs for results. Additionally, there have been several attempts to create completely different kinds of experimental concurrent OO languages, most notably Actor languages in which each object is a process-like entity. See:

Futures and related structured concurrent messaging constructs are natively supported in several concurrent OO languages. For example, the versions used in ABCL are described in:

Research papers on other systems and languages can be found in proceedings of OO conferences (e.g., ECOOP, OOPSLA, COOTS). Also, the following collections contain chapters surveying most current approaches and issues:

Particular papers of referenced in these collections include:

Formal Methods

Most critical properties of concurrent software cannot be checked automatically in the same way as, for example, type safety. It can be very difficult to test concurrent programs for correctness, safety and liveness failures. Formalisms and formal methods have been introduced to help developers rigorously specify and analyze properties of concurrent programs. The best-studied methods are not geared for use with object-oriented programs, and are not fully enough developed to be applied readily to several problems of practical interest. They tend to be most useful for analyzing relatively small sections of programs that it is vitally important to prove problem-free. See, for example:

A more formal approach to development than described in this book is always to start out using design methods that, when flawlessly adhered to, ensure correctness by construction with respect to safety. Transformations can then be applied that improve liveness while provably preserving safety. Top-down class design methods using fully synchronized objects are the Java versions of the most common and usable design strategies along these lines. Accounts of more formal versions that apply in OO contexts are only starting to emerge. See, for example:

Theory

Given the diversity of forms of concurrency seen in software, it's not surprising that there have been a large number of approaches to the basic theory of concurrency. Until recently, few of these applied in any obviously useful way to concurrent object-oriented programming. However, work on process calculi (in particular the -calculus), event structures, linear logic, Petri nets, and temporal logic has potential relevance to the understanding of concurrent OO systems. Most of this work is still scattered throughout the technical literature; see, for example, proceedings of conferences such as CONCUR. For overviews of basic approaches to the theory of concurrency, see:

John Mitchell's course notes on concurrent programming includes surveys of some of these formalisms.

Synchronous Communication

Most active object models rely on asynchronous communication. Many non-object-oriented concurrency models are instead based on synchronous communication among processes (which may be construed as active objects). Under synchronous rendezvous-style communication rules, a message sender cannot proceed until the recipient is ready to accept the message. Synchronous communication plays a central role in languages (including Ada) and models based on process calculi such as CSP and CCS: It is possible to implement versions of synchronous communication channels in Java using variants and extensions of the flow-based techniques described in Chapter 7.

Channels based on synchronized put-take connectors play a prominent role in rendezvous-style parallel programming. A description of Java implementation can be found in Andrew Bakker's paper Communicating Java Threads, as well as code. A conference on using Java in parellel programming will be held in April 1997.

Concurrent algorithms

The TwoLockQueue class is a Java adaptation of an algorithm described in:

An example of research on tools to help automate loosening of synchronization is the paper Lock Coarsening: Eliminating Lock Overhead in Automatically Parallelized Object-Based Programs by Martin Rinard.

Event-counts and sequencers are strictly monotonic latch-style variables used for synchronization. A good description can be found in:

The theory of wait-free algorithms is described in:

Work on wait-free algorithms is still scattered across the technical research literature, and guaranteed wait-free algorithms are known for only a small number of common design problems, for example simple queues and lists. Implementations of these algorithms tend to outperform more standard algorithms only on multiple CPUs supporting special machine instructions.

Links to Concurrent Java Code

Doug Lea
Last modified: Fri Feb 26 10:53:36 EST 1999