Java, Java, Java

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 cen- tral 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 indepen- dent 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 at time, it can run multiple threads concurrently by rapidly alternating among them. The main ad- vantage of concurrency is that it allows the computer to do more than one task at a time. For example, the CPU could alternate between down- loading an image from the Internet and running a spreadsheet calcula- tion. 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 an effectively scheduling threads.

 

 

Concurrent Execution of Threads

The technique of concurrently executing several tasks within a program is Multitasking

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 dis- playing 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 in- struction 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 instruc- tion 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 sched- ules threads for execution on the CPU. The choice of a scheduling algo- rithm 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 CPUs are sequential

 

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

 

Thread 1

 

Thread 2

 

 

 

CPU time

Quantum

 

 

 

 

 

 

 

 

Time slicing

 

 

 

Priority scheduling

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Figure 14.2: The NumberThread class overrides the inherited run() method.

each thread alternatively gets a slice of the CPU’s time. For example, sup- pose we have a program that consists of two threads. Using this tech- nique, the system would give each thread a small quantum of CPU time— say, one thousandth of a second (one millisecond)—to execute its instruc- tions. 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 mil- lion 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.

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 key- board 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, higher- priority threads are those that can complete their task within a few mil- liseconds, 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

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 used

 

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

 

 

 

 

 

 

 

 

to set the thread’s ID number. In the run() method, the thread simply executes a loop that prints its own number ten times:

,,

 

 

 

 

 

 

 

 

 

 

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:

J

Thread subclass

 

,,

 

 

 

 

 

 

 

 

 

J

When a thread is started by calling its start() method, it automati-

cally calls its run() method. The output generated by this version ofStarting a thread

 

the Numbers application is as follows:

,,

 

J

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 per- forms? Will each thread still run to completion? The following output was generated for 200 iterations per thread:

,,

 

 

 

 

 

 

 

 

 

 

 

 

Figure14.4:

 

 

 

 

 

The

J

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.

 

java.lang.Threadclass. NOTE: NEEDS REVISION TO

ADD PRIORITY, YIELD() and SLEEP().

Create several instances of the subclass and start each thread by invok- ing the start() method on each instance.

 

 

 

From the Java Library: java.lang.Thread

The java.lang.Thread class contains the public methods shown in Fig- ure 14.4 (the figure contains only a partial list). Note that Thread im- plements the Runnable interface, which consists simply of the run() method. As we will now see, another way to create a thread is to instan- tiate 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 imple- ment the NumberThread program:

,,

 

 

 

 

 

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

Figure 14.5: Any object that im- plements the Runnable interface Jcan be run as a separate thread.

 

,,

 

 

 

 

 

 

 

 

J

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 individ- ual 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 implement- ing the void run() method, which contains the statements to be exe- cuted 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:

,,

 

 

 

 

 

 

 

 

J

 

Thread Control

 

 

Controlling threads

The various methods in the Thread class (Fig. 14.4) can be used to ex- ert 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 appletviewer, which is responsible for starting and stopping it.

As we saw in the NumberThread example, the run() method encap- sulates the thread’s basic algorithm. It is usually not called directly. In- stead, 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 in- teger value between Thread.MIN PRIORITY and Thread.MAX PRIOR- ITY, the bounds defined as constants in the Thread class. Using set- Priority() gives you some control over a thread’s execution. In gen-

 

eral, 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. Sup- pose 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:

,

J

 

Thread priority

 

 

 

,

 

 

 

J

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

Numbers:

,,

 

J

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.

 

 

 

 

 

 

 

Sleep versus yield

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 mil- liseconds, 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.

,,

 

 

 

J

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

,,

 

 

 

 

 

 

 

J

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:

,,

 

J

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 itera- tions.

EXERCISE 14.4 The purpose of the Java garbage collector is to recap- ture 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 pro- grammer’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 im- possible for the programmer to predict when and for how long an indi-

vidual thread will run. In some systems, under some circumstances, a Thread preemptions are unpredictable

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 com- plete a simple Java arithmetic operation once it has started it. For example, suppose a thread had to execute the following operation:

,,

 

J

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, itAn arithmetic operation can be

 

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 ma- chine language, this operation would break down into something like the following three steps:

interrupted

 

,,

 

 

J

 

 

 

 

 

Threads are asynchronous

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Ready, running, and sleeping Controlling a thread

 

 

 

 

 

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

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 of multithreaded programs:

 

 

 

 

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