Threads and Concurrent Programming

14.1 Introduction

OBJECTIVES 

After studying this chapter, you will 

• Understand the concept of a thread. 
• Know how to design and write multithreaded programs. 
• Be able to use the Thread class and the Runnable interface. 
• Understand the life cycle of a thread. 
• Know how to synchronize threads. 

14.1 Introduction 1
4.2 What Is a Thread? 
14.3 From the Java Library: java.lang.Thread 
14.4 Thread States and Life Cycle 
14.5 Using Threads to Improve Interface Responsiveness 
14.6 Case Study: Cooperating Threads 
14.7 Case Study: The Game of Pong Chapter Summary

Introduction

This chapter is about doing more than one thing at a time. Doing more than one thing at once is commonplace in our everyday lives. For example, let’s say your breakfast today consists of cereal, toast, and a cup of java. You have to do three things at once to have breakfast: eat cereal, eat toast,and drink coffee.

Actually, you do these things “at the same time” by alternating among them: You take a spoonful of cereal, then a bite of toast, and then sip some coffee. Then you have another bite of toast, or another spoonful of cereal, more coffee, and so on, until breakfast is finished. If the phone rings while you’re having breakfast, you will probably answer it—and continue to have breakfast, or at least to sip the coffee. This means you’re doing even more “at the same time.” Everyday life is full of examples where we do more than one task at the same time.

The computer programs we have written so far have performed one task at a time. But there are plenty of applications where a program needs to do several things at once, or concurrently. For example, if you wrote an Internet chat program, it would let several users take part in a discussion group. The program would have to read messages from several users at the same time and broadcast them to the other participants in the group. The reading and broadcasting tasks would have to take place concurrently. In Java, concurrent programming is handled by threads, the topic of this chapter.

Source: R. Morelli and R. Walde, Trinity College
This work is licensed under a Creative Commons Attribution 4.0 License.

14.2 What Is a Thread?

A thread (or a thread of execution or a thread of control) is a single sequence of executable statements within a program. For Java applications, the flow of control begins at the first statement in main() and continues sequentially through the program statements. For Java applets, the flow of control begins with the first statement in init(). Loops within a program cause a certain block of statements to be repeated. If-else structures cause certain statements to be selected and others to be skipped. Method calls cause the flow of execution to jump to another part of the program, from which it returns after the method’s statements are executed. Thus, within a single thread, you can trace the sequential flow of execution from one statement to the next.

One way to visualize a thread is to imagine that you could make a list of the program’s statements as they are executed by the computer’s central processing unit (CPU). Thus, for a particular execution of a program with loops, method calls, and selection statements, you could list each instruction that was executed, beginning at the first, and continuing until the program stopped, as a single sequence of executed statements. That’s a thread!

Now imagine that we break a program up into two or more independent threads. Each thread will have its own sequence of instructions. Within a single thread, the statements are executed one after the other, as usual. However, by alternately executing the statements from one thread and another, the computer can run several threads concurrently. Even though the CPU executes one instruction at a time, it can run multiple threads concurrently by rapidly alternating among them. The main advantage of concurrency is that it allows the computer to do more than one task at a time. For example, the CPU could alternate between downloading an image from the Internet and running a spreadsheet calculation. This is the same way you ate toast and cereal and drank coffee in our earlier breakfast example. From our perspective, it might look as if the computer had several CPUs working in parallel, but that’s just the illusion created by effectively scheduling threads.

Concurrent Execution of Threads

The technique of concurrently executing several tasks within a program is known as multitasking. A task in this sense is a computer operation of some sort, such as reading or saving a file, compiling a program, or displaying an image on the screen. Multitasking requires the use of a separate thread for each of the tasks. The methods available in the Java Thread class make it possible (and quite simple) to implement multithreaded programs.

Most computers, including personal computers, are sequential machines that consist of a single CPU, which is capable of executing one machine instruction at a time. In contrast, parallel computers, used primarily for large scale scientific and engineering applications, are made up of multiple CPUs working in tandem.

Today’s personal computers, running at clock speeds over 1 gigahertz— 1 gigahertz equals 1 billion cycles per second—are capable of executing millions of machine instructions per second. Despite its great speed, however, a single CPU can process only one instruction at a time.

Each CPU uses a fetch-execute cycle to retrieve the next instruction from memory and execute it. Since CPUs can execute only one instruction at a time, multithreaded programs are made possible by dividing the CPU’s time and sharing it among the threads. The CPU’s schedule is managed by a scheduling algorithm, which is an algorithm that schedules threads for execution on the CPU. The choice of a scheduling algorithm depends on the platform on which the program is running. Thus, thread scheduling might be handled differently on Unix, Windows, and Macintosh systems.

One common scheduling technique is known as time slicing, in which each thread alternatively gets a slice of the CPU’s time. For example, suppose we have a program that consists of two threads. Using this technique, the system would give each thread a small quantum of CPU time— say, one thousandth of a second (one millisecond)—to execute its instructions. When its quantum expires, the thread would be preempted and the other thread would be given a chance to run. The algorithm would then alternate in this round-robin fashion between one thread and the other(Fig. 14.1). During each millisecond on a 300-megahertz CPU, a thread can execute 300,000 machine instructions. One megahertz equals 1 million cycles per second. Thus, within each second of real time, each thread will receive 500 time slices and will be able to execute something like 150 million machine instructions.

Figure 14.1: Each thread gets a slice of the CPU’s time.

Under priority scheduling, threads of higher priority are allowed to run to completion before lower-priority threads are given a chance. An example of a high-priority thread would be one that is processing keyboard input or any other kind of interactive input from the user. If such tasks were given low priority, users would experience noticeable delays in their interaction, which would be quite unacceptable.

The only way a high-priority thread can be preempted is if a thread of still higher priority becomes available to run. In many cases, higherpriority threads are those that can complete their task within a few milliseconds, so they can be allowed to run to completion without starving the lower-priority threads. An example would be processing a user’s keystroke, a task that can begin as soon as the key is struck and can be completed very quickly. Starvation occurs when one thread is repeatedly preempted by other threads.

Multithreaded Numbers

Let’s consider a simple example of a threaded program. Suppose we give every individual thread a unique ID number, and each time it runs, it prints its ID ten times. For example, when the thread with ID 1 runs the output produced would just be a sequence of ten 1’s: 1111111111.

As shown in Figure 14.2, the NumberThread class is defined +NumberThread(in n : int) +run() NumberThread +run() Thread as a subclass of Thread and overrides the run() method. To set the thread’s ID number, the constructor takes a single parameter that is use to set the thread’s ID number. In the run() method, the thread simply executes a loop that prints its own number ten times:

Figure 14.3: The Numbers object creates several instances of NumberThread and tells each one to start().

