Detecting deadlocks in multithreaded programs

• US 7,093,262 B2
• Filed: 07/30/2002
• Issued: 08/15/2006
• 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.
• Primary Examiner(s): Thomson, William
• Assistant Examiner(s): Truong, LeChi
• Application Number:
  US10/207,262
• Publication Number:
  US 20040025164A1
• Time in Patent Office: 1,477 Days
• Field of Search: 719/310
• US Class Current: 719/310
• 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 computer implemented method to be performed by a processing system, the method comprising:

monitoring relationships between threads of a multithreaded program and mutually exclusive shared resources, the relationships created by resource operations performed by the threads, the resource operations related to at least one of the mutually exclusive shared resources;

generating at least one thread descriptor and at least one resource descriptor, based on the monitored relationships between the threads and the mutually exclusive shared resources, wherein the at least one thread descriptor corresponds to a thread in the multithreaded program and the at least one resource descriptor corresponds to a mutually exclusive shared resource; and

detecting deadlocks based on the relationships between the threads and the mutually exclusive shared resources, 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.

2. The method according to claim 1, wherein the operation of monitoring relationships comprises monitoring relationships created by at least one resource operation from the group consisting of:

a request operation;

an acquire operation; and

a release operation.

3. The method acording to claim 1, wherein the the operation of monitoring relationships comprises monitoring relationships created by at least one resource operation from the group consisting of:

a request-any operation; and

a request-all operation.

4. The method according to claim 1, wherein the operation of generating at least one thread descriptor comprises generating a thread descriptor to include at least one item from the group consisting 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.

5. The method according to claim 1, wherein the operation of generating at least one resource descriptor comprises generating a resource descriptor to include at least one item from the group consisting of:

information describing a feature 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.

6. The method according to claim 1, wherein the operation of generating at least one thread descriptor and at least one resource descriptor comprises:

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

if the thread acquires a shared resource, (a) creating an acquired link for the acquired shared resource in the thread descriptor of the thread, (b) creating an acquired-by link in the resource descriptor corresponding to the acquired shared resource, and (c) removing 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, (a) removing an acquired link for the released shared resource in the thread descriptor and (b) removing an acquired-by link in the resource descriptor corresponding to the released shared resource.

7. The method according to claim 1, 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

adding the thread descriptor to 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

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

8. The method according to claim 7, wherein the live queue has a head and an end, and the operation of 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 corresponds 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 corresponds 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; and

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.

9. The method according to claim 1, further comprising reporting a deadlock in response to detecting a deadlock.

10. The method according to claim 1, further comprising:

reporting threads as deadlocked in response to detecting a deadlock, wherein the operation of reporting threads as deadlocked 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.

11. An apparatus, comprising:

a tangible machine-accessible medium; and

instructions in the machine-accessible medium, wherein the instructions, when executed by a processing system, cause the processing system to perform operations comprising;

monitoring relationships between threads of a multithreaded program and mutually exclusive shared resources, the relationships created by resource operations performed by one or more of the threads, the resource operations related to at least one of the mutually exclusive shared resources;

generating at least one thread descriptor and at least one resource descriptor, based on the monitored relationships between the threads and the mutually exclusive shared resources, wherein the at least one thread descriptor corresponds to a thread in the multithreaded program and the at least one resource descriptor corresponds to a mutually exclusive shared resource; and

detecting deadlocks based on the relationships between the threads and the mutually exclusive shared resources, wherein the operation of 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.

12. An apparatus according to claim 11, wherein the instructions, when executed, cause the processing system to monitor relationships created by at least one resource operation from the group consisting of:

a request operation;

an acquire operation; and

a release operation.

13. An apparatus according to claim 11, wherein the instructions, when executed, cause the processing system to monitor relationships created by at least one resource operation from the group consisting of:

a request-any operation; and

a request-all operation.

14. An apparatus according to claim 11, wherein the instructions, when executed, create thread descriptors that include at least one item from the group consisting of:

information to identify an underlying thread;

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

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

15. An apparatus according to claim 11, wherein the instructions, when executed, create resource descriptors that include at least one item from the group consisting of:

information describing a feature of a corresponding resource;

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

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

16. An apparatus according to claim 11, comprising instructions which, when executed, perform operations comprising:

if a thread requests a shared resource, (a) creating a request link for the requested shared resource in the thread descriptor for the thread and (b) creating a requested-by link in the resource descriptor for the resource requested by the thread;

if the thread acquires a shared resource, (a) removing a request link from the thread descriptor and removing a requested-by link from the resource descriptor, (b) creating an acquired link for the acquired shared resource in the thread descriptor for the thread, and (c) creating an acquired-by link in the resource descriptor for the acquired shared resource; and

if the thread releases a shared resource, (a) removing an acquired link from the thread descriptor and (b) removing an acquired-by link from the resource descriptor.

