SE450: Horstmann Chapter 9

public class MyRunnable implements Runnable
{
   public void run()
   {
      thread action
   }
}
...
Runnable r = new MyRunnable();
Thread t = new Thread(t);
t.start();

Thread Example [6/36]

Run two threads in parallel

Each thread prints 10 greetings

for (int i = 1; i <= 10; i++)
{
   System.out.println(i + ": " + greeting);
   Thread.sleep(100);
}

After each printout, sleep for 100 millisec
All threads should occasionally yield control
sleep throws InterruptedException

Thread Example [7/36]

file:horstmann/ch09_greeting/GreetingProducer.java [source] [doc-public] [doc-private]

package horstmann.ch09_greeting;
/**
   An action that repeatedly prints a greeting.
 */
public class GreetingProducer implements Runnable
{
  /**
      Constructs the producer object.
      @param aGreeting the greeting to display
   */
  public GreetingProducer(String aGreeting)
  {
    greeting = aGreeting;
  }

  public void run()
  {
    try
    {
      for (int i = 1; i <= REPETITIONS; i++)
      {
        System.out.println(i + ": " + greeting);
        Thread.sleep(DELAY);
      }
    }
    catch (InterruptedException exception)
    {
    }
  }

  private String greeting;

  private static final int REPETITIONS = 10;
  private static final int DELAY = 100;
}

file:horstmann/ch09_greeting/ThreadTester.java [source] [doc-public] [doc-private]

package horstmann.ch09_greeting;
/**
   This program runs two threads in parallel.
 */
public class ThreadTester
{
  public static void main(String[] args)
  {
    Runnable r1 = new GreetingProducer("Hello, World!");
    Runnable r2 = new GreetingProducer("Goodbye, World!");

    Thread t1 = new Thread(r1);
    Thread t2 = new Thread(r2);

    t1.start();
    t2.start();
  }
}

Thread Example [8/36]

Note: output not exactly interleaved

1: Hello, World! 
1: Goodbye, World! 
2: Hello, World! 
2: Goodbye, World! 
3: Hello, World! 
3: Goodbye, World! 
4: Hello, World! 
4: Goodbye, World! 
5: Hello, World! 
5: Goodbye, World! 
6: Hello, World! 
6: Goodbye, World! 
7: Hello, World! 
7: Goodbye, World! 
8: Goodbye, World! 
8: Hello, World! 
9: Goodbye, World! 
9: Hello, World! 
10: Goodbye, World! 
10: Hello, World!

Starting Two Threads [9/36]

Thread States [10/36]

Each thread has
- thread state
- priority
Thread states:
- new (before start called)
- runnable
- blocked
- dead (after run method exits)

Thread States [11/36]

Blocked Thread State [12/36]

Reasons for blocked state:
- Sleeping
- Waiting for I/O
- Waiting to acquire lock (later)
- Waiting for condition (later)
Unblocks only if reason for block goes away

Scheduling Threads [13/36]

Scheduler activates new thread if
- a thread has completed its time slice
- a thread has blocked itself
- a thread with higher priority has become runnable
Scheduler determines new thread to run
- looks only at runnable threads
- picks one with max priority

Terminating Threads [14/36]

Thread terminates when run exits
Sometimes necessary to terminate running thread
Don't use deprecated stop method
Interrupt thread by calling interrupt
Calling t.interrupt() doesn't actually interrupt t; just sets a flag
Interrupted thread must sense interruption and exit its run method
Interrupted thread has chance to clean up

Sensing Interruptions [15/36]

Thread could occasionally call
Thread.currentThread().isInterrupted()
sleep, wait throw InterruptedException when thread interrupted
. . . and then the interruption status is cleared!
More robust: Sleep occasionally, catch exception and react to interruption
Recommendation: Terminate run when sensing interruption

Sensing Interruptions [16/36]

public class MyRunnable implements Runnable
{
   public void run()
   {
      try
      {
         while (...)
         {
            do work            
            Thread.sleep(...);
         }      
      }
      catch (InterruptedException e) {}
      clean up
   }
}

Thread Synchronization [17/36]

Use bounded queue from chapter 3
Each producer thread inserts greetings
Each consumer thread removes greetings
Two producers, one consumer

Producer Thread [18/36]

int i = 1; 
while (i <= greetingCount) 
{ 
   if (!queue.isFull()) 
   { 
      queue.add(i + ": " + greeting); 
      i++; 
   } 
   Thread.sleep((int)(Math.random() * DELAY)); 
}

