Detecting lock acquisition hierarchy violations in multithreaded programs

• US 20060070076A1
• Filed: 09/29/2004
• Published: 03/30/2006
• Est. Priority Date: 09/29/2004
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Ma, Zhiqiang
• Granted Patent: US 7,657,894 B2
• Time in Patent Office: Days
• US Class Current: 718/104
• CPC Class Codes: G06F 11/366 using diagnostics G06F11/0703 takes precedence
• CPC Class Codes: G06F 9/524 Deadlock detection or avoidance

Abstract

A method, apparatus, and system are provided for monitoring resource operations and detecting lock acquisition hierarchy violations in multithreaded programs. In one embodiment, a lock acquisition hierarchy graph is constructed to facilitate monitoring of resource operations performed by each of a plurality of threads of a multithreaded program. The resource operations performed by each thread are monitored by a monitor. Any violation in the hierarchy is detected by a detector, which is triggered with an occurrence of a change in the graph.

Claims

1. A method, comprising:

constructing a lock acquisition hierarchy graph to facilitate monitoring of resource operations corresponding to each of a plurality of threads of a multithreaded program;

monitoring the resource operations being performed in accordance with a hierarchy; and

detecting a violation in the hierarchy, wherein the detecting of the violation is triggered with an occurrence of a change in the graph.

2. The method of claim 1, further comprising reporting the violation to a user.

3. The method of claim 1, wherein the resource operations comprise one or more of the following:

resource acquisition operations and resource release operations.

4. The method of claim 1, further comprising maintaining a thread descriptor corresponding to each of the plurality of threads.

5. The method of claim 1, wherein the graph comprises one or more lock acquisition nodes, each node representing one or more resources acquired by each thread of the plurality of threads.

6. The method of claim 1, wherein the change in the graph comprises creating a new node in the graph, and adding the new node to the graph, the new node having a parent node.

7. The method of claim 1, wherein the detecting of the violation comprises seeking one or more cycles satisfying a set of conditions in the graph, the set of conditions includes a plurality of conditions relating to activities of the nodes and the new node in the graph, wherein the violation is detected if the set of conditions is satisfied, and the violation is not detected if one or more of the set of conditions is not satisfied.

8. A system, comprising:

a monitor to

construct a lock acquisition hierarchy graph to facilitate monitoring of resource operations corresponding to each of a plurality of threads of a multithreaded program, and

monitor the resource operations being performed in accordance with a hierarchy; and

a detector to detect a violation in the hierarchy, wherein the detecting of the violation is triggered with an occurrence of a change in the graph.

9. The system of claim 8, wherein the detector is further to report the violation to a user.

10. The system of claim 8, wherein the resource operations comprise one or more of the following:

resource acquisition operations and resource release operations.

11. The system of claim 8, wherein the monitor is further to maintain a thread descriptor corresponding to each of the plurality of threads.

12. The system of claim 8, wherein the graph comprises one or more lock acquisition nodes, each node representing one or more resources acquired by each thread of the plurality of threads.

13. The system of claim 8, wherein the change in the graph comprises creating a new node in the graph, and adding the new node to the graph, the new node having a parent node.

14. The system of claim 8, wherein the detecting of the violation comprises seeking one or more cycles satisfying a set of conditions in the graph, the set of conditions includes a plurality of conditions relating to activities of the nodes and the new node in the graph, wherein the violation is detected if the set of conditions is satisfied, and the violation is not detected if one or more of the set of conditions is not satisfied.

15. An apparatus, comprising

a processor;

and

a storage medium coupled with the processor, the storage device having stored thereon data representing sets of instructions, the sets of instructions which, when executed by the processor, cause the processor to;

construct a lock acquisition hierarchy graph to facilitate monitoring of resource operations corresponding to each of a plurality of threads of a multithreaded program,

monitor the resource operations being performed in accordance with a hierarchy, and

detect a violation in the hierarchy, wherein the detecting of the violation is triggered with an occurrence of a change in the graph.

16. The apparatus of claim 15, wherein the processor is further to report the violation to a user.

17. The apparatus of claim 15, wherein the resource operations comprise one or more of the following:

resource acquisition operations and resource release operations.

18. The apparatus of claim 15, the processor is further to maintain a thread descriptor corresponding to each of the plurality of threads.

19. The apparatus of claim 15, wherein the graph comprises one or more lock acquisition nodes, each node representing one or more resources acquired by each thread of the plurality of threads.

20. The apparatus of claim 15, wherein the change in the graph comprises creating a new node in the graph, and adding the new node to the graph, the new node having a parent node.

21. The apparatus of claim 15, wherein the detecting of the violation comprises seeking one or more cycles satisfying a set of conditions in the graph, the set of conditions includes a plurality of conditions relating to activities of the nodes and the new node in the graph, wherein the violation is detected if the set of conditions is satisfied, and the violation is not detected if one or more of the set of conditions is not satisfied.

22. A machine-readable medium having stored thereon data representing sets of instructions which, when executed by a machine, cause the machine to:

construct a lock acquisition hierarchy graph to facilitate monitoring of resource operations corresponding to each of a plurality of threads of a multithreaded program;

monitor the resource operations being performed in accordance with a hierarchy; and

detect a violation in the hierarchy, wherein the detecting of the violation is triggered with an occurrence of a change in the graph.

23. The machine-readable medium of claim 22, wherein the sets of instructions which, when executed by the machine, further cause the machine to report the violation to a user.

24. The machine-readable medium of claim 22, wherein the resource operations comprise one or more of the following:

resource acquisition operations and resource release operations.

25. The machine-readable medium of claim 22, wherein the sets of instructions which, when executed by the machine, further cause the machine to maintain a thread descriptor corresponding to each of the plurality of threads.

26. The machine-readable medium of claim 22, wherein the graph comprises one or more lock acquisition nodes, each node representing one or more resources acquired by each thread of the plurality of threads.

27. The machine-readable medium of claim 22, wherein the change in the graph comprises creating a new node in the graph, and adding the new node to the graph, the new node having a parent node.

28. The machine-readable medium of claim 22, wherein the detecting of the violation comprises seeking one or more cycles satisfying a set of conditions in the graph, the set of conditions includes a plurality of conditions relating to activities of the nodes and the new node in the graph, wherein the violation is detected if the set of conditions is satisfied, and the violation is not detected if one or more of the set of conditions is not satisfied.