Chapter 23
Multithreading
Chapter Goals
- To understand how multiple threads can execute in parallel
- To learn how to implement threads
- To understand race conditions and deadlocks
- To be able to avoid corruption of shared objects by using locks and conditions
- To be able to use threads for programming animations
Threads
- A thread is a program unit that is executed independently of other parts
of the program
- The Java Virtual Machine executes each thread in the program for a short
amount of time
- This gives the impression of parallel execution
Running a Thread
- Implement a class that implements the Runnable interface
public interface Runnable
{
void run();
}
- Place the code for your task into the run
method of your class
public class MyRunnable implements Runnable
{
public void run()
{
// Task statements go here
. . .
}
}
Running a Thread
- Create an object of your subclass
Runnable r = new MyRunnable();
- Construct a Thread object from the runnable object.
Thread t = new Thread(r);
- Call the start method to start the thread.
t.start();
Example
A program to print a time stamp and "Hello World" once a second for ten seconds:
Thu Dec 28 23:12:03 PST 2004 Hello, World!
Thu Dec 28 23:12:04 PST 2004 Hello, World!
Thu Dec 28 23:12:05 PST 2004 Hello, World!
Thu Dec 28 23:12:06 PST 2004 Hello, World!
Thu Dec 28 23:12:07 PST 2004 Hello, World!
Thu Dec 28 23:12:08 PST 2004 Hello, World!
Thu Dec 28 23:12:09 PST 2004 Hello, World!
Thu Dec 28 23:12:10 PST 2004 Hello, World!
Thu Dec 28 23:12:11 PST 2004 Hello, World!
Thu Dec 28 23:12:12 PST 2004 Hello, World!
GreetingRunnable Outline
public class GreetingRunnable implements Runnable
{
public GreetingRunnable(String aGreeting)
{
greeting = aGreeting;
}
public void run()
{
// Task statements go here
. . .
}
// Fields used by the task statements
private String greeting;
}
Thread Action for GreetingRunnable
- Print a time stamp
- Print the greeting
- Wait a second
GreetingRunnable
- We can get the date and time by constructing a Date object
Date now = new Date();
- To wait a second, use the sleep method of the Thread class
sleep(milliseconds)
- A sleeping thread can generate an InterruptedException
- Catch the exception
- Terminate the thread
Running Threads
Generic run method
public void run()
{
try
{
Task statements
}
catch (InterruptedException exception)
{
}
Clean up, if necessary
}
File GreetingRunnable.java
To Start the Thread
File GreetingThreadTester.java
Output
Thu Dec 28 23:12:03 PST 2004 Hello, World!
Thu Dec 28 23:12:03 PST 2004 Goodbye, World!
Thu Dec 28 23:12:04 PST 2004 Hello, World!
Thu Dec 28 23:12:05 PST 2004 Hello, World!
Thu Dec 28 23:12:04 PST 2004 Goodbye, World!
Thu Dec 28 23:12:05 PST 2004 Goodbye, World!
Thu Dec 28 23:12:06 PST 2004 Hello, World!
Thu Dec 28 23:12:06 PST 2004 Goodbye, World!
Thu Dec 28 23:12:07 PST 2004 Hello, World!
Thu Dec 28 23:12:07 PST 2004 Goodbye, World!
Thu Dec 28 23:12:08 PST 2004 Hello, World!
Thu Dec 28 23:12:08 PST 2004 Goodbye, World!
Thu Dec 28 23:12:09 PST 2004 Hello, World!
Thu Dec 28 23:12:09 PST 2004 Goodbye, World!
Thu Dec 28 23:12:10 PST 2004 Hello, World!
Thu Dec 28 23:12:10 PST 2004 Goodbye, World!
Thu Dec 28 23:12:11 PST 2004 Goodbye, World!
Thu Dec 28 23:12:11 PST 2004 Hello, World!
Thu Dec 28 23:12:12 PST 2004 Goodbye, World!
Thu Dec 28 23:12:12 PST 2004 Hello, World!
Thread Scheduler
- The thread scheduler runs each thread for a short amount of time (a time slice)
- Then the scheduler activates another thread
- There will always be slight variations in running times
especially when calling operating system services (e.g. input and output)
- There is no guarantee about the order in which threads are executed
Self Check
- What happens if you change the call to the sleep method in the run method to Thread.sleep(1)?
- What would be the result of the program if the main method called
r1.run();
r2.run();
instead of starting threads?
Answers
- The messages are printed about one millisecond apart.
- The first call to run would print ten "Hello" messages, and then the second call
to run would print ten "Goodbye" messages.
Terminating Threads
- A thread terminates when its run method terminates
- Do not terminate a thread using the deprecated stop method
- Instead, notify a thread that it should terminate
t.interrupt();
- interrupt does not cause the thread to terminateit sets a boolean field in the thread data structure
Terminating Threads
- The run method should check occasionally whether it has been interrupted
Terminating Threads
Terminating Threads
- Java does not force a thread to terminate when it is interrupted
- It is entirely up to the thread what it does when it is interrupted
- Interrupting is a general mechanism for getting the thread's attention
Self Check
- Suppose a web browser uses multiple threads to load the images on a web page.
Why should these threads be terminated when the user hits the "Back" button?
Self Check
- Consider the following runnable.
public class MyRunnable implements Runnable
{
public void run()
{
try
{
System.out.println(1);
Thread.sleep(1000);
System.out.println(2);
}
catch (InterruptedException exception)
{
System.out.println(3);
}
System.out.println(4);
}
}
Suppose a thread with this runnable is started and immediately interrupted.
Thread t = new Thread(new MyRunnable());
t.start();
t.interrupt();
What output is produced?
Answers
- If the user hits the "Back" button, the current web page is no longer displayed,
and it makes no sense to expend network resources for fetching additional
image data.
- The run method prints the values 1, 3, and 4. The call to interrupt merely
sets the interruption flag, but the sleep method immediately throws an
InterruptedException.
Race Conditions
Sample Application
Sample Application
- The result should be zero, but sometimes it is not
- Normally, the program output looks somewhat like this:
Depositing 100.0, new balance is 100.0
Withdrawing 100.0, new balance is 0.0
Depositing 100.0, new balance is 100.0
Depositing 100.0, new balance is 200.0
Withdrawing 100.0, new balance is 100.0
. . .
Withdrawing 100.0, new balance is 0.0
- But sometimes you may notice messed-up output, like this:
Depositing 100.0Withdrawing 100.0, new balance is 100.0, new balance is -100.0
Scenario to Explain Non-zero Result: Race Condition
- The first thread t1 executes the lines
System.out.print("Depositing " + amount);
double newBalance = balance + amount;
The balance field is still 0, and the newBalance local variable is 100
- t1 reaches the end of its time slice and t2 gains control
- t2 calls the withdraw method which withdraws $100 from the balance
variable;
it is now -100
- t2 goes to sleep
- t1 regains control and picks up where it left off; it executes:
System.out.println(", new balance is " + newBalance);
balance = newBalance;
The balance is now 100 instead of 0 because the deposit method used the
OLD balance
Corrupting the Contents of the balance Field
Race condition
- Occurs if the effect of multiple threads on shared data depends on the order
in which they are scheduled
- It is possible for a thread to reach the end of its time slice in the middle
of a statement
- It may evaluate the right-hand side of an equation but not be able to store
the result until its next turn
public void deposit(double amount)
{
balance = balance + amount
;
System.out.print("Depositing " + amount + ", new balance is " + balance);
}
Race condition can still occur:
balance = the right-hand-side value
File BankAccountThreadTester.java
File DepositRunnable.java
File WithdrawRunnable.java
File BankAccount.java
Output
Depositing 100.0, new balance is 100.0
Withdrawing 100.0, new balance is 0.0
Depositing 100.0, new balance is 100.0
Withdrawing 100.0, new balance is 0.0
. . .
Withdrawing 100.0, new balance is 400.0
Depositing 100.0, new balance is 500.0
Withdrawing 100.0, new balance is 400.0
Withdrawing 100.0, new balance is 300.0
Self Check
- Give a scenario in which a race condition causes the bank balance to be -100
after one iteration of a deposit thread and a withdraw thread.
- Suppose two threads simultaneously insert objects into a linked list.
Using the implementation in Chapter 20, explain how the list can be damaged in the process.
Answers
- There are many possible scenarios. Here is one:
- The first thread loses control after the first print statement.
- The second thread loses control just before the assignment balance = newBalance.
- The first thread completes the deposit method.
- The second thread completes the withdraw method.
- One thread calls addFirst and is preempted just before executing the assignment
first = newLink. Then the next thread calls addFirst, using the old value
of first. Then the first thread completes the process, setting first to its new
link. As a result, the links are not in sequence.
Synchronizing Object Access
- To solve problems such as the one just seen, use a lock object
- A lock object is used to control threads that manipulate shared resources
- In Java: Lock interface and several classes that implement it
- ReentrantLock: most commonly used lock class
- Locks are a feature of Java version 5.0
- Earlier versions of Java have a lower-level facility for thread synchronization
Synchronizing Object Access
Synchronizing Object Access
Synchronizing Object Access
Synchronizing Object Access
- When a thread calls lock, it owns the lock until it calls unlock
- A thread that calls lock while another thread owns the lock is temporarily deactivated
- Thread scheduler periodically reactivates thread so it can try to acquire the lock
- Eventually, waiting thread can acquire the lock
Visualizing Object Locks
Self Check
- If you construct two BankAccount objects, how many lock objects are created?
- What happens if we omit the call unlock at the end of the deposit method?
Answers
- Two, one for each bank account object. Each lock protects a separate balance
field.
- When a thread calls deposit, it continues to own the lock, and any other thread
trying to deposit or withdraw money in the same bank account is blocked
forever.
Avoiding Deadlocks
Avoiding Deadlocks
- How can we wait for the balance to grow?
- We can't simply call sleep inside withdraw method;
thread will block all other threads that want to use balanceChangeLock
- In particular, no other thread can successfully execute deposit
- Other threads will call deposit, but will be blocked until withdraw exits
- But withdraw doesn't exit until it has funds available
- DEADLOCK
Condition Objects
Condition Objects
Condition Objects
File BankAccountThreadTester.java
File BankAccount.java
Output
Depositing 100.0, new balance is 100.0
Withdrawing 100.0, new balance is 0.0
Depositing 100.0, new balance is 100.0
Depositing 100.0, new balance is 200.0
. . .
Withdrawing 100.0, new balance is 100.0
Depositing 100.0, new balance is 200.0
Withdrawing 100.0, new balance is 100.0
Withdrawing 100.0, new balance is 0.0
Self Check
- What is the essential difference between calling sleep and await?
- Why is the sufficientFundsCondition object a field of the BankAccount class
and not a local variable of the withdraw and deposit methods?
Answers
- A sleeping thread is reactivated when the sleep delay has passed. A waiting
thread is only reactivated if another thread has called signalAll or signal.
- The calls to await and signal/signalAll must be made to the same object.
An Application of Threads: Animation
- Shows different objects moving or changing as time progresses
- Is often achieved by launching one or more threads that compute how parts of the animation change
- Can use Swing Timer class for simple animations
- More advanced animations are best implemented with threads
- An algorithm animation helps visualize the steps in the algorithm
Algorithm Animation
- Runs in a separate thread that periodically updates an image of the current
state of the algorithm
- It then pauses so the user can see the change
- After a short time the algorithm thread wakes up and runs to the next point
of interest
- It updates the image again and pauses again
Selection Sort Algorithm Animation
- Items in the algorithm's state
- The array of values
- The size of the already sorted area
- The currently marked element
- This state is accessed by two threads:
- One that sorts the array, and
- One that repaints the frame
- To visualize the algorithm
- Show the sorted part of the array in a different color
- Mark the currently visited array element in red
A Step in the Animation of the Selection Sort Algorithm
Selection Sort Algorithm Animation: Implementation
- Use a lock to synchronize access to the shared state
- Add a component instance field to the algorithm class and augment the constructor to set it
- That instance field is needed for
- Repainting the component, and
- Finding out the dimensions of the component when drawing the algorithm state
public class SelectionSorter
{
public SelectionSorter(int[] anArray, JComponent aComponent
)
{
a = anArray;
sortStateLock = new ReentrantLock();
component = aComponent;
}
. . .
private JComponent component;
}
Selection Sort Algorithm Animation: Implementation
Selection Sort Algorithm Animation: Implementation
- We add a draw method to the algorithm class
- draw draws the current state of the data structure, highlighting items of special interest
- draw is specific to the particular algorithm
- In this case, draws the array elements as a sequence of sticks in different colors
- The already sorted portion is blue
- The marked position is red
- The remainder is black
Selection Sort Algorithm Animation: draw
public void draw(Graphics2D g2)
{
sortStateLock.lock();
try
{
int deltaX = component.getWidth() / a.length;
for (int i = 0; i < a.length; i++)
{
if (i == markedPosition)
g2.setColor(Color.RED);
else if (i <= alreadySorted)
g2.setColor(Color.BLUE);
else
g2.setColor(Color.BLACK);
g2.draw(new Line2D.Double(i * deltaX, 0, i * deltaX, a[i]));
}
}
finally
{
sortStateLock.unlock();
}
}
Selection Sort Algorithm Animation: Pausing
- Update the special positions as the algorithm progresses
- Pause the animation whenever something interesting happens
- Pause should be proportional to the number of steps that are being executed
- In this case, pause one unit for each visited array element
- Augment minimumPosition and sort accordingly
Selection Sort Algorithm Animation: Pausing
public int minimumPosition(int from)
throws InterruptedException
{
int minPos = from;
for (int i = from + 1; i < a.length; i++)
{
sortStateLock.lock();
try
{
if (a[i] < a[minPos]) minPos = i;
markedPosition = i;
}
finally
{
sortStateLock.unlock();
}
pause(2); // two array elements were inspected
}
return minPos;
}
Selection Sort Algorithm Animation: paintComponent
paintComponent calls the draw method of the algorithm object:
public class SelectionSortComponent extends JComponent
{
public void paintComponent(Graphics g)
{
if (sorter == null) return;
Graphics2D g2 = (Graphics2D) g;
sorter.draw(g2);
}
. . .
private SelectionSorter sorter;
}
Selection Sort Algorithm Animation: startAnimation
public void startAnimation()
{
int[] values = ArrayUtil.randomIntArray(30, 300);
sorter = new SelectionSorter(values, this);
class AnimationRunnable implements Runnable
{
public void run()
{
try
{
sorter.sort();
}
catch (InterruptedException exception)
{
}
}
}
Runnable r = new AnimationRunnable();
Thread t = new Thread(r);
t.start();
}
File SelectionSortViewer.java
File SelectionSortComponent.java
File SelectionSorter.java
Self Check
- Why is the draw method added to the SelectionSorter class and not the
SelectionSortComponent class?
- Would the animation still work if the startAnimation method simply called
sorter.sort() instead of spawning a thread that calls that method?
Answers
- The draw method uses the array values and the values that keep track of the
algorithm's progress. These values are available only in the SelectionSorter class.
- Yes, provided you only show a single frame. If you modify the
SelectionSortViewer program to show two frames, you want the sorters
to run in parallel.
Embedded Systems