Read sharing using global conflict indication and semi-transparent reading in a transactional memory space

• US 7,711,909 B1
• Filed: 12/09/2004
• Issued: 05/04/2010
• Est. Priority Date: 12/09/2004
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Oracle America, Inc. (Oracle Corporation)
• Inventors: Moir, Mark S., Lev, Yosef
• Primary Examiner(s): Thai; Tuan V
• Assistant Examiner(s): Ayash; Marwan
• Application Number:
  US11/008,692
• Time in Patent Office: 1,972 Days
• Field of Search: 711/156
• US Class Current: 711/156
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores

Abstract

It has been discovered that globally indicating read-write conflicts and semi-transparent read sharing in a transactional memory space allows for a more expedient validation. Without being aware of particular transactions, a writing transaction can determine that a read-write conflict will occur with some transaction that has read one or more memory locations to be modified by the writing transaction. With semi-transparent reading, reading transactions can validate quickly. If a read-write conflict has not occurred since a reading transaction began (or since the last validation), then the previous reads are valid. Otherwise, the reading transaction investigates each memory location or ownership record to determine if a read-write conflict affected the investigating transaction.

Claims

1. A system, comprising:

one or more processors; and

a memory coupled to the one or more processors and comprising program instructions configured to;

execute a plurality of transactions operating in a transactional memory space within the memory, wherein the transactional memory space comprises a plurality of locations each associated with one of a plurality of ownership records;

wherein the memory further comprises;

a global conflict indication comprising a single value indicating whether a read-write conflict has occurred that affects any of the plurality of locations in the transactional memory space, wherein the global conflict indication is accessible by all of the plurality of transactions operating in the transactional memory space;

means for semi-transparently reading the transactional memory space, wherein to support semi-transparently reading, the memory is configured to indicate in an ownership record associated with one or more locations in the transactional memory that one or more of the plurality of transactions are reading the one or more locations in the transactional memory space without specifically identifying the one or more transactions; and

means for validating transactional reads of the transactional memory space, wherein to validate one or more transactional reads of a given transaction, the means for validating is configured to;

determine whether the value of the global conflict indication indicates that a read-write conflict has occurred in the transactional memory space;

attempt to validate the one or more transactional reads in response to determining that the value of the global conflict indication indicates that a read-write conflict has occurred in the transactional memory; and

allow execution of the given transaction to continue without attempting to validate the one or more transactional reads in response to determining that the value of the global conflict indication indicates that a read-write conflict has not occurred in the transactional memory.

2. The system of claim 1, wherein the memory is further configured to indicate that the one or more transactions are reading the one or more locations associated with the ownership record by maintaining a transaction reading counter for the number of transactions reading the one or more locations in the ownership record.

3. The system of claim 2, wherein to execute transactions, the program instructions are further configured to execute a transaction identifying itself in the ownership record to acquire write ownership of the locations associated with the ownership record.

4. The system of claim 3, wherein to execute a transaction that acquires write ownership, the program instructions are further configured to implement:

the transaction reading the transaction reading counter to determine if a read-write conflict will occur from the transaction writing to at least one of the locations associated with the ownership record; and

,

if it is determined that a read-write conflict will occur, the transaction updating the global conflict indication to indicate the read-write conflict.

5. The system of claim 4, wherein the program instructions are further configured to implement:

the transaction executing said updating the global conflict indication only if the transaction reading counter indicates that other transactions have read at least one of the locations.

6. The system of claim 4,

wherein in executing a transaction that has read at least one of the locations associated with the ownership record, the program instructions are further configured to implement:

the transaction reading the global conflict indication to determine whether a read-write conflict has occurred;

wherein if a read-write conflict has occurred, the program instructions are further configured to implement;

the transaction determining whether the location previously read by the transaction has been modified; and

wherein if a read-write conflict has not occurred, the previous read is valid; and

wherein if the previous read is valid, the program instructions are configured to implement;

the transaction continuing with execution.

7. The system of claim 1, wherein to validate transactional reads, the program instructions are further configured to implement:

a transaction which has read one or more transactional memory space locations reading the global conflict indication to determine whether a read-write conflict has occurred.

8. The system of claim 7, wherein the memory further comprises means for determining whether the read-write conflict affected the locations read by the transaction.

9. The system of claim 7, wherein to determine whether the read-write conflict affected the locations, the program instructions are further configured to execute the transaction determining whether a transaction acquired write ownership for the locations since the transaction read the locations.

10. The system of claim 1, wherein, proximate to a first validation, the program instructions are further configured to execute a transaction recording the global conflict indication;

and wherein, proximate to a subsequent validation, the program instructions are further configured to execute a transaction avoiding determining whether a conflict affected locations read by the transaction if the global conflict indication matches the recorded global conflict indication.

11. The system of claim 10, wherein the program instructions are further configured to execute the transaction recording the global conflict indication prior to beginning validation operations or during validation operations.

12. The system of claim 1, wherein the transactional memory space is implemented in a hardware transactional memory, a software transactional memory, or a hybrid transactional memory.

13. The system of claim 1, wherein the memory is further configured to employ at least one of transparent reading and non-transparent reading for a second transactional memory space within the memory.

