- Forward


Threads
An Introduction with Examples in Java


Prof. David Bernstein
James Madison University

Computer Science Department
bernstdh@jmu.edu

Print

Background
Back Forward
  • 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.)
Back Forward
  • 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
Back Forward
  • A Dispatching Application:
    • We have "regular" dispatches every day
    • We must dispatch vehicles in real-time
  • The Design:
    • images/emergency-dispatch.gif
Motivation (cont.)
Back Forward

A Dispatcher

javaexamples/threads/v1/Dispatcher.java
 
Motivation (cont.)
Back Forward

An AbstractDispatchHandler

javaexamples/threads/v1/AbstractDispatchHandler.java
 
Motivation (cont.)
Back Forward

A DailyDispatchHandler

javaexamples/threads/v1/DailyDispatchHandler.java
 
Motivation (cont.)
Back Forward

A RealTimeDispatchHandler

javaexamples/threads/v1/RealTimeDispatchHandler.java
 
Motivation (cont.)
Back Forward

The Main Class

javaexamples/threads/v1/Driver.java
 
Motivation (cont.)
Back Forward
  • 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
Back Forward
javaexamples/threads/v2/AbstractDispatchHandler.java
 
Using Multiple Threads Naively (cont.)
Back Forward
  • 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
Back Forward

images/threadlife.gif

Sleeping
Back Forward
  • An Observation:
    • The DailyDispatchHandler uses a tight loop that wastes processor resources
  • A Fix:
    • Have the thread sleep
Sleeping (cont.)
Back Forward
javaexamples/threads/v3/DailyDispatchHandler.java
 
Interruption
Back Forward
  • 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
Back Forward
  • 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
Back Forward
  • 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.)
Back Forward
  • 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)
Back Forward
javaexamples/threads/v4/AbstractDispatchHandler.java
 
Understanding the Defect in the Dispatching Example
Back Forward
  • 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
Back Forward
javaexamples/threads/v1/Dispatcher.java (Fragment: dispatch)
 
Understanding the Defect (cont.)
Back Forward
  • 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
Back Forward
  • 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.)
Back Forward
  • 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.)
Back Forward

A Simple Example of Mutable State

javaexamples/threads/NonatomicInteger.java
 
Race Conditions (cont.)
Back Forward

Making the Mutable State Shared

javaexamples/threads/Counter.java
 
Race Conditions (cont.)
Back Forward

An Application that Illustrates the Defect

javaexamples/threads/CounterDriver.java
 
Synchronization with Monitors
Back Forward
  • 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
Back Forward
  • 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.)
Back Forward

Protecting the Shared Mutable State

javaexamples/threads/SynchronizedInteger.java
 
The Dispatching Example (cont.)
Back Forward

A Modification to the Dispatcher

javaexamples/threads/v5a/Dispatcher.java (Fragment: dispatch)
 
A Fault Still Exists
Back Forward
  • 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.)
Back Forward

Another Modification to the Dispatcher

javaexamples/threads/v5a/Dispatcher.java (Fragment: makeVehicleAvailable)
 
Liveness Defects
Back Forward
  • 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.)
Back Forward
  • 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.)
Back Forward
  • 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.)
Back Forward

The Modified Dispatcher

javaexamples/threads/v6a/Dispatcher.java
 
Memory Consistency
Back Forward
  • 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.)
Back Forward
  • 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
Back Forward
  • Coordination:
    • Alternatives to Monitors
  • Thread-Aware Objects:
    • Synchronized Collections
    • Concurrent Collections
    • Atomic Variables
  • Pools:
    • Executors and Thread Pools
    • Fork/Join Pools
Other Topics
Back Forward
  • Thread Confinement:
    • Stack Confinement
    • ThreadLocal java.lang.ThreadLocal
  • Building on Thread-Safe Classes:
    • Composing Thread-Safe Objects
    • Adding Functionality to Thread-Safe Classes
There's Always More to Learn
Back -