Concurrent Object-Oriented Programming
- Concurrent Object-Oriented Programming
- 2 Objects and Concurrency
- 3 Design Forces
- 4 Before/After Patterns
This book discusses some ways of thinking about, designing, and implementing concurrent programs in the Java programming language. Most presentations in this book assume that you are an experienced developer familiar with object-oriented (OO) OO terminological conventions: programs define methods (implementing operations) and fields (representing attributes) that hold for all instances (objects) of specified classes.
Interactions in OO 1.3.4 and 3:
1.1 Using Concurrency Constructs
This section introduces basic concurrency support constructs by example and then proceeds with a walk-through of the principal methods of class Thread. Other concurrency constructs are briefly described as they are introduced, but full technical details are postponed to later chapters (mainly 2.2.1 and 3.2.2). Also, concurrent programs often make use of a few ordinary Java programming language features that are not as widely used elsewhere. These are briefly reviewed as they arise.
1.1.1 A Particle Applet
ParticleApplet is an Applet that displays randomly moving particles. In addition to concurrency constructs, this example illustrates a few of the issues encountered when using threads with any GUI-based program. The version described here needs a lot of embellishment to be visually attractive or realistic. You might enjoy experimenting with additions and variations as an exercise.
As is typical of GUI-based programs, ParticleApplet uses several auxiliary classes that do most of the work. We'll step through construction of the Particle and ParticleCanvas classes before discussing ParticleApplet.
1.1.1.1 Particle
The Particle class defines a completely unrealistic model of movable bodies. Each particle is represented only by its (x, y) location. Each particle also supports a method to randomly change its location and a method to draw itself (as a small square) given a supplied java.awt.Graphics object.
While Particle objects do not themselves exhibit any intrinsic concurrency, their methods may be invoked across multiple concurrent activities. When one activity is performing a move and another is invoking draw at about the same time, we'd like to make sure that the draw paints an accurate representation of where the Particle is. Here, we require that draw uses the location values current either before or after the move. For example, it would be conceptually wrong for a draw operation to display using the y-value current before a given move, but the x-value current after the move. If we were to allow this, then the draw method would sometimes display the particle at a location that it never actually occupied.
This protection can be obtained using the synchronized keyword, which can modify either a method or a block of code. Every instance of class Object (and its subclasses) possesses a lock that is obtained on entry to a synchronized method and automatically released upon exit. The code-block version works in the same way except that it takes an argument stating which object to lock. The most common argument is this, meaning to lock the object whose method is executing. When a lock is held by one thread, other threads must block waiting for the holding thread to release the lock. Locking has no effect on non-synchronized methods, which can execute even if the lock is being held by another thread.
Locking provides protection against both high-level and low-level conflicts by enforcing atomicity among methods and code-blocks synchronized on the same object. Atomic actions are performed as units, without any interleaving of the actions of other threads. But, as discussed in 1.3.2 and in Chapter 2, too much locking can also produce liveness problems that cause programs to freeze up. Rather than exploring these issues in detail now, we'll rely on some simple default rules for writing methods that preclude interference problems:
Always lock during updates to object fields.
Always lock during access of possibly updated object fields.
Never lock when invoking methods on other objects.
These rules have many exceptions and refinements, but they provide enough guidance to write class Particle:
import java.util.Random; class Particle { protected int x; protected int y; protected final Random rng = new Random(); public Particle(int initialX, int initialY) { x = initialX; y = initialY; } public synchronized void move() { x += rng.nextInt(10) - 5; y += rng.nextInt(20) - 10; } public void draw(Graphics g) { int lx, ly; synchronized (this) { lx = x; ly = y; } g.drawRect(lx, ly, 10, 10); } }
Notes:
The use of final in the declaration of the random number generator rng reflects our decision that this reference field cannot be changed, so it is not impacted by our locking rules. Many concurrent programs use final extensively, in part as helpful, automatically enforced documentation of design decisions that reduce the need for synchronization (see 2.1).
The draw method needs to obtain a consistent snapshot of both the x and y values. Since a single method can return only one value at a time, and we need both the x and y values here, we cannot easily encapsulate the field accesses as a synchronized method. We instead use a synchronized block. (See 2.4 for some alternatives.)
The draw method conforms to our rule of thumb to release locks during method invocations on other objects (here g.drawRect). The move method appears to break this rule by calling rng.nextInt. However, this is a reasonable choice here because each Particle confines its own rng conceptually, the rng is just a part of the Particle itself, so it doesn't count as an "other" object in the rule. Section 2.3 describes more general conditions under which this sort of reasoning applies and discusses factors that should be taken into account to be sure that this decision is warranted.
1.1.1.2 ParticleCanvas
ParticleCanvas is a simple subclass of java.awt.Canvas that provides a drawing area for all of the Particles. Its main responsibility is to invoke draw for all existing particles whenever its paint method is called.
However, the ParticleCanvas itself does not create or manage the particles. It needs either to be told about them or to ask about them. Here, we choose the former.
The instance variable particles holds the array of existing Particle objects. This field is set when necessary by the applet, but is used in the paint method. We can again apply our default rules, which in this case lead to the creation of little synchronized get and set methods (also known as accessor and assignment methods) for particles, otherwise avoiding direct access of the particles variable itself. To simplify and to enforce proper usage, the particles field is never allowed to be null. It is instead initialized to an empty array:
class ParticleCanvas extends Canvas { private Particle[ ] particles = new Particle[0]; ParticleCanvas(int size) { setSize(new Dimension(size, size)); } // intended to be called by applet protected synchronized void setParticles(Particle[ ] ps) { if (ps == null) throw new IllegalArgumentException("Cannot set null"); particles = ps; } protected synchronized Particle[ ] getParticles() { return particles; } public void paint(Graphics g) { // override Canvas.paint Particle[ ] ps = getParticles(); for (int i = 0; i < ps.length; ++i) ps[i].draw(g); } }
1.1.1.3 ParticleApplet
The Particle and ParticleCanvas classes could be used as the basis of several different programs. But in ParticleApplet all we want to do is set each of a collection of particles in autonomous "continuous" motion and update the display accordingly to show where they are. To comply with standard applet conventions, these activities should begin when Applet.start is externally invoked (normally from within a web browser), and should end when Applet.stop is invoked. (We could also add buttons allowing users to start and stop the particle animation themselves.)
There are several ways to implement all this. Among the simplest is to associate an independent loop with each particle and to run each looping action in a different thread.
Actions to be performed within new threads must be defined in classes implementing java.lang.Runnable. This interface lists only the single method run, taking no arguments, returning no results, and throwing no checked exceptions:
public interface java.lang.Runnable { void run(); }
An interface encapsulates a coherent set of services and attributes (broadly, a role) without assigning this functionality to any particular object or code. Interfaces are more abstract than classes since they say nothing at all about representations or code. All they do is describe the signatures (names, arguments, result types, and exceptions) of public operations, without even pinning down the classes of the objects that can perform them. The classes that can support Runnable typically have nothing in common except that they contain a run method.
Each instance of the Thread class maintains the control state necessary to execute and manage the call sequence comprising its action. The most commonly used constructor in class Thread accepts a Runnable object as an argument, which arranges to invoke the Runnable's run method when the thread is started. While any class can implement Runnable, it often turns out to be both convenient and helpful to define a Runnable as an anonymous inner class.
The ParticleApplet class uses threads in this way to put particles into motion, and cancels them when the applet is finished. This is done by overriding the standard Applet methods start and stop (which have the same names as, but are unrelated to, methods Thread.start and Thread.stop).
The above interaction diagram shows the main message sequences during execution of the applet. In addition to the threads explicitly created, this applet interacts with the AWT event thread, described in more detail in 4.1.4. The producer-consumer relationship extending from the omitted right hand side of the interaction diagram takes the approximate form:
public class ParticleApplet extends Applet { protected Thread[ ] threads = null; // null when not running protected final ParticleCanvas canvas = new ParticleCanvas(100); public void init() { add(canvas); } protected Thread makeThread(final Particle p) { // utility Runnable runloop = new Runnable() { public void run() { try { for(;;) { p.move(); canvas.repaint(); Thread.sleep(100); // 100msec is arbitrary } } catch (InterruptedException e) { return; } } }; return new Thread(runloop); } public synchronized void start() { int n = 10; // just for demo if (threads == null) { // bypass if already started Particle[ ] particles = new Particle[n]; for (int i = 0; i < n; ++i) particles[i] = new Particle(50, 50); canvas.setParticles(particles); threads = new Thread[n]; for (int i = 0; i < n; ++i) { threads[i] = makeThread(particles[i]); threads[i].start(); } } } public synchronized void stop() { if (threads != null) { // bypass if already stopped for (int i = 0; i < threads.length; ++i) threads[i].interrupt(); threads = null; } } }
Notes:
The action in makeThread defines a "forever" loop (which some people prefer to write equivalently as "while (true)") that is broken only when the current thread is interrupted. During each iteration, the particle moves, tells the canvas to repaint so the move will be displayed, and then does nothing for a while, to slow things down to a human-viewable rate. Thread.sleep pauses the current thread. It is later resumed by a system timer.
One reason that inner classes are convenient and useful is that they capture all appropriate context variables here p and canvas without the need to create a separate class with fields that record these values. This convenience comes at the price of one minor awkwardness: All captured method arguments and local variables must be declared as final, as a guarantee that the values can indeed be captured unambiguously. Otherwise, for example, if p were reassigned after constructing the Runnable inside method makeThread, then it would be ambiguous whether to use the original or the assigned value when executing the Runnable.
The call to canvas.repaint does not directly invoke canvas.paint. The repaint method instead places an UpdateEvent on a java.awt.EventQueue. (This may be internally optimized and further manipulated to eliminate duplicate events.) A java.awt.EventDispatchThread asynchronously takes this event from the queue and dispatches it by (ultimately) invoking canvas.paint. This thread and possibly other system-created threads may exist even in nominally single-threaded programs.
The activity represented by a constructed Thread object does not begin until invocation of the Thread.start method.
As discussed in 3.1.2, there are several ways to cause a thread's activity to stop. The simplest is just to have the run method terminate normally. But in infinitely looping methods, the best option is to use Thread.interrupt. An interrupted thread will automatically abort (via an InterruptedException) from the methods Object.wait, Thread.join, and Thread.sleep. Callers can then catch this exception and take any appropriate action to shut down. Here, the catch in runloop just causes the run method to exit, which in turn causes the thread to terminate.
The start and stop methods are synchronized to preclude concurrent starts or stops. Locking works out OK here even though these methods need to perform many operations (including calls to other objects) to achieve the required started-to-stopped or stopped-to-started state transitions. Nullness of variable threads is used as a convenient state indicator.
1.1.2 Thread Mechanics
A thread is a call sequence that executes independently of others, while at the same time possibly sharing underlying system resources such as files, as well as accessing other objects constructed within the same program (see 1.2.2). A java.lang.Thread object maintains bookkeeping and control for this activity.
Every program consists of at least one thread the one that runs the main method of the class provided as a startup argument to the Java virtual machine ("JVM"). Other internal background threads may also be started during JVM initialization. The number and nature of such threads vary across JVM implementations. However, all user-level threads are explicitly constructed and started from the main thread, or from any other threads that they in turn create.
Here is a summary of the principal methods and properties of class Thread, as well as a few usage notes. They are further discussed and illustrated throughout this book. The Java Language Specification ("JLS") and the published API documentation should be consulted for more detailed and authoritative descriptions.
1.1.2.1 Construction
Different Thread constructors accept combinations of arguments supplying:
A Runnable object, in which case a subsequent Thread.start invokes run of the supplied Runnable object. If no Runnable is supplied, the default implementation of Thread.run returns immediately.
A String that serves as an identifier for the Thread. This can be useful for tracing and debugging, but plays no other role.
The ThreadGroup in which the new Thread should be placed. If access to the ThreadGroup is not allowed, a SecurityException is thrown.
Class Thread itself implements Runnable. So, rather than supplying the code to be run in a Runnable and using it as an argument to a Thread constructor, you can create a subclass of Thread that overrides the run method to perform the desired actions. However, the best default strategy is to define a Runnable as a separate class and supply it in a Thread constructor. Isolating code within a distinct class relieves you of worrying about any potential interactions of synchronized methods or blocks used in the Runnable with any that may be used by methods of class Thread. More generally, this separation allows independent control over the nature of the action and the context in which it is run: The same Runnable can be supplied to threads that are otherwise initialized in different ways, as well as to other lightweight executors (see 4.1.4). Also note that subclassing Thread precludes a class from subclassing any other class.
Thread objects also possess a daemon status attribute that cannot be set via any Thread constructor, but may be set only before a Thread is started. The method setDaemon asserts that the JVM may exit, abruptly terminating the thread, so long as all other non-daemon threads in the program have terminated. The isDaemon method returns status. The utility of daemon status is very limited. Even background threads often need to do some cleanup upon program exit. (The spelling of daemon, often pronounced as "day-mon", is a relic of systems programming tradition. System daemons are continuous processes, for example print-queue managers, that are "always" present on a system.)
1.1.2.2 Starting threads
Invoking its start method causes an instance of class Thread to initiate its run method as an independent activity. None of the synchronization locks held by the caller thread are held by the new thread (see 2.2.1).
A Thread terminates when its run method completes by either returning normally or throwing an unchecked exception (i.e., RuntimeException, Error, or one of their subclasses). Threads are not restartable, even after they terminate. Invoking start more than once results in an InvalidThreadStateException.
The method isAlive returns true if a thread has been started but has not terminated. It will return true if the thread is merely blocked in some way. JVM implementations have been known to differ in the exact point at which isAlive returns false for threads that have been cancelled (see 3.1.2). There is no method that tells you whether a thread that is not isAlive has ever been started. Also, one thread cannot readily determine which other thread started it, although it may determine the identities of other threads in its ThreadGroup (see 1.1.2.6).
1.1.2.3 Priorities
To make it possible to implement the Java virtual machine across diverse hardware platforms and operating systems, the Java programming language makes no promises about scheduling or fairness, and does not even strictly guarantee that threads make forward progress (see 3.4.1.5). But threads do support priority methods that heuristically influence schedulers:
Each Thread has a priority, ranging between Thread.MIN_PRIORITY and Thread.MAX_PRIORITY (defined as 1 and 10 respectively).
By default, each new thread has the same priority as the thread that created it. The initial thread associated with a main by default has priority Thread.NORM_PRIORITY (5).
The current priority of any thread can be accessed via method getPriority.
The priority of any thread can be dynamically changed via method setPriority. The maximum allowed priority for a thread is bounded by its ThreadGroup.
When there are more runnable (see 1.3.2) threads than available CPUs, a scheduler is generally biased to prefer running those with higher priorities. The exact policy may and does vary across platforms. For example, some JVM implementations always select the thread with the highest current priority (with ties broken arbitrarily). Some JVM implementations map the ten Thread priorities into a smaller number of system-supported categories, so threads with different priorities may be treated equally. And some mix declared priorities with aging schemes or other scheduling policies to ensure that even low-priority threads eventually get a chance to run. Also, setting priorities may, but need not, affect scheduling with respect to other programs running on the same computer system.
Priorities have no other bearing on semantics or correctness (see 1.3). In particular, priority manipulations cannot be used as a substitute for locking. Priorities can be used only to express the relative importance or urgency of different threads, where these priority indications would be useful to take into account when there is heavy contention among threads trying to get a chance to execute. For example, setting the priorities of the particle animation threads in ParticleApplet below that of the applet thread constructing them might on some systems improve responsiveness to mouse clicks, and would at least not hurt responsiveness on others. But programs should be designed to run correctly (although perhaps not as responsively) even if setPriority is defined as a no-op. (Similar remarks hold for yield; see 1.1.2.5.)
The following table gives one set of general conventions for linking task categories to priority settings. In many concurrent applications, relatively few threads are actually runnable at any given time (others are all blocked in some way), in which case there is little reason to manipulate priorities. In other cases, minor tweaks in priority settings may play a small part in the final tuning of a concurrent system.
1.1.2.4 Control methods
Only a few methods are available for communicating across threads:
Each Thread has an associated boolean interruption status (see 3.1.2). Invoking t.interrupt for some Thread t sets t's interruption status to true, unless Thread t is engaged in Object.wait, Thread.sleep, or Thread.join; in this case interrupt causes these actions (in t) to throw InterruptedException, but t's interruption status is set to false.
The interruption status of any Thread can be inspected using method isInterrupted. This method returns true if the thread has been interrupted via the interrupt method but the status has not since been reset either by the thread invoking Thread.interrupted (see 1.1.2.5) or in the course of wait, sleep, or join throwing InterruptedException.
Invoking t.join() for Thread t suspends the caller until the target Thread t completes: the call to t.join() returns when t.isAlive() is false (see 4.3.2). A version with a (millisecond) time argument returns control even if the thread has not completed within the specified time limit. Because of how isAlive is defined, it makes no sense to invoke join on a thread that has not been started. For similar reasons, it is unwise to try to join a Thread that you did not create.
Originally, class Thread supported the additional control methods suspend, resume, stop, and destroy. Methods suspend, resume, and stop have since been deprecated; method destroy has never been implemented in any release and probably never will be. The effects of methods suspend and resume can be obtained more safely and reliably using the waiting and notification techniques discussed in 3.2. The problems surrounding stop are discussed in 3.1.2.3.
1.1.2.5 Static methods
Some Thread class methods can be applied only to the thread that is currently running (i.e., the thread making the call to the Thread method). To enforce this, these methods are declared as static.
Thread.currentThread returns a reference to the current Thread. This reference may then be used to invoke other (non-static) methods. For example, Thread.currentThread().getPriority() returns the priority of the thread making the call.
Thread.interrupted clears interruption status of the current Thread and returns previous status. (Thus, one Thread's interruption status cannot be cleared from other threads.)
Thread.sleep(long msecs) causes the current thread to suspend for at least msecs milliseconds (see 3.2.2).
Thread.yield is a purely heuristic hint advising the JVM that if there are any other runnable but non-running threads, the scheduler should run one or more of these threads rather than the current thread. The JVM may interpret this hint in any way it likes.
Despite the lack of guarantees, yield can be pragmatically effective on some single-CPU JVM implementations that do not use time-sliced pre-emptive scheduling (see 1.2.2). In this case, threads are rescheduled only when one blocks (for example on IO, or via sleep). On these systems, threads that perform time-consuming non-blocking computations can tie up a CPU for extended periods, decreasing the responsiveness of an application. As a safeguard, methods performing non-blocking computations that might exceed acceptable response times for event handlers or other reactive threads can insert yields (or perhaps even sleeps) and, when desirable, also run at lower priority settings. To minimize unnecessary impact, you can arrange to invoke yield only occasionally; for example, a loop might contain:
if (Math.random() < 0.01) Thread.yield();
On JVM implementations that employ pre-emptive scheduling policies, especially those on multiprocessors, it is possible and even desirable that the scheduler will simply ignore this hint provided by yield.
1.1.2.6 ThreadGroups
Every Thread is constructed as a member of a ThreadGroup, by default the same group as that of the Thread issuing the constructor for it. ThreadGroups nest in a tree-like fashion. When an object constructs a new ThreadGroup, it is nested under its current group. The method getThreadGroup returns the group of any thread. The ThreadGroup class in turn supports methods such as enumerate that indicate which threads are currently in the group.
One purpose of class ThreadGroup is to support security policies that dynamically restrict access to Thread operations; for example, to make it illegal to interrupt a thread that is not in your group. This is one part of a set of protective measures against problems that could occur, for example, if an applet were to try to kill the main screen display update thread. ThreadGroups may also place a ceiling on the maximum priority that any member thread can possess.
ThreadGroups tend not to be used directly in thread-based programs. In most applications, normal collection classes (for example java.util.Vector) are better choices for tracking groups of Thread objects for application-dependent purposes.
Among the few ThreadGroup methods that commonly come into play in concurrent programs is method uncaughtException, which is invoked when a thread in a group terminates due to an uncaught unchecked exception (for example a NullPointerException). This method normally causes a stack trace to be printed.
1.1.3 Further Readings
This book is not a reference manual on the Java programming language. (It is also not exclusively a how-to tutorial guide, or an academic textbook on concurrency, or a report on experimental research, or a book on design methodology or design patterns or pattern languages, but includes discussions on each of these facets of concurrency.) Most sections conclude with lists of resources that provide more information on selected topics. If you do a lot of concurrent programming, you will want to read more about some of them.
The JLS should be consulted for more authoritative accounts of the properties of Java programming language constructs summarized in this book:
Gosling, James, Bill Joy, and Guy Steele. The Java Language Specification, Addison-Wesley, 1996. As of this writing, a second edition of JLS is projected to contain clarifications and updates for the Java 2 Platform.
Introductory accounts include:
Arnold, Ken, and James Gosling. The Java Programming Language, Second Edition, Addison-Wesley, 1998.
If you have never written a program using threads, you may find it useful to work through either the online or book version of the Threads section of:
Campione, Mary, and Kathy Walrath. The Java Tutorial, Second Edition, Addison-Wesley, 1998.
A concise guide to UML notation is:
Fowler, Martin, with Kendall Scott. UML Distilled, Second Edition, Addison-Wesley, 1999. The UML diagram keys on pages 3-4 of the present book are excerpted by permission.
A more extensive account of UML is:
Rumbaugh, James, Ivar Jacobson, and Grady Booch. The Unified Modeling Language Reference Manual, Addison-Wesley, 1999.