Now let’s define another class whose task will be to create many NumberThreads and get them all running at the same time (Fig. 14.3). For each NumberThread, we want to call its constructor and then start() it:

When a thread is started by calling its start() method, it automatically calls its run() method. The output generated by this version of the Numbers application is as follows:

From this output, it appears that the individual threads were run in the order in which they were created. In this case, each thread was able to run to completion before the next thread started running.

What if we increase the number of iterations that each thread performs? Will each thread still run to completion? The following output was generated for 200 iterations per thread:

In this case, only thread 1 managed to run to completion. Threads 2, 3, 4, and 5 did not. As this example illustrates, the order and timing of a thread’s execution are highly unpredictable. This example also serves to illustrate one way of creating a multithreaded program:

• Create a subclass of the Thread class. 
• Within the subclass, implement a method with the signature void run() that contains the statements to be executed by that thread. 
• Create several instances of the subclass and start each thread by invoking the start() method on each

14.3 From the Java Library: java.

The java.lang.Thread class contains the public methods shown in Figure 14.4 (the figure contains only a partial list). Note that Thread implements the Runnable interface, which consists simply of the run() method. As we will now see, another way to create a thread is to instantiate a Thread object and pass it a Runnable object that will become its body. This approach allows you to turn an existing class into a separate thread.

A Runnable object is any object that implements the Runnable interface—that is, any object that implements the run() method (Fig. 14.5). The following example provides an alternative way to implement the NumberThread program:

Given this definition, we would then pass instances of this class to the individual threads as we create them:

The NumberPrinter class implements Runnable by defining exactly the same run() that was used previously in the NumberThread class. We then pass instances of NumberPrinter when we create the individual threads. Doing things this way gives exactly the same output as earlier. This example serves to illustrate another way of creating a multithreaded program: 

• Implement the Runnable interface for an existing class by implementing the void run() method, which contains the statements to be executed by that thread. 
• Create several Thread instances by first creating instances of the Runnable class and passing each instance as an argument to the Thread() constructor. 
• For each thread instance, start it by invoking the start() method on it.

SELF-STUDY EXERCISE 

EXERCISE 14.1 Use the Runnable interface to convert the following class into a thread. You want the thread to print all the odd numbers up to its bound:

Thread Control

The various methods in the Thread class (Fig. 14.4) can be used to exert some control over a thread’s execution. The start() and stop() methods play the obvious roles of starting and stopping a thread. These methods will sometimes be called automatically. For example, an applet is treated as a thread by the browser, or applet viewer, which is responsible for starting and stopping it.

As we saw in the NumberThread example, the run() method encapsulates the thread’s basic algorithm. It is usually not called directly. Instead, it is called by the thread’s start() method, which handles any system-dependent initialization tasks before calling run().

Thread Priority

The setPriority(int) method lets you set a thread’s priority to an integer value between Thread.MIN PRIORITY and Thread.MAX PRIORITY, the bounds defined as constants in the Thread class. Using setPriority() gives you some control over a thread’s execution. In general, higher-priority threads get to run before, and longer than, lower priority threads.

To see how setPriority() works, suppose we change NumberThread’s constructor to the following:

In this case, each thread sets its priority to its ID number. So, thread five will have priority five, a higher priority than all the other threads. Suppose we now run 2 million iterations of each of these threads. Because 2 million iterations will take a long time if we print the thread’s ID on each iteration, let’s modify the run() method, so that the ID is printed every 1 million iterations:

Given this modification, we get the following output when we run Numbers:

It appears from this output that the threads ran to completion in priority order. Thus, thread five completed 2 million iterations before thread four started to run, and so on. This shows that, on my system at least, the Java Virtual Machine (JVM) supports priority scheduling.

Forcing Threads to Sleep

The Thread.sleep() and Thread.yield() methods also provide some control over a thread’s behavior. When executed by a thread, the yield() method causes the thread to yield the CPU, allowing the thread scheduler to choose another thread. The sleep() method causes the thread to yield and not to be scheduled until a certain amount of real time has passed.

The sleep() method can halt a running thread for a given number of milliseconds, allowing other waiting threads to run. The sleep() method throws an InterruptedException, which is a checked exception. This means that the sleep() call must be embedded within a try/catch block or the method it’s in must throw an InterruptedException. Try/catch blocks were covered in Chapter 10.

For example, consider the following version of the NumberPrinter.run():

In this example, each thread is forced to sleep for a random number of milliseconds between 0 and 1,000. When a thread sleeps, it gives up the CPU, which allows one of the other waiting threads to run. As you would expect, the output we get from this example will reflect the randomness in the amount of time that each thread sleeps:

As we will see, the sleep() method provides a rudimentary form of thread synchronization, in which one thread yields control to another.

SELF-STUDY EXERCISES 

EXERCISE 14.2 What happens if you run five NumberThreads of equal priority through 2 million iterations each? Run this experiment and note the output. Don’t print after every iteration! What sort of scheduling algorithm (round-robin, priority scheduling, or something else) was used to schedule threads of equal priority on your system? 

EXERCISE 14.3 Try the following experiment and note the output. Let each thread sleep for 50 milliseconds (rather than a random number of milliseconds). How does this affect the scheduling of the threads? To make things easier to see, print each thread’s ID after every 100,000 iterations. 

EXERCISE 14.4 The purpose of the Java garbage collector is to recapture memory that was used by objects that are no longer being used by your program. Should its thread have higher or lower priority than your program?

The Asynchronous Nature of Threaded Programs

Threads are asynchronous. This means that the order of execution and the timing of a set of threads are unpredictable, at least from the programmer’s point of view. Threads are executed under the control of the scheduling algorithm used by the operating system and the Java Virtual Machine. In general, unless threads are explicitly synchronized, it is impossible for the programmer to predict when and for how long an individual thread will run. In some systems, under some circumstances, a thread might run to completion before any other thread can run. In other systems, or under different circumstances, a thread might run for a short time and then be suspended while another thread runs. Of course, when a thread is preempted by the system, its state is saved so that its execution can be resumed without losing any information.

One implication of a thread’s asynchronicity is that it is not generally possible to determine where in its source code an individual thread might be preempted. You can’t even assume that a thread will be able to complete a simple Java arithmetic operation once it has started it. For example, suppose a thread had to execute the following operation:

This operation computes the sum of 5 and 3 and assigns the result to N. It would be tempting to think that once the thread started this operation, it would be able to complete it, but that is not necessarily so. You have to remember that Java code is compiled into a rudimentary bytecode, which is translated still further into the computer’s machine language. In machine language, this operation would break down into something like the following three steps:

Although none of the individual machine instructions can be preempted, the thread could be interrupted between any two machine instructions. The point here is that not even a single Java language instruction can be assumed to be indivisible or unpreemptible. Therefore, it is impossible to make any assumptions about when a particular thread will run and when it will give up the CPU. This suggests the following important principle Threads are of multithreaded programs:

