Threads

Threads
An Introduction with Examples in Java

Prof. David Bernstein
James Madison University

Computer Science Department

bernstdh@jmu.edu

Background

Multi-Tasking:
- More than one application can be run "at the same time"
Multi-Threading:
- One application can run more than one method/function "at the same time"

Background (cont.)

Multithreading Made "Easy":
- When the code running in the different threads is independent
Multithreading in General:
- The threads interact, making the design and programming much more difficult

Motivation

A Dispatching Application:
- We have "regular" dispatches every day
- We must dispatch vehicles in real-time
The Design:

Motivation (cont.)

A Dispatcher

javaexamples/threads/v1/Dispatcher.java

Motivation (cont.)

An AbstractDispatchHandler

javaexamples/threads/v1/AbstractDispatchHandler.java

Motivation (cont.)

A DailyDispatchHandler

javaexamples/threads/v1/DailyDispatchHandler.java

Motivation (cont.)

A RealTimeDispatchHandler

javaexamples/threads/v1/RealTimeDispatchHandler.java

Motivation (cont.)

The Main Class

javaexamples/threads/v1/Driver.java

Motivation (cont.)

The Problem:
- The RealTimeDispatchHandler does not start working until the DailyDispatchHandler has completed its job
- In other words, the while loop in the processDispatches() method maintains control of the CPU until all of the daily dispatches have been completed
What We Need:
- A way for multiple objects to use the Dispatcher "at the same time"

Using Multiple Threads Naively

javaexamples/threads/v2/AbstractDispatchHandler.java

Using Multiple Threads Naively (cont.)

Some Important Observations:
- The Dispatcher now has shared mutable state
The Implication:
- We must coordinate the threads
Before Exploring Coordination:
- We should consider some other issues

The Thread Lifecycle in Java

Sleeping

An Observation:
- The DailyDispatchHandler uses a tight loop that wastes processor resources
A Fix:
- Have the thread sleep

Sleeping (cont.)

javaexamples/threads/v3/DailyDispatchHandler.java

Interruption

The interrupt() Method:
- Used to ask a thread to stop what it is currently doing (by setting its interrupt status to true
Writing Cancellable Methods:
- Periodically check the interrupt status using the isInterrupted() method of the controlling Thread object

Starting and Stopping Threads

Some Remaining Problems:
- The DailyDispatchHandler and RealTimeDispatcher run until EOS
A Solution:
- Add a boolean attribute called keepRunning and change the do-while loop from do{...}while (line != null); to do{...}while (keepRunning && (line != null));
- Add a stop() method that assigns false to keepRunning

Volatile Attributes

An Observation:
- One thread "stores" values in keepRunning (i.e., the thread that stop() executes in) and another "loads" values from it (i.e., the dispatch handler's thread)
A Speculation:
- This doesn't cause a problem since "store" and "load" must be atomic
In Fact:
- Java does not ensure that changes to attributes that are made in one thread will propogate to other threads in the way you would expect (e.g., because of processor-specific caching and the re-ordering of operations)

Volatile Attributes (cont.)

The volatile Modifier:
- Indicates to the compiler and JVM that the variable is shared
The Impact:
- A read of a volatible attribute always returns the most recent write by any thread
A Caution:
- volatile reference types only provide this guarantee for the referenec itself (e.g., not the elemnts of an array or the attributes of an object)

Stopping and Interrupting Threads (and Volatile Attributes)

javaexamples/threads/v4/AbstractDispatchHandler.java

Understanding the Defect in the Dispatching Example

An Observation:
- The Dispatcher has shared mutable state
The Implication:
- We need to take steps to ensure that the code is correct

Understanding the Defect

javaexamples/threads/v1/Dispatcher.java (Fragment: dispatch)

Understanding the Defect (cont.)

The Situation:
- One vehicle in the queue
- The first thread executes all of the code up to and including the evaluation of (availableVehicles.size() > 0) and then runs out of time
- The seconds thread executes all of the code in this method before it runs out of time
The Problem:
- When the first thread starts executing again, it will proceed as if it had never been off the CPU and will attempt to get a vehicle from the queue (which is empty)

Race Conditions

Defined:
- Code that causes the correctness of a computation to depend on the relative timing of different threads
This Example:
- A check-then-act condition
Other Kinds:
- read-modify-write conditions

Race Conditions (cont.)

A Simpler Example:
- public int getNextIndex() { return ++index; }
The Problem:
- This method can return the same value to two threads since the increment operator is not atomic - it loads the value (read), increments the value (modify), and stores the value (write)

Race Conditions (cont.)

A Simple Example of Mutable State

javaexamples/threads/NonatomicInteger.java

Race Conditions (cont.)

Making the Mutable State Shared

javaexamples/threads/Counter.java

Race Conditions (cont.)

An Application that Illustrates the Defect

javaexamples/threads/CounterDriver.java

Synchronization with Monitors

Monitors (a.k.a. Implicit Locks):
- Every object (and class) has a "concurrency protection" object called a monitor
- A thread of execution can only enter a synchronized method or block if it can acquire the relevant monitor
- When a thread exits a synchronized method it releases the monitor
How This Provides Protection:
- Only one thread can acquire a monitor at a time
- Other threads block until they can acquire the relevant monitor
A Detail:
- One thread can acquire the same monitor multiple times (a counter is used), making it re-entrant

Two Ways to Use Monitors

synchronized Methods:
- The method is declared synchronized
- The "owner's" monitor is used
synchronized Blocks:
- The block is declared to be synchronized
- The declaration explicitly includes the Object whose monitor should be used

Synchronization (cont.)

Protecting the Shared Mutable State

javaexamples/threads/SynchronizedInteger.java

The Dispatching Example (cont.)

A Modification to the Dispatcher

javaexamples/threads/v5a/Dispatcher.java (Fragment: dispatch)

A Fault Still Exists

The Fault:
- Both the dispatch() method and the makeVehicleAvailable() method change the queue
- So, one thread can be removing vehicles from the queue and another thread can be adding vehicles to the queue
The Fix:
- Synchronize makeVehicleAvailable()

The Dispatching Example (cont.)

Another Modification to the Dispatcher

javaexamples/threads/v5a/Dispatcher.java (Fragment: makeVehicleAvailable)

Liveness Defects

Defined:
- A state in which an application/algorithm is unable to make progress
Types:
- Deadlock - two or more threads are waiting on a condition that can't be satisfied
- Livelock - a thread can't make progress because it repeatedly attempts an operation that fails (e.g., "you first", "no, you first")

Liveness Defects (cont.)

A Seemingly Small Change:
- Suppose the dispatch() method is modified so that, instead of returning false if no vehicles are available it loops until one is available
A Deadlock Situation:
- No vehicles are available and one thread acquries the monitor by executing dispatch()
Why this is a Deadlock:
- No other thread can acquire the monitor and execute makeVehicleAvailable()

Liveness Defects (cont.)

One Possible Fix:
- Have the thread executing the dispatch() method enter the waiting state if no vehicles are available
Why It Works:
- The thread gives up the monitor so makeVehicleAvailable() can be executed in another thread
To Remember:
- The thread that executes makeVehicleAvailable() must notify the waiting threads

The Dispatching Example (cont.)

The Modified Dispatcher

javaexamples/threads/v6a/Dispatcher.java

Memory Consistency

Memory Consistency Errors:
- Occur when different threads have inconsistent views of what should be the same data (e.g., as with keepRunning before it was declared to be volatile)
The Happens-Before Relationship:
- A guarantee that memory writes by one specific statement are visible to another specific statement

Memory Consisteny (cont.)

Some Actions that Create Happens-Before Relationships:
- Each action in a thread happens-before every action in that thread that comes later in the program's order
- A synchronized block or method exit happens-before every subsequent synchronized block or method entry
- A write to a volatile attribute happens-before every subsequent read of that same attribute
- A call to start() on a thread happens-before any action in the started thread
- All actions in a thread happen-before any other thread successfully returns from a join() on that thread
Transitivity?
- The happens-before relationship is transitive

Future Topics

Coordination:
- Alternatives to Monitors
Thread-Aware Objects:
Pools:
- Executors and Thread Pools
- Fork/Join Pools