Consumer Thread [19/36]

int i = 1; 
while (i <= greetingCount) 
{ 
   if (!queue.isEmpty()) 
   { 
      Object greeting = queue.remove(); 
      System.out.println(greeting); 
      i++; 
   } 
   Thread.sleep((int)(Math.random() * DELAY)); 
}

Expected Program Output [20/36]

1: Hello, World! 
1: Goodbye, World! 
2: Hello, World! 
3: Hello, World! 
... 
99: Goodbye, World! 
100: Goodbye, World!

Why is Output Corrupted? [21/36]

Sometimes program gets stuck and doesn't complete
Can see problem better when turning debugging on
queue.setDebug(true);

file:horstmann/ch09_queue1/ThreadTester.java [source] [doc-public] [doc-private]

package horstmann.ch09_queue1;
/**
   This program runs two threads in parallel.
 */
public class ThreadTester
{
  public static void main(String[] args)
  {
    BoundedQueue<String> queue = new BoundedQueue<String>(10);
    queue.setDebug(true);
    final int GREETING_COUNT = 100;
    Runnable run1 = new Producer("Hello, World!",
        queue, GREETING_COUNT);
    Runnable run2 = new Producer("Goodbye, World!",
        queue, GREETING_COUNT);
    Runnable run3 = new Consumer(queue, 2 * GREETING_COUNT);

    Thread thread1 = new Thread(run1);
    Thread thread2 = new Thread(run2);
    Thread thread3 = new Thread(run3);

    thread1.start();
    thread2.start();
    thread3.start();
  }
}

file:horstmann/ch09_queue1/Producer.java [source] [doc-public] [doc-private]

package horstmann.ch09_queue1;
/**
   An action that repeatedly inserts a greeting into a queue.
 */
public class Producer implements Runnable
{
  /**
      Constructs the producer object.
      @param aGreeting the greating to insert into a queue
      @param aQueue the queue into which to insert greetings
      @param count the number of greetings to produce
   */
  public Producer(String aGreeting, BoundedQueue<String> aQueue, int count)
  {
    greeting = aGreeting;
    queue = aQueue;
    greetingCount = count;
  }

  public void run()
  {
    try
    {
      int i = 1;
      while (i <= greetingCount)
      {
        if (!queue.isFull())
        {
          queue.add(i + ": " + greeting);
          i++;
        }
        Thread.sleep((int) (Math.random() * DELAY));
      }
    }
    catch (InterruptedException exception)
    {
    }
  }

  private String greeting;
  private BoundedQueue<String> queue;
  private int greetingCount;

  private static final int DELAY = 10;
}

file:horstmann/ch09_queue1/Consumer.java [source] [doc-public] [doc-private]

package horstmann.ch09_queue1;
/**
   An action that repeatedly removes a greeting from a queue.
 */
public class Consumer implements Runnable
{
  /**
      Constructs the consumer object.
      @param aQueue the queue from which to retrieve greetings
      @param count the number of greetings to consume
   */
  public Consumer(BoundedQueue<String> aQueue, int count)
  {
    queue = aQueue;
    greetingCount = count;
  }

  public void run()
  {
    try
    {
      int i = 1;
      while (i <= greetingCount)
      {
        if (!queue.isEmpty())
        {
          String greeting = queue.remove();
          System.out.println(greeting);
          i++;
        }
        Thread.sleep((int)(Math.random() * DELAY));
      }
    }
    catch (InterruptedException exception)
    {
    }
  }

  private BoundedQueue<String> queue;
  private int greetingCount;

  private static final int DELAY = 10;
}

file:horstmann/ch09_queue1/BoundedQueue.java [source] [doc-public] [doc-private]

package horstmann.ch09_queue1;
import java.util.ArrayList;
/**
    A first-in, first-out bounded collection of objects.
 */
public class BoundedQueue<E>
{
  /**
       Constructs an empty queue.
       @param capacity the maximum capacity of the queue
   */
  public BoundedQueue(int capacity)
  {
    elements = new ArrayList<E>(capacity);
    head = 0;
    tail = 0;
    size = 0;
  }

  /**
       Removes the object at the head.
       @return the object that has been removed from the queue
       <p><b>Precondition:</b> !isEmpty()</p>
   */
  public E remove()
  {
    if (debug) System.out.print("removeFirst");
    E r = elements.get(head);
    if (debug) System.out.print(".");
    head++;
    if (debug) System.out.print(".");
    size--;
    if (head == elements.size())
    {
      if (debug) System.out.print(".");
      head = 0;
    }
    if (debug)
      System.out.println("head=" + head + ",tail=" + tail
          + ",size=" + size);
    return r;
  }

  /**
       Appends an object at the tail.
       @param newValue the object to be appended
       <p><b>Precondition:</b> !isFull();</p>
   */
  public void add(E newValue)
  {
    if (debug) System.out.print("add");
    elements.set(tail,newValue);
    if (debug) System.out.print(".");
    tail++;
    if (debug) System.out.print(".");
    size++;
    if (tail == elements.size())
    {
      if (debug) System.out.print(".");
      tail = 0;
    }
    if (debug)
      System.out.println("head=" + head + ",tail=" + tail
          + ",size=" + size);
  }

  public boolean isFull()
  {
    return size == elements.size();
  }

  public boolean isEmpty()
  {
    return size == 0;
  }

  public void setDebug(boolean newValue)
  {
    debug = newValue;
  }

  private ArrayList<E> elements;
  private int head;
  private int tail;
  private int size;
  private boolean debug;
}

Race Condition Scenario [22/36]

First thread calls add and executes
elements[tail] = anObject;
First thread at end of time slice
Second thread calls add and executes
elements[tail] = anObject;
tail++;
Second thread at end of time slice
First thread executes
tail++;

Race Condition Scenario [23/36]

Locks [24/36]

Thread can acquire lock
When another thread tries to acquire same lock, it blocks
When first thread releases lock, other thread is unblocked and tries again
Two kinds of locks
- Objects of class implementing java.util.concurrent.Lock interface type, usually ReentrantLock
- Locks that are built into every Java object

Reentrant Locks [25/36]

aLock = new ReentrantLock();
. . .
aLock.lock();
try
{
   protected code
}
finally
{
   aLock.unlock();
}

Scenario with Locks [26/36]

First thread calls add and acquires lock, then executes
elements[tail] = anObject;
Second thread calls add and tries to acquire lock, but it is blocked
First thread executes
tail++;
First thread completes add, releases lock
Second thread unblocked
Second thread acquires lock, starts executing protected code

Deadlocks [27/36]

Not enough to synchronize add, remove
if (!queue.isFull()) queue.add(...);
can still be interrupted

Must move test inside add method

public void add(E newValue)
{
   queueLock.lock();
   try
   {
      while (queue is full)
         wait for more space
      . . .
   }
   finally { qeueLock.unlock(); }
}

Problem: nobody else can call remove

Avoiding Deadlocks [28/36]

Use condiiton object to manage "space available" condition

private Lock queueLock = new ReentrantLock();
private Condition spaceAvailableCondition
   = queueLock.newCondition();

Call await when condition is not fulfilled:

public void add(E newValue)
{
   . . .
   while (size == elements.length)
      spaceAvailableCondition.await();
   . . .
}

Avoiding Deadlocks [29/36]

Waiting thread is blocked
Condition object manages set of threads that wait for the condition to change
To unblock, another thread must call signalAll on the same condition object

Call when state changes

public E remove()
{
   . . .
   E r = elements[head];
   . . .
   spaceAvailableCondition.signalAll(); // Unblock waiting threads
   return r;
}

All waiting threads removed from wait set, unblocked