14. A method, comprising:

indicating whether a read-write conflict occurred in a transactional memory space comprising a plurality of locations each associated with one of a plurality of ownership records by maintaining a global conflict indication accessible by all of a plurality of transactions operating in the transactional memory space, wherein the global conflict indication comprises a single value indicating whether a read-write conflict has occurred that affects any of the plurality of locations in the transactional memory space; and

validating transactional reads in accordance with the global conflict indication, wherein said validating comprises;

for a given validation operation;

one of the plurality of transactions reading the global conflict indication to determine whether a read-write conflict occurred;

in response to determining that a read-write conflict has occurred, the transaction determining whether the read-write conflict affected any locations read by the transaction; and

in response to determining that the read-write conflict did not affect any locations read by the transaction, allowing the transaction to continue execution.

15. The method of claim 14, further comprising,

for another validation operation:

one of the plurality of transactions reading the global conflict indication to determine whether a read-write conflict occurred; and

in response to determining that the global conflict indication indicates that a read-write conflict has not occurred, the transaction continuing execution without determining whether the read-write conflict affected any locations read by the transaction.

16. The method of claim 14, further comprising a first of the plurality of transactions attempting to modify a set of one or more locations in the transactional memory space while refraining from aborting other ones of the plurality of transactions that have read the set of locations.

17. The method of claim 16, further comprising the first transaction updating the global conflict indication if other ones of the plurality of transactions have read the set of locations.

18. The method of claim 17, further comprising the other transactions aborting themselves if the modifications by the first transaction affect locations read by the other transactions.

19. The method of claim 16 further comprising:

associating one of the plurality of ownership records with the set of locations,

wherein the ownership record indicates a counter for the number of transactions that have read at least one of the set of locations, and

wherein the ownership record indicates the first transaction as having write ownership on the set of locations.

20. The method of claim 19, further comprising:

a transaction incrementing the counter prior to reading at least one of the set of locations; and

the transaction decrementing the counter after validating.

21. The method of claim 19, further comprising the first transaction incrementing the counter to indicate the first transaction reading at least one of the set of locations and refrains from updating the global conflict indication if no other transactions have read at least one of the set of locations.

22. A method, comprising:

a first transaction reading a global conflict indication to determine whether a read-write conflict has occurred in a transactional memory space, wherein the transactional memory space comprises a plurality of locations each associated with one of a plurality of ownership records, and wherein the global conflict indication comprises a single value indicating whether a read-write conflict has occurred that affects any of the plurality of locations in the transactional memory space;

in response to determining that a read-write conflict has occurred, determining whether the read-write conflict corresponds to any locations read by the first transaction; and

in response to determining that the read-write conflict did not correspond to any locations read by the first transaction, the first transaction continuing execution;

wherein the global conflict indication is accessible by all of a plurality of transactions executing in the transactional memory space.

23. The method of claim 22, further comprising:

a second transaction acquiring write ownership for a set of one or more locations in the transactional memory space;

the second transaction determining whether any other transaction has read the set of locations; and

updating the global conflict indication to indicate occurrence of a read-write conflict if any other transaction has read the set of locations.

24. The method of claim 23, further comprising the second transaction accessing at least one of the set of locations without aborting transactions that have read at least one of the set of locations.

25. The method of claim 24, further comprising:

the other transactions determining whether a read-write conflict caused by the second transaction corresponds to transactional memory space locations read by the other transactions; and

in response to one or more of the other transactions determining that a read-write conflict caused by the second transaction corresponds to transactional memory space locations read by the one or more of the other transactions, the one or more of the other transactions aborting themselves.

26. The method of claim 22, further comprising the first transaction continuing to execute if a read-write conflict has not occurred.

27. The method of claim 22, wherein the transactional memory space is implemented with hardware transactional memory, software transactional memory, or hybrid hardware/software transactional memory.

28. The method of claim 22, further comprising the first transaction incrementing a counter for the set of locations to indicate that the first transaction has read at least one of the set of locations prior to validating, but without the first transaction identifying itself.

29. The method of claim 28, further comprising the first transaction decrementing the counter subsequent to the first transaction being either validated or aborted.

30. The method of claim 22, wherein the first transaction determining whether the read-write conflict corresponds to locations read by the first transaction comprises:

reading a write ownership identifier that indicates a transaction that currently possesses write ownership for the locations; and

comparing the write ownership identifier with a previous recording of the write

ownership identifier to determine if the write ownership identifier has changed.

31. An apparatus, comprising:

means for implementing a transactional memory comprising a plurality of storage locations each associated with one of a plurality of ownership records;

means for semi-transparently reading the transactional memory, wherein semi-transparently reading allows writing transactions to be aware of reading transactions by providing an indication in an ownership record associated with one or more locations in the transactional memory that one or more transactions are reading the one or more locations in the transactional memory;

means for determining a read-write conflict between a writing transaction and one or more reading transactions of which the writing transaction is aware; and

means for updating a global conflict indication in response to said determining;

