Method and system for deadlock detection in a distributed environment

• US 7,735,089 B2
• Filed: 03/08/2005
• Issued: 06/08/2010
• 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
• Primary Examiner(s): An; Meng-Ai
• Assistant Examiner(s): Lee; Adam
• Application Number:
  US11/075,068
• Publication Number:
  US 20060206901A1
• Time in Patent Office: 1,918 Days
• Field of Search: 710/200, 707/8, 718/100, 718/108
• US Class Current: 718/108
• 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 in a distributed system, comprising:

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

if the waiting time has exceeded the timeout time, initiating a plurality of deadlock searches, wherein the initiating said plurality of deadlock searches includes obtaining a timestamp indicating a staff time of said initiating;

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;

wherein

the method is performed by one or more computing devices.

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

3. A computer-readable medium bearing instructions for deadlock detection, said instructions being arranged, upon execution, to cause one or more processors to perform steps of:

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

if the waiting time has exceeded the timeout time, initiating a plurality of deadlock searches, wherein the initiating said plurality of deadlock searches includes obtaining a timestamp indicating a start time of said initiating;

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.

7. The computer-readable storage of claim 3, wherein the terminating further includes increasing the search duration time associated with the lock request.

4. 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;

if the waiting time has exceeded the threshold timeout value, initiating a particular type of parallel search, wherein the particular type of parallel search is either a parallel forward search for deadlock or a parallel backward search for deadlock, wherein selecting the type of parallel search is based on a size of a convert queue of said requested resource;

wherein a granted queue includes a granted resource lock associated with a first process which has been granted a lock on the requested object, and wherein the convert queue includes a waiting resource lock which is associated with a second process that has requested a lock on the requested object that is incompatible with the granted resource lock; and

wherein the method is performed by one or more computing devices.

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

6. A computer-readable storage bearing instructions for deadlock detection, said instructions being arranged, upon execution, to cause one or more processors to perform steps of:

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

if the waiting time has exceeded the threshold timeout value, initiating a particular type of parallel search, wherein the particular type of parallel search is either a parallel forward search for deadlock or a parallel backward search for deadlock, wherein selecting the type of parallel search is based on a size of a convert queue of said requested resource; and

wherein a granted queue includes a granted resource lock associated with a first process which has been granted a lock on the requested object, and wherein the convert queue includes a waiting resource lock which is associated with a second process that has requested a lock on the requested object that is incompatible with the granted resource lock.

8. The computer-readable storage of claim 6, wherein the threshold timeout value is adjusted based on the statistics.