Address level synchronization of shared data

• US 8,261,024 B1
• Filed: 10/31/2005
• Issued: 09/04/2012
• Est. Priority Date: 09/15/2005
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Oracle America, Inc. (Oracle Corporation)
• Inventors: Shavit, Nir N., Shalev, Ori
• Primary Examiner(s): Campos, Yaima
• Application Number:
  US11/263,414
• Time in Patent Office: 2,500 Days
• Field of Search: None
• US Class Current: 711/147
• CPC Class Codes: G06F 2209/522 Manager
• CPC Class Codes: G06F 2209/523 Mode
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

From among a plurality of threads accessing a shared data object, one thread acquires a “master” status to arbitrate among the requests of competing threads during a given session of data access to the shared data object. During the session, the master thread resolves any conflicts resulting from attempts to access or modify the shared data object by other threads, and only the master thread may apply modifications to the shared data object during the session. Meanwhile, during the session, non-master threads may perform non-blocking read operations on the shared data object. During a subsequent session, a different thread may acquire master status.

Claims

1. A computer-implemented method, comprising:

two or more of a plurality of threads executing on one or more processors concurrently accessing a shared data object during a data access session, wherein a data access session comprises a set of access operations performed on the shared data object by a given one of the two or more threads that has acquired master status during the period of time in which the given one of the two or more threads acts as a master thread with respect to access operations targeting the shared data object, and wherein the given one of the two or more threads acts as the master thread for the duration of the data access session;

wherein concurrently accessing the shared data object during the data access session comprises;

the given one of the two or more threads performing one or more data modifications on a first version of the shared data object;

the given one of the two or more threads performing one or more data modifications of a thread of the two or more threads other than the given one of the two or more threads that target the shared data object on the first version of the shared data object; and

a thread of the two or more threads other than the given one of the two or more threads performing one or more read accesses that target the shared data object in a non-blocking manner on a second version of the shared data object;

wherein the method further comprises;

the given one of the two or more threads ending the data access session; and

the given one of the two or more threads making the first version of the shared data object and the second version of the shared data object identical.

2. The method as recited in claim 1, further comprising:

prior to ending the data access session, the given one of the two or more threads determining if any read accesses performed on the second version are in conflict with any data modifications performed on the first version; and

the given one of the two or more threads resolving any conflicts found.

3. The method as recited in claim 2, wherein the shared data object comprises a plurality of addressable data locations, wherein data accesses to the shared data object are performed at an address level, and wherein said conflicts are determined at the address level.

4. The method as recited in claim 1, further comprising:

one of the plurality of threads other than the given one of the two or more threads becoming a master thread for a subsequent session during which two or more of the plurality of threads concurrently access the shared data object, wherein said concurrently accessing the shared data object during the subsequent session comprises;

the master thread for the subsequent session performing one or more data modifications of one or more of the two or more threads concurrently accessing the shared data object during the subsequent session other than the master thread for the subsequent session on the second version of the shared data object; and

a thread of the two or more threads concurrently accessing the shared data object during the subsequent session other than the master thread for the subsequent session performing read accesses to the shared data object in a non-blocking manner on the first version of the shared data object.

5. The method as recited in claim 1, wherein the shared data object is one of a plurality of data objects comprised within a data structure, the method further comprising:

two or more of the plurality of threads concurrently accessing another one of the plurality of data objects during an other session, wherein the other session overlaps at least partly with said data access session, wherein a given thread among the plurality of threads other than the given one of the two or more threads is the corresponding master thread during the other session for accessing the other data object, and wherein said accessing the other data object during the other session comprises;

the corresponding master thread performing one or more data modifications of a thread of the two or more threads accessing the other data object other than the corresponding master thread on a first version of the other data object; and

a thread of the two or more threads accessing the other data object other than the corresponding master thread performing read accesses to the other data object in a non-blocking manner on a second version of the other data object.

6. The method as recited in claim 5, wherein the data structure is an instance of an object class defined in an application program, wherein each of the plurality of data objects comprises one or more member fields of the instance of the object class.

7. A system, comprising:

a processor; and

memory coupled to the processor, wherein the memory stores program instructions executable by the processor to cause the processor to perform;