wherein the global conflict indication is accessible by all of a plurality of transactions executing in the transactional memory, and wherein the global conflict indication comprises a single value indicating whether a read-write conflict has occurred that affects any of the plurality of locations in the transactional memory.

32. The apparatus of claim 31, further comprising means for validating transactional reads, wherein to validate one or more transactional reads of a given transaction, the means for validating is configured to:

determine whether the value of the global conflict indication indicates that a read-write conflict has occurred in the transactional memory;

attempt to validate the one or more transactional reads in response to determining that the value of the global conflict indication indicates that a read-write conflict has occurred in the transactional memory; and

allow execution of the given transaction to continue without attempting to validate the one or more transactional reads in response to determining that the value of the global conflict indication indicates that a read-write conflict has not occurred in the transactional memory.

33. The apparatus of claim 31, wherein semi-transparently reading allows writing transactions to be aware of reading transactions, without specifically identifying the reading transactions.

34. The apparatus of claim 31, wherein the means for implementing transactional memory comprises software transactional memory.

35. A computer-readable storage medium comprising:

a first sequence of program instructions executable to implement;

writing at least one location in a set of one or more locations in a transactional memory space comprising a plurality of locations each associated with one of a plurality of ownership records;

accessing one of the plurality of ownership records to determine whether any other transactions have read the set of one or more locations, wherein the ownership record is associated with the set of locations; and

in response to said determining, indicating to all of a plurality of transactions operating in a transactional memory space whether a read-write conflict will occur that corresponds to the set of locations, wherein said indicating comprises updating a global conflict indication that is accessible by all of the plurality of transactions and that comprises a single value indicating whether a read-write conflict has occurred that affects any of the plurality of locations in the transactional memory.

36. The computer-readable storage medium of claim 35, wherein the ownership record includes a counter that indicates a number of transactions that have read at least one of the set of locations.

37. The computer-readable storage medium of claim 35, wherein the first sequence of program instructions is further executable to implement acquiring write ownership for a transaction for the set of locations.

38. The computer-readable storage medium of claim 37, wherein the acquiring write ownership comprises identifying the transaction.

39. The computer-readable storage medium of claim 37, wherein the acquiring write ownership comprises indicating a timestamp.

40. The computer-readable storage medium of claim 38, wherein identifying the transaction comprises identifying the transaction in the ownership record that is associated with the set of locations.

41. The computer-readable storage medium of claim 35, wherein the transactional memory space is implemented with hardware transactional memory, software transactional memory, or a hybrid of hardware and software transactional memory.

42. The computer-readable storage medium of claim 35, wherein the first sequence of program instructions comprises a synchronization construct configured to atomically update at least one of the global conflict indication and the ownership record associated with the set of locations.

43. The computer-readable storage medium of claim 42, wherein the synchronization construct comprises a compare-and-swap instruction, a load-linked/store conditional operation sequence, or a hardware transactional memory access.

44. A computer-readable storage medium comprising:

a first sequence of program instructions executable to implement semi-transparently reading a set of one or more locations in a transactional memory space comprising a plurality of locations each associated with one of a plurality of ownership records, wherein semi-transparently reading comprises indicating in an ownership record associated with the set of one or more locations that one or more transactions are reading the set of one or more locations without specifically identifying the transactions;

a second sequence of program instructions executable to implement validating a transactional read, wherein said validating comprises;

determining whether a value of a global conflict indication indicates that a read-write conflict has occurred in the transactional memory space, wherein the global conflict indication comprises a single value indicating whether a read-write conflict has occurred that affects any of the plurality of locations in the transactional memory space, and wherein the global conflict indication is accessible by all of a plurality of transactions operating in the transactional memory space; and

in response to determining that the value of the global conflict indication indicates that a read-write conflict has occurred that affects one or more of the plurality of locations in the transactional memory space, attempting to validate the transactional read.

45. The computer-readable storage medium of claim 44, wherein the semi-transparent reading comprises transactions indicating acquisition of read ownership for the set of one or more locations without specifically identifying themselves.

46. The computer-readable storage medium of claim 45, wherein the semi-transparent reading comprises the first sequence of program instructions executing incrementing a counter in the ownership record associated with the set of one or more locations prior to reading at least one of the set of one or more locations.

47. The computer-readable storage medium of claim 46 further comprising a third sequence of program instructions executable to implement decrementing the counter in response to a transaction that corresponds to the first sequence of program instructions being aborted or validated.

48. The computer-readable storage medium of claim 46, wherein the ownership record indicates the counter and indicates an identity of a transaction that has held or currently holds write ownership for the set of one or more locations.

49. The computer-readable storage medium of claim 44, wherein said attempting to validate comprises:

determining whether the read-write conflict corresponds to any locations read by a transaction that corresponds to the first sequence of program instructions.

50. The computer-readable storage medium of claim 44 further comprising a third sequence of program instructions executable to implement recording the global conflict indication.

51. The computer-readable storage medium of claim 50, wherein the second sequence of program instructions is further executable to implement:

comparing a previous recording of the global conflict indication with a current reading of the global conflict indication; and

determining that a read-write conflict has occurred if there is a difference between the current reading of the global conflict indication and the previous recording of the global conflict indication.