Thread code

• HelloThread.java  simple example 1
• HelloRunnable.java   simple example 2
• SleepMessages.java   print messages at four-second intervals:
• SimpleThreads.java

Supporting Interruption

for (int i = 0; i < importantInfo.length; i++) {
 //Pause for 4 seconds
 try {
 Thread.sleep(4000);
 } catch (InterruptedException e) {
 //We've been interrupted: no more messages.
 return;
 }
 //Print a message
 System.out.println(importantInfo[i]);
}

The join method allows one thread to wait for the completion of another. If t is a Thread object whose thread is currently executing,

t.join();

causes the current thread to pause execution until t's thread terminates. Overloads of join allow the programmer to specify a waiting period. However, as with sleep, join is dependent on the OS for timing, so you should not assume that join will wait exactly as long as you specify.

Like sleep, join responds to an interrupt by exiting with an InterruptedException. 

Threads communicate primarily by sharing access to fields and the objects reference fields refer to. This form of communication is extremely efficient, but makes two kinds of errors possible: thread interference and memory consistency errors. The tool needed to prevent these errors is synchronization.

• Thread Interference describes how errors are introduced when multiple threads access shared data.
• Memory Consistency Errors describes errors that result from inconsistent views of shared memory.
• Synchronized Methods describes a simple idiom that can effectively prevent thread interference and memory consistency errors.
• Implicit Locks and Synchronization describes a more general synchronization idiom, and describes how synchronization is based on implicit locks.
• Atomic Access talks about the general idea of operations that can't be interfered with by other threads.

Multithreading

• 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

1. Implement a class that implements the Runnable interface

   public interface Runnable
   {
    void run();
   }

2. 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

3. Create an object of your subclass

   Runnable r = new MyRunnable();

4. Construct a Thread object from the runnable object.

   Thread t = new Thread(r);

5. 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

• sleep puts current thread to sleep for given number of milliseconds

  Thread.sleep(milliseconds)

• When a thread is interrupted, most common response is to terminate run

Generic run method

public void run()
{
 try
 {
 Task statements
 }
 catch (InterruptedException exception)
 {
 }
 Clean up, if necessary
}

File GreetingRunnable.java

To Start the Thread

• Construct an object of your runnable class
  

  Runnable t = new GreetingRunnable("Hello World");

• Then construct a thread and call the start method.

  Thread t = new Thread(r);
  t.start();

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

1. What happens if you change the call to the sleep method in the run method to Thread.sleep(1)?
2. What would be the result of the program if the main method called

   r1.run();
   r2.run();

   instead of starting threads?

Answers

1. The messages are printed about one millisecond apart.
2. 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 terminate–it sets a boolean field in the thread data structure

Terminating Threads

• The run method should check occasionally whether it has been interrupted
  • Use the interrupted method
  • An interrupted thread should release resources, clean up, and exit

    public void run()
    {
     for (int i = 1;
     i <= REPETITIONS && !Thread.interrupted(); i++)
     {
     Do work
     }
     Clean up
    }

Terminating Threads

• The sleep method throws an InterruptedException when a sleeping thread is interrupted
  • Catch the exception
  • Terminate the thread

  public void run()
  {
   try
   {
   for (int i = 1; i <= REPETITIONS; i++)
   {
   Do work
   }
   }
   catch (InterruptedException exception)
   {
   }
   Clean up
  }

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

3. 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

4. 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

3. 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.
4. 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

• When threads share a common object, they can conflict with each other
• Sample program: multiple threads manipulate a bank account
  Here is the run method of DepositRunnable:

  public void run()
  {
   try
   {
   for (int i = 1; i <= count; i++)
   {
   account.deposit(amount);
   Thread.sleep(DELAY);
   }
   }
   catch (InterruptedException exception)
   {
   }
  }

• The WithdrawRunnable class is similar

Sample Application

• Create a BankAccount object
• Create two threads:
  • t1 deposits $100 into the bank account for 10 iterations
  • t2 withdraws $100 from the bank account for 10 iterations
• deposit and withdraw have been modified to print messages:

  public void deposit(double amount)
  {
   System.out.print("Depositing " + amount);
   double newBalance = balance + amount;
   System.out.println(", new balance is " + newBalance);
   balance = newBalance;
  }

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

1. 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
2. t1 reaches the end of its time slice and t2 gains control
3. t2 calls the withdraw method which withdraws $100 from the balance variable;
   it is now -100
4. t2 goes to sleep
5. 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

5. 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.
6. 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

5. 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.
6. 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

• Typically, a lock object is added to a class whose methods access shared resources, like this:

  public class BankAccount
  {
   public BankAccount()
   {
   balanceChangeLock = new ReentrantLock();
   . . .
   }
   . . .
   private Lock balanceChangeLock;
  }

Synchronizing Object Access

• Code that manipulates shared resource is surrounded by calls to lock and unlock:

  balanceChangeLock.lock();
  Code that manipulates the shared resource
  balanceChangeLock.unlock();

Synchronizing Object Access

• If code between calls to lock and unlock throws an exception, call to unlock never happens
• To overcome this problem, place call to unlock into a finally clause:

  public void deposit(double amount)
  {
   balanceChangeLock.lock();
   try
   {
   System.out.print("Depositing " + amount);
   double newBalance = balance + amount;
   System.out.println(", new balance is " + newBalance);
   balance = newBalance;
   }
   finally
   {
   balanceChangeLock.unlock();
   }
  }

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

7. If you construct two BankAccount objects, how many lock objects are created?
8. What happens if we omit the call unlock at the end of the deposit method?

Answers

7. Two, one for each bank account object. Each lock protects a separate balance field.
8. 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

• A deadlock occurs if no thread can proceed because each thread is waiting for another to do some work first
• BankAccount example

  public void withdraw(double amount)
  {
   balanceChangeLock.lock();
   try
   {
   while (balance < amount)
   Wait for the balance to grow
   . . .
   }
   finally
   {
   balanceChangeLock.unlock();
   }
  }

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

• To overcome problem, use a condition object
• Condition objects allow a thread to temporarily release a lock, and to regain the lock at a later time
• Each condition object belongs to a specific lock object
• You obtain a condition object with newCondition method of Lock interface

  public class BankAccount
  {
   public BankAccount()
   {
   balanceChangeLock = new ReentrantLock();
   sufficientFundsCondition = balanceChangeLock.newCondition();
   . . .
   }
   . . .
   private Lock balanceChangeLock;
   private Condition sufficientFundsCondition;
  }

Condition Objects

• It is customary to give the condition object a name that describes condition to test
• You need to implement an appropriate test
• As long as test is not fulfilled, call await on the condition object:

  public void withdraw(double amount)
  {
   balanceChangeLock.lock();
   try
   {
   while (balance < amount)
   sufficientFundsCondition.await();
   . . .
   }
   finally
   {
   balanceChangeLock.unlock();
   }
  }

Condition Objects

• Calling await
  • Makes current thread wait
  • Allows another thread to acquire the lock object
• To unblock, another thread must execute signalAll on the same condition object

  sufficientFundsCondition.signalAll();

• signalAll unblocks all threads waiting on the condition
• signal: randomly picks just one thread waiting on the object and unblocks it
• signal can be more efficient, but you need to know that every waiting thread can proceed
• Recommendation: always call signalAll

Self Check

9. What is the essential difference between calling sleep and await?
10. Why is the sufficientFundsCondition object a field of the BankAccount class and not a local variable of the withdraw and deposit methods?

Answers

9. 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.
10. The calls to await and signal/signalAll must be made to the same object.