System and method for deadlock management in database systems with demultiplexed connections

• US 20020042850A1
• Filed: 05/31/2001
• Published: 04/11/2002
• Est. Priority Date: 10/06/2000
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Huras, Matthew A., Xue, Xun, Zheng, Roger L., McKeough, Sean W., Vincent, Timothy J.
• Granted Patent: US 6,807,540 B2
• Time in Patent Office: Days
• US Class Current: 719/330
• CPC Class Codes: G06F 16/2343 Locking methods, e.g. distributed locking or locking implementation details
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms
• CPC Class Codes: Y10S 707/99938 Concurrency, e.g. lock management in shared database
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

A system and method for managing deadlocks in a database management system (DBMS) for a demultiplexed database system having worker agents and applications associated with, and disassociated from, the worker agents is disclosed. The DBMS of the present invention supports applications that are capable of holding and retaining locks on database resources while disassociated from worker agents. The system and method of the present invention includes an application scheduler for managing requests for access to the database, and a deadlock detector for identifying a deadlock. According to one embodiment of the present invention, the application scheduler assigns one worker agent to an application requesting access to a database resource, assigns a flag to an application holding a lock on the database resource while disassociated from a worker agent, and in cooperation with the deadlock detector, resolves the deadlock between the application requesting access and the flagged application holding the lock.

Claims

1. A method for managing requests for access to database resources in a database system, the database system comprising a plurality of applications capable of requesting access to a plurality of database resources and capable of holding locks on the plurality of database resources, and the database system further comprising an application scheduler for managing requests from the plurality of applications for access to database resources, the method comprising the steps of:

a) assigning a worker agent from a plurality of worker agents to an application by the application scheduler;

b) identifying a deadlock via a deadlock detector coupled to the application scheduler, the deadlock being between an application disassociated from the worker agent while holding a lock on a database resource and another application requesting access to the database resource; and

c) resolving the deadlock.

2. The method of claim 1, wherein the plurality of worker agents includes normal worker agents and overflow worker agents, and assigning step a) further includes:

(a1) marking an application with a flag value based on an existing application flag value and on a state of applications requesting and holding locks on database resources,

(a2) assigning a normal worker agent or an overflow worker agent to the application, or placing the application on a wait queue or on a priority queue, based on the application flag value.

3. The method of claim 2, wherein identifying step (b) further includes:

(b1) polling an application; and

(b2) declaring a deadlock where the application has a specified flag value and the application holds a lock on a database resource requested by another application.

4. The method of claim 3, wherein the marking step (a I) comprising the steps of:

marking an application with a flag value W where the application becomes disassociated from a worker agent and holds a lock on a database resource;

marking an application with a flag value H where the application has a flag value W and the database resource is requested by another application;

marking an application with a flag value D where the application requests a worker agent, has a flag value H and there a normal worker agent or overflow worker agent is not available for the application;

marking an application with the flag value Q where the application has the flag value W and a normal worker agent is not available upon request, wherein the application is placed on a wait queue, and

marking an application with the flag value D where the application has the flag value Q and another application requests a lock held by the application having the flag value Q.

5. The method of claim 4, wherein assigning step (a2) comprising the steps of:

providing a normal worker agent if available to an application with flag value H and alternatively providing an overflow worker agent, and if normal worker agent and overflow worker agent are not available, placing the application on the priority queue, and

providing a normal worker agent to an application with flag value W and alternatively placing the application on the wait queue if a normal worker agent is not available.

6. The method of claim 5, wherein the declaring step (b2) comprises the step of declaring a deadlock wherein the specified flag value is D.

7. The method of claim 5, wherein the declaring step (b2) comprising:

using a lock wait deadlock graph and a resource representation, the lock wait deadlock graph comprising means to represent applications requesting and holding locks on database resources.

8. The method of claim 7, wherein the resolving step (c) comprising the step of selecting an application holding a lock and requiring the application to release the lock, following detection of a deadlock on the lock.

9. The method of claim 8, further comprising the step:

(d) clearing the application flag value when an application is provided a worker agent.

10. A database management system (DBMS), wherein the DBMS includes a plurality of applications capable of requesting access to a plurality of database resources and capable of holding locks on the plurality of database resources, and an application scheduler for managing requests from the plurality of applications for access to database resources, the DBMS further comprising:

a plurality of worker agents, the plurality of worker agents including a plurality of normal worker agents and overflow worker agents; and

a deadlock detector coupled to the- application scheduler for identifying a deadlock;

wherein the application scheduler assigns one worker agent to an application requesting access to a database resource, assigns a flag to an application holding a lock on the database resource while disassociated from a worker agent, and in cooperation with the deadlock detector, resolves the deadlock between the application requesting access and the flagged application holding the lock.

