Fine-locked transactional memory

• US 7,792,805 B2
• Filed: 05/30/2006
• Issued: 09/07/2010
• Est. Priority Date: 05/30/2006
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Oracle America, Inc. (Oracle Corporation)
• Inventors: Dice, David, Shavit, Nir N.
• Primary Examiner(s): Trujillo; James
• Assistant Examiner(s): Conyers; Dawaune
• Application Number:
  US11/443,234
• Publication Number:
  US 20070282838A1
• Time in Patent Office: 1,561 Days
• Field of Search: 707/8
• US Class Current: 707/704
• CPC Class Codes: G06F 9/3004 to perform operations on memory
• CPC Class Codes: G06F 9/30087 Synchronisation or serialisation instructions
• CPC Class Codes: G06F 9/3834 Maintaining memory consistency
• CPC Class Codes: G06F 9/467 Transactional memory G06F9/528 takes precedence

Abstract

A method comprises associating a plurality of locks with a data object accessed concurrently by a plurality of threads, where each lock corresponds to a respective partition of the object. The method includes using a first non-blocking transaction (such as a Hardware Transactional-Memory (HTM) transaction) to attempt to complete a programmer-specified transaction. The first non-blocking transaction may access one or more of the locks but may not actually acquire any of the locks. In response to an indication that the first non-blocking transaction failed to complete, the method may include acquiring a set of locks in another non-blocking transaction, where the set of locks corresponds to a set of partitions expected to be accessed in the programmer-specified transaction. If the set of locks is acquired, the method may include performing the memory access operations of the programmer-specified transaction, and releasing the set of locks.

Claims

1. A computer-implemented method, comprising:

partitioning at least a portion of shared memory accessible concurrently by a plurality of threads, into a plurality of partitions and associating the plurality of partitions with respective locks;

a first of the plurality of threads attempting to execute as an atomic memory transaction a first set of operations, the first set of operations including accesses to one or more of the plurality of partitions, wherein the accesses are performed in a first transactional mode, said performing the accesses in the first transactional mode being dependent on reading but not on acquiring those of the plurality of locks associated with the one or more accessed partitions;

receiving an indication that the attempt to execute the first set of operations as an atomic memory transaction in the first transactional mode failed and in response, attempting to execute the first set of operations as an atomic memory transaction in a second transactional mode, said executing the operations in a second transactional mode comprising;

attempting to execute a second set of operations to acquire a subset of the plurality of locks associated with the partitions accessed by the first set of operations, wherein the second set of operations is executed as an atomic memory transaction in the first transactional mode;

performing the first set of operations; and

releasing the acquired locks.

2. The method as recited in claim 1, wherein the first transactional mode comprises a hardware transactional-memory (HTM) transaction.

3. The method as recited in claim 1, wherein said releasing the acquired locks is performed within an other transaction in the first transactional mode.

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

in response to receiving an indication that the attempt to execute the second set of operations failed attempting to acquire the subset of the plurality of locks in a sequence dependent on an ordering of addresses of the partitions corresponding to the subset of locks.

5. The method as recited in claim 1, wherein each lock of the plurality of locks supports a plurality of lock modes including a read mode and a write mode.

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

determining that the first set of operations includes a read but not a write of a particular partition of the plurality of partitions;

determining, using a probability function, whether a particular lock associated with the particular partition is to be acquired in the read lock mode, or whether an indication of a conditional acquisition of the particular lock is to be stored without acquiring the lock;

if the lock is to be acquired in the read lock mode, including the particular lock in the subset of locks; and

if an indication of a conditional acquisition of the particular lock is to be stored,

storing an indication of the conditional acquisition without acquiring the particular lock; and

verifying that a write lock on the particular partition has not been acquired on behalf of an other thread prior to reading the particular partition.

7. The method as recited in claim 6, wherein the indication of the conditional acquisition is stored within a thread-local variable of the particular thread.

8. The method as recited in claim 6, wherein the particular lock comprises a read version counter indicating a number of times that a number of concurrent holders of the lock in read mode has changed from a value greater than zero to a value of zero.

9. The method as recited in claim 6, further comprising, if the indication of the conditional acquisition is to be stored, storing a value of the read version counter in a thread-local variable.

10. The method as recited in claim 9, wherein said verifying that a write lock on the particular partition has not been acquired comprises verifying that a value of the read version counter has not changed since the indication of the conditional acquisition was stored.

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

prior to acquiring the subset of locks, executing at least a portion of the first set of operations in a speculative run-ahead mode of operation at a processor to identify at least one of the one or more of the plurality of partitions expected to the accessed by the first set of operations.

