Detecting deadlocks in multithreaded programs

• US 20040025164A1
• Filed: 07/30/2002
• Published: 02/05/2004
• Est. Priority Date: 07/30/2002
• Status: Active Grant

• Current Assignee: Sony Corporation Of America (Sony Group Corp.)
• Original Assignee: Intel Corporation
• Inventors: Ma, Zhiqiang, Petersen, Paul M.
• Granted Patent: US 7,093,262 B2
• Time in Patent Office: Days
• US Class Current: 718/107
• CPC Class Codes: G06F 11/362 Software debugging
• CPC Class Codes: G06F 9/524 Deadlock detection or avoidance

Abstract

An arrangement is provided for detecting deadlocks in a multithreaded program. When a thread in a multithreaded program performs a resource operation related to a mutually exclusive shared resource, it creates relationships between the thread and the shared resource as well as between the thread and other threads of the multithreaded program. Such created relationships are monitored and used to detect deadlocks.

Claims

1. A method, comprising:

performing, by a thread in a multithreaded program, a resource operation related to at least one mutually exclusive shared resource;

monitoring the relationships created by the resource operation between the thread and the at least one mutually exclusive shared resource and other threads in the multithreaded program;

detecting deadlocks based on the relationships between the thread and the at least one mutually exclusive shared resource and the other threads of the multithreaded program.

2. The method according to claim 1, wherein said detecting deadlocks comprises:

constructing a live queue and a dead set based on at least one thread descriptor, each of which corresponding to a thread in the multithreaded program, and at least one resource descriptor, each of which corresponding to a mutually exclusive shared resource, the at least one thread descriptor and the at least one resource descriptor being established based on relationships between threads and shared resources created during resource operations; and

checking deadlocks based on the live queue and the dead set.

3. A method for detecting deadlocks in a multithreaded program, comprising:

monitoring shared resource operations performed by a plurality of threads in a multithreaded program;

updating at least one thread descriptor associated with the plurality of threads and at least one resource descriptor associated with at least one shared resource based on the monitored shared resource operations; and

detecting deadlocks based on the updated thread descriptors and the resource descriptors.

4. The method according to claim 3, wherein shared resource operations include at least one of:

a request operation;

an acquire operation; and

a release operation.

5. The method acording to claim 4, wherein the request operation includes:

a request-any operation; and

a request-all operation.

6. The method according to claim 5, wherein each of the at least one thread descriptor includes at least one of:

information specifying an underlying thread;

zero or more request links, each pointing to a corresponding resource descriptor related to a resource requested by the underlying thread; and

zero or more acquired links, each pointing to a corresponding resource descriptor related to a resource acquired by the underlying thread.

7. The method according to claim 6, wherein each of the at least one resource descriptor includes at least one of:

information describing features of a corresponding resource;

a requested-by link pointing to a thread descriptor describing a thread that requested the corresponding resource; and

an acquired-by link pointing to a thread descriptor describing a thread that acquired the corresponding resource.

8. The method according to claim 7, wherein said updating comprises:

if a thread requests a shared resource via the request operation, creating, for the requested shared resource, a request link in the thread descriptor of the thread and a requested-by link in the resource descriptor corresponding to the resource requested by the thread;

if the thread acquires a shared resource via the acquire operation, creating, for the acquired shared resource, an acquired link in the thread descriptor of the thread and an acquired-by link in the resource descriptor corresponding to the acquired shared resource, after removing at least one corresponding pair of a request link in the thread descriptor and an associated requested-by link in the resource descriptor; and

if the thread releases a shared resource via the release operation, removing, for the released shared resource, an acquired link in the thread descriptor and an acquired-by link in the resource descriptor corresponding to the released shared resource.

9. The method according to claim 8, wherein said detecting deadlocks comprises:

constructing a live queue and a dead set based on the at least one thread descriptor and the at least one resource descriptor; and

checking deadlock based on the live queue and the dead set.

10. The method according to claim 9, wherein said constructing comprises:

initializing the live queue and the dead set;

for each thread descriptor corresponding to a thread;

adding the thread descriptor to the dead set if the number of request links in the thread descriptor is not zero, and

inserting the thread descriptor to the end of the live queue if the number of request links in the thread descriptor is zero;

for each resource descriptor corresponding to a shared resource;

adding the resource descriptor to the dead set if the number of acquired-by links in the resource descriptor is not zero, and

inserting the resource descriptor to the end of the live queue if the number of acquired-by links in the resource descriptor is zero.

