class Deadlock
extends java.lang.Object
Code to support deadlock detection.
This class implements deadlock detection by searching for cycles in the wait graph. If a cycle is found, it means that (at least) two transactions are blocked by each other, and one of them must be aborted to allow the other one to continue.
The wait graph is obtained by asking the LockSet
instance to
provide a map representing all wait relations, see getWaiters(org.apache.derby.impl.services.locks.LockTable)
.
The map consists of two distinct sets of (key, value) pairs:
space
is the compatibility space
of a waiting transaction and lock
is the ActiveLock
instance on which the transaction is waitinglock
is an ActiveLock
and
prevLock
is the ActiveLock
or LockControl
for the
first waiter in the queue behind lock
The search is performed as a depth-first search starting from the lock
request of a waiter that has been awoken for deadlock detection (either
because derby.locks.deadlockTimeout
has expired or because some
other waiter had picked it as a victim in order to break a deadlock).
From this lock request, the wait graph is traversed by checking which
transactions have already been granted a lock on the object, and who they
are waiting for.
The state of the search is maintained by pushing compatibility spaces (representing waiting transactions) and granted locks onto a stack. When a dead end is found (that is, a transaction that holds locks without waiting for any other transaction), the stack is popped and the search continues down a different path. This continues until a cycle is found or the stack is empty. Detection of cycles happens when pushing a new compatibility space onto the stack. If the same space already exists on the stack, it means the graph has a cycle and we have a deadlock.
When a deadlock is found, one of the waiters in the deadlock cycle is awoken and it will terminate itself, unless it finds that the deadlock has been broken in the meantime, for example because one of the involved waiters has timed out.
Modifier | Constructor and Description |
---|---|
private |
Deadlock() |
Modifier and Type | Method and Description |
---|---|
private static void |
addInfo(java.lang.StringBuffer sb,
java.lang.String desc,
java.lang.Object data) |
(package private) static StandardException |
buildException(AbstractPool factory,
java.lang.Object[] data)
Build an exception that describes a deadlock.
|
(package private) static Context |
getContext(java.lang.String contextID)
Privileged lookup of a Context.
|
private static java.util.Hashtable |
getWaiters(LockTable set)
Get all the waiters in a
LockTable . |
private static java.lang.Object[] |
handle(AbstractPool factory,
java.util.Stack chain,
int start,
java.util.Dictionary waiters,
byte deadlockWake)
Handle a deadlock when it has been detected.
|
(package private) static java.lang.Object[] |
look(AbstractPool factory,
LockTable set,
LockControl control,
ActiveLock startingLock,
byte deadlockWake)
Look for a deadlock.
|
private static void |
rollback(java.util.Stack chain)
Backtrack in the depth-first search through the wait graph.
|
static java.lang.Object[] look(AbstractPool factory, LockTable set, LockControl control, ActiveLock startingLock, byte deadlockWake)
Look for a deadlock.
Walk through the graph of all locks and search for cycles among the waiting lock requests which would indicate a deadlock. A simple deadlock cycle is where the granted locks of waiting compatibility space A is blocking compatibility space B and space B holds locks causing space A to wait.
MT - if the LockTable
is a LockSet
object, the
callers must be synchronized on the LockSet
object in order
to satisfy the synchronization requirements of
LockSet.addWaiters()
. If it is a
ConcurrentLockSet
object, the callers must not hold any of
the ReentrantLock
s guarding the entries in the lock table,
and the callers must make sure that only a single thread calls
look()
at a time.
factory
- The locking system factoryset
- The complete lock table. A lock table is a hash
table keyed by a Lockable and with a LockControl as
the data element.control
- A LockControl contains a reference to the item being
locked and doubly linked lists for the granted locks
and the waiting locks. The passed in value is the
lock that the caller was waiting on when woken up
to do the deadlock check.startingLock
- represents the specific waiting lock request that
the caller has been waiting on, before just being
woken up to do this search.deadlockWake
- Either Constants.WAITING_LOCK_IN_WAIT, or
Constants.WAITING_LOCK_DEADLOCK.StandardException
- Standard exception policy.private static void rollback(java.util.Stack chain)
chain
- the stack representing the state of the searchprivate static java.util.Hashtable getWaiters(LockTable set)
LockTable
. The waiters are returned
as pairs (space, lock) mapping waiting compatibility spaces to the
lock request in which they are blocked, and (lock, prevLock) linking
a lock request with the lock request that's behind it in the queue of
waiters.set
- the lock tableLockControl.addWaiters(java.util.Map)
private static java.lang.Object[] handle(AbstractPool factory, java.util.Stack chain, int start, java.util.Dictionary waiters, byte deadlockWake)
null
if the waiter that started looking for the deadlock
isn't involved in the deadlock (in which case another victim will have
been picked and awoken), or an array describing the deadlock otherwisestatic StandardException buildException(AbstractPool factory, java.lang.Object[] data)
factory
- the lock factory requesting the exceptiondata
- an array with information about who's involved in
a deadlock (as returned by handle(org.apache.derby.impl.services.locks.AbstractPool, java.util.Stack, int, java.util.Dictionary, byte)
)private static void addInfo(java.lang.StringBuffer sb, java.lang.String desc, java.lang.Object data)
static Context getContext(java.lang.String contextID)
Apache Derby V10.13 Internals - Copyright © 2004,2016 The Apache Software Foundation. All Rights Reserved.