Methods and apparatus for detecting deadlock in multithreading programs

Abstract

A method of detecting deadlock in a multithreading program is provided. An invocation graph is constructed having a single root and a plurality of nodes corresponding to one or more functions written in code of the multithreading program. A resource graph is computed in accordance with one or more resource sets in effect at each node of the invocation graph. It is determined whether cycles exist between two or more nodes of the resource graph. A cycle is an indication of deadlock in the multithreading program.

1 . A method of detecting deadlock in a multithreading program, comprising the steps of: 
 constructing an invocation graph having a single root and a plurality of nodes corresponding to one or more functions written in code of the multithreading program;    computing a resource graph in accordance with one or more resource sets in effect at each node of the invocation graph; and    determining whether cycles exist between two or more nodes of the resource graph, wherein a cycle is an indication of deadlock in the multithreading program.    
   
   
       2 . The method of  claim 1 , wherein the multithreading program comprises a Java™ program.  
   
   
       3 . The method of  claim 1 , wherein, in the step of constructing an invocation graph, each node comprises basic blocks of a control flow graph of a function written in the code of the multithreading program and locations where resources are accessed and released.  
   
   
       4 . The method of  claim 1 , wherein, in the step of constructing an invocation graph, each edge connecting two nodes corresponds to an invocation of a function written in the code of the multithreading program from within another function written in the code of the multithreading program.  
   
   
       5 . The method of  claim 1 , wherein, in the step of constructing an invocation graph, the invocation graph allows for bidirectional traversal between nodes to determine sets of predecessor nodes and successor nodes.  
   
   
       6 . The method of  claim 1 , wherein the step of constructing an invocation graph comprises the step of performing a data flow analysis.  
   
   
       7 . The method of  claim 1 , wherein, in the step of constructing an invocation graph, each node in the invocation graph is identifiable by a calling context.  
   
   
       8 . The method of  claim 7 , wherein the calling context comprises at least one of a target function, a set of possible receiver types, and parameter types.  
   
   
       9 . The method of  claim 1 , wherein, in the step of computing a resource graph, a resource comprises an object and a counter, and a resource set comprises resources having distinct objects.  
   
   
       10 . The method of  claim 1 , wherein the step of computing a resource graph comprises the steps of: 
 constructing a set of nodes and edges in accordance with the resource sets in effect at each node of the invocation graph; and    refining a definition of the resource graph through post-processing.    
   
   
       11 . The method of  claim 10 , wherein the step of constructing a set of nodes and edges comprises the steps of: 
 calculating a first resource set from the invocation graph;    adding edges as resources are requested;    computing resource sets for each edge leaving a node of the first resource set;    updating the resource graph as required after each step; and    repeating the calculating, adding, computing and updating steps for each newly created resource set.    
   
   
       12 . The method of  claim 10 , wherein the step of refining a definition of the lock graph comprises the step of examining a current set of vertices to generate additional edges.  
   
   
       13 . The method of  claim 1 , further comprising the step of reporting any cycles with associated path information.  
   
   
       14 . Apparatus for detecting deadlock in a multithreading program, comprising: 
 a memory; and    at least one processor coupled to the memory and operative to: (i) construct an invocation graph having a single root and a plurality of nodes corresponding to one or more functions written in code of the multithreading program; (ii) compute a resource graph in accordance with one or more resource sets in effect at each node of the invocation graph; and (iii) determine whether cycles exist between two or more nodes of the resource graph, wherein a cycle is an indication of deadlock in the multithreading program.    
   
   
       15 . The apparatus of  claim 14 , wherein the multithreading program comprises a Java™ program.  
   
   
       16 . The apparatus of  claim 14 , wherein, in the operation of constructing an invocation graph, each node comprises basic blocks of a control flow graph of a function written in the code of the multithreading program and locations where resources are accessed and released.  
   
   
       17 . The apparatus of  claim 14 , wherein, in the operation of constructing an invocation graph, each edge connecting two nodes corresponds to an invocation of a function written in the code of the multithreading program from within another function written in the code of the multithreading program.  
   
   
       18 . The apparatus of  claim 14 , wherein, in the operation of constructing an invocation graph, the invocation graph allows for bidirectional traversal between nodes to determine sets of predecessor nodes and successor nodes.  
   
   
       19 . The apparatus of  claim 14 , wherein the operation of constructing an invocation graph comprises the step of performing a data flow analysis.  
   
   
       20 . The apparatus of  claim 14 , wherein, in the operation of constructing an invocation graph, each node in the invocation graph is identifiable by a calling context.  
   
   
       21 . The apparatus of  claim 20 , wherein the calling context comprises at least one of a target function, a set of possible receiver types, and parameter types.  
   
   
       22 . The apparatus of  claim 14 , wherein, in the operation of computing a resource graph, a resource comprises an object and a counter, and a resource set comprises resources having distinct objects.  
   
   
       23 . The apparatus of  claim 14 , wherein the operation of computing a resource graph comprises the steps of: 
 constructing a set of nodes and edges in accordance with the resource sets in effect at each node of the invocation graph; and    refining a definition of the resource graph through post-processing.    
   
   
       24 . The apparatus of  claim 23 , wherein the step of constructing a set of nodes and edges comprises the steps of: 
 calculating a first resource set from the invocation graph;    adding edges as resources are requested;    computing resource sets for each edge leaving a node of the first resource set;    updating the resource graph as required after each step; and    repeating the calculating, adding, computing and updating steps for each newly created resource set.    
   
   
       25 . The apparatus of  claim 24 , wherein the step of refining a definition of the lock graph comprises the step of examining a current set of vertices to generate additional edges.  
   
   
       26 . The apparatus of  claim 14 , further comprising the operation of reporting any cycles with associated path information.  
   
   
       27 . An article of manufacture for detecting deadlock in a multithreading program, comprising a machine readable medium containing one or more programs which when executed implement the steps of: 
 constructing an invocation graph having a single root and a plurality of nodes corresponding to one or more functions written in code of the multithreading program;    computing a resource graph in accordance with one or more resource sets in effect at each node of the invocation graph; and    determining whether cycles exist between two or more nodes of the resource graph, wherein a cycle is an indication of deadlock in the multithreading program.