Figure 14.1 Using a thread to animate a bouncing ball
You are probably familiar with multitasking—your operating system’s ability to have more than one program working at what seems like the same time. For example, you can print while editing or downloading your email. Nowadays, you are likely to have a computer with more than one CPU, but the number of concurrently executing processes is not limited by the number of CPUs. The operating system assigns CPU time slices to each process, giving the impression of parallel activity.
Multithreaded programs extend the idea of multitasking by taking it one level lower: Individual programs will appear to do multiple tasks at the same time. Each task is usually called a thread, which is short for thread of control. Programs that can run more than one thread at once are said to be multithreaded.
So, what is the difference between multiple processes and multiple threads? The essential difference is that while each process has a complete set of its own variables, threads share the same data. This sounds somewhat risky, and indeed it can be, as you will see later in this chapter. However, shared variables make communication between threads more efficient and easier to program than interprocess communication. Moreover, on some operating systems, threads are more “lightweight” than processes—it takes less overhead to create and destroy individual threads than it does to launch new processes.
Multithreading is extremely useful in practice. For example, a browser should be able to simultaneously download multiple images. A web server needs to be able to serve concurrent requests. Graphical user interface (GUI) programs have a separate thread for gathering user interface events from the host operating environment. This chapter shows you how to add multithreading capability to your Java applications.
Fair warning: Concurrent programming can get very complex. In this chapter, we cover all the tools that an application programmer is likely to need. However, for more intricate system-level programming, we suggest that you turn to a more advanced reference, such as Java Concurrency in Practice by Brian Goetz et al. (Addison-Wesley Professional, 2006).
Let us start by looking at a program that does not use multiple threads and that, as a consequence, makes it difficult for the user to perform several tasks with that program. After we dissect it, we will show you how easy it is to have this program run separate threads. This program animates a bouncing ball by continually moving the ball, finding out if it bounces against a wall, and then redrawing it. (See Figure 14.1.)
As soon as you click the Start button, the program launches a ball from the upper left corner of the screen and the ball begins bouncing. The handler of the Start button calls the addBall method. That method contains a loop running through 1,000 moves. Each call to move moves the ball by a small amount, adjusts the direction if it bounces against a wall, and redraws the panel.
Ball ball = new Ball();
panel.add(ball);
for (int i = 1; i <= STEPS; i++)
{
ball.move(panel.getBounds());
panel.paint(panel.getGraphics());
Thread.sleep(DELAY);
}
The call to Thread.sleep does not create a new thread—sleep is a static method of the Thread class that temporarily stops the activity of the current thread for the given number of milliseconds.
The sleep method can throw an InterruptedException. We discuss this exception and its proper handling later. For now, we simply terminate the bouncing if this exception occurs.
If you run the program, the ball bounces around nicely, but it completely takes over the application. If you become tired of the bouncing ball before it has finished its 1,000 moves and click the Close button, the ball continues bouncing anyway. You cannot interact with the program until the ball has finished bouncing.
If you carefully look over the code at the end of this section, you will notice the call
comp.paint(comp.getGraphics())
inside the addBall method of the BounceFrame class. That is pretty strange—normally, you’d call repaint and let the AWT worry about getting the graphics context and doing the painting. But if you try to call comp.repaint() in this program, you’ll find that the panel is only repainted after the addBall method has returned. Also note that the ball component extends JPanel; this makes it easier to erase the background. In the next program, in which we use a separate thread to compute the ball position, we can go back to the familiar use of repaint and JComponent.
Obviously, the behavior of this program is rather poor. You would not want a program you use to behave in this way when you ask it to do a time-consuming job. After all, when you are reading data over a network connection, it is all too common to be stuck in a task that you would really like to interrupt. For example, suppose you download a large image and decide, after seeing a piece of it, that you do not need or want to see the rest; you certainly would like to be able to click a Stop or Back button to interrupt the loading process. In the next section, we will show you how to keep the user in control by running crucial parts of the code in a separate thread.
Listings 14.1 through 14.3 show the code for the program.
Listing 14.1 bounce/Bounce.java
1 package bounce;
2
3 import java.awt.*;
4 import java.awt.event.*;
5 import javax.swing.*;
6
7 /**
8 * Shows an animated bouncing ball.
9 * @version 1.34 2015-06-21
10 * @author Cay Horstmann
11 */
12 public class Bounce
13 {
14 public static void main(String[] args)
15 {
16 EventQueue.invokeLater(() -> {
17 JFrame frame = new BounceFrame();
18 frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
19 frame.setVisible(true);
20 });
21 }
22 }
23
24 /**
25 * The frame with ball component and buttons.
26 */
27 class BounceFrame extends JFrame
28 {
29 private BallComponent comp;
30 public static final int STEPS = 1000;
31 public static final int DELAY = 3;
32
33 /**
34 * Constructs the frame with the component for showing the bouncing ball and
35 * Start and Close buttons
36 */
37 public BounceFrame()
38 {
39 setTitle("Bounce");
40 comp = new BallComponent();
41 add(comp, BorderLayout.CENTER);
42 JPanel buttonPanel = new JPanel();
43 addButton(buttonPanel, "Start", event -> addBall());
44 addButton(buttonPanel, "Close", event -> System.exit(0));
45 add(buttonPanel, BorderLayout.SOUTH);
46 pack();
47 }
48
49 /**
50 * Adds a button to a container.
51 * @param c the container
52 * @param title the button title
53 * @param listener the action listener for the button
54 */
55 public void addButton(Container c, String title, ActionListener listener)
56 {
57 JButton button = new JButton(title);
58 c.add(button);
59 button.addActionListener(listener);
60 }
61
62 /**
63 * Adds a bouncing ball to the panel and makes it bounce 1,000 times.
64 */
65 public void addBall()
66 {
67 try
68 {
69 Ball ball = new Ball();
70 comp.add(ball);
71
72 for (int i = 1; i <= STEPS; i++)
73 {
74 ball.move(comp.getBounds());
75 comp.paint(comp.getGraphics());
76 Thread.sleep(DELAY);
77 }
78 }
79 catch (InterruptedException e)
80 {
81 }
82 }
83 }
1 package bounce;
2
3 import java.awt.geom.*;
4
5 /**
6 * A ball that moves and bounces off the edges of a rectangle
7 * @version 1.33 2007-05-17
8 * @author Cay Horstmann
9 */
10 public class Ball
11 {
12 private static final int XSIZE = 15;
13 private static final int YSIZE = 15;
14 private double x = 0;
15 private double y = 0;
16 private double dx = 1;
17 private double dy = 1;
18
19 /**
20 * Moves the ball to the next position, reversing direction if it hits one of the edges
21 */
22 public void move(Rectangle2D bounds)
23 {
24 x += dx;
25 y += dy;
26 if (x < bounds.getMinX())
27 {
28 x = bounds.getMinX();
29 dx = -dx;
30 }
31 if (x + XSIZE >= bounds.getMaxX())
32 {
33 x = bounds.getMaxX() - XSIZE;
34 dx = -dx;
35 }
36 if (y < bounds.getMinY())
37 {
38 y = bounds.getMinY();
39 dy = -dy;
40 }
41 if (y + YSIZE >= bounds.getMaxY())
42 {
43 y = bounds.getMaxY() - YSIZE;
44 dy = -dy;
45 }
46 }
47
48 /**
49 * Gets the shape of the ball at its current position.
50 */
51 public Ellipse2D getShape()
52 {
53 return new Ellipse2D.Double(x, y, XSIZE, YSIZE);
54 }
55 }
Listing 14.3 bounce/BallComponent.java
1 package bounce;
2
3 import java.awt.*;
4 import java.util.*;
5 import javax.swing.*;
6
7 /**
8 * The component that draws the balls.
9 * @version 1.34 2012-01-26
10 * @author Cay Horstmann
11 */
12 public class BallComponent extends JPanel
13 {
14 private static final int DEFAULT_WIDTH = 450;
15 private static final int DEFAULT_HEIGHT = 350;
16
17 private java.util.List<Ball> balls = new ArrayList<>();
18
19 /**
20 * Add a ball to the component.
21 * @param b the ball to add
22 */
23 public void add(Ball b)
24 {
25 balls.add(b);
26 }
27
28 public void paintComponent(Graphics g)
29 {
30 super.paintComponent(g); // erase background
31 Graphics2D g2 = (Graphics2D) g;
32 for (Ball b : balls)
33 {
34 g2.fill(b.getShape());
35 }
36 }
37
38 public Dimension getPreferredSize() { return new Dimension(DEFAULT_WIDTH, DEFAULT_HEIGHT); }
39 }
java.lang.Thread 1.0
• static void sleep(long millis)
sleeps for the given number of milliseconds.
We will make our bouncing ball program more responsive by running the code that moves the ball in a separate thread. In fact, you will be able to launch multiple balls, each moved by its own thread. In addition, the AWT event dispatch thread will continue running in parallel, taking care of user interface events. Since each thread gets a chance to run, the event dispatch thread has the opportunity to notice that the user clicks the Close button while the balls are bouncing. The thread can then process the “close” action.
We use ball-bouncing code as an example to give you a visual impression of the need for concurrency. In general, you need to be wary of any long-running computation. Your computation is likely to be a part of some bigger framework, such as a GUI or web framework. Whenever the framework calls one of your methods, there is usually an expectation of a quick return. If you need to do any task that takes a long time, your task should run concurrently.
Here is a simple procedure for running a task in a separate thread:
1. Place the code for the task into the run method of a class that implements the Runnable interface. That interface is very simple, with a single method:
public interface Runnable
{
void run();
}
Since Runnable is a functional interface, you can make an instance with a lambda expression:
Runnable r = () -> { task code };
2. Construct a Thread object from the Runnable:
Thread t = new Thread(r);
3. Start the thread:
t.start();
To make our bouncing ball program into a separate thread, we need only place the code for the animation inside the run method of a Runnable, and then start a thread:
Runnable r = () -> {
try
{
for (int i = 1; i <= STEPS; i++)
{
ball.move(comp.getBounds());
comp.repaint();
Thread.sleep(DELAY);
}
}
catch (InterruptedException e)
{
}
};
Thread t = new Thread(r);
t.start();
Again, we need to catch an InterruptedException that the sleep method threatens to throw. We will discuss this exception in the next section. Typically, interruption is used to request that a thread terminates. Accordingly, our run method exits when an InterruptedException occurs.
Whenever the Start button is clicked, the ball is moved in a new thread (see Figure 14.2).
That’s all there is to it! You now know how to run tasks in parallel. The remainder of this chapter tells you how to control the interaction between threads.
The complete code is shown in Listing 14.4.
Note
You can also define a thread by forming a subclass of the Thread class, like this:
class MyThread extends Thread
{
public void run()
{
task code
}
}
Then you construct an object of the subclass and call its start method. However, this approach is no longer recommended. You should decouple the task that is to be run in parallel from the mechanism of running it. If you have many tasks, it is too expensive to create a separate thread for each of them. Instead, you can use a thread pool—see Section 14.9, “Executors,” on p. 920.
Do not call the run method of the Thread class or the Runnable object. Calling the run method directly merely executes the task in the same thread—no new thread is started. Instead, call the Thread.start method. It creates a new thread that executes the run method.
Listing 14.4 bounceThread/BounceThread.java
1 package bounceThread;
2
3 import java.awt.*;
4 import java.awt.event.*;
5
6 import javax.swing.*;
7
8 /**
9 * Shows animated bouncing balls.
10 * @version 1.34 2015-06-21
11 * @author Cay Horstmann
12 */
13 public class BounceThread
14 {
15 public static void main(String[] args)
16 {
17 EventQueue.invokeLater(() -> {
18 JFrame frame = new BounceFrame();
19 frame.setTitle("BounceThread");
20 frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
21 frame.setVisible(true);
22 });
23 }
24 }
25
26 /**
27 * The frame with panel and buttons.
28 */
29 class BounceFrame extends JFrame
30 {
31 private BallComponent comp;
32 public static final int STEPS = 1000;
33 public static final int DELAY = 5;
34
35 /**
36 * Constructs the frame with the component for showing the bouncing ball and
37 * Start and Close buttons
38 */
39 public BounceFrame()
40 {
41 comp = new BallComponent();
42 add(comp, BorderLayout.CENTER);
43 JPanel buttonPanel = new JPanel();
44 addButton(buttonPanel, "Start", event -> addBall());
45 addButton(buttonPanel, "Close", event -> System.exit(0));
46 add(buttonPanel, BorderLayout.SOUTH);
47 pack();
48 }
49
50 /**
51 * Adds a button to a container.
52 * @param c the container
53 * @param title the button title
54 * @param listener the action listener for the button
55 */
56 public void addButton(Container c, String title, ActionListener listener)
57 {
58 JButton button = new JButton(title);
59 c.add(button);
60 button.addActionListener(listener);
61 }
62
63 /**
64 * Adds a bouncing ball to the canvas and starts a thread to make it bounce
65 */
66 public void addBall()
67 {
68 Ball ball = new Ball();
69 comp.add(ball);
70 Runnable r = () -> {
71 try
72 {
73 for (int i = 1; i <= STEPS; i++)
74 {
75 ball.move(comp.getBounds());
76 comp.repaint();
77 Thread.sleep(DELAY);
78 }
79 }
80 catch (InterruptedException e)
81 {
82 }
83 };
84 Thread t = new Thread(r);
85 t.start();
86 }
87 }
A thread terminates when its run method returns—by executing a return statement, after executing the last statement in the method body, or if an exception occurs that is not caught in the method. In the initial release of Java, there also was a stop method that another thread could call to terminate a thread. However, that method is now deprecated. We discuss the reason in Section 14.5.15, “Why the stop and suspend Methods Are Deprecated,” on p. 896.
Other than with the deprecated stop method, there is no way to force a thread to terminate. However, the interrupt method can be used to request termination of a thread.
When the interrupt method is called on a thread, the interrupted status of the thread is set. This is a boolean flag that is present in every thread. Each thread should occasionally check whether it has been interrupted.
To find out whether the interrupted status was set, first call the static Thread.currentThread method to get the current thread, and then call the isInterrupted method:
while (!Thread.currentThread().isInterrupted() && more work to do)
{
do more work
}
However, if a thread is blocked, it cannot check the interrupted status. This is where the InterruptedException comes in. When the interrupt method is called on a thread that blocks on a call such as sleep or wait, the blocking call is terminated by an InterruptedException. (There are blocking I/O calls that cannot be interrupted; you should consider interruptible alternatives. See Chapters 1 and 3 of Volume II for details.)
There is no language requirement that a thread which is interrupted should terminate. Interrupting a thread simply grabs its attention. The interrupted thread can decide how to react to the interruption. Some threads are so important that they should handle the exception and continue. But quite commonly, a thread will simply want to interpret an interruption as a request for termination. The run method of such a thread has the following form:
Runnable r = () -> {
try
{
. . .
while (!Thread.currentThread().isInterrupted() && more work to do)
{
do more work
}
}
catch(InterruptedException e)
{
// thread was interrupted during sleep or wait
}
finally
{
cleanup, if required
}
// exiting the run method terminates the thread
};
The isInterrupted check is neither necessary nor useful if you call the sleep method (or another interruptible method) after every work iteration. If you call the sleep method when the interrupted status is set, it doesn’t sleep. Instead, it clears the status (!) and throws an InterruptedException. Therefore, if your loop calls sleep, don’t check the interrupted status. Instead, catch the InterruptedException, like this:
Runnable r = () -> {
try
{
. . .
while (more work to do)
{
do more work
Thread.sleep(delay);
}
}
catch(InterruptedException e)
{
// thread was interrupted during sleep
}
finally
{
cleanup, if required
}
// exiting the run method terminates the thread
};
Note
There are two very similar methods, interrupted and isInterrupted. The interrupted method is a static method that checks whether the current thread has been interrupted. Furthermore, calling the interrupted method clears the interrupted status of the thread. On the other hand, the isInterrupted method is an instance method that you can use to check whether any thread has been interrupted. Calling it does not change the interrupted status.
You’ll find lots of published code in which the InterruptedException is squelched at a low level, like this:
void mySubTask()
{
. . .
try { sleep(delay); }
catch (InterruptedException e) {} // Don't ignore!
. . .
}
Don’t do that! If you can’t think of anything good to do in the catch clause, you still have two reasonable choices:
• In the catch clause, call Thread.currentThread().interrupt() to set the interrupted status. Then the caller can test it.
void mySubTask()
{
. . .
try { sleep(delay); }
catch (InterruptedException e) { Thread.currentThread().interrupt(); }
. . .
}
• Or, even better, tag your method with throws InterruptedException and drop the try block. Then the caller (or, ultimately, the run method) can catch it.
void mySubTask() throws InterruptedException
{
. . .
sleep(delay);
. . .
}
• New
• Runnable
• Blocked
• Waiting
• Timed waiting
• Terminated
Each of these states is explained in the sections that follow.
To determine the current state of a thread, simply call the getState method.
When you create a thread with the new operator—for example, new Thread(r)—the thread is not yet running. This means that it is in the new state. When a thread is in the new state, the program has not started executing code inside of it. A certain amount of bookkeeping needs to be done before a thread can run.
Once you invoke the start method, the thread is in the runnable state. A runnable thread may or may not actually be running. It is up to the operating system to give the thread time to run. (The Java specification does not call this a separate state, though. A running thread is still in the runnable state.)
Once a thread is running, it doesn’t necessarily keep running. In fact, it is desirable that running threads occasionally pause so that other threads have a chance to run. The details of thread scheduling depend on the services that the operating system provides. Preemptive scheduling systems give each runnable thread a slice of time to perform its task. When that slice of time is exhausted, the operating system preempts the thread and gives another thread an opportunity to work (see Figure 14.4). When selecting the next thread, the operating system takes into account the thread priorities—see Section 14.4.1, “Thread Priorities,” on p. 858 for more information.
All modern desktop and server operating systems use preemptive scheduling. However, small devices such as cell phones may use cooperative scheduling. In such a device, a thread loses control only when it calls the yield method, or when it is blocked or waiting.
On a machine with multiple processors, each processor can run a thread, and you can have multiple threads run in parallel. Of course, if there are more threads than processors, the scheduler still has to do time slicing.
Always keep in mind that a runnable thread may or may not be running at any given time. (This is why the state is called “runnable” and not “running.”)
When a thread is blocked or waiting, it is temporarily inactive. It doesn’t execute any code and consumes minimal resources. It is up to the thread scheduler to reactivate it. The details depend on how the inactive state was reached.
• When the thread tries to acquire an intrinsic object lock (but not a Lock in the java.util.concurrent library) that is currently held by another thread, it becomes blocked. (We discuss java.util.concurrent locks in Section 14.5.3, “Lock Objects,” on p. 868 and intrinsic object locks in Section 14.5.5, “The synchronized Keyword,” on p. 878.) The thread becomes unblocked when all other threads have relinquished the lock and the thread scheduler has allowed this thread to hold it.
• When the thread waits for another thread to notify the scheduler of a condition, it enters the waiting state. We discuss conditions in Section 14.5.4, “Condition Objects,” on p. 872. This happens by calling the Object.wait or Thread.join method, or by waiting for a Lock or Condition in the java.util.concurrent library. In practice, the difference between the blocked and waiting state is not significant.
• Several methods have a timeout parameter. Calling them causes the thread to enter the timed waiting state. This state persists either until the timeout expires or the appropriate notification has been received. Methods with timeout include Thread.sleep and the timed versions of Object.wait, Thread.join, Lock.tryLock, and Condition.await.
Figure 14.3 shows the states that a thread can have and the possible transitions from one state to another. When a thread is blocked or waiting (or, of course, when it terminates), another thread will be scheduled to run. When a thread is reactivated (for example, because its timeout has expired or it has succeeded in acquiring a lock), the scheduler checks to see if it has a higher priority than the currently running threads. If so, it preempts one of the current threads and picks a new thread to run.
A thread is terminated for one of two reasons:
• It dies a natural death because the run method exits normally.
• It dies abruptly because an uncaught exception terminates the run method.
In particular, you can kill a thread by invoking its stop method. That method throws a ThreadDeath error object that kills the thread. However, the stop method is deprecated, and you should never call it in your own code.
In the following sections, we discuss miscellaneous properties of threads: thread priorities, daemon threads, thread groups, and handlers for uncaught exceptions.
In the Java programming language, every thread has a priority. By default, a thread inherits the priority of the thread that constructed it. You can increase or decrease the priority of any thread with the setPriority method. You can set the priority to any value between MIN_PRIORITY (defined as 1 in the Thread class) and MAX_PRIORITY (defined as 10). NORM_PRIORITY is defined as 5.
Whenever the thread scheduler has a chance to pick a new thread, it prefers threads with higher priority. However, thread priorities are highly system dependent. When the virtual machine relies on the thread implementation of the host platform, the Java thread priorities are mapped to the priority levels of the host platform, which may have more or fewer thread priority levels.
For example, Windows has seven priority levels. Some of the Java priorities will map to the same operating system level. In the Oracle JVM for Linux, thread priorities are ignored altogether—all threads have the same priority.
Beginning programmers sometimes overuse thread priorities. There are few reasons ever to tweak priorities. You should certainly never structure your programs so that their correct functioning depends on priority levels.
Caution
If you do use priorities, you should be aware of a common beginner’s error. If you have several threads with a high priority that don’t become inactive, the lower-priority threads may never execute. Whenever the scheduler decides to run a new thread, it will choose among the highest-priority threads first, even though that may starve the lower-priority threads completely.
You can turn a thread into a daemon thread by calling
t.setDaemon(true);
There is nothing demonic about such a thread. A daemon is simply a thread that has no other role in life than to serve others. Examples are timer threads that send regular “timer ticks” to other threads or threads that clean up stale cache entries. When only daemon threads remain, the virtual machine exits. There is no point in keeping the program running if all remaining threads are daemons.
Daemon threads are sometimes mistakenly used by beginners who don’t want to think about shutdown actions. However, this can be dangerous. A daemon thread should never access a persistent resource such as a file or database since it can terminate at any time, even in the middle of an operation.
The run method of a thread cannot throw any checked exceptions, but it can be terminated by an unchecked exception. In that case, the thread dies.
However, there is no catch clause to which the exception can be propagated. Instead, just before the thread dies, the exception is passed to a handler for uncaught exceptions.
The handler must belong to a class that implements the Thread.UncaughtExceptionHandler interface. That interface has a single method,
void uncaughtException(Thread t, Throwable e)
You can install a handler into any thread with the setUncaughtExceptionHandler method. You can also install a default handler for all threads with the static method setDefaultUncaughtExceptionHandler of the Thread class. A replacement handler might use the logging API to send reports of uncaught exceptions into a log file.
If you don’t install a default handler, the default handler is null. However, if you don’t install a handler for an individual thread, the handler is the thread’s ThreadGroup object.
Note
A thread group is a collection of threads that can be managed together. By default, all threads that you create belong to the same thread group, but it is possible to establish other groupings. Since there are now better features for operating on collections of threads, we recommend that you do not use thread groups in your programs.
The ThreadGroup class implements the Thread.UncaughtExceptionHandler interface. Its uncaughtException method takes the following action:
1. If the thread group has a parent, then the uncaughtException method of the parent group is called.
2. Otherwise, if the Thread.getDefaultUncaughtExceptionHandler method returns a non-null handler, it is called.
3. Otherwise, if the Throwable is an instance of ThreadDeath, nothing happens.
4. Otherwise, the name of the thread and the stack trace of the Throwable are printed on System.err.
That is the stack trace that you have undoubtedly seen many times in your programs.
java.lang.Thread.UncaughtExceptionHandler 5.0
• void uncaughtException(Thread t, Throwable e)
defined to log a custom report when a thread is terminated with an uncaught exception.
In most practical multithreaded applications, two or more threads need to share access to the same data. What happens if two threads have access to the same object and each calls a method that modifies the state of the object? As you might imagine, the threads can step on each other’s toes. Depending on the order in which the data were accessed, corrupted objects can result. Such a situation is often called a race condition.
To avoid corruption of shared data by multiple threads, you must learn how to synchronize the access. In this section, you’ll see what happens if you do not use synchronization. In the next section, you’ll see how to synchronize data access.
In the next test program, we simulate a bank with a number of accounts. We randomly generate transactions that move money between these accounts. Each account has one thread. Each transaction moves a random amount of money from the account serviced by the thread to another random account.
The simulation code is straightforward. We have the class Bank with the method transfer. This method transfers some amount of money from one account to another. (We don’t yet worry about negative account balances.) Here is the code for the transfer method of the Bank class.
public void transfer(int from, int to, double amount)
// CAUTION: unsafe when called from multiple threads
{
System.out.print(Thread.currentThread());
accounts[from] -= amount;
System.out.printf(" %10.2f from %d to %d", amount, from, to);
accounts[to] += amount;
System.out.printf(" Total Balance: %10.2f%n", getTotalBalance());
}
Here is the code for the Runnable instances. The run method keeps moving money out of a given bank account. In each iteration, the run method picks a random target account and a random amount, calls transfer on the bank object, and then sleeps.
Runnable r = () -> {
try
{
while (true)
{
int toAccount = (int) (bank.size() * Math.random());
double amount = MAX_AMOUNT * Math.random();
bank.transfer(fromAccount, toAccount, amount);
Thread.sleep((int) (DELAY * Math.random()));
}
}
catch (InterruptedException e)
{
}
};
When this simulation runs, we do not know how much money is in any one bank account at any time. But we do know that the total amount of money in all the accounts should remain unchanged because all we do is move money from one account to another.
At the end of each transaction, the transfer method recomputes the total and prints it.
This program never finishes. Just press Ctrl+C to kill the program.
Here is a typical printout:
. . .
Thread[Thread-11,5,main] 588.48 from 11 to 44 Total Balance: 100000.00
Thread[Thread-12,5,main] 976.11 from 12 to 22 Total Balance: 100000.00
Thread[Thread-14,5,main] 521.51 from 14 to 22 Total Balance: 100000.00
Thread[Thread-13,5,main] 359.89 from 13 to 81 Total Balance: 100000.00
. . .
Thread[Thread-36,5,main] 401.71 from 36 to 73 Total Balance: 99291.06
Thread[Thread-35,5,main] 691.46 from 35 to 77 Total Balance: 99291.06
Thread[Thread-37,5,main] 78.64 from 37 to 3 Total Balance: 99291.06
Thread[Thread-34,5,main] 197.11 from 34 to 69 Total Balance: 99291.06
Thread[Thread-36,5,main] 85.96 from 36 to 4 Total Balance: 99291.06
. . .
Thread[Thread-4,5,main]Thread[Thread-33,5,main] 7.31 from 31 to 32 Total Balance:
99979.24
627.50 from 4 to 5 Total Balance: 99979.24
. . .
As you can see, something is very wrong. For a few transactions, the bank balance remains at $100,000, which is the correct total for 100 accounts of $1,000 each. But after some time, the balance changes slightly. When you run this program, errors may happen quickly, or it may take a very long time for the balance to become corrupted. This situation does not inspire confidence, and you would probably not want to deposit your hard-earned money in such a bank.
The program in Listings 14.5 and 14.6 provides the complete source code. See if you can spot the problems with the code. We will unravel the mystery in the next section.
Listing 14.5 unsynch/UnsynchBankTest.java
1 package unsynch;
2
3 /**
4 * This program shows data corruption when multiple threads access a data structure.
5 * @version 1.31 2015-06-21
6 * @author Cay Horstmann
7 */
8 public class UnsynchBankTest
9 {
10 public static final int NACCOUNTS = 100;
11 public static final double INITIAL_BALANCE = 1000;
12 public static final double MAX_AMOUNT = 1000;
13 public static final int DELAY = 10;
14
15 public static void main(String[] args)
16 {
17 Bank bank = new Bank(NACCOUNTS, INITIAL_BALANCE);
18 for (int i = 0; i < NACCOUNTS; i++)
19 {
20 int fromAccount = i;
21 Runnable r = () -> {
22 try
23 {
24 while (true)
25 {
26 int toAccount = (int) (bank.size() * Math.random());
27 double amount = MAX_AMOUNT * Math.random();
28 bank.transfer(fromAccount, toAccount, amount);
29 Thread.sleep((int) (DELAY * Math.random()));
30 }
31 }
32 catch (InterruptedException e)
33 {
34 }
35 };
36 Thread t = new Thread(r);
37 t.start();
38 }
39 }
40 }
Listing 14.6 unsynch/Bank.java
1 package unsynch;
2
3 import java.util.*;
4
5 /**
6 * A bank with a number of bank accounts.
7 * @version 1.30 2004-08-01
8 * @author Cay Horstmann
9 */
10 public class Bank
11 {
12 private final double[] accounts;
13
14 /**
15 * Constructs the bank.
16 * @param n the number of accounts
17 * @param initialBalance the initial balance for each account
18 */
19 public Bank(int n, double initialBalance)
20 {
21 accounts = new double[n];
22 Arrays.fill(accounts, initialBalance);
23 }
24
25 /**
26 * Transfers money from one account to another.
27 * @param from the account to transfer from
28 * @param to the account to transfer to
29 * @param amount the amount to transfer
30 */
31 public void transfer(int from, int to, double amount)
32 {
33 if (accounts[from] < amount) return;
34 System.out.print(Thread.currentThread());
35 accounts[from] -= amount;
36 System.out.printf(" %10.2f from %d to %d", amount, from, to);
37 accounts[to] += amount;
38 System.out.printf(" Total Balance: %10.2f%n", getTotalBalance());
39 }
40
41 /**
42 * Gets the sum of all account balances.
43 * @return the total balance
44 */
45 public double getTotalBalance()
46 {
47 double sum = 0;
48
49 for (double a : accounts)
50 sum += a;
51
52 return sum;
53 }
54
55 /**
56 * Gets the number of accounts in the bank.
57 * @return the number of accounts
58 */
59 public int size()
60 {
61 return accounts.length;
62 }
63 }
In the previous section, we ran a program in which several threads updated bank account balances. After a while, errors crept in and some amount of money was either lost or spontaneously created. This problem occurs when two threads are simultaneously trying to update an account. Suppose two threads simultaneously carry out the instruction
accounts[to] += amount;
The problem is that these are not atomic operations. The instruction might be processed as follows:
1. Load accounts[to] into a register.
2. Add amount.
3. Move the result back to accounts[to].
Now, suppose the first thread executes Steps 1 and 2, and then it is preempted. Suppose the second thread awakens and updates the same entry in the account array. Then, the first thread awakens and completes its Step 3.
That action wipes out the modification of the other thread. As a result, the total is no longer correct (see Figure 14.4).
Our test program detects this corruption. (Of course, there is a slight chance of false alarms if the thread is interrupted as it is performing the tests!)
You can actually peek at the virtual machine bytecodes that execute each statement in our class. Run the command
javap -c -v Bank
accounts[to] += amount;
aload_0
getfield #2; //Field accounts:[D
iload_2
dup2
daload
dload_3
dadd
dastore
What is the chance of this corruption occurring? We boosted the chance of observing the problem by interleaving the print statements with the statements that update the balance.
If you omit the print statements, the risk of corruption is quite a bit lower because each thread does so little work before going to sleep again, and it is unlikely that the scheduler will preempt it in the middle of the computation. However, the risk of corruption does not go away completely. If you run lots of threads on a heavily loaded machine, the program will still fail even after you have eliminated the print statements. The failure may take a few minutes or hours or days to occur. Frankly, there are few things worse in the life of a programmer than an error that only manifests itself once every few days.
The real problem is that the work of the transfer method can be interrupted in the middle. If we could ensure that the method runs to completion before the thread loses control, the state of the bank account object would never be corrupted.
There are two mechanisms for protecting a code block from concurrent access. The Java language provides a synchronized keyword for this purpose, and Java SE 5.0 introduced the ReentrantLock class. The synchronized keyword automatically provides a lock as well as an associated “condition,” which makes it powerful and convenient for most cases that require explicit locking. However, we believe that it is easier to understand the synchronized keyword after you have seen locks and conditions in isolation. The java.util.concurrent framework provides separate classes for these fundamental mechanisms, which we explain here and in Section 14.5.4, “Condition Objects,” on p. 872. Once you have understood these building blocks, we present the synchronized keyword in Section 14.5.5, “The synchronized Keyword,” on p. 878.
The basic outline for protecting a code block with a ReentrantLock is:
myLock.lock(); // a ReentrantLock object
try
{
critical section
}
finally
{
myLock.unlock(); // make sure the lock is unlocked even if an exception is thrown
}
This construct guarantees that only one thread at a time can enter the critical section. As soon as one thread locks the lock object, no other thread can get past the lock statement. When other threads call lock, they are deactivated until the first thread unlocks the lock object.
Caution
It is critically important that the unlock operation is enclosed in a finally clause. If the code in the critical section throws an exception, the lock must be unlocked. Otherwise, the other threads will be blocked forever.
Note
When you use locks, you cannot use the try-with-resources statement. First off, the unlock method isn’t called close. But even if it was renamed, the try-with-resources statement wouldn’t work. Its header expects the declaration of a new variable. But when you use a lock, you want to keep using the same variable that is shared among threads.
Let us use a lock to protect the transfer method of the Bank class.
public class Bank
{
private Lock bankLock = new ReentrantLock(); // ReentrantLock implements the Lock interface
. . .
public void transfer(int from, int to, int amount)
{
bankLock.lock();
try
{
System.out.print(Thread.currentThread());
accounts[from] -= amount;
System.out.printf(" %10.2f from %d to %d", amount, from, to);
accounts[to] += amount;
System.out.printf(" Total Balance: %10.2f%n", getTotalBalance());
}
finally
{
bankLock.unlock();
}
}
}
Suppose one thread calls transfer and gets preempted before it is done. Suppose a second thread also calls transfer. The second thread cannot acquire the lock and is blocked in the call to the lock method. It is deactivated and must wait for the first thread to finish executing the transfer method. When the first thread unlocks the lock, then the second thread can proceed (see Figure 14.5).
Try it out. Add the locking code to the transfer method and run the program again. You can run it forever, and the bank balance will not become corrupted.
Note that each Bank object has its own ReentrantLock object. If two threads try to access the same Bank object, then the lock serves to serialize the access. However, if two threads access different Bank objects, each thread acquires a different lock and neither thread is blocked. This is as it should be, because the threads cannot interfere with one another when they manipulate different Bank instances.
The lock is called reentrant because a thread can repeatedly acquire a lock that it already owns. The lock has a hold count that keeps track of the nested calls to the lock method. The thread has to call unlock for every call to lock in order to relinquish the lock. Because of this feature, code protected by a lock can call another method that uses the same locks.
For example, the transfer method calls the getTotalBalance method, which also locks the bankLock object, which now has a hold count of 2. When the getTotalBalance method exits, the hold count is back to 1. When the transfer method exits, the hold count is 0, and the thread relinquishes the lock.
In general, you will want to protect blocks of code that update or inspect a shared object, so you can be assured that these operations run to completion before another thread can use the same object.
Be careful to ensure that the code in a critical section is not bypassed by throwing an exception. If an exception is thrown before the end of the section, the finally clause will relinquish the lock, but the object may be in a damaged state.
Caution
It sounds nice to be fair, but fair locks are a lot slower than regular locks. You should only enable fair locking if you truly know what you are doing and have a specific reason to consider fairness essential for your program. Even if you use a fair lock, you have no guarantee that the thread scheduler is fair. If the thread scheduler chooses to neglect a thread that has been waiting a long time for the lock, it doesn’t get the chance to be treated fairly by the lock.
Often, a thread enters a critical section only to discover that it can’t proceed until a condition is fulfilled. Use a condition object to manage threads that have acquired a lock but cannot do useful work. In this section, we introduce the implementation of condition objects in the Java library. (For historical reasons, condition objects are often called condition variables.)
Let us refine our simulation of the bank. We do not want to transfer money out of an account that does not have the funds to cover the transfer. Note that we cannot use code like
if (bank.getBalance(from) >= amount)
bank.transfer(from, to, amount);
It is entirely possible that the current thread will be deactivated between the successful outcome of the test and the call to transfer.
if (bank.getBalance(from) >= amount)
// thread might be deactivated at this point
bank.transfer(from, to, amount);
By the time the thread is running again, the account balance may have fallen below the withdrawal amount. You must make sure that no other thread can modify the balance between the test and the transfer action. You do so by protecting both the test and the transfer action with a lock:
public void transfer(int from, int to, int amount)
{
bankLock.lock();
try
{
while (accounts[from] < amount)
{
// wait
. . .
}
// transfer funds
. . .
}
finally
{
bankLock.unlock();
}
}
Now, what do we do when there is not enough money in the account? We wait until some other thread has added funds. But this thread has just gained exclusive access to the bankLock, so no other thread has a chance to make a deposit. This is where condition objects come in.
A lock object can have one or more associated condition objects. You obtain a condition object with the newCondition method. It is customary to give each condition object a name that evokes the condition that it represents. For example, here we set up a condition object to represent the “sufficient funds” condition.
class Bank
{
private Condition sufficientFunds;
. . .
public Bank()
{
. . .
sufficientFunds = bankLock.newCondition();
}
}
If the transfer method finds that sufficient funds are not available, it calls
sufficientFunds.await();
The current thread is now deactivated and gives up the lock. This lets in another thread that can, we hope, increase the account balance.
There is an essential difference between a thread that is waiting to acquire a lock and a thread that has called await. Once a thread calls the await method, it enters a wait set for that condition. The thread is not made runnable when the lock is available. Instead, it stays deactivated until another thread has called the signalAll method on the same condition.
When another thread has transferred money, it should call
sufficientFunds.signalAll();
This call reactivates all threads waiting for the condition. When the threads are removed from the wait set, they are again runnable and the scheduler will eventually activate them again. At that time, they will attempt to reenter the object. As soon as the lock is available, one of them will acquire the lock and continue where it left off, returning from the call to await.
At this time, the thread should test the condition again. There is no guarantee that the condition is now fulfilled—the signalAll method merely signals to the waiting threads that it may be fulfilled at this time and that it is worth checking for the condition again.
Note
In general, a call to await should be inside a loop of the form
while (!(ok to proceed))
condition.await();
It is crucially important that some other thread calls the signalAll method eventually. When a thread calls await, it has no way of reactivating itself. It puts its faith in the other threads. If none of them bother to reactivate the waiting thread, it will never run again. This can lead to unpleasant deadlock situations. If all other threads are blocked and the last active thread calls await without unblocking one of the others, it also blocks. No thread is left to unblock the others, and the program hangs.
When should you call signalAll? The rule of thumb is to call signalAll whenever the state of an object changes in a way that might be advantageous to waiting threads. For example, whenever an account balance changes, the waiting threads should be given another chance to inspect the balance. In our example, we call signalAll when we have finished the funds transfer.
public void transfer(int from, int to, int amount)
{
bankLock.lock();
try
{
while (accounts[from] < amount)
sufficientFunds.await();
// transfer funds
. . .
sufficientFunds.signalAll();
}
finally
{
bankLock.unlock();
}
}
Note that the call to signalAll does not immediately activate a waiting thread. It only unblocks the waiting threads so that they can compete for entry into the object after the current thread has relinquished the lock.
Another method, signal, unblocks only a single thread from the wait set, chosen at random. That is more efficient than unblocking all threads, but there is a danger. If the randomly chosen thread finds that it still cannot proceed, it becomes blocked again. If no other thread calls signal again, then the system deadlocks.
Caution
A thread can only call await, signalAll, or signal on a condition if it owns the lock of the condition.
If you run the sample program in Listing 14.7, you will notice that nothing ever goes wrong. The total balance stays at $100,000 forever. No account ever has a negative balance. (Again, press Ctrl+C to terminate the program.) You may also notice that the program runs a bit slower—this is the price you pay for the added bookkeeping involved in the synchronization mechanism.
In practice, using conditions correctly can be quite challenging. Before you start implementing your own condition objects, you should consider using one of the constructs described in Section 14.10, “Synchronizers,” on p. 934.
1 package synch;
2
3 import java.util.*;
4 import java.util.concurrent.locks.*;
5
6 /**
7 * A bank with a number of bank accounts that uses locks for serializing access.
8 * @version 1.30 2004-08-01
9 * @author Cay Horstmann
10 */
11 public class Bank
12 {
13 private final double[] accounts;
14 private Lock bankLock;
15 private Condition sufficientFunds;
16
17 /**
18 * Constructs the bank.
19 * @param n the number of accounts
20 * @param initialBalance the initial balance for each account
21 */
22 public Bank(int n, double initialBalance)
23 {
24 accounts = new double[n];
25 Arrays.fill(accounts, initialBalance);
26 bankLock = new ReentrantLock();
27 sufficientFunds = bankLock.newCondition();
28 }
29
30 /**
31 * Transfers money from one account to another.
32 * @param from the account to transfer from
33 * @param to the account to transfer to
34 * @param amount the amount to transfer
35 */
36 public void transfer(int from, int to, double amount) throws InterruptedException
37 {
38 bankLock.lock();
39 try
40 {
41 while (accounts[from] < amount)
42 sufficientFunds.await();
43 System.out.print(Thread.currentThread());
44 accounts[from] -= amount;
45 System.out.printf(" %10.2f from %d to %d", amount, from, to);
46 accounts[to] += amount;
47 System.out.printf(" Total Balance: %10.2f%n", getTotalBalance());
48 sufficientFunds.signalAll();
49 }
50 finally
51 {
52 bankLock.unlock();
53 }
54 }
55
56 /**
57 * Gets the sum of all account balances.
58 * @return the total balance
59 */
60 public double getTotalBalance()
61 {
62 bankLock.lock();
63 try
64 {
65 double sum = 0;
66
67 for (double a : accounts)
68 sum += a;
69
70 return sum;
71 }
72 finally
73 {
74 bankLock.unlock();
75 }
76 }
77
78 /**
79 * Gets the number of accounts in the bank.
80 * @return the number of accounts
81 */
82 public int size()
83 {
84 return accounts.length;
85 }
86 }
In the preceding sections, you saw how to use Lock and Condition objects. Before going any further, let us summarize the key points about locks and conditions:
• A lock protects sections of code, allowing only one thread to execute the code at a time.
• A lock manages threads that are trying to enter a protected code segment.
• A lock can have one or more associated condition objects.
• Each condition object manages threads that have entered a protected code section but that cannot proceed.
The Lock and Condition interfaces give programmers a high degree of control over locking. However, in most situations, you don’t need that control—you can use a mechanism that is built into the Java language. Ever since version 1.0, every object in Java has an intrinsic lock. If a method is declared with the synchronized keyword, the object’s lock protects the entire method. That is, to call the method, a thread must acquire the intrinsic object lock.
In other words,
public synchronized void method()
{
method body
}
is the equivalent of
public void method()
{
this.intrinsicLock.lock();
try
{
method body
}
finally { this.intrinsicLock.unlock(); }
}
For example, instead of using an explicit lock, we can simply declare the transfer method of the Bank class as synchronized.
The intrinsic object lock has a single associated condition. The wait method adds a thread to the wait set, and the notifyAll/notify methods unblock waiting threads. In other words, calling wait or notifyAll is the equivalent of
intrinsicCondition.await();
intrinsicCondition.signalAll();
The wait, notifyAll, and notify methods are final methods of the Object class. The Condition methods had to be named await, signalAll, and signal so that they don’t conflict with those methods.
For example, you can implement the Bank class in Java like this:
class Bank
{
private double[] accounts;
public synchronized void transfer(int from, int to, int amount) throws InterruptedException
{
while (accounts[from] < amount)
wait(); // wait on intrinsic object lock's single condition
accounts[from] -= amount;
accounts[to] += amount;
notifyAll(); // notify all threads waiting on the condition
}
public synchronized double getTotalBalance() { . . . }
}
As you can see, using the synchronized keyword yields code that is much more concise. Of course, to understand this code, you have to know that each object has an intrinsic lock, and that the lock has an intrinsic condition. The lock manages the threads that try to enter a synchronized method. The condition manages the threads that have called wait.
Tip
Synchronized methods are relatively straightforward. However, beginners often struggle with conditions. Before you use wait/notifyAll, you should consider using one of the constructs described in Section 14.10, “Synchronizers,” on p. 934.
It is also legal to declare static methods as synchronized. If such a method is called, it acquires the intrinsic lock of the associated class object. For example, if the Bank class has a static synchronized method, then the lock of the Bank.class object is locked when it is called. As a result, no other thread can call this or any other synchronized static method of the same class.
The intrinsic locks and conditions have some limitations. Among them:
• You cannot interrupt a thread that is trying to acquire a lock.
• You cannot specify a timeout when trying to acquire a lock.
• Having a single condition per lock can be inefficient.
What should you use in your code—Lock and Condition objects or synchronized methods? Here is our recommendation:
• It is best to use neither Lock/Condition nor the synchronized keyword. In many situations, you can use one of the mechanisms of the java.util.concurrent package that do all the locking for you. For example, in Section 14.6, “Blocking Queues,” on p. 898, you will see how to use a blocking queue to synchronize threads that work on a common task. You should also explore parallel streams—see Volume II, Chapter 1.
• If the synchronized keyword works for your situation, by all means, use it. You’ll write less code and have less room for error. Listing 14.8 shows the bank example, implemented with synchronized methods.
• Use Lock/Condition if you really need the additional power that these constructs give you.
1 package synch2;
2
3 import java.util.*;
4
5 /**
6 * A bank with a number of bank accounts that uses synchronization primitives.
7 * @version 1.30 2004-08-01
8 * @author Cay Horstmann
9 */
10 public class Bank
11 {
12 private final double[] accounts;
13
14 /**
15 * Constructs the bank.
16 * @param n the number of accounts
17 * @param initialBalance the initial balance for each account
18 */
19 public Bank(int n, double initialBalance)
20 {
21 accounts = new double[n];
22 Arrays.fill(accounts, initialBalance);
23 }
24
25 /**
26 * Transfers money from one account to another.
27 * @param from the account to transfer from
28 * @param to the account to transfer to
29 * @param amount the amount to transfer
30 */
31 public synchronized void transfer(int from, int to, double amount) throws InterruptedException
32 {
33 while (accounts[from] < amount)
34 wait();
35 System.out.print(Thread.currentThread());
36 accounts[from] -= amount;
37 System.out.printf(" %10.2f from %d to %d", amount, from, to);
38 accounts[to] += amount;
39 System.out.printf(" Total Balance: %10.2f%n", getTotalBalance());
40 notifyAll();
41 }
42
43 /**
44 * Gets the sum of all account balances.
45 * @return the total balance
46 */
47 public synchronized double getTotalBalance()
48 {
49 double sum = 0;
50
51 for (double a : accounts)
52 sum += a;
53
54 return sum;
55 }
56
57 /**
58 * Gets the number of accounts in the bank.
59 * @return the number of accounts
60 */
61 public int size()
62 {
63 return accounts.length;
64 }
65 }
java.lang.Object 1.0
• void notifyAll()
unblocks the threads that called wait on this object. This method can only be called from within a synchronized method or block. The method throws an IllegalMonitorStateException if the current thread is not the owner of the object’s lock.
unblocks one randomly selected thread among the threads that called wait on this object. This method can only be called from within a synchronized method or block. The method throws an IllegalMonitorStateException if the current thread is not the owner of the object’s lock.
• void wait()
causes a thread to wait until it is notified. This method can only be called from within a synchronized method or block. It throws an IllegalMonitorStateException if the current thread is not the owner of the object’s lock.
• void wait(long millis)
• void wait(long millis, int nanos)
causes a thread to wait until it is notified or until the specified amount of time has passed. These methods can only be called from within a synchronized method or block. They throw an IllegalMonitorStateException if the current thread is not the owner of the object’s lock.
As we just discussed, every Java object has a lock. A thread can acquire the lock by calling a synchronized method. There is a second mechanism for acquiring the lock: by entering a synchronized block. When a thread enters a block of the form
synchronized (obj) // this is the syntax for a synchronized block
{
critical section
}
then it acquires the lock for obj.
You will sometimes find “ad hoc” locks, such as
public class Bank
{
private double[] accounts;
private Object lock = new Object();
. . .
public void transfer(int from, int to, int amount)
{
synchronized (lock) // an ad-hoc lock
{
accounts[from] -= amount;
accounts[to] += amount;
}
System.out.println(. . .);
}
}
Here, the lock object is created only to use the lock that every Java object possesses.
Sometimes, programmers use the lock of an object to implement additional atomic operations—a practice known as client-side locking. Consider, for example, the Vector class, which is a list whose methods are synchronized. Now suppose we stored our bank balances in a Vector<Double>. Here is a naive implementation of a transfer method:
public void transfer(Vector<Double> accounts, int from, int to, int amount) // Error
{
accounts.set(from, accounts.get(from) - amount);
accounts.set(to, accounts.get(to) + amount);
System.out.println(. . .);
}
The get and set methods of the Vector class are synchronized, but that doesn’t help us. It is entirely possible for a thread to be preempted in the transfer method after the first call to get has been completed. Another thread may then store a different value into the same position. However, we can hijack the lock:
public void transfer(Vector<Double> accounts, int from, int to, int amount)
{
synchronized (accounts)
{
accounts.set(from, accounts.get(from) - amount);
accounts.set(to, accounts.get(to) + amount);
}
System.out.println(. . .);
}
This approach works, but it is entirely dependent on the fact that the Vector class uses the intrinsic lock for all of its mutator methods. However, is this really a fact? The documentation of the Vector class makes no such promise. You have to carefully study the source code and hope that future versions do not introduce unsynchronized mutators. As you can see, client-side locking is very fragile and not generally recommended.
Locks and conditions are powerful tools for thread synchronization, but they are not very object oriented. For many years, researchers have looked for ways to make multithreading safe without forcing programmers to think about explicit locks. One of the most successful solutions is the monitor concept that was pioneered by Per Brinch Hansen and Tony Hoare in the 1970s. In the terminology of Java, a monitor has these properties:
• A monitor is a class with only private fields.
• Each object of that class has an associated lock.
• All methods are locked by that lock. In other words, if a client calls obj.method(), then the lock for obj is automatically acquired at the beginning of the method call and relinquished when the method returns. Since all fields are private, this arrangement ensures that no thread can access the fields while another thread manipulates them.
• The lock can have any number of associated conditions.
Earlier versions of monitors had a single condition, with a rather elegant syntax. You can simply call await accounts[from] >= amount without using an explicit condition variable. However, research showed that indiscriminate retesting of conditions can be inefficient. This problem is solved with explicit condition variables, each managing a separate set of threads.
The Java designers loosely adapted the monitor concept. Every object in Java has an intrinsic lock and an intrinsic condition. If a method is declared with the synchronized keyword, it acts like a monitor method. The condition variable is accessed by calling wait/notifyAll/notify.
However, a Java object differs from a monitor in three important ways, compromising thread safety:
• Fields are not required to be private.
• Methods are not required to be synchronized.
• The intrinsic lock is available to clients.
This disrespect for security enraged Per Brinch Hansen. In a scathing review of the multithreading primitives in Java, he wrote: “It is astounding to me that Java’s insecure parallelism is taken seriously by the programming community, a quarter of a century after the invention of monitors and Concurrent Pascal. It has no merit” [Java’s Insecure Parallelism, ACM SIGPLAN Notices 34:38–45, April 1999].
Sometimes, it seems excessive to pay the cost of synchronization just to read or write an instance field or two. After all, what can go wrong? Unfortunately, with modern processors and compilers, there is plenty of room for error.
• Computers with multiple processors can temporarily hold memory values in registers or local memory caches. As a consequence, threads running in different processors may see different values for the same memory location!
• Compilers can reorder instructions for maximum throughput. Compilers won’t choose an ordering that changes the meaning of the code, but they make the assumption that memory values are only changed when there are explicit instructions in the code. However, a memory value can be changed by another thread!
If you use locks to protect code that can be accessed by multiple threads, you won’t have these problems. Compilers are required to respect locks by flushing local caches as necessary and not inappropriately reordering instructions. The details are explained in the Java Memory Model and Thread Specification developed by JSR 133 (see www.jcp.org/en/jsr/detail?id=133). Much of the specification is highly complex and technical, but the document also contains a number of clearly explained examples. A more accessible overview article by Brian Goetz is available at www.ibm.com/developerworks/library/j-jtp02244.
Note
Brian Goetz coined the following “synchronization motto”: “If you write a variable which may next be read by another thread, or you read a variable which may have last been written by another thread, you must use synchronization.”
The volatile keyword offers a lock-free mechanism for synchronizing access to an instance field. If you declare a field as volatile, then the compiler and the virtual machine take into account that the field may be concurrently updated by another thread.
For example, suppose an object has a boolean flag done that is set by one thread and queried by another thread. As we already discussed, you can use a lock:
private boolean done;
public synchronized boolean isDone() { return done; }
public synchronized void setDone() { done = true; }
Perhaps it is not a good idea to use the intrinsic object lock. The isDone and setDone methods can block if another thread has locked the object. If that is a concern, one can use a separate lock just for this variable. But this is getting to be a lot of trouble.
In this case, it is reasonable to declare the field as volatile:
private volatile boolean done;
public boolean isDone() { return done; }
public void setDone() { done = true; }
The compiler will insert the appropriate code to ensure that a change to the done variable in one thread is visible from any other thread that reads the variable.
Caution
Volatile variables do not provide any atomicity. For example, the method
public void flipDone() { done = !done; } // not atomic
is not guaranteed to flip the value of the field. There is no guarantee that the reading, flipping, and writing is uninterrupted.
As you saw in the preceding section, you cannot safely read a field from multiple threads unless you use locks or the volatile modifier.
There is one other situation in which it is safe to access a shared field—when it is declared final. Consider
final Map<String, Double> accounts = new HashMap<>();
Other threads get to see the accounts variable after the constructor has finished.
Without using final, there would be no guarantee that other threads would see the updated value of accounts—they might all see null, not the constructed HashMap.
Of course, the operations on the map are not thread safe. If multiple threads mutate and read the map, you still need synchronization.
You can declare shared variables as volatile provided you perform no operations other than assignment.
There are a number of classes in the java.util.concurrent.atomic package that use efficient machine-level instructions to guarantee atomicity of other operations without using locks. For example, the AtomicInteger class has methods incrementAndGet and decrementAndGet that atomically increment or decrement an integer. For example, you can safely generate a sequence of numbers like this:
public static AtomicLong nextNumber = new AtomicLong();
// In some thread...
long id = nextNumber.incrementAndGet();
The incrementAndGet method atomically increments the AtomicLong and returns the post-increment value. That is, the operations of getting the value, adding 1, setting it, and producing the new value cannot be interrupted. It is guaranteed that the correct value is computed and returned, even if multiple threads access the same instance concurrently.
There are methods for atomically setting, adding, and subtracting values, but if you want to make a more complex update, you have to use the compareAndSet method. For example, suppose you want to keep track of the largest value that is observed by different threads. The following won’t work:
public static AtomicLong largest = new AtomicLong();
// In some thread...
largest.set(Math.max(largest.get(), observed)); // Error--race condition!
This update is not atomic. Instead, compute the new value and use compareAndSet in a loop:
do {
oldValue = largest.get();
newValue = Math.max(oldValue, observed);
} while (!largest.compareAndSet(oldValue, newValue));
If another thread is also updating largest, it is possible that it has beat this thread to it. Then compareAndSet will return false without setting the new value. In that case, the loop tries again, reading the updated value and trying to change it. Eventually, it will succeed replacing the existing value with the new one. This sounds tedious, but the compareAndSet method maps to a processor operation that is faster than using a lock.
In Java SE 8, you don’t have to write the loop boilerplate any more. Instead, you provide a lambda expression for updating the variable, and the update is done for you. In our example, we can call
largest.updateAndGet(x -> Math.max(x, observed));
or
largest.accumulateAndGet(observed, Math::max);
The accumulateAndGet method takes a binary operator that is used to combine the atomic value and the supplied argument.
There are also methods getAndUpdate and getAndAccumulate that return the old value.
These methods are also provided for the classes AtomicInteger, AtomicIntegerArray, AtomicIntegerFieldUpdater, AtomicLongArray, AtomicLongFieldUpdater, AtomicReference, AtomicReferenceArray, and AtomicReferenceFieldUpdater.
When you have a very large number of threads accessing the same atomic values, performance suffers because the optimistic updates require too many retries. Java SE 8 provides classes LongAdder and LongAccumulator to solve this problem. A LongAdder is composed of multiple variables whose collective sum is the current value. Multiple threads can update different summands, and new summands are automatically provided when the number of threads increases. This is efficient in the common situation where the value of the sum is not needed until after all work has been done. The performance improvement can be substantial.
If you anticipate high contention, you should simply use a LongAdder instead of an AtomicLong. The method names are slightly different. Call increment to increment a counter or add to add a quantity, and sum to retrieve the total.
final LongAdder adder = new LongAdder();
for (. . .)
pool.submit(() -> {
while (. . .) {
. . .
if (. . .) adder.increment();
}
});
. . .
long total = adder.sum());
Note
Of course, the increment method does not return the old value. Doing that would undo the efficiency gain of splitting the sum into multiple summands.
The LongAccumulator generalizes this idea to an arbitrary accumulation operation. In the constructor, you provide the operation, as well as its neutral element. To incorporate new values, call accumulate. Call get to obtain the current value. The following has the same effect as a LongAdder:
LongAccumulator adder = new LongAccumulator(Long::sum, 0);
// In some thread...
adder.accumulate(value);
Internally, the accumulator has variables a1, a2,. . .,an. Each variable is initialized with the neutral element (0 in our example).
When accumulate is called with value v, then one of them is atomically updated as ai = ai op v, where op is the accumulation operation written in infix form. In our example, a call to accumulate computes ai = ai + v for some i.
The result of get is a1 op a2 op ... op an. In our example, that is the sum of the accumulators, a1 + a2 + ... + an.
If you choose a different operation, you can compute maximum or minimum. In general, the operation must be associative and commutative. That means that the final result must be independent of the order in which the intermediate values were combined.
There are also DoubleAdder and DoubleAccumulator that work in the same way, except with double values.
Locks and conditions cannot solve all problems that might arise in multithreading. Consider the following situation:
1. Account 1: $200
2. Account 2: $300
3. Thread 1: Transfer $300 from Account 1 to Account 2
4. Thread 2: Transfer $400 from Account 2 to Account 1
As Figure 14.6 indicates, Threads 1 and 2 are clearly blocked. Neither can proceed because the balances in Accounts 1 and 2 are insufficient.
It is possible that all threads get blocked because each is waiting for more money. Such a situation is called a deadlock.
In our program, a deadlock cannot occur for a simple reason. Each transfer amount is for, at most, $1,000. Since there are 100 accounts and a total of $100,000 in them, at least one of the accounts must have must have at least $1,000 at any time. The thread moving money out of that account can therefore proceed.
But if you change the run method of the threads to remove the $1,000 transaction limit, deadlocks can occur quickly. Try it out. Set NACCOUNTS to 10. Construct each transfer runnable with a max value of 2 * INITIAL_BALANCE and run the program. The program will run for a while and then hang.
Tip
When the program hangs, press Ctrl+\. You will get a thread dump that lists all threads. Each thread has a stack trace, telling you where it is currently blocked. Alternatively, run jconsole, as described in Chapter 7, and consult the Threads panel (see Figure 14.7).
Another way to create a deadlock is to make the ith thread responsible for putting money into the ith account, rather than for taking it out of the ith account. In this case, there is a chance that all threads will gang up on one account, each trying to remove more money from it than it contains. Try it out. In the SynchBankTest program, turn to the run method of the TransferRunnable class. In the call to transfer, flip fromAccount and toAccount. Run the program and see how it deadlocks almost immediately.
Here is another situation in which a deadlock can occur easily: Change the signalAll method to signal in the SynchBankTest program. You will find that the program eventually hangs. (Again, it is best to set NACCOUNTS to 10 to observe the effect more quickly.) Unlike signalAll, which notifies all threads that are waiting for added funds, the signal method unblocks only one thread. If that thread can’t proceed, all threads can be blocked. Consider the following sample scenario of a developing deadlock:
1. Account 1: $1,990
2. All other accounts: $990 each
3. Thread 1: Transfer $995 from Account 1 to Account 2
4. All other threads: Transfer $995 from their account to another account
Clearly, all threads but Thread 1 are blocked, because there isn’t enough money in their accounts.
Thread 1 proceeds. Afterward, we have the following situation:
1. Account 1: $995
2. Account 2: $1,985
3. All other accounts: $990 each
Then, Thread 1 calls signal. The signal method picks a thread at random to unblock. Suppose it picks Thread 3. That thread is awakened, finds that there isn’t enough money in its account, and calls await again. But Thread 1 is still running. A new random transaction is generated, say,
1. Thread 1: Transfer $997 from Account 1 to Account 2
Now, Thread 1 also calls await, and all threads are blocked. The system has deadlocked.
The culprit here is the call to signal. It only unblocks one thread, and it may not pick the thread that is essential to make progress. (In our scenario, Thread 2 must proceed to take money out of Account 2.)
Unfortunately, there is nothing in the Java programming language to avoid or break these deadlocks. You must design your program to ensure that a deadlock situation cannot occur.
In the preceding sections, we discussed the risks of sharing variables between threads. Sometimes, you can avoid sharing by giving each thread its own instance, using the ThreadLocal helper class. For example, the SimpleDateFormat class is not thread safe. Suppose we have a static variable
public static final SimpleDateFormat dateFormat = new SimpleDateFormat("yyyy-MM-dd");
If two threads execute an operation such as
String dateStamp = dateFormat.format(new Date());
then the result can be garbage since the internal data structures used by the dateFormat can be corrupted by concurrent access. You could use synchronization, which is expensive, or you could construct a local SimpleDateFormat object whenever you need it, but that is also wasteful.
To construct one instance per thread, use the following code:
public static final ThreadLocal<SimpleDateFormat> dateFormat =
ThreadLocal.withInitial(() -> new SimpleDateFormat("yyyy-MM-dd"));
To access the actual formatter, call
String dateStamp = dateFormat.get().format(new Date());
The first time you call get in a given thread, the lambda in the constructor is called. From then on, the get method returns the instance belonging to the current thread.
A similar problem is the generation of random numbers in multiple threads. The java.util.Random class is thread safe. But it is still inefficient if multiple threads need to wait for a single shared generator.
You could use the ThreadLocal helper to give each thread a separate generator, but Java SE 7 provides a convenience class for you. Simply make a call such as
int random = ThreadLocalRandom.current().nextInt(upperBound);
The call ThreadLocalRandom.current() returns an instance of the Random class that is unique to the current thread.
A thread blocks indefinitely when it calls the lock method to acquire a lock that is owned by another thread. You can be more cautious about acquiring a lock. The tryLock method tries to acquire a lock and returns true if it was successful. Otherwise, it immediately returns false, and the thread can go off and do something else.
if (myLock.tryLock())
{
// now the thread owns the lock
try { . . . }
finally { myLock.unlock(); }
}
else
// do something else
You can call tryLock with a timeout parameter, like this:
if (myLock.tryLock(100, TimeUnit.MILLISECONDS)) . . .
TimeUnit is an enumeration with values SECONDS, MILLISECONDS, MICROSECONDS, and NANOSECONDS.
The lock method cannot be interrupted. If a thread is interrupted while it is waiting to acquire a lock, the interrupted thread continues to be blocked until the lock is available. If a deadlock occurs, then the lock method can never terminate.
However, if you call tryLock with a timeout, an InterruptedException is thrown if the thread is interrupted while it is waiting. This is clearly a useful feature because it allows a program to break up deadlocks.
You can also call the lockInterruptibly method. It has the same meaning as tryLock with an infinite timeout.
When you wait on a condition, you can also supply a timeout:
myCondition.await(100, TimeUnit.MILLISECONDS))
The await method returns if another thread has activated this thread by calling signalAll or signal, or if the timeout has elapsed, or if the thread was interrupted.
The await methods throw an InterruptedException if the waiting thread is interrupted. In the (perhaps unlikely) case that you’d rather continue waiting, use the awaitUninterruptibly method instead.
The java.util.concurrent.locks package defines two lock classes, the ReentrantLock that we already discussed and the ReentrantReadWriteLock. The latter is useful when there are many threads that read from a data structure and fewer threads that modify it. In that situation, it makes sense to allow shared access for the readers. Of course, a writer must still have exclusive access.
Here are the steps that are necessary to use a read/write lock:
1. Construct a ReentrantReadWriteLock object:
private ReentrantReadWriteLock rwl = new ReentrantReadWriteLock();
2. Extract the read and write locks:
private Lock readLock = rwl.readLock();
private Lock writeLock = rwl.writeLock();
3. Use the read lock in all accessors:
public double getTotalBalance()
{
readLock.lock();
try { . . . }
finally { readLock.unlock(); }
}
4. Use the write lock in all mutators:
public void transfer(. . .)
{
writeLock.lock();
try { . . . }
finally { writeLock.unlock(); }
}
The initial release of Java defined a stop method that simply terminates a thread, and a suspend method that blocks a thread until another thread calls resume. The stop and suspend methods have something in common: Both attempt to control the behavior of a given thread without the thread’s cooperation.
The stop, suspend, and resume methods have been deprecated. The stop method is inherently unsafe, and experience has shown that the suspend method frequently leads to deadlocks. In this section, you will see why these methods are problematic and what you can do to avoid problems.
Let us turn to the stop method first. This method terminates all pending methods, including the run method. When a thread is stopped, it immediately gives up the locks on all objects that it has locked. This can leave objects in an inconsistent state. For example, suppose a TransferRunnable is stopped in the middle of moving money from one account to another, after the withdrawal and before the deposit. Now the bank object is damaged. Since the lock has been relinquished, the damage is observable from the other threads that have not been stopped.
When a thread wants to stop another thread, it has no way of knowing when the stop method is safe and when it leads to damaged objects. Therefore, the method has been deprecated. You should interrupt a thread when you want it to stop. The interrupted thread can then stop when it is safe to do so.
Note
Some authors claim that the stop method has been deprecated because it can cause objects to be permanently locked by a stopped thread. However, that claim is not valid. A stopped thread exits all synchronized methods it has called—technically, by throwing a ThreadDeath exception. As a consequence, the thread relinquishes the intrinsic object locks that it holds.
Next, let us see what is wrong with the suspend method. Unlike stop, suspend won’t damage objects. However, if you suspend a thread that owns a lock, then the lock is unavailable until the thread is resumed. If the thread that calls the suspend method tries to acquire the same lock, the program deadlocks: The suspended thread waits to be resumed, and the suspending thread waits for the lock.
This situation occurs frequently in graphical user interfaces. Suppose we have a graphical simulation of our bank. A button labeled Pause suspends the transfer threads, and a button labeled Resume resumes them.
pauseButton.addActionListener(event -> {
for (int i = 0; i < threads.length; i++)
threads[i].suspend(); // Don't do this
});
resumeButton.addActionListener(event -> {
for (int i = 0; i < threads.length; i++)
threads[i].resume();
});
Suppose a paintComponent method paints a chart of each account, calling a getBalances method to get an array of balances.
As you will see in Section 14.11, “Threads and Swing,” on p. 937, both the button actions and the repainting occur in the same thread, the event dispatch thread. Consider the following scenario:
1. One of the transfer threads acquires the lock of the bank object.
2. The user clicks the Pause button.
3. All transfer threads are suspended; one of them still holds the lock on the bank object.
4. For some reason, the account chart needs to be repainted.
5. The paintComponent method calls the getBalances method.
6. That method tries to acquire the lock of the bank object.
Now the program is frozen.
The event dispatch thread can’t proceed because the lock is owned by one of the suspended threads. Thus, the user can’t click the Resume button, and the threads won’t ever resume.
If you want to safely suspend a thread, introduce a variable suspendRequested and test it in a safe place of your run method—in a place where your thread doesn’t lock objects that other threads need. When your thread finds that the suspendRequested variable has been set, it should keep waiting until it becomes available again.
