com.google.common.util.concurrent
Class CycleDetectingLockFactory

java.lang.Object
  com.google.common.util.concurrent.CycleDetectingLockFactory

Direct Known Subclasses:

CycleDetectingLockFactory.WithExplicitOrdering

@Beta
@ThreadSafe
public class CycleDetectingLockFactory
extends Object

The CycleDetectingLockFactory creates ReentrantLocks and ReentrantReadWriteLocks that detect potential deadlock by checking for cycles in lock acquisition order.

Potential deadlocks detected when calling the lock(), lockInterruptibly(), or tryLock() methods will result in the execution of the CycleDetectingLockFactory.Policy specified when creating the factory. The currently available policies are:

• DISABLED
• WARN
• THROW

The locks created by a factory instance will detect lock acquisition cycles with locks created by other CycleDetectingLockFactory instances (except those with Policy.DISABLED). A lock's behavior when a cycle is detected, however, is defined by the Policy of the factory that created it. This allows detection of cycles across components while delegating control over lock behavior to individual components.

Applications are encouraged to use a CycleDetectingLockFactory to create any locks for which external/unmanaged code is executed while the lock is held. (See caveats under Performance).

Cycle Detection

Deadlocks can arise when locks are acquired in an order that forms a cycle. In a simple example involving two locks and two threads, deadlock occurs when one thread acquires Lock A, and then Lock B, while another thread acquires Lock B, and then Lock A:

 Thread1: acquire(LockA) --X acquire(LockB)
 Thread2: acquire(LockB) --X acquire(LockA)
 

Neither thread will progress because each is waiting for the other. In more complex applications, cycles can arise from interactions among more than 2 locks:

 Thread1: acquire(LockA) --X acquire(LockB)
 Thread2: acquire(LockB) --X acquire(LockC)
 ...
 ThreadN: acquire(LockN) --X acquire(LockA)
 

The implementation detects cycles by constructing a directed graph in which each lock represents a node and each edge represents an acquisition ordering between two locks.

• Each lock adds (and removes) itself to/from a ThreadLocal Set of acquired locks when the Thread acquires its first hold (and releases its last remaining hold).
• Before the lock is acquired, the lock is checked against the current set of acquired locks---to each of the acquired locks, an edge from the soon-to-be-acquired lock is either verified or created.
• If a new edge needs to be created, the outgoing edges of the acquired locks are traversed to check for a cycle that reaches the lock to be acquired. If no cycle is detected, a new "safe" edge is created.
• If a cycle is detected, an "unsafe" (cyclic) edge is created to represent a potential deadlock situation, and the appropriate Policy is executed.

Note that detection of potential deadlock does not necessarily indicate that deadlock will happen, as it is possible that higher level application logic prevents the cyclic lock acquisition from occurring. One example of a false positive is:

 LockA -> LockB -> LockC
 LockA -> LockC -> LockB
 

ReadWriteLocks

While ReadWriteLocks have different properties and can form cycles without potential deadlock, this class treats ReadWriteLocks as equivalent to traditional exclusive locks. Although this increases the false positives that the locks detect (i.e. cycles that will not actually result in deadlock), it simplifies the algorithm and implementation considerably. The assumption is that a user of this factory wishes to eliminate any cyclic acquisition ordering.

Explicit Lock Acquisition Ordering

The CycleDetectingLockFactory.WithExplicitOrdering class can be used to enforce an application-specific ordering in addition to performing general cycle detection.

Garbage Collection

In order to allow proper garbage collection of unused locks, the edges of the lock graph are weak references.

Performance

The extra bookkeeping done by cycle detecting locks comes at some cost to performance. Benchmarks (as of December 2011) show that:

• for an unnested lock() and unlock(), a cycle detecting lock takes 38ns as opposed to the 24ns taken by a plain lock.
• for nested locking, the cost increases with the depth of the nesting:
  • 2 levels: average of 64ns per lock()/unlock()
  • 3 levels: average of 77ns per lock()/unlock()
  • 4 levels: average of 99ns per lock()/unlock()
  • 5 levels: average of 103ns per lock()/unlock()
  • 10 levels: average of 184ns per lock()/unlock()
  • 20 levels: average of 393ns per lock()/unlock()

As such, the CycleDetectingLockFactory may not be suitable for performance-critical applications which involve tightly-looped or deeply-nested locking algorithms.

Since:

13.0

Author:

Darick Tong

Nested Class Summary

static class	CycleDetectingLockFactory.Policies Pre-defined CycleDetectingLockFactory.Policy implementations.
static interface	CycleDetectingLockFactory.Policy Encapsulates the action to be taken when a potential deadlock is encountered.
static class	CycleDetectingLockFactory.PotentialDeadlockException Represents a detected cycle in lock acquisition ordering.
static class	CycleDetectingLockFactory.WithExplicitOrdering<E extends Enum<E>> A CycleDetectingLockFactory.WithExplicitOrdering provides the additional enforcement of an application-specified ordering of lock acquisitions.

Method Summary

static CycleDetectingLockFactory	newInstance(CycleDetectingLockFactory.Policy policy) Creates a new factory with the specified policy.
static <E extends Enum<E>> CycleDetectingLockFactory.WithExplicitOrdering<E>	newInstanceWithExplicitOrdering(Class<E> enumClass, CycleDetectingLockFactory.Policy policy) Creates a CycleDetectingLockFactory.WithExplicitOrdering<E>.
ReentrantLock	newReentrantLock(String lockName) Equivalent to newReentrantLock(lockName, false).
ReentrantLock	newReentrantLock(String lockName, boolean fair) Creates a ReentrantLock with the given fairness policy.
ReentrantReadWriteLock	newReentrantReadWriteLock(String lockName) Equivalent to newReentrantReadWriteLock(lockName, false).
ReentrantReadWriteLock	newReentrantReadWriteLock(String lockName, boolean fair) Creates a ReentrantReadWriteLock with the given fairness policy.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Method Detail

newInstance

public static CycleDetectingLockFactory newInstance(CycleDetectingLockFactory.Policy policy)

Creates a new factory with the specified policy.

newReentrantLock

public ReentrantLock newReentrantLock(String lockName)

Equivalent to newReentrantLock(lockName, false).

newReentrantLock

public ReentrantLock newReentrantLock(String lockName,
                                      boolean fair)

Creates a ReentrantLock with the given fairness policy. The lockName is used in the warning or exception output to help identify the locks involved in the detected deadlock.

newReentrantReadWriteLock

public ReentrantReadWriteLock newReentrantReadWriteLock(String lockName)

Equivalent to newReentrantReadWriteLock(lockName, false).

newReentrantReadWriteLock

public ReentrantReadWriteLock newReentrantReadWriteLock(String lockName,
                                                        boolean fair)

Creates a ReentrantReadWriteLock with the given fairness policy. The lockName is used in the warning or exception output to help identify the locks involved in the detected deadlock.

newInstanceWithExplicitOrdering

public static <E extends Enum<E>> CycleDetectingLockFactory.WithExplicitOrdering<E> newInstanceWithExplicitOrdering(Class<E> enumClass,
                                                                                                                    CycleDetectingLockFactory.Policy policy)

Creates a CycleDetectingLockFactory.WithExplicitOrdering<E>.