Two-level management of locks on shared resources

• US 9,940,346 B2
• Filed: 07/23/2014
• Issued: 04/10/2018
• Est. Priority Date: 10/11/2010
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Attaluri, Gopi K., Finnie, James L., Palmer, Stewart L., Plachta, Piotr M., Swart, Garret F., Xue, Xun, Zheng, Roger L. Q.
• Primary Examiner(s): Woolcock, Madhu
• Application Number:
  US14/338,452
• Publication Number:
  US 20150019739A1
• Time in Patent Office: 1,357 Days
• Field of Search: 709202, 709224, 709226, 710200, 718104
• CPC Class Codes: G06F 16/2343 Locking methods, e.g. distributed locking or locking implementation details
• CPC Class Codes: G06F 9/5005 to service a request
• CPC Class Codes: G06F 9/5038 considering the execution order of a plurality of tasks, e.g. taking priority or time dependency constraints into consideration scheduling strategies G06F9/4881 and subgroups
• CPC Class Codes: G06F 9/524 Deadlock detection or avoidance
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

In a shared data system comprising one or more primary nodes and a plurality of secondary nodes, global lock manager on a primary node manages locks for shared resources by exchanging an abstract lock state with local lock managers on the secondary nodes. The abstract lock state includes a particular representation of all of the applications on the nodes that are requesting or are granted locks. The exchange of these particular lock states instead of individual requests improves performance by increasing concurrency and reducing off-machine communication. A global deadlock detector on a node detects and resolves global deadlocks, in conjunction with local deadlock detectors on the secondary nodes.

Claims

1. A method for managing locks on shared resources in a distributed computer system comprising:

receiving at a first primary node a first local lock state from a first secondary node of a plurality of secondary nodes, wherein the first local lock state comprises a lock request for access to a shared resource, a requested lock mode, and merged state information identifying a current state of a plurality of different locks for shared resources held by a plurality of tasks on the first secondary node and indicating a group lock mode representing a combined lock mode for the plurality of tasks on the first secondary node holding the plurality of different locks on the shared resources, wherein the group lock mode is generated by comparing different lock modes held by the plurality of tasks and identifying a lock mode with a corresponding set of compatible lock modes including each of the different lock modes held by the plurality of tasks;

granting the lock request at the first primary node in response to an absence of conflicts;

generating at the first primary node a first global lock state in response to the first local lock state; and

communicating the first global lock state from the first primary node to the first secondary node.

2. The method of claim 1, wherein a priority queue for the shared resource comprises a plurality of client entries each comprising a priority, a local lock state from one of the plurality of secondary nodes, and a responsive global lock state from the first primary node, wherein each local lock state comprises a lock request for access to the shared resource by one or more tasks on the one of the plurality of secondary nodes and each task has an associated lock mode, a fair lock mode that is the associated lock mode of a top waiter task on the one of the plurality of secondary nodes, a concurrent lock mode that is the associated lock mode of at least two tasks on the one of the plurality of secondary nodes that are able to run concurrently when the concurrent lock mode is granted, and a maximum lock mode that is a supremum of the associated lock modes for the one or more tasks on the one of the plurality of secondary nodes, and wherein each responsive global lock state comprises a holdable lock mode indicating a lock mode that was granted to the one of the plurality of secondary nodes, wherein the method further comprises processing the priority queue including:

(a) processing fair lock mode requests for each individual client entry by granting a lock request in a fair lock mode for the individual client entry when the fair lock mode of the individual client entry is compatible with the fair lock mode of all client entries having a higher priority than the individual client entry and the holdable lock mode of all client entries in the priority queue;

(b) processing concurrent lock mode requests for each individual client entry by granting a lock request in a concurrent lock mode for the individual client entry when the concurrent lock mode of the individual client entry is compatible with the fair lock mode of all client entries in the priority queue and the holdable lock mode of all client entries in the priority queue; and

(c) processing maximum lock mode requests for each individual client entry by granting a lock request in a maximum lock mode for the individual client entry when the maximum lock mode of the individual client entry is compatible with the concurrent lock mode of all client entries in the priority queue and the holdable lock mode of all client entries in the priority queue.

3. The method of claim 1, further comprising:

in response to the first secondary node waiting for a certain lock mode on the shared resource and being blocked by a second secondary node of the plurality of secondary nodes holding a lock on the shared resource;

determining that the first secondary node has a higher priority than the second secondary node;

generating a first lock state notification to the second secondary node signalling a reclaim of the held lock; and

communicating the first lock state notification from the first primary node to the second secondary node.

