Class CycleDetectingLockFactory
- java.lang.Object
-
- com.google.common.util.concurrent.CycleDetectingLockFactory
-
- Direct Known Subclasses:
CycleDetectingLockFactory.WithExplicitOrdering
@GwtIncompatible public class CycleDetectingLockFactory extends java.lang.Object
TheCycleDetectingLockFactory
createsReentrantLock
instances andReentrantReadWriteLock
instances that detect potential deadlock by checking for cycles in lock acquisition order.Potential deadlocks detected when calling the
lock()
,lockInterruptibly()
, ortryLock()
methods will result in the execution of theCycleDetectingLockFactory.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 withPolicy.DISABLED
). A lock's behavior when a cycle is detected, however, is defined by thePolicy
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
ReadWriteLock
instances have different properties and can form cycles without potential deadlock, this class treatsReadWriteLock
instances 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()
andunlock()
, 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
Nested Classes Modifier and Type Class Description static class
CycleDetectingLockFactory.Policies
Pre-definedCycleDetectingLockFactory.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 java.lang.Enum<E>>
ACycleDetectingLockFactory.WithExplicitOrdering
provides the additional enforcement of an application-specified ordering of lock acquisitions.
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description static CycleDetectingLockFactory
newInstance(CycleDetectingLockFactory.Policy policy)
Creates a new factory with the specified policy.static <E extends java.lang.Enum<E>>
CycleDetectingLockFactory.WithExplicitOrdering<E>newInstanceWithExplicitOrdering(java.lang.Class<E> enumClass, CycleDetectingLockFactory.Policy policy)
Creates aCycleDetectingLockFactory.WithExplicitOrdering<E>
.java.util.concurrent.locks.ReentrantLock
newReentrantLock(java.lang.String lockName)
Equivalent tonewReentrantLock(lockName, false)
.java.util.concurrent.locks.ReentrantLock
newReentrantLock(java.lang.String lockName, boolean fair)
Creates aReentrantLock
with the given fairness policy.java.util.concurrent.locks.ReentrantReadWriteLock
newReentrantReadWriteLock(java.lang.String lockName)
Equivalent tonewReentrantReadWriteLock(lockName, false)
.java.util.concurrent.locks.ReentrantReadWriteLock
newReentrantReadWriteLock(java.lang.String lockName, boolean fair)
Creates aReentrantReadWriteLock
with the given fairness policy.
-
-
-
Method Detail
-
newInstance
public static CycleDetectingLockFactory newInstance(CycleDetectingLockFactory.Policy policy)
Creates a new factory with the specified policy.
-
newReentrantLock
public java.util.concurrent.locks.ReentrantLock newReentrantLock(java.lang.String lockName)
Equivalent tonewReentrantLock(lockName, false)
.
-
newReentrantLock
public java.util.concurrent.locks.ReentrantLock newReentrantLock(java.lang.String lockName, boolean fair)
Creates aReentrantLock
with the given fairness policy. ThelockName
is used in the warning or exception output to help identify the locks involved in the detected deadlock.
-
newReentrantReadWriteLock
public java.util.concurrent.locks.ReentrantReadWriteLock newReentrantReadWriteLock(java.lang.String lockName)
Equivalent tonewReentrantReadWriteLock(lockName, false)
.
-
newReentrantReadWriteLock
public java.util.concurrent.locks.ReentrantReadWriteLock newReentrantReadWriteLock(java.lang.String lockName, boolean fair)
Creates aReentrantReadWriteLock
with the given fairness policy. ThelockName
is used in the warning or exception output to help identify the locks involved in the detected deadlock.
-
newInstanceWithExplicitOrdering
public static <E extends java.lang.Enum<E>> CycleDetectingLockFactory.WithExplicitOrdering<E> newInstanceWithExplicitOrdering(java.lang.Class<E> enumClass, CycleDetectingLockFactory.Policy policy)
Creates aCycleDetectingLockFactory.WithExplicitOrdering<E>
.
-
-