@Beta @ThreadSafe 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 -> LockBReadWriteLocks
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 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 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.