Method and system for deadlock detection and avoidance

• US 6,983,461 B2
• Filed: 02/07/2002
• Issued: 01/03/2006
• Est. Priority Date: 07/27/2001
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Hutchison, Gordon Douglas, Peacock, Brian David
• Primary Examiner(s): An, Meng-Al T.
• Assistant Examiner(s): Vo, Lilian
• Application Number:
  US10/068,337
• Publication Number:
  US 20030023656A1
• Time in Patent Office: 1,426 Days
• Field of Search: 718/100, 718/104, 718/102, 718/106, 718/107, 707/8, 710/200
• US Class Current: 718/104
• CPC Class Codes: G06F 9/524 Deadlock detection or avoidance
• CPC Class Codes: Y10S 707/99938 Concurrency, e.g. lock management in shared database

Abstract

The invention relates to a method of operating a computer system supporting multiple processes, and the intention is to avoid deadlock (an example of which is where process A owns resource A, and is waiting on resource B, but resource B is currently owned by process B, which is waiting on resource A). The method commences with receipt of a request from a first process for access to a resource of said computer system. If the requested resource is currently unavailable because it is currently owned by another process, the system examines which processes own or are waiting for other resources on the system, in order to try to detect whether adding the first process to a queue for the requested resource would cause a deadlock situation to arise. If so, the system will typically throw an exception, or possibly return an error to the request for the resource.

Claims

1. A computer implemented method in a virtual machine layer of a computer system supporting multiple processes, said method including the steps of:

utilizing a set of monitors for controlling access to resources of the computer system, whereby a given process has to enter a given monitor in order to access a corresponding given resource, and has to join an entry queue for the given monitor if the given resource is currently owned by another process for which the given process has entered;

responsive to a predetermined condition of a requesting process requesting to enter a requested monitor, from the set of monitors, currently owned by a different process, examining queued processes queued on at least one of the set of monitors to determine whether there is a deadlock situation by detecting a cyclic dependency at a time a given dependency is created, wherein the examination of queued processes queued on the at least one of the set of monitors to determine whether there is the deadlock situation includes those processes having a conditional wait on at least one of the set of monitors; and

if the deadlock situation is found, returning information about an identity of i) identified processes from the examined queued processes, and ii) identified monitors from the set of monitors, involved in the deadlock situation with an exception returned to an application while the application is running on the virtual machine layer of the computer system thereby enabling the application to resolve the deadlock situation by having at least one of the identified processes release at least one of the identified monitors that the at least one identified process owns but is not currently using for continued processing by the application without the deadlock situation.

2. The computer implemented method of claim 1, wherein the examined queued processes involved in said examining step are determined iteratively based on at least one of the multiple processes queued on the requested monitor, and at least one of the multiple processes queued on other monitors owned by examined queued processes already determined to be involved in said examining step.

3. The computer implemented method of claim 1, wherein the system maintains a global table of contended monitors, a given one of the contended monitors being contended if there is a given queued process in its entry queue, the table further identifying those processes which own or are queued on contended monitors.

4. The computer implemented method of claim 1, wherein said exception is returned to the requesting process.

5. The computer implemented method of claim 1, wherein the exception is returned to all identified processes involved in the deadlock situation.

6. The computer implemented method of claim 1, wherein the examination of queued processes queued on at least one of the set of monitors includes those monitors on at least one remote machine.

7. A computer system having a virtual machine layer between applications executing on the computer system and an operating system of the computer system, the computer system having means for supporting multiple processes, the computer system comprising:

a set of monitors for controlling access to a plurality of resources of the computer system, whereby a given process has to enter a given monitor in order to access a corresponding given resource;

an entry queue for the each given monitor if the corresponding given resource is currently owned by another process for which the given process has entered;

means, within the virtual machine layer of the computer system, responsive to a predetermined condition of a requesting process requesting to enter a requested monitor, from the set of monitors, currently owned by a different process for examining queued processes queued on at least one of the set of monitors to determine whether there is a deadlock situation by detecting a cyclic dependency at a time a given dependency is created, wherein the examination of queued processes queued on the at least one of the set of monitors to determine whether there is the deadlock situation includes those processes having a conditional wait on at least one of the set of monitors; and

means, responsive to the deadlock situation being found, for returning information about an identity of the i) identified processes from the examined queued processes, and ii) identified monitors the set of monitors, involved in the deadlock situation with an exception returned to a given one of the given applications while the given application is running on the virtual machine layer of the computer system thereby enabling the given application to resolve the deadlock situation by having at least one of the identified processes release at least one of the identified monitors that the at least one identified process owns but is not currently using for continued processing by the application without the deadlock situation.

8. The system of claim 7, wherein the examined queued processes to be examined are determined iteratively based on at least one of the multiple processes queued on the requested monitor, and at least one of the multiple processes queued on other monitors owned by examined queued processes already determined to be examined.

9. The system of claim 7, wherein the system maintains a global table of contended monitors, a given one of the contended monitors being contended if there is a given queued process in its entry queue, the table further identifying those processes which own or are queued on contended monitors.

10. The system of claim 7, wherein said exception is returned to the requesting process.

11. The system of claim 7, wherein the exception is returned to all identified processes involved in the deadlock situation.

12. The system of claim 7, wherein the examination of queued processes queued on at least one of the set of monitors includes those monitors on at least one remote machine.

13. A computer program product comprising program instructions encoded in machine readable firm on a medium, said instructions when loaded into a computer system, having means to support multiple processes, causing a virtual machine layer of the computer system to perform the steps of:

utilizing a set of monitors for controlling access to resources of the computer system, whereby a given process has to enter a given monitor in order to access a corresponding given resource, and has to join an entry queue for the given monitor if the given resource is currently owned by another process for which the given process has entered;

responsive to a predetermined condition of a requesting process requesting to enter a requested monitor, from the set of monitors, currently owned by a different process, examining queued processes queued on at least one of the set of monitors to determine whether there is a deadlock situation by detecting a cyclic dependency at a time a given dependency is created; and

if the deadlock situation is found, returning information about an identity of i) identified processes from the examined queued processes, and ii) identified monitors from the set of monitors, involved in the deadlock situation with an exception returned to an application while the application is running on the virtual machine layer of the computer system thereby enabling the application to resolve the deadlock situation by having at least one of the identified processes release at least one of the identified monitors that the at least one identified process owns but is not currently using for continued processing by the application without the deadlock situation.

14. The computer program product of claim 13, wherein the examined queued processes involved in said examining step are determined iteratively based on at least one of the multiple processes queued on the requested monitor, and at least one of the multiple processes queued on other monitors owned by examined queued processes already determined to be involved in said examining step.

15. The computer program product of claim 13, wherein the system maintains a global table of contended monitors, a given one of the contended monitors being contended if there is a given queued process in its entry queue, the table further identifiying those processes which own or are queued on contended monitors.

16. The computer program product of claim 13, wherein said exception is returned to the requesting process.

17. The computer program product of claim 13, wherein the exception is returned to all identified processes involved in the deadlock situation.

18. The computer program product of claim 13, wherein the examination of queued processes queued on at least one of the set of monitors includes those monitors on at least one remote machine.