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
The map consists of two distinct sets of (key, value) pairs:
spaceis the compatibility space of a waiting transaction and
ActiveLockinstance on which the transaction is waiting
LockControlfor the first waiter in the queue behind
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
db.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 and Type||Method and Description|
Build an exception that describes a deadlock.
Look for a deadlock.
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
ReentrantLocks 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 factory
set- 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.
static StandardException buildException(AbstractPool factory, java.lang.Object data)
factory- the lock factory requesting the exception
data- an array with information about who's involved in a deadlock (as returned by
handle(com.splicemachine.db.impl.services.locks.AbstractPool, java.util.Stack, int, java.util.Dictionary, byte))