Deadlock resolution through lock requeuing

• US 20040199734A1
• Filed: 04/03/2003
• Published: 10/07/2004
• Est. Priority Date: 04/03/2003
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Lee, Jaebock, Rajamani, Kumar
• Granted Patent: US 7,337,290 B2
• Time in Patent Office: Days
• US Class Current: 711/163
• CPC Class Codes: G06F 2209/523 Mode
• CPC Class Codes: G06F 9/524 Deadlock detection or avoidance
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

A method and system for using a requeueing procedure to resolve deadlocks in a computing system is disclosed. A request for a resource may be requeued after a designated period of time or wait cycles if it is blocked from being granted. For example, a request for exclusive ownership of a resource could be requeued if it cannot be granted within an appropriate period of time. These types of requests are requeued to allow other requests for the same resource to move ahead in the wait queue. This allows other grantable requests behind the blocked request to be immediately granted. Using this approach, it is possible that allowing the other requests behind the timed-out request to move ahead in the queue will set off a chain reaction of accesses to resources which will clear the deadlock situation that initially causes the requeued request(s) to be blocked.

Claims

1. A method for resolving a deadlock in a computing system, comprising:

identifying a first request for an exclusive lock that is associated with a resource, the first request forming part of a deadlock in which the deadlock cannot be resolved unless the first request is granted;

allowing a period of time for the first request to be granted;

if the first request cannot be granted during the period of time, then identifying whether a second request for a shared lock exists behind the first request in a lock request queue; and

reordering the lock request queue to place the second request ahead of the first request in the lock request queue, wherein the present configuration of locks allows the second request to be granted, and the granting of the second request initiates a chain of resource accesses that resolves the deadlock and allows the first request to be granted.

2. The method of claim 1 in which the period of time comprises a number of wait cycles.

3. The method of claim 1 in which the deadlock involves multiple classes of resource and lock spaces.

4. The method of claim 3 in which the multiple classes of resources comprises a first class of resources directed to metadata and a second class of resources directed to data.

5. The method of claim 1 further comprising:

sending a message to a distributed system identify the reordering step.

6. The method of claim 5 in which the reordering step is performed at other instances in the distributed system.

7. The method of claim 5 further comprising:

determining whether a failure has occurred during the reordering step.

8. The method of claim 7 in which a flag is set when the message has been successfully sent, wherein the flag is checked to determine whether a failure has occurred.

9. The method of claim 7 in which the message is resent if the failure has been identified.

10. The method of claim 1 in which the first request is placed at the end of the lock request queue.

11. The method of claim 1 in which the first request is not queued behind any other requests for an exclusive lock.

12. The method of claim 1 in which multiple lock requested are queued ahead of the first request.

13. A method for resolving a deadlock in a computing system, comprising:

identifying a first request that is associated with a resource, the first request forming part of a deadlock;

allowing a period of time for the first request to be granted;

if the first request cannot be granted during the period of time, then identifying whether a second request exists behind the first request in a lock request queue; and

reordering the lock request queue to place the second request ahead of the first request in the lock request queue, wherein the reordering action allows the second request to be granted ahead of the first request, and the granting of the second request initiates a chain of resource accesses that resolves the deadlock and allows the first request to be granted.

14. The method of claim 13 in which the period of time comprises a number of wait cycles.

15. The method of claim 13 in which the deadlock involves multiple classes of resource and lock spaces.

16. The method of claim 15 in which the multiple classes of resources comprises a first class of resources directed to metadata and a second class of resources directed to data.

17. The method of claim 13 further comprising:

sending a message to a distributed system identify the reordering step.

18. The method of claim 17 in which the reordering step is performed at other instances in the distributed system.

19. The method of claim 17 further comprising:

determining whether a failure has occurred during the reordering step.

20. The method of claim 19 in which a flag is set when the message has been successfully sent, wherein the flag is checked to determine whether a failure has occurred.

21. The method of claim 19 in which the message is resent if the failure has been identified.

22. The method of claim 13 in which the first request is placed at the end of the lock request queue.

23. The method of claim 13 in which the first request is not queued behind any other requests for an exclusive lock.

24. The method of claim 13 in which multiple lock requested are queued ahead of the first request.

25. The method of claim 13 in which a determination is made whether the second request is otherwise grantable if queued ahead of the first request.

26. The method of claim 25 in which multiple grantable requests are queued ahead of the first request.

27. A computer program product comprising a computer usable medium having executable code to execute a process for resolving a deadlock in a computing system, the process comprising the steps of:

identifying a first request that is associated with a resource, the first request forming part of a deadlock;

allowing a period of time for the first request to be granted;

if the first request cannot be granted during the period of time, then identifying whether a second request exists behind the first request in a lock request queue; and

reordering the lock request queue to place the second request ahead of the first request in the lock request queue, wherein the reordering action allows the second request to be granted ahead of the first request, and the granting of the second request initiates a chain of resource accesses that resolves the deadlock and allows the first request to be granted.

28. A system for resolving a deadlock in a computing system, comprising:

means for identifying a first request that is associated with a resource, the first request forming part of a deadlock;

means for allowing a period of time for the first request to be granted;

means for identifying whether a second request exists behind the first request in a lock request queue if the first request cannot be granted during the period of time; and

means for reordering the lock request queue to place the second request ahead of the first request in the lock request queue, wherein the reordering action allows the second request to be granted ahead of the first request, and the granting of the second request initiates a chain of resource accesses that resolves the deadlock and allows the first request to be granted.

29. A computer program product comprising a computer usable medium having executable code to execute a process for resolving a deadlock in a computing system, the process comprising the steps of:

identifying a first request for an exclusive lock that is associated with a resource, the first request forming part of a deadlock in which the deadlock cannot be resolved unless the first request is granted;

allowing a period of time for the first request to be granted;

if the first request cannot be granted during the period of time, then identifying whether a second request for a shared lock exists behind the first request in a lock request queue; and

reordering the lock request queue to place the second request ahead of the first request in the lock request queue, wherein the present configuration of locks allows the second request to be granted, and the granting of the second request initiates a chain of resource accesses that resolves the deadlock and allows the first request to be granted.

30. A system for resolving a deadlock in a computing system, comprising:

means for identifying a first request for an exclusive lock that is associated with a resource, the first request forming part of a deadlock in which the deadlock cannot be resolved unless the first request is granted;

means for allowing a period of time for the first request to be granted;

means for identifying whether a second request for a shared lock exists behind the first request in a lock request queue if the first request cannot be granted during the period of time; and

means for reordering the lock request queue to place the second request ahead of the first request in the lock request queue, wherein the present configuration of locks allows the second request to be granted, and the granting of the second request initiates a chain of resource accesses that resolves the deadlock and allows the first request to be granted.