## Object-Oriented Design & Patterns

#### Cay S. Horstmann

### Chapter 9

### Multithreading

## Chapter Topics

- Thread Basics
- Thread Synchronization
- Animations

## Threads

- Thread: program unit that is executed independently
- Multiple threads run simultaneously
- Virtual machine executes each thread for short time slice
- Thread scheduler activates, deactivates threads
- Illusion of threads running in parallel
- Multiprocessor computers: threads actually run in parallel

## Running Threads

- Define class that implements `Runnable`
- ``Runnable`` has one method
  `void run()`
- Place thread action into `run` method
- Construct object of runnable class
- Construct thread from that object
- Start thread

## Running Threads

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

## Thread Example

- 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

- Ch9/greeting/GreetingProducer.java
- Ch9/greeting/ThreadTester.java

## Thread Example

- 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

## Thread States

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

## Thread States

## Blocked Thread State

- 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

- 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

- 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

- 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

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

## Thread Synchronization

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

## Producer Thread

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

## Consumer Thread

    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

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

## Why is Output Corrupted?

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

- Ch9/queue1/ThreadTester.java
- Ch9/queue1/Producer.java
- Ch9/queue1/Consumer.java
- Ch9/queue1/BoundedQueue.java

## Race Condition Scenario

- 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

## Locks

- 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

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

## Scenario with Locks

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

## Deadlocks

- 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

- 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

- 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
- Ch9/queue2/BoundedQueue.java

## Object Locks

- 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

- 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
      }

- Ch9/queue3/BoundedQueue.java

## Visualizing Locks

- Object = phone booth
- Thread = person
- Locked object = closed booth
- Blocked thread = person waiting for booth to open

## Visualizing Locks

## Algorithm Animation

- Use thread to make progress in algorithm
- Display algorithm state
- Example: Animate Ch9/animation/Sorter.java
- Sleeps inside `compare` method
- Pass custom comparator
  `Comparator<Double> comp = new
  Comparator<Double>()
  {
  public void compare(Double d1, Double d2)
  {
  ` `sleep
  ` `return comparison result
  }
  };
  `

## Algorithm Animation

- Ch9/animation1/ArrayComponent.java
- Ch9/animation1/AnimationTester.java

## Pausing and Running the Animation

- 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
- Ch9/animation2/Sorter.java
- Ch9/animation2/AnimationTester.java