EFFICIENT SUPPORT OF CONSISTENT CYCLIC SEARCH WITH READ-COPY UPDATE AND PARALLEL UPDATES
First Claim
1. A method for supporting concurrent updates to a shared data element group while preserving group integrity on behalf of one or more readers that are concurrently referencing group data elements without using locks or atomic instructions, comprising:
- invoking two or more updaters to generate new group data elements;
assigning each new data element created by the same updater a new generation number that is different than a global generation number associated with said data element group and which allows a reader of said data element group to determine whether said new data element is a correct version for said reader;
said new generation numbers being different for each updater and being assigned according to an order in which said updaters respectively begin update operations;
performing data element update processing by;
respectively establishing a first version link that links each of said new data elements to a prior version thereof having a different generation number;
respectively establishing a second version link that links each of said new data elements from its prior version; and
respectively establishing group links that link said new data elements into said data element group so that said new data elements are reachable by readers;
updating said global generation number associated with said data element group so that when all of said updaters have completed said data element update processing, said global generation number will correspond to said new generation number that is associated with the last of said updaters to begin update operations; and
respectively freeing said prior version, said first version link and said second version link for each of said new data elements following a grace period.
1 Assignment
0 Petitions
Accused Products
Abstract
A method, system and computer program product for supporting concurrent updates to a shared data element group while preserving group integrity on behalf of one or more readers that are concurrently referencing group data elements without using locks or atomic instructions. Two or more updaters may be invoked to generate new group data elements. Each new data element created by the same updater is assigned a new generation number that is different than a global generation number associated with the data element group and which allows a reader of the data element group to determine whether the new data element is a correct version for the reader. The new generation numbers are different for each updater and assigned according to an order in which the updaters respectively begin update operations. The global generation number is updated so that when all of the updaters have completed data element update processing, the global generation number will correspond to the new generation number that is associated with the last of the updaters to begin update operations.
-
Citations
20 Claims
-
1. A method for supporting concurrent updates to a shared data element group while preserving group integrity on behalf of one or more readers that are concurrently referencing group data elements without using locks or atomic instructions, comprising:
-
invoking two or more updaters to generate new group data elements; assigning each new data element created by the same updater a new generation number that is different than a global generation number associated with said data element group and which allows a reader of said data element group to determine whether said new data element is a correct version for said reader; said new generation numbers being different for each updater and being assigned according to an order in which said updaters respectively begin update operations; performing data element update processing by; respectively establishing a first version link that links each of said new data elements to a prior version thereof having a different generation number; respectively establishing a second version link that links each of said new data elements from its prior version; and respectively establishing group links that link said new data elements into said data element group so that said new data elements are reachable by readers; updating said global generation number associated with said data element group so that when all of said updaters have completed said data element update processing, said global generation number will correspond to said new generation number that is associated with the last of said updaters to begin update operations; and respectively freeing said prior version, said first version link and said second version link for each of said new data elements following a grace period. - View Dependent Claims (2, 3, 4, 5, 6)
-
-
7. A system for supporting concurrent updates to a shared data element group while preserving group integrity on behalf of one or more readers that are concurrently referencing group data elements without using locks or atomic instructions, comprising:
-
one or more processors; a memory coupled to said one or more processors, said memory including a computer useable medium tangibly embodying at least one program of instructions executable by said processor to perform operations, comprising; invoking two or more updaters to generate new group data elements; assigning each new data element created by the same updater a new generation number that is different than a global generation number associated with said data element group and which allows a reader of said data element group to determine whether said new data element is a correct version for said reader; said new generation numbers being different for each updater and being assigned according to an order in which said updaters respectively begin update operations; performing data element update processing by; respectively establishing a first version link that links each of said new data elements to a prior version thereof having a different generation number; respectively establishing a second version link that links each of said new data elements from its prior version; and respectively establish group links that link said new data elements into said data element group so that said new data elements are reachable by readers; updating said global generation number associated with said data element group so that when all of said updaters have completed said data element update processing, said global generation number will correspond to said new generation number that is associated with the last of said updaters to begin update operations; and respectively freeing said prior version, said first version link and said second version link for each of said new data elements following a grace period. - View Dependent Claims (8, 9, 10, 11, 12)
-
-
13. A computer program product, comprising:
-
one or more machine-useable media; logic provided by said one or more media for programming a data processing platform to support concurrent updates to a shared data element group while preserving group integrity on behalf of one or more readers that are concurrently referencing group data elements without using locks or atomic instructions, as by; invoking two or more updaters to generate new group data elements; assigning each new data element created by the same updater a new generation number that is different than a global generation number associated with said data element group and which allows a reader of said data element group to determine whether said new data element is a correct version for said reader; said new generation numbers being different for each updater and being assigned according to an order in which said updaters respectively begin update operations; performing data element update processing by; respectively establishing a first version link that links each of said new data elements to a prior version thereof having a different generation number; respectively establishing a second version link that links each of said new data elements from its prior version; and respectively establishing group links that link said new data elements into said data element group so that said new data elements are reachable by readers; updating said global generation number associated with said data element group so that when all of said updaters have completed said data element update processing, said global generation number will correspond to said new generation number that is associated with the last of said updaters to begin update operations; and respectively freeing said prior version, said first version link and said second version link for each of said new data elements following a grace period. - View Dependent Claims (14, 15, 16, 17, 18)
-
-
19. A method for supporting concurrent updates to a shared data element group while preserving group integrity on behalf of one or more readers that are concurrently referencing group data elements without using locks or atomic instructions, comprising:
-
invoking two or more updaters to generate new group data elements; assigning each new data element created by the same updater a new generation number that is different than a global generation number associated with said data element group and which allows a reader of said data element group to determine whether said new data element is a correct version for said reader; said new generation numbers being different for each updater and being assigned according to an order in which said updaters respectively begin update operations; performing data element update processing by; respectively establishing a first version link that links each of said new data elements to a prior version thereof having a different generation number; respectively establishing a second version link that links each of said new data elements from its prior version; and respectively establishing group links that link said new data elements into said data element group so that said new data elements are reachable by readers; updating said global generation number associated with said data element group so that when all of said updaters have completed said data element update processing, said global generation number will correspond to said new generation number that is associated with the last of said updaters to begin update operations; said updating of said global generation number being performed using a data structure that tracks updaters that have completed said data element update operations out-of-order; said updating of said global generation number being further performed by setting said global generation number one or more times to correspond to the largest of a sequence of said new generation numbers that are represented by value or by position in said data structure, and which sequence begins with a new generation number that is the only possible next global generation number; and respectively freeing said prior version, said first version link and said second version link for each of said new data elements following a grace period. - View Dependent Claims (20)
-
Specification