file:horstmann/ch09_queue2/BoundedQueue.java [source] [doc-public] [doc-private] 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 package horstmann.ch09_queue2; import java.util.ArrayList; import java.util.concurrent.locks.Condition; import java.util.concurrent.locks.Lock; import java.util.concurrent.locks.ReentrantLock; /** A first-in, first-out bounded collection of objects. */ public class BoundedQueue<E> { /** Constructs an empty queue. @param capacity the maximum capacity of the queue */ public BoundedQueue(int capacity) { elements = new ArrayList<E>(capacity); head = 0; tail = 0; size = 0; } /** Removes the object at the head. @return the object that has been removed from the queue */ public E remove() throws InterruptedException { queueLock.lock(); try { while (size == 0) valueAvailableCondition.await(); E r = elements.get(head); head++; size--; if (head == elements.size()) head = 0; spaceAvailableCondition.signalAll(); return r; } finally { queueLock.unlock(); } } /** Appends an object at the tail. @param newValue the object to be appended */ public void add(E newValue) throws InterruptedException { queueLock.lock(); try { while (size == elements.size()) spaceAvailableCondition.await(); elements.set(tail,newValue); tail++; size++; if (tail == elements.size()) tail = 0; valueAvailableCondition.signalAll(); } finally { queueLock.unlock(); } } private ArrayList<E> elements; private int head; private int tail; private int size; private Lock queueLock = new ReentrantLock(); private Condition spaceAvailableCondition = queueLock.newCondition(); private Condition valueAvailableCondition = queueLock.newCondition(); } Object Locks [30/36] Each object has a lock Calling a synchronized method acquires lock of implicit parameter Leaving the synchronized method releases lock Easier than explicit Lock objects public class BoundedQueue<E> { public synchronized void add(E newValue) { . . . } public synchronized E remove() { . . . } . . . } Object Locks [31/36] Each implicit lock has one associated (anonymous) condition object Object.wait blocks current thread and adds it to wait set Object.notifyAll unblocks waiting threads public synchronized void add(E newValue) throws InterruptedException { while (size == elements.length) wait(); elements[tail] = anObject; . . . notifyAll(); // notifies threads waiting to remove elements } file:horstmann/ch09_queue3/BoundedQueue.java [source] [doc-public] [doc-private] 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 package horstmann.ch09_queue3; import java.util.ArrayList; /** A first-in, first-out bounded collection of objects. */ public class BoundedQueue<E> { /** Constructs an empty queue. @param capacity the maximum capacity of the queue */ public BoundedQueue(int capacity) { elements = new ArrayList<E>(capacity); head = 0; tail = 0; size = 0; } /** Removes the object at the head. @return the object that has been removed from the queue */ public synchronized E remove() throws InterruptedException { while (size == 0) wait(); E r = elements.get(head); head++; size--; if (head == elements.size()) head = 0; notifyAll(); return r; } /** Appends an object at the tail. @param newValue the object to be appended */ public synchronized void add(E newValue) throws InterruptedException { while (size == elements.size()) wait(); elements.set(tail,newValue); tail++; size++; if (tail == elements.size()) tail = 0; notifyAll(); } private ArrayList<E> elements; private int head; private int tail; private int size; } Visualizing Locks [32/36] Object = phone booth Thread = person Locked object = closed booth Blocked thread = person waiting for booth to open Visualizing Locks [33/36] Algorithm Animation [34/36] Use thread to make progress in algorithm Display algorithm state Example: Animate the Sorter below Sleeps inside compare method Pass custom comparator Comparator<Double> comp = new Comparator<Double>() { public void compare(Double d1, Double d2) { sleep return comparison result } }; file:horstmann/ch09_animation1/Sorter.java [source] [doc-public] [doc-private] 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 package horstmann.ch09_animation1; import java.util.Comparator; /** This runnable executes a sort algorithm. When two elements are compared, the algorithm pauses and updates a panel. */ public class Sorter implements Runnable { /** Constructs the sorter. @param values the array to sort @param panel the panel for displaying the array */ public Sorter(Double[] values, ArrayComponent panel) { this.values = values; this.panel = panel; } public void run() { Comparator<Double> comp = (d1, d2) -> { panel.setValues(values, d1, d2); try { Thread.sleep(DELAY); } catch (InterruptedException exception) { Thread.currentThread().interrupt(); } return (d1).compareTo(d2); }; MergeSorter.sort(values, comp); panel.setValues(values, null, null); } private Double[] values; private ArrayComponent panel; private static final int DELAY = 100; } Algorithm Animation [35/36] file:horstmann/ch09_animation1/ArrayComponent.java [source] [doc-public] [doc-private] 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 package horstmann.ch09_animation1; import java.awt.Graphics; import java.awt.Graphics2D; import java.awt.geom.Rectangle2D; import javax.swing.JComponent; /** This component draws an array and marks two elements in the array. */ @SuppressWarnings("serial") public class ArrayComponent extends JComponent { public synchronized void paintComponent(Graphics g) { if (values == null) return; Graphics2D g2 = (Graphics2D) g; int width = getWidth() / values.length; for (int i = 0; i < values.length; i++) { Double v = values[i]; Rectangle2D bar = new Rectangle2D.Double( width * i, 0, width, v); if (v == marked1 || v == marked2) g2.fill(bar); else g2.draw(bar); } } /** Sets the values to be painted. @param values the array of values to display @param marked1 the first marked element @param marked2 the second marked element */ public synchronized void setValues(Double[] values, Double marked1, Double marked2) { this.values = values.clone(); this.marked1 = marked1; this.marked2 = marked2; repaint(); } private Double[] values; private Double marked1; private Double marked2; } file:horstmann/ch09_animation1/AnimationTester.java [source] [doc-public] [doc-private] 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 package horstmann.ch09_animation1; import java.awt.BorderLayout; import javax.swing.JFrame; /** This program animates a sort algorithm. */ public class AnimationTester { public static void main(String[] args) { JFrame frame = new JFrame(); frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE); ArrayComponent panel = new ArrayComponent(); frame.add(panel, BorderLayout.CENTER); frame.setSize(FRAME_WIDTH, FRAME_HEIGHT); frame.setVisible(true); Double[] values = new Double[VALUES_LENGTH]; for (int i = 0; i < values.length; i++) values[i] = Math.random() * panel.getHeight(); Runnable r = new Sorter(values, panel); Thread t = new Thread(r); t.start(); } private static final int VALUES_LENGTH = 30; private static final int FRAME_WIDTH = 300; private static final int FRAME_HEIGHT = 300; } Pausing and Running the Animation [36/36] Want to pause animation until "Run" or "Step" button is clicked Need to coordinate UI thread, animation thread Try to use built-in thread-safe construct in java.util.concurrent Trick: Use a blocking queue Button click adds string "Run" or "Step" to queue Animation thread calls take on the queue, blocks if no string inserted file:horstmann/ch09_animation2/Sorter.java [source] [doc-public] [doc-private] 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 package horstmann.ch09_animation2; import java.util.Comparator; import java.util.concurrent.BlockingQueue; /** This runnable executes a sort algorithm. When two elements are compared, the algorithm pauses and updates a panel. */ public class Sorter implements Runnable { public Sorter(Double[] values, ArrayComponent panel, BlockingQueue<String> queue) { this.values = values; this.panel = panel; this.queue = queue; } public void run() { Comparator<Double> comp = (d1, d2) -> { try { String command = queue.take(); if (command.equals("Run")) { Thread.sleep(DELAY); if (!"Step".equals(queue.peek())) queue.add("Run"); } } catch (InterruptedException exception) { Thread.currentThread().interrupt(); } panel.setValues(values, d1, d2); return d1.compareTo(d2); }; MergeSorter.sort(values, comp); panel.setValues(values, null, null); } private Double[] values; private ArrayComponent panel; private BlockingQueue<String> queue; private static final int DELAY = 100; } file:horstmann/ch09_animation2/AnimationTester.java [source] [doc-public] [doc-private] 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 package horstmann.ch09_animation2; import java.awt.BorderLayout; import java.util.concurrent.BlockingQueue; import java.util.concurrent.LinkedBlockingQueue; import javax.swing.JButton; import javax.swing.JFrame; import javax.swing.JPanel; /** This program animates a sort algorithm. */ public class AnimationTester { public static void main(String[] args) { JFrame frame = new JFrame(); frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE); ArrayComponent panel = new ArrayComponent(); frame.add(panel, BorderLayout.CENTER); JButton stepButton = new JButton("Step"); final JButton runButton = new JButton("Run"); JPanel buttons = new JPanel(); buttons.add(stepButton); buttons.add(runButton); frame.add(buttons, BorderLayout.NORTH); frame.setSize(FRAME_WIDTH, FRAME_HEIGHT); frame.setVisible(true); Double[] values = new Double[VALUES_LENGTH]; for (int i = 0; i < values.length; i++) values[i] = Math.random() * panel.getHeight(); final BlockingQueue<String> queue = new LinkedBlockingQueue<String>(); queue.add("Step"); final Sorter sorter = new Sorter(values, panel, queue); stepButton.addActionListener(event -> { queue.add("Step"); runButton.setEnabled(true); }); runButton.addActionListener(event -> { runButton.setEnabled(false); queue.add("Run"); }); Thread sorterThread = new Thread(sorter); sorterThread.start(); } private static final int FRAME_WIDTH = 300; private static final int FRAME_HEIGHT = 300; private static final int VALUES_LENGTH = 30; } Revised: 2007/09/11 16:41