As we will see, this principle plays a large role in the design of multithreaded programs.

14.4 Thread States and Life Cycle

Each thread has a life cycle that consists of several different states, which are summarized in Figure 14.6 and Table 14.1. Thread states are represented by labeled ovals, and the transitions between states are repreReady, running, and sleeping sented by labeled arrows. Much of a thread’s life cycle is under the control of the operating system and the Java Virtual Machine. Those Controlling a thread transitions represented by method names—such as start(), stop(), wait(), sleep(), notify()—can be controlled by the program. Of these methods, the stop() method has been deprecated in JDK 1.2 because it is inherently unsafe to stop a thread in the middle of its execution. Other transitions—such as dispatch, I/O request, I/O done, time expired, done sleeping—are under the control of the CPU scheduler. When first created a thread is in the ready state, which means that it is ready to run. In the ready state, a thread is waiting, perhaps with other threads, in the ready queue, for its turn on the CPU. A queue is like a waiting line. When the CPU becomes available, the first thread in the ready queue will be dispatched—that is, it will be given the CPU. It will then be in the running state.

Figure 14.6: A depiction of a thread’s life cycle.

Transitions between the ready and running states happen under the control of the CPU scheduler, a fundamental part of the Java runtime system. The job of scheduling many threads in a fair and efficient manner is a little like sharing a single bicycle among several children. Children who are ready to ride the bike wait in line for their turn. The grown up (scheduler) lets the first child (thread) ride for a period of time before the bike is taken away and given to the next child in line. In round-robin scheduling, each child (thread) gets an equal amount of time on the bike (CPU).

When a thread calls the sleep() method, it voluntarily gives up the CPU, and when the sleep period is over, it goes back into the ready queue. This would be like one of the children deciding to rest for a moment during his or her turn. When the rest was over, the child would get back in line.

When a thread calls the wait() method, it voluntarily gives up the CPU, but this time it won’t be ready to run again until it is notified by some other thread.

This would be like one child giving his or her turn to another child. When the second child’s turn is up, it would notify the first child, who would then get back in line.

The system also manages transitions between the blocked and ready states. A thread is put into a blocked state when it does some kind of I/O operation. I/O devices, such as disk drives, modems, and keyboards, are very slow compared to the CPU. Therefore, I/O operations are handled by separate processors known as controllers. For example, when a thread wants to read data from a disk drive, the system will give this task to the disk controller, telling it where to place the data. Because the thread can’t do anything until the data is read, it is blocked, and another thread is allowed to run. When the disk controller completes the I/O operation, the blocked thread is unblocked and placed back in the ready queue.

In terms of the bicycle analogy, blocking a thread would be like giving the bicycle to another child when the rider has to stop to tie his or her shoe. Instead of letting the bicycle just sit there, we let another child ride it. When the shoe is tied, the child is ready to ride again and goes back into the ready line. Letting other threads run while one thread is waiting for an I/O operation to complete improves the overall utilization of the CPU.

SELF-STUDY EXERCISE 

EXERCISE 14.5 Round-robin scheduling isn’t always the best idea. Sometimes priority scheduling leads to a better system. Can you think of ways that priority scheduling—higher-priority threads go to the head of the line—can be used to improve the responsiveness of an interactive program?

14.5 Using Threads to Improve Interface Responsiveness

One good use for a multithreaded program is to help make a more responsive user interface. In a single-threaded program, a program that is executing statements in a long (perhaps even infinite) loop remains unresponsive to the user’s actions until the loop is exited. Thus, the user will experience a noticeable and sometimes frustrating delay between the time an action is initiated and the time it is actually handled by the program.

Single-Threaded Design

It’s always a good idea that the interface be responsive to user input, but sometimes it is crucial to an application. For example, suppose a psychology experiment is trying to measure how quickly a user responds to a certain stimulus presented by a program. Obviously, for this kind of application, the program should take action as soon as the user clicks a button to indicate a response to the stimulus. Let’s work through an appropriate program design for the experiment. First, we will formally state the situation and describe what the program should do. Then, we will examine the components that would make up an effective program.

Problem Statement

A psychologist is conducting a psychometric experiment to measure user response to a visual cue and asks you to create the following program. The program should have two buttons. When the Draw button is clicked, the program begins drawing thousands of black dots at random locations within a rectangular region of the screen (Fig. 14.7). After a random time interval, the program begins drawing red dots. This change corresponds to the presentation of the stimulus. As soon as the stimulus is presented the user is supposed to click on a Clear button, which clears the drawing area. To provide a measure of the user’s reaction time, the program should report how many red dots were drawn before the user clicked the Clear button.

Figure 14.8: GUI design for the dot-drawing

ogram. Figure 14.8 shows a design for this program’s GUI. It contains a control JPanel that contains the two JButtons. The dots are drawn on a JPanel, which is positioned in the center of a BorderLayout design. 

Problem Decomposition 

This program should be decomposed into two classes, a GUI to handle the user interface and a drawing class to manage the drawing. The main features of its classes are as follows: 

• RandomDotGUI Class: This class manages the user interface, responding to user actions by calling methods of the Dotty class (Fig. 14.9). 
• Dotty Class: This class contains draw() and clear() methods for drawing on the GUI’s drawing panel (Fig. 14.10)

The RandomDotGUI Class

Note that Dotty is passed a reference to the drawing canvas as well as the number of dots to be drawn. When the user clicks the Clear button, the GUI should call the dotty.clear() method. Of course, the important question is, how responsive will the GUI be to the user's action?

The Dotty Class 

The purpose of the Dotty class will be to draw the dots and to report how many red dots were drawn before the canvas was cleared. Because it will be passed a reference to the drawing panel and the number of dots to draw, the Dotty class will need instance variables to store these two values. It will also need a variable to keep track of how many dots were drawn. Finally, since it will be drawing within a fixed rectangle on the panel, the reference coordinates and dimensions of the drawing area are declared as class constants. 

The Dotty() constructor method will pass a reference to a drawing panel as well as the number of dots to be drawn and will merely assign these parameters to its instance variables. In addition to its constructor method, the Dotty class will have public draw() and clear() methods, which will be called from the GUI. The draw() method will use a loop to draw random dots. The clear() will clear the canvas and report the number of dots drawn.

The complete implementation of Dotty is shown in Figure 14.12. Note how its draw() method is designed. The drawing loop is bounded by the number of dots to be drawn. On each iteration, the draw() method picks a random location within the rectangle defined by the coordinates (HREF,VREF) and (HREF+LEN, VREF+LEN), and draws a dot there. On each iteration it also generates a random number. If the random number is less than 0.001, it changes the drawing color to red and keeps track of the number of dots drawn up to that point.

