Method and system for deadlock detection in a distributed environment

• US 20060206901A1
• Filed: 03/08/2005
• Published: 09/14/2006
• Est. Priority Date: 03/08/2005
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Chan, Wilson
• Granted Patent: US 7,735,089 B2
• Time in Patent Office: Days
• US Class Current: 718/107
• CPC Class Codes: G06F 2209/523 Mode
• CPC Class Codes: G06F 9/524 Deadlock detection or avoidance

Abstract

A method of deadlock detection is disclosed which adjusts the detection technique based on statistics maintained for tracking the number of actual deadlocks that are detected in a distributed system, and for which types of locks are most frequently involved in deadlocks. When deadlocks occur rarely, the deadlock detection may be tuned down, for example, by reducing a threshold value which determines timeouts for waiting lock requests. When it is determined that actual deadlocks are detected frequently, the processing time for deadlock detection may be reduced, for example, by using parallel forward or backward search operations and/or by according higher priority in deadlock detection processing to locks which are more likely to involve deadlocks.

Claims

1. A method of deadlock detection, comprising:

collecting statistics of frequency of deadlocks detected in a system;

adjusting a threshold timeout value for a lock based on the statistics; and

if a waiting time associated with the lock exceeds the threshold timeout value, initiating a deadlock detection based on the lock.

2. A method according to claim 1, wherein the collecting statistics includes collecting statistics of frequency of deadlocks detected classified according to deadlocks detected corresponding to a lock type associated with the deadlocks detected or an instance type associated with the deadlocks detected.

3. A method according to claim 2, further including determining a priority of initiating the deadlock detection, based on the classified frequency of deadlocks.

4. A method according to claim 1, wherein the collecting statistics includes collecting statistics of frequency of deadlocks detected classified according to deadlocks detected corresponding to a lock type associated with the deadlocks detected or an instance type associated with the deadlocks detected.

5. A method according to claim 1, wherein the deadlock detection includes detecting a cycle.

6. A method according to claim 1, wherein the deadlock detection includes a parallel search or a single path, single direction search over a plurality of nodes in a distributed system.

7. A computer-readable medium bearing instructions for deadlock detection, said instructions being arranged, upon execution, to cause one or more processors to perform the steps of a method according to claim 1.

8. A method of deadlock detection in a distributed system, comprising:

determining whether a waiting time for a lock request has exceeded a predetermined timeout time; and

if the waiting time has exceeded the timeout time, initiating a plurality of deadlock searches.

9. A method according to claim 8, wherein the initiating said plurality of deadlock searches includes obtaining a timestamp indicating a start time of said initiating, and

wherein said method further includes terminating the plurality of deadlock searches if it is determined that an elapsed time for the plurality of deadlock searches has exceeded a predetermined search duration time associated with the lock request, based on the obtained timestamp.

10. A method according to claim 9, wherein the terminating further includes increasing the search duration time associated with the lock request.

11. A computer-readable medium bearing instructions for deadlock detection, said instructions being arranged, upon execution, to cause one or more processors to perform the steps of a method according to claim 8.

12. A method of deadlock detection, comprising:

determining whether a waiting time associated with a lock for a requested resource has exceeded a threshold timeout value; and

if the waiting time has exceeded the threshold timeout value, initiating a forward search for deadlock or initiating a backward search for deadlock based on statistics collected on a frequency of detected deadlocks.

13. A method according to claim 12, wherein the threshold timeout value is adjusted based on the statistics.

14. A computer-readable medium bearing instructions for deadlock detection, said instructions being arranged, upon execution, to cause one or more processors to perform the steps of a method according to claim 12.

15. A computer-readable medium bearing an instance of a distributed lock manager including a resource object having a granted queue and a convert queue, and a communication means for communicating statistical information regarding a frequency of detected deadlocks associated with a waiting resource lock included in the convert queue, wherein a frequency of initiating deadlock detection searches is adjusted based on the statistical information.

16. A computer-readable medium according to claim 15, wherein the granted queue includes a granted resource lock associated with a first process which has been granted a lock on the resource object, and wherein the convert queue includes the waiting resource lock which is associated with a second process that has requested a lock on the resource object that is incompatible with the granted resource lock.

17. A computer-readable medium according to claim 15, further bearing instructions associated with one of the deadlock detection searches, including instructions for sending messages to all instances of processes owning granted resource locks included in the granted queue, the messages including instructions to initiate deadlock detection searches on each instance.