Highly scalable tree-based trylock
First Claim
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.
1 Assignment
0 Petitions
Accused Products
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.
-
Citations
13 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. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
-
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. - View Dependent Claims (9, 10, 11, 12, 13)
-
Specification