Method and apparatus for coordinating access to and modifying multiple element data objects in a shared memory
First Claim
1. A method of modifying an original data object that is located in a shared memory, the original data object having a memory address indicated by a first pointer, the shared memory being accessible by multiple processors, wherein each processor attempting to modify the original data object performs steps comprising:
- (a) copying the original data object into a first memory area of the shared memory whose memory address is indicated by a second pointer;
(b) determining whether the original data object has been modified since the beginning of step (a), and if no such modification has occurred, proceeding to step (c);
alternatively, starting over at step (a);
(c) modifying the copied data object;
(d) determining whether the original data object or the first pointer has been modified since step (a), and if neither has been modified, proceeding to step (e);
otherwise starting over at step (a);
(e) modifying the first pointer to indicate the memory address of the first memory area; and
(f) modifying the second pointer to indicate the memory address of the original data object.
3 Assignments
0 Petitions
Accused Products
Abstract
A method and apparatus for improved access to shared memory of an electronic computing system supporting load-- linked and store-- conditional machine operations. Data objects in the shared memory are referenced by root pointers of an object directory of the shared memory. Each data object is associated with a check[0] counter and a check[1] counter. A processor first reads the root pointer and the data object'"'"'s check[0] counter, then copies the data object to a scratch area of memory associated with that processor, the scratch area also having check[0] and check[1] counters associated therewith. The processor then reads the data object'"'"'s check[1] counter. If the data object'"'"'s check[0] and check[1] counters are unequal, the processor performs an exponential "back-off" by waiting for a randomly selected period of time before attempting to access the data object again. When the data object is successfully read, the scratch area'"'"'s check[1] counter is incremented, the data object in the scratch area is modified as desired, and the scratch area'"'"'s check[0] counter is incremented. A load-- linked operation is then used to read the root pointer, and the data object'"'"'s check[0] and check[1] counters are read. If the data object'"'"'s check[0] and check[1] counters match and the root pointer has not been modified since the processor first read it, a store-conditional operation is attempted. If the store-- conditional is unsuccessful, exponential back-off is performed, and the routine is re-started. Otherwise, the store-- conditional succeeds in "swinging" the root pointer to the modified object, and the routine ends. A new scratch area may be established in the shared memory by utilizing the elements of the old data object that were changed.
-
Citations
22 Claims
-
1. A method of modifying an original data object that is located in a shared memory, the original data object having a memory address indicated by a first pointer, the shared memory being accessible by multiple processors, wherein each processor attempting to modify the original data object performs steps comprising:
-
(a) copying the original data object into a first memory area of the shared memory whose memory address is indicated by a second pointer; (b) determining whether the original data object has been modified since the beginning of step (a), and if no such modification has occurred, proceeding to step (c);
alternatively, starting over at step (a);(c) modifying the copied data object; (d) determining whether the original data object or the first pointer has been modified since step (a), and if neither has been modified, proceeding to step (e);
otherwise starting over at step (a);(e) modifying the first pointer to indicate the memory address of the first memory area; and (f) modifying the second pointer to indicate the memory address of the original data object. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9)
-
-
10. An apparatus for coordinating access to one or more data objects contained in memory, the apparatus comprising:
-
multiple processors; and a shared memory including one or more counters corresponding to each data object, wherein each counter can be modified to indicate modification of the corresponding data object; one pointer corresponding to each data object, indicating the memory address of the data object in the shared memory; one or more first memory areas contained in the shared memory and corresponding exclusively to each of the processors, for receiving a copy of a data object for modification by the corresponding processor; one or more counters corresponding to each first memory area, wherein each counter can be modified to indicate a modification of that first memory area; and one pointer for each first memory area, indicating the memory address of the first memory area; wherein at least one of said processors includes; means for copying a data object into one of the first memory areas, and means for comparing and modifying the counters corresponding to each data object and the counters corresponding to each first memory area to coordinate access to each data object.
-
-
11. A method of modifying a data object in shared memory with a processor, the shared memory also being accessible by one or more other processors, wherein each processor attempting to modify the data object performs steps comprising:
-
(a) reading the contents of a first root pointer, said first root pointer containing the address of the data object in the shared memory; (b) reading a data object check[0] counter associated with the data object; (c) copying the data object from the shared memory into a scratch memory area, the address of the scratch memory area being contained in a scratch memory pointer; (d) reading the data object check[1] counter associated with the data object; (e) determining whether the data object check[1] counter matches the data object check[0] counter, and proceeding with step (f) if the counters are equal, alternatively, starting over a step (a); (f) incrementing a scratch memory check[1] counter associated with the scratch memory area; (g) modifying the copy of the data object in the scratch memory area; (h) incrementing a scratch memory check[0] counter associated with the scratch memory area; (i) utilizing a load-- linked machine operation to read the contents of the first root pointer; (j) determining whether the data object check[0] counter has changed since step (b), or whether the data object check[1] counter has changed since step (d), or whether the root pointer has changed since step (a), and proceeding with step (k) if no changes have occurred, otherwise starting over at step (a); (k) utilizing a store-- conditional machine operation to attempt to replace the contents of the first root pointer with the contents of the scratch memory pointer; and (l) in the event the store-- conditional stop (k) was successful, storing the replaced contents of the first root pointer as the scratch area pointer, alternatively, starting over at step (a). - View Dependent Claims (12, 13, 14, 15)
-
-
16. A method of enabling any given one of a plurality of data processors to modify a given data object stored in a first memory area in a memory accessible by said plurality of processors, comprising:
-
(a) causing the given processor to make a copy of the given data object into a second memory area; (b) verifying that the given data object has not been accessed by another of said processors since the commencement of step (a); (c) modifying the copy of the data object upon such verification, or failing such verification, repeating steps (a) and (b) after a period of time that changes at random for each successive such failure; (d) again verifying that the dam object has not been accessed by another of said data processors following the modification in step (c); and (e) substituting the modified data object in the second memory area for the given data object in the first memory area upon such verification, or, failing such verification, repeating steps (a) through (d) after a period of time that changes at random for each successive such failure.
-
-
17. A method of modifying a data object located in a first memory area in a memory shared by multiple processors, wherein the first memory area has a scratch area, a first and a second counter, and the address of the first memory area is contained in a first pointer, comprising the steps of:
-
(a) reading the first counter; (b) creating a copy of the data object in a second memory area in the shared memory, the second memory area having a third counter and a fourth associated therewith, the address of the second memory area being contained in a second pointer; (c) reading the second counter; (d) if the first and second counters do not indicate that the data object in the first memory area has been modified since step (a), incrementing the third counter and modifying the copy of the data object in the second memory area; (e) incrementing the fourth counter; (f) reading the first and second counters and the first pointer; (g) if the first and second counters do not indicate that the data object in the first memory area has been modified since steps (a) and (c), respectively, and if the first pointer has not changed since step (a), swapping the values contained in the first and second pointers. - View Dependent Claims (18, 19, 20, 21, 22)
-
Specification