two or more of a plurality of threads concurrently access a shared data object during a data access session, wherein a data access session comprises a set of access operations performed on the shared data object by a given one of the two or more threads that has acquired master status during the period of time in which the given one of the two or more threads acts as a master thread with respect to access operations targeting the shared data object, and wherein the given one of the two or more threads acts as the master thread for the duration of the data access session;

wherein concurrently accessing the shared data object during the data access session comprises;

the given one of the two or more threads performing one or more data modifications on a first version of the shared data object;

the given one of the two or more threads performing one or more data modifications of a thread of the two or more threads other than the given one of the two or more threads that target the shared data object on the first version of the shared data object; and

a thread of the two or more threads other than the given one of the two or more threads performing one or more read accesses that target the shared data object in a non-blocking manner on a second version of the shared data object;

wherein the program instructions are further executable by the processor to cause the processor to perform;

the given one of the two or more threads ending the data access session; and

the given one of the two or more threads making the first version of the shared data object and the second version of the shared data object identical.

8. The system as recited in claim 7, wherein the program instructions are further executable by the processor to cause the processor to perform:

prior to ending the data access session, the given one of the two or more threads determining if any read accesses performed on the second version of the shared data object are in conflict with any data modifications performed on the first version of the shared data object; and

the given one of the two or more threads resolving any conflicts found.

9. A non-transitory computer readable storage medium storing program instructions that when executed on one or more computers cause the one or more computers to perform:

two or more of a plurality of threads concurrently accessing a shared data object during a data access session, wherein a data access session comprises a set of access operations performed on the shared data object by a given one of the two or more threads that has acquired master status during the period of time in which the given one of the two or more threads acts as a master thread with respect to access operations targeting the shared data object, and wherein the given one of the two or more threads acts as the master thread for the duration of the data access session;

wherein concurrently accessing the shared data object during the data access session comprises;

the given one of the two or more threads performing one or more data modifications on a first version of the shared data object;

the given one of the two or more threads performing one or more data modifications of a thread of the two or more threads other than the given one of the two or more threads that target the shared data object on the first version of the shared data object; and

a thread of the two or more threads other than the given one of the two or more threads performing one or more read accesses that target the shared data object in a non-blocking manner on a second version of the shared data object;

wherein executing the program instructions on the one or more computers further causes the one or more computers perform;

the given one of the two or more threads ending the data access session; and

the given one of the two or more threads making the first version of the shared data object and the second version of the shared data object identical.

10. The non-transitory computer readable storage medium as recited in claim 9, wherein executing the program instructions on the one or more computers further causes the one or more computers perform:

prior to ending the data access session, the given one of the two or more threads determining if any read accesses performed on the second version are in conflict with any data modifications performed on the first version; and

the given one of the two or more threads resolving any conflicts found.

11. A computer-implemented method, comprising:

a plurality of threads executing on one or more processors concurrently accessing a shared data object during a data access session, wherein a data access session comprises a set of access operations performed on the shared data object by a given one of the plurality of threads that has acquired master thread status during the period of time in which the given one of the plurality of threads is a master thread with respect to access operations targeting the shared data object, wherein the given one of the threads is the master thread for the duration of the data access session;

wherein, during the data access session, said accessing comprises;

one or more of the threads performing read accesses on the shared data object in a non-blocking manner;

the master thread performing one or more data modifications of a thread of the plurality of threads other than the master thread that target the shared data object; and

the master thread determining if any read accesses are in conflict with any data modifications to the shared data object and resolving any conflicts; and

during a subsequent session for accessing the shared data object, a given one of the plurality of threads other than the master thread becoming a master thread for the subsequent session.

12. The method as recited in claim 11, wherein the one or more data modifications are performed by the master thread on a first version of the shared data object during the data access session, wherein non-blocking read accesses by threads other than the master thread are performed on a second version of the shared data object during the data access session, wherein the second version of the shared data object remains unmodified during the data access session, and wherein the method further comprises, after the data access session ends, updating the second version of the shared data object to reflect modifications made to the first version of the shared data object during the data access session.

13. The method as recited in claim 11, wherein the shared data object comprises a member field of a parent object comprising a plurality of member fields, the method further comprising:

