|
|||||||||
| Home >> All >> org >> eclipse >> core >> internal >> [ jobs overview ] | PREV CLASS NEXT CLASS | ||||||||
SUMMARY:  JAVADOC |  SOURCE |  DOWNLOAD | NESTED | FIELD | CONSTR | METHOD |
DETAIL: FIELD | CONSTR | METHOD | ||||||||
org.eclipse.core.internal.jobs
Class DeadlockDetector
java.lang.Objectorg.eclipse.core.internal.jobs.DeadlockDetector
- class DeadlockDetector
- extends java.lang.Object
Stores all the relationships between locks (rules are also considered locks), and the threads that own them. All the relationships are stored in a 2D integer array. The rows in the array are threads, while the columns are locks. Two corresponding arrayLists store the actual threads and locks. The index of a thread in the first arrayList is the index of the row in the graph. The index of a lock in the second arrayList is the index of the column in the graph. An entry greater than 0 in the graph is the number of times a thread in the entry's row acquired the lock in the entry's column. An entry of -1 means that the thread is waiting to acquire the lock. An enry of 0 means that the thread and the lock have no relationship. The difference between rules and locks is that locks can be suspended, while rules are implicit locks and as such cannot be suspended. To resolve deadlock, the graph will first try to find a thread that only owns locks. Failing that, it will find a thread in the deadlock that owns at least one lock and suspend it. Deadlock can only occur among locks, or among locks in combination with rules. Deadlock among rules only is impossible. Therefore, in any deadlock one can always find a thread that owns at least one lock that can be suspended. The implementation of the graph assumes that a thread can only own 1 rule at any one time. It can acquire that rule several times, but a thread cannot acquire 2 non-conflicting rules at the same time. The implementation of the graph will sometimes also find and resolve bogus deadlocks. graph: assuming this rule hierarchy: R2 R3 L1 R1 J1 1 0 0 / \ J2 0 1 -1 R2 R3 J3 -1 0 1 If in the above situation job4 decides to acquire rule1, then the graph will transform to the following: R2 R3 R1 L1 J1 1 0 1 0 J2 1 1 1 -1 J3 -1 0 0 1 J4 0 0 -1 0 and the graph will assume that job2 and job3 are deadlocked and suspend lock1 of job3. The reason the deadlock is bogus is that the deadlock is unlikely to actually happen (the threads are currently not deadlocked, but might deadlock later on when it is too late to detect it) Therefore, in order to make sure that no deadlock is possible, the deadlock will still be resolved at this point.
| Field Summary | |
private static int[][] |
EMPTY_MATRIX
|
private int[][] |
graph
|
private java.util.ArrayList |
locks
|
private java.util.ArrayList |
lockThreads
|
private static int |
NO_STATE
|
private boolean |
resize
|
private static int |
WAITING_FOR_LOCK
|
| Constructor Summary | |
(package private) |
DeadlockDetector()
|
| Method Summary | |
private boolean |
addCycleThreads(java.util.ArrayList deadlockedThreads,
java.lang.Thread next)
Recursively check if any of the threads that prevent the current thread from running are actually deadlocked with the current thread. |
private java.lang.Thread[] |
blockingThreads(java.lang.Thread current)
Get the thread(s) that own the lock this thread is waiting for. |
private boolean |
checkWaitCycles(int[] waitingThreads,
int lockIndex)
Check that the addition of a waiting thread did not produce deadlock. |
(package private) boolean |
contains(java.lang.Thread t)
Returns true IFF the matrix contains a row for the given thread. |
private void |
fillPresentEntries(org.eclipse.core.runtime.jobs.ISchedulingRule newLock,
int lockIndex)
A new rule was just added to the graph. |
private java.lang.Object[] |
getOwnedLocks(java.lang.Thread current)
Returns all the locks owned by the given thread |
private java.lang.Thread[] |
getThreadsInDeadlock(java.lang.Thread cause)
Returns an array of threads that form the deadlock (usually 2). |
private java.lang.Thread[] |
getThreadsOwningLock(org.eclipse.core.runtime.jobs.ISchedulingRule rule)
Returns the thread(s) that own the given lock. |
private java.lang.Object |
getWaitingLock(java.lang.Thread current)
Returns the lock the given thread is waiting for. |
private int |
indexOf(org.eclipse.core.runtime.jobs.ISchedulingRule lock,
boolean add)
Returns the index of the given lock in the lock array. |
private int |
indexOf(java.lang.Thread owner,
boolean add)
Returns the index of the given thread in the thread array. |
(package private) boolean |
isEmpty()
Returns true IFF the adjacency matrix is empty. |
(package private) void |
lockAcquired(java.lang.Thread owner,
org.eclipse.core.runtime.jobs.ISchedulingRule lock)
The given lock was aquired by the given thread. |
(package private) void |
lockReleased(java.lang.Thread owner,
org.eclipse.core.runtime.jobs.ISchedulingRule lock)
The given lock was released by the given thread. |
(package private) void |
lockReleasedCompletely(java.lang.Thread owner,
org.eclipse.core.runtime.jobs.ISchedulingRule rule)
The given scheduling rule is no longer used because the job that invoked it is done. |
(package private) Deadlock |
lockWaitStart(java.lang.Thread client,
org.eclipse.core.runtime.jobs.ISchedulingRule lock)
The given thread could not get the given lock and is waiting for it. |
(package private) void |
lockWaitStop(java.lang.Thread owner,
org.eclipse.core.runtime.jobs.ISchedulingRule lock)
The given thread has stopped waiting for the given lock. |
private boolean |
ownsLocks(java.lang.Thread cause)
Returns true IFF the given thread owns a single lock |
private boolean |
ownsRealLocks(java.lang.Thread owner)
Returns true IFF the given thread owns a single real lock. |
private boolean |
ownsRuleLocks(java.lang.Thread owner)
Return true IFF this thread owns rule locks (ie. |
private org.eclipse.core.runtime.jobs.ISchedulingRule[] |
realLocksForThread(java.lang.Thread owner)
Returns an array of real locks that are owned by the given thread. |
private void |
reduceGraph(int row,
org.eclipse.core.runtime.jobs.ISchedulingRule lock)
The matrix has been simplified. |
private void |
reportDeadlock(Deadlock deadlock)
Adds a 'deadlock detected' message to the log with a stack trace. |
private void |
resizeGraph()
The number of threads/locks in the graph has changed. |
private java.lang.Thread |
resolutionCandidate(java.lang.Thread[] candidates)
Get the thread whose locks can be suspended. |
private void |
setToWait(java.lang.Thread owner,
org.eclipse.core.runtime.jobs.ISchedulingRule lock,
boolean suspend)
The given thread is waiting for the given lock. |
void |
toDebugString()
Prints out the current matrix to standard output. |
| Methods inherited from class java.lang.Object |
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
| Field Detail |
NO_STATE
private static int NO_STATE
WAITING_FOR_LOCK
private static int WAITING_FOR_LOCK
EMPTY_MATRIX
private static final int[][] EMPTY_MATRIX
graph
private int[][] graph
locks
private final java.util.ArrayList locks
lockThreads
private final java.util.ArrayList lockThreads
resize
private boolean resize
| Constructor Detail |
DeadlockDetector
DeadlockDetector()
| Method Detail |
addCycleThreads
private boolean addCycleThreads(java.util.ArrayList deadlockedThreads, java.lang.Thread next)
- Recursively check if any of the threads that prevent the current thread from running
are actually deadlocked with the current thread.
Add the threads that form deadlock to the deadlockedThreads list.
blockingThreads
private java.lang.Thread[] blockingThreads(java.lang.Thread current)
- Get the thread(s) that own the lock this thread is waiting for.
checkWaitCycles
private boolean checkWaitCycles(int[] waitingThreads,
int lockIndex)
- Check that the addition of a waiting thread did not produce deadlock.
If deadlock is detected return true, else return false.
contains
boolean contains(java.lang.Thread t)
- Returns true IFF the matrix contains a row for the given thread.
(meaning the given thread either owns locks or is waiting for locks)
fillPresentEntries
private void fillPresentEntries(org.eclipse.core.runtime.jobs.ISchedulingRule newLock, int lockIndex)
- A new rule was just added to the graph.
Find a rule it conflicts with and update the new rule with the number of times
it was acquired implicitly when threads acquired conflicting rule.
getOwnedLocks
private java.lang.Object[] getOwnedLocks(java.lang.Thread current)
- Returns all the locks owned by the given thread
getThreadsInDeadlock
private java.lang.Thread[] getThreadsInDeadlock(java.lang.Thread cause)
- Returns an array of threads that form the deadlock (usually 2).
getThreadsOwningLock
private java.lang.Thread[] getThreadsOwningLock(org.eclipse.core.runtime.jobs.ISchedulingRule rule)
- Returns the thread(s) that own the given lock.
getWaitingLock
private java.lang.Object getWaitingLock(java.lang.Thread current)
- Returns the lock the given thread is waiting for.
indexOf
private int indexOf(org.eclipse.core.runtime.jobs.ISchedulingRule lock, boolean add)
- Returns the index of the given lock in the lock array. If the lock is
not present in the array, it is added to the end.
indexOf
private int indexOf(java.lang.Thread owner, boolean add)
- Returns the index of the given thread in the thread array. If the thread
is not present in the array, it is added to the end.
isEmpty
boolean isEmpty()
- Returns true IFF the adjacency matrix is empty.
lockAcquired
void lockAcquired(java.lang.Thread owner, org.eclipse.core.runtime.jobs.ISchedulingRule lock)
- The given lock was aquired by the given thread.
lockReleased
void lockReleased(java.lang.Thread owner, org.eclipse.core.runtime.jobs.ISchedulingRule lock)
- The given lock was released by the given thread. Update the graph.
lockReleasedCompletely
void lockReleasedCompletely(java.lang.Thread owner, org.eclipse.core.runtime.jobs.ISchedulingRule rule)
- The given scheduling rule is no longer used because the job that invoked it is done.
Release this rule regardless of how many times it was acquired.
lockWaitStart
Deadlock lockWaitStart(java.lang.Thread client, org.eclipse.core.runtime.jobs.ISchedulingRule lock)
- The given thread could not get the given lock and is waiting for it.
Update the graph.
lockWaitStop
void lockWaitStop(java.lang.Thread owner, org.eclipse.core.runtime.jobs.ISchedulingRule lock)
- The given thread has stopped waiting for the given lock.
Update the graph.
ownsLocks
private boolean ownsLocks(java.lang.Thread cause)
- Returns true IFF the given thread owns a single lock
ownsRealLocks
private boolean ownsRealLocks(java.lang.Thread owner)
- Returns true IFF the given thread owns a single real lock.
A real lock is a lock that can be suspended.
ownsRuleLocks
private boolean ownsRuleLocks(java.lang.Thread owner)
- Return true IFF this thread owns rule locks (ie. implicit locks which
cannot be suspended)
realLocksForThread
private org.eclipse.core.runtime.jobs.ISchedulingRule[] realLocksForThread(java.lang.Thread owner)
- Returns an array of real locks that are owned by the given thread.
Real locks are locks that implement the ILock interface and can be suspended.
reduceGraph
private void reduceGraph(int row,
org.eclipse.core.runtime.jobs.ISchedulingRule lock)
- The matrix has been simplified. Check if any unnecessary rows or columns
can be removed.
reportDeadlock
private void reportDeadlock(Deadlock deadlock)
- Adds a 'deadlock detected' message to the log with a stack trace.
resizeGraph
private void resizeGraph()
- The number of threads/locks in the graph has changed. Update the
underlying matrix.
resolutionCandidate
private java.lang.Thread resolutionCandidate(java.lang.Thread[] candidates)
- Get the thread whose locks can be suspended. (ie. all locks it owns are
actual locks and not rules). Return the first thread in the array by default.
setToWait
private void setToWait(java.lang.Thread owner, org.eclipse.core.runtime.jobs.ISchedulingRule lock, boolean suspend)
- The given thread is waiting for the given lock. Update the graph.
toDebugString
public void toDebugString()
- Prints out the current matrix to standard output.
Only used for debugging.
|
|||||||||
| Home >> All >> org >> eclipse >> core >> internal >> [ jobs overview ] | PREV CLASS NEXT CLASS | ||||||||
|
SUMMARY: JAVADOC | SOURCE | DOWNLOAD | NESTED | FIELD | CONSTR | METHOD |
DETAIL: FIELD | CONSTR | METHOD | ||||||||