Figure 14.12: The Dotty class, single-threaded version.

The problem with this design is that as long as the draw() method is executing, the program will be unable to respond to the GUI’s Clear button. In a single-threaded design, both the GUI and dotty are combined into a single thread of execution (Fig. 14.13). When the user clicks the Draw button, the GUI’s actionPerformed() method is invoked. It then invokes Dotty’s draw() method, which must run to completion before anything else can be done. If the user clicks the Clear button while the dots are being drawn, the GUI won’t be able to get to this until all the dots are drawn.

If you run this program with nDots set to 10,000, the program will not clear the drawing panel until all 10,000 dots are drawn, no matter when the Clear button is pressed. Therefore, the values reported for the user’s reaction time will be wrong. Obviously, since it is so unresponsive to user input, this design completely fails to satisfy the program’s specifications.

SELF-STUDY EXERCISE 

EXERCISE 14.6 Suppose the Java Virtual Machine (JVM) was single threaded and your program got stuck in an infinite loop. Would you be able to break out of the loop by typing some special command (such as Control-C) from the keyboard?

Multithreaded Drawing: The Dotty Thread

One way to remedy this problem is to create a second thread (in addition to the GUI itself) to do the drawing. The drawing thread will be responsible just for drawing, while the GUI thread will be responsible for handling user actions in the interface. The trick to making the user interface more responsive will be to interrupt the drawing thread periodically so that the GUI thread has a chance to handle any events that have occurred.

As Figure 14.14 illustrates, the easiest way to convert Dotty into a thread is to have it implement the Runnable interface:

This version of Dotty will perform the same task as before except that it will now run as a separate thread of execution. Note that its run() method just calls the draw() method that we defined in the previous version. When the Dotty thread is started by the RandomDotGUI, we will have a multithreaded program. 

However, just because this program has two threads doesn’t necessarily mean that it will be any more responsive to the user. There’s no guarantee that the drawing thread will stop as soon as the Clear button is clicked. On most systems, if both threads have equal priority, the GUI thread won’t run until the drawing thread finishes drawing all N dots.

Therefore, we have to modify our design in order to guarantee that the GUI thread will get a chance to handle the user’s actions. One good way to do this is to have Dotty sleep for a short instance after it draws each dot. When a thread sleeps, any other threads that are waiting their turn the will get a chance to run. If the GUI thread is waiting to handle the user’s click on Clear, it will now be able to call Dotty’s clear() method.

The new version of draw() is shown in Figure 14.15. In this version of draw(), the thread sleeps for 1 millisecond on each iteration of the loop. This will make it possible for the GUI to run on every iteration, so it will handle user actions immediately.

Another necessary change is that once the clear() method is called, the Dotty thread should stop running (drawing). The correct way to stop a thread is to use some variable whose value will cause the run loop (or in this case the drawing loop) to exit, so the new version of Dotty uses the boolean variable isCleared to control when drawing is stopped. Note that the variable is initialized to false and then set to true in the clear() method. The for loop in draw() will exit when isCleared becomes true. This causes the draw() method to return, which causes the run() method to return, which causes the thread to stop in an orderly fashion.

Modifications to RandomDotGUI 

We don’t need to make many changes in RandomDotGUI to get it to work with the new version of Dotty. The primary change comes in the actionPerformed() method. Each time the Draw button was clicked in the original version of this method, we created a dotty instance and then called its draw() method. 

Figure 14.15: By implementing the Runnable interface, this version of Dotty can run as a separate thread.

In the revised version we must create a new Thread and pass it an instance of Dotty, which will then run as a separate thread:

Note that in addition to a reference to dotty we also have a reference to a Thread named dottyThread. This additional variable must be declared within the GUI.

Remember that when you call the start() method, it automatically calls the thread’s run() method. When dottyThread starts to run, it will immediately call the draw() method and start drawing dots. After each dot is drawn, dottyThread will sleep for an instant.

Notice how the GUI stops the drawing thread. In the new version, Dotty.clear() will set the isCleared variable, which will cause the drawing loop to terminate. Once again, this is the proper way to stop a thread. Thus, as soon as the user clicks the Clear button, the Dotty thread will stop drawing and report its result.

Advantages of Multithreaded Design

By creating a separate thread for Dotty, we have turned a single-threaded program into a multithreaded program. One thread, the GUI, handles the user interface. The second thread handles the drawing task. By forcing the drawing to sleep on each iteration, we guarantee that the GUI thread will remain responsive to the user’s actions. Figure 14.16 illustrates the difference between the single- and multithreaded designs. Note that the GUI thread starts and stops the drawing thread, and the GUI thread executes dotty.clear(). The drawing thread simply executes its draw() method. In the single-threaded version, all of these actions are done by one thread.

The trade-off involved in this design is that it will take longer to draw N random dots, since dottyThread.draw() will sleep for an instant on each iteration. However, the extra time is hardly noticeable. By breaking the program into two separate threads of control, one to handle the drawing task and one to handle the user interface, the result is a much more responsive program.

Figure 14.16: Two independent threads: one for drawing, the other for the GUI.

SELF-STUDY EXERCISES 

EXERCISE 14.7 Someone might argue that because the Java Virtual Machine uses a round-robin scheduling algorithm, it’s redundant to use the sleep() method, since the GUI thread will get its chance to run. What’s wrong with this argument for interface responsiveness? 

EXERCISE 14.8 Instead of sleeping on each iteration, another way to make the interface more responsive would be to set the threaded Dotty’s priority to a low number, such as 1. Make this change, and experiment with its effect on the program’s responsiveness. Is it more or less responsive than sleeping on each iteration? Why?

14.6 CASE STUDY: Cooperating Threads

For some applications it is necessary to synchronize and coordinate the behavior of threads to enable them to carry out a cooperative task. Many cooperative applications are based on the producer/consumer model. According to this model, two threads cooperate at producing and consuming a particular resource or piece of data. The producer thread creates some message or result, and the consumer thread reads or uses the result. The consumer has to wait for a result to be produced, and the producer has to take care not to overwrite a result that hasn’t yet been consumed. Many types of coordination problems fit the producer/consumer model.

One example of an application for this model would be to control the display of data that is read by your browser. As information arrives from the Internet, it is written to a buffer by the producer thread. A separate consumer thread reads information from the buffer and displays it in your browser window. Obviously, the two threads must be carefully synchronized.

Problem Statement

To illustrate how to address the sorts of problems that can arise when you try to synchronize threads, let’s consider a simple application in which several threads use a shared resource. You’re familiar with those take- a-number devices that are used in bakeries to manage a waiting line. Customers take a number when they arrive, and the clerk announces who’s next by looking at the device. As customers are called, the clerk increments the “next customer” counter by one.