11. The system of claim 10, further comprising:

means for marking an application with a flag value based on the existing application flag value and on the state of applications requesting and holding locks on database resources;

means for the application scheduler to respond to the application requesting access and to selectively assign a normal worker agent, an overflow worker agent, or place the application on a wait queue or on a priority queue, based on the application flag value; and

means for clearing the application flag value when an application is provided with a worker agent.

12. The system of claim 11, wherein the deadlock detector further includes:

means for polling an application and means for declaring a deadlock where the application has a specified flag value, and the application holds a lock on a database resource requested by another application.

13. The system of claim 12, wherein the means for marking an application comprises:

means for marking an application with a flag value W where the application becomes disassociated from a worker agent and holds a lock on a database resource;

means for marking an application with a flag value H where the application has a flag value W and where another application requests access to the locked database resource;

means for marking an application with a flag value D where the application requests a worker agent, has a flag value H and a normal worker agent or overflow worker agent is not available for the application;

means for marking an application with the flag value Q where the application has the flag value W and a normal worker agent is not available upon request, wherein the application is placed on the wait queue; and

means for marking an application with the flag value D where the application has the flag value Q and another application requests a lock held by the application having the flag value Q.

14. The system of claim 13, wherein the means for the application scheduler responding to an application requesting access comprises:

means for responding to a request for a worker agent from an application with flag value H by obtaining a normal worker agent if available and alternatively providing an overflow worker agent, further comprising, means for placing the application on the priority queue where no overflow worker agent is available; and

means for responding to a request for a worker agent from an application with flag value W by obtaining a normal worker agent if available and alternatively by placing the application on the wait queue.

15. The system of claim 14, wherein the deadlock detector comprises means for declaring a deadlock where an application has a flag value D and the application holds a lock on a database resource that is requested by another application.

16. The system of claim 15, wherein the deadlock detector further comprises a lock wait deadlock graph and a resource representation, the lock wait deadlock graph comprising means to represent applications requesting and holding locks on database resources, whereby the deadlock detector determines if an application holds a lock requested by another application.

17. The system of claim 16, further comprising means for selecting an application holding a lock and requiring the application to release the lock, following detection of a deadlock on the lock.

19. The computer readable medium of claim 18, wherein the plurality of worker agents includes normal worker agents and overflow worker agents, and assigning instruction a) further includes:

(a1) marking an application with a flag value based on an existing application flag value and on a state of applications requesting and holding locks on database resources, and

(a2) assigning a normal worker agent or an overflow worker agent to the application, or placing the application on a wait queue or on a priority queue, based on the application flag value.

20. The computer readable medium of claim 19, wherein identifying instruction (b) further includes:

(b1) polling an application; and

(b2) declaring a deadlock where the application has a specified flag value and the application holds a lock on a database resource requested by another application.

21. The computer readable medium of claim 20, wherein the marking instruction (a1) comprising the instructions for:

marking an application with a flag value W where the application becomes disassociated from a worker agent and holds a lock on a database resource;

marking an application with a flag value H where the application has a flag value W and the database resource is requested by another application;

marking an application with a flag value D where the application requests a worker agent, has a flag value H and there a normal worker agent or overflow worker agent is not available for the application;

marking an application with the flag value Q where the application has the flag value W and a normal worker agent is not available upon request, wherein the application is placed on a wait queue, and

marking an application with the flag value D where the application has the flag value Q and another application requests a lock held by the application having the flag value Q.

22. The computer readable medium of claim 21, wherein assigning instruction (a2) comprising the instructions for:

providing a normal worker agent if available to an application with flag value H and alternatively providing an overflow worker agent, and if normal worker agent and overflow worker agent are not available, placing the application on the priority queue, and

providing a normal worker agent to an application with flag value W and alternatively placing the application on the wait queue if a normal worker agent is not available.

23. The computer readable medium of claim 22, wherein the declaring instruction (b2) comprises the instruction of declaring a deadlock wherein the specified flag value is D.

24. The computer readable medium of claim 22, wherein the declaring instruction (b2) comprising:

using a lock wait deadlock graph and a resource representation, the lock wait deadlock graph comprising means to represent applications requesting and holding locks on database resources.

25. The computer readable medium of claim 24, wherein the resolving instruction (c) comprising the instruction of selecting an application holding a lock and requiring the application to release the lock, following detection of a deadlock on the lock.

26. The computer readable medium of claim 19, further comprising an instruction for:

(d) clearing the application flag value when an application is provided a worker agent.

18. A computer readable medium containing program instructions for managing requests for access to database resources in a database system, the database system comprising a plurality of applications capable of requesting access to a plurality of database resources and capable of holding locks on the plurality of database resources, the database system further comprising an application scheduler for managing requests from the plurality of applications for access to the plurality of database resources, the program instructions for:

