System and methods for deadlock detection

• US 7,496,918 B1
• Filed: 06/01/2004
• Issued: 02/24/2009
• Est. Priority Date: 06/01/2004
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Chung, Mandy L., Dice, David
• Primary Examiner(s): An; Meng-Ai
• Assistant Examiner(s): ARCOS, CAROLINE H
• Application Number:
  US10/857,811
• Time in Patent Office: 1,729 Days
• Field of Search: 718/104, 718/107, 718/100, 718/102, 709/225, 711/100, 707/10
• US Class Current: 718/100
• CPC Class Codes: G06F 9/524 Deadlock detection or avoidance

Abstract

A lightweight, concurrent detection mechanism avoids global thread suspension by operating during runtime with threads under examination. A particular configuration combines a dependency (“waits for”) snapshot with a progression check to determine advancement of purportedly deadlocked threads. Thread blocking is enumerated in a table or graph which denotes dependencies of threads and the corresponding resources. For identified circular dependencies, a successive transition, or progression check ratifies the potential deadlock. A transition counter corresponding to each thread is analyzed in the progression check. The transition counter is indicative of a change in state for the process in question, hence is indicative of instruction execution, an activity not performed by a blocked process. Deadlock is therefore ratified if the transition counters associated with the threads in the potential deadlock have not advanced.

Claims

1. A computerized method for controlling execution in an object based environment comprising:

identifying a plurality of threads having a potential demand for at least one of a plurality of shared resources;

determining when multiple identified threads are waiting for at least one of the shared resources;

enumerating, for each of the determined waiting threads, a lock holding entity (blocking entity) holding the shared resource sought by each of the waiting threads;

computing whether an undesirable dependency exists by analyzing each of the blocking entities and corresponding waiting threads; and

comparing, if the analyzing indicates that pending undesirable dependency exists, a progression indicator indicative of advancement of the threads corresponding to the undesirable dependency;

wherein computing the pending undesirable dependency further comprises determining a circular dependency among a plurality of waiting threads, the circular dependency indicative of a thread waiting for a resource held by a lock holding entity and simultaneously holding a resource sought, directly or indirectly, by the same lock holding entity;

wherein computing and comparing occur in a non-intrusive manner during continuous concurrent execution of the threads; and

wherein enumerating further comprises;

building a blocking information tuple indicative of an instance of a thread waiting for a resource;

aggregating a plurality of blocking information tuples indicative of a plurality of threads and corresponding blocking entities; and

wherein comparing and computing further comprises analyzing multiple sets of the blocking information tuples, the blocking information tuples derived from multiple pass scanning snapshots of the identified threads.

2. The method of claim 1 wherein comparing further comprises ratifying a potential deadlock presented by the pending undesirable dependency, wherein a lack of advancement by a potentially deadlocked thread is indicative of ratifying the potential deadlock.

3. The method of claim 2 wherein ratifying further comprises identifying progression of the threads in question by performing a successive snapshot to identify advancement of the threads in question.

4. The method of claim 3 wherein advancement is indicated by a state transition of at least one of the threads in the computed undesirable dependency.

5. The method of claim 4 further comprising reading a transition register indicative of advancement of an instruction counter in the thread, the instruction counter advancing according to a thread control flow when the thread is unblocked and stopped when the thread is waiting for a resource.

6. A computing device for detecting deadlock between concurrent threads in a multiprogramming environment comprising:

a processor operable for performing;

a deadlock detector operable to identify a plurality of threads having a potential demand for at least one of a plurality of shared resources;

an agent interface operable for receiving messages for determining when multiple identified threads are waiting for at least one of the shared resources;

a thread dependency table operable to enumerate, for each of the determined waiting threads, a lock holding entity (blocking entity) holding the shared resource sought by each of the waiting threads, the deadlock detector further operable to employ the thread dependency table to computer whether an undesirable dependency exists by analyzing each of the blocking entities and corresponding waiting threads; and

a transition comparator operable to compare, if the analyzing indicates that an undesirable dependency exists, a progression indicator indicative of advancement of the threads corresponding to the undesirable dependency;

wherein the deadlock detector is further operable to compute the undesirable dependency by;

determining a circular dependency among a plurality of waiting threads, the circular dependency indicative of a thread waiting for a resource held by a lock holding entity; and

simultaneously holding a resource sought, directly or indirectly, by the same lock holding entity; and