There are some obvious potential coordination problems here. The device must keep proper count and can’t skip customers. Nor can it give the same number to two different customers. Nor can it allow the clerk to serve nonexistent customers.

Our task is to build a multithreaded simulation that uses a model of a take-a-number device to coordinate the behavior of customers and a (single) clerk in a bakery waiting line. To help illustrate the various issues involved in trying to coordinate threads, we will develop more than one version of the program.

Problem Decomposition

This simulation will use four classes of objects. Figure 14.17 provides a UML representation of the interactions among the objects. The

Figure 14.17: The Bakery creates the Customer and Clerk threads and the TakeANumber gadget. Then Customers request and receive waiting numbers and the Clerk requests and receives the number of the next customer to serve.

TakeANumber object will serve as a model of a take-a-number device. This is the resource that will be shared by the threads, but it is not a thread itself. The Customer class, a subclass of Thread, will model the behavior of a customer who arrives online and takes a number from the TakeANumber device. There will be several Customer threads created that then compete for a space in line. The Clerk thread, which simulates the behavior of the store clerk, should use the TakeANumber device to determine who the next customer is and should serve that customer. Finally, there will be a main program that will have the task of creating and starting the various threads. Let’s call this the Bakery class, which gives us the following list of classes:

• Bakery—creates the threads and starts the simulation. 
• TakeANumber—represents the gadget that keeps track of the next customer to be served. 
• Clerk—uses the TakeANumber to determine the next customer and will serve the customer. 
• Customer—represents the customers who will use the TakeANumber to take their place in line.

Design: The TakeANumber Class

The TakeANumber class must track two things: Which customer will be served next, and which waiting number the next customer will be given. This suggests that it should have at least two public methods: nextNumber(), which will be used by customers to get their waiting numbers, and nextCustomer(), which will be used by the clerk to determine who should be served (Fig. 14.18). Each of these methods will simply retrieve the values of the instance variables, next and serving, which keep track of these two values. As part of the object’s state, these variables should be private. 

How should we make this TakeANumber object accessible to all of the other objects—that is, to all of the customers and to the clerk? The easiest way to do that is to have the main program pass a reference to the TakeANumber when it constructs the Customers and the Clerk. They can each store the reference as an instance variable. In this way, all the objects in the simulation can share a TakeANumber object as a common resource. Our design considerations lead to the definition of the TakeANumber class shown in Figure 14.1

Note that the nextNumber() method is declared synchronized. As we will discuss in more detail, this ensures that only one customer at a time can take a number. Once a thread begins executing a synchronized method, no other thread can execute that method until the first thread finishes. This is important because, otherwise, several Customers could call the nextNumber method at the same time. It’s important that the customer threads have access only one at a time, also called mutually exclusive access to the TakeANumber object. This form of mutual exclusion is important for the correctness of the simulation.

SELF-STUDY EXERCISE 

EXERCISE 14.9 What is the analogue to mutual exclusion in the real world bakery situation?

Java Monitors and Mutual Exclusion

An object that contains synchronized methods has a monitor associated with it. A monitor is a widely used synchronization mechanism that ensures that only one thread at a time can execute a synchronized method. When a synchronized method is called, a lock is acquired on that object. For example, if one of the Customer threads calls nextNumber(), a lock will be placed on that TakeANumber object. While an object is locked, no other synchronized method can run in that object. Other threads must wait for the lock to be released before they can execute a synchronized method.

While one Customer is executing nextNumber(), all other Customers will be forced to wait until the first Customer is finished. When the synchronized method is exited, the lock on the object is released, allowing other Customer threads to access their synchronized methods. In effect, a synchronized method can be used to guarantee mutually exclusive access to the TakeANumber object among the competing customers.

One cautionary note here is that although a synchronized method blocks access to other synchronized methods, it does not block access to non-synchronized methods. This could cause problems. We will return to this issue in the next part of our case study when we discuss the testing of our program.

The Customer Class

A Customer thread should model the behavior of taking a number from the TakeANumber gadget. For the sake of this simulation, let’s suppose that after taking a number, the Customer object just prints it out. This will serve as a simple model of “waiting on line.” What about the Customer’s state? To help distinguish one customer from another, let’s give each customer a unique ID number starting at 10001, which will be set in the constructor method. Also, as we noted earlier, each Customer needs a reference to the TakeANumber object, which is passed as a constructor parameter (Fig. 14.20). This leads to the definition of Customer shown in Figure 14.21. Note that before taking a number the customer sleeps for a random interval of up to 1,000 milliseconds. This will introduce a bit of randomness into the simulation.

Another important feature of this definition is the use of the static variable number to assign each customer a unique ID number. Remember that a static variable belongs to the class itself, not to its instances. Therefore, each Customer that is created can share this variable. By incrementing it and assigning its new value as the Customer’s ID, we guarantee that each customer has a unique ID number.

The Clerk Class

The Clerk thread should simulate the behavior of serving the next customer in line, so the Clerk thread will repeatedly access TakeANumber.nextCustomer() and then serve that customer.  For the sake of this simulation, we’ll just print a message to indicate which customer is being served. Because there’s only one clerk in this simulation, the only variable in its internal state will be a reference to the TakeANumber object (Fig. 14.22). In addition to the constructor, all we really need to define for this class is the run() method. This leads to the definition of Clerk shown in Figure 14.23. In this case, the sleep() method is necessary to allow the Customer threads to run. The Clerk will sit in an infinite loop serving the next customer on each iteration.

The Bakery Class

Finally, Bakery is the simplest class to design. It contains the main() method, which gets the whole simulation started. As we said, its role will be to create one Clerk thread and several Customer threads, and get them all started (Fig. 14.24). Notice that the Customers and the Clerk are each passed a reference to the shared TakeANumber gadget.

Problem: Nonexistent Customers

Now that we have designed and implemented the classes, let’s run several experiments to test that everything works as intended. Except for the synchronized nextNumber() method, we’ve made little attempt to make sure that the Customer and Clerk threads will work together cooperatively, without violating the real-world constraints that should be satisfied by the simulation. If we run the simulation as it is presently 

coded, it will generate five customers and the clerk will serve all of them. But we get something like the following output:

Our current solution violates an important real-world constraint: You can’t serve customers before they enter the line! How can we ensure that the clerk doesn’t serve a customer unless there’s actually a customer waiting?

The wrong way to address this issue would be to increase the amount of sleeping that the Clerk does between serving customers. Indeed, this would allow more customer threads to run, so it might appear to have the desired effect, but it doesn’t truly address the main problem: A clerk cannot serve a customer if no customer is waiting.

The correct way to solve this problem is to have the clerk check that there are customers waiting before taking the next customer. One way to model this would be to add a customerWaiting() method to our TakeANumber object. This method would return true whenever next is greater than serving. That will correspond to the real-world situation in which the clerk can see customers waiting in line. We can make the following modification to Clerk.run():

And we add the following method to TakeANumber (Fig. 14.25): 

In other words, the Clerk won’t serve a customer unless there are customers waiting—that is, unless next is greater than serving. Given these changes, we get the following type of output when we run the simulation:

This example illustrates that when application design involves cooperating threads, the algorithm used must ensure the proper cooperation and coordination among the threads.

Problem: Critical Sections

It is easy to forget that thread behavior is asynchronous. You can’t predict when a thread might be interrupted or might have to give up the CPU to another thread. In designing applications that involve cooperating threads, it’s important that the design incorporates features to guard against problems caused by asynchronicity. To illustrate this problem, consider the following statement from the Customer.run() method:

Even though this is a single Java statement, it breaks up into several Java bytecode statements. A Customer thread could certainly be interrupted between getting the next number back from TakeANumber and printing it out. We can simulate this by breaking the println() into two statements and putting a sleep() in their midst:

If this change is made in the simulation, you might get the following output:

Because the Customer threads are now interrupted in between taking a number and reporting their number, it looks as if they are being served in the wrong order. Actually, they are being served in the correct order. It’s their reporting of their numbers that is wrong!

The problem here is that the Customer.run() method is being interrupted in such a way that it invalidates the simulation’s output. A section method that displays the simulation’s state should be designed so that once a thread begins reporting its state, that thread will be allowed to finish reporting before another thread can start reporting its state. Accurate reporting of a thread’s state is a critical element of the simulation’s overall integrity.

A critical section is any section of a thread that should not be interrupted during its execution. In the bakery simulation, all of the statements that report the simulation’s progress are critical sections. Even though the chances are small that a thread will be interrupted in the midst of a println() statement, the faithful reporting of the simulation’s state should not be left to chance. Therefore, we must design an algorithm that prevents the interruption of critical sections.

Creating a Critical Section

The correct way to address this problem is to treat the reporting of the customer’s state as a critical section. As we saw earlier when we discussed the concept of a monitor, a synchronized method within a shared object ensures that once a thread starts the method, it will be allowed to finish it before any other thread can start it. Therefore, one way out of this dilemma is to redesign the nextNumber() and nextCustomer() uninterruptible methods in the TakeANumber class so that they report which customer receives a ticket and which customer is being served (Fig. 14.26). In this version all of the methods are synchronized, so all the actions of the TakeANumber object are treated as critical sections.

Note that the reporting of both the next number and the next customer to be served are now handled by TakeANumber in Figure 14.26 . Because the methods that handle these actions are synchronized, they cannot be interrupted by any threads involved in the simulation. This guarantees that the simulation’s output will faithfully report the simulation’s state.

Given these changes to TakeANumber, we must remove the println() statements from the run() methods in Customer:

and from the run() method in Clerk:

Rather than printing their numbers, these methods now just call the appropriate methods in TakeANumber. Given these design changes, our simulation now produces the following correct output:

The lesson to be learned from this is that in designing multithreaded programs, it is important to assume that if a thread can be interrupted at a certain point, it will be interrupted at that point. The fact that an interrupt is unlikely to occur is no substitute for the use of a critical section. This is something like “Murphy’s Law of Thread Coordination.”

In a multithreaded application, the classes and methods should be designed so that undesirable interrupts will not affect the correctness of the algorithm.

SELF-STUDY EXERCISE 

EXERCISE 14.10 Given the changes we’ve described, the bakery simulation should now run correctly regardless of how slow or fast the Customer and Clerk threads run. Verify this by placing different-sized sleep intervals in their run() methods. (Note: You don’t want to put a sleep() in the synchronized methods because that would undermine the whole purpose of making them synchronized in the first place.)

Using wait/notify to Coordinate Threads

The examples in the previous sections were designed to illustrate the issue of thread asynchronicity and the principles of mutual exclusion and critical sections. Through the careful design of the algorithm and the appropriate use of the synchronized qualifier, we have managed to design a program that correctly coordinates the behavior of the Customers and Clerk in this bakery simulation.

The Busy-Waiting Problem

One problem with our current design of the Bakery algorithm is that it uses busy waiting on the part of the Clerk thread. Busy waiting occurs when a thread, while waiting for some condition to change, executes a loop instead of giving up the CPU. Because busy waiting is wasteful of CPU time, we should modify the algorithm.

As it is presently designed, the Clerk thread sits in a loop that repeatedly checks whether there’s a customer to serve:

A far better solution would be to force the Clerk thread to wait until a customer arrives without using the CPU. Under such a design, the Clerk thread can be notified and enabled to run as soon as a Customer becomes available. Note that this description views the customer/clerk relationship as one-half of the producer/consumer relationship. When a customer takes a number, it produces a customer in line that must be served (that is, consumed) by the clerk.

This is only half the producer/consumer relationship because we haven’t placed any constraint on the size of the waiting line. There’s no real limit to how many customers can be produced. If we did limit the line size, customers might be forced to wait before taking a number if, say, the tickets ran out, or the bakery filled up. In that case, customers would have to wait until the line resource became available and we would have a full-fledged producer/consumer relationship.

The wait/notify Mechanism

So, let’s use Java’s wait/notify mechanism to eliminate busy waiting from our simulation. As noted in Figure 14.6, the wait() method puts a thread into a waiting state, and notify() takes a thread out of waiting and places it back in the ready queue. To use these methods in this program we need to modify the nextNumber() and nextCustomer() methods. If there is no customer in line when the Clerk calls the nextCustomer() method, the Clerk should be made to wait():

Note that the Clerk still checks whether there are customers waiting. If there are none, the Clerk calls the wait() method. This removes the Clerk from the CPU until some other thread notifies it, at which point it will be ready to run again. When it runs again, it should check that there is in fact a customer waiting before proceeding. That’s why we use a while loop here. In effect, the Clerk will wait until there’s a customer to serve. This is not busy waiting because the Clerk thread loses the CPU and must be notified each time a customer becomes available.

When and how will the Clerk be notified? Clearly, the Clerk should be notified as soon as a customer takes a number. Therefore, we put a notify() in the nextNumber() method, which is the method called by each Customer as it gets in line:

Thus, as soon as a Customer thread executes the nextNumber() method, the Clerk will be notified and allowed to proceed.

What happens if more than one Customer has executed a wait()? In that case, the JVM will maintain a queue of waiting Customer threads. Then, each time a notify() is executed, the JVM will take the first Customer out of the queue and allow it to proceed.

If we use this model of thread coordination, we no longer need to test customerWaiting() in the Clerk.run() method. It is to be tested in the TakeANumber.nextCustomer(). Thus, the Clerk.run() can be simplified to

The Clerk thread may be forced to wait when it calls the nextCustomer method.

