Address level log-based synchronization of shared data

• US 8,037,476 B1
• Filed: 10/31/2005
• Issued: 10/11/2011
• Est. Priority Date: 09/15/2005
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Oracle America, Inc. (Oracle Corporation)
• Inventors: Shalev, Ori, Shavit, Nir N.
• Primary Examiner(s): Tang; Kenneth
• Application Number:
  US11/263,439
• Time in Patent Office: 2,171 Days
• Field of Search: 718/104, 718/107, 718/108, 712/228, 707/8, 711/150
• US Class Current: 718/104
• CPC Class Codes: G06F 2209/522 Manager
• CPC Class Codes: G06F 2209/523 Mode
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

A method of address-level log-based synchronization comprises a thread attempting to acquire a lock on an object. If its lock attempt fails, a thread logs, at a synchronization log, data access operations directed at the shared data object, and waits for a notification from the lock-owning thread indicating whether the logged operations succeeded. If its lock attempt succeeds, the lock-owning thread performs data access operations on the shared data object, and arbitrates among requests logged by other threads in the synchronization log, applying the modifications logged in the requests that do not conflict with other modification operations, and rejecting the requests that conflict. The master sends a success notification to the logging threads whose requests were accepted, and a failure notification to the logging threads whose requests were rejected.

Claims

1. A computer-implemented method, comprising:

a given thread of a plurality of concurrently executing threads attempting to acquire a lock on a shared data object to be modified by the given thread; and

in response to the thread'"'"'s attempt to acquire the lock being unsuccessful, the given thread;

assuming the role of a slave thread;

logging at a synchronization log one or more data access operations directed to the shared data object, wherein the one or more data access operations comprise at least one write access operation, and wherein said logging comprises recording addresses and modified data values of data locations targeted for modification by the at least one write access operation;

waiting for a notification from a thread holding the lock on the shared data object, wherein the thread holding the lock on the shared data object acts as a master thread with respect to the shared data object, wherein the notification indicates whether or not the one or more data access operations logged by the given thread succeeded, wherein a notification indicating that the one or more data access operations logged by the given thread succeeded indicates that the at least one write access operation logged by the given thread was performed on a particular one of two or more versions of the shared data object by the thread holding the lock on the shared data object; and

wherein the particular one of the two or more versions of the shared data object is accessible as a writable version of the shared data object by the thread holding the lock; and

receiving the notification from the thread holding the lock on the shared data object.

2. The method of claim 1, further comprising:

a second thread of the plurality of concurrently executing threads attempting to acquire the lock on the shared data object to be modified by the second thread; and

in response to acquiring the lock, the second thread;

assuming the role of a master thread with respect to the shared data object;

performing one or more data access operations of the second thread on the shared data object, wherein the one or more data access operations of the second thread comprise at least one write access operation; and

for each of one or more threads of the plurality of concurrently executing threads that have assumed the role of a slave thread;

accessing the synchronization log to determine whether any read access operations logged by the slave thread conflict with write access operations previously performed by the second thread while assuming the role of the master thread;

if no conflicts are found, performing all write access operations logged by the slave thread on the shared data object; and

returning a notification to the slave thread indicating whether or not a set of data access operations logged by the slave thread succeeded, wherein a notification indicating that the set of data access operations logged by the slave thread succeeded indicates that all write access operations logged by the slave thread were performed by the second thread, and wherein a notification indicating that the set of data access operations logged by the slave thread failed indicates that at least one conflict was found.

3. The method as recited in claim 2,

wherein said performing one or more data access operations of the second thread on the shared data object comprises performing the one or more data access operations of the second thread on a first version of the shared data object, wherein the first version of the shared data object includes a first copy of a portion of the shared data object;

wherein the method further comprises, prior to said waiting, the given thread performing one or more read access operations on a second version of the shared data object, wherein the second version of the shared data object includes a second copy of the portion of the shared data object;

wherein said logging one or more data access operations further comprises recording, in the synchronization log, addresses of data locations read by the given thread during performance of the one or more read operations on the second version of the shared data object; and

wherein said recording addresses and modified data values of data locations targeted for modification by the at least one write access operation comprises recording addresses and modified data values of data locations of the second version of the shared data object.

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