simultaneously holding a resource sought, directly or indirectly, by the same lock holding entity;

wherein the deadlock detector is operable to perform computing and comparing in a non-intrusive manner during continuous concurrent execution of the threads;

wherein the deadlock detector is further operable to;

build a blocking information tuple indicative of an instance of a thread waiting for a resource; and

aggregate a plurality of blocking information tuples indicative of a plurality of threads and corresponding blocking entities; and

wherein the deadlock detector is further operable to perform the comparing and computing by analyzing multiple sets of the blocking information tuples, the blocking information tuples derived from multiple pass scanning snapshots of the identified threads.

7. The computing device of claim 6 wherein the transition comparator is operable to ratify a potential deadlock presented by the pending undesirable dependency, wherein a lack of advancement by a potentially deadlocked thread is indicative of ratifying the potential deadlock.

8. The computing device of claim 7 wherein the transition comparator is further operable to identify progression of the threads in question by performing a successive snapshot to identify advancement of the threads in question.

9. The computing device of claim 8 wherein the transition comparator is operable to determine a state transition of at least one of the threads in the computed undesirable dependency.

10. The computing device of claim 9 wherein the transition counter is further operable to read a transition register indicative of advancement of an instruction counter in the thread, the instruction counter advancing according to a thread control flow when the thread is unblocked and stopped when the thread is waiting for a resource.

11. A computer program product having a computer readable medium operable to store computer program logic embodied in computer program code encoded thereon when executed by a processor operable for controlling execution in an object based environment comprising:

computer program code for identifying a plurality of threads having a potential demand for at least one of a plurality of shared resources;

computer program code for determining when multiple identified threads are waiting for at least one of the shared resources;

computer program code for enumerating, for each of the determined waiting threads, a lock holding entity (blocking entity) holding the shared resource sought by each of the waiting threads;

computer program code for computing whether an undesirable dependency exists by analyzing each of the blocking entities and corresponding waiting threads; and

computer program code for comparing, if the analyzing indicates that a pending undesirable dependency exists, a progression indicator indicative of advancement of the threads corresponding to the undesirable dependency;

wherein the computer program code for computing the pending undesirable dependency further comprises computer program code for determining a circular dependency among a plurality of waiting threads, the circular dependency indicative of a thread waiting for a resource held by a lock holding entity and simultaneously holding a resource sought, directly or indirectly, by the same lock holding entity;

wherein computing and comparing occur in a non-intrusive manner during continuous concurrent execution of the threads; and

wherein the computer program code for enumerating further comprises;

computer program code for building a blocking information tuple indicative of an instance of a thread waiting for a resource;

computer program code for aggregating a plurality of blocking information tuples indicative of a plurality of threads and corresponding blocking entities; and

wherein the computer program code for comparing and computing further comprises computer program code for analyzing multiple sets of the blocking information tuples, the blocking information tuples derived from multiple pass scanning snapshots of the identified threads.

12. A system for detecting deadlock between concurrent threads in a multiprogramming environment comprising a processor operable for performing:

means for identifying a plurality of threads having a potential demand for at least one of a plurality of shared resources;

means for determining when multiple identified threads are waiting for at least one of the shared resources;

means for enumerating, for each of the determined waiting threads, a lock holding entity (blocking entity) holding the shared resource sought by each of the waiting threads;

means for computing whether an undesirable dependency exists by analyzing each of the blocking entities and corresponding waiting threads; and

means for comparing, if the analyzing indicates that a pending undesirable dependency exists, a progression indicator indicative of advancement of the threads corresponding to the undesirable dependency;

wherein the means for computing the pending undesirable dependency further comprises means for determining a circular dependency among a plurality of waiting threads, the circular dependency indicative of a thread waiting for a resource held by a lock holding entity and simultaneously holding a resource sought, directly or indirectly, by the same lock holding entity;

wherein computing and comparing occur in a non-intrusive manner during continuous concurrent execution of the threads; and

wherein the means for enumerating further comprises;

means for building a blocking information tuple indicative of an instance of a thread waiting for a resource;

means for aggregating a plurality of blocking information tuples indicative of a plurality of threads and corresponding blocking entities; and

wherein the means for comparing and computing further comprises means for analyzing multiple sets of the blocking information tuples, the blocking information tuples derived from multiple pass scanning snapshots of the identified threads.