18. Multithreading
Objectives
In this chapter you’ll learn:
• What threads are and why they are useful.
• How threads enable you to manage concurrent activities.
• The life cycle of a thread.
• Thread priorities and scheduling.
• To create and execute Runnables.
• Thread synchronization.
• What producer/consumer relationships are and how they are implemented with multithreading.
• To enable multiple threads to update Swing GUI components in a thread-safe manner.
• About interfaces Callable and Future, which you can use with threading to execute tasks that return results.
The most general definition of beauty...Multeity in Unity.
—Samuel Taylor Coleridge
Do not block the way of inquiry.
—Charles Sanders Peirce
A person with one watch knows what time it is; a person with two watches is never sure.
—Proverb
Learn to labor and to wait.
—Henry Wadsworth Longfellow
The world is moving so fast these days that the man who says it can’t be done is generally interrupted by someone doing it.
—Elbert Hubbard
Outline
18.1 Introduction
18.2 Thread States: Life Cycle of a Thread
18.3 Thread Priorities and Thread Scheduling
18.4 Creating and Executing Threads
18.4.1 Runnables and the Thread Class
18.4.2 Thread Management with the Executor Framework
18.5 Thread Synchronization
18.5.1 Unsynchronized Data Sharing
18.5.2 Synchronized Data Sharing—Making Operations Atomic
18.6 Producer/Consumer Relationship without Synchronization
18.7 Producer/Consumer Relationship: ArrayBlockingQueue
18.8 Producer/Consumer Relationship with Synchronization
18.9 Producer/Consumer Relationship: Bounded Buffers
18.10 Producer/Consumer Relationship: The Lock and Condition Interfaces
18.11 Multithreading with GUI
18.11.1 Performing Computations in a Worker Thread
18.11.2 Processing Intermediate Results with SwingWorker
18.12 Other Classes and Interfaces in java.util.concurrent
18.13 Wrap-Up
18.1 Introduction
It would be nice if we could focus our attention on performing only one action at a time and performing it well, but that is usually difficult to do. The human body performs a great variety of operations in parallel—or, as we’ll say throughout this chapter, concurrently. Respiration, blood circulation, digestion, thinking and walking, for example, can occur concurrently. All the senses—sight, touch, smell, taste and hearing—can be employed at once. Computers, too, can perform operations concurrently. It is common for personal computers to compile a program, send a file to a printer and receive electronic mail messages over a network concurrently. Only computers that have multiple processors can truly execute multiple instructions concurrently. Operating systems on single-processor computers create the illusion of concurrent execution by rapidly switching between activities, but on such computers only a single instruction can execute at once.
Most programming languages do not enable you to specify concurrent activities. Rather, the languages provide sequential control statements which enable you to specify that only one action at a time should be performed, with execution proceeding to the next action after the previous one has finished. Historically, concurrency has been implemented with operating system primitives available only to experienced systems programmers.
The Ada programming language, developed by the United States Department of Defense, made concurrency primitives widely available to defense contractors building military command-and-control systems. However, Ada has not been widely used in academia and industry.
Java makes concurrency available to you through the language and APIs. You specify that an application contains separate threads of execution, where each thread has its own method-call stack and program counter, allowing it to execute concurrently with other threads while sharing application-wide resources such as memory with these other threads. This capability, called multithreading, is not available in the core C and C++ languages, which influenced the design of Java.
Performance Tip 18.1
A problem with single-threaded applications that can lead to poor responsiveness is that lengthy activities must complete before others can begin. In a multithreaded application, threads can be distributed across multiple processors (if available) so that multiple tasks execute concurrently and the application can operate more efficiently. Multithreading can also increase performance on single-processor systems that simulate concurrency—when one thread cannot proceed (because, for example, it is waiting for the result of an I/O operation), another can use the processor.
Unlike languages that do not have built-in multithreading capabilities (such as C and C++) and must therefore make nonportable calls to operating system multithreading primitives, Java includes multithreading primitives as part of the language itself and as part of its libraries. This facilitates manipulating threads in a portable manner across platforms.
We’ll discuss many applications of concurrent programming. For example, when downloading a large file (e.g., an image, an audio clip or a video clip) over the Internet, the user may not want to wait until the entire clip downloads before starting the playback. To solve this problem, we can put multiple threads to work—one to download the clip, and another to play it. These activities proceed concurrently. To avoid choppy playback, we synchronize (coordinate the actions of) the threads so that the player thread doesn’t begin until there is a sufficient amount of the clip in memory to keep the player thread busy.
The Java Virtual Machine (JVM) uses threads as well. In addition to creating threads to run a program, the JVM also may create threads for performing housekeeping tasks such as garbage collection.
Writing multithreaded programs can be tricky. Although the human mind can perform functions concurrently, people find it difficult to jump between parallel trains of thought. To see why multithreaded programs can be difficult to write and understand, try the following experiment: Open three books to page 1, and try reading the books concurrently. Read a few words from the first book, then a few from the second, then a few from the third, then loop back and read the next few words from the first book, and so on. After this experiment, you’ll appreciate many of the challenges of multithreading—switching between the books, reading briefly, remembering your place in each book, moving the book you’re reading closer so that you can see it and pushing the books you are not reading aside—and, amid all this chaos, trying to comprehend the content of the books!
Programming concurrent applications is a difficult and error-prone undertaking. If you find that you must use synchronization in a program, you should follow some simple guidelines. First, use existing classes from the Java API (such as the ArrayBlockingQueue class we discuss in Section 18.7, Producer/Consumer Relationship: ArrayBlockingQueue) that manage synchronization for you. The classes in the Java API are written by experts, have been fully tested and debugged, operate efficiently and help you avoid common traps and pitfalls. Second, if you find that you need more custom functionality than that provided in the Java APIs, you should use the synchronized keyword and Object methods wait, notify and notifyAll (discussed in Section 18.5 and Section 18.8). Finally, if you need even more complex capabilities, then you should use the Lock and Condition interfaces that are introduced in Section 18.10.
The Lock and Condition interfaces should be used only by advanced programmers who are familiar with the common traps and pitfalls of concurrent programming. We explain these topics in this chapter for several reasons—they provide a solid basis for understanding how concurrent applications synchronize access to shared memory; the concepts are important to understand, even if an application does not use these tools explicitly; and by showing you the complexity involved in using these low-level features, we hope to impress upon you the importance of using prepackaged concurrency capabilities whenever possible.
18.2 Thread States: Life Cycle of a Thread
At any time, a thread is said to be in one of several thread states—illustrated in the UML state diagram in Fig. 18.1. Several of the terms in the diagram are defined in later sections.
Fig. 18.1. Thread life-cycle UML state diagram.
A new thread begins its life cycle in the new state. It remains in this state until the program starts the thread, which places it in the runnable state. A thread in the runnable state is considered to be executing its task.
Sometimes a runnable thread transitions to the waiting state while it waits for another thread to perform a task. A waiting thread transitions back to the runnable state only when another thread notifies the waiting thread to continue executing.
A runnable thread can enter the timed waiting state for a specified interval of time. It transitions back to the runnable state when that time interval expires or when the event it is waiting for occurs. Timed waiting and waiting threads cannot use a processor, even if one is available. A runnable thread can transition to the timed waiting state if it provides an optional wait interval when it is waiting for another thread to perform a task. Such a thread returns to the runnable state when it is notified by another thread or when the timed interval expires—whichever comes first. Another way to place a thread in the timed waiting state is to put a runnable thread to sleep. A sleeping thread remains in the timed waiting state for a designated period of time (called a sleep interval), after which it returns to the runnable state. Threads sleep when they momentarily do not have work to perform. For example, a word processor may contain a thread that periodically backs up (i.e., writes a copy of) the current document to disk for recovery purposes. If the thread did not sleep between successive backups, it would require a loop in which it continually tested whether it should write a copy of the document to disk. This loop would consume processor time without performing productive work, thus reducing system performance. In this case, it is more efficient for the thread to specify a sleep interval (equal to the period between successive backups) and enter the timed waiting state. This thread is returned to the runnable state when its sleep interval expires, at which point it writes a copy of the document to disk and reenters the timed waiting state.
A runnable thread transitions to the blocked state when it attempts to perform a task that cannot be completed immediately and it must temporarily wait until that task completes. For example, when a thread issues an input/output request, the operating system blocks the thread from executing until that I/O request completes—at that point, the blocked thread transitions to the runnable state, so it can resume execution. A blocked thread cannot use a processor, even if one is available.
A runnable thread enters the terminated state (sometimes called the dead state) when it successfully completes its task or otherwise terminates (perhaps due to an error). In the UML state diagram of Fig. 18.1, the terminated state is followed by the UML final state (the bull’s-eye symbol) to indicate the end of the state transitions.
At the operating system level, Java’s runnable state typically encompasses two separate states (Fig. 18.2). The operating system hides these states from the Java Virtual Machine (JVM), which sees only the runnable state. When a thread first transitions to the runnable state from the new state, the thread is in the ready state. A ready thread enters the running state (i.e., begins executing) when the operating system assigns the thread to a processor—also known as dispatching the thread. In most operating systems, each thread is given a small amount of processor time—called a quantum or timeslice—with which to perform its task. (Deciding how large the quantum should be is a key topic in operating systems courses.) When its quantum expires, the thread returns to the ready state and the operating system assigns another thread to the processor (see Section 18.3). Transitions between the ready and running states are handled solely by the operating system. The JVM does not “see” the transitions—it simply views the thread as being runnable and leaves it up to the operating system to transition the thread between ready and running. The process that an operating system uses to determine which thread to dispatch is called thread scheduling and is dependent on thread priorities (discussed in the next section).
Fig. 18.2. Operating system’s internal view of Java’s runnable state.
18.3 Thread Priorities and Thread Scheduling
Every Java thread has a thread priority that helps the operating system determine the order in which threads are scheduled. Java priorities range between MIN_PRIORITY (a constant of 1) and MAX_PRIORITY (a constant of 10). By default, every thread is given priority NORM_PRIORITY (a constant of 5). Each new thread inherits the priority of the thread that created it. Informally, higher-priority threads are more important to a program and should be allocated processor time before lower-priority threads. However, thread priorities cannot guarantee the order in which threads execute.
[Note: The constants (MAX_PRIORITY, MIN_PRIORITY and NORM_PRIORITY) are declared in the Thread class. It is recommended that you do not explicitly create and use Thread objects to implement concurrency, but rather use the Executor interface (which is described in Section 18.4.2). The Thread class contains some useful static methods, which we discuss later in the chapter.]
Most operating systems support timeslicing, which enables threads of equal priority to share a processor. Without timeslicing, each thread in a set of equal-priority threads runs to completion (unless it leaves the runnable state and enters the waiting or timed waiting state, or gets interrupted by a higher-priority thread) before other threads of equal priority get a chance to execute. With timeslicing, even if a thread has not finished executing when its quantum expires, the processor is taken away from the thread and given to the next thread of equal priority, if one is available.
An operating system’s thread scheduler determines which thread runs next. One simple thread scheduler implementation keeps the highest-priority thread running at all times and, if there is more than one highest-priority thread, ensures that all such threads execute for a quantum each in round-robin fashion. Figure 18.3 illustrates a multilevel priority queue for threads. In the figure, assuming a single-processor computer, threads A and B each execute for a quantum in round-robin fashion until both threads complete execution. This means that A gets a quantum of time to run. Then B gets a quantum. Then A gets another quantum. Then B gets another quantum. This continues until one thread completes. The processor then devotes all its power to the thread that remains (unless another priority 10 thread becomes ready). Next, thread C runs to completion (assuming that no higher-priority threads arrive). Threads D, E and F each execute for a quantum in round-robin fashion until they all complete execution (again assuming that no higher-priority threads arrive). This process continues until all threads run to completion.
Fig. 18.3. Thread-priority scheduling.
When a higher-priority thread enters the ready state, the operating system generally preempts the currently running thread (an operation known as preemptive scheduling). Depending on the operating system, higher-priority threads could postpone—possibly indefinitely—the execution of lower-priority threads. Such indefinite postponement is sometimes referred to more colorfully as starvation.
Java provides higher-level concurrency utilities to hide some of this complexity and make multithreaded programs less error prone. Thread priorities are used behind the scenes to interact with the operating system, but most programmers who use Java multithreading will not be concerned with setting and adjusting thread priorities.
Portability Tip 18.1
Thread scheduling is platform dependent—the behavior of a multithreaded program could vary across different Java implementations.
When designing multithreaded programs consider the threading capabilities of all the platforms on which the programs will execute. Using priorities other than the default will make your programs’ behavior platform specific. If portability is your goal, don’t adjust thread priorities.
18.4 Creating and Executing Threads
The preferred means of creating multithreaded Java applications is by implementing the Runnable interface (of package java.lang). A Runnable object represents a “task” that can execute concurrently with other tasks. The Runnable interface declares a single method, run, which contains the code that defines the task that a Runnable object should perform. When a thread executing a Runnable is created and started, the thread calls the Runnable object’s run method, which executes in the new thread.
18.4.1 Runnables and the Thread Class
Class PrintTask (Fig. 18.4) implements Runnable (line 5), so that multiple PrintTasks can execute concurrently. Variable sleepTime (line 7) stores a random integer value from 0 to 5 seconds created in the PrintTask constructor (line 16). Each thread running a PrintTask sleeps for the amount of time specified by sleepTime, then outputs its task’s name and a message indicating that it’s done sleeping.
Fig. 18.4. PrintTask class sleeps for a random time from 0 to 5 seconds.
A PrintTask executes when a thread calls the PrintTask’s run method. Lines 24–25 display a message indicating the name of the currently executing task and that the task is going to sleep for sleepTime milliseconds. Line 26 invokes static method sleep of class Thread to place the thread in the timed waiting state for the specified amount of time. At this point, the thread loses the processor, and the system allows another thread to execute. When the thread awakens, it reenters the runnable state. When the PrintTask is assigned to a processor again, line 35 outputs a message indicating that the task is done sleeping, then method run terminates. Note that the catch at lines 28–32 is required because method sleep might throw a (checked) InterruptedException if the sleeping thread’s interrupt method is called.
Figure 18.5 creates Thread objects to execute PrintTasks. Lines 12–14 create three threads, each of which specifies a new PrintTask to execute. Lines 19–21 call Thread method start on each of the threads—each call invokes the corresponding Runnable’s run method to execute the task. Line 23 outputs a message indicating that all of the threads’ tasks have been started and that the main method is finished executing.
Fig. 18.5. Creating and starting three threads to execute Runnables.
The code in method main executes in the main thread, a thread created by the JVM. The code in the run method of PrintTask (lines 20–36 of Fig. 18.4) executes in the threads created in lines 12–14 of Fig. 18.5. When method main terminates, the program itself continues running because there are still threads that are alive (i.e., any of the three threads we created that have not yet reached the terminated state). The program will not terminate until its last thread completes execution, at which point the JVM will also terminate.
The sample outputs for this program show each task’s name and sleep time as the thread goes to sleep. The thread with the shortest sleep time normally awakens first, indicates that it’s done sleeping and terminates. In Section 18.9, we discuss multithreading issues that could prevent the thread with the shortest sleep time from awakening first. In the first output, the main thread terminates before any of the other threads output their names and sleep times. This shows that the main thread runs to completion before any of the other threads get a chance to run. In the second output, all of the threads output their names and sleep times before the main thread terminates. This shows that the operating system allowed other threads to execute before the main thread terminated. This is an example of the round-robin scheduling we discussed in Section 18.3. Also notice that in the first example output, task3 goes to sleep first and task1 goes to sleep last, even though we started task1’s thread first. This illustrates the fact that we cannot predict the order in which threads will be scheduled, even if we know the order in which they were created and started. Finally, in each of the outputs, notice that the order in which the threads indicate that they are done sleeping matches the smallest to largest sleep times of the three threads. Although this is the reasonable and intuitive order for these threads to finish their tasks, the threads are not guaranteed to finish in this order.
18.4.2 Thread Management with the Executor Framework
Though it is possible to create threads explicitly as in Figure 18.5, it is recommended that you use the Executor interface to manage the execution of Runnable objects for you. An Executor object typically creates and manages a group of threads called a thread pool to execute Runnables. Using an Executor has many advantages over creating threads yourself. Executors can reuse existing threads to eliminate the overhead of creating a new thread for each task and can improve performance by optimizing the number of threads to ensure that the processor stays busy, without creating so many threads that the application runs out of resources.
The Executor interface declares a single method named execute which accepts a Runnable as an argument. The Executor assigns every Runnable passed to its execute method to one of the available threads in the thread pool. If there are no available threads, the Executor creates a new thread or waits for a thread to become available and assigns that thread the Runnable that was passed to method execute.
Interface ExecutorService (of package java.util.concurrent) is an interface that extends Executor and declares a number of other methods for managing the life cycle of an Executor. An object that implements the ExecutorService interface can be created using static methods declared in class Executors (of package java.util.concurrent). We use interface ExecutorService and a method of class Executors in the next application, which executes three tasks.
Figure 18.6 uses an ExecutorService object to manage threads that execute PrintTasks. Method main (lines 8–29) creates and names three PrintTask objects (lines 11–13). Line 18 uses Executors method newCachedThreadPool to obtain an ExecutorService that creates new threads as they are needed by the application. These threads are used by threadExecutor to execute the Runnables.
Fig. 18.6. Using an ExecutorService to execute Runnables.
Lines 21–23 each invoke the ExecutorService’s execute method. This method executes the Runnable passed to it as an argument (in this case a PrintTask) some time in the future. The specified task may execute in one of the threads in the ExecutorService’s thread pool, in a new thread created to execute it, or in the thread that called the execute method; the ExecutorService manages these details. Method execute returns immediately from each invocation—the program does not wait for each PrintTask to finish. Line 26 calls ExecutorService method shutdown, which notifies the ExecutorService to stop accepting new tasks, but continues executing tasks that have already been submitted. Once all of the previously submitted Runnables have completed, the threadExecutor terminates. Line 28 outputs a message indicating that the tasks were started and the main thread is finishing its execution. The sample outputs for this program are similar to those of the previous program and again demonstrate the nondeterminism of thread scheduling.
18.5 Thread Synchronization
When multiple threads share an object and that object is modified by one or more of the threads, indeterminate results may occur (as we’ll see in the examples) unless access to the shared object is managed properly. If one thread is in the process of updating a shared object and another thread also tries to update it, it is unclear which thread’s update takes effect. When this happens, the program’s behavior cannot be trusted—sometimes the program will produce the correct results, and sometimes it won’t. In either case, there will be no indication that the shared object was manipulated incorrectly.
The problem can be solved by giving only one thread at a time exclusive access to code that manipulates the shared object. During that time, other threads desiring to manipulate the object are kept waiting. When the thread with exclusive access to the object finishes manipulating it, one of the threads that was waiting is allowed to proceed. This process, called thread synchronization, coordinates access to shared data by multiple concurrent threads. By synchronizing threads in this manner, you can ensure that each thread accessing a shared object excludes all other threads from doing so simultaneously—this is called mutual exclusion.
A common way to perform synchronization is to use Java’s built-in monitors. Every object has a monitor and a monitor lock (or intrinsic lock). The monitor ensures that its object’s monitor lock is held by a maximum of only one thread at any time. Monitors and monitor locks can thus be used to enforce mutual exclusion. If an operation requires the executing thread to hold a lock while the operation is performed, a thread must acquire the lock before proceeding with the operation. Other threads attempting to perform an operation that requires the same lock will be blocked until the first thread releases the lock, at which point the blocked threads may attempt to acquire the lock and proceed with the operation.
To specify that a thread must hold a monitor lock to execute a block of code, the code should be placed in a synchronized statement. Such code is said to be guarded by the monitor lock; a thread must acquire the lock to execute the synchronized statements. The monitor allows only one thread at a time to execute statements within synchronized blocks that lock on the same object, as only one thread at a time can hold the monitor lock. The synchronized statements are declared using the synchronized keyword:
where object is the object whose monitor lock will be acquired; object is normally this if it is the object in which the synchronized statement appears. If several synchronized statements are trying to execute on an object at the same time, only one of them may be active on the object—all the other threads attempting to enter a synchronized statement on the same object are placed in the blocked state.
When a synchronized statement finishes executing, the object’s monitor lock is released and the operating system can allow one of the blocked threads attempting to enter a synchronized statement to acquire the lock to proceed. Java also allows synchronized methods. Such a method is equivalent to a synchronized statement enclosing the entire body of a method and using this as the object whose monitor lock will be acquired. You can specify a method as synchronized by placing the synchronized keyword before the method’s return type in the method declaration.
18.5.1 Unsynchronized Data Sharing
We now present an example to illustrate the dangers of sharing an object across threads without proper synchronization. In this example, two Runnables maintain references to a single integer array. Each Runnable writes five values to the array, then terminates. This may seem harmless, but it can result in errors if the array is manipulated without synchronization.
Class SimpleArray
An object of class SimpleArray (Fig. 18.7) will be shared across multiple threads. SimpleArray will enable those threads to place int values into array (declared at line 7). Line 8 initializes variable writeIndex, which will be used to determine the array element that should be written to next. The constructor (lines 12–15) creates an integer array of the desired size.
Fig. 18.7. Class that manages an integer array to be shared by multiple threads.
Method add (lines 18–39) allows new values to be inserted at the end of the array. Line 20 stores the current writeIndex value. Line 25 puts the thread that invokes add to sleep for a random interval from 0 to 499 milliseconds. This is done to make the problems associated with unsynchronized access to shared data more obvious. After the thread is done sleeping, line 33 inserts the value passed to add into the array at the element specified by position. Lines 34–35 output a message indicating the executing thread’s name, the value that was inserted in the array and where it was inserted. Line 37 increments writeIndex so that the next call to add will insert a value in the array’s next element. Lines 42–50 override method toString to create a String representation of the array’s contents.
Class ArrayWriter
Class ArrayWriter (Fig. 18.8) implements the interface Runnable to define a task for inserting values in a SimpleArray object. The constructor (lines 10–14) takes two arguments—an integer value, which is the first value this task will insert in the SimpleArray object, and a reference to the SimpleArray object. Line 20 invokes method add on the SimpleArray object. The task completes after three consecutive integers beginning with startValue are added to the SimpleArray object.
Fig. 18.8. Adds integers to an array shared with other Runnables.
Class SharedArrayTest
Class SharedArrayTest executes two ArrayWriter tasks that add values to a single SimpleArray object. Line 12 constructs a six-element SimpleArray object. Lines 15–16 create two new ArrayWriter tasks, one that places the values 1–3 in the SimpleArray object, and one that places the values 11–13. Lines 19–21 create an ExecutorService and execute the two ArrayWriters. Line 23 invokes the ExecutorService’s shutDown method to prevent additional tasks from starting and to enable the application to terminate when the currently executing tasks complete execution.
Recall that ExecutorService method shutdown returns immediately. Thus any code that appears after the call to ExecutorService method shutdown in line 23 will continue executing as long as the main thread is still assigned to a processor. We’d like to output the SimpleArray object to show you the results after the threads complete their tasks. So, we need the program to wait for the threads to complete before main outputs the SimpleArray object’s contents. Interface ExecutorService provides the awaitTermination method for this purpose. This method returns control to its caller either when all tasks executing in the ExecutorService complete or when the specified timeout elapses. If all tasks are completed before awaitTermination times out, this method returns true; otherwise it returns false. The two arguments to awaitTermination represent a timeout value and a unit of measure specified with a constant from class TimeUnit (in this case, TimeUnit.MINUTES). In this example, if both tasks complete before awaitTermination times out, line 32 displays the SimpleArray object’s contents. Otherwise, lines 34–35 print a message indicating that the tasks did not finish executing before awaitTermination timed out.
The output in Fig. 18.9 demonstrates the problems (highlighted in the output) that can be caused by failure to synchronize access to shared data. The value 1 was written to element 0, then overwritten later by the value 11. Also, when writeIndex was incremented to 3, nothing was written to that element, as indicated by the 0 in that element of the printed array.
Fig. 18.9. Executes two Runnables to insert values in a shared array.
Recall that we have added calls to Thread method sleep between operations on the shared data to emphasize the unpredictability of thread scheduling and increase the likelihood of producing erroneous output. It is important to note that even if these operations were allowed to proceed at their normal pace, you could still see errors in the program’s output. However, modern processors can handle the simple operations of the SimpleArray method add so quickly that you might not see the errors caused by the two threads executing this method concurrently, even if you tested the program dozens of times. One of the challenges of multithreaded programming is spotting the errors—they may occur so infrequently that a broken program does not produce incorrect results during testing, creating the illusion that the program is correct.
18.5.2 Synchronized Data Sharing—Making Operations Atomic
The output errors of Fig. 18.9 can be attributed to the fact that the shared object, SimpleArray, is not thread safe—SimpleArray is susceptible to errors if it is accessed concurrently by multiple threads. The problem lies in method add, which stores the value of writeIndex, places a new value in that element, then increments writeIndex. Such a method would present no problem in a single-threaded program. However, if one thread obtains the value of writeIndex, there is no guarantee that another thread cannot come along and increment writeIndex before the first thread has had a chance to place a value in the array. If this happens, the first thread will be writing to the array based on a stale value of writeIndex—a value that is no longer valid. Another possibility is that one thread might obtain the value of writeIndex after another thread adds an element to the array but before writeIndex is incremented. In this case, too, the first thread would write to the array based on an invalid value for writeIndex.
SimpleArray is not thread safe because it allows any number of threads to read and modify shared data concurrently, which can cause errors. To make SimpleArray thread safe, we must ensure that no two threads can access it at the same time. We also must ensure that while one thread is in the process of storing writeIndex, adding a value to the array, and incrementing writeIndex, no other thread may read or change the value of writeIndex or modify the contents of the array at any point during these three operations. In other words, we want these three operations—storing writeIndex, writing to the array, incrementing writeIndex—to be an atomic operation, which cannot be divided into smaller suboperations. While no processor can carry out all three stages of the add method in a single clock cycle to make the operation truly atomic, we can simulate atomicity by ensuring that only one thread carries out the three operations at a time. Any other threads that need to perform the operation must wait until the first thread has finished the add operation in its entirety.
Atomicity can be achieved using the synchronized keyword. By placing our three suboperations in a synchronized statement or synchronized method, only one thread at a time will be allowed to acquire the lock and perform the operations. When that thread has completed all of the operations in the synchronized block and releases the lock, another thread may acquire the lock and begin executing the operations. This ensures that a thread executing the operations will see the actual values of the shared data and that these values will not change unexpectedly in the middle of the operations as a result of another thread’s modifying them.
Software Engineering Observation 18.1
Place all accesses to mutable data that may be shared by multiple threads inside synchronized statements or synchronized methods that synchronize on the same lock. When performing multiple operations on shared data, hold the lock for the entirety of the operation to ensure that the operation is effectively atomic.
Figure 18.10 displays class SimpleArray with the proper synchronization. Notice that it’s identical to the SimpleArray class of Fig. 18.7, except that add is now a synchronized method (line 19). So, only one thread at a time can execute this method. We reuse classes ArrayWriter (Fig. 18.8) and SharedArrayTest (Fig. 18.9) from the previous example.
Fig. 18.10. Class that manages an integer array to be shared by multiple threads with synchronization.
Line 18 declares method as synchronized, making all of the operations in this method behave as a single, atomic operation. Line 20 performs the first suboperation—storing the value of writeIndex. Line 33 defines the second suboperation, writing an element to the element at the index position. Line 37 increments writeIndex. When the method finishes executing at line 39, the executing thread releases the SimpleArray lock, making it possible for another thread to begin executing the add method.
In the synchronized add method, we print messages to the console indicating the progress of threads as they execute this method, in addition to performing the actual operations required to insert a value in the array. We do this so that the messages will be printed in the correct order, allowing you to see whether the method is properly synchronized by comparing these outputs with those of the previous, unsynchronized example. We continue to output messages from synchronized blocks in later examples for demonstration purposes; typically, however, I/O should not be performed in synchronized blocks, because it’s important to minimize the amount of time that an object is “locked.”
Performance Tip 18.2
Keep the duration of synchronized statements as short as possible while maintaining the needed synchronization. This minimizes the wait time for blocked threads. Avoid performing I/O, lengthy calculations and operations that do not require synchronization with a lock held.
Another note on thread safety: We have said that it is necessary to synchronize access to all data that may be shared across multiple threads. Actually, this synchronization is necessary only for mutable data, or data that may change in its lifetime. If the shared data will not change in a multithreaded program, then it is not possible for a thread to see old or incorrect values as a result of another thread’s manipulating that data.
When you share immutable data across threads, declare the corresponding data fields final to indicate that variables’ values will not change after they are initialized. This prevents accidental modification of the shared data later in a program, which could compromise thread safety. Labeling object references as final indicates that the reference will not change, but it does not guarantee that the object itself is immutable—this depends entirely on the properties of the object. However, it is still good practice to mark references that will not change as final, as doing so forces the object’s constructor to be atomic—the object will be fully constructed with all its fields initialized before it is accessed by the program.
Good Programming Practice 18.1
Always declare data fields that you do not expect to change as final. Primitive variables that are declared as final can safely be shared across threads. An object reference that is declared as final ensures that the object it refers to will be fully constructed and initialized before it is used by the program and prevents the reference from pointing to another object.
18.6 Producer/Consumer Relationship without Synchronization
In a producer/consumer relationship, the producer portion of an application generates data and stores it in a shared object, and the consumer portion of an application reads data from the shared object. The producer/consumer relationship separates the task of identifying work to be done from the tasks involved in actually carrying out the work. One example of a common producer/consumer relationship is print spooling. Although a printer might not be available when you want to print from an application (i.e., the producer), you can still “complete” the print task, as the data is temporarily placed on disk until the printer becomes available. Similarly, when the printer (i.e., a consumer) is available, it doesn’t have to wait until a current user wants to print. The spooled print jobs can be printed as soon as the printer becomes available. Another example of the producer/consumer relationship is an application that copies data onto CDs by placing data in a fixed-size buffer, which is emptied as the CD-RW drive “burns” the data onto the CD.
In a multithreaded producer/consumer relationship, a producer thread generates data and places it in a shared object called a buffer. A consumer thread reads data from the buffer. This relationship requires synchronization to ensure that values are produced and consumed properly. All operations on mutable data that is shared by multiple threads (e.g., the data in the buffer) must be guarded with a lock to prevent corruption, as discussed in Section 18.5. Operations on the buffer data shared by a producer and consumer thread are also state dependent—the operations should proceed only if the buffer is in the correct state. If the buffer is in a not-full state, the producer may produce; if the buffer is in a not-empty state, the consumer may consume. All operations that access the buffer must use synchronization to ensure that data is written to the buffer or read from the buffer only if the buffer is in the proper state. If the producer attempting to put the next data into the buffer determines that it is full, the producer thread should wait until there is space to write a new value. If a consumer thread finds the buffer empty or finds that the previous data has already been read, the consumer must also wait for new data to become available.
Consider how logic errors can arise if we do not synchronize access among multiple threads manipulating shared data. Our next example (Fig. 18.11–Fig. 18.15) implements a producer/consumer relationship without the proper synchronization. A producer thread writes the numbers 1 through 10 into a shared buffer—a single memory location shared between two threads (a single int variable called buffer in line 6 of Fig. 18.14 in this example). The consumer thread reads this data from the shared buffer and displays the data. The program’s output shows the values that the producer writes (produces) into the shared buffer and the values that the consumer reads (consumes) from the shared buffer.
Fig. 18.11. Buffer interface specifies methods called by Producer and Consumer.
Each value the producer thread writes to the shared buffer must be consumed exactly once by the consumer thread. However, the threads in this example erroneously are not synchronized. Therefore, data can be lost or garbled if the producer places new data into the shared buffer before the consumer reads the previous data. Also, data can be incorrectly duplicated if the consumer consumes data again before the producer produces the next value. To show these possibilities, the consumer thread in the following example keeps a total of all the values it reads. The producer thread produces values from 1 through 10. If the consumer reads each value produced once and only once, the total will be 55. However, if you execute this program several times, you’ll see that the total is not always 55 (as shown in the outputs in Fig. 18.10). To emphasize the point, the producer and consumer threads in the example each sleep for random intervals of up to three seconds between performing their tasks. Thus, we do not know when the producer thread will attempt to write a new value, or when the consumer thread will attempt to read a value.
The program consists of interface Buffer (Fig. 18.11) and four classes—Producer (Fig. 18.12), Consumer (Fig. 18.13), UnsynchronizedBuffer (Fig. 18.14) and SharedBufferTest (Fig. 18.15). Interface Buffer declares methods set (line 6) and get (line 9) that a Buffer must implement to enable the Producer thread to place a value in the Buffer and the Consumer thread to retrieve a value from the Buffer, respectively. Some programmers prefer to call these methods put and take, respectively. In subsequent examples, methods set and get will call methods that throw InterruptedExceptions. We declare each method with a throws clause here so that we don’t have to modify this interface for the later examples Figure 18.14 shows the implementation of this interface.
Fig. 18.12. Producer with a run method that inserts the values 1 to 10 in buffer.
Fig. 18.13. Consumer with a run method that loops, reading 10 values from buffer.
Class Producer (Fig. 18.12) implements the Runnable interface, allowing it to be executed as a task in a separate thread. The constructor (lines 11–14) initializes the Buffer reference sharedLocation with an object created in main (line 14 of Fig. 18.15) and passed to the constructor in the parameter shared. As we’ll see, this is an UnsynchronizedBuffer object that implements the interface Buffer without synchronizing access to the shared object. The Producer thread in this program executes the tasks specified in the method run (lines 17–39). Each iteration of the loop (lines 21–35) invokes Thread method sleep (line 25) to place the Producer thread into the timed waiting state for a random time interval between 0 and 3 seconds. When the thread awakens, line 26 passes the value of control variable count to the Buffer object’s set method to set the shared buffer’s value. Line 27 keeps a total of all the values produced so far and line 28 outputs that value. When the loop completes, lines 37–38 display a message indicating that the Producer has finished producing data and is terminating. Next, method run terminates, which indicates that the Producer completed its task. It is important to note that any method called from a Runnable’s run method (e.g., Buffer method set) executes as part of that task’s thread of execution. This fact becomes important in Section 18.7 when we add synchronization to the producer/consumer relationship.
Class Consumer (Fig. 18.13) also implements interface Runnable, allowing the Consumer to execute concurrently with the Producer. The constructor (lines 11–14) initializes Buffer reference sharedLocation with an object that implements the Buffer interface created in main (Fig. 18.15) and passed to the constructor as the parameter shared. As we’ll see, this is the same UnsynchronizedBuffer object that is used to initialize the Producer object—thus, the two threads share the same object. The Consumer thread in this program performs the tasks specified in method run (lines 17–39). The loop at lines 21–35 iterates 10 times. Each iteration invokes Thread method sleep (line 26) to put the Consumer thread into the timed waiting state for up to 3 seconds. Next, line 27 uses the Buffer’s get method to retrieve the value in the shared buffer, then adds the value to variable sum. Line 28 displays the total of all the values consumed so far. When the loop completes, lines 37–38 display a line indicating the sum of the consumed values. Then method run terminates, which indicates that the Consumer completed its task. Once both threads enter the terminated state, the program ends.
[Note: We call method sleep in method run of the Producer and Consumer classes to emphasize the fact that in multithreaded applications, it is unpredictable when each thread will perform its task and for how long it will perform the task when it has a processor. Normally, these thread scheduling issues are the job of the computer’s operating system, beyond the control of the Java developer. In this program, our thread’s tasks are quite simple—the Producer writes the values 1 to 10 to the buffer, and the Consumer reads 10 values from the buffer and adds each value to variable sum. Without the sleep method call, and if the Producer executes first, given today’s phenomenally fast processors, the Producer would likely complete its task before the Consumer got a chance to execute. If the Consumer executed first, it would likely consume garbage data ten times, then terminate before the Producer could produce the first real value.]
Class UnsynchronizedBuffer (Fig. 18.14) implements interface Buffer (line 4). An object of this class is shared between the Producer and the Consumer. Line 6 declares instance variable buffer and initializes it with the value –1. This value is used to demonstrate the case in which the Consumer attempts to consume a value before the Producer ever places a value in buffer. Methods set (lines 9–13) and get (lines 16–20) do not synchronize access to the field buffer. Method set simply assigns its argument to buffer (line 12), and method get simply returns the value of buffer (line 19).
Fig. 18.14. UnsynchronizedBuffer maintains the shared integer that is accessed by a producer thread and a consumer thread via methods set and get.
Class SharedBufferTest contains method main (lines 9–25). Line 11 creates an ExecutorService to execute the Producer and ConsumerRunnables. Line 14 creates an UnsynchronizedBuffer object and assigns it to Buffer variable sharedLocation. This object stores the data that the Producer and Consumer threads will share. Lines 23–24 create and execute the Producer and Consumer. Note that the Producer and Consumer constructors are each passed the same Buffer object (sharedLocation), so each object is initialized with a reference to the same Buffer. These lines also implicitly launch the threads and call each Runnable’s run method. Finally, line 26 calls method shutdown so that the application can terminate when the threads executing the Producer and Consumer complete their tasks. When main terminates (line 27), the main thread of execution enters the terminated state. Recall from the overview of this example that we would like the Producer to execute first and every value produced by the Producer to be consumed exactly once by the Consumer. However, when we study the first output of Fig. 18.15, we see that the Producer writes the values 1, 2 and 3 before the Consumer reads its first value (3). Therefore, the values 1 and 2 are lost. Later, the values 5, 6 and 9 are lost, while 7 and 8 are read twice and 10 is read four times. So the first output produces an incorrect total of 77, instead of the correct total of 55. In the second output, the Consumer reads the value -1 before the Producer ever writes a value. The Consumer reads the value 1 five times before the Producer writes the value 2. Meanwhile, the values 5, 7, 8, 9 and 10 are all lost—the last four because the Consumer terminates before the Producer. An incorrect consumer total of 19 is displayed. (Lines in the output where the Producer or Consumer has acted out of order are highlighted.) This example clearly demonstrates that access to a shared object by concurrent threads must be controlled carefully or a program may produce incorrect results.
Fig. 18.15. Application with two threads manipulating an unsynchronized buffer.
To solve the problems of lost and duplicated data, Section 18.7 presents an example in which we use an ArrayBlockingQueue (from package java.util.concurrent) to synchronize access to the shared object, guaranteeing that each and every value will be processed once and only once.
18.7 Producer/Consumer Relationship: ArrayBlockingQueue
One way to synchronize producer and consumer threads is to use classes from Java’s concurrency package that encapsulate the synchronization for you. Java includes the class ArrayBlockingQueue (from package java.util.concurrent)—a fully implemented, thread-safe buffer class that implements interface BlockingQueue. This interface extends the Queue interface discussed in Chapter 16 and declares methods put and take, the blocking equivalents of Queue methods offer and poll, respectively. Method put places an element at the end of the BlockingQueue, waiting if the queue is full. Method take removes an element from the head of the BlockingQueue, waiting if the queue is empty. These methods make class ArrayBlockingQueue a good choice for implementing a shared buffer. Because method put blocks until there is room in the buffer to write data, and method take blocks until there is new data to read, the producer must produce a value first, the consumer correctly consumes only after the producer writes a value and the producer correctly produces the next value (after the first) only after the consumer reads the previous (or first) value. ArrayBlockingQueue stores the shared data in an array. The array’s size is specified as an argument to the ArrayBlockingQueue constructor. Once created, an ArrayBlockingQueue is fixed in size and will not expand to accommodate extra elements.
The program in Fig. 18.16 and Fig. 18.17 demonstrates a Producer and a Consumer accessing an ArrayBlockingQueue. Class BlockingBuffer (Fig. 18.16) uses an ArrayBlockingQueue object that stores an Integer (line 7). Line 11 creates the ArrayBlockingQueue and passes 1 to the constructor so that the object holds a single value, as we did with the UnsynchronizedBuffer of Fig. 18.14. Note that lines 7 and 11 use generics, which we discussed in Chapters 15–16. We discuss multiple-element buffers in Section 18.9. Because our BlockingBuffer class uses the thread-safe ArrayBlockingQueue class to manage access to the shared buffer, BlockingBuffer is itself thread safe, even though we have not implemented the synchronization ourselves.
Fig. 18.16. Creates a synchronized buffer using an ArrayBlockingQueue.
Fig. 18.17. Two threads manipulating a blocking buffer.
BlockingBuffer implements interface Buffer (Fig. 18.11) and use classes Producer (Fig. 18.12 modified to remove line 28) and Consumer (Fig. 18.13 modified to remove line 28) from the example in Section 18.6. This approach demonstrates that the threads accessing the shared object are unaware that their buffer accesses are now synchronized. The synchronization is handled entirely in the set and get methods of BlockingBuffer by calling the synchronized ArrayBlockingQueue methods put and take, respectively. Thus, the Producer and ConsumerRunnables are properly synchronized simply by calling the shared object’s set and get methods.
Line 17 in method set (lines 15–20) calls the ArrayBlockingQueue object’s put method. This method call blocks if necessary until there is room in the buffer to place the value. Method get (lines 23–32) calls the ArrayBlockingQueue object’s take method (line 27). This method call blocks if necessary until there is an element in the buffer to remove. Lines 18–19 and 28–29 use the ArrayBlockingQueue object’s size method to display the total number of elements currently in the ArrayBlockingQueue.
Class BlockingBufferTest (Fig. 18.17) contains the main method that launches the application. Line 11 creates an ExecutorService, and line 14 creates a BlockingBuffer object and assigns its reference to the Buffer variable sharedLocation. Lines 16–17 execute the Producer and ConsumerRunnables. Line 19 calls method shutdown to end the application when the threads finish executing the Producer and Consumer tasks.
Note that while methods put and take of ArrayBlockingQueue are properly synchronized, BlockingBuffer methods set and get (Fig. 18.16) are not declared to be synchronized. Thus, the statements performed in method set—the put operation (line 19) and the output (lines 20–21)—are not atomic; nor are the statements in method get—the take operation (line 36) and the output (lines 37–38). So there is no guarantee that each output will occur immediately after the corresponding put or take operation, and the outputs may appear out of order. Even they do, the ArrayBlockingQueue object is properly synchronizing access to the data, as evidenced by the fact that the sum of values read by the consumer is always correct.
18.8 Producer/Consumer Relationship with Synchronization
The previous example showed how multiple threads can share a single-element buffer in a thread-safe manner by using the ArrayBlockingQueue class that encapsulates the synchronization necessary to protect the shared data. For educational purposes, we now explain how you can implement a shared buffer yourself using the synchronized keyword. Using an ArrayBlockingQueue will result in more maintainable and better performing code.
The first step in synchronizing access to the buffer is to implement methods get and set as synchronized methods. This requires that a thread obtain the monitor lock on the Buffer object before attempting to access the buffer data, but it does not solve the state-dependence problem associated with producer/consumer relationships. We must ensure that threads proceed with an operation only if the buffer is in the proper state. We need a way to allow our threads to wait, depending on whether certain conditions are true. In the case of placing a new item in the buffer, the condition that allows the operation to proceed is that the buffer is not full. In the case of fetching an item from the buffer, the condition that allows the operation to proceed is that the buffer is not empty. If the condition in question is true, the operation may proceed; if it is false, the thread must wait until it becomes true. When a thread is waiting on a condition, it is removed from contention for the processor, placed in the object’s wait queue and the lock it holds is released.
Methods wait, notify and notifyAll
Methods wait, notify and notifyAll, which are declared in class Object and inherited by all other classes, can be used with conditions to make threads wait when they cannot perform their tasks. If a thread obtains the monitor lock on an object, then determines that it cannot continue with its task on that object until some condition is satisfied, the thread can call Object method wait; this releases the monitor lock on the object, and the thread waits in the waiting state while the other threads try to enter the object’s synchronized statement(s) or method(s). When a thread executing a synchronized statement (or method) completes or satisfies the condition on which another thread may be waiting, it can call Object method notify to allow a waiting thread to transition to the runnable state again. At this point, the thread that was transitioned from the wait state to the runnable state can attempt to reacquire the monitor lock on the object. Even if the thread is able to reacquire the monitor lock, it still might not be able to perform its task at this time—in which case the thread will reenter the waiting state and implicitly release the monitor lock. If a thread calls notifyAll, then all the threads waiting for the monitor lock become eligible to reacquire the lock (that is, they all transition to the runnable state). Remember that only one thread at a time can obtain the monitor lock on the object—other threads that attempt to acquire the same monitor lock will be blocked until the monitor lock becomes available again (i.e., until no other thread is executing in a synchronized statement on that object).
Common Programming Error 18.1
It is an error if a thread issues a wait, a notify or a notifyAll on an object without having acquired a lock for it. This causes an IllegalMonitorStateException.
Error-Prevention Tip 18.1
It is a good practice to use notifyAll to notify waiting threads to become runnable. Doing so avoids the possibility that your program would forget about waiting threads, which would otherwise starve.
The application in Fig. 18.18 and Fig. 18.19 demonstrates a Producer and a Consumer accessing a shared buffer with synchronization. In this case, the Producer always produces a value first, the Consumer correctly consumes only after the Producer produces a value and the Producer correctly produces the next value only after the Consumer consumes the previous (or first) value. We reuse interface Buffer and classes Producer and Consumer from the example in Section 18.6. The synchronization is handled in the set and get methods of class SynchronizedBuffer (Fig. 18.18), which implements interface Buffer (line 4). Thus, the Producer’s and Consumer’s run methods simply call the shared object’s synchronized set and get methods.
Fig. 18.18. Synchronizing access to shared data using Object methods wait and notify.
Fig. 18.19. Two threads manipulating a synchronized buffer.
Fields and Methods of Class SynchronizedBuffer
Class SynchronizedBuffer contains two fields—buffer (line 6) and occupied (line 7). Method set (lines 10–30) and method get (lines 33–53) are declared as synchronized—only one thread can call either of these methods at a time on a particular SynchronizedBuffer object. Field occupied is used to determine whether it is the Producer’s or the Consumer’s turn to perform a task. This field is used in conditional expressions in both the set and get methods. If occupied is false, then buffer is empty, so the Consumer cannot read the value of buffer, but the Producer can place a value into buffer. If occupied is true, the Consumer can read a value from buffer, but the Producer cannot place a value into buffer.
Method set and the Producer Thread
When the Producer thread’s run method invokes synchronized method set, the thread implicitly attempts to acquire the SynchronizedBuffer object’s monitor lock. If the monitor lock is available, the Producer thread implicitly acquires the lock. Then the loop at lines 13–19 first determines whether occupied is true. If so, buffer is full, so line 16 outputs a message indicating that the Producer thread is trying to write a value, and line 17 invokes method displayState (lines 56–60) to output another message indicating that buffer is full and that the Producer thread is waiting until there is space. Line 18 invokes method wait (inherited from Object by SynchronizedBuffer) to place the thread that called method set (i.e., the Producer thread) in the waiting state for the SynchronizedBuffer object. The call to wait causes the calling thread to implicitly release the lock on the SynchronizedBuffer object. This is important because the thread cannot currently perform its task and because other threads (in this case, the Consumer) should be allowed to access the object to allow the condition (occupied) to change. Now another thread can attempt to acquire the SynchronizedBuffer object’s lock and invoke the object’s set or get method.
The Producer thread remains in the waiting state until another thread notifies the Producer that it may proceed—at which point the Producer returns to the runnable state and attempts to implicitly reacquire the lock on the SynchronizedBuffer object. If the lock is available, the Producer thread reacquires the lock, and method set continues executing with the next statement after the wait call. Because wait is called in a loop, the loop-continuation condition is tested again to determine whether the thread can proceed. If not, then wait is invoked again—otherwise, method set continues with the next statement after the loop.
Line 21 in method set assigns the value to the buffer. Line 25 sets occupied to true to indicate that the buffer now contains a value (i.e., a consumer can read the value, but a Producer cannot yet put another value there). Line 27 invokes method displayState to output a message indicating that the Producer is writing a new value into the buffer. Line 29 invokes method notifyAll (inherited from Object). If any threads are waiting on the SynchronizedBuffer object’s monitor lock, those threads enter the runnable state and can now attempt to reacquire the lock. Method notifyAll returns immediately, and method set then returns to the calling method (i.e., the Producer’s run method). When method set returns, it implicitly releases the monitor lock on the SynchronizedBuffer object.
Method get and the Consumer Thread
Methods get and set are implemented similarly. When the Consumer thread’s run method invokes synchronized method get, the thread attempts to acquire the monitor lock on the SynchronizedBuffer object. If the lock is available, the Consumer thread acquires it. Then the while loop at lines 36–42 determines whether occupied is false. If so, the buffer is empty, so line 39 outputs a message indicating that the Consumer thread is trying to read a value, and line 40 invokes method displayState to output a message indicating that the buffer is empty and that the Consumer thread is waiting. Line 41 invokes method wait to place the thread that called method get (i.e., the Consumer) in the waiting state for the SynchronizedBuffer object. Again, the call to wait causes the calling thread to implicitly release the lock on the SynchronizedBuffer object, so another thread can attempt to acquire the SynchronizedBuffer object’s lock and invoke the object’s set or get method. If the lock on the SynchronizedBuffer is not available (e.g., if the Producer has not yet returned from method set), the Consumer is blocked until the lock becomes available.
The Consumer thread remains in the waiting state until it is notified by another thread that it may proceed—at which point the Consumer thread returns to the runnable state and attempts to implicitly reacquire the lock on the SynchronizedBuffer object. If the lock is available, the Consumer reacquires the lock, and method get continues executing with the next statement after wait. Because wait is called in a loop, the loop-continuation condition is tested again to determine whether the thread can proceed with its execution. If not, wait is invoked again—otherwise, method get continues with the next statement after the loop. Line 46 sets occupied to false to indicate that buffer is now empty (i.e., a Consumer cannot read the value, but a Producer can place another value in buffer), line 48 calls method displayState to indicate that the consumer is reading and line 50 invokes method notifyAll. If any threads are in the waiting state for the lock on this SynchronizedBuffer object, they enter the runnable state and can now attempt to reacquire the lock. Method notifyAll returns immediately, then method get returns the value of buffer to its caller. When method get returns, the lock on the SynchronizedBuffer object is implicitly released.
Error-Prevention Tip 18.2
Always invoke method wait in a loop that tests the condition the task is waiting on. It is possible that a thread will reenter the runnable state (via a timed wait or another thread calling notifyAll) before the condition is satisfied. Testing the condition again ensures that the thread will not erroneously execute if it was notified early.
Testing Class SynchronizedBuffer
Class SharedBufferTest2 (Fig. 18.19) is similar to class SharedBufferTest (Fig. 18.15). SharedBufferTest2 contains method main (lines 8–24), which launches the application. Line 11 creates an ExecutorService to run the Producer and Consumer tasks. Line 14 creates a SynchronizedBuffer object and assigns its reference to Buffer variable sharedLocation. This object stores the data that will be shared between the Producer and Consumer. Lines 16–17 display the column heads for the output. Lines 20–21 execute a Producer and a Consumer. Finally, line 23 calls method shutdown to end the application when the Producer and Consumer complete their tasks. When method main ends (line 24), the main thread of execution terminates.
Study the outputs in Fig. 18.19. Observe that every integer produced is consumed exactly once—no values are lost, and no values are consumed more than once. The synchronization ensures that the Producer produces a value only when the buffer is empty and the Consumer consumes only when the buffer is full. The Producer always goes first, the Consumer waits if the Producer has not produced since the Consumer last consumed, and the Producer waits if the Consumer has not yet consumed the value that the Producer most recently produced. Execute this program several times to confirm that every integer produced is consumed exactly once. In the sample output, note the highlighted lines indicating when the Producer and Consumer must wait to perform their respective tasks.
18.9 Producer/Consumer Relationship: Bounded Buffers
The program in Section 18.8 uses thread synchronization to guarantee that two threads manipulate data in a shared buffer correctly. However, the application may not perform optimally. If the two threads operate at different speeds, one of the threads will spend more (or most) of its time waiting. For example, in the program in Section 18.8 we shared a single integer variable between the two threads. If the Producer thread produces values faster than the Consumer can consume them, then the Producer thread waits for the Consumer, because there are no other locations in the buffer in which to place the next value. Similarly, if the Consumer consumes values faster than the Producer produces them, the Consumer waits until the Producer places the next value in the shared buffer. Even when we have threads that operate at the same relative speeds, those threads may occasionally become “out of sync” over a period of time, causing one of them to wait for the other. We cannot make assumptions about the relative speeds of concurrent threads—interactions that occur with the operating system, the network, the user and other components can cause the threads to operate at different speeds. When this happens, threads wait. When threads wait excessively, programs become less efficient, interactive programs become less responsive and applications suffer longer delays.
Bounded Buffers
To minimize the amount of waiting time for threads that share resources and operate at the same average speeds, we can implement a bounded buffer that provides a fixed number of buffer cells into which the Producer can place values, and from which the Consumer can retrieve those values. (In fact, we have already done this with the ArrayBlockingQueue class in Section 18.7.) If the Producer temporarily produces values faster than the Consumer can consume them, the Producer can write additional values into the extra buffer space (if any are available). This capability enables the Producer to perform its task even though the Consumer is not ready to retrieve the current value being produced. Similarly, if the Consumer consumes faster than the Producer produces new values, the Consumer can read additional values (if there are any) from the buffer. This enables the Consumer to keep busy even though the Producer is not ready to produce additional values.
Note that even a bounded buffer is inappropriate if the Producer and the Consumer operate consistently at different speeds. If the Consumer always executes faster than the Producer, then a buffer containing one location is enough. Additional locations would simply waste memory. If the Producer always executes faster, only a buffer with an “infinite” number of locations would be able to absorb the extra production. However, if the Producer and Consumer execute at about the same average speed, a bounded buffer helps to smooth the effects of any occasional speeding up or slowing down in either thread’s execution.
The key to using a bounded buffer with a Producer and Consumer that operate at about the same speed is to provide the buffer with enough locations to handle the anticipated “extra” production. If, over a period of time, we determine that the Producer often produces as many as three more values than the Consumer can consume, we can provide a buffer of at least three cells to handle the extra production. Making the buffer too small would cause threads to wait longer; making the buffer too large would waste memory.
Performance Tip 18.3
Even when using a bounded buffer, it is possible that a producer thread could fill the buffer, which would force the producer to wait until a consumer consumed a value to free an element in the buffer. Similarly, if the buffer is empty at any given time, a consumer thread must wait until the producer produces another value. The key to using a bounded buffer is to optimize the buffer size to minimize the amount of thread wait time, while not wasting space.
Bounded Buffers Using ArrayBlockingQueue
The simplest way to implement a bounded buffer is to use an ArrayBlockingQueue for the buffer so that all of the synchronization details are handled for you. This can be done by reusing the example from Section 18.7 and simply passing the desired size for the bounded buffer into the ArrayBlockingQueue constructor. Rather than repeat our previous ArrayBlockingQueue example with a different size, we instead present an example that illustrates how you can build a bounded buffer yourself. Again, note that using an ArrayBlockingQueue will result in more maintainable and better performing code.
Implementing Your Own Bounded Buffer as a Circular Buffer
The program in Fig. 18.20 and Fig. 18.21 demonstrates a Producer and a Consumer accessing a bounded buffer with synchronization. We implement the bounded buffer in class CircularBuffer (Fig. 18.20) as a circular buffer that uses a shared array of three elements. A circular buffer writes into and reads from the array elements in order, beginning at the first cell and moving toward the last. When a Producer or Consumer reaches the last element, it returns to the first and begins writing or reading, respectively, from there. In this version of the producer/consumer relationship, the Consumer consumes a value only when the array is not empty and the Producer produces a value only when the array is not full. The statements that created and started the thread objects in the main method of class SharedBufferTest2 (Fig. 18.19) now appear in class CircularBufferTest (Fig. 18.21).
Fig. 18.20. Synchronizing access to a shared three-element bounded buffer.
Fig. 18.21. Producer and Consumer threads manipulating a circular buffer.
Line 5 initializes array buffer as a three-element integer array that represents the circular buffer. Variable occupiedCells (line 7) counts the number of elements in buffer that contain data to be read. When occupiedBuffers is 0, there is no data in the circular buffer and the Consumer must wait—when occupiedCells is 3 (the size of the circular buffer), the circular buffer is full and the Producer must wait. Variable writeIndex (line 8) indicates the next location in which a value can be placed by a Producer. Variable readIndex (line 9) indicates the position from which the next value can be read by a Consumer.
CircularBuffer method set (lines 12–30) performs the same tasks as in Fig. 18.18, with a few modifications. The loop at lines 16–20 determines whether the Producer must wait (i.e., all buffers are full). If so, line 18 indicates that the Producer is waiting to perform its task. Then line 19 invokes method wait, causing the Producer thread to release the CircularBuffer’s lock and wait until there is space for a new value to be written into the buffer. When execution continues at line 22 after the while loop, the value written by the Producer is placed in the circular buffer at location writeIndex. Then line 25 updates writeIndex for the next call to CircularBuffer method set. This line is the key to the “circularity” of the buffer. When writeIndex is incremented past the end of the buffer, the line sets it to 0. Line 27 increments occupiedCells, because there is now one more value in the buffer that the Consumer can read. Next, line 28 invokes method displayState (lines 56–85) to update the output with the value produced, the number of occupied buffers, the contents of the buffers and the current writeIndex and readIndex. Line 29 invokes method notifyAll to transition waiting threads to the runnable state, so that a waiting Consumer thread (if there is one) can now try again to read a value from the buffer.
CircularBuffer method get (lines 33–53) also performs the same tasks as it did in Fig. 18.18, with a few minor modifications. The loop at lines 37–41 determines whether the Consumer must wait (i.e., all buffer cells are empty). If the Consumer must wait, line 39 updates the output to indicate that the Consumer is waiting to perform its task. Then line 40 invokes method wait, causing the current thread to release the lock on the CircularBuffer and wait until data is available to read. When execution eventually continues at line 43 after a notifyAll call from the Producer, readValue is assigned the value at location readIndex in the circular buffer. Then line 46 updates readIndex for the next call to CircularBuffer method get. This line and line 25 implement the “circularity” of the buffer. Line 48 decrements occupiedCells, because there is now one more position in the buffer in which the Producer thread can place a value. Line 49 invokes method displayState to update the output with the consumed value, the number of occupied buffers, the contents of the buffers and the current writeIndex and readIndex. Line 50 invokes method notifyAll to allow any Producer threads waiting to write into the CircularBuffer object to attempt to write again. Then line 52 returns the consumed value to the caller.
Method displayState (lines 56–85) outputs the state of the application. Lines 62–63 output the current values of the buffer cells. Line 63 uses method printf with a "%2d" format specifier to print the contents of each buffer with a leading space if it is a single digit. Lines 70–82 output the current writeIndex and readIndex with the letters W and R, respectively.
Testing Class CircularBuffer
Class CircularBufferTest (Fig. 18.21) contains the main method that launches the application. Line 11 creates the ExecutorService, and line 14 creates a CircularBuffer object and assigns its reference to CircularBuffer variable sharedLocation. Line 17 invokes the CircularBuffer’s displayState method to show the initial state of the buffer. Lines 20–21 execute the Producer and Consumer tasks. Line 23 calls method shutdown to end the application when the threads complete the Producer and Consumer tasks.
Each time the Producer writes a value or the Consumer reads a value, the program outputs a message indicating the action performed (a read or a write), the contents of buffer, and the location of writeIndex and readIndex. In the output of Fig. 18.21, the Producer first writes the value 1. The buffer then contains the value 1 in the first cell and the value –1 (the default value that we use for output purposes) in the other two cells. The write index is updated to the second cell, while the read index stays at the first cell. Next, the Consumer reads 1. The buffer contains the same values, but the read index has been updated to the second cell. The Consumer then tries to read again, but the buffer is empty and the Consumer is forced to wait. Note that only once in this execution of the program was it necessary for either thread to wait.
18.10 Producer/Consumer Relationship: The Lock and Condition Interfaces
Though the synchronized keyword provides for most basic thread synchronization needs, Java provides other tools to assist in developing concurrent programs. In this section, we discuss the Lock and Condition interfaces, which were introduced in Java SE 5. These interfaces give programmers more precise control over thread synchronization, but are more complicated to use.
Interface Lock and Class ReentrantLock
Any object can contain a reference to an object that implements the Lock interface (of package java.util.concurrent.locks). A thread calls the Lock’s lock method to acquire the lock. Once a Lock has been obtained by one thread, the Lock object will not allow another thread to obtain the Lock until the first thread releases the Lock (by calling the Lock’s unlock method). If several threads are trying to call method lock on the same Lock object at the same time, only one of these threads can obtain the lock—all the others are placed in the waiting state for that lock. When a thread calls method unlock, the lock on the object is released and a waiting thread attempting to lock the object proceeds.
Class ReentrantLock (of package java.util.concurrent.locks) is a basic implementation of the Lock interface. The constructor for a ReentrantLock takes a boolean argument that specifies whether the lock has a fairness policy. If the argument is true, the ReentrantLock’s fairness policy is “the longest-waiting thread will acquire the lock when it is available.” Such a fairness policy guarantees that indefinite postponement (also called starvation) cannot occur. If the fairness policy argument is set to false, there is no guarantee as to which waiting thread will acquire the lock when it is available.
Software Engineering Observation 18.2
Using a ReentrantLock with a fairness policy avoids indefinite postponement.
Performance Tip 18.4
Using a ReentrantLock with a fairness policy can decrease program performance significantly.
Condition Objects and Interface Condition
If a thread that owns a Lock determines that it cannot continue with its task until some condition is satisfied, the thread can wait on a condition object. Using Lock objects allows you to explicitly declare the condition objects on which a thread may need to wait. For example, in the producer/consumer relationship, producers can wait on one object and consumers can wait on another. This is not possible when using the synchronized keywords and an object’s built-in monitor lock. Condition objects are associated with a specific Lock and are created by calling a Lock’s newCondition method, which returns an object that implements the Condition interface (of package java.util.concurrent.locks). To wait on a condition object, the thread can call the Condition’s await method. This immediately releases the associated Lock and places the thread in the waiting state for that Condition. Other threads can then try to obtain the Lock. When a runnable thread completes a task and determines that the waiting thread can now continue, the runnable thread can call Condition method signal to allow a thread in that Condition’s waiting state to return to the runnable state. At this point, the thread that transitioned from the waiting state to the runnable state can attempt to reacquire the Lock. Even if it is able to reacquire the Lock, the thread still might not be able to perform its task at this time—in which case the thread can call the Condition’s await method to release the Lock and reenter the waiting state. If multiple threads are in a Condition’s waiting state when signal is called, the default implementation of Condition signals the longest-waiting thread to transition to the runnable state. If a thread calls Condition method signalAll, then all the threads waiting for that condition transition to the runnable state and become eligible to reacquire the Lock. Only one of those threads can obtain the Lock on the object—the others will wait until the Lock becomes available again. If the Lock has a fairness policy, the longest-waiting thread acquires the Lock. When a thread is finished with a shared object, it must call method unlock to release the Lock.
Common Programming Error 18.2
Deadlock occurs when a waiting thread (let us call this thread1) cannot proceed because it is waiting (either directly or indirectly) for another thread (let us call this thread2) to proceed, while simultaneously thread2 cannot proceed because it is waiting (either directly or indirectly) for thread1 to proceed. The two threads are waiting for each other, so the actions that would enable each thread to continue execution can never occur.
Error-Prevention Tip 18.3
When multiple threads manipulate a shared object using locks, ensure that if one thread calls method await to enter the waiting state for a condition object, a separate thread eventually will call Condition method signal to transition the thread waiting on the condition object back to the runnable state. If multiple threads may be waiting on the condition object, a separate thread can call Condition method signalAll as a safeguard to ensure that all the waiting threads have another opportunity to perform their tasks. If this is not done, starvation might occur.
Common Programming Error 18.3
An IllegalMonitorStateException occurs if a thread issues an await, a signal, or a signalAll on a condition object without having acquired the lock for that condition object.
Lock and Condition vs. the synchronized Keyword
In some applications, using Lock and Condition objects may be preferable to using the synchronized keyword. Locks allow you to interrupt waiting threads or to specify a timeout for waiting to acquire a lock, which is not possible using the synchronized keyword. Also, a Lock is not constrained to be acquired and released in the same block of code, which is the case with the synchronized keyword. Condition objects allow you to specify multiple condition objects on which threads may wait. Thus, it is possible indicate to waiting threads that a specific condition object is now true by calling signal or signallAll on that Condition object. With the synchronized keyword, there is no way to explicitly state the condition on which threads are waiting, and thus there is no way to notify threads waiting on one condition that they may proceed without also signaling threads waiting on any other conditions. There are other possible advantages to using Lock and Condition objects, but note that generally it is best to use the synchronized keyword unless your application requires advanced synchronization capabilities. Using interfaces Lock and Condition is error prone—unlock is not guaranteed to be called, whereas the monitor in a synchronized statement will always be released when the statement completes execution.
Using Locks and Conditions to Implement Synchronization
To illustrate how to use the Lock and Condition interfaces, we now implement the producer/consumer relationship using Lock and Condition objects to coordinate access to a shared single-element buffer (Fig. 18.22 and Fig. 18.23). In this case, each produced value is correctly consumed exactly once.
Fig. 18.22. Synchronizing access to a shared integer using the Lock and Condition interfaces.
Fig. 18.23. Two threads manipulating a synchronized buffer.
Class SynchronizedBuffer (Fig. 18.22) contains five fields. Line 11 creates a new object of type ReentrantLock and assigns its reference to Lock variable accessLock. The ReentrantLock is created without the fairness policy because at any time only a single Producer or Consumer will be waiting to acquire the Lock in this example. Lines 14–15 create two Conditions using Lock method newCondition. ConditioncanWrite contains a queue for a Producer thread waiting while the buffer is full (i.e., there is data in the buffer that the Consumer has not read yet). If the buffer is full, the Producer calls method await on this Condition. When the Consumer reads data from a full buffer, it calls method signal on this Condition. ConditioncanRead contains a queue for a Consumer thread waiting while the buffer is empty (i.e., there is no data in the buffer for the Consumer to read). If the buffer is empty, the Consumer calls method await on this Condition. When the Producer writes to the empty buffer, it calls method signal on this Condition. The int variable buffer (line 17) holds the shared data. The boolean variable occupied (line 18) keeps track of whether the buffer currently holds data (that the Consumer should read).
Line 23 in method set calls method lock on the SynchronizedBuffer’s accessLock. If the lock is available (i.e., no other thread has acquired this lock), method lock returns immediately (this thread now owns the lock) and the thread continues. If the lock is unavailable (i.e., it is held by another thread), this method waits until the lock is released by the other thread. After the lock is acquired, the try block in lines 26–46 executes. Line 29 tests occupied to determine whether buffer is full. If it is, lines 31–32 display a message indicating that the thread will wait. Line 33 calls Condition method await on the canWrite condition object, which temporarily releases the SynchronizedBuffer’s Lock and waits for a signal from the Consumer that buffer is available for writing. When buffer is available, the method proceeds, writing to buffer (line 36), setting occupied to true (line 40) and displaying a message indicating that the producer wrote a value (line 42). Line 45 calls Condition method signal on condition object canRead to notify the waiting Consumer (if there is one) that the buffer has new data to be read. Line 49 calls method unlock from a finally block to release the lock and allow the Consumer to proceed.
Error-Prevention Tip 18.4
Place calls to Lock method unlock in a finally block. If an exception is thrown, unlock must still be called or deadlock could occur.
Line 57 of method get (lines 54–86) calls method lock to acquire the Lock. This method waits until the Lock is available. Once the Lock is acquired, line 63 tests whether occupied is false, indicating that the buffer is empty. If the buffer is empty, line 67 calls method await on condition object canRead. Recall that method signal is called on variable canRead in the set method (line 45). When the Condition object is signaled, the get method continues. Line 72 sets occupied to false, line 74 stores the value of buffer in readValue and line 75 outputs the readValue. Then line 78 signals the condition object canWrite. This will awaken the Producer if it is indeed waiting for the buffer to be emptied. Line 82 calls method unlock from a finally block to release the lock, and line 85 returns readValue to the calling method.
Forgetting to signal a waiting thread is a logic error. The thread will remain in the waiting state, which will prevent the thread from proceeding. Such waiting can lead to indefinite postponement or deadlock.
Class SharedBufferTest2 (Fig. 18.23) is identical to that of Fig. 18.19. Study the outputs in Fig. 18.23. Observe that every integer produced is consumed exactly once—no values are lost, and no values are consumed more than once. The Lock and Condition objects ensure that the Producer and Consumer cannot perform their tasks unless it is their turn. The Producer must go first, the Consumer must wait if the Producer has not produced since the Consumer last consumed and the Producer must wait if the Consumer has not yet consumed the value that the Producer most recently produced. Execute this program several times to confirm that every integer produced is consumed exactly once. In the sample output, note the highlighted lines indicating when the Producer and Consumer must wait to perform their respective tasks.
18.11 Multithreading with GUI
Swing applications present a unique set of challenges for multithreaded programming. All Swing applications have a single thread, called the event dispatch thread, to handle interactions with the application’s GUI components. Typical interactions include updating GUI components or processing user actions such as mouse clicks. All tasks that require interaction with an application’s GUI are placed in an event queue and are executed sequentially by the event dispatch thread.
Swing GUI components are not thread safe—they cannot be manipulated by multiple threads without the risk of incorrect results. Unlike the other examples presented in this chapter, thread safety in GUI applications is achieved not by synchronizing thread actions, but by ensuring that Swing components are accessed from only a single thread—the event dispatch thread. This technique is called thread confinement. Allowing just one thread to access non-thread-safe objects eliminates the possibility of corruption due to multiple threads accessing these objects concurrently.
Usually it is sufficient to perform simple calculations on the event dispatch thread in sequence with GUI component manipulations. If an application must perform a lengthy computation in response to a user interface interaction, the event dispatch thread cannot attend to other tasks in the event queue while the thread is tied up in that computation. This causes the GUI components to become unresponsive. It is preferable to handle a long-running computation in a separate thread, freeing the event dispatch thread to continue managing other GUI interactions. Of course, to update the GUI based on the computation’s results, you must update the GUI from the event dispatch thread, rather than from the worker thread that performed the computation.
Class SwingWorker
Java SE 6 provides class SwingWorker (in package javax.swing) to perform long-running computations in a worker thread and to update Swing components from the event dispatch thread based on the computations’ results. SwingWorker implements the Runnable interface, meaning that a SwingWorker object can be scheduled to execute in a separate thread. The SwingWorker class provides several methods to simplify performing computations in a worker thread and making the results available for display in a GUI. Some common SwingWorker methods are described in Fig. 18.24.
Fig. 18.24. Commonly used SwingWorker methods.
18.11.1 Performing Computations in a Worker Thread
In the next example, a GUI provides components for a user to enter a number n and get the nth Fibonacci number, which we calculate using the recursive algorithm discussed in Section 6.16. Since the recursive algorithm is time consuming for large values, we use a SwingWorker object to perform the calculation in a worker thread. The GUI also provides a separate set of components that get the next Fibonacci number in the sequence with each click of a button, beginning with fibonacci(1). This set of components performs its short computation directly in the event dispatch thread.
Class BackgroundCalculator (Fig. 18.25) performs the recursive Fibonacci calculation in a worker thread. This class extends SwingWorker (line 8), overriding the methods doInBackground and done. Method doInBackground (lines 21–25) computes the nth Fibonacci number in a worker thread and returns the result. Method done (lines 28–44) displays the result in a JLabel.
Fig. 18.25. SwingWorker subclass for calculating Fibonacci numbers in a background thread.
Note that SwingWorker is a generic class. In line 8, the first type parameter is String and the second is Object. The first type parameter indicates the type returned by the doInBackground method; the second indicates the type that is passed between the publish and process methods to handle intermediate results. Since we do not use publish and process in this example, we simply use Object as the second type parameter. We discuss publish and process in Section 18.11.2.
A BackgroundCalculator object can be instantiated from a class that controls a GUI. A BackgroundCalculator maintains instance variables for an integer that represents the Fibonacci number to be calculated and a JLabel that displays the results of the calculation (lines 10–11). The BackgroundCalculator constructor (lines 14–18) initializes these instance variables with the arguments that are passed to the constructor.
Software Engineering Observation 18.3
Any GUI components that will be manipulated by SwingWorker methods, such as components that will be updated from methods process or done, should be passed to the SwingWorker subclass’s constructor and stored in the subclass object. This gives these methods access to the GUI components they will manipulate.
When method execute is called on a BackgroundCalculator object, the object is scheduled for execution in a worker thread. Method doInBackground is called from the worker thread and invokes the fibonacci method (lines 47–53), passing instance variable n as an argument (line 23). Method fibonacci uses recursion to compute the Fibonacci of n. When fibonacci returns, method doInBackground returns the result.
After doInBackground returns, method done is called from the event dispatch thread. This method attempts to set the result JLabel to the return value of doInBackground by calling method get to retrieve this return value (line 33). Method get waits for the result to be ready if necessary, but since we call it from method done, the computation will be complete before get is called. Lines 35–38 catch InterruptedException if the current thread is interrupted while waiting for get to return. Lines 39–43 catch ExecutionException, which is thrown if an exception occurs during the computation.
Class FibonacciNumbers (Fig. 18.26) displays a window containing two sets of GUI components—one set to compute a Fibonacci number in a worker thread and another to get the next Fibonacci number in response to the user’s clicking a JButton. The constructor (lines 38–109) places these components in separate titled JPanels. Lines 46–47 and 78–79 add two JLabels, a JTextField and a JButton to the workerJPanel to allow the user to enter an integer whose Fibonacci number will be calculated by the BackgroundWorker. Lines 84–85 and 103 add two JLabels and a JButton to the event dispatch thread panel to allow the user to get the next Fibonacci number in the sequence. Instance variables n1 and n2 contain the previous two Fibonacci numbers in the sequence and are initialized to 0 and 1, respectively (lines 29–30). Instance variable count stores the most recently computed sequence number and is initialized to 1 (line 31). The two JLabels display count and n2 initially, so that the user will see the text Fibonacci of 1: 1 in the eventThreadJPanel when the GUI starts.
Fig. 18.26. Using SwingWorker to perform a long calculation with intermediate results displayed in a GUI.
a)
b)
c)
Lines 48–77 register the event handler for the goJButton. If the user clicks this JButton, line 58 gets the value entered in the numberJTextField and attempts to parse it as an integer. Lines 72–73 create a new BackgroundCalculator object, passing in the userentered value and the fibonacciJLabel that is used to display the calculation’s results. Line 74 calls method execute on the BackgroundCalculator, scheduling it for execution in a separate worker thread. Method execute does not wait for the BackgroundCalculator to finish executing. It returns immediately, allowing the GUI to continue processing other events while the computation is performed.
If the user clicks the nextNumberJButton in the eventThreadJPanel, the event handler registered in lines 86–102 executes. The previous two Fibonacci numbers stored in n1 and n2 are added together and count is incremented to determine the next number in the sequence (lines 92–95). Then lines 98–99 update the GUI to display the next number. The code to perform these calculations is written directly in method actionPerformed, so these calculations are performed on the event dispatch thread. Handling such short computations in the event dispatch thread does not cause the GUI to become unresponsive, like the recursive algorithm for calculating the Fibonacci of a large number. Because the longer Fibonacci computation is performed in a separate worker thread using the SwingWorker, it is possible to get the next Fibonacci number while the recursive computation is still in progress.
18.11.2 Processing Intermediate Results with SwingWorker
We have presented an example that uses the SwingWorker class to execute a long process in a background thread and update the GUI when the process is finished. We now present an example of updating the GUI with intermediate results before the long process completes. Figure 18.27 presents class PrimeCalculator, which extends SwingWorker to compute the first n primes in a worker thread. In addition to the doInBackground and done methods used in the previous example, this class uses SwingWorker methods publish, process and setProgress. In this example, method publish sends prime numbers to method process as they are found, method process displays these primes in a GUI component and method setProgress updates the progress property. We later show how to use this property to update a JProgressBar.
Fig. 18.27. Calculates the first n primes, displaying them as they are found.
Class PrimeCalculator extends SwingWorker (line 11), with the first type parameter indicating the return type of method doInBackground and the second indicating the type of intermediate results passed between methods publish and process. In this case, both type parameters are Integers. The constructor (lines 22–34) takes as arguments an integer that indicates the upper limit of the prime numbers to locate, a JTextArea used to display primes in the GUI, one JButton for initiating a calculation and one for canceling it, and a JLabel used to display the status of the calculation.
Lines 32–33 initialize the elements of the boolean array primes to true. PrimeCalculator uses this array and the Sieve of Eratosthenes algorithm to find all primes less than max. The Sieve of Eratosthenes takes a list of natural numbers of any length and, beginning with the first prime number, filters out all multiples of that prime. It then moves to the next prime, which will be the next number that is not yet filtered out, and eliminates all of its multiples. It continues until the end of the list is reached and all non-primes have been filtered out. Algorithmically, we begin with element 2 of the boolean array and set the cells corresponding to all values that are multiples of 2 to false to indicate that they are divisible by 2 and thus not prime. We then move to the next array element, check whether it is true, and if so set all of its multiples to false to indicate that they are divisible by the current index. When the whole array has been traversed in this way, all indices that contain true are prime, as they have no divisors.
In method doInBackground (lines 37–73), the control variable i for the loop (lines 43–70) controls the current index for implementing the Sieve of Eratosthenes. Line 45 tests the stoppedboolean flag, which indicates whether the user has clicked the Cancel button. If stopped is true, the method returns the number of primes found so far (line 46) without finishing the computation.
If the calculation is not canceled, line 49 calls method setProgress to update the progress property with the percentage of the array that has been traversed so far. Line 53 puts the currently executing thread to sleep for up to 4 milliseconds. We discuss the reason for this shortly. Line 61 tests whether the element of array primes at the current index is true (and thus prime). If so, line 63 passes the index to method publish so that it can be displayed as an intermediate result in the GUI and line 64 increments the number of primes found. Lines 66–67 set all multiples of the current index to false to indicate that they are not prime. When the entire boolean array has been traversed, the number of primes found is returned at line 72.
Lines 76–80 declare method process, which executes in the event dispatch thread and receives its argument publishedVals from method publish. The passing of values between publish in the worker thread and process in the event dispatch thread is asynchronous; process is not necessarily invoked for every call to publish. All Integers published since the last call to process are received as a List by method process. Lines 78–79 iterate through this list and display the published values in a JTextArea. Because the computation in method doInBackground progresses quickly, publishing values often, updates to the JTextArea can pile up on the event dispatch thread, causing the GUI to become sluggish. In fact, when searching for a large enough number of primes, the event dispatch thread may receive so many requests in quick succession to update the JTextArea that the thread will run out of memory in its event queue. This is why we put the worker thread to sleep for a few milliseconds between each potential call to publish. The calculation is slowed just enough to allow the event dispatch thread to keep up with requests to update the JTextArea with new primes, enabling the GUI to update smoothly and remain responsive.
Lines 83–106 define method done. When the calculation is finished or canceled, method done enables the Get Primes button and disables the Cancel button (lines 85–86). Line 92 gets the return value—the number of primes found—from method doInBackground. Lines 94–103 catch the exceptions thrown by method get and display an appropriate error message in the statusJLabel. If no exceptions occur, line 105 sets the statusJLabel to indicate the number of primes found.
Lines 109–112 define public method stopCalculation, which is invoked when the Cancel button is clicked. This method sets the flag stopped at line 111 so that doInBackground will return without finishing its calculation the next time it tests this flag. Though SwingWorker provides a method cancel, this method simply calls Thread method interrupt on the worker thread. Using the boolean flag instead of cancel allows us to stop the calculation cleanly, return a value from doInBackground and ensure that method done is called even though the calculation did not run to completion, without the risk of throwing an InterruptedException associated with interrupting the worker thread.
Class FindPrimes (Fig. 18.28) displays a JTextField that allows the user to enter a number, a JButton to begin finding all primes less than that number and a JTextArea to display the primes. A JButton allows the user to cancel the calculation, and a JProgressBar indicates the calculation’s progress. The FindPrimes constructor (lines 32–125) initializes these components and displays them in a JFrame using BorderLayout.
Fig. 18.28. Using a SwingWorker to display prime numbers and update a JProgressBar while the prime numbers are being calculated.
a)
b)
c)
Lines 42–94 register the event handler for the getPrimesJButton. When the user clicks this JButton, lines 47–49 reset the JProgressBar and clear the displayPrimesJTextArea and the statusJLabel. Lines 53–63 parse the value in the JTextField and display an error message if the value is not an integer. Lines 66–68 construct a new PrimeCalculator object, passing as arguments the integer the user entered, the displayPrimesJTextArea for displaying the primes, the statusJLabel and the two JButtons.
Lines 71–85 register a PropertyChangeListener for the new PrimeCalculator object using an anonymous inner class. PropertyChangeListener is an interface from package java.beans that defines a single method, propertyChange. Every time method setProgress is invoked on a PrimeCalculator, the PrimeCalculator generates a PropertyChangeEvent to indicate that the progress property has changed. Method propertyChange listens for these events. Line 78 tests whether a given PropertyChangeEvent indicates a change to the progress property. If so, line 80 gets the new value of the property and line 81 updates the JProgressBar with the new progress property value. The Get Primes JButton is disabled (line 88) so that only one calculation that updates the GUI can execute at a time, and the Cancel JButton is enabled (line 89) to allow the user to stop the computation before it completes. Line 91 executes the PrimesCalculator to begin finding primes. If the user clicks the cancelJButton, the event handler registered at lines 107–115 calls PrimeCalculator method stopCalculation (line 112) and the calculation returns early.
18.12 Other Classes and Interfaces in java.util.concurrent
Interface Runnable provides only the most basic functionality for multithreaded programming. In fact, this interface has several limitations. Suppose a Runnable encounters a problem and tries to throw a checked exception. The run method is not declared to throw any exceptions, so the problem must be handled within the Runnable—the exception cannot be passed to the calling thread. Now suppose a Runnable is performing a long calculation and the application wants to retrieve the result of that calculation. The run method cannot return a value, so the application must use shared data to pass the value back to the calling thread. This also involves the overhead of synchronizing access to the data. The developers of the concurrency APIs introduced in Java SE 5 recognized these limitations and created a new interface to fix them. The Callable interface (of package java.util.concurrent) declares a single method named call. This interface is designed to be similar to the Runnable interface—allowing an action to be performed concurrently in a separate thread—but the call method allows the thread to return a value or to throw a checked exception.
An application that creates a Callable likely wants to run the Callable concurrently with other Runnables and Callables. The ExecutorService interface provides method submit, which will execute a Callable passed in as its argument. The submit method returns an object of type Future (of package java.util.concurrent), which is an interface that represents the executing Callable. The Future interface declares method get to return the result of the Callable and provides other methods to manage a Callable’s execution.
18.13 Wrap-Up
In this chapter, you learned that concurrency has historically been implemented with operating system primitives available only to experienced systems programmers, but that Java makes concurrency available to you through the language and APIs. You also learned that the JVM itself creates threads to run a program, and that it also may create threads to perform housekeeping tasks such as garbage collection.
We discussed the life cycle of a thread and the states that a thread may occupy during its lifetime. We also discussed Java’s thread priorities, which help the system schedule threads for execution. You learned that you should avoid manipulating Java thread priorities directly and you learned about problems associated with thread priorities, such as indefinite postponement (sometimes called starvation).
Next, we presented the interface Runnable, which is used to specify a task that can execute concurrently with other tasks. This interface’s run method is invoked by the thread executing the task. We showed how to execute a Runnable object by associating it with an object of class Thread. Then we showed how to use the Executor interface to manage the execution of Runnable objects via thread pools, which can reuse existing threads to eliminate the overhead of creating a new thread for each task and can improve performance by optimizing the number of threads to ensure that the processor stays busy.
You learned that when multiple threads share an object and one or more of them modify that object, indeterminate results may occur unless access to the shared object is managed properly. We showed you how to solve this problem via thread synchronization, which coordinates access to shared data by multiple concurrent threads. You learned several techniques for performing synchronization—first with the built-in class ArrayBlockingQueue (which handles all the synchronization details for you), then with Java’s built-in monitors and the synchronized keyword, and finally with interfaces Lock and Condition.
We discussed the fact that Swing GUIs are not thread safe, so all interactions with and modifications to the GUI must be performed in the event dispatch thread. We also discussed the problems associated with performing long-running calculations in the event dispatch thread. Then we showed how you can use Java SE 6’s SwingWorker class to perform long-running calculations in worker threads. You learned how to display the results of a SwingWorker in a GUI when the calculation completed and how to display intermediate results while the calculation was still in process.
Finally, we discussed the Callable and Future interfaces, which enable you to execute tasks that return results and to obtain those results, respectively. We use the multithreading techniques introduced here again in Chapter 19, Networking, to help build multithreaded servers that can interact with multiple clients concurrently.