Globally incremented variable or clock based methods and apparatus to implement parallel transactions

• US 8,028,133 B2
• Filed: 01/30/2007
• Issued: 09/27/2011
• Est. Priority Date: 02/22/2006
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Oracle America, Inc. (Oracle Corporation)
• Inventors: Shalev, Ori, Moir, Mark, Shavit, Nir N., Dice, David
• Primary Examiner(s): Elmore; Reba I
• Application Number:
  US11/699,802
• Publication Number:
  US 20070239943A1
• Time in Patent Office: 1,701 Days
• Field of Search: 711/152, 711/153, 711/173
• US Class Current: 711/152
• CPC Class Codes: G06F 9/466 Transaction processing

Abstract

The present disclosure describes a unique way for each of multiple processes to operate in parallel and use the same shared data without causing corruption to the shared data. For example, during a commit phase, a corresponding transaction can attempt to increment a globally accessible version information variable and store a current value of the globally accessible version information variable for updating version information associated with modified data regardless of whether an associated attempt by the corresponding transaction to modify the globally accessible version information variable was successful. As an alternative mode, a corresponding transaction can merely read and store a current value of the globally accessible version information variable without attempting to update the globally accessible version information variable before such use. In yet another application, a parallel processing environment implements a combination of both aforementioned modes depending on a self-abort rate of the transaction.

Claims

1. A method comprising:

accessing globally accessible shared data to execute a corresponding transaction of multiple transactions being executed in parallel with each other, the globally accessible shared data accessible by each of the multiple transactions;

accessing a globally accessible version information variable indicating when the globally accessible shared data was last modified and utilized by each of multiple processes executing the multiple transactions to maintain version information associated with the globally accessible shared data, the globally accessible version information variable accessible by each of the multiple transactions; and

after completion of the corresponding transaction, initiating at least one of mode A and mode B, wherein mode A includes;

for the corresponding transaction, storing a current value of the globally accessible version information regardless of whether an associated attempt by the corresponding transaction to modify the globally accessible version information variable was successful, the current value used by the corresponding transaction for maintaining the version information associated with the globally accessible shared data, and

wherein mode B includes;

for the corresponding transaction, retrieving a current value of the globally accessible version information variable for maintaining the version information associated with the globally accessible shared data.

2. A method as in claim 1 further comprising:

utilizing the stored current value of the globally accessible version information variable to update version information associated with the globally accessible shared data even though the associated attempt by the corresponding transaction failed as a result of another transaction attempting to simultaneously modify the globally accessible version information variable.

3. A method as in claim 2, wherein utilizing the stored current value to update the version information occurs after obtaining write locks with respect to corresponding accessed shared data that was modified locally during execution of the corresponding transaction, the write locks preventing other concurrent transactions from modifying the corresponding shared data.

4. A method as in claim 1 further comprising:

at a start time with respect to execution of the corresponding transaction, storing a current value of a globally accessible version information variable;

at a commit time with respect to execution of the corresponding transaction, initiating the modification of the globally accessible version information variable.

5. A method as in claim 1, wherein initiating modification of the globally accessible version information variable may occur around a same time as another process attempts to modify the globally accessible version information variable, the initiated modification by the corresponding transaction failing as a result of write contention between the corresponding transaction and another concurrent transaction attempting to modify the globally accessible version information variable at the same time.

6. A method as in claim 1, wherein storing the current value of the globally accessible version information in mode A occurs after failure of the attempt to modify the globally accessible version information variable.

7. A method as in claim 1, wherein mode B further includes:

initiating modification of the globally accessible version information variable when aborting the corresponding transaction.

8. A method as in claim 1 further comprising:

selectively switching between initiation of mode A and mode B at an end of each of multiple successive transactions following execution of the corresponding transaction.

9. A method as in claim 8 further comprising:

monitoring an abort rate associated with the multiple successive transactions;

initiating selection of mode B to carry out completion of future transactions based on detecting a corresponding low abort rate.

10. A method as in claim 1 further comprising:

associating a first portion of random values with mode A;

associating a second portion of random values with mode B;

initiating generation of a random value; and

selecting mode A for completing the corresponding transaction if the generated random value is included in the first portion of random values and selecting mode B for completing the corresponding transaction if the generated random value is included in the second portion of random values.

11. A method as in claim 10, wherein allocation of the first portion and the second portion depend on successful completion of multiple transactions.

12. A method as in claim 1, wherein accessing the globally accessible version information variable and accessing the globally accessible shared data includes:

