Patent ID: 8230437

Claim:
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, wherein computing a resource graph comprises 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; 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, wherein constructing, computing and determining are steps that are performed by a computer, 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, and 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.