11. The method according to claim 10, wherein said checking deadlocks comprises:

for each descriptor in the live queue, starting from the head of the live queue;

if the descriptor is a thread descriptor;

for each resource descriptor linked via an acquired link in the thread descriptor;

setting the number of acquired-by links in the resource descriptor to zero, and

moving the resource descriptor from the dead set to the end of the live queue;

if the descriptor is a resource descriptor;

for each thread descriptor linked via a requested-by link in the resource descriptor;

if the requested-by link corresponding to a request-any operation;

setting the number of request links to zero in the thread descriptor, and

moving the thread descriptor from the dead set to the end of the live queue;

if the requested-by link corresponding to a request-all operation;

decreasing the number of request links by one in the thread descriptor to generate an updated number of request links;

moving the thread descriptor from the dead set to the end of the live queue when the updated number of request links reaches zero; and

indicating a deadlock situation if the dead set is not empty after all of the descriptors in the live queue are processed.

12. The method according to claim 9, further comprising reporting deadlocks when a deadlock situation is indicated.

13. The method according to claim 12, wherein said reporting comprises:

for each thread descriptor in the dead set;

for each request link in the thread descriptor pointing to a resource descriptor corresponding to a shared resource, indicating the thread being deadlocked on the shared resource.

14. A system, comprising:

at least one shared resource;

a multithreaded program having a plurality of threads that share the at least one shared resource through resource operations; and

a dynamic deadlock monitoring and detection mechanism capable of dynamically detecting a deadlock situation in which a thread is deadlocked on a shared resource.

15. The system according to claim 14, wherein the dynamic deadlock monitoring and detection mechanism includes:

a resource operation monitoring mechanism capable of monitoring the resource operations performed by the plurality of threads; and

a deadlock detection mechanism capable of detecting a deadlock situation in which a thread is deadlocked on a shared resource.

16. The system according to claim 15, wherein the resource operation monitoring mechanism comprises:

an operation observation mechanism capable of observing the resource operations performed by the plurality of threads with respect to the shared resources;

at least one resource descriptor, each of which corresponding to a shared resource;

a plurality of thread descriptors, each of which corresponding to a thread of the multithreaded program;

a resource descriptor update mechanism capable of updating a resource descriptor based on the observed resource operations; and

a thread descriptor update mechanism capable of updating a thread descriptor based on the observed resource operations.

17. The system according to claim 16, wherein the deadlock detection mechanism comprises:

a live queue;

a dead set;

a construction mechanism capable of constructing the live queue and the dead set based on the resource descriptors and the thread descriptors; and

a deadlock detector capable of detecting deadlocks based on information contained in the live queue and the dead set.

18. A dynamic deadlock monitoring and detection mechanism comprising:

a resource operation monitoring mechanism capable of monitoring the resource operations performed by the plurality of threads; and

a deadlock detection mechanism capable of detecting a deadlock situation in which a thread is deadlocked on a shared resource.

19. The mechanism according to claim 18, wherein the resource operation monitoring mechanism comprises:

an operation observation mechanism capable of observing the resource operations performed by the plurality of threads with respect to the shared resources;

at least one resource descriptor, each of which corresponding to a shared resource;

a plurality of thread descriptors, each of which corresponding to a thread of the multithreaded program;

a resource descriptor update mechanism capable of updating a resource descriptor based on the observed resource operations; and

a thread descriptor update mechanism capable of updating a thread descriptor based on the observed resource operations.

20. The mechanism according to claim 19, wherein the deadlock detection mechanism comprises:

a live queue;

a dead set;

a construction mechanism capable of constructing the live queue and the dead set based on the resource descriptors and the thread descriptors; and

a deadlock detector capable of detecting deadlocks based on information contained in the live queue and the dead set.

21. The mechanism according to claim 18, further comprising a deadlock reporting mechanism capable of reporting that a thread is deadlocked on a shared resource.

22. An article comprising a storage medium having stored thereon instructions that, when executed by a machine, result in the following:

performing, by a thread in a multithreaded program, a resource operation related to at least one mutually exclusive shared resource;

monitoring the relationships created by the resource operation between the thread and the at least one mutually exclusive shared resource and other threads in the multithreaded program;

detecting deadlocks based on the relationships between the thread and the at least one mutually exclusive shared resource and the other threads of the multithreaded program.

23. The article comprising a storage medium having stored thereon instructions according to claim 22, wherein said detecting deadlock comprises:

