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.
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.
| Access | Constructor and Description |
|---|---|
| private |
| Modifier and Type | Method and Description |
|---|---|
| private static void | |
| pack-priv static StandardException | Returns: a deadlock exceptionthe lock factory requesting the exception factory, Object[] an array with information about who's involved in
a deadlock (as returned by data)handle)Build an exception that describes a deadlock. |
| pack-priv static Context | getContext(final String contextID)
Must be package protected so that user code can't call this entry point. |
| private static Hashtable | Returns: all waiters in the lock tablethe lock table set)Get all the waiters in a |
| private static Object[] | 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 otherwiseHandle a deadlock when it has been detected. |
| pack-priv static Object[] | Returns: The identifier to be used to open the conglomerate later.The locking system factory factory, LockTable The complete lock table. A lock table is a hash
table keyed by a Lockable and with a LockControl as
the data element. set, LockControl 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. control, ActiveLock represents the specific waiting lock request that
the caller has been waiting on, before just being
woken up to do this search. startingLock, byte Either Constants.WAITING_LOCK_IN_WAIT, or
Constants.WAITING_LOCK_DEADLOCK. deadlockWake)Look for a deadlock. |
| private static void |
| Deadlock | back to summary |
|---|---|
| private Deadlock() | |
| addInfo | back to summary |
|---|---|
| private static void addInfo(StringBuffer sb, String desc, Object data) | |
| buildException | back to summary |
|---|---|
| pack-priv static StandardException buildException(AbstractPool factory, Object[] data) Build an exception that describes a deadlock.
| |
| getContext | back to summary |
|---|---|
| pack-priv static Context getContext(final String contextID) Must be package protected so that user code can't call this entry point. | |
| getWaiters | back to summary |
|---|---|
| private static Hashtable Get all the waiters in a
| |
| handle | back to summary |
|---|---|
| private static Object[] handle(AbstractPool factory, Stack<E> chain, int start, Dictionary<K, V> 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.
| |
| look | back to summary |
|---|---|
| pack-priv static 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
| |
| rollback | back to summary |
|---|---|
| private static void rollback(Stack<E> 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.
| |