a) assigning a worker agent from a plurality of worker agents to an application by the application scheduler;

b) identifying a deadlock via a deadlock detector coupled to the application scheduler, the deadlock being between an application disassociated from the worker agent while holding a lock on a database resource and another application requesting access to the database resource; and

c) resolving the deadlock.

27. A method of deadlock management for a database system, the database system comprising a set of applications selectively requesting and holding locks on database resources, a pool of worker agents comprising normal worker agents and overflow worker agents, a wait queue, and a priority queue, the method comprising the steps of:

marking an application with a flag value based on an existing application flag value and on a state of applications requesting and holding locks on database resources, comprising the steps of;

marking an application with a flag value W where the application becomes disassociated from a worker agent and holds a lock on a database resource;

marking an application with a flag value H where the application has a flag value W and where another application requests a lock on the database resource;

marking an application with a flag value D where the application requests a worker agent, has a flag value H and there a normal worker agent or overflow worker agent is not available for the application;

marking an application with the flag value Q where the application has a flag value W and a normal worker agent is not available upon request, the application being placed on the wait queue, and

marking an application with the flag value D where the application has the flag value Q and another application requests a lock held by the application having the flag value Q;

responding to an application request for a worker agent and selectively providing a normal worker agent, an overflow worker agent, or placing the application on the wait queue or on the priority queue, based on the application flag value, comprising the steps of;

responding to a request for a worker agent from an application with flag value H by obtaining a normal worker agent if available and alternatively by providing an overflow worker agent, further comprising the step of placing the application on the priority queue where an overflow worker agent is not available, and

responding to a request for a worker agent from an application with flag value W by obtaining a normal worker agent if available and alternatively by placing the application on the wait queue;

clearing the application flag value when an application is provided with a worker agent;

polling an application and declaring a deadlock where the application has a specified flag value and the application holds a lock on a database resource requested by another application, comprising the step of declaring a deadlock where an application has a flag value D and the application holds a lock on a database resource that is requested by another application, the database system further comprising a lock wait deadlock graph and a resource representation, the lock wait deadlock graph comprising means to represent applications requesting and holding locks on database resources whereby the step of declaring a deadlock comprises the step of determining if an application holds a lock requested by another application by accessing the lock wait graph, and

selecting an application holding a lock and requiring the application to release the lock, following detection of a deadlock on the lock.

28. A deadlock management system for a database system, the database system comprising a set of applications selectively requesting and holding locks on database resources, a pool of worker agents comprising normal worker agents and overflow worker agents, an application scheduler, a wait queue, a priority queue, and a deadlock detector, the database system supporting an application holding a lock while disassociated from a worker agent, the deadlock management system comprising:

means for marking an application with a flag value based on an existing application flag value and on a state of applications requesting and holding locks on database resources, comprising;

means for marking an application with a flag value W where the application becomes disassociated from a worker agent and holds a lock on a database resource;

means for marking an application with a flag value H where the application has a flag value W and where the database resource is requested by another application;

means for marking an application with a flag value D where the application requests a worker agent, has a flag value H and a normal worker agent or overflow worker agent is not available for the application

means for marking an application with the flag value Q where the application has a flag value W and a normal worker agent is not available upon request, wherein the application is placed on the wait queue; and

means for marking an application with the flag value D where the application has the flag value Q and another application requests a lock held by the application having the flag value Q;

means for the application scheduler to respond to an application request for a worker agent from the pool and to selectively provide a normal worker agent, an overflow worker agent, or place the application on the wait queue or on the priority queue, based on the application flag value, comprising;

means for responding to a request for a worker agent from an application with flag value H by obtaining a normal worker agent if available and alternatively providing an overflow worker agent, further comprising means for placing the application on the priority queue where an overflow worker agent is not available; and

means for responding to a request for a worker agent from an application with flag value W by obtaining a normal worker agent if available and alternatively by placing the application on the wait queue;

means for clearing the application flag value when an application is provided with a worker agent,

means for the deadlock detector to poll an application; and

means for the deadlock detector to declare a deadlock where the application has a specified flag, value and the application holds a lock on a database resource requested by another application;

comprising;

means for declaring a deadlock where an application has a flag value D and the application holds a lock on a database resource that is requested by another application,

the deadlock detector further comprising a lock wait deadlock graph and a resource representation, the lock wait deadlock graph comprising means to represent applications requesting and holding locks on database resources whereby the deadlock detector determines if an application holds a lock requested by another application; and

means to select an application holding a lock and to require the application to release the lock, following detection of a deadlock on the lock.