4. The method of claim 1, wherein each task of the first secondary node has an associated lock mode, and further comprising, at the first secondary node:

receiving the first global lock state signalling a reclaim of a lock held by the first secondary node;

identifying a current lock mode of the lock held by the first secondary node and one or more tasks on the first secondary node that are holding or waiting for access to the shared resource and have lock modes that are dominated by the current lock mode; and

allowing the identified one or more tasks to finish accessing the shared resource and releasing the lock held by the first secondary node to the first primary node to enable the first primary node to grant the lock held by the first secondary node to a remote secondary node.

5. The method of claim 4, further comprising, at the remote secondary node:

receiving the lock held by the first secondary node from the first primary node after the lock held by the first secondary node has been released by the first secondary node;

identifying a current lock mode of the lock held by the first secondary node and granted to the remote secondary node on the remote secondary node and one or more tasks on the remote secondary node that are holding or waiting for access to the shared resource and have lock modes that are dominated by the current lock mode of the lock held by the first secondary node and granted to the remote secondary node; and

allowing the identified one or more tasks on the remote secondary node to finish accessing the shared resource and releasing the lock held by the first secondary node and granted to the remote secondary node back to the first primary node to enable the first primary node to grant the lock held by the first secondary node and panted to the remote secondary node back to the first secondary node.

6. The method of claim 1, further comprising, at the first secondary node:

detecting and resolving local deadlocks between tasks on the first secondary node;

identifying at least one task on the first secondary node associated with a block of a task on a remote secondary node;

generating lock conflict information comprising local lock waits for one or more tasks on the first secondary node including the identified at least one task; and

communicating the generated lock conflict information to a second primary node.

7. The method of claim 1, further comprising:

receiving at a global deadlock detector lock conflict information from two or more secondary nodes;

detecting at the global deadlock detector a global deadlock between tasks on two or more different secondary nodes using the received lock conflict information;

resolving the detected global deadlock at the global deadlock detector by selecting one of the deadlocked tasks on the two or more different secondary nodes;

communicating the selected deadlocked task to a secondary node associated with the selected deadlocked task; and

terminating the selected deadlocked task at the secondary node associated with the selected deadlocked task.

8. The method of claim 1, wherein granting the lock request at the first primary node comprises:

granting the lock request at the first primary node based on the merged state information of a plurality of the secondary nodes.

9. A computer program product for managing locks on shared resources in a distributed computer system comprising:

a computer readable storage device having computer readable program code embodied therewith, the computer readable program code comprising computer readable program code configured to;

receive at a first primary node a first local lock state from a first secondary node of a plurality of secondary nodes, wherein the first local lock state comprises a lock request for access to a shared resource, a requested lock mode, and merged state information identifying a current state of a plurality of different locks for shared resources held by a plurality of tasks on the first secondary node and indicating a group lock mode representing a combined lock mode for the plurality of tasks on the first secondary node holding the plurality of different locks on the shared resources, wherein the group lock mode is generated by comparing different lock modes held by the plurality of tasks and identifying a lock mode with a corresponding set of compatible lock modes including each of the different lock modes held by the plurality of tasks;

grant the lock request at the first primary node in response to an absence of conflicts;

generate at the first primary node a first global lock state in response to the first local lock state; and

communicate the first global lock state from the first primary node to the first secondary node.

10. The computer program product of claim 9, wherein each task of the first secondary node has an associated lock mode, and the computer readable program code further comprises computer readable program code configured to, at the first secondary node:

receive the first global lock state signalling a reclaim of a lock held by the first secondary node;

identify a current lock mode of the lock held by the first secondary node on the first secondary node and one or more tasks on the first secondary node that are holding or waiting for access to the shared resource and have lock modes that are dominated by the current lock mode; and

allow the identified one or more tasks to finish accessing the shared resource and release the lock held by the first secondary node to the first primary node to enable the first primary node to grant the lock held by the first secondary node to a remote secondary node.

11. The computer program product of claim 10, wherein the computer readable program code further comprises computer readable program code configured to, at the remote secondary node:

receive the lock held by the first secondary node from the first primary node after the lock held by the first secondary node has been released by the first secondary node;

identify a current lock mode of the lock held by the first secondary node and granted to the remote secondary node on the remote secondary node and one or more tasks on the remote secondary node that are holding or waiting for access to the shared resource and have lock modes that are dominated by the current lock mode of the lock held by the first secondary node and granted to the remote secondary node; and

allow the identified one or more tasks on the remote secondary node to finish accessing the shared resource and release the lock held by the first secondary node and granted to the remote secondary node back to the first primary node to enable the first primary node to grant the lock held by the first secondary node and granted to the remote secondary node back to the first secondary node.