two or more threads of the plurality of threads concurrently accessing an other member field of the parent object during an other session that overlaps at least partly in time with the data access session, wherein a given thread other than the master thread is designated as a master thread for the other session, and wherein, during the other session, said concurrently accessing the other member field comprises;

one or more of the two or more threads accessing the other member field performing read accesses on the other member field in a non-blocking manner;

the master thread for the other session performing one or more data modifications to the other member field of one or more of the two or more threads accessing the other member field other than the master thread for the other session that target the other member field; and

the master thread for the other session determining if any read accesses are in conflict with any data modifications to the other member field and resolving any conflicts.

14. The method as recited in claim 11, further comprising:

a modifying thread other than the master thread logging one or more data modifications directed to the shared data object during the data access session to a log;

wherein, in performing data modifications of the modifying thread, the master thread accesses the log.

15. A system, comprising:

a processor; and

memory coupled to the processor, wherein the memory stores program instructions executable by the processor to cause the processor to perform;

a plurality of threads accessing a shared data object during a data access session, wherein a data access session comprises a set of access operations performed on the shared data object by a given one of the plurality of threads designated as a master thread during the period of time in which the given one of the plurality of threads is designated as the master thread with respect to access operations targeting the shared data object, wherein the given one of the threads is designated as the master thread for the duration of the data access session;

wherein said accessing the shared data object during the data access session comprises;

one or more of the threads performing read accesses on the shared data object in a non-blocking manner;

the given one of the threads designated as the master thread performing one or more data modifications of a thread other than the given one of the threads designated as the master thread that target the shared data object; and

the given one of the threads designated as the master thread determining if any read accesses are in conflict with any data modifications to the shared data object and resolving any conflicts; and

during a subsequent session for accessing the shared data object, a given one of the plurality of threads other than the given one of the threads designated as the master thread being designated as a master thread for the subsequent session.

16. The system as recited in claim 15, wherein the one or more data modifications are performed by the given one of the threads designated as the master thread for the data access session on a first version of the shared data object during the data access session, wherein non-blocking read accesses by threads other than the given one of the threads designated as the master thread for the data access session are performed on a second version of the shared data object during the data access session, wherein the second version of the shared data object remains unmodified during the data access session, and wherein the program instructions are further executable by the processor to cause the processor to perform, after the data access session ends, updating the second version of the shared data object to reflect modifications made to the first version of the shared data object during the data access session.

17. The system as recited in claim 15, wherein the plurality of threads are executed within a single virtual machine process at a single computer host.

18. A non-transitory computer readable storage medium storing program instructions that when executed on one or more computers cause the one or more computers to perform:

a plurality of threads accessing a shared data object during a data access session, wherein a data access session comprises a set of access operations performed on the shared data object by a given one of the plurality of threads designated as a master thread during the period of time in which the given one of the plurality of threads acts is designated as a master thread with respect to access operations targeting the shared data object, and wherein the given one of the threads is designated as the master thread for the duration of the data access session;

wherein said accessing the shared data object during the data access session comprises;

one or more of the threads performing read accesses on the shared data object in a non-blocking manner;

the given one of the threads designated as the master thread performing one or more data modifications of a thread other than the given one of the threads designated as the master thread that target the shared data object; and

the given one of the threads designated as the master thread determining if any read accesses are in conflict with any data modifications to the shared data object and resolving any conflicts; and

during a subsequent session for accessing the shared data object, a given one of the plurality of threads other than the given one of the threads designated as the master thread being designated as a master thread for the subsequent session.

19. The non-transitory computer readable storage medium as recited in claim 18, wherein the modifications are performed by the given one of the thread designated as the master thread for the data access session on a first version of the shared data object during the data access session, wherein non-blocking read accesses by threads other than the given one of the thread designated as the master thread for the data access session are performed on a second version of the shared data object during the data access session, wherein the second version of the shared data object remains unmodified during the data access session, and wherein executing the program instructions further causes the one or more computers to perform, after the data access session ends, updating the second version of the shared data object to reflect modifications made to the first version of the shared data object during the data access session.

20. The non-transitory computer readable storage medium as recited in claim 19, wherein each access to the shared data object by the plurality of threads comprises a virtual memory address specifying a targeted data location within the shared data object.