the second thread determining, dependent on a value of a mode indicator, that the second thread is to access the first version of the shared data object as the writable version of the shared data object while the second thread holds the lock; and

after returning the notification, the second thread;

modifying the mode indicator to indicate that a next master thread is to access the second version of the shared data object as the writable version of the shared data object; and

releasing the lock.

5. The method as recited in claim 3, further comprising:

an additional thread that does not modify the shared data object reading data of the shared data object from the second version of the shared data object while the second thread holds the lock without attempting to acquire the lock.

6. The method as recited in claim 3, further comprising:

the second thread, after acquiring the lock and prior to performing a data access operation on the first version of the shared data object, determining whether one or more additional threads are currently readers of the first version of the shared data object; and

in response to determining that one or more additional threads are currently readers of the first version of the shared data object, the second thread determining whether to terminate the one or more additional threads or to wait for the one or more additional threads to finish reading the first version of the shared data object before performing any data access operations on the first version of the shared data object.

7. The method as recited in claim 3, further comprising:

the second thread, after acquiring the lock and prior to performing a data access operation on the first version of the shared data object, synchronizing the first and second versions of the shared data object, wherein said synchronizing comprises performing, on the first version of the shared data object, one or more write operations that were previously logged at the synchronization log by an additional thread while the additional thread was acting as the master thread with respect to the shared data object.

8. The method as recited in claim 3, further comprising:

the given thread registering as a reader of the shared data object prior to said performing one or more read access operations on the second version of the shared data object; and

after said performing one or more read access operations on the second version of the shared data object and prior to said waiting, the given thread unregistering as a reader of the shared data object.

9. The method as recited in claim 2, wherein determining whether any read access operations logged by the slave thread conflict with write operations previously performed by the second thread comprises determining whether any portion of the shared data object read in the read access operations overlaps with a portion of the shared data object that has been modified by the second thread.

10. A system, comprising:

a processor; and

a memory coupled to the processor, wherein the memory stores program instructions executable by the processor to implement a code generator that when operating generates code executable by the processor to implement a mechanism to coordinate concurrent accesses to shared data objects by a plurality of threads, wherein according to the mechanism;

a given thread of a plurality of concurrently executing threads attempts to acquire a lock on a shared data object to be modified by the given thread;

in response to the thread'"'"'s attempt to acquire the lock being unsuccessful, the given thread;

assumes the role of a slave thread;

logs at a synchronization log one or more data access operations directed to the shared data object, wherein the one or more data access operations comprise at least one write access operation, and wherein said logging comprises recording addresses and modified data values of data locations targeted for modification by the at least one write access operation;

waits for a notification from a thread holding the lock on the shared data object, wherein the thread holding the lock on the shared data object acts as a master thread with respect to the shared data object, wherein the notification indicates whether or not the one or more data access operations logged by the given thread succeeded, and wherein a notification indicating that the one or more data access operations logged by the given thread succeeded indicates that the at least one write access operation logged by the given thread was performed on a particular one of two or more versions of the shared data object by the thread holding the lock on the shared data object, and wherein the particular one of the two or more versions of the shared data object is accessible as a writable version of the shared data object by the thread holding the lock; and

receives the notification from the thread holding the lock on the shared data object.

11. The system as recited in claim 10, wherein, when operating, the code generator further generates code executable by the processor to:

maintain the synchronization log for the shared data object;

maintain the two or more versions of the shared data object, including a first version and a second version, wherein the first version includes a first copy of a portion of the shared data object, and wherein the second version includes a second copy of the portion of the shared data object; and

maintain a mode indicator for the shared data object, wherein the mode indicator indicates the particular version of the shared data object that the thread currently acting as the master thread with respect to the shared object is to access as a writable version of the shared data object while holding the lock.

12. The system as recited in claim 11, wherein, when operating, the code generator identifies the portion of the shared data object of which the first and second copies are to be maintained.

13. The system as recited in claim 10, wherein, when operating, the code generator identifies, from among a plurality of data objects defined in an application, a particular data object as a shared data object for which the mechanism is to be implemented.

14. The system as recited in claim 10, wherein the code generator is implemented within a virtual machine process that when operating executes an application written in a platform-independent programming language, and wherein the shared data object is defined within the application.

15. The system of claim 10, wherein according to the mechanism:

a second thread of the plurality of concurrently executing threads attempts to acquire the lock on the shared data object to be modified by the second thread; and

