Methods and apparatus for detecting deadlock in multithreading programs
First Claim
Patent Images
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.
1 Assignment
0 Petitions
Accused Products
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.
30 Citations
27 Claims
-
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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13)
-
-
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. - View Dependent Claims (15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26)
-
-
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.
-
Specification