Highly scalable tree-based trylock

• US 9,396,226 B2
• Filed: 06/24/2013
• Issued: 07/19/2016
• Est. Priority Date: 06/24/2013
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: McKenney, Paul E.
• Primary Examiner(s): Dwivedi, Mahesh
• Application Number:
  US13/924,667
• Publication Number:
  US 20140379676A1
• Time in Patent Office: 1,121 Days
• Field of Search: 707/704
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2336 Pessimistic concurrency control approaches, e.g. locking or multiple versions without time stamps

Abstract

A tree-based trylock technique for reducing contention on a root trylock includes attempting to acquire a trylock at each node of a tree-based hierarchical node structure while following a traversal path that begins at a leaf node, passes through one or more of internal nodes, and ends at a root node having the root trylock. The trylock acquisition operation succeeds if each trylock on the traversal path is acquired, and fails if any trylock on the traversal path cannot be acquired. A trylock housekeeping operation releases all non-root trylocks visited by the trylock acquisition operation, such that if the trylock acquisition operation succeeds, only the root trylock will be remain acquired at the end of the operation, and if the trylock acquisition operation fails, none of the trylocks will be remain acquired at the end of the operation.

Claims

1. A multiprocessor system, comprising:

two or more processors;

a memory coupled to said processors, said memory including a computer useable medium tangibly embodying at least one program of instructions executable by said processors to perform tree-based trylock operations that reduce contention on a root trylock, said operations comprising;

providing a lock hierarchy which plural trylocks are distributed among nodes of a tree-based node structure having a plurality of leaf nodes, one or more internal nodes, and a root node;

assigning said processors to said leaf nodes in a distributed and balanced manner in order to minimize memory contention on said trylocks;

implementing a trylock acquisition operation on a selected one of said processors for acquiring a root trylock associated with said root node;

said trylock acquisition operation including attempting to acquire one of said trylocks at each node of said node structure that lies on a traversal path beginning at one of said leaf nodes, passing through one or more of said internal nodes, and ending at said root node;

said trylock acquisition operation succeeding if each trylock on said traversal path is acquired, and failing if any trylock on said traversal path cannot be acquired; and

performing a trylock housekeeping operation that releases all non-root trylocks visited by said trylock acquisition operation, such that if said trylock acquisition operation succeeds, only said root trylock will be remain acquired at the end of said operation, and if said trylock acquisition operation fails, none of said trylocks will be remain acquired at the end of said operation.

2. The system of claim 1, wherein said root trylock guards a guarded operation for which duplicate initiations are redundant, or guards a global lock that in turn guards said guarded operation.

3. The system of claim 2, wherein said guarded operation comprises read-copy update quiescent state forcing.

4. The system of claim 1, wherein said trylock acquisition operation further includes checking, at each node on said traversal path, a condition indicating that an operation protected by said root trylock has already been initiated by another one of said processors, and failing said trylock acquisition operation if said condition exists.

5. The system of claim 1, wherein said trylock housekeeping operation is performed at each of said nodes on said traversal path by releasing a trylock acquired at an immediately preceding node.

6. The system of claim 1, wherein said operations further include performing a global lock acquisition to acquire a global lock after said trylock acquisition operation successfully acquires said root trylock, said root trylock being released if said global lock acquisition is successful.

7. The system of claim 1, wherein said global lock acquisition operation includes checking a condition indicating that an operation guarded by said global lock has already been initiated by another one of said processors, and failing said global lock acquisition operation if said condition exists.

8. A computer program product, comprising:

one or more machine-readable non-transitory data storage media;

program instructions provided by said one or more data storage media for programming a multiprocessor data processing platform to perform tree-based trylock operations that reduce contention on a root trylock, said operations comprising;

providing a lock hierarchy which plural trylocks are distributed among nodes of a tree-based node structure having a plurality of leaf nodes, one or more internal nodes, and a root node;

assigning said processors to said leaf nodes in a distributed and balanced manner in order to minimize memory contention on said trylocks;

implementing a trylock acquisition operation on a selected one of said processors for acquiring a root trylock associated with said root node;

said trylock acquisition operation including attempting to acquire one of said trylocks at each node of said node structure that lies on a traversal path beginning at one of said leaf nodes, passing through one or more of said internal nodes, and ending at said root node;

said trylock acquisition operation succeeding if each trylock on said traversal path is acquired, and failing if any trylock on said traversal path cannot be acquired; and

performing a trylock housekeeping operation that releases all non-root trylocks visited by said trylock acquisition operation, such that if said trylock acquisition operation succeeds, only said root trylock will be remain acquired at the end of said operation, and if said trylock acquisition operation fails, none of said trylocks will be remain acquired at the end of said operation.

9. The computer program product of claim 8, wherein said root trylock guards a guarded operation for which duplicate initiations are redundant, or guards a global lock that in turn guards said guarded operation.

10. The computer program product of claim 9, wherein said guarded operation comprises read-copy update quiescent state forcing.

11. The computer program product of claim 8, wherein said trylock acquisition operation further includes checking, at each node on said traversal path, a condition indicating that an operation protected by said root trylock has already been initiated by another one of said processors, and failing said trylock acquisition operation if said condition exists.

12. The computer program product of claim 8, wherein said trylock housekeeping operation is performed at each of said nodes on said traversal path by releasing a trylock acquired at an immediately preceding node.

13. The computer program product of claim 8, wherein said operations further include performing a global lock acquisition to acquire a global lock after said trylock acquisition operation successfully acquires said root trylock, said root trylock being released if said global lock acquisition is successful.