Highly scalable tree-based trylock

• US 9,400,818 B2
• Filed: 09/16/2013
• Issued: 07/26/2016
• Est. Priority Date: 06/24/2013
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: McKenney, Paul E.
• Primary Examiner(s): Dwivedi, Mahesh
• Application Number:
  US14/027,408
• Publication Number:
  US 20140379678A1
• Time in Patent Office: 1,044 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. In a multiprocessor computer system having two or more processors operatively coupled to one or more memory devices, a tree-based trylock method that reduces contention on a root trylock, comprising:

providing a lock hierarchy in 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 method 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 method of claim 2, wherein said guarded operation comprises read-copy update quiescent state forcing.

4. The method 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 method 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 method of claim 1, further including 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 method 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.