in response to acquiring the lock, the second thread;

assumes the role of a master thread with respect to the shared data object;

performs one or more data access operations of the second thread on the shared data object, wherein the one or more data access operations of the second thread comprise at least one write access operation; and

for each of one or more threads of the plurality of concurrently executing threads that have assumed the role of a slave thread;

accesses the synchronization log to determine whether any read access operations logged by the slave thread conflict with write access operations previously performed by the second thread while assuming the role of the master thread;

if no conflicts are found, performs all write access operations logged by the slave thread on the shared data object; and

returns a notification to the slave thread indicating whether or not a set of data access operations logged by the slave thread succeeded, wherein a notification indicating that the set of data access operations logged by the slave thread succeeded indicates that all write access operations logged by the slave thread were performed by the second thread, and wherein a notification indicating that the set of data access operations logged by the slave thread failed indicates that at least one conflict was found.

16. A non-transitory, computer readable storage medium storing program instructions, wherein the instructions are computer-executable to implement a mechanism to coordinate concurrent accesses to shared data objects by a plurality of threads, wherein according to the mechanism:

a given thread of a plurality of concurrently executing threads attempts to acquire a lock on a shared data object to be modified by the given thread;

in response to the thread'"'"'s attempt to acquire the lock being unsuccessful, the given thread;

assumes the role of a slave thread;

logs at a synchronization log one or more data access operations directed to the shared data object, wherein the one or more data access operations comprise at least one write access operation, and wherein said logging comprises recording addresses and modified data values of data locations targeted for modification by the at least one write access operation;

waits for a notification from a thread holding the lock on the shared data object, wherein the thread holding the lock on the shared data object acts as a master thread with respect to the shared data object, wherein the notification indicates whether or not the one or more data access operations logged by the given thread succeeded, and wherein a notification indicating that the one or more data access operations logged by the given thread succeeded indicates that the at least one write access operation logged by the given thread was performed on a particular one of two or more versions of the shared data object by the thread holding the lock on the shared data object, and wherein the particular one of the two or more versions of the shared data object is accessible as a writable version of the shared data object by the thread holding the lock; and

receives the notification from the thread holding the lock on the shared data object.

17. The non-transitory, computer readable storage medium as recited in claim 16, wherein the instructions are further computer-executable to:

maintain the synchronization log for the shared data object;

maintain the two or more versions of the shared data object, including a first version and a second version, wherein the first version includes a first copy of a portion of the shared data object, and wherein the second version includes a second copy of the portion of the shared data object; and

maintain a mode indicator for the shared data object, wherein the mode indicator indicates the particular version of the shared data object that the thread currently acting as the master thread with respect to the shared object is to access as a writable version of the shared data object while holding the lock.

18. The non-transitory, computer readable storage medium as recited in claim 16, wherein the instructions are further computer-executable to identify, from among a plurality of data objects defined in an application, a particular data object or portion thereof as a shared data object for which the mechanism is to be implemented.

19. The non-transitory, computer readable storage medium as recited in claim 16, wherein the instructions are implemented within a virtual machine process that when operating executes an application written in a platform-independent programming language, and wherein the shared data object is defined within the application.

20. The non-transitory, computer readable storage medium of claim 16, wherein according to the mechanism:

a second thread of the plurality of concurrently executing threads attempts to acquire the lock on the shared data object to be modified by the second thread; and

in response to acquiring the lock, the second thread;

assumes the role of a master thread with respect to the shared data object;

performs one or more data access operations of the second thread on the shared data object, wherein the one or more data access operations of the second thread comprise at least one write access operation; and

for each of one or more threads of the plurality of concurrently executing threads that have assumed the role of a slave thread;

accesses the synchronization log to determine whether any read access operations logged by the slave thread conflict with write access operations previously performed by the second thread while assuming the role of the master thread;

if no conflicts are found, performs all write access operations logged by the slave thread on the shared data object; and

returns a notification to the slave thread indicating whether or not a set of data access operations logged by the slave thread succeeded, wherein a notification indicating that the set of data access operations logged by the slave thread succeeded indicates that all write access operations logged by the slave thread were performed by the second thread, and wherein a notification indicating that the set of data access operations logged by the slave thread failed indicates that at least one conflict was found.