Because we no longer need the customerWaiting() method, we end up with the new definition of TakeANumber shown in Figures 14.27 and 14.28. 

Given this version of the program, the following kind of output will be generated:

SELF-STUDY EXERCISE

EXERCISE 14.11 An interesting experiment to try is to make the Clerk a little slower by making it sleep for up to 2,000 milliseconds. Take a guess at what would happen if you ran this experiment. Then run the experiment and observe the results.

The wait/notify Mechanism 

There are a number of important restrictions that must be observed when using the wait/notify mechanism: methods:

• Both wait() and notify() are methods of the Object class, not the Thread class. This enables them to lock objects, which is the essential feature of Java’s monitor mechanism. 
• A wait() method can be used within a synchronized method. The method doesn’t have to be part of a Thread. 
• You can only use wait() and notify() within synchronized methods. If you use them in other methods, you will cause an IllegalMonitorStateException with the message “current thread not owner.” 
• When a wait()—or a sleep()—is used within a synchronized method, the lock on that object is released so that other methods can access the object’s synchronized methods.

14.7 CASE STUDY: The Game of Pong

The game of Pong was one of the first computer video games and was all the rage in the 1970s. The game consists of a ball that moves horizontally and vertically within a rectangular region, and a single paddle, which is located at the right edge of the region that can be moved up and down by the user. When the ball hits the top, left, or bottom walls or the paddle, it bounces off in the opposite direction. If the ball misses the paddle, it passes through the right wall and re-emerges at the left wall. Each time the ball bounces off a wall or paddle, it emits a pong sound.

A Multithreaded Design

Let’s develop a multithreaded GUI to play the game of Pong.

Figure 14.29 shows how the game’s GUI should appear. There are three objects involved in this program: the frame, which serves as the GUI, the ball, which is represented as a blue circle in the program, and the paddle, which is represented by a red rectangle along the right edge of the frame. What cannot be seen in this figure is that the ball moves autonomously, bouncing off the walls and paddle. The paddle’s motion is controlled by the user by pressing the up- and down-arrow keys on the keyboard.

We will develop class definitions for the ball, paddle, and the frame. Following the example of our dot-drawing program earlier in the Chapter, we will employ two independent threads, one for the GUI and one for the ball. Because the user will control the movements of the paddle, the frame will employ a listener object to listen for and respond to the user’s key presses.

Figure 14.30 provides an overview of the object-oriented design of the Pong program. The PongFrame class is the main class. It uses instances of the Ball and Paddle classes. PongFrame is a subclass of JFrame and implements the KeyListener interface.

Figure 14.30: Design of the Pong program.

This is another of the several event handlers provided in the java.awt library. This one handles KeyEvents and the KeyListener interface consists of three abstract methods: keyPressed(), keyTyped(), and keyReleased(), all of which are associated with the act of pressing a key on the keyboard. All three of these methods are implemented in the PongFrame class. A key-typed event occurs when a key is pressed down. A key-release event occurs when a key that has been pressed down is released. A key-press event is a combination of both of these events.

The Ball class is a Thread subclass. Its data and methods are designed mainly to keep track of its motion within the program’s drawing panel. The design strategy employed here leaves the drawing of the ball up to the frame. The Ball thread itself just handles the movement within the program’s drawing panel. Note that the Ball() constructor takes a reference to the PongFrame. As we will see, the Ball uses this reference to set the dimensions of the frame’s drawing panel. Also, as the Ball moves, it will repeatedly call the frame’s repaint() method to draw the ball.

The Paddle class is responsible for moving the paddle up and down along the drawing panel’s right edge. Its public methods, moveUP() and moveDown(), will be called by the frame in response to the user pressing the up and down arrows on the keyboard. Because the frame needs to know where to draw the paddle, the paddle class contains several public methods, getX(), getY(), and resetLocation(), whose tasks are to report the paddle’s location or to adjust its location in case the frame is resized.

The PongFrame controls the overall activity of the program. Note in particular its ballHitsPaddle() method. This method has the task of determining when the ball and paddle come in contact as the ball continuously moves around in the frame’s drawing panel. As in the ThreadedDotty example earlier in the chapter, it is necessary for the Ball and the the frame to be implemented as separated threads so that the frame can be responsive to the user’s key presses.

Implementation of the Pong Program

We begin our discussion of the program’s implementation with the Paddle class implementation (Fig. 14.31).

Class constants, HEIGHT and WIDTH are used to define the size of the Paddle, which is represented on the frame as a simple rectangle. The frame will use the Graphics.fillRect() method to draw the paddle:

Note how the frame uses the paddle’s getX() and getY() methods to get the paddle’s current location.

The class constants DELTA and BORDER are used to control the paddle’s movement. DELTA represents the number of pixels that the paddle moves on each move up or down, and BORDER is used with gameAreaHeight to keep the paddle within the drawing area. The moveUp() and moveDown() methods are called by the frame each time the user presses an up- or down-arrow key. They simply change the paddle’s location by DELTA pixels up or down.

The Ball class (Fig. 14.32) uses the class constant SIZE to determine the size of the oval that represents the ball, drawn by the frame as follows:

As with the paddle, the frame uses the ball’s getX() and getY() method to determine the ball’s current location.

Unlike the paddle, however, the ball moves autonomously. Its run() method, which is inherited from its Thread superclass, repeatedly moves the ball, draws the ball, and then sleeps for a brief interval (to slow down the speed of the ball’s apparent motion). The run() method itself is quite simple because it consists of a short loop. We will deal with the details of how the ball is painted on the frame when we discuss the frame itself.

The most complex method in the Ball class is the move() method. This is the method that controls the ball’s movement within the boundaries of the frame’s drawing area. This method begins by moving the ball by one pixel left, right, up, or down by adjusting the values of its locationX and locationY coordinates:

The directionX and directionY variables are set to either +1 or 1, depending on whether the ball is moving left or right, up or down. After the ball is moved, the method uses a sequence of if statements to check whether the ball is touching one of the walls or the paddle. If the ball is in contact with the top, left, or bottom walls or the paddle, its direction is changed by reversing the value of the directionX or directionY variable. The direction changes depend on whether the ball has touched a horizontal or vertical wall. When the ball touches the right wall, having missed the paddle, it passes through the right wall and re-emerges from the left wall going in the same direction.

Note how the frame method, ballHitsPaddle() is used to determine whether the ball has hit the paddle. This is necessary because only the frame knows the locations of both the ball and the paddle.

The KeyListener Interface

The implementation of the PongFrame class is shown in figure 14.33. The frame’s main task is to manage the drawing of the ball and paddle and to handle the user’s key presses. Handling keyboard events is a simple matter of implementing the KeyListener interface. This works in much the same way as the ActionListener interface, which is used to handle button clicks and other ActionEvents. Whenever a key is pressed, it generates KeyEvents, which are passed to the appropriate methods of the KeyListener interface.