17. An apparatus according to claim 11, wherein the instructions to construct a live queue and a dead set comprise instructions which, when executed, perform operations comprising:

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

adding the thread descriptor to the live queue if the number of request links in the thread descriptor is zero; and

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

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

18. An apparatus according to claim 17, wherein the live queue has a head and an end, and wherein the instructions to check deadlocks comprise instructions which, when executed, perform operations comprising:

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, (a) setting the number of acquired-by links in the resource descriptor to zero, and (b) 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 corresponds to a request-any operation, (a) setting the number of request links to zero in the thread descriptor, and (b) moving the thread descriptor from the dead set to the end of the live queue; and

if the requested-by link corresponds to a request-all operation, (a) decreasing the number of request links by one in the thread descriptor to generate an updated number of request links, and (b) 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

determining that deadlock exists if the dead set is not empty after all of the descriptors in the live queue have been processed.

19. An apparatus according to claim 11, further comprising instructions which, when executed, perform operations comprising:

reporting a deadlock in response to detecting a deadlock.

20. An apparatus according to claim 11, further comprising instructions which, when executed, perform operations comprising:

reporting threads as deadlocked in response to detecting a deadlock, wherein the operation of reporting threads as deadlocked comprises;

for each thread descriptor in the dead set;

for each request link that points to a resource descriptor for a shared resource, reporting the thread as deadlocked on the shared resource.

21. A processing system, comprising:

a processor;

a machine-accessible medium responsive to the processor; and

instructions in the machine-accessible medium, wherein the instructions, when executed by the processor, cause the processing system to perform operations comprising;

monitoring relationships between threads of a multithreaded program and mutually exclusive shared resources, the relationships created by resource operations performed by one or more of the threads, the resource operations related to at least one of the mutually exclusive shared resources;

generating at least one thread descriptor and at least one resource descriptor, based on the monitored relationships between the threads and the mutually exclusive shared resources, wherein the at least one thread descriptor corresponds to a thread in the multithreaded program and the at least one resource descriptor corresponds to a mutually exclusive shared resource; and

detecting deadlocks based on the relationships between the threads and the mutually exclusive shared resources, wherein the operation of 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.

22. A processing system according to claim 21, wherein the instructions, when executed, cause the processing system to monitor relationships created by at least one resource operation from the group consisting of:

a request operation;

an acquire operation; and

a release operation.

23. A processing system according to claim 21, wherein the instructions, when executed, cause the processing system to monitor relationships created by at least one resource operation from the group consisting of:

a request-any operation; and

a request-all operation.

24. A processing system according to claim 21, wherein the instructions, when executed, create thread descriptors that include at least one item from the group consisting of:

information to identify an underlying thread;

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

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

25. A processing system according to claim 21, wherein the instructions, when executed, create resource descriptors that include at least one item from the group consisting of:

information describing a feature of a corresponding resource;

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

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

26. A processing system according to claim 21, wherein the instructions, when executed, perform operations comprising:

if a thread requests a shared resource, (a) creating a request link for the requested shared resource in the thread descriptor for the thread and (b) creating a requested-by link in the resource descriptor for the resource requested by the thread;

if the thread acquires a shared resource, (a) removing a request link from the thread descriptor and removing a requested-by link from the resource descriptor, (b) creating an acquired link for the acquired shared resource in the thread descriptor for the thread, and (c) creating an acquired-by link in the resource descriptor for the acquired shared resource; and

if the thread releases a shared resource, (a) removing an acquired link from the thread descriptor and (b) removing an acquired-by link from the resource descriptor.

27. A processing system according to claim 21, wherein the instructions to construct a live queue and a dead set comprise instructions which, when executed, perform operations comprising:

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

adding the thread descriptor to the live queue if the number of request links in the thread descriptor is zero; and

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

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

28. A processing system according to claim 27, wherein the live queue has a head and an end, and wherein the instructions to check deadlocks comprise instructions which, when executed, perform operations comprising:

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, (a) setting the number of acquired-by links in the resource descriptor to zero, and (b) 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 corresponds to a request-any operation, (a) setting the number of request links to zero in the thread descriptor, and (b) moving the thread descriptor from the dead set to the end of the live queue; and

if the requested-by link corresponds to a request-all operation, (a) decreasing the number of request links by one in the thread descriptor to generate an updated number of request links, and (b) 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

determining that deadlock exists if the dead set is not empty after all of the descriptors in the live queue have been processed.

29. A processing system according to claim 21, wherein the instructions, when executed, perform operations comprising:

reporting a deadlock in response to detecting a deadlock.

30. A processing system according to claim 21, wherein the instructions, when executed, perform operations comprising:

reporting threads as deadlocked in response to detecting a deadlock, wherein the operation of reporting threads as deadlocked comprises;

for each thread descriptor in the dead set;

for each request link that points to a resource descriptor for a shared resource, reporting the thread as deadlocked on the shared resource.