Chapter 23

Multithreading


Chapter Goals

Threads

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

  1. Create an object of your subclass
    Runnable r = new MyRunnable();
  2. Construct a Thread object from the runnable object.
    Thread t = new Thread(r);
  3. 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

GreetingRunnable

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

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

Terminating Threads

Terminating Threads

Terminating Threads

Self Check

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

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

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

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

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

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

  1. There are many possible scenarios. Here is one:
  2. 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

Synchronizing Object Access

Synchronizing Object Access

Synchronizing Object Access

Synchronizing Object Access

Visualizing Object Locks


Self Check

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

Answers

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

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

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

Answers

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

An Application of Threads: Animation

Algorithm Animation

Selection Sort Algorithm Animation

A Step in the Animation of the Selection Sort Algorithm


Selection Sort Algorithm Animation: Implementation

Selection Sort Algorithm Animation: Implementation

Selection Sort Algorithm Animation: Implementation

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

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

  1. Why is the draw method added to the SelectionSorter class and not the SelectionSortComponent class?
  2. Would the animation still work if the startAnimation method simply called sorter.sort() instead of spawning a thread that calls that method?

Answers

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