Efficient and consistent software transactional memory

摘要

A method and apparatus for efficient and consistent validation/conflict detection in a Software Transactional Memory (STM) system is herein described. A version check barrier is inserted after a load to compare versions of loaded values before and after the load. In addition, a global timestamp (GTS) is utilized to track a latest committed transaction. Each transaction is associated with a local timestamp (LTS) initialized to the GTS value at the start of a transaction. As a transaction commits it updates the GTS to a new value and sets versions of modified locations to the new value. Pending transactions compare versions determined in read barriers to their LTS. If the version is greater than their LTS indicating another transaction has committed after the pending transaction started and initialized the LTS, then the pending transaction validates its read set to maintain efficient and consistent transactional execution.

主权项

1. One or more tangible machine readable storage medium storing code, which when executed, causes the machine to perform the operations of:
maintaining a global most recent transaction timestamp to be updated in response to a commit of any transaction of a plurality of transactions; starting a new transaction, wherein starting the new transaction comprises copying the global most recent transaction timestamp to a first local timestamp of the new transaction; in response to executing a current read in the new transaction, comparing a version number of a metadata location associated with the current read to the first local timestamp to determine whether the global most recent transaction timestamp has been updated between starting the new transaction and executing the current read, wherein the global most recent transaction timestamp being updated is indicative of a transaction of the plurality of transactions having committed between starting the new transaction and executing the current read; executing one or more prior reads in the new transaction between starting the new transaction and executing the current read, wherein executing the one or more prior reads comprises adding a version number of a metadata location associated with each of the prior reads to a current read set of the new transaction; determining whether the current read set for the new transaction including the one or more prior reads executed between starting the new transaction and the current read is valid in response to determining that the global most recent transaction timestamp has been updated, wherein determining whether the current read set is valid comprises comparing each of the one or more version numbers of the current read set to a version number of the metadata location associated with the corresponding prior read; continuing execution of the new transaction in response to determining that the global most recent transaction timestamp has not been updated; continuing execution of the new transaction in response to determining that the current read set including the one or more prior reads executed from starting the new transaction to the current read is valid, wherein continuing execution of the new transaction comprises performing the current read; and aborting the new transaction in response to determining that the current read set including the one or more prior reads executed from starting the new transaction to the current read is not valid, wherein aborting the new transaction comprises reversing changes to memory made by the new transaction.