Java > Open Source Codes > org > eclipse > core > internal > jobs > DeadlockDetector


1 /*******************************************************************************
2  * Copyright (c) 2003, 2006 IBM Corporation and others.
3  * All rights reserved. This program and the accompanying materials
4  * are made available under the terms of the Eclipse Public License v1.0
5  * which accompanies this distribution, and is available at
6  * http://www.eclipse.org/legal/epl-v10.html
7  *
8  * Contributors:
9  * IBM Corporation - initial API and implementation
10  *******************************************************************************/
11 package org.eclipse.core.internal.jobs;
12
13 import java.io.PrintWriter ;
14 import java.io.StringWriter ;
15 import java.util.ArrayList ;
16 import org.eclipse.core.internal.runtime.RuntimeLog;
17 import org.eclipse.core.runtime.*;
18 import org.eclipse.core.runtime.jobs.ILock;
19 import org.eclipse.core.runtime.jobs.ISchedulingRule;
20
21 /**
22  * Stores all the relationships between locks (rules are also considered locks),
23  * and the threads that own them. All the relationships are stored in a 2D integer array.
24  * The rows in the array are threads, while the columns are locks.
25  * Two corresponding arrayLists store the actual threads and locks.
26  * The index of a thread in the first arrayList is the index of the row in the graph.
27  * The index of a lock in the second arrayList is the index of the column in the graph.
28  * An entry greater than 0 in the graph is the number of times a thread in the entry's row
29  * acquired the lock in the entry's column.
30  * An entry of -1 means that the thread is waiting to acquire the lock.
31  * An entry of 0 means that the thread and the lock have no relationship.
32  *
33  * The difference between rules and locks is that locks can be suspended, while
34  * rules are implicit locks and as such cannot be suspended.
35  * To resolve deadlock, the graph will first try to find a thread that only owns
36  * locks. Failing that, it will find a thread in the deadlock that owns at least
37  * one lock and suspend it.
38  *
39  * Deadlock can only occur among locks, or among locks in combination with rules.
40  * Deadlock among rules only is impossible. Therefore, in any deadlock one can always
41  * find a thread that owns at least one lock that can be suspended.
42  *
43  * The implementation of the graph assumes that a thread can only own 1 rule at
44  * any one time. It can acquire that rule several times, but a thread cannot
45  * acquire 2 non-conflicting rules at the same time.
46  *
47  * The implementation of the graph will sometimes also find and resolve bogus deadlocks.
48  * graph: assuming this rule hierarchy:
49  * R2 R3 L1 R1
50  * J1 1 0 0 / \
51  * J2 0 1 -1 R2 R3
52  * J3 -1 0 1
53  *
54  * If in the above situation job4 decides to acquire rule1, then the graph will transform
55  * to the following:
56  * R2 R3 R1 L1
57  * J1 1 0 1 0
58  * J2 1 1 1 -1
59  * J3 -1 0 0 1
60  * J4 0 0 -1 0
61  *
62  * and the graph will assume that job2 and job3 are deadlocked and suspend lock1 of job3.
63  * The reason the deadlock is bogus is that the deadlock is unlikely to actually happen (the threads
64  * are currently not deadlocked, but might deadlock later on when it is too late to detect it)
65  * Therefore, in order to make sure that no deadlock is possible,
66  * the deadlock will still be resolved at this point.
67  */
68 class DeadlockDetector {
69     private static int NO_STATE = 0;
70     //state variables in the graph
71 private static int WAITING_FOR_LOCK = -1;
72     //empty matrix
73 private static final int[][] EMPTY_MATRIX = new int[0][0];
74     //matrix of relationships between threads and locks
75 private int[][] graph = EMPTY_MATRIX;
76     //index is column in adjacency matrix for the lock
77 private final ArrayList locks = new ArrayList ();
78     //index is row in adjacency matrix for the thread
79 private final ArrayList lockThreads = new ArrayList ();
80     //whether the graph needs to be resized
81 private boolean resize = false;
82
83     /**
84      * Recursively check if any of the threads that prevent the current thread from running
85      * are actually deadlocked with the current thread.
86      * Add the threads that form deadlock to the deadlockedThreads list.
87      */
88     private boolean addCycleThreads(ArrayList deadlockedThreads, Thread next) {
89         //get the thread that block the given thread from running
90 Thread [] blocking = blockingThreads(next);
91         //if the thread is not blocked by other threads, then it is not part of a deadlock
92 if (blocking.length == 0)
93             return false;
94         boolean inCycle = false;
95         for (int i = 0; i < blocking.length; i++) {
96             //if we have already visited the given thread, then we found a cycle
97 if (deadlockedThreads.contains(blocking[i])) {
98                 inCycle = true;
99             } else {
100                 //otherwise, add the thread to our list and recurse deeper
101 deadlockedThreads.add(blocking[i]);
102                 //if the thread is not part of a cycle, remove it from the list
103 if (addCycleThreads(deadlockedThreads, blocking[i]))
104                     inCycle = true;
105                 else
106                     deadlockedThreads.remove(blocking[i]);
107             }
108         }
109         return inCycle;
110     }
111
112     /**
113      * Get the thread(s) that own the lock this thread is waiting for.
114      */
115     private Thread [] blockingThreads(Thread current) {
116         //find the lock this thread is waiting for
117 ISchedulingRule lock = (ISchedulingRule) getWaitingLock(current);
118         return getThreadsOwningLock(lock);
119     }
120
121     /**
122      * Check that the addition of a waiting thread did not produce deadlock.
123      * If deadlock is detected return true, else return false.
124      */
125     private boolean checkWaitCycles(int[] waitingThreads, int lockIndex) {
126         /**
127          * find the lock that this thread is waiting for
128          * recursively check if this is a cycle (i.e. a thread waiting on itself)
129          */
130         for (int i = 0; i < graph.length; i++) {
131             if (graph[i][lockIndex] > NO_STATE) {
132                 if (waitingThreads[i] > NO_STATE) {
133                     return true;
134                 }
135                 //keep track that we already visited this thread
136 waitingThreads[i]++;
137                 for (int j = 0; j < graph[i].length; j++) {
138                     if (graph[i][j] == WAITING_FOR_LOCK) {
139                         if (checkWaitCycles(waitingThreads, j))
140                             return true;
141                     }
142                 }
143                 //this thread is not involved in a cycle yet, so remove the visited flag
144 waitingThreads[i]--;
145             }
146         }
147         return false;
148     }
149
150     /**
151      * Returns true IFF the matrix contains a row for the given thread.
152      * (meaning the given thread either owns locks or is waiting for locks)
153      */
154     boolean contains(Thread t) {
155         return lockThreads.contains(t);
156     }
157
158     /**
159      * A new rule was just added to the graph.
160      * Find a rule it conflicts with and update the new rule with the number of times
161      * it was acquired implicitly when threads acquired conflicting rule.
162      */
163     private void fillPresentEntries(ISchedulingRule newLock, int lockIndex) {
164         //fill in the entries for the new rule from rules it conflicts with
165 for (int j = 0; j < locks.size(); j++) {
166             if ((j != lockIndex) && (newLock.isConflicting((ISchedulingRule) locks.get(j)))) {
167                 for (int i = 0; i < graph.length; i++) {
168                     if ((graph[i][j] > NO_STATE) && (graph[i][lockIndex] == NO_STATE))
169                         graph[i][lockIndex] = graph[i][j];
170                 }
171             }
172         }
173         //now back fill the entries for rules the current rule conflicts with
174 for (int j = 0; j < locks.size(); j++) {
175             if ((j != lockIndex) && (newLock.isConflicting((ISchedulingRule) locks.get(j)))) {
176                 for (int i = 0; i < graph.length; i++) {
177                     if ((graph[i][lockIndex] > NO_STATE) && (graph[i][j] == NO_STATE))
178                         graph[i][j] = graph[i][lockIndex];
179                 }
180             }
181         }
182     }
183
184     /**
185      * Returns all the locks owned by the given thread
186      */
187     private Object [] getOwnedLocks(Thread current) {
188         ArrayList ownedLocks = new ArrayList (1);
189         int index = indexOf(current, false);
190
191         for (int j = 0; j < graph[index].length; j++) {
192             if (graph[index][j] > NO_STATE)
193                 ownedLocks.add(locks.get(j));
194         }
195         if (ownedLocks.size() == 0)
196             Assert.isLegal(false, "A thread with no locks is part of a deadlock."); //$NON-NLS-1$
197 return ownedLocks.toArray();
198     }
199
200     /**
201      * Returns an array of threads that form the deadlock (usually 2).
202      */
203     private Thread [] getThreadsInDeadlock(Thread cause) {
204         ArrayList deadlockedThreads = new ArrayList (2);
205         /**
206          * if the thread that caused deadlock doesn't own any locks, then it is not part
207          * of the deadlock (it just caused it because of a rule it tried to acquire)
208          */
209         if (ownsLocks(cause))
210             deadlockedThreads.add(cause);
211         addCycleThreads(deadlockedThreads, cause);
212         return (Thread []) deadlockedThreads.toArray(new Thread [deadlockedThreads.size()]);
213     }
214
215     /**
216      * Returns the thread(s) that own the given lock.
217      */
218     private Thread [] getThreadsOwningLock(ISchedulingRule rule) {
219         if (rule == null)
220             return new Thread [0];
221         int lockIndex = indexOf(rule, false);
222         ArrayList blocking = new ArrayList (1);
223         for (int i = 0; i < graph.length; i++) {
224             if (graph[i][lockIndex] > NO_STATE)
225                 blocking.add(lockThreads.get(i));
226         }
227         if ((blocking.size() == 0) && (JobManager.DEBUG_LOCKS))
228             System.out.println("Lock " + rule + " is involved in deadlock but is not owned by any thread."); //$NON-NLS-1$ //$NON-NLS-2$
229 if ((blocking.size() > 1) && (rule instanceof ILock) && (JobManager.DEBUG_LOCKS))
230             System.out.println("Lock " + rule + " is owned by more than 1 thread, but it is not a rule."); //$NON-NLS-1$ //$NON-NLS-2$
231 return (Thread []) blocking.toArray(new Thread [blocking.size()]);
232     }
233
234     /**
235      * Returns the lock the given thread is waiting for.
236      */
237     private Object getWaitingLock(Thread current) {
238         int index = indexOf(current, false);
239         //find the lock that this thread is waiting for
240 for (int j = 0; j < graph[index].length; j++) {
241             if (graph[index][j] == WAITING_FOR_LOCK)
242                 return locks.get(j);
243         }
244         //it can happen that a thread is not waiting for any lock (it is not really part of the deadlock)
245 return null;
246     }
247
248     /**
249      * Returns the index of the given lock in the lock array. If the lock is
250      * not present in the array, it is added to the end.
251      */
252     private int indexOf(ISchedulingRule lock, boolean add) {
253         int index = locks.indexOf(lock);
254         if ((index < 0) && add) {
255             locks.add(lock);
256             resize = true;
257             index = locks.size() - 1;
258         }
259         return index;
260     }
261
262     /**
263      * Returns the index of the given thread in the thread array. If the thread
264      * is not present in the array, it is added to the end.
265      */
266     private int indexOf(Thread owner, boolean add) {
267         int index = lockThreads.indexOf(owner);
268         if ((index < 0) && add) {
269             lockThreads.add(owner);
270             resize = true;
271             index = lockThreads.size() - 1;
272         }
273         return index;
274     }
275
276     /**
277      * Returns true IFF the adjacency matrix is empty.
278      */
279     boolean isEmpty() {
280         return (locks.size() == 0) && (lockThreads.size() == 0) && (graph.length == 0);
281     }
282
283     /**
284      * The given lock was acquired by the given thread.
285      */
286     void lockAcquired(Thread owner, ISchedulingRule lock) {
287         int lockIndex = indexOf(lock, true);
288         int threadIndex = indexOf(owner, true);
289         if (resize)
290             resizeGraph();
291         if (graph[threadIndex][lockIndex] == WAITING_FOR_LOCK)
292             graph[threadIndex][lockIndex] = NO_STATE;
293         /**
294          * acquire all locks that conflict with the given lock
295          * or conflict with a lock the given lock will acquire implicitly
296          * (locks are acquired implicitly when a conflicting lock is acquired)
297          */
298         ArrayList conflicting = new ArrayList (1);
299         //only need two passes through all the locks to pick up all conflicting rules
300 int NUM_PASSES = 2;
301         conflicting.add(lock);
302         graph[threadIndex][lockIndex]++;
303         for (int i = 0; i < NUM_PASSES; i++) {
304             for (int k = 0; k < conflicting.size(); k++) {
305                 ISchedulingRule current = (ISchedulingRule) conflicting.get(k);
306                 for (int j = 0; j < locks.size(); j++) {
307                     ISchedulingRule possible = (ISchedulingRule) locks.get(j);
308                     if (current.isConflicting(possible) && !conflicting.contains(possible)) {
309                         conflicting.add(possible);
310                         graph[threadIndex][j]++;
311                     }
312                 }
313             }
314         }
315     }
316
317     /**
318      * The given lock was released by the given thread. Update the graph.
319      */
320     void lockReleased(Thread owner, ISchedulingRule lock) {
321         int lockIndex = indexOf(lock, false);
322         int threadIndex = indexOf(owner, false);
323         //make sure the lock and thread exist in the graph
324 if (threadIndex < 0) {
325             if (JobManager.DEBUG_LOCKS)
326                 System.out.println("[lockReleased] Lock " + lock + " was already released by thread " + owner.getName()); //$NON-NLS-1$ //$NON-NLS-2$
327 return;
328         }
329         if (lockIndex < 0) {
330             if (JobManager.DEBUG_LOCKS)
331                 System.out.println("[lockReleased] Thread " + owner.getName() + " already released lock " + lock); //$NON-NLS-1$ //$NON-NLS-2$
332 return;
333         }
334         //if this lock was suspended, set it to NO_STATE
335 if ((lock instanceof ILock) && (graph[threadIndex][lockIndex] == WAITING_FOR_LOCK)) {
336             graph[threadIndex][lockIndex] = NO_STATE;
337             return;
338         }
339         //release all locks that conflict with the given lock
340 //or release all rules that are owned by the given thread, if we are releasing a rule
341 for (int j = 0; j < graph[threadIndex].length; j++) {
342             if ((lock.isConflicting((ISchedulingRule) locks.get(j))) || (!(lock instanceof ILock) && !(locks.get(j) instanceof ILock) && (graph[threadIndex][j] > NO_STATE))) {
343                 if (graph[threadIndex][j] == NO_STATE) {
344                     if (JobManager.DEBUG_LOCKS)
345                         System.out.println("[lockReleased] More releases than acquires for thread " + owner.getName() + " and lock " + lock); //$NON-NLS-1$ //$NON-NLS-2$
346 } else {
347                     graph[threadIndex][j]--;
348                 }
349             }
350         }
351         //if this thread just released the given lock, try to simplify the graph
352 if (graph[threadIndex][lockIndex] == NO_STATE)
353             reduceGraph(threadIndex, lock);
354     }
355
356     /**
357      * The given scheduling rule is no longer used because the job that invoked it is done.
358      * Release this rule regardless of how many times it was acquired.
359      */
360     void lockReleasedCompletely(Thread owner, ISchedulingRule rule) {
361         int ruleIndex = indexOf(rule, false);
362         int threadIndex = indexOf(owner, false);
363         //need to make sure that the given thread and rule were not already removed from the graph
364 if (threadIndex < 0) {
365             if (JobManager.DEBUG_LOCKS)
366                 System.out.println("[lockReleasedCompletely] Lock " + rule + " was already released by thread " + owner.getName()); //$NON-NLS-1$ //$NON-NLS-2$
367 return;
368         }
369         if (ruleIndex < 0) {
370             if (JobManager.DEBUG_LOCKS)
371                 System.out.println("[lockReleasedCompletely] Thread " + owner.getName() + " already released lock " + rule); //$NON-NLS-1$ //$NON-NLS-2$
372 return;
373         }
374         /**
375          * set all rules that are owned by the given thread to NO_STATE
376          * (not just rules that conflict with the rule we are releasing)
377          * if we are releasing a lock, then only update the one entry for the lock
378          */
379         for (int j = 0; j < graph[threadIndex].length; j++) {
380             if (!(locks.get(j) instanceof ILock) && (graph[threadIndex][j] > NO_STATE))
381                 graph[threadIndex][j] = NO_STATE;
382         }
383         reduceGraph(threadIndex, rule);
384     }
385
386     /**
387      * The given thread could not get the given lock and is waiting for it.
388      * Update the graph.
389      */
390     Deadlock lockWaitStart(Thread client, ISchedulingRule lock) {
391         setToWait(client, lock, false);
392         int lockIndex = indexOf(lock, false);
393         int[] temp = new int[lockThreads.size()];
394         //check if the addition of the waiting thread caused deadlock
395 if (!checkWaitCycles(temp, lockIndex))
396             return null;
397         //there is a deadlock in the graph
398 Thread [] threads = getThreadsInDeadlock(client);
399         Thread candidate = resolutionCandidate(threads);
400         ISchedulingRule[] locksToSuspend = realLocksForThread(candidate);
401         Deadlock deadlock = new Deadlock(threads, locksToSuspend, candidate);
402         //find a thread whose locks can be suspended to resolve the deadlock
403 if (JobManager.DEBUG_LOCKS)
404             reportDeadlock(deadlock);
405         if (JobManager.DEBUG_DEADLOCK)
406             throw new IllegalStateException ("Deadlock detected. Caused by thread " + client.getName() + '.'); //$NON-NLS-1$
407 // Update the graph to indicate that the locks will now be suspended.
408 // To indicate that the lock will be suspended, we set the thread to wait for the lock.
409 // When the lock is forced to be released, the entry will be cleared.
410 for (int i = 0; i < locksToSuspend.length; i++)
411             setToWait(deadlock.getCandidate(), locksToSuspend[i], true);
412         return deadlock;
413     }
414
415     /**
416      * The given thread has stopped waiting for the given lock.
417      * Update the graph.
418      */
419     void lockWaitStop(Thread owner, ISchedulingRule lock) {
420         int lockIndex = indexOf(lock, false);
421         int threadIndex = indexOf(owner, false);
422         //make sure the thread and lock exist in the graph
423 if (threadIndex < 0) {
424             if (JobManager.DEBUG_LOCKS)
425                 System.out.println("Thread " + owner.getName() + " was already removed."); //$NON-NLS-1$ //$NON-NLS-2$
426 return;
427         }
428         if (lockIndex < 0) {
429             if (JobManager.DEBUG_LOCKS)
430                 System.out.println("Lock " + lock + " was already removed."); //$NON-NLS-1$ //$NON-NLS-2$
431 return;
432         }
433         if (graph[threadIndex][lockIndex] != WAITING_FOR_LOCK)
434             Assert.isTrue(false, "Thread " + owner.getName() + " was not waiting for lock " + lock.toString() + " so it could not time out."); //$NON-NLS-1$ //$NON-NLS-2$ //$NON-NLS-3$
435 graph[threadIndex][lockIndex] = NO_STATE;
436         reduceGraph(threadIndex, lock);
437     }
438
439     /**
440      * Returns true IFF the given thread owns a single lock
441      */
442     private boolean ownsLocks(Thread cause) {
443         int threadIndex = indexOf(cause, false);
444         for (int j = 0; j < graph[threadIndex].length; j++) {
445             if (graph[threadIndex][j] > NO_STATE)
446                 return true;
447         }
448         return false;
449     }
450
451     /**
452      * Returns true IFF the given thread owns a single real lock.
453      * A real lock is a lock that can be suspended.
454      */
455     private boolean ownsRealLocks(Thread owner) {
456         int threadIndex = indexOf(owner, false);
457         for (int j = 0; j < graph[threadIndex].length; j++) {
458             if (graph[threadIndex][j] > NO_STATE) {
459                 Object lock = locks.get(j);
460                 if (lock instanceof ILock)
461                     return true;
462             }
463         }
464         return false;
465     }
466
467     /**
468      * Return true IFF this thread owns rule locks (i.e. implicit locks which
469      * cannot be suspended)
470      */
471     private boolean ownsRuleLocks(Thread owner) {
472         int threadIndex = indexOf(owner, false);
473         for (int j = 0; j < graph[threadIndex].length; j++) {
474             if (graph[threadIndex][j] > NO_STATE) {
475                 Object lock = locks.get(j);
476                 if (!(lock instanceof ILock))
477                     return true;
478             }
479         }
480         return false;
481     }
482
483     /**
484      * Returns an array of real locks that are owned by the given thread.
485      * Real locks are locks that implement the ILock interface and can be suspended.
486      */
487     private ISchedulingRule[] realLocksForThread(Thread owner) {
488         int threadIndex = indexOf(owner, false);
489         ArrayList ownedLocks = new ArrayList (1);
490         for (int j = 0; j < graph[threadIndex].length; j++) {
491             if ((graph[threadIndex][j] > NO_STATE) && (locks.get(j) instanceof ILock))
492                 ownedLocks.add(locks.get(j));
493         }
494         if (ownedLocks.size() == 0)
495             Assert.isLegal(false, "A thread with no real locks was chosen to resolve deadlock."); //$NON-NLS-1$
496 return (ISchedulingRule[]) ownedLocks.toArray(new ISchedulingRule[ownedLocks.size()]);
497     }
498
499     /**
500      * The matrix has been simplified. Check if any unnecessary rows or columns
501      * can be removed.
502      */
503     private void reduceGraph(int row, ISchedulingRule lock) {
504         int numLocks = locks.size();
505         boolean[] emptyColumns = new boolean[numLocks];
506
507         /**
508          * find all columns that could possibly be empty
509          * (consist of locks which conflict with the given lock, or of locks which are rules)
510          */
511         for (int j = 0; j < numLocks; j++) {
512             if ((lock.isConflicting((ISchedulingRule) locks.get(j))) || !(locks.get(j) instanceof ILock))
513                 emptyColumns[j] = true;
514         }
515
516         boolean rowEmpty = true;
517         int numEmpty = 0;
518         //check if the given row is empty
519 for (int j = 0; j < graph[row].length; j++) {
520             if (graph[row][j] != NO_STATE) {
521                 rowEmpty = false;
522                 break;
523             }
524         }
525         /**
526          * Check if the possibly empty columns are actually empty.
527          * If a column is actually empty, remove the corresponding lock from the list of locks
528          * Start at the last column so that when locks are removed from the list,
529          * the index of the remaining locks is unchanged. Store the number of empty columns.
530          */
531         for (int j = emptyColumns.length - 1; j >= 0; j--) {
532             for (int i = 0; i < graph.length; i++) {
533                 if (emptyColumns[j] && (graph[i][j] != NO_STATE)) {
534                     emptyColumns[j] = false;
535                     break;
536                 }
537             }
538             if (emptyColumns[j]) {
539                 locks.remove(j);
540                 numEmpty++;
541             }
542         }
543         //if no columns or rows are empty, return right away
544 if ((numEmpty == 0) && (!rowEmpty))
545             return;
546
547         if (rowEmpty)
548             lockThreads.remove(row);
549
550         //new graph (the list of locks and the list of threads are already updated)
551 final int numThreads = lockThreads.size();
552         numLocks = locks.size();
553         //optimize empty graph case
554 if (numThreads == 0 && numLocks == 0) {
555             graph = EMPTY_MATRIX;
556             return;
557         }
558         int[][] tempGraph = new int[numThreads][numLocks];
559
560         //the number of rows we need to skip to get the correct entry from the old graph
561 int numRowsSkipped = 0;
562         for (int i = 0; i < graph.length - numRowsSkipped; i++) {
563             if ((i == row) && rowEmpty) {
564                 numRowsSkipped++;
565                 //check if we need to skip the last row
566 if (i >= graph.length - numRowsSkipped)
567                     break;
568             }
569             //the number of columns we need to skip to get the correct entry from the old graph
570 //needs to be reset for every new row
571 int numColsSkipped = 0;
572             for (int j = 0; j < graph[i].length - numColsSkipped; j++) {
573                 while (emptyColumns[j + numColsSkipped]) {
574                     numColsSkipped++;
575                     //check if we need to skip the last column
576 if (j >= graph[i].length - numColsSkipped)
577                         break;
578                 }
579                 //need to break out of the outer loop
580 if (j >= graph[i].length - numColsSkipped)
581                     break;
582                 tempGraph[i][j] = graph[i + numRowsSkipped][j + numColsSkipped];
583             }
584         }
585         graph = tempGraph;
586         Assert.isTrue(numThreads == graph.length, "Rows and threads don't match."); //$NON-NLS-1$
587 Assert.isTrue(numLocks == ((graph.length > 0) ? graph[0].length : 0), "Columns and locks don't match."); //$NON-NLS-1$
588 }
589
590     /**
591      * Adds a 'deadlock detected' message to the log with a stack trace.
592      */
593     private void reportDeadlock(Deadlock deadlock) {
594         String msg = "Deadlock detected. All locks owned by thread " + deadlock.getCandidate().getName() + " will be suspended."; //$NON-NLS-1$ //$NON-NLS-2$
595 MultiStatus main = new MultiStatus(JobManager.PI_JOBS, JobManager.PLUGIN_ERROR, msg, new IllegalStateException ());
596         Thread [] threads = deadlock.getThreads();
597         for (int i = 0; i < threads.length; i++) {
598             Object [] ownedLocks = getOwnedLocks(threads[i]);
599             Object waitLock = getWaitingLock(threads[i]);
600             StringBuffer buf = new StringBuffer ("Thread "); //$NON-NLS-1$
601 buf.append(threads[i].getName());
602             buf.append(" has locks: "); //$NON-NLS-1$
603 for (int j = 0; j < ownedLocks.length; j++) {
604                 buf.append(ownedLocks[j]);
605                 buf.append((j < ownedLocks.length - 1) ? ", " : " "); //$NON-NLS-1$ //$NON-NLS-2$
606 }
607             buf.append("and is waiting for lock "); //$NON-NLS-1$
608 buf.append(waitLock);
609             Status child = new Status(IStatus.ERROR, JobManager.PI_JOBS, JobManager.PLUGIN_ERROR, buf.toString(), null);
610             main.add(child);
611         }
612         RuntimeLog.log(main);
613     }
614
615     /**
616      * The number of threads/locks in the graph has changed. Update the
617      * underlying matrix.
618      */
619     private void resizeGraph() {
620         // a new row and/or a new column was added to the graph.
621 // since new rows/columns are always added to the end, just transfer
622 // old entries to the new graph, with the same indices.
623 final int newRows = lockThreads.size();
624         final int newCols = locks.size();
625         //optimize 0x0 and 1x1 matrices
626 if (newRows == 0 && newCols == 0) {
627             graph = EMPTY_MATRIX;
628             return;
629         }
630         int[][] tempGraph = new int[newRows][newCols];
631         for (int i = 0; i < graph.length; i++)
632             System.arraycopy(graph[i], 0, tempGraph[i], 0, graph[i].length);
633         graph = tempGraph;
634         resize = false;
635     }
636
637     /**
638      * Get the thread whose locks can be suspended. (i.e. all locks it owns are
639      * actual locks and not rules). Return the first thread in the array by default.
640      */
641     private Thread resolutionCandidate(Thread [] candidates) {
642         //first look for a candidate that has no scheduling rules
643 for (int i = 0; i < candidates.length; i++) {
644             if (!ownsRuleLocks(candidates[i]))
645                 return candidates[i];
646         }
647         //next look for any candidate with a real lock (a lock that can be suspended)
648 for (int i = 0; i < candidates.length; i++) {
649             if (ownsRealLocks(candidates[i]))
650                 return candidates[i];
651         }
652         //unnecessary, return the first entry in the array by default
653 return candidates[0];
654     }
655
656     /**
657      * The given thread is waiting for the given lock. Update the graph.
658      */
659     private void setToWait(Thread owner, ISchedulingRule lock, boolean suspend) {
660         boolean needTransfer = false;
661         /**
662          * if we are adding an entry where a thread is waiting on a scheduling rule,
663          * then we need to transfer all positive entries for a conflicting rule to the
664          * newly added rule in order to synchronize the graph.
665          */
666         if (!suspend && !(lock instanceof ILock))
667             needTransfer = true;
668         int lockIndex = indexOf(lock, !suspend);
669         int threadIndex = indexOf(owner, !suspend);
670         if (resize)
671             resizeGraph();
672
673         graph[threadIndex][lockIndex] = WAITING_FOR_LOCK;
674         if (needTransfer)
675             fillPresentEntries(lock, lockIndex);
676     }
677
678     /**
679      * Prints out the current matrix to standard output.
680      * Only used for debugging.
681      */
682     public String toDebugString() {
683         StringWriter sWriter = new StringWriter ();
684         PrintWriter out = new PrintWriter (sWriter, true);
685         out.println(" :: "); //$NON-NLS-1$
686 for (int j = 0; j < locks.size(); j++) {
687             out.print(" " + locks.get(j) + ','); //$NON-NLS-1$
688 }
689         out.println();
690         for (int i = 0; i < graph.length; i++) {
691             out.print(" " + ((Thread ) lockThreads.get(i)).getName() + " : "); //$NON-NLS-1$ //$NON-NLS-2$
692 for (int j = 0; j < graph[i].length; j++) {
693                 out.print(" " + graph[i][j] + ','); //$NON-NLS-1$
694 }
695             out.println();
696         }
697         out.println("-------"); //$NON-NLS-1$
698 return sWriter.toString();
699     }
700 }
701

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags