Efficient retry for transactional memory
Various technologies and techniques are disclosed for implementing retrying transactions in a transactional memory system. The system allows a transaction to execute a retry operation. The system registers for waits on every read in a read set of the retrying transaction. The retrying transaction waits for notification that something in the read set has changed. A transaction knows if notification is required in one of two ways. If the transactional memory word contained a waiters bit during write lock acquisition, then during release the transactional memory word is looked up in an object waiters map, and waiting transactions are signaled. If a writing transaction finds a global count of waiting transactions to be greater than zero after releasing write locks, a transaction waiters map is used to determine which waiting transactions need to be signaled. In each case, the write lock is released using a normal store operation.
1. A computer storage medium having computer-executable instructions for causing a computer to perform steps comprising:
allowing a retrying transaction to execute a retry operation;
registering for waits on every read in a read set of the retrying transaction;
causing the retrying transaction to wait for notification that something in the read set has changed; and
initiating a wait notification from a transaction that is releasing a write lock, the write lock being released with a normal store operation.
2. The computer storage medium of claim 1 , further having computer-executable instructions for causing a computer to perform steps comprising:
receiving the wait notification from the signaling transaction, and then proceeding with waking up the retrying transaction, undoing all wait registrations, and re-executing the retrying transaction.
3. The computer storage medium of claim 1 , wherein upon rolling back the retrying transaction, all normal rollback processing is performed.
4. The computer storage medium of claim 1 , wherein upon rolling back the retrying transaction, if the transaction is also determined to already be inconsistent, then retrying the transaction immediately.
5. The computer storage medium of claim 1 , wherein the registering for waits step comprises the steps of:
for each optimistic read in the read set of the retrying transaction, if a transactional memory word is currently locked by another transaction, then adding an entry in a global transaction waiters map indicating the retrying transaction is waiting for a locking transaction to release the write lock.
6. The computer storage medium of claim 1 , wherein the registering for waits step comprises the steps of:
for each optimistic read in the read set of the retrying transaction:
ensuring a transactional memory word is not currently locked by another transaction;
if the optimistic read is invalid, then finishing rollback as normal and stopping the registering for waits; and
if the optimistic read is valid, setting a waiters bit using an atomic series of one or more writes.
7. The computer storage medium of claim 6 , wherein the registering for waits step further comprises the steps of:
if the atomic series of one or more writes was successful, then adding an entry to a global object waiters map to indicate the retrying transaction is waiting for any change to the read set.
8. The computer storage medium of claim 7 , wherein the registering for waits step further comprises the steps of:
if the atomic series of one or more writes was not successful, and failed because another transaction had written a different version number into the transactional memory word, then finish rollback processing as normal without registering any more waits.
9. The computer storage medium of claim 8 , wherein the registering for waits step further comprises the steps of:
if the atomic series of one or more writes was not successful, and failed because another transaction had written a write-lock value into the transactional memory word, then adding an entry in a global transaction waiters map indicating the retrying transaction is waiting for a locking transaction to release the write lock.
10. A method for performing a wait notification for a retrying transaction comprising the steps of:
forming a new value for a transactional memory word based on an original value of the transactional memory word in a write log of a transaction;
if the original value of the transactional memory word from the write log contains a waiters bit, looking up the transactional memory word in an object waiters map, signaling each waiting transaction, and then releasing the write lock.
11. The method of claim 10 , wherein the write lock is released with a normal store of the new transactional memory word value.
12. The method of claim 10 , wherein the stages are repeated for each individual write lock release.
13. The method of claim 12 , after all write locks are released, executing a memory barrier operation to ensure proper ordering of memory read and write operations.
14. The method of claim 13 , wherein if a count of transaction waiters is read after the memory barrier operation and the count is greater than zero, then acquiring a global waiters lock, looking in the transaction waiters map and signaling any other transaction that is waiting for the transaction to release a held lock, and then releasing the global waiters lock.
15. A method for starting a rollback with just a retrying transaction and progressively expanding to ancestors of the retrying transaction comprising the steps of:
rolling back just a retrying transaction and performing a first wait on a first read set of the retrying transaction;
after waiting for some particular time, performing a backoff process to backoff and roll back an immediate parent of the retrying transaction, adding a second wait on a second read set of the parent transaction; and
repeating the backoff process until rollback of a top-most parent, adding an additional wait for each next parent.
16. The method of claim 15 , wherein an aggregate of the first wait, second wait, and any additional waits are associated with the top-most parent.
17. The method of claim 16 , wherein any notification will result in re-execution of the top-most parent.
18. The method of claim 15 , wherein heuristics are used as part of the backoff process.