12. The method as recited in claim 1 further comprising:

partitioning the shared memory into the plurality of partitions in accordance with received input.

13. A system, comprising:

one or more processors; and

a memory coupled to the processors, wherein the memory stores program instructions executable by the one or more processors to;

partition at least a portion of shared memory accessible concurrently by a plurality of threads, into a plurality of partitions and associate the plurality of partitions with respective locks;

a first of the plurality of threads attempting to execute a first set of operations as an atomic memory transaction, the first set of operations including accesses to one or more of the plurality of partitions, wherein the accesses are performed in a first transactional mode, said performing the accesses in the first transactional mode being dependent on reading but not on acquiring those of the plurality of locks associated with the one or more accessed partitions;

receive an indication that the attempt to execute the first set of operations as an atomic memory transaction in the first transactional mode failed and in response, attempt to execute the first set of operations as an atomic memory transaction in a second transactional mode, said executing the operations in a second transactional mode comprising;

attempting to execute a second set of operations to acquire a subset of the plurality of locks associated with the partitions accessed by the first set of operations, wherein the second set of operations is executed as an atomic memory transaction in the first transactional mode;

perform the first set of operations; and

release the acquired locks.

14. The system as recited in claim 13, wherein the first transactional mode comprises a hardware transactional-memory (HTM) transaction.

15. The system as recited in claim 13, wherein the instructions are further executable to:

respond to receiving an indication that the attempt to execute the second set of operations failed, attempt to acquire the subset of the plurality of locks in a sequence dependent on an ordering of addresses of the partitions corresponding to the subset of locks.

16. The system as recited in claim 13, wherein each lock of the plurality of locks supports a plurality of lock modes including a read mode and a write mode, and wherein the instructions are further executable to:

determine that the first set of operations includes a read but not a write of a particular partition of the plurality of partitions;

determine, using a probability function, whether a particular lock associated with the particular partition is to be acquired in the read lock mode, or whether an indication of a conditional acquisition of the particular lock is to be stored without acquiring the lock;

if the lock is to be acquired in the read lock mode, include the particular lock in the subset of locks; and

if an indication of a conditional acquisition of the particular lock is to be stored,

store an indication of the conditional acquisition without acquiring the particular lock; and

verify that a write lock on the particular partition has not been acquired on behalf of an other thread prior to reading the particular partition.

17. A computer readable storage medium, comprising program instructions, wherein the instructions are computer-executable to:

partition at least a portion of shared memory accessible concurrently by a plurality of threads, into a plurality of partitions and associate the plurality of partitions with respective locks;

a first of the plurality of threads attempting to execute a first set of operations as an atomic memory transaction, the first set of operations including accesses to one or more of the plurality of partitions, wherein the accesses are performed in a first transactional mode, said performing the accesses in the first transactional mode being dependent on reading but not on acquiring those of the plurality of locks associated with the one or more accessed partitions;

receive an indication that the attempt to execute the first set of operations as an atomic memory transaction in the first transactional mode failed and in response, attempt to execute the first set of operations as an atomic memory transaction in a second transactional mode, said executing the operations in a second transactional mode comprising;

attempting to execute a second set of operations to acquire a subset of the plurality of locks associated with the partitions accessed by the first set of operations, wherein the second set of operations is executed as an atomic memory transaction in the first transactional mode;

perform the first set of operations; and

release the acquired locks.

18. The storage medium as recited in claim 17, wherein the first transactional mode comprises a hardware transactional-memory (HTM) transaction.

19. The storage medium as recited in claim 17, wherein the instructions are further executable to:

respond to receiving an indication that the attempt to execute the second set of operations failed, attempt to acquire the subset of the plurality of locks in a sequence dependent on an ordering of addresses of the partitions corresponding to the other subset of locks.

20. The storage medium as recited in claim 17, wherein each lock of the plurality of locks supports a plurality of lock modes including a read mode and a write mode, and wherein the instructions are further executable to:

determine that the first set of operations includes a read but not a write of a particular partition of the plurality of partitions;

determine, using a probability function, whether a particular lock associated with the particular partition is to be acquired in the read lock mode, or whether an indication of a conditional acquisition of the particular lock is to be stored without acquiring the lock;

if the lock is to be acquired in the read lock mode, include the particular lock in the subset of locks; and

if an indication of a conditional acquisition of the particular lock is to be stored,

store an indication of the conditional acquisition without acquiring the particular lock; and

verify that a write lock on the particular partition has not been acquired on behalf of an other thread prior to reading the particular partition.