Predictive log synchronization

• US 8,060,879 B2
• Filed: 05/30/2006
• Issued: 11/15/2011
• Est. Priority Date: 05/30/2006
• 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): An; Meng
• Assistant Examiner(s): Zhe; Mengyao
• Application Number:
  US11/442,870
• Publication Number:
  US 20080005112A1
• Time in Patent Office: 1,995 Days
• Field of Search: 718/102
• US Class Current: 718/102
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

A method for coordinating shared access to data objects comprises applying modification operations to a data object from a first thread of a plurality of threads on behalf of all the other threads during a session in which the first thread owns a lock on the data object. Each modification operation corresponds to a respective entry recorded in a log associated with the data object by a respective thread. The method may further comprise predicting, for a second thread, a result of a particular operation requested by the second thread on the data object. The result may be predicted using log entries corresponding to modification operations that have not yet been applied to the data object. In addition, the method includes performing one or more other operations in a non-blocking manner from the second thread during the session, where at least one other operation is dependent on the predicted result.

Claims

1. A computer-implemented method for sharing access to a data object by a plurality of threads, comprising:

applying modification operations to the data object from a first thread of the plurality of threads on behalf of all other threads of the plurality of threads during a session in which the first thread owns a lock on the data object, wherein each of the modification operations corresponds to a respective entry recorded in a log by a respective thread of the plurality of threads;

predicting, for a second thread of the plurality of threads, a result of a particular operation requested by the second thread on the data object, wherein said predicting comprises using one or more entries in the log corresponding to one or more of the modification operations that have not yet been applied to the data object; and

performing one or more other operations in a non-blocking manner from the second thread during the session, wherein at least one other operation of the one or more other operations is dependent on the predicted result of the particular operation.

2. The method as recited in claim 1, wherein the particular operation includes a read operation.

3. The method as recited in claim 1, wherein the particular operation includes a modification operation.

4. The method as recited in claim 1, wherein each entry recorded in the log corresponds to one or more operations of a method expressed in a programming language.

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

applying the one or more modification operations to a first version of the data object during the session, wherein said applying is performed from the first thread; and

wherein said predicting comprises reading a second version of the data object from the second thread, wherein the second version is not modified during the session.

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

releasing the lock on the data object from the first thread to end the session;

acquiring the lock on the data object from a different thread of the plurality of threads to initiate a new session; and

applying a modification operation from the different thread to the second version of the data object during the new session;

wherein the first version of the data object is not modified during the new session.

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

incrementing a version number associated with the data object from the first thread prior to releasing the lock.

8. The method as recited in claim 7, wherein said predicting comprises:

(a) recording the version number from the second thread;

(b) extracting state information for the data object at the second thread using the second version of the data object after recording the version number;

(c) determining, from the second thread after extracting the state information, whether the version number has changed since the version number was last recorded; and

if the version number has changed, repeating (a), (b) and (c) from the second thread until a result of said determining indicates that the version number has not changed since the version number was last recorded.

9. The method as recited in claim 7, wherein said predicting further comprises:

storing, at the second thread, an object representing a state of the data object, wherein said representation is dependent on the state information;

applying, to the object from the second thread, the one or more modification operations that have not yet been applied to the first version of the data object by the first thread.

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

recording a particular entry in the log from the second thread, wherein said recording comprises appending the particular entry to the log using an atomic compare and swap operation.

11. A system, comprising:

a processor; and

memory coupled to the processor, wherein the memory stores program instructions executable by the processor to implement a mechanism to coordinate concurrent accesses to data objects, wherein according to the mechanism;

a first thread of a plurality of threads applies modification operations to a data object behalf of all other threads of the plurality of threads during a session in which the first thread owns a lock on the data object, wherein each of the modification operations corresponds to a respective entry recorded in a log by a respective thread of the plurality of threads;

a second thread of the plurality of threads predicts a result of a particular operation requested by the second thread on the data object, wherein said predicting comprises using one or more entries in the log corresponding to one or more of the modification operations that have not yet been applied to the data object; and

the second thread performs one or more other operations in a non-blocking manner during the session, wherein the one or more other operations are dependent on the predicted result of the particular operation.

12. The system as recited in claim 11, wherein the particular operation includes a read operation.

13. The system as recited in claim 11, wherein the particular operation includes a modification operation.

14. The system as recited in claim 11, wherein each entry recorded in the log corresponds to one or more operations of a method expressed in a programming language.

15. The system as recited in claim 11, wherein according to the mechanism,

the first thread applies the one or more modification operations to a first version of the data object during the session;

and

wherein, to predict the result of the particular operation, the second thread reads a second version of the data object, wherein the second version is not modified during the session.

16. The system as recited in claim 15, wherein according to the mechanism,

the first thread releases the lock on the data object to end the session;

a different thread of the plurality of threads acquires the lock on the data object to initiate a new session; and

the different thread applies a modification operation to the second version of the data object during the new session,

wherein the first version of the data object is not modified during the new session.

17. A computer-readable storage medium, comprising program instructions, wherein the instructions are computer executable to implement a mechanism to coordinate concurrent accesses to data objects, wherein according to the mechanism:

a first thread of a plurality of threads applies modification operations to a data object behalf of all other threads of the plurality of threads during a session in which the first thread owns a lock on the data object, wherein each of the modification operations corresponds to a respective entry recorded in a log by a respective thread of the plurality of threads;

a second thread of the plurality of threads predicts a result of a particular operation requested by the second thread on the data object, wherein said predicting comprises using one or more entries in the log corresponding to one or more of the modification operations that have not yet been applied to the data object; and

the second thread performs one or more other operations in a non-blocking manner during the session, wherein the one or more other operations are dependent on the predicted result of the particular operation.

18. The storage medium as recited in claim 17, wherein each entry recorded in the log corresponds to one or more operations of a method expressed in a programming language.

19. The storage medium as recited in claim 17, wherein according to the mechanism,

the first thread applies the one or more modification operations to a first version of the data object during the session;

and

wherein, to predict the result of the particular operation, the second thread reads a second version of the data object, wherein the second version is not modified during the session.

20. The storage medium as recited in claim 19, wherein according to the mechanism,

the first thread releases the lock on the data object to end the session;

a different thread of the plurality of threads acquires the lock on the data object to initiate a new session; and

the different thread applies a modification operation to the second version of the data object during the new session,

wherein the first version of the data object is not modified during the new session.