Software Transactional Memory - Transactional Locking

Transactional Locking

STM can be implemented as a lock-free algorithm or it can use locking. There are two types of locking schemes: In encounter-time locking (Ennals, Saha, and Harris), memory writes are done by first temporarily acquiring a lock for a given location, writing the value directly, and logging it in the undo log. Commit-time locking locks memory locations only during the commit phase.

A commit-time scheme named "Transactional Locking II" implemented by Dice, Shalev, and Shavit uses a global version clock. Every transaction starts by reading the current value of the clock and storing it as the read-version. Then, on every read or write, the version of the particular memory location is compared to the read-version; and, if it's greater, the transaction is aborted. This guarantees that the code is executed on a consistent snapshot of memory. During commit, all write locations are locked, and version numbers of all read and write locations are re-checked. Finally, the global version clock is incremented, new write values from the log are written back to memory and stamped with the new clock version.

An increasingly utilized method to manage transactional conflicts in Transactional memory, and especially in STM, is Commitment ordering (also called Commit ordering; CO). It is utilized for achieving serializability optimistically (i.e., without blocking upon conflict, and only locking for commit) by "commit order" (e.g., Ramadan et al. 2009, and Zhang et al. 2006). Serializability is the basis for the correctness of (concurrent transactions and) transactional memory. Tens of STM articles on "commit order" have already been published, and the technique is encumbered by a number of patents.

(Zhang et al. 2006) is a US patent entitled "Software transaction commit order and conflict management" (which references CO US patent 5701480). Its abstract part is the following:

"Various technologies and techniques are disclosed for applying ordering to transactions in a software transactional memory system. A software transactional memory system is provided with a feature to allow a pre-determined commit order to be specified for a plurality of transactions. The pre-determined commit order is used at runtime to aid in determining an order in which to commit the transactions in the software transactional memory system. A contention management process is invoked when a conflict occurs between a first transaction and a second transaction. The pre-determined commit order is used in the contention management process to aid in determining whether the first transaction or the second transaction should win the conflict and be allowed to proceed."

With CO the desired serializability property is achieved by committing transactions only in chronological order that is compatible with the precedence order (as determined by chronological orders of operations in conflicts) of the respective transactions. To enforce CO some implementation of the Generic local CO algorithm needs to be utilized. The patent abstract quoted above describes a general implementation of the algorithm with a pre-determined commit order (this falls into the category of "CO generic algorithm with real-time constraints").