Chapter 16 -- Multithreading with Java
Chapter 16
Multithreading with Java
CONTENTS
A thread executes a series of instructions. Every line of code
that is executed is done so by a thread. Some threads can run
for the entire life of the applet, while others are alive for
only a few milliseconds. A thread also creates a new thread or
kills an existing one. Threads run in methods or constructors.
The methods and constructors themselves are lifeless. The threads
go into the methods and follow their instructions. Methods and
constructors reside in the computer's memory. Figure 16.1 shows
threads, constructors, and methods in a typical applet.
Figure 16.1 : Two threads running through three classes.
The applet methods start(),
paint(), and so on are all
called by underlying threads. These threads are created by the
Web browser. When there is a mouse click or a repaint()
has been called, the underlying thread calls the appropriate thread
in the applet. While the threads are running in the applet methods,
they cannot do anything else. If the applet holds these threads
too long, it locks up the browser. If an applet needs to do something
that will take some time in one of its methods, it should start
a new thread. Some specific uses for threads are listed below:
- Long initiations. Threads are used in applets that
may take a while to initialize. The applet may need to do something
like wait for an image to be loaded. A thread is used so that
the system thread can handle other events.
- Repetitive or timed tasks. Threads are used
to do tasks that happen repetitively. A common example of this
is found in animations. Every few milliseconds a new frame is
shown. A thread displays a frame, sleeps for a while, and then
repeats the process.
- Asynchronous events. Threads are used to handle
events. An example of this is a mouse click. If the user clicks
the mouse, a new thread is created to render a new frame in an
image.
- Multiple tasks. Threads are used to do more than
one thing at once. One thread controls an animation, while another
does a computation.
The class java.lang.Thread
is used to create and control threads. To create a thread, a new
instance of this class must be created. However, the thread does
not start running right away. Thread.start()
must be called to actually make the thread run. When Thread.start()
is called, the thread begins executing in the run()
method of the target class. A new Thread
class always starts running the public
void run() method of a class. There are two ways to
create a thread:
- Extend the Thread class. With
this technique the new class inherits from the class Thread.
The thread can start running in the class's run
method.
- Implement the Runnable
interface. This technique is probably more common than
extending the Thread class.
It is not necessary to define a new class to run the thread. If
a thread is to start running in the applet, it must use the Runnable
interface. The applet cannot inherit from both the Thread
and Applet classes. An applet
with the Runnable interface
must have a run() method
for the thread to start.
There isn't much difference between the two approaches. Both extending
the Thread class and implementing
the Runnable interface have
the same functionality. The interface approach must be used if
the thread is to actually start in the applet
class. But if the thread is going to be running in its own class,
it may be more convenient to extend the Thread
class. Examples of both approaches are in this chapter.
The Thread class has seven
constructors. All of them create a new thread. The thread does
not start running until Thread.start()
is called. When Thread.start()
is called, the new thread starts running in the run()
method of an object. The constructors are the following:
Thread()
Thread(Runnable)
Thread(ThreadGroup)
Thread(String)
Thread(ThreadGroup,String)
Thread(Runnable,String)
Thread(ThreadGroup,Runnable,String)
The constructors can use three possible parameters:
- String The
name of the new thread is the parameter String.
A thread can get its name by calling Thread.getName().
- ThreadGroup The
new thread will belong to the group specified by the parameter
ThreadGroup. A ThreadGroup
can be used to organize a thread.
- Runnable The
Runnable parameter is an
object that has implemented the Runnable
interface. The thread will start executing in the run()
method of the Runnable parameter
when Thread.start() has been
called.
There are many methods in the Thread
class. Some of them, such as destroy(),
don't seem to have been implemented yet, and may never be. Some
of the methods that control the thread execution are the following:
- start() This
method starts the thread. It starts executing in the run()
method of its Runnable target
that was set when the constructor was called. This method can
be called only once.
- suspend() This
method suspends the execution of the thread. It remains suspended
until resume() is called.
- resume() This
method resumes the execution of a suspended thread. It has no
effect on a thread that is not suspended.
- stop() This
method stops and kills a running thread. Currently, the thread
does not stop unless it is running. If it is suspended, it does
not die until it starts running again. However, this may be fixed
someday.
- sleep(int m)/sleep(int
m,int n) The thread sleeps for
m milliseconds, plus
n nanoseconds.
Listing 16.1 shows how to start, stop, suspend, and resume threads.
It uses the Runnable interface.
Threads like this are useful for things like controlling animation
sequences or repeatedly playing audio samples. This example uses
a thread that counts and prints a string every second. The thread
starts when the applet is initialized. It continues to run until
the user leaves the page. If the user returns to the page (and
all is well), the thread continues from where it left off. This
allows applets to retain their states while the user is away.
Listing 16.1. Thread examples.
import java.lang.Thread;
import java.applet.Applet;
public class InfiniteThreadExample extends Applet implements Runnable
{
Thread myThread;
public void init()
{
System.out.println("in
init() -- starting thread.");
myThread= new Thread(this);
myThread.start();
}
public void start()
{
System.out.println("in
start() -- resuming thread.");
myThread.resume();
}
public void stop()
{
System.out.println("in
stop() -- suspending thread.");
myThread.suspend();
}
public void destroy()
{
System.out.println("in
destroy() -- stoping thread.");
myThread.resume();
myThread.stop();
}
public void run()
{
int i=0;
for(;;)
{
i++;
System.out.println("At
" + i + " and counting!");
try
{myThread.sleep(1000);}
catch
(InterruptedException e ) {}
}
}
}
SimpleThreadExample
Output
The output of InfiniteThreadExample
is shown here. The applet ran for nine seconds until it was stopped.
in init() -- starting thread.
At 1 and counting!
in start() -- resuming thread.
At 2 and counting!
At 3 and counting!
At 4 and counting!
At 5 and counting!
At 6 and counting!
At 7 and counting!
At 8 and counting!
At 9 and counting!
in stop() -- suspending thread.
in destroy() -- stoping thread.
The applet has only five methods:
- public void init() The
thread is initialized and is started in this method. In this example,
the constructor Thread takes
the argument this. When the
Thread.start() method is
called, the thread looks for a public
void run() method in the this
object.
- public void start() When
this method is called by the system, the thread resumes execution.
If the thread is already running, this method has no effect.
- public void stop() This
method suspends the thread.
- public void destroy() This
method stops the thread. Thread.stop()
stops and kills the thread. However, it only kills a thread that
is running, so Thread.resume()
is called beforehand.
- public void run() This
is where the thread actually starts running. This example has
an infinite loop that prints a string and then sleeps for a second.
Long running threads should sleep every once in a while to give
other threads a chance to run. If not, the system may not even
get a chance to paint the applet.
When Are the Methods in InfiniteThreadExample
Called?
Unfortunately, its not always possible to know exactly when or
if the methods are called. It can vary from browser to browser,
or even by how the user has the browser configured. Netscape 3.0
calls init() and then calls
start() the first time the
applet is loaded. If the user leaves the page with the applet,
stop() is called. Returning
to the applet calls start(),
but it is possible that init()
may be the first called. It depends on whether or not the applet
is still residing in memory. If it is, then only start()
is called; otherwise, both init()
and start() are called again.
The method destroy() is called
before the applet is removed from memory. All threads should be
destroyed at this time so that its resources can be used by other
applets. The browsers can only handle so many threads. If the
user visits too many applets that don't clean up after themselves,
the browser may crash. Generally, threads should be suspended
when the user leaves the page and killed when the applet is destroyed.
It is possible to leave threads running while the user is visiting
other pages, but the user may not appreciate it.
Listing 16.2 shows how to use threads to handle events. When an
event that existing threads shouldn't take the time to handle
happens in the applet, a new thread is spawned to handle that
event. After the event is handled, the new thread quietly dies.
Listing 16.2 uses threads to handle mouse clicks. Each thread
draws a blue target, as you can see in Figure 16.2. Methods such
as mouseDown() or mouseUp()
are called by threads external to the applet. While the thread
is running in the applet, no other mouse movements are detected.
Keeping the external thread may not just affect the applet, but
possibly the whole browser. Generally, these methods should be
returned as soon as possible. If it is necessary to do a long
computation or wait for something else, a new thread should be
started. By starting a new thread, the external thread can return
almost immediately.
Figure 16.2 : The applet in Listing 16.2 draws targets.
Listing 16.2. Handling an event with threads.
import java.applet.Applet;
import java.awt.*;
public class FiniteThreadExample extends Applet
{
Image offImage; /*
off screen image */
Graphics offGraphics; /* Graphics for offImage
*/
public void init()
{
offImage=createImage(400,300);
offGraphics=offImage.getGraphics();
}
public void paint(Graphics g)
{
g.drawImage(offImage,0,0,null);
}
public void update(Graphics g)
{
paint(g);
}
public boolean mouseDown(Event e, int x, int y)
{
new DrawTarget(this,x,y,offGraphics);
return true;
}
}
class DrawTarget extends Thread
{
int xPos,yPos; /*
position of the target */
Applet myMaster; /*
who to repaint */
Graphics offGraphics; /* Graphics to draw on */
public DrawTarget(Applet a, int x, int y, Graphics
g)
{
xPos=x; yPos=y;
myMaster=a;
offGraphics=g;
start();
}
public void run()
{
int i; /* i is
direction the circles are moving */
int r; /* r is
the radius of the current circle */
offGraphics.setColor(Color.white);
offGraphics.setXORMode(Color.blue);
for(r=0,i=10;i>-20;i-=20) /*
i=(10,-10) */
for(r+=i;(r<90)&&(r>0);r+=i)
/* r=(10,20...80,80,70...10) */
{
offGraphics.fillOval(xPos-r,yPos-r,2*r,2*r);
myMaster.repaint();
try
{sleep(200);}
catch
(InterruptedException e) {}
}
}
}
The class FiniteThreadExample
is used to paint the applet, to catch the mouse clicks, but not
to start the threads. The applet uses a class that extends the
Thread class to start new
threads. The class FiniteThreadExample
has four methods shown below that sets up things, handles the
painting, and catches the mouse clicks:
- public void init() This
method creates an image and gets a Graphics
context for that image.
- public void paint(Graphics) This
method paints the Image offImage
on the screen.
- public void update(Graphics) This
method isn't really necessary. It overrides update(Graphics)
in java.awt.Component, and
is used to reduce flickering.
- public boolean mouseDown(Event, int,
int) This method is called when there is
a mouse click in the applet. It creates a new instance of the
class DrawTarget. DrawTarget
is defined in the next class.
DrawTarget is where the threads
are created to draw the targets. DrawTarget
inherits properties from java.lang.Thread
and has a single constructor and method, which are listed below:
- public DrawTarget(Applet a, int x,
int y, Graphics g) The constructor copies
the parameters to instance variables and starts the thread. Applet
is needed so the run method
can tell the applet to repaint. The integers x
and y are the coordinates
of target. Graphics is the
graphics context on which the targets are drawn. The thread is
started by simply calling start().
- public void run() This
method is where the thread starts and draws the targets. It is
called sometime after start()
is called in the constructor. The method first sets offGraphics
to XOR-Mode. In this mode, if something is drawn on something
previously drawn, it reverts back to its original color. Next,
the thread enters the nested for
loops. Each iteration draws a circle, asks the applet to repaint,
and sleeps for 200ms. The radius of the circle is varied from
10 to 80, and then from 80 back to 10. The thread dies on its
own after it exits the loops, so there is no need to call stop().
Listing 16.3 shows how data can be corrupted in a multithreaded
environment. If more than one thread manipulates shared variables
or objects at the same time, corruption may result. Instance variables
are shared between threads. If one is modified by a thread, the
change affects the other threads. Method variables are unique
for each threads. Each Thread has its own copy. Listing 16.3 uses
2 classes, ProblemThreadExample
and CorruptedDataExample.
The class ProblemThreadExample
extends the Applet class.
It has two methods, which are listed after Listing 16.3.
Listing 16.3. How to get corrupted data.
import java.lang.*;
import java.applet.Applet;
public class ProblemThreadExample extends Applet
{
CorruptedDataExample CDE;
public void start()
{
int i;
CDE=new CorruptedDataExample();
for(i=0;i<20;i++) /*
start 20 threads */
new Thread(CDE,new
String("booThread"+i)).start();
}
public void stop()
{
CDE.stopThreads();
}
}
class CorruptedDataExample extends Object implements Runnable
{
int num=0; /* num will be corrupted */
public void run()
{
int i=0;
for(;;)
{
for(i=0;i<1000;i++)
{
num=num+10;
num=num-10;
}
try
{Thread.sleep(10000);}
catch
(InterruptedException e ) {}
System.out.println(Thread.currentThread().getName()+
"
sees the number: " + num);
}
}
void stopThreads()
{
Thread tArray[];
int numThreads;
numThreads=Thread.activeCount();
tArray=new Thread[numThreads];
Thread.enumerate(tArray);
for(int i=0;i<numThreads;i++)
if(tArray[i].getName().startsWith("booThread"))
tArray[i].stop();
}
}
- public void start() This
method gets a new instance of the CorruptedDataExample
class and starts 20 threads. Each thread has an individual name
that is from "booThread0"
to "booThread19".
The threads start running in CorruptedDataExample's
run method.
- public void stop() This
method calls stopThreads()
in CorruptedDataExample.
The class CorruptedDataExample
does not guard against corruption of its instance variable num.
The class has two methods, which are as follows:
- public void run() This
method has an infinite loop that shows how data can be corrupted
by multiple threads. Twenty threads are executed in this loop
at the same time. The loop does the following:
- Adds 10 then -10 to num
1000 times
- Sleeps
- Prints a string that contains num
- The first step is the cause of the corruption. It serves no
purpose other than illustrating how data is corrupted.
- void stopThreads() All
of the booThreads are stopped
in this method. A list of threads is fetched. All of the threads
that have names that begin with booThread
are stopped.
The following is the ProblemThreadExample
output:
booThread0 sees the number: 0
booThread1 sees the number: 0
booThread2 sees the number: 0
booThread3 sees the number: 0
booThread4 sees the number: 10
booThread6 sees the number: 10
booThread7 sees the number: 10
booThread8 sees the number: 10
booThread9 sees the number: 10
booThread10 sees the number: 0
booThread11 sees the number: 0
booThread12 sees the number: 0
booThread13 sees the number: 0
booThread5 sees the number: 0
booThread14 sees the number: 0
booThread15 sees the number: 0
booThread16 sees the number: 0
booThread17 sees the number: 0
booThread18 sees the number: 0
booThread19 sees the number: 0
booThread0 sees the number: 0
booThread1 sees the number: 0
booThread3 sees the number: 0
booThread4 sees the number: 0
booThread6 sees the number: 0
booThread8 sees the number: 0
booThread9 sees the number: 0
booThread2 sees the number: 0
booThread7 sees the number: 0
booThread10 sees the number: 10
booThread11 sees the number: 0
booThread12 sees the number: -10
booThread13 sees the number: -10
booThread5 sees the number: -10
booThread14 sees the number: -10
booThread16 sees the number: -10
booThread17 sees the number: -10
booThread18 sees the number: -10
booThread19 sees the number: -10
The first step in the infinite loop would have no ill effect in
a single-threaded environment. It simply adds and then subtracts
10 to a variable with the net result being no change. However,
in a multithreaded environment, the operations can interfere with
each other. You can see one scenario in the following steps in
which two threads try to add 10 at the same time.
| Step | Thread A
| Thread B | num
|
| 1. | Atmp num
| | 0 |
| 2. | Atmp Atmp+10
| | 0 |
| 3. | | Btmp num
| 0 |
| 4. | | Btmp Btmp+10
| 0 |
| 5. | | num Btmp
| 10 |
| . | . | .
| . |
| . | . | .
| . |
| . | . | .
| . |
| 10. | num Atmp
| | 10 |
Two num=num+10; operations
have been executed, but the value of num
has only increased by 10. The problem here is that Thread A
was interrupted in the middle of its operation before it could
save its results. Threads A
and B have added 10 to the
same number.
This type of problem is somewhat rare, but should not be ignored.
In the previous example, 10 is added and subtracted 1000 times
in 20 threads, and the problem still did not occur that often.
The bad thing about these types of bugs is that they can be extremely
difficult to find. Imagine that num
is the index of an array. The problem may not show up until long
after num has been corrupted.
Generally, these bugs are not reproducible, so they are hard to
catch. In some ways the problem is amplified in Java because Java
is expected to run on so many platforms. On some systems, num=num+10
may be an atomic operation (cannot be interrupted). In this case,
everything works fine. A developer may create an applet on such
a system thinking that everything is fine, but it may not work
when someone from a different system views the applet. Data corruption
can also be more common with other data types. Integer operations
are simple compared to many others. Arrays or other data structures
can take much longer to process so it is much more likely to be
corrupted.
In Listing 16.3, the threads are given names. They are named booThread0
through booThread19 when
they are created by the constructor Thread(Runnable,String).
The names can be used to identify the threads. The thread names
are printed along with num
in the run() method of CorruptedDataExample.
The Thread method current.Thread()
is called to get a reference to the currently running thread.
The names are also used to stop the threads. A reference is needed
for each thread so that stop()
can be called to kill it. Thread.enumerate(Thread[])
gets a reference to every thread in this group. Some of these
threads are the booThreads,
but they may be others. The other threads should not be killed.
Before each thread is killed it is checked to see if its name
starts with booThread.
A way to prevent data from being corrupted by multiple threads
is to prevent the interruption of critical regions. Critical
regions are places like num=num+10
above, where only one thread should be running at once. Java's
synchronized can be used
to ensure that only one thread is in a critical region at once.
When the thread enters a synchronized code block, it tries to
get a lock on that region. While the thread is in the critical
region, no other thread can enter the critical region. If a thread
tries to enter and the code is already locked, the thread has
to wait for the other thread to leave the critical region. Listing
16.3 can be fixed by synchronizing the access to num.
The run() method in CorruptedDataExample
can be modified to the following:
public void run()
{
int i=0;
int tmp; /*new*/
for(;;)
{
for(i=0;i<1000;i++)
{
synchronized
(this) /*new*/
{
num=num+10;
num=num-10;
}
}
try
{Thread.sleep(10000);}
catch
(InterruptedException e ) {}
synchronized
(this) /*new*/
{tmp=num;} /*new*/
System.out.println(Thread.currentThread().getName()+
"
sees the number: " + tmp); /*new*/
}
}
The following lines make up a protected critical region:
synchronized
(this)
{
num=num+10;
num=num-10;
}
synchronized (this) ensures
that only one thread can be in the following code block. The argument
this tells the thread to
use the lock for this this
object.
The variable num is also
referenced when the string is printed. The new code is as follows:
synchronized
(this) /*new*/
{tmp=num;}
/*new*/
System.out.println(currentThread().getName()+
"
sees the number: " + tmp); /*new*/
A critical region is used to copy num
to temporary storage. The string is then printed using the temporary
storage. It would have been possible to synchronize the print
line directly, but it would cut performance because the print
line does many other things that have nothing to do with referencing
num. All the threads waiting
to enter the critical region will needlessly wait longer while
the print line is executed. Generally, the synchronized blocks
should be as small as possible while still protecting the critical
region.
You may also think that the other variables in the run
method, i and tmp,
also need to be synchronized, but it's not necessary. Both i
and tmp are method variables
so each running thread has its own private copy. There are 20
i's and tmp's
but there is only one num.
Listing 16.4 can be seen in Figure 16.3. This example shows how
synchronized can be used
to control critical regions. There are two synchronized methods:
drawRoundTarget() and drawSquareTarget().
If a thread is in a synchronized method, no other thread can be
in any synchronized method that uses the same lock. This example
draws only one square or circle at a time. The seven methods of
the SynchronizedThreadExample
applet are shown after Listing 16.4.
Figure 16.3 : Listing 16.4 draws a square.
Listing 16.4. Using synchronized.
import java.applet.Applet;
import java.awt.*;
public class SynchronizedThreadExample extends Applet
implements Runnable
{
Image offImage; /*
off screen image */
Graphics offGraphics; /* Graphics for offImage
*/
Thread Thr1, Thr2; /* threads */
public void start()
{
offImage=createImage(400,300);
offGraphics=offImage.getGraphics();
offGraphics.setColor(Color.white);
offGraphics.setXORMode(Color.blue);
Thr1=new Thread(this); Thr1.start();
Thr2=new Thread(this); Thr2.start();
}
public void stop()
{
Thr1.stop();
Thr2.stop();
}
public void paint(Graphics g)
{
g.drawImage(offImage,0,0,null);
}
public void update(Graphics g)
{
paint(g);
}
public void run()
{
for(;;)
{
drawRoundTarget();
drawSquareTarget();
}
}
synchronized void drawRoundTarget()
{
for(int r=0,i=10;i>-20;i-=20) /*
i=(10,-10) */
for(r+=i;(r<90)&&(r>0);r+=i)
/* r=(10,20...80,80,70...10) */
{
offGraphics.fillOval(200-r,150-r,2*r,2*r);
repaint();
try
{Thread.currentThread().sleep(200);}
catch
(InterruptedException e) {}
}
}
synchronized void drawSquareTarget()
{
int i,r;
for(r=0,i=10;i>-20;i-=20) /*
i=(10,-10) */
for(r+=i;(r<90)&&(r>0);r+=i)
/* r=(10,20...80,80,70...10) */
{
offGraphics.fillRect
(200-r,150-r,2*r,2*r);
repaint();
try
{Thread.currentThread().sleep(250);}
catch
(InterruptedException e) {}
}
}
}
The methods of the SynchronizedThreadExample
applet are as follows:
- public void start()/stop() The
threads are started and stopped in these methods.
- public void paint/update(Graphics) These
methods paint the applet.
- public void run() Both
threads start executing in this method. It is an infinite loop
that draws round and then square targets.
- synchronized void drawRoundTarget() This
method is synchronized. Only one thread can be inside drawing
circles.
- synchronized void drawSquareTarget() This
method is like drawRoundTarget,
but draws squares instead of circles.
What if two locks are needed?
The current applet only allows one target to be drawn at a time,
be it round or square. Suppose that you want the applet to draw
a round and a square target at the same time; you would need two
locks for two independent critical regions. The problem is that
each object has only one lock. Creating separate classes for drawRoundTarget()
and drawSquareTarget() could
solve the problem, but it may not be convenient. A better way
is to create new objects, and to use their locks to control the
methods. This is done by modifying Listing 16.4 as follows:
.
.
.
Object RoundSync,SquareSync; /*new*/
public void start()
{
. .
. .
. .
RoundSync=new Object(); /*new*/
SquareSync=new Object(); /*new*/
Thr1=new Thread(this); Thr1.start();
Thr2=new Thread(this); Thr2.start();
}
void drawRoundTarget()
{
synchronized (RoundSync) /*new*/
{
for(int
r=0,i=10;i>-20;i-=20)
. .
. .
. .
}
}
void drawSquareTarget()
{
synchronized (SquareSync) /*new*/
{
for(r=0,i=10;i>-20;i-=20)
. .
. .
. .
}
}
}
Two new Objects are created:
RoundSync and SquareSync.
The Objects don't actually
do anything themselves, but their locks are used when drawing
the targets. The instances of Object
are obtained in the start method. synchronized
(RoundSync) is put in front of the for
loops in the drawRoundTarget()
method and drawSquareTarget()
is modified similarly. When a thread tries to execute the body
of the target drawing methods, it first has to get a lock. drawRoundTarget()
gets a lock from the object RoundSync
and drawSquareTarget() gets
a lock from SquareSync().
After these modifications have been made, the drawRoundTarget()
and drawSquareTargets() methods
do not block each other. The applet draws round and square targets
at the same time. But it is not able to draw two round targets
or two square targets at the same time. Figure 16.4 shows the
results of the modifications.
Figure 16.4 : A square and round target being drawn at the same time.
The Dining Philosophers problem is a classic concurrent programming
problem. In the problem, a philosopher only does two things, think
and eat. A philosopher thinks for a while, and then gets hungry.
Then it eats until it gets full, and then starts thinking again.
Each philosopher is so involved in its own thinking or eating
that it's oblivious to anything else. The problem has five philosophers
that are sitting at a table. Between neighboring philosophers
there is a single chop stick. A philosopher must have both the
stick on its right and the stick on its left in order for it to
eat. Obviously, no two neighboring philosophers can be eating
at the same time. The philosophers cannot disturb each other.
If a philosopher wants to start eating and its neighbor has one
of the sticks, the philosopher must wait until the stick becomes
available. To solve the problem, an algorithm must be designed
to let all of the philosophers eat.
A simple algorithm for the philosophers could be:
Think
Get right chopstick
Get left chopstick
Eat
Drop left chopstick
Drop right chopstick
Repeat
There is one very serious problem with this algorithm. Suppose
that each philosopher picks up the right chopstick at the same
time. When they try to get the left stick, it won't be there.
The neighbor to the left has it. All of the philosophers starve
to death with a chopstick in one hand and food on the table. This
is known as a deadlock.
Deadlocks are always a danger in multithreaded environments. A
deadlock has occurred because
- Each thread needed exclusive use of the chopsticks.
- One thread is not allowed to take a chopstick from its neighbor.
- Each thread is waiting while holding a chopstick that another
thread is waiting for.
All deadlocks in any problem have the same reasons for deadlocking.
Instead of waiting for chopsticks, they are waiting for some other
resource or resources. If only one of the conditions can be broken,
a deadlock will not occur.
The first condition is usually hard to break. In the previous
algorithm this could done by allowing philosophers to share a
chopstick, but that isn't really possible. Sometimes threads need
exclusive use of a resource. Things like the instance of a class
or a socket may require that only one thread may use it at once.
The second condition can sometimes be used to avoid deadlocks.
If a philosopher was allowed to take a chopstick from its neighbor,
there would not be a deadlock. However, if the philosophers keep
taking sticks from each other, they may never get a chance to
take a bite. Some problems can be solved by allowing resource
stealing. It depends on the resource and the problem.
If the deadlock cannot be avoided with the other conditions, it
should be avoided by breaking the third condition. The philosophers
can avoid a deadlock if there is a special chopstick that they
aren't allowed to hold while they are waiting for the second chopstick.
They are allowed to eat with the special stick, but they can't
just hold it. An algorithm should not be too strict, otherwise
the resources may be underused. For example, an algorithm could
be made that only allows one philosopher to eat at once. Obviously,
there would be no deadlocks, but a philosopher may have to wait
longer before it can eat.
There are many solutions to the Dining Philosophers problem. One
solution follows.
One of the chopsticks is marked as gold, while the rest are wood.
No philosopher is allowed to hold the gold stick without eating.
This prevents the philosophers from deadlocking. The philosophers
picks up one chopstick then the other. If the gold stick is picked
up first, it is put down and the other stick is picked up. It
is possible that in the time between putting down the gold chopstick
and picking up the other chopstick, all the other philosophers
will have eaten and moved the gold chopstick all the way around
the table, so when the philosopher picks up the other chopstick,
it too is the gold chopstick. If this happens, the philosopher
starts over. The solution is as follows:
Think
Pick up right chopstick
If right chopstick is gold
Drop right chopstick
Pick up left chopstick
If left chopstick is gold
Start over
Pick up right chopstick
Else
Pick up left chopstick
Eat
Switch chopsticks in hands
Drop right chopstick
Drop left chopstick
Repeat
The chopsticks are switched when the philosopher puts down the
chopsticks. This allows the philosophers equal chances to eat.
Otherwise, the philosopher to the left of the gold chopstick would
be disadvantaged.
The philosophers may interfere with each other when they try to
pick up a chopstick. A critical region is used to ensure that
one philosopher can pick up or put down a chopstick. If one philosopher
is picking up or putting down a stick, its neighbor is not allowed
to touch the stick. What if a philosopher enters the critical
section to get a chopstick, but the chopstick is not there? The
philosopher must wait until the stick returns. This is done by
a special wait in the critical
section. The philosopher releases its lock and waits in the critical
section. This allows the other philosopher to enter the critical
section to return the chopstick. After the chopstick is returned,
the waiting philosopher is woken up. After awakening, the philosopher
reacquires the lock and continues executing. At any one time there
can be only one philosopher running in the critical section, but
it is OK if another philosopher is also sleeping in the critical
section.
Java has three wait() and
two notify() methods that
aid in synchronizing threads. The wait()
methods cause the thread to pause in the critical region. While
paused, the thread releases its lock. It must get the lock again
before it starts executing again. The notify()
methods wake up threads that have called wait().
Calling notify() when no
wait() has been called has
no effect. The methods shown below are in the Object
class and can only be called in a synchronized
block or method.
- public final void wait() This
method causes the thread to wait forever until a notify()
or notifyAll() is called.
The thread releases its lock on the critical regions so that other
threads may enter.
- public final void wait(long m) This
method causes the thread to wait m
milliseconds for a notify()
or notifyAll() to be called.
After the time is expired, the thread tries to resume execution.
However, it must first reobtain the lock for the critical region.
Another thread may have entered the critical section while the
thread was waiting.
- public final void wait(long m, int
n) This method is similar to the previous
one except that it waits for m
milliseconds plus n nanoseconds.
- public final void notify() This
method wakes up a thread that has previously called wait().
The thread that was waiting has to get the lock before it can
resume execution. It has to wait until the current thread leaves
the critical region. Only one thread that has called wait()
is woken up. It is not guaranteed that the first thread that called
wait() is the first one woken
up.
- public final void notifyAll() This
method wakes up all the threads that have called wait().
Each waiting thread has to get the lock for the critical region
before it resumes. There can still be only one thread running
in the critical section at once.
The Dining Philosophers applet uses four classes: the ones shown
in Listings 16.5, 16.6, 16.7, and 16.8. The first class, DiningPhilosophers,
extends the Applet class.
The structure of this class is similar to the first example. Philosopher
threads are created when the applet is initialized. They are suspended
if the user leaves the page and resumed if the user returns. However,
unlike the first example, no threads are created in this class.
The Dining Philosophers example can be seen in Figure 16.5.
Figure 16.5 : The Dining Philosophers example.
Listing 16.5. The class DiningPhilosophers.
public class DiningPhilosophers extends
Applet
{
final int numPhils=5;
Image offImage; /*
off screen image */
Graphics offGraphics; /* Graphics for offImage
*/
Philosopher Phil[] = new Philosopher[numPhils];
Chopstick Stick[] = new Chopstick[numPhils];
ScenePainter painter;
public void init()
{
int i;
offImage=createImage(400,300);
offGraphics=offImage.getGraphics();
painter=new ScenePainter(offGraphics,this,numPhils);
for(i=0;i<numPhils;i++)
Stick[i]=new Chopstick
(i==0 ? Chopstick.gold :
Chopstick.wood,
painter,i);
for(i=0;i<numPhils;i++)
Phil[i]= new Philosopher(Stick[i],Stick[(i+1)%numPhils],
painter,i);
}
public void start()
{
int i;
for(i=0;i<numPhils;i++)
Phil[i].resume();
}
public void stop()
{
int i;
for(i=0;i<numPhils;i++)
Phil[i].suspend();
}
public void destroy()
{
int i;
for(i=0;i<numPhils;i++)
{
Phil[i].resume();
Phil[i].stop();
}
}
public void paint(Graphics g)
{
g.drawImage(offImage,0,0,null);
}
public void update(Graphics Dijkstra)
{
paint(Dijkstra);
}
}
The class DiningPhilosophers
has six methods and is similar to the InfiniteThreadExample.
- public void init() This
method initializes the applet. It creates five instances of the
classes Chopstick and Philosopher.
One of the Chopstick classes
is created as a gold chopstick,
the rest are wood. Each Philosopher
can reach two Chopsticks.
On the right is Chopstick
i, and on the left is Chopstick
i+1 mod 5.
- public void start() This
method resumes philosopher execution.
- public void stop() This
method suspends philosopher execution.
- public void destroy() This
method kills the philosophers.
- public void paint()/update() These
two methods paint the state of the philosophers.
Each philosopher at the table is its own thread. The thread is
created in the class Philosopher
by extending Thread. The
methods in the class control the philosopher's life of thinking
and eating. Initially, the philosopher is thinking. After some
time, the philosopher picks up the two chopsticks next to it and
starts eating. It calls methods in the Chopstick
class (see Listing 16.7) to get the chopsticks. The philosopher
also paints its state by calling methods in the ScenePainter
class (see Listing 16.8).
Listing 16.6. The class Philosopher.
class Philosopher extends Thread
{
final int ThinkTime=5000, EatTime=3000;
Chopstick rightStick,leftStick;
ScenePainter painter;
int rightHand,leftHand;
int myNum;
public Philosopher(Chopstick right, Chopstick left,
ScenePainter
p, int n)
{
painter=p;
myNum=n;
rightStick=right;
leftStick=left;
start();
}
public void run()
{
for(;;)
{
think();
PickUpSticks();
eat();
PutDownSticks();
}
}
void think()
{
painter.drawThink(myNum);
try {sleep((int)(ThinkTime*Math.random()));}
catch (InterruptedException
e) {}
painter.drawThink(myNum);
}
void PickUpSticks()
{
for(boolean gotem=false;!gotem;)
{
painter.drawFirstGrab(myNum);
rightHand=rightStick.grabStick();
painter.drawSecondGrab(myNum);
if(rightHand==Chopstick.gold)
{
painter.drawGoldGrab(myNum);
rightStick.dropStick(rightHand);
leftHand=leftStick.grabStick();
if(leftHand==Chopstick.gold)
{
leftStick.dropStick(leftHand);
continue; /*
gold stick went around table */
}
rightHand=rightStick.grabStick();
painter.drawGoldGrab(myNum);
}
else
leftHand=leftStick.grabStick();
painter.drawSecondGrab(myNum);
painter.drawFirstGrab(myNum);
gotem=true;
}
}
void eat()
{
painter.drawEat(myNum);
try {sleep((int)(EatTime*Math.random()));}
catch (InterruptedException
e) {}
painter.drawEat(myNum);
}
void PutDownSticks()
{/* swap sticks and put them down */
rightStick.dropStick(leftHand);
leftStick.dropStick(rightHand);
}
}
The class Philosopher is
used to start the threads for the Dining Philosophers applet.
The class has the following five methods:
- public void run() This
method defines the philosophers actions. Each philosopher thinks,
waits to pick up its chopsticks, eats, returns the chopsticks,
and repeats the cycle.
- void think() This
method is where the philosopher thinks. The thinking image is
drawn and the philosopher sleeps for a random amount of time.
- void PickUpSticks() In
this method, the philosopher picks up the chopsticks in a way
that is fair and avoids deadlocks.
- void eat() This
method is where the philosopher eats. The eating image is drawn
and the philosopher sleeps for a random amount of time.
- void PutDownSticks() In
this method, the philosopher returns the sticks. The chopsticks
are switched when they are put down so that the gold stick is
not always in the same place.
All of the synchronization is done in the Chopstick
class. There is one instance of this class for each chopstick
on the table. The class is used by the philosophers when they
want to pick up or return a chopstick. The three states of the
chopstick are represented by the variable stickHolder:
noStick means the chopstick
is gone, wood means this
is the wooden stick, and gold
means this is the golden stick. stickHolder
is an instance variable. More than one philosopher may be trying
to get/drop it at once, so there is a danger of data corruption.
The methods of this class are synchronized
to ensure that stickHolder
does not get corrupted (see Listing 16.7).
Listing 16.7. The class Chopstick.
class Chopstick extends Object
{
final static int noStick=0;
final static int wood=1;
final static int gold=2;
ScenePainter painter;
int stickHolder;
int myNum;
public Chopstick(int stick, ScenePainter p, int n)
{
painter=p;
myNum=n;
dropStick(stick);
}
synchronized int grabStick()
{
int Thuy;
if(stickHolder==noStick)
try {wait();}
catch (InterruptedException e) {}
painter.drawStick(myNum,stickHolder);
Thuy=stickHolder;
stickHolder=noStick;
return Thuy;
}
synchronized void dropStick(int stick)
{
stickHolder=stick;
painter.drawStick(myNum,stickHolder);
notify();
}
}
The class Chopstick is used
to synchronize the threads in the Dining Philosophers applet.
The class has the following two methods:
- synchronized int grabStick() Philosophers
(threads) will come into this method when they attempt to get
a stick. If the stick is there, the method gives the stick to
the philosopher. If the stick has already been taken by its neighbor,
the philosopher waits for the stick to be returned.
- synchronized void dropStick() The
philosophers use this method to return the sticks. If the other
philosopher is waiting for this chopstick, it is woken.
The class ScenePainter is
used by the philosophers to paint their state. If a philosopher
starts eating, puts down a stick, or does anything else, it calls
methods in this class. The states of philosophers (for example,
eating or waiting for a stick) are represented by different shapes.
When a philosopher starts thinking, it calls drawThink(myNum)
to draw the philosopher in its thinking state. Then, when it is
done thinking, it calls drawThink(myNum)
again to erase the philosopher. All of the methods in this class
are called in pairs. The first call draws a state and the second
erases it.
Listing 16.8. The class ScenePainter.
class ScenePainter extends Object
{
int sX1[], sY1[], sX2[], sY2[], pX[], pY[];
final int xOffset=150, yOffset=150, Tscale=70;
final int rg=2, rEating=15, rThinking=8, rFirst=7;
final int rSecond=3, rGold=5;
Graphics G;
Component C;
public ScenePainter(Graphics g, Component c, int numPhils)
{
int i;
pX = new int[numPhils];
pY = new int[numPhils];
sX1 = new int[numPhils]; sY1
= new int[numPhils];
sX2 = new int[numPhils]; sY2
= new int[numPhils];
double arc=Math.PI/numPhils;
G=g; C=c;
for(i=0;i<numPhils;i++)
{
pX[i]=
(int)(xOffset+ Tscale*Math.cos(i*2*arc));
pY[i]=
(int)(yOffset+ Tscale*Math.sin(i*2*arc));
sX1[i]=(int)(xOffset+
Tscale*Math.cos(i*2*arc+arc));
sY1[i]=(int)(yOffset+
Tscale*Math.sin(i*2*arc+arc));
sX2[i]=(int)(xOffset+.7*Tscale*Math.cos(i*2*arc+arc));
sY2[i]=(int)(yOffset+.7*Tscale*Math.
sin(i*2*arc+arc));
}
G.setColor(Color.white);
G.setXORMode(Color.blue);
}
void drawStick(int num, int stick)
{
G.drawLine(sX1[num],sY1[num],sX2[num],sY2[num]);
if(stick==Chopstick.gold)
G.fillOval(sX1[num]-rg,sY1[num]-rg,rg+rg,rg+rg);
C.repaint();
}
void drawEat(int num)
{
fillCircle(num,rEating);
}
void drawThink(int num)
{
fillCircle(num,rThinking);
}
void drawFirstGrab(int num)
{
fillSquare(num,rFirst);
}
The class ScenePainter is
used to draw the state of all the philosophers in the Dining Philosophers
applet.
- public ScenePainter(Graphics, Component,
int) The constructor for this class calculates
the position of each philosopher and chopstick.
- void drawStick(num, stick) This
method draws/erases the chopstick specified by num.
A stick is represented by drawing a line between the two philosophers
that may use it. If stick
is the gold chopstick, a
small circle is added to the end of the chopstick.
- void drawEat(num) This
method draws/erases the philosopher specified by num
in its eating state. A large circle represents the eating state.
- void drawThink(num) This
method draws/erases a small circle that represents a philosopher
in its thinking state.
- void drawFirstGrab(num) This
method draws/erases a small square. The method is called when
the philosopher tries to grab the first stick.
- void drawSecondGrab(num) This
method erases/draws a smaller square inside the square drawn by
drawFirstGrab(num). The method
is called after the philosopher already has one chopstick and
is trying to grab the second. A philosopher in this state is represented
by a small hollow square.
- void drawGoldGrab(num) This
method is called if the first stick the philosopher picked up
is the gold stick. It is
only called after both drawFirstGrab(num)
and drawSecondGrab(num) have
been called. A philosopher in this state is represented by a small
hollow square with a tiny circle in the middle.
Threads are the life in an applet. Some threads are created by
the system, but others are started in the applet. Threads can
be started to remove some of the burden from a system thread,
or to start its own line of execution.
This chapter contained several applets that started threads. The
examples showed specific uses of threads that can be expanded
to general use. Most threading problems can be solved by using
slight variations of the first two examples. These examples have
threads that do not communicate with other threads. If threads
need to communicate with each other, care must be taken to avoid
data corruption. The third example shows data corruption and the
steps that must be taken to avoid it. The forth example shows
how two threads can be synchronized so that they can do things
in the right order. The final example, the Dining Philosophers,
shows many of the subtle problems in a multithreaded environment.
If threads in an applet compete for common resources, a deadlock
can occur unless care is taken to avoid it. The examples in this
chapter are just that, examples. The reader is encouraged to experiment
with them, tweak some of the parameters, add more threads, but
most of all, have fun.
Next
Previous
Contents
|
