Method and apparatus for coordinating access to and modifying multiple element data objects in a shared memory

• US 5,553,267 A
• Filed: 07/01/1992
• Issued: 09/03/1996
• Est. Priority Date: 07/01/1992
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Digital Equipment Corporation (HP Inc.)
• Inventors: Herlihy, Maurice P.
• Primary Examiner(s): Gossage, Glenn
• Application Number:
  US07/907,330
• Time in Patent Office: 1,525 Days
• Field of Search: 395/425, 395/600, 395/474, 395/478, 395/481, 395/482, 395/497.04, 395/456, 395/457, 395/468, 395/480, 395/485, 364/134
• US Class Current: 711/147
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores

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.

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.

2. The method of claim 1, wherein the step of copying the original data object includes the steps of:

(1) copying a first counter associated with the original data object before copying the original data object;

(2) copying the original data object;

(3) copying a second counter associated with the original data object after copying the original data object;

and wherein step (c) comprises the steps of;

(1) advancing the copy of the second counter;

(2) modifying the copy of the original data object in the first memory area;

(3) advancing the copy of the first counter.

3. The method of claim 1, wherein step (b) comprises the steps of:

(1) reading a first counter associated with the original data object before copying the original data object,;

(2) reading a second counter associated with the original data object after copying the original data object;

and

(3) determining whether the first and second counter readings reflect modification of the original data object, and if no such modification is reflected, proceeding to step (c);

alternatively, starting over at step (1).

4. The method of claim 3, wherein step (d) comprises a step of determining whether the first and second counters match and whether the first pointer has been modified since step (a), and in the event the counters do match and the first pointer has not been so modified, proceeding to step (e);

alternatively, starting over at step (a).

5. The method of claim 1, wherein the step of determining whether the first pointer has been modified comprises the steps of:

(1) performing a load_-- linked operation to read the contents of the first pointer; and

(2) comparing the contents read in step (1) to the contents of the first pointer prior to step (a).

6. The method of claim 5, wherein step (e) comprises the step of performing a store_-- conditional operation to store the memory address of the first memory area in the first pointer.

7. The method of claim 1, wherein the alternative of starting over at step (a) follows a randomly selected interval of time.

8. The method of claim 7, wherein the randomly selected interval of time is bounded by a selected upper limit.

9. The method of claim 8, wherein the selected upper limit is increased each time starting over at step (a) is required.

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).

12. The method of claim 11, wherein the alternative in steps (e), (j), and (l) of starting over at step (a) follows a randomly selected interval of time.

13. The method of claim 12, wherein the randomly selected interval of time is bounded by a selectively adjustable upper limit.

14. The method of claim 11, wherein the data object comprises a linked list of elements.

15. The method of claim 14, wherein step (c) comprises copying the following items into the scratch memory area:

one or more elements of the data object to be modified;

the first element of the data object; and

all elements between the one or more elements to be modified and the first element of the data object.

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.

18. The method of claim 17, wherein step (g) further comprises the step of starting over at step (a) if the first and second counters indicate that the data object in the first memory area has been modified since steps (a) and (c), respectively, or if the first pointer has changed since step (a).

19. The method of claim 18, wherein said step of starting over at step (a) follows a randomly selected interval of time.

20. The method of claim 17, wherein step (d) further comprises the step of starting over at step (a) if the first and second counters indicate that the data object in the first memory area has been modified since step (a).

21. The method of claim 20, wherein the first and second counters indicate that the data object in the first memory area has not been modified if the first and second counter readings match each other.

22. The method of claim 20, wherein the step of starting over at step (a) follows a randomly selected interval of time.