Class Deadlock
- java.lang.Object
-
- org.apache.derby.impl.services.locks.Deadlock
-
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, seegetWaiters(org.apache.derby.impl.services.locks.LockTable)
. The map consists of two distinct sets of (key, value) pairs:- (space, lock) pairs, where
space
is the compatibility space of a waiting transaction andlock
is theActiveLock
instance on which the transaction is waiting - (lock, prevLock) pairs, where
lock
is anActiveLock
andprevLock
is theActiveLock
orLockControl
for the first waiter in the queue behindlock
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.
- (space, lock) pairs, where
-
-
Constructor Summary
Constructors Modifier Constructor Description private
Deadlock()
-
Method Summary
All Methods Static Methods Concrete Methods Modifier and Type Method 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 aLockTable
.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.
-
-
-
Method Detail
-
look
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 aLockSet
object, the callers must be synchronized on theLockSet
object in order to satisfy the synchronization requirements ofLockSet.addWaiters()
. If it is aConcurrentLockSet
object, the callers must not hold any of theReentrantLock
s guarding the entries in the lock table, and the callers must make sure that only a single thread callslook()
at a time.- Parameters:
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.- Returns:
- The identifier to be used to open the conglomerate later.
- Throws:
StandardException
- Standard exception policy.
-
rollback
private static void rollback(java.util.Stack chain)
Backtrack in the depth-first search through the wait graph. Expect the top of the stack to hold the compatibility space we've just investigated. Pop the stack until the most recently examined granted lock has been removed.- Parameters:
chain
- the stack representing the state of the search
-
getWaiters
private static java.util.Hashtable getWaiters(LockTable set)
Get all the waiters in aLockTable
. 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.- Parameters:
set
- the lock table- Returns:
- all waiters in the lock table
- See Also:
LockControl.addWaiters(java.util.Map)
-
handle
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. Find out if the waiter that started looking for the deadlock is involved in it. If it isn't, pick a victim among the waiters that are involved.- Returns:
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 otherwise
-
buildException
static StandardException buildException(AbstractPool factory, java.lang.Object[] data)
Build an exception that describes a deadlock.- Parameters:
factory
- the lock factory requesting the exceptiondata
- an array with information about who's involved in a deadlock (as returned byhandle(org.apache.derby.impl.services.locks.AbstractPool, java.util.Stack, int, java.util.Dictionary, byte)
)- Returns:
- a deadlock exception
-
addInfo
private static void addInfo(java.lang.StringBuffer sb, java.lang.String desc, java.lang.Object data)
-
getContext
static Context getContext(java.lang.String contextID)
Privileged lookup of a Context. Must be package protected so that user code can't call this entry point.
-
-