12. The computer program product of claim 9, wherein the computer readable program code further comprises computer readable program code configured to, at the first secondary node:

detect and resolve local deadlocks between tasks on the first secondary node;

identify at least one task on the first secondary node associated with a block of a task on a remote secondary node;

generate lock conflict information comprising local lock waits for one or more tasks on the first secondary node including the identified at least one task; and

communicate the generated lock conflict information to a second primary node.

13. The computer program product of claim 9, wherein the computer readable program code further comprises computer readable program code configured to:

receive at a global deadlock detector lock conflict information from two or more secondary nodes;

detect at the global deadlock detector a global deadlock between tasks on two or more different secondary nodes using the received lock conflict information;

resolve the detected global deadlock at the global deadlock detector by selecting one of the deadlocked tasks on the taro or more different secondary nodes;

communicate the selected deadlocked task to a secondary node associated with the selected deadlocked task; and

terminate the selected deadlocked task at the secondary node associated with the selected deadlocked task.

14. A system for managing locks on shared resources in a distributed computer system comprising:

a first primary node comprising a first processor and a memory and configured to communicate with a plurality of secondary nodes each comprising a plurality of tasks, and wherein the plurality of secondary nodes collectively comprises a plurality of shared resources;

wherein the first processor is configured with logic to;

receive a first local lock state from a first secondary node of the plurality of secondary nodes, wherein the first local lock state comprises a lock request for access to a shared resource, a requested lock mode, and merged state information identifying a current state of a plurality of different locks for shared resources held by a plurality of tasks on the first secondary node and indicating a group lock mode representing a combined lock mode for the plurality of tasks on the first secondary node holding the plurality of different locks on the shared resources, wherein the group lock mode is generated by comparing different lock modes held by the plurality of tasks and identifying a lock mode with a corresponding set of compatible lock modes including each of the different lock modes held by the plurality of tasks;

grant the lock request in response to an absence of conflicts;

generate a first global lock state in response to the first local lock state; and

communicate the first global lock state to the first secondary node.

15. The system of claim 14, wherein each task of the first secondary node has an associated lock mode, and wherein the first secondary node comprises a second processor configured with logic to:

receive the first global lock state signalling a reclaim of a lock held by the first secondary node;

identify a current lock mode of the lock held by the first secondary node on the first secondary node and one or more tasks on the first secondary node that are holding or waiting for access to the shared resource and have lock modes that are dominated by the current lock mode; and

allow the identified one or more tasks to finish accessing the shared resource and release the lock held by the first secondary node to the first primary node to enable the first primary node to grant the lock held by the first secondary node to a remote secondary node.

16. The system of claim 15, wherein the remote secondary node comprises a third processor configured with logic to:

receive the lock held by the first secondary node from the first primary node after the lock held by the first secondary node has been released by the first secondary node;

identify a current lock mode of the lock held by the first secondary node and granted to the remote secondary node on the remote secondary node and one or more tasks on the remote secondary node that are holding or waiting for access to the shared resource and have lock modes that are dominated by the current lock mode of the lock held by the first secondary node and granted to the remote secondary node; and

allow the identified one or more tasks on the remote secondary node to finish accessing the shared resource and release the lock held by the first secondary node and granted to the remote secondary node back to the first primary node to enable the first primary node to grant the lock held by the first secondary node and granted to the remote secondary node back to the first secondary node.

17. The system of claim 14, wherein the first secondary node comprises a second processor configured with logic to:

detect and resolve local deadlocks between tasks on the first secondary node;

identify at least one task on the first secondary node associated with a block of a task on a remote secondary node;

generate lock conflict information comprising local lock waits for one or more tasks on the first secondary node including the identified at least one task; and

communicate the generated lock conflict information to a second primary node.

18. The system of claim 14, further comprising:

a global deadlock detector comprising a second processor configured with logic to;

receive lock conflict information from two or more secondary nodes;

detect a global deadlock between tasks on two or more different secondary nodes using the received lock conflict information;

resolve the detected global deadlock by selecting one of the deadlocked tasks on the two or more different secondary nodes; and

communicate the selected deadlocked task to a secondary node associated with the selected deadlocked task.

19. The system of claim 18, wherein the secondary node associated with the selected deadlocked task includes a third processor configured with logic to:

receive the selected deadlocked task from the global deadlock detector;

generate updated lock conflict information for the selected deadlocked task; and

terminate the selected deadlocked task.

20. The system of claim 18, wherein the global deadlock detector resides on one of the plurality of secondary nodes.