@Beta @GwtIncompatible public class CycleDetectingLockFactory extends java.lang.Object
CycleDetectingLockFactory
creates ReentrantLock
instances and ReentrantReadWriteLock
instances 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:
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.
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 treats ReadWriteLock
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:
lock()
and unlock()
, a cycle detecting lock takes 38ns as
opposed to the 24ns taken by a plain lock.
As such, the CycleDetectingLockFactory may not be suitable for performance-critical applications which involve tightly-looped or deeply-nested locking algorithms.
Modifier and Type | Class and Description |
---|---|
private static interface |
CycleDetectingLockFactory.CycleDetectingLock
Internal Lock implementations implement the
CycleDetectingLock interface, allowing the
detection logic to treat all locks in the same manner. |
(package private) class |
CycleDetectingLockFactory.CycleDetectingReentrantLock |
private class |
CycleDetectingLockFactory.CycleDetectingReentrantReadLock |
(package private) class |
CycleDetectingLockFactory.CycleDetectingReentrantReadWriteLock |
private class |
CycleDetectingLockFactory.CycleDetectingReentrantWriteLock |
private static class |
CycleDetectingLockFactory.ExampleStackTrace
A Throwable used to record a stack trace that illustrates an example of a specific lock
acquisition ordering.
|
private static class |
CycleDetectingLockFactory.LockGraphNode
A
LockGraphNode associated with each lock instance keeps track of the directed edges in
the lock acquisition graph. |
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 java.lang.Enum<E>>
A
CycleDetectingLockFactory.WithExplicitOrdering provides the additional enforcement of
an application-specified ordering of lock acquisitions. |
Modifier and Type | Field and Description |
---|---|
private static java.lang.ThreadLocal<java.util.ArrayList<CycleDetectingLockFactory.LockGraphNode>> |
acquiredLocks
Tracks the currently acquired locks for each Thread, kept up to date by calls to
aboutToAcquire(CycleDetectingLock) and lockStateChanged(CycleDetectingLock) . |
private static java.util.concurrent.ConcurrentMap<java.lang.Class<? extends java.lang.Enum>,java.util.Map<? extends java.lang.Enum,CycleDetectingLockFactory.LockGraphNode>> |
lockGraphNodesPerType |
private static java.util.logging.Logger |
logger |
(package private) CycleDetectingLockFactory.Policy |
policy |
Modifier | Constructor and Description |
---|---|
private |
CycleDetectingLockFactory(CycleDetectingLockFactory.Policy policy) |
Modifier and Type | Method and Description |
---|---|
private void |
aboutToAcquire(CycleDetectingLockFactory.CycleDetectingLock lock)
CycleDetectingLock implementations must call this method before attempting to acquire the lock.
|
(package private) static <E extends java.lang.Enum<E>> |
createNodes(java.lang.Class<E> clazz)
For a given Enum type, creates an immutable map from each of the Enum's values to a
corresponding LockGraphNode, with the
allowedPriorLocks and disallowedPriorLocks prepopulated with nodes according to the natural ordering of the
associated Enum values. |
private static java.lang.String |
getLockName(java.lang.Enum<?> rank)
For the given Enum value
rank , returns the value's "EnumClass.name" , which is
used in exception and warning output. |
private static java.util.Map<? extends java.lang.Enum,CycleDetectingLockFactory.LockGraphNode> |
getOrCreateNodes(java.lang.Class<? extends java.lang.Enum> clazz) |
private static void |
lockStateChanged(CycleDetectingLockFactory.CycleDetectingLock lock)
CycleDetectingLock implementations must call this method in a
finally clause after any
attempt to change the lock state, including both lock and unlock attempts. |
static CycleDetectingLockFactory |
newInstance(CycleDetectingLockFactory.Policy policy)
Creates a new factory with the specified policy.
|
static <E extends java.lang.Enum<E>> |
newInstanceWithExplicitOrdering(java.lang.Class<E> enumClass,
CycleDetectingLockFactory.Policy policy)
Creates a
CycleDetectingLockFactory.WithExplicitOrdering<E> . |
java.util.concurrent.locks.ReentrantLock |
newReentrantLock(java.lang.String lockName)
Equivalent to
newReentrantLock(lockName, false) . |
java.util.concurrent.locks.ReentrantLock |
newReentrantLock(java.lang.String lockName,
boolean fair)
Creates a
ReentrantLock with the given fairness policy. |
java.util.concurrent.locks.ReentrantReadWriteLock |
newReentrantReadWriteLock(java.lang.String lockName)
Equivalent to
newReentrantReadWriteLock(lockName, false) . |
java.util.concurrent.locks.ReentrantReadWriteLock |
newReentrantReadWriteLock(java.lang.String lockName,
boolean fair)
Creates a
ReentrantReadWriteLock with the given fairness policy. |
private static final java.util.concurrent.ConcurrentMap<java.lang.Class<? extends java.lang.Enum>,java.util.Map<? extends java.lang.Enum,CycleDetectingLockFactory.LockGraphNode>> lockGraphNodesPerType
private static final java.util.logging.Logger logger
final CycleDetectingLockFactory.Policy policy
private static final java.lang.ThreadLocal<java.util.ArrayList<CycleDetectingLockFactory.LockGraphNode>> acquiredLocks
aboutToAcquire(CycleDetectingLock)
and lockStateChanged(CycleDetectingLock)
.private CycleDetectingLockFactory(CycleDetectingLockFactory.Policy policy)
public static CycleDetectingLockFactory newInstance(CycleDetectingLockFactory.Policy policy)
public java.util.concurrent.locks.ReentrantLock newReentrantLock(java.lang.String lockName)
newReentrantLock(lockName, false)
.public java.util.concurrent.locks.ReentrantLock newReentrantLock(java.lang.String lockName, boolean fair)
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.public java.util.concurrent.locks.ReentrantReadWriteLock newReentrantReadWriteLock(java.lang.String lockName)
newReentrantReadWriteLock(lockName, false)
.public java.util.concurrent.locks.ReentrantReadWriteLock newReentrantReadWriteLock(java.lang.String lockName, boolean fair)
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.public static <E extends java.lang.Enum<E>> CycleDetectingLockFactory.WithExplicitOrdering<E> newInstanceWithExplicitOrdering(java.lang.Class<E> enumClass, CycleDetectingLockFactory.Policy policy)
CycleDetectingLockFactory.WithExplicitOrdering<E>
.private static java.util.Map<? extends java.lang.Enum,CycleDetectingLockFactory.LockGraphNode> getOrCreateNodes(java.lang.Class<? extends java.lang.Enum> clazz)
static <E extends java.lang.Enum<E>> java.util.Map<E,CycleDetectingLockFactory.LockGraphNode> createNodes(java.lang.Class<E> clazz)
allowedPriorLocks
and disallowedPriorLocks
prepopulated with nodes according to the natural ordering of the
associated Enum values.private static java.lang.String getLockName(java.lang.Enum<?> rank)
rank
, returns the value's "EnumClass.name"
, which is
used in exception and warning output.private void aboutToAcquire(CycleDetectingLockFactory.CycleDetectingLock lock)
private static void lockStateChanged(CycleDetectingLockFactory.CycleDetectingLock lock)
finally
clause after any
attempt to change the lock state, including both lock and unlock attempts. Failure to do so can
result in corrupting the acquireLocks set.