What Is a Thread?
All programmers are familiar with writing sequential programs. You've
probably written a program that displays "Hello World!" or
sorts a list of names or computes a list of prime numbers. These are
sequential programs. That is, each has a beginning, an execution
sequence, and an end. At any given time during the runtime of the
program, there is a single point of execution.
A thread is similar to the sequential programs described
previously. A single thread also has a beginning, a sequence, and an
end and at any given time during the runtime of the thread, there is a
single point of execution. However, a thread itself is not a program;
it cannot run on its own. Rather, it runs within a program. The
following figure shows this relationship.
Definition: A thread is a single sequential
flow of control within a program.
There is nothing new in the concept of a single thread. The real
hoopla surrounding threads is not about a single sequential thread.
Rather, it's about the use of multiple threads in a single program,
running at the same time and performing different tasks. This is
illustrated by the following figure:
The HotJava Web browser is an example of a multithreaded
application. Within the HotJava browser you can scroll a page while
it's downloading an applet or image, play animation and sound
concurrently, print a page in the background while you download a new
page, or watch three sorting algorithms race to the finish. You are
used to life operating in a concurrent fashion...so why not your
browser?
Some texts use the name lightweight process instead of
thread. A thread is similar to a real process in that a thread and a
running program are both a single sequential flow of control. However,
a thread is considered lightweight because it runs within the context
of a full-blown program and takes advantage of the resources allocated
for that program and the program's environment.
As a sequential flow of control, a thread must carve out some of
its own resources within a running program. (It must have its own
execution stack and program counter for example.) The code running
within the thread works only within that context. Thus, some other
texts use execution context as a synonym for thread.
Customizing a Thread's run Method
The run method gives a thread something to do. Its code
implements the thread's running behavior. It can do anything that can
be encoded in Java statements: compute a list of prime's, sort some
data, perform some animation.
The Thread class implements a generic thread that, by
default, does nothing. That is, the implementation of its run
method is empty. This is not particularly useful, so the Thread
class defines API that lets a Runnable object provide a
more interesting run method for a thread.
There are two techniques for providing a run method for a thread:
Subclassing Thread and Overriding
run
The first way to customize what a thread does when it is running is to
subclass Thread (itself a Runnable object)
and override its empty run method so that it does
something. Let's look at the SimpleThread class, the
first of two classes in this example, which does just that:
public class SimpleThread extends Thread {
public SimpleThread(String str) {
super(str);
}
public void run() {
for (int i = 0; i < 10; i++) {
System.out.println(i + " " + getName());
try {
sleep((long)(Math.random() * 1000));
} catch (InterruptedException e) {}
}
System.out.println("DONE! " + getName());
}
}
The first method in the SimpleThread class is a
constructor that takes a String as its only argument.
This constructor is implemented by calling a superclass constructor
and is interesting to us only because it sets the Thread's
name, which is used later in the program.
The next method in the SimpleThread class is the run
method. The run method is the heart of any Thread
and where the action of the Thread takes place. The run
method of the SimpleThread class contains a for
loop that iterates ten times. In each iteration the method displays
the iteration number and the name of the Thread, then
sleeps for a random interval of up to 1 second. After the loop has
finished, the run method prints DONE! along
with the name of the thread. That's it for the SimpleThread
class.
The TwoThreadsDemo class provides a main
method that creates two SimpleThread threads: one is
named "Jamaica" and the other is named "Fiji". (If
you can't decide on where to go for vacation you can use this program
to help you decide--go to the island whose thread prints
"DONE!" first.)
public class TwoThreadsDemo {
public static void main (String[] args) {
new SimpleThread("Jamaica").start();
new SimpleThread("Fiji").start();
}
}
The main method also starts each thread immediately
following its construction by calling the start
method. You should see output similar to the following:
0 Jamaica
0 Fiji
1 Fiji
1 Jamaica
2 Jamaica
2 Fiji
3 Fiji
3 Jamaica
4 Jamaica
4 Fiji
5 Jamaica
5 Fiji
6 Fiji
6 Jamaica
7 Jamaica
7 Fiji
8 Fiji
9 Fiji
8 Jamaica
DONE! Fiji
9 Jamaica
DONE! Jamaica
(Looks like I'm going to Fiji!!) Notice how the output from each
thread is intermingled with the output from the other. This is because
both SimpleThread threads are running concurrently. Thus,
both run methods are running at the same time and each
thread is displaying its output at the same time as the other.
Implementing the Runnable Interface
The Clock applet uses a different technique than SimpleThread
for providing the run method for its thread. Instead of
subclassing Thread, Clock implements the Runnable
interface (and therefore implements the run method defined in it). Clock
then creates a thread and provides itself as an argument to the Thread's
constructor. When created in this way, the Thread gets its run
method from the object passed into the constructor. The code that
accomplishes this is shown in bold here:
import java.awt.Graphics;
import java.util.*;
import java.text.DateFormat;
import java.applet.Applet;
public class Clock extends Applet implements Runnable {
private Thread clockThread = null;
public void start() {
if (clockThread == null) {
clockThread = new Thread(this, "Clock");
clockThread.start();
}
}
public void run() {
Thread myThread = Thread.currentThread();
while (clockThread == myThread) {
repaint();
try {
Thread.sleep(1000);
} catch (InterruptedException e){
// the VM doesn't want us to sleep anymore,
// so get back to work
}
}
}
public void paint(Graphics g) {
// get the time and convert it to a date
Calendar cal = Calendar.getInstance();
Date date = cal.getTime();
// format it and display it
DateFormat dateFormatter = DateFormat.getTimeInstance();
g.drawString(dateFormatter.format(date), 5, 10);
}
// overrides Applet's stop method, not Thread's
public void stop() {
clockThread = null;
}
}
The Clock applet's run method loops until the
browser asks it to stop. During each iteration of the loop, the clock
repaints its display. The paint method figures out what
time it is, formats it in a localized way, and displays it. You'll see
more of the Clock applet in The Life Cycle of a Thread
which uses it to teach you about the life of a thread.
Deciding to Use the Runnable Interface
You have now seen two ways to provide the run method for a Java
thread:
- Subclass the
Thread class defined in the java.lang
package and override the run method.
Example: See the SimpleThread
class described in Subclassing Thread and
Overriding run.
- Provide a class that implements the
Runnable
interface (also defined in the java.lang package) and
therefore implements the run method. In this case, a Runnable
object provides the run method to the thread.
Example: See the Clock
applet just shown.
There are good reasons for choosing either of these options over the
other. However, for most cases, including that of the Clock
applet, the following rule of thumb will guide you to the best option.
Rule of Thumb: If your class must subclass
some other class (the most common example being Applet),
you should use Runnable as described in option #2.
To run in a Java-enabled browser, the Clock class has
to be a subclass of the Applet class. Also, the Clock
applet needs a thread so that it can continuously update its display
without taking over the process in which it is running. (Some browsers
might create a new thread for each applet so as to prevent a
misbehaved applet from taking over the main browser thread. However,
you should not count on this when writing your applets; your applets
should create their own threads when doing computer-intensive work.)
But since the Java language does not support multiple class
inheritance, the Clock class cannot be a subclass of both
Thread and Applet. Thus the Clock
class must use the Runnable interface to provide its
threaded behavior.
The Life Cycle of a Thread
The following diagram shows the states that a Java thread can be in
during its life. It also illustrates which method calls cause a
transition to another state. This figure is not a complete finite state
diagram, but rather an overview of the more interesting and common
facets of a thread's life. The remainder of this section uses the Clock
applet previously introduced to discuss a thread's life cycle in terms
of its state.
Creating a Thread
The application in which an applet is running calls the applet's start
method when the user visits the applet's page. The Clock
applet creates a Thread, clockThread, in its
start with the bold code shown here:
public void start() {
if (clockThread == null) {
clockThread = new Thread(this, "Clock");
clockThread.start();
}
}
After the bold statement has been executed, clockThread
is in the New Thread state. When a thread is a New Thread, it is
merely an empty Thread object; no system resources have
been allocated for it yet. When a thread is in this state, you can
only start the thread. Calling any method besides start when a thread
is in this state makes no sense and causes an IllegalThreadStateException.
(In fact, the runtime system throws an IllegalThreadStateException
any time a method is called on a thread and that thread's state does
not allow for that method call.)
Notice that this--the Clock instance-- is the first
argument to the thread constructor. The first argument to this thread
constructor must implement the Runnable interface and
provides the thread with its run method. The second
argument is just a name for the thread.
Starting a Thread
Now consider the next line of code in Clock's start
method shown here in bold:
public void start() {
if (clockThread == null) {
clockThread = new Thread(this, "Clock");
clockThread.start();
}
}
The start method creates the system resources necessary
to run the thread, schedules the thread to run, and calls the thread's
run method. clockThread's run
method is the one defined in the Clock class.
After the start method has returned, the thread is
"running". Yet, it's somewhat more complex than that. As the
previous figure shows, a thread that has been started is actually in
the Runnable state. Many computers have a single processor, thus
making it impossible to run all "running" threads at the
same time. The Java runtime system must implement a scheduling scheme
that shares the processor between all "running" threads.
(See Understanding Thread Priority for more information about
scheduling.) So at any given time, a "running" thread
actually may be waiting for its turn in the CPU.
Here's another look at Clock's run
method:
public void run() {
Thread myThread = Thread.currentThread();
while (clockThread == myThread) {
repaint();
try {
Thread.sleep(1000);
} catch (InterruptedException e){
// the VM doesn't want us to sleep anymore,
// so get back to work
}
}
}
Clock's run method loops while the condition
clockThread == myThread is true. This exit
condition is explained in more detail in Stopping a Thread. However,
for now, know that it allows the thread, and thus the applet, to exit
gracefully.
Within the loop, the applet repaints itself and then tells the
thread to sleep for one second (1000 milliseconds). An applet's repaint
method ultimately calls the applet's paint method, which
does the actual update of the applet's display area. The Clock
paint method gets the current time, formats, and displays
it:
public void paint(Graphics g) {
// get the time and convert it to a date
Calendar cal = Calendar.getInstance();
Date date = cal.getTime();
// format it and display it
DateFormat dateFormatter = DateFormat.getTimeInstance();
g.drawString(dateFormatter.format(date), 5, 10);
}
Making a Thread Not Runnable
A thread becomes Not Runnable when one of these events occurs:
- Its
sleep method is invoked.
- The thread calls the
wait method to wait for a
specific condition to be satisifed.
- The thread is blocking on I/O.
The clockThread in the Clock applet becomes
Not Runnable when the run method calls sleep on the
current thread:
public void run() {
Thread myThread = Thread.currentThread();
while (clockThread == myThread) {
repaint();
try {
Thread.sleep(1000);
} catch (InterruptedException e){
// the VM doesn't want us to sleep anymore,
// so get back to work
}
}
}
During the second that the clockThread is asleep, the
thread does not run, even if the processor becomes available. After
the second has elapsed, the thread becomes Runnable again and, if the
processor becomes available, the thread begins running again.
For each entrance into the Not Runnable state, there is a specific
and distinct escape route that returns the thread to the Runnable
state. An escape route works only for its corresponding entrance. For
example, if a thread has been put to sleep, then the specified number
of milliseconds must elapse before the thread becomes Runnable again.
The following list describes the escape route for every entrance into
the Not Runnable state:
- If a thread has been put to sleep, then the specified number of
milliseconds must elapse.
- If a thread is waiting for a condition, then another object must
notify the waiting thread of a change in condition by calling
notify
or notifyAll. More information is available in
Synchronizing Threads.
- If a thread is blocked on I/O, then the I/O must complete.
Stopping a Thread
A program doesn't stop a thread like it stops an applet (by calling a
method). Rather, a thread arranges for its own death by having a run
method that terminates naturally. For example, the while
loop in this run method is a finite loop-- it will
iterate 100 times and then exit:
public void run() {
int i = 0;
while (i < 100) {
i++;
System.out.println("i = " + i);
}
}
A thread with this run method dies naturally when the
loop completes and the run method exits.
Let's look at how the Clock applet thread arranges for
its own death. You might want to use this technique with your applets.
Recall Clock's run method:
public void run() {
Thread myThread = Thread.currentThread();
while (clockThread == myThread) {
repaint();
try {
Thread.sleep(1000);
} catch (InterruptedException e){
// the VM doesn't want us to sleep anymore,
// so get back to work
}
}
}
The exit condition for this run method is the exit
condition for the while loop because there is no code
after the while loop:
while (clockThread == myThread) {
This condition indicates that the loop will exit when the currently
executing thread is not equal to clockThread. When would
this ever be the case?
When you leave the page, the application in which the applet is
running calls the applet's stop method. This method then
sets the clockThread to null, thereby
telling the main loop in the run method to terminate:
public void stop() { // applets' stop method
clockThread = null;
}
If you revisit the page, the start method is called again
and the clock starts up again with a new thread. Even if you stop and
start the applet faster than one iteration of the loop, clockThread
will be a different thread than myThread and the loop
will still terminate.
The isAlive Method
A final word about thread state: The API for the Thread
class includes a method called isAlive. The isAlive
method returns true if the thread has been started and not stopped. If
the isAlive method returns false, you know that the
thread either is a New Thread or is Dead. If the isAlive
method returns true, you know that the thread is either Runnable or
Not Runnable. You cannot differentiate between a New Thread or a Dead
thread. Nor can you differentiate between a Runnable thread and a Not
Runnable thread.
Understanding Thread Priority
Previously, this lesson claimed that threads run concurrently. While
conceptually this is true, in practice it usually isn't. Most computer
configurations have a single CPU, so threads actually run one at a
time in such a way as to provide an illusion of concurrency. Execution
of multiple threads on a single CPU, in some order, is called scheduling.
The Java runtime supports a very simple, deterministic scheduling
algorithm known as fixed priority scheduling. This algorithm
schedules threads based on their priority relative to other
runnable threads.
When a Java thread is created, it inherits its priority from the
thread that created it. You can also modify a thread's priority at any
time after its creation using the setPriority method.
Thread priorities are integers ranging between MIN_PRIORITY
and MAX_PRIORITY (constants defined in the Thread
class). The higher the integer, the higher the priority. At any given
time, when multiple threads are ready to be executed, the runtime
system chooses the runnable thread with the highest priority for
execution. Only when that thread stops, yields, or becomes not
runnable for some reason will a lower priority thread start executing.
If two threads of the same priority are waiting for the CPU, the
scheduler chooses one of them to run in a round-robin fashion. The
chosen thread will run until one of the following conditions is true:
- A higher priority thread becomes runnable.
- It yields, or its
run method exits.
- On systems that support time-slicing, its time allotment has
expired.
Then the second thread is given a chance to run, and so on, until the
interpreter exits.
The Java runtime system's thread scheduling algorithm is also preemptive.
If at any time a thread with a higher priority than all other runnable
threads becomes runnable, the runtime system chooses the new higher
priority thread for execution. The new higher priority thread is said
to preempt the other threads.
Rule of thumb: At any given time, the highest
priority thread is running. However, this is not guaranteed. The
thread scheduler may choose to run a lower priority thread to avoid
starvation. For this reason, use priority only to affect scheduling
policy for efficiency purposes. Do not rely on thread priority for
algorithm correctness.
A Thread Race
RaceApplet is an applet
that animates a race between two "runner" threads with
different priorities. The top runner, labelled "2", has
a priority of 2. The second runner, labelled "3", has a
priority of 3.
This is the run method for both runners
public int tick = 1;
public void run() {
while (tick < 10000000)
tick++;
}
This run method simply counts from 1 to 10,000,000.
The instance variable tick is public because the
applet uses this value to determine how far the runner has
progressed (how long its line is).
In addition to the two runner threads, this applet also has a
third thread that handles the drawing. The drawing thread's run
method contains an infinite loop; during each iteration of the
loop it draws a line for each runner (whose length is computed
from the runner's tick variable), and then sleeps for
3 milliseconds. The drawing thread has a thread priority of
4--higher than either runner. So, whenever the drawing thread
wakes up after 3 milliseconds, it becomes the highest priority
thread, preempting whichever runner is currently running, and
draws the lines. You can see the lines inch their way across the
page
This is not a fair race because one runner has a higher
priority than the other. Each time the drawing thread yields the
CPU by going to sleep for 3 milliseconds, the scheduler chooses
the highest priority runnable thread to run; in this case, it's
always the runner with a priority of 3. Here is another version of
the applet that implements a fair race, that is, both of the
runners have the same priority and they have an equal chance of
being chosen to run.
In this race, each time the drawing thread yields the CPU by
going to sleep, there are two runnable threads of equal
priority--the runners--waiting for the CPU; the scheduler must
choose one of the threads to run. In this situation, the scheduler
chooses the next thread to run in a round-robin fashion.
Selfish Threads
The Runner class used in the races above actually
implements "socially-impaired" thread behavior. Recall
the run method from the Runner class used in the
races above:
public int tick = 1;
public void run() {
while (tick < 10000000)
tick++;
}
The while loop in the run method is in a
tight loop. Once the scheduler chooses a thread with this thread
body for execution, the thread never voluntarily relinquishes
control of the CPU--the thread continues to run until the while
loop terminates naturally or until the thread is preempted by a
higher priority thread. This thread is called a selfish thread.
In some situations, having selfish threads doesn't cause any
problems because a higher priority thread preempts the selfish one
(just as the drawing thread in the RaceApplet preempts the selfish
runners). However, in other situations, threads with CPU-greedy run
methods, such as the Runner class, can take over the
CPU and cause other threads to wait for a long time before getting
a chance to run.
Time-Slicing
Some systems, such as Windows 95/NT, fight selfish thread behavior
with a strategy known as time-slicing. Time-slicing comes
into play when there are multiple "Runnable" threads of
equal priority and those threads are the highest priority threads
competing for the CPU. For example, this creates two equal
priority selfish threads that have the following run
method.
public void run() {
while (tick < 400000) {
tick++;
if ((tick % 50000) == 0)
System.out.println("Thread #" + num
+ ", tick = " + tick);
}
}
This run contains a tight loop that increments the
integer tick and every 50,000 ticks prints out the
thread's identifier and its tick count.
When running this program on a time-sliced system, you will see
messages from both threads intermingled with one another. Like
this:
Thread #1, tick = 50000
Thread #0, tick = 50000
Thread #0, tick = 100000
Thread #1, tick = 100000
Thread #1, tick = 150000
Thread #1, tick = 200000
Thread #0, tick = 150000
Thread #0, tick = 200000
Thread #1, tick = 250000
Thread #0, tick = 250000
Thread #0, tick = 300000
Thread #1, tick = 300000
Thread #1, tick = 350000
Thread #0, tick = 350000
Thread #0, tick = 400000
Thread #1, tick = 400000
This output is produced because a time-sliced system divides the
CPU into time slots and iteratively gives each of the
equal-and-highest priority threads a time slot in which to run.
The time-sliced system iterates through the equal-and-highest
priority threads, allowing each one a bit of time to run, until
one or more of them finishes or until a higher priority thread
preempts them. Notice that time-slicing makes no guarantees as to
how often or in what order threads are scheduled to run.
When running this program on a non-time-sliced system, however,
you will see messages from one thread finish printing before the
other thread ever gets a chance to print one message. Like this:
Thread #0, tick = 50000
Thread #0, tick = 100000
Thread #0, tick = 150000
Thread #0, tick = 200000
Thread #0, tick = 250000
Thread #0, tick = 300000
Thread #0, tick = 350000
Thread #0, tick = 400000
Thread #1, tick = 50000
Thread #1, tick = 100000
Thread #1, tick = 150000
Thread #1, tick = 200000
Thread #1, tick = 250000
Thread #1, tick = 300000
Thread #1, tick = 350000
Thread #1, tick = 400000
This is because a non-time-sliced system chooses one of the
equal-and-highest priority threads to run and allows that thread
to run until it relinquishes the CPU (by sleeping, yielding,
finishing its job) or until a higher priority preempts it.
Note: The Java runtime does not implement
(and therefore does not guarantee) time-slicing. However, some
systems on which you can run Java do support time-slicing. Your
Java programs should not rely on time-slicing as it may produce
different results on different systems.
As you can imagine, writing CPU-intensive code can have
negative repercussions on other threads running in the same
process. In general, you should try to write
"well-behaved" threads that voluntarily relinquish the
CPU periodically and give other threads an opportunity to run. In
particular, you should never write Java code that relies on
time-sharing--this will practically guarantee that your program
will give different results on different computer systems.
A thread can voluntarily yield the CPU without going to sleep
or some other drastic means by calling the yield
method. The yield method gives other threads of the
same priority a chance to run. If there are no equal priority
threads that are runnable, then the yield is ignored.
Summary
- Most computers have only one CPU, so threads must share the
CPU with other threads. The execution of multiple threads on a
single CPU, in some order, is called scheduling. The Java
runtime supports a very simple, deterministic scheduling
algorithm known as fixed priority scheduling.
- Each Java thread is given a numeric priority between
MIN_PRIORITY
and MAX_PRIORITY (constants defined in the Thread
class). At any given time, when multiple threads are ready to be
executed, the thread with the highest priority is chosen for
execution. Only when that thread stops, or is suspended for some
reason, will a lower priority thread start executing.
- Scheduling of the CPU is fully preemptive. If a thread with a
higher priority than the currently executing thread needs to
execute, the higher priority thread is immediately scheduled.
- The Java runtime will not preempt the currently running thread
for another thread of the same priority. In other words, the
Java runtime does not time-slice. However, the system
implementation of threads underlying the Java Thread class may
support time-slicing. Do not write code that relies on
time-slicing.
- In addition, a given thread may, at any time, give up its
right to execute by calling the
yield method.
Threads can only yield the CPU to other threads of the same
priority--attempts to yield to a lower priority thread are
ignored.
- When all the runnable threads in the system have the same
priority, the scheduler chooses the next thread to run in a
simple, non-preemptive, round-robin scheduling order.
Synchronizing Threads
So far, this lesson has contained examples with independent,
asynchronous threads. That is, each thread contained all of the
data and methods required for its execution and didn't require any
outside resources or methods. In addition, the threads in those
examples ran at their own pace without concern over the state or
activities of any other concurrently running threads.
However, there are many interesting situations where separate,
concurrently running threads do share data and must consider the
state and activities of other threads. One such set of programming
situations are known as producer/consumer scenarios where the
producer generates a stream of data which then is consumed by a
consumer.
For example, imagine a Java application where one thread (the
producer) writes data to a file while a second thread (the
consumer) reads data from the same file. Or, as you type
characters on the keyboard, the producer thread places key events
in an event queue and the consumer thread reads the events from
the same queue. Both of these examples use concurrent threads that
share a common resource: the first shares a file, the second
shares an event queue. Because the threads share a common
resource, they must be synchronized in some way.
The Producer generates an
integer between 0 and 9 (inclusive), stores it in a CubbyHole
object, and prints the generated number. To make the
synchronization problem more interesting, the Producer
sleeps for a random amount of time between 0 and 100 milliseconds
before repeating the number generating cycle:
public class Producer extends Thread {
private CubbyHole cubbyhole;
private int number;
public Producer(CubbyHole c, int number) {
cubbyhole = c;
this.number = number;
}
public void run() {
for (int i = 0; i < 10; i++) {
cubbyhole.put(i);
System.out.println("Producer #" + this.number
+ " put: " + i);
try {
sleep((int)(Math.random() * 100));
} catch (InterruptedException e) { }
}
}
}
The Consumer, being
ravenous, consumes all integers from the CubbyHole
(the exact same object into which the Producer put
the integers in the first place) as quickly as they become
available.
public class Consumer extends Thread {
private CubbyHole cubbyhole;
private int number;
public Consumer(CubbyHole c, int number) {
cubbyhole = c;
this.number = number;
}
public void run() {
int value = 0;
for (int i = 0; i < 10; i++) {
value = cubbyhole.get();
System.out.println("Consumer #" + this.number
+ " got: " + value);
}
}
}
The Producer and Consumer in this
example share data through a common CubbyHole object.
And you will note that neither the Producer nor the Consumer
makes any effort whatsoever to ensure that the Consumer
is getting each value produced once and only once. The
synchronization between these two threads actually occurs at a
lower level, within the get and put
methods of the CubbyHole object. However, let's
assume for a moment that these two threads make no arrangements
for synchronization and talk about the potential problems that
might arise in that situation.
One problem arises when the Producer is quicker
than the Consumer and generates two numbers before
the Consumer has a chance to consume the first one.
Thus the Consumer would skip a number. Part of the
output might look like this:
. . .
Consumer #1 got: 3
Producer #1 put: 4
Producer #1 put: 5
Consumer #1 got: 5
. . .
Another problem that might arise is when the Consumer
is quicker than the Producer and consumes the same
value twice. In this situation, the Consumer would
print the same value twice and might produce output that looked
like this:
. . .
Producer #1 put: 4
Consumer #1 got: 4
Consumer #1 got: 4
Producer #1 put: 5
. . .
Either way, the result is wrong. You want the Consumer
to get each integer produced by the Producer exactly
once. Problems such as those just described are called race
conditions. They arise from multiple, asynchronously
executing threads trying to access a single object at the same
time and getting the wrong result.
Race conditions in the producer/consumer example are prevented
by having the storage of a new integer into the CubbyHole
by the Producer be synchronized with the retrieval of
an integer from the CubbyHole by the Consumer.
The Consumer must consume each integer exactly once.
The activities of the Producer and Consumer
must be synchronized in two ways. First, the two threads must not
simultaneously access the CubbyHole. A Java thread can
prevent this from happening by locking an object. When an object is
locked by one thread and another thread tries to call a synchronized
method on the same object, the second thread will block until the
object is unlocked. Locking an Object discusses this.
And second, the two threads must do some simple
coordination. That is, the Producer must have some way
to indicate to the Consumer that the value is ready and
the Consumer must have some way to indicate that the
value has been retrieved. The Thread class provides a
collection of methods--wait, notify, and notifyAll--to
help threads wait for a condition and notify other threads of when
that condition changes. Using the notifyAll and wait
Methods has more information.
The Main Program
Here's a small stand-alone Java
application that creates a CubbyHole
object, a Producer, a Consumer, and then
starts both the Producer and the Consumer.
public class ProducerConsumerTest {
public static void main(String[] args) {
CubbyHole c = new CubbyHole();
Producer p1 = new Producer(c, 1);
Consumer c1 = new Consumer(c, 1);
p1.start();
c1.start();
}
}
The Output
Here's the output of ProducerConsumerTest.
Producer #1 put: 0
Consumer #1 got: 0
Producer #1 put: 1
Consumer #1 got: 1
Producer #1 put: 2
Consumer #1 got: 2
Producer #1 put: 3
Consumer #1 got: 3
Producer #1 put: 4
Consumer #1 got: 4
Producer #1 put: 5
Consumer #1 got: 5
Producer #1 put: 6
Consumer #1 got: 6
Producer #1 put: 7
Consumer #1 got: 7
Producer #1 put: 8
Consumer #1 got: 8
Producer #1 put: 9
Consumer #1 got: 9
Locking an Object
The code segments within a program that access the
same object from separate, concurrent threads are called critical
sections. In the Java language, a critical section can be a
block or a method and are identified with the synchronized
keyword. The Java platform then associates a lock with every object
that has synchronized code.
In the producer/consumer example, the put
and get methods of the CubbyHole are the
critical sections. The Consumer should not access the CubbyHole
when the Producer is changing it, and the Producer
should not modify it when the Consumer is getting the
value. So put and get in the CubbyHole
class should be marked with the synchronized keyword.
Here's a code skeleton for the CubbyHole
class:
public class CubbyHole {
private int contents;
private boolean available = false;
public synchronized int get() {
...
}
public synchronized void put(int value) {
...
}
}
Note that the method declarations for both put
and get contain the synchronized keyword.
Hence, the system associates a unique lock with every instance of CubbyHole
(including the one shared by the Producer and the Consumer).
Whenever control enters a synchronized method, the thread that
called the method locks the object whose method has been called.
Other threads cannot call a synchronized method on the same object
until the object is unlocked.
So, when the Producer calls CubbyHole's
put method, it locks the CubbyHole,
thereby preventing the Consumer from calling the CubbyHole's
get method:
public synchronized void put(int value) {
// CubbyHole locked by the Producer
..
// CubbyHole unlocked by the Producer
}
When the put method returns, the Producer
unlocks the CubbyHole.
Similarly, when the Consumer calls CubbyHole's
get method, it locks the CubbyHole,
thereby preventing the Producer from calling put:
public synchronized int get() {
// CubbyHole locked by the Consumer
...
// CubbyHole unlocked by the Consumer
}
The acquisition and release of a lock is done
automatically and atomically by the Java runtime system. This
ensures that race conditions cannot occur in the underlying
implementation of the threads, thus ensuring data integrity.
Synchronization isn't the whole story. The two threads must also be
able to notify one another when they've done their job. Learn more
about that after a brief foray into reentrant locks.
Using the notifyAll and wait Methods
You really want the Consumer to wait until the Producer
puts something in the CubbyHole and the Producer
must notify the Consumer when it's done so. Similarly,
the Producer must wait until the Consumer
takes a value (and notifies the Producer of its
activities) before replacing it with a new value. The two threads must
coordinate more fully and can use Object's wait
and notifyAll methods to do so.
Here are the new implementations of get and put
that wait on and notify each other of their activities:
public synchronized int get() {
while (available == false) {
try {
// wait for Producer to put value
wait();
} catch (InterruptedException e) {
}
}
available = false;
// notify Producer that value has been retrieved
notifyAll();
return contents;
}
public synchronized void put(int value) {
while (available == true) {
try {
// wait for Consumer to get value
wait();
} catch (InterruptedException e) {
}
}
contents = value;
available = true;
// notify Consumer that value has been set
notifyAll();
}
The code in the get method loops until the Producer
has produced a new value. Each time through the loop, get
calls the wait method. The wait method
relinquishes the lock held by the Consumer on the CubbyHole
(thereby allowing the Producer to get the lock and update
the CubbyHole) and then waits for notification from the Producer.
When the Producer puts something in the CubbyHole,
it notifies the Consumer by calling notifyAll.
The Consumer then comes out of the wait state, available
is now true, the loop exits, and the get
method returns the value in the CubbyHole.
The put method works in a similar fashion, waiting for
the Consumer thread to consume the current value before
allowing the Producer to produce a new one.
The notifyAll method wakes up all threads waiting on
the object in question (in this case, the CubbyHole). The
awakened threads compete for the lock. One thread gets it, and the
others go back to waiting. The Object class also defines
the notify method, which arbitrarily wakes up one of the threads
waiting on this object.
The Object class contains not only the version of wait
that is used in the producer/consumer example and which waits
indefinitely for notification, but also two other versions of the wait
method:
- wait(long timeout)
- Waits for notification or until the
timeout period
has elapsed. timeout is measured in milliseconds.
- wait(long timeout, int nanos)
- Waits for notification or until
timeout
milliseconds plus nanos nanoseconds have elapsed.
Note: Besides using these timed wait
methods to synchronize threads, you also can use them in place of sleep.
Both wait and sleep delay for the
requested amount of time, but you can easily wake up wait
with a notify but a sleeping thread cannot be awakened prematurely.
This doesn't matter too much for threads that don't sleep for long,
but it could be important for threads that sleep for minutes at a
time.
Avoiding Starvation and Deadlock
The dining philosophers are often used to illustrate various
problems that can occur when many synchronized threads are competing
for limited resources.
The story goes like this: Five philosophers are sitting at a
round table. In front of each philosopher is a bowl of rice. Between
each pair of philosophers is one chopstick. Before an individual
philosopher can take a bite of rice he must have two chopsticks--one
taken from the left, and one taken from the right. The philosophers
must find some way to share chopsticks such that they all get to
eat.
The following applet does a rough animation using an image of
Duke for the dining philosophers. This particular algorithm works as
follows: Duke always reaches for the chopstick on his right first.
If the chopstick is there, Duke takes it and raises his right hand.
Next, Duke tries for the left chopstick. If the chopstick is
available, Duke picks it up and raises his other hand. Now that Duke
has both chopsticks, he takes a bite of rice and says "Mmm!"
He then puts both chopsticks down, allowing either of his two
neighbors to get the chopsticks. Duke then starts all over again by
trying for the right chopstick. Between each attempt to grab a
chopstick, each Duke pauses for a random period of time.
This is a picture of the applet's GUI. To run the applet, click
the picture. The applet will appear in a new browser window.
The slider controls the amount of time that each philosopher will
wait before attempting to pick up a chopstick. When the slider is
set to 0, the philosophers don't wait--they just grab--and most
often, the applet ends up in deadlock: all the philosophers are
frozen with their right hand in the air. Why? Because each
philosopher immediately has one chopstick and is waiting on a
condition that cannot be satisfied--they are all waiting for the
left chopstick, which is held by the philosopher to their left.
When you move the slider so that the waiting period is longer,
the applet may proceed for a while without deadlocking. However,
deadlock is always possible with this particular implementation of
the dining philosophers problem because it is possible for all five
philosophers to be holding their right chopsticks. Rather than rely
on luck to prevent deadlock, you must either prevent it or detect
it.
For most Java programmers, the best choice is to prevent deadlock
rather than to try and detect it. Deadlock detection is complicated
and beyond the scope of this tutorial. The simplest approach to
preventing deadlock is to impose ordering on the condition
variables. In the dining philosopher applet, there is no ordering
imposed on the condition variables because the philosophers and the
chopsticks are arranged in a circle. All chopsticks are equal.
However, we can change the rules in the applet by numbering the
chopsticks 1 through 5 and insisting that the philosophers pick up
the chopstick with the lower number first. The philosopher who is
sitting between chopsticks 1 and 2 and the philosopher who is
sitting between chopsticks 1 and 5 must now reach for the same
chopstick first (chopstick 1) rather than picking up the one on the
right. Whoever gets chopstick 1 first is now free to take another
one. Whoever doesn't get chopstick 1 must now wait for the first
philosopher to release it. Deadlock is not possible.
|
