- Forward


Coordinating Threads
without Monitors/Intrinsic Locks


Prof. David Bernstein
James Madison University

Computer Science Department
bernstdh@jmu.edu

Print

Review
Back SMYC Forward
  • 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
Back SMYC Forward
  • Purpose:
    • Consider alternatives to monitors/intrinsic locks
  • Types of Alternatives:
    • Explicit Locks
    • Latches
    • Joining
    • Barriers
    • Semaphores
Explicit Locks
Back SMYC Forward
  • 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.)
Back SMYC Forward
  • 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.)
Back SMYC Forward

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.)
Back SMYC Forward
  • 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.)
Back SMYC Forward
  • 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.)
Back SMYC Forward
  • 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.)
Back SMYC Forward

An Example

javaexamples/coordination/PresenceRecord.java
 
Explicit Locks (cont.)
Back SMYC Forward
  • 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
Back SMYC Forward
  • 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.)
Back SMYC Forward
  • 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.)
Back SMYC Forward
javaexamples/coordination/LatchExample.java
 
Joining a Thread
Back SMYC Forward
  • 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.)
Back SMYC Forward
The Runnable Used in the Example
javaexamples/coordination/Averager.java
 
Joining a Thread (cont.)
Back SMYC Forward
An Example
javaexamples/coordination/MultiThreadedMovingAverageExample.java
 
Barriers
Back SMYC Forward
  • 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.)
Back SMYC Forward
  • 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.)
Back SMYC Forward
  • 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.)
Back SMYC Forward
A Decorator for Runnable Objects
javaexamples/coordination/Barriered.java
 
Barriers (cont.)
Back SMYC Forward
An Example
javaexamples/coordination/BarrierMovingAverageExample.java
 
Hybrids
Back SMYC Forward
  • 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
Back SMYC Forward
  • 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.)
Back SMYC Forward
  • 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.)
Back SMYC Forward
  • 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
Back SMYC Forward
  • 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
Back -