There’s a bit of redundancy in the KeyListener interface in the sense that a single key press and release generates three KeyEvents: A keytyped event, when the key is pressed, a key-released event, when the key is released, and a key-pressed event, when the key is pressed and released. While it is important for some programs to be able to distinguish between a key-typed and key-released event, for this program, we will take action whenever one of the arrow keys is pressed (typed and released). Therefore, we implement the keyPressed() method as follows:

Each key on the keyboard has a unique code that identifies the key. The key’s code is gotten from the KeyEvent object by means of the

getKeyCode() method. Then it is compared with the codes for the uparrow and down-arrow keys, which are implemented as class constants, VK UP and VK DOWN, in the KeyEvent class. If either of those keys were typed, the appropriate paddle method, moveUP() or moveDown(), is called.

Note that even though we are not using the keyPressed() and keyReleased() methods in this program, it is still necessary to provide implementations for these methods in the frame. In order to implement an interface, such as the KeyListener interface, you must implement all the abstract methods in the interface. That is why we provide trivial implementations of both the keyPressed() and keyReleased() methods.

Animating the Bouncing Ball

Computer animation is accomplished by repeatedly drawing, erasing, and re-drawing an object at different locations on the drawing panel. The frame’s paint() method is used for drawing the ball and the paddle at their current locations. The paint() method is never called directly. Rather, it is called automatically after the constructor method PongFrame(), when the program is started. It is then invoked indirectly by the program by calling the repaint() method, which is called in the run() method of the Ball class. The reason that paint() is called indirectly is because Java needs to pass it the frame’s current Graphics object. Recall that in Java all drawing is done using a Graphics object.

In order to animate the bouncing ball, we first erase the current image of the ball, then we draw the ball in its new location. We also draw the paddle in its current location. These steps are carried out in the frame’s paint() method. First, the drawing area is cleared by painting its rectangle in the background color. Then the ball and paddle are painted at their current locations. Note that before painting the paddle, we first call its resetLocation() method. This causes the paddle to be relocated in case the user has resized the frame’s drawing area. There is no need to do this for the ball because the ball’s drawing area is updated within the Ball.move() method every time the ball is moved.

One problem with computer animations of this sort is that the repeated Double buffering drawing and erasing of the drawing area can cause the screen to flicker. In some drawing environments a technique known as double buffering is used to reduce the flicker. In double buffering, an invisible, off-screen, buffer is used for the actual drawing operations and it is then used to replace the visible image all at once when the drawing is done. Fortunately, Java’s Swing components, including JApplet and JFrame, perform an automatic form of double buffering, so we needn’t worry about it. Some graphics environments, including Java’s AWT environment, do not perform double buffering automatically, in which case the program itself must carry it out.

Like the other examples in this chapter, the game of Pong provides a simple illustration of how threads are used to coordinate concurrent actions in a computer program. As most computer game fans will realize, most modern interactive computer games utilize a multithreaded design. The use of threads allows our interactive programs to achieve a responsiveness and sophistication that is not possible in single-threaded programs. One of the great advantages of Java is that it simplifies the use of threads, thereby making thread programming accessible to programmers. However, one of the lessons that should be drawn from this chapter is that multithreaded programs must be carefully designed in order to work effectively.

SELF-STUDY EXERCISE 

EXERCISE 14.12 Modify the PongFrame program so that it contains a second ball that starts at a different location from the first ball.

CHAPTER SUMMARY

Technical Terms 

• asynchronous 
• blocked 
• busy waiting 
• concurrent 
• critical section 
• dispatched 
• fetch-execute cycle 
• lock 
• monitor 
• multitasking 
• multithreaded 
• mutual exclusion 
• priority scheduling 
• producer/consumer model 
• quantum 
• queue 
• ready queue 
• round-robin scheduling 
• scheduling algorithm 
• task 
• thread 
• thread life cycle 
• time slicing

Summary of Important Points 

• Multitasking is the technique of executing several tasks at the same time within a single program. In Java we give each task a separate thread of execution, thus resulting in a multithreaded program. 
• A sequential computer with a single central processing unit (CPU) can execute only one machine instruction at a time. A parallel computer uses multiple CPUs operating simultaneously to execute more than one instruction at a time. 
• Each CPU uses a fetch-execute cycle to retrieve the next machine instruction from memory and execute it. The cycle is under the control of the CPU’s internal clock, which typically runs at several hundred megahertz—where 1 megahertz (MHz) is 1 million cycles per second. 
• Time slicing is the technique whereby several threads can share a single CPU over a given time period. Each thread is given a small slice of the CPU’s time under the control of some kind of scheduling algorithm.
• In round-robin scheduling, each thread is given an equal slice of time, in a first-come–first-served order. In priority scheduling, higher-priority threads are allowed to run before lower-priority threads are run. 
• There are generally two ways of creating threads in a program. One is to create a subclass of Thread and implement a run() method. The other is to create a Thread instance and pass it a Runnable object— that is, an object that implements run(). 
• The sleep() method removes a thread from the CPU for a determinate length of time, giving other threads a chance to run. 
• The setPriority() method sets a thread’s priority. Higher-priority threads have more and longer access to the CPU.
• Threads are asynchronous. Their timing and duration on the CPU are highly sporadic and unpredictable. In designing threaded programs, you must be careful not to base your algorithm on any assumptions about the threads’ timing. 
• To improve the responsiveness of interactive programs, you could give compute-intensive tasks, such as drawing lots of dots, to a lower priority thread or to a thread that sleeps periodically. 
• A thread’s life cycle consists of ready, running, waiting, sleeping, and blocked states. Threads start in the ready state and are dispatched to the CPU by the scheduler, an operating system program. If a thread performs an I/O operation, it blocks until the I/O is completed. If it voluntarily sleeps, it gives up the CPU. 
• According to the producer/consumer model, two threads share a resource, one serving to produce the resource and the other to consume the resource. Their cooperation must be carefully synchronized. 
• An object that contains synchronized methods is known as a monitor. Such objects ensure that only one thread at a time can execute a synchronized method. The object is locked until the thread completes the method or voluntarily sleeps. This is one way to ensure mutually exclusive access to a resource by a collection of cooperating threads.
• The synchronized qualifier can also be used to designate a method as a critical section, whose execution should not be preempted by one of the other cooperating threads.
• In designing multithreaded programs, it is useful to assume that if a thread can be interrupted at a certain point, it will be interrupted there. Thread coordination should never be left to chance.
• One way of coordinating two or more cooperating threads is to use the wait/notify combination. One thread waits for a resource to be available, and the other thread notifies when a resource becomes available.
  

Solutions to Self-Study Exercises