at a start of the corresponding transaction, storing a current value of the globally accessible version information variable as an RV-value for the corresponding transaction;

initiating virtual execution of the corresponding transaction based on use of a local read set and write set with respect to the corresponding transaction; and

after the virtual execution, attempting to commit values in the write set associated with the corresponding transaction to the shared data, the write set including accessed shared data that has been modified locally by the corresponding transaction.

13. A method as in claim 12, wherein attempting to commit the values in the write set includes:

obtaining a lock over each globally accessible shared variable modified locally as indicated in the write set;

storing data values associated with the write set to corresponding locations in the globally accessible shared data;

releasing obtained locks; and

updating globally accessible version information associated with the corresponding locations in the globally accessible shared data.

14. A computer system comprising:

a processor;

a memory unit that stores instructions associated with an application executed by the processor; and

an interconnect coupling the processor and the memory unit, enabling the computer system to execute the application and perform operations of;

accessing globally accessible shared data to execute a corresponding transaction of multiple transactions being executed in parallel with each other, the globally accessible shared data accessible by each of the multiple transactions;

accessing a globally accessible version information variable indicating when the globally accessible shared data was last modified and utilized by each of multiple processes executing the multiple transactions to maintain version information associated with the globally accessible shared data, the globally accessible version information variable accessible by each of the multiple transactions; and

after completion of the corresponding transaction, initiating at least one of mode A and mode B, wherein mode A includes;

for the corresponding transaction, storing a current value of the globally accessible version information regardless of whether an associated attempt by the corresponding transaction to modify the globally accessible version information variable was successful, the current value used by the corresponding transaction for maintaining the version information associated with the globally accessible shared data, and

wherein mode B includes;

for the corresponding transaction, retrieving a current value of the globally accessible version information variable for maintaining the version information associated with the globally accessible shared data.

15. A computer system as in claim 14 further supporting operations of:

utilizing the stored current value of the globally accessible version information variable to update version information associated with the globally accessible shared data even though the associated attempt by the corresponding transaction failed as a result of another transaction attempting to simultaneously modify the globally accessible version information variable; and

wherein utilizing the stored current value to update the version information occurs after obtaining write locks with respect to corresponding accessed shared data that was modified locally during execution of the corresponding transaction, the write locks preventing other concurrent transactions from modifying the corresponding shared data.

16. A computer system as in claim 14, wherein mode B further includes:

initiating modification of the globally accessible version information variable when aborting the corresponding transaction.

17. A computer system as in claim 14 further supporting operations of:

selectively switching between initiation of mode A and mode B at an end of each of multiple successive transactions following execution of the corresponding transaction.

18. A computer system as in claim 14, wherein accessing the globally accessible version information variable and accessing the globally accessible shared data includes:

at a start of the corresponding transaction, storing a current value of the globally accessible version information variable as an RV-value for the corresponding transaction;

initiating virtual execution of the corresponding transaction based on use of a local read set and write set with respect to the corresponding transaction; and

after the virtual execution, attempting to commit values in the write set associated with the corresponding transaction to the shared data, the write set including accessed shared data that has been modified locally by the corresponding transaction.

19. A computer system as in claim 18, wherein attempting to commit the values in the write set includes:

obtaining a lock over each globally accessible shared variable modified locally as indicated in the write set;

storing data values associated with the write set to corresponding locations in the globally accessible shared data;

releasing obtained locks; and

updating globally accessible version information associated with the corresponding locations in the globally accessible shared data.

20. A computer program product including a computer-readable storage medium having instructions stored thereon for processing data information, such that the instructions, when carried out by a processing device, enable the processing device to:

access globally accessible shared data to execute a corresponding transaction of multiple transactions being executed in parallel with each other, the globally accessible shared data accessible by each of the multiple transactions;

access a globally accessible version information variable indicating when the globally accessible shared data was last mofified and utilized by each of multiple processes executing the multiple transactions to maintain version information associated with the globally accessible shared data, the globally accessible version information variable accessible by each of the multiple transactions; and

after completion of the corresponding transaction, initiating at least one of mode A and mode B, wherein mode A includes;

for the corresponding transaction, storing a current value of the globally accessible version information regardless of whether an associated attempt by the corresponding transaction to modify the globally accessible version information variable was successful, the current value used by the corresponding transaction for maintaining the version information associated with the globally accessible shared data, and

wherein mode B includes;

for the corresponding transaction, retrieving a current value of the globally accessible version information variable for maintaining the version information associated with the globally accessible shared data.