constructing a live queue and a dead set based on at least one thread descriptor, each of which corresponding to a thread in the multithreaded program, and at least one resource descriptor, each of which corresponding to a mutually exclusive shared resource, the at least one thread descriptor and the at least one resource descriptor being established based on relationships between threads and shared resources created during resource operations; and

checking deadlocks based on the live queue and the dead set.

24. An article comprising a storage medium having stored thereon instructions for detecting deadlocks in a multithreaded program that, when executed by a machine, result in the following:

monitoring shared resource operations performed by a plurality of threads in a multithreaded program;

updating at least one thread descriptor associated with the plurality of threads and at least one resource descriptor associated with at least one shared resource based on the minotored shared resource operations; and

detecting deadlocks based on the updated thread descriptors and the resource descriptors.

25. The article comprising a storage medium having stored thereon instructions according to claim 24, wherein

each of the at least one thread descriptor includes at least one of:

information specifying an underlying thread,

zero or more request links, each pointing to a corresponding resource descriptor related to a resource requested by the underlying thread, and

zero or more acquired links, each pointing to a corresponding resource descriptor related to a reource acquired by the underlying thread;

each of the at least one resource descriptor includes at least one of;

information describing features of a corresponding resource,

a requested-by link pointing to a thread descriptor describing a thread that requested the corresponding resource, and

an acquired-by link pointing to a thread descriptor describing a thread that acquired the corresponding resource.

26. The article comprising a storage medium having stored thereon instructions according to claim 25, wherein said updating comprises:

if a thread requests a shared resource via the request operation, creating, for the requested shared resource, a request link in the thread descriptor of the thread and a requested-by link in the resource descriptor corresponding to the resource requested by the thread;

if the thread acquires a shared resource via the acquire operation, creating, for the acquired shared resource, an acquired link in the thread descriptor of the thread and an acquired-by link in the resource descriptor corresponding to the acquired shared resource, after removing at least one corresponding pair of a request link in the thread descriptor and an associated requested-by link in the resource descriptor; and

if the thread releases a shared resource via the release operation, removing, for the released shared resource, an acquired link in the thread descriptor and an acquired-by link in the resource descriptor corresponding to the released shared resource.

27. The article comprising a storage medium having stored thereon instructions according to claim 26, wherein said detecting deadlocks comprises:

constructing a live queue and a dead set based on the at least one thread descriptor and the at least one resource descriptor; and

checking deadlocks based on the live queue and the dead set.

28. The article comprising a storage medium having stored thereon instructions according to claim 27, wherein said constructing comprises:

initializing the live queue and the dead set;

for each thread descriptor corresponding to a thread;

adding the thread descriptor to the dead set if the number of request links in the thread descriptor is not zero, and

inserting the thread descriptor to the end of the live queue if the number of request links in the thread descriptor is zero;

for each resource descriptor corresponding to a shared resource;

adding the resource descriptor to the dead set if the number of acquired-by links in the resource descriptor is not zero, and

inserting the resource descriptor to the end of the live queue if the number of acquired-by links in the resource descriptor is zero.

29. The article comprising a storage medium having stored thereon instructions according to claim 28, wherein said checking deadlocks comprises:

for each descriptor in the live queue, starting from the head of the live queue;

if the descriptor is a thread descriptor;

for each resource descriptor linked via an acquired link in the thread descriptor;

setting the number of acquired-by links in the resource descriptor to zero, and

moving the resource descriptor from the dead set to the end of the live queue;

if the descriptor is a resource descriptor;

for each thread descriptor linked via a requested-by link in the resource descriptor;

if the requested-by link corresponding to a request-any operation;

setting the number of request links to zero in the thread descriptor, and

moving the thread descriptor from the dead set to the end of the live queue;

if the requested-by link corresponding to a request-all operation;

decreasing the number of request links by one in the thread descriptor to generate an updated number of request links;

moving the thread descriptor from the dead set to the end of the live queue when the updated number of request links reaches zero; and

indicating a deadlock situation if the dead set is not empty after all of the descriptors in the live queue are processed.

30. The article comprising a storage medium having stored thereon instructions according to claim 29, the instructions, when executed by a machine, further result in the following:

if a deadlock situation is indicated, for each thread descriptor in the dead set;

for each request link in the thread descriptor pointing to a resource descriptor corresponding to a shared resource, indicating the thread being deadlocked on the shared resource.