Coordinating Threads

Coordinating Threads
without Monitors/Intrinsic Locks

Prof. David Bernstein
James Madison University

Computer Science Department

bernstdh@jmu.edu

Review

Multi-Threaded Programs:
- In some cases the threads are independent and don't require coordination
- In some cases objects have shared mutable state and threads must be coordinated
Synchronization:
- Methods and/or blocks can be synchronized easily using monitors/intrinsic locks but there are limitations

Overview

Purpose:
- Consider alternatives to monitors/intrinsic locks
Types of Alternatives:
- Explicit Locks
- Latches
- Joining
- Barriers
- Semaphores

Explicit Locks

Purpose:
- An alternative to monitors that provide some advanced capabilities
The Lock Interface:
- lock() - Acquire the lock when it is/becomes free
- lockInterruptibly() - Acquire the lock unless the current Thread is interrupted
- tryLock() - Acquire the lock only if it is free (perhaps within a given amount of time)
- unlock() - Free the lock
An Important Detail:
- Unlike monitors/intrinsic locks, all lock and unlock operations are explicit

Explicit Locks (cont.)

The ReentrantLock Class:
- Has the same mututal exclusion and memory-visibility guarantees as monitors
Advantages Over Monitors:
- It is possible to interrupt a Thread that is waiting to acquire a ReentrantLock
- Can be freed in a different block of code
- Allow for probabilistic deadlock avoidance (using tryLock())

Explicit Locks (cont.)

The ReentrantLock Idiom

Lock lock = new ReentrantLock(); // ... lock.lock(); try { // Update the mutable shared state } catch () // Handle possible exceptions { } finally { lock.unlock(); }

Explicit Locks (cont.)

Fairness Options for ReentrantLock Objects:
- Nonfair - threads requesting a lock can jump the queue if the lock is available when requested (called barging)
- Fair - threads acquire a fair lock in the order in which they requested it
Mechanics:
- Use the explicit value constructor
Tradeoffs:
- Enforcing fairness reduces performance

Explicit Locks (cont.)

A Limitation of ReentrantLock Objects:
- They only provide for mutual exclusion
When Does this Limitation Arise:
- In Reader-Writer problems, Writers must have exclusive access but Readers may share access
An Alternative:
- ReentrantReadWriteLock objects maintain two different Lock objects

Explicit Locks (cont.)

Fairness Options for ReentrantReadWriteLock Objects:
- Nonfair - the order of entry is unspecified
- Fair - when the currently held lock is freed either the longest-waiting writer thread will be given the lock or, if there is a group of reader threads waiting longer than all writer threads, that group will be given the lock
Other Properties:
- Both reader threads and writer threads can reacquire locks
- A writer can acquire the write lock, then acquire the read lock, and the release the write lock (a process known as downgrading from write to read)

Explicit Locks (cont.)

An Example

javaexamples/coordination/PresenceRecord.java

Explicit Locks (cont.)

Optimistic Locks:
- Are valid when acquired but don't prevent other threads from acquiring them so may not remain valid (and, hence, must be validated after accessing any shared mutable state)
A Class that Provides Optimistic Locking:
- StampedLock

Latches

Purpose:
- Delay the progress of a thread until it reaches its terminal state (from which it can't leave)
Examples of Use:
- Ensuring initialization has been completed
- Ensuring all necessary tasks have been completed
- Ensuring all necessary objects exist

Latches (cont.)

An Important Class:
- CountDownLatch
How It Is Used:
- Constructor - is passed an int named count
- await() - causes the calling current thread to enter the wait state until the count reaches 0 (or it is interrupted, or a given amount of time has elapsed)
- countDown() - decreases the count (releasing all waiting threads when the count reaches 0)
An Important Note:
- countDown() can be called from any thread (all that matters is the number of times it is called, not the number of different threads that call it)

Latches (cont.)

javaexamples/coordination/LatchExample.java

Joining a Thread

Purpose:
- Allow one thread of execution to wait for another to terminate
Important Methods:
- The join() methods in the Thread class

Joining a Thread (cont.)

The Runnable Used in the Example javaexamples/coordination/Averager.java

Joining a Thread (cont.)

An Example javaexamples/coordination/MultiThreadedMovingAverageExample.java

Barriers

Purpose:
- Allow a program to block until a group of threads reach a barrier point
Difference from Latches:
- Latches wait for actions/events while barriers wait for threads
Difference from Joining:
- join() waits for the thread to terminate; barriers can be used at any point

Barriers (cont.)

An Important Class:
- CyclicBarrier
What It Provides:
- Useful when a fixed-size group of threads must wait for each other
- Can be re-used after the waiting threads are released
How It Is Used:
- Constructor - is passed an int named parties and an optional Runnable named barrierAction (that will be executed in on of the threads)
- await() - causes the calling current thread to enter the wait state until the count reaches 0 (or it is interrupted, or a given amount of time has elapsed)
- getNumberWaiting() - returns the number of parties currently waiting at the barrier point
- isBroken() - returns true if a call to await() times-out or is interrupted
- reset() - resets the barrier to its initial state

Barriers (cont.)

Common Uses:
- Applications in which the work for some steps can be performed in parallel but in which all of the work one step must be completed before the next can be started
Other Variants:
- Exchanger which is a two-party barrier in which the two parties exchange data at the barrier point

Barriers (cont.)

A Decorator for Runnable Objects javaexamples/coordination/Barriered.java

Barriers (cont.)

An Example javaexamples/coordination/BarrierMovingAverageExample.java

Hybrids

An Important Class:
- Phaser
Capabilities:
- The number of parties can vary over time (using a registration/deregistration process)
- May be reused
- May be tiered
- May be monitored

Semaphores

Purpose:
- Control the number of activities that can access a resource or perform an action
Approach:
- Manages a set of permits (which can be acquired and released)

Semaphores (cont.)

An Important Class:
- Semaphore
How It Is Used:
- Constructor - is passed an int named permits
- acquire() - acquire a permit, blocking until one is available (otr the thread is interrupted)
- release() - releases a permit

Semaphores (cont.)

Fairness:
- When fairness is enabled, threads invoking any of the acquire() methods are given permits on a first-in-first-out basis
When To Impose Fairness:
- When the need to avoid starvation outweights the performance costs

The Happens-Before Relationship

Lock, Semaphore, CountDownLatch:
- Actions prior to "release" methods happen-before actions subsequent to a successful "acquisition" method
CyclicBarrier, Phaser:
- Actions prior to calling "await" methods happen-before actions performed by the "barrier" action
- Actions performed by the "barrier" action happen-before actions subsequent to a successful return from the corresponding "await"

There's Always More to Learn