Jay Taylor's notes

back to listing index

Software transactional memory - Wikipedia

[web search]
Original source (en.wikipedia.org)
Tags: memory transactions en.wikipedia.org
Clipped on: 2025-08-21

Jump to content
Image (Asset 1/5) alt= —Tim Harris et al., "Composable Memory Transactions", Section 2: Background, pg.2[6]

With STM, this problem is simple to solve: simply wrapping two operations in a transaction makes the combined operation atomic. The only sticking point is that it is unclear to the caller, who is unaware of the implementation details of the component methods, when it should attempt to re-execute the transaction if it fails. In response, the authors proposed a retry command which uses the transaction log generated by the failed transaction to determine which memory cells it read, and automatically retries the transaction when one of these cells is modified, based on the logic that the transaction will not behave differently until at least one such value is changed.

The authors also proposed a mechanism for composition of alternatives, the orElse function. It runs one transaction and, if that transaction does a retry, runs a second one. If both retry, it tries them both again as soon as a relevant change is made.[clarification needed] This facility, comparable to features such as the Portable Operating System Interface (POSIX) networking select() call, allows the caller to wait on any one of a number of events simultaneously. It also simplifies programming interfaces, for example by providing a simple mechanism to convert between blocking and nonblocking operations.

This scheme has been implemented in the Glasgow Haskell Compiler.

Proposed language support

[edit]

The conceptual simplicity of STMs enables them to be exposed to the programmer using relatively simple language syntax. Tim Harris and Keir Fraser's "Language Support for Lightweight Transactions" proposed the idea of using the classical conditional critical region (CCR) to represent transactions. In its simplest form, this is just an "atomic block", a block of code which logically occurs at a single instant:

// Insert a node into a doubly linked list atomically
atomic {
    newNode->prev = node;
    newNode->next = node->next;
    node->next->prev = newNode;
    node->next = newNode;
}

When the end of the block is reached, the transaction is committed if possible, or else aborted and retried. (This is simply a conceptual example, not correct code. For example, it behaves incorrectly if node is deleted from the list during the transaction.)

CCRs also permit a guard condition, which enables a transaction to wait until it has work to do:

atomic (queueSize > 0) {
    remove item from queue and use it
}

If the condition is not satisfied, the transaction manager will wait until another transaction has made a commit that affects the condition before retrying. This loose coupling between producers and consumers enhances modularity compared to explicit signaling between threads. "Composable Memory Transactions"[6] took this a step farther with its retry command (discussed above), which can, at any time, abort the transaction and wait until some value previously read by the transaction is modified before retrying. For example:

atomic {
    if (queueSize > 0) {
        remove item from queue and use it
    } else {
        retry
    }
}

This ability to retry dynamically late in the transaction simplifies the programming model and opens up new possibilities.

One issue is how exceptions behave when they propagate outside of transactions. In "Composable Memory Transactions",[6] the authors decided that this should abort the transaction, since exceptions normally indicate unexpected errors in Concurrent Haskell, but that the exception could retain information allocated by and read during the transaction for diagnostic purposes. They stress that other design decisions may be reasonable in other settings.

Transactional locking

[edit]

STM can be implemented as a lock-free algorithm or it can use locking.[7] 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 is 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.

Implementation issues

[edit]

One problem with implementing software transactional memory with optimistic reading is that it is possible for an incomplete transaction to read inconsistent state (that is, to read a mixture of old and new values written by another transaction). Such a transaction is doomed to abort if it ever tries to commit, so this does not violate the consistency condition enforced by the transactional system, but it is possible for this "temporary" inconsistent state to cause a transaction to trigger a fatal exceptional condition such as a segmentation fault or even enter an endless loop, as in the following contrived example from Figure 4 of "Language Support for Lightweight Transactions":

atomic {
    if (x != y)
        while (true) { 
        }
}
atomic {
    x++;
    y++;
}
Transaction A
Transaction B

Provided x=y initially, neither transaction above alters this invariant, but it is possible that transaction A will read x after transaction B updates it but read y before transaction B updates it, causing it to enter an infinite loop. The usual strategy for dealing with this is to intercept any fatal exceptions and abort any transaction that is not valid.

One way to deal with these issues is to detect transactions that execute illegal operations or fail to terminate and abort them cleanly; another approach is the transactional locking scheme.

Practical implementations

[edit]

References

[edit]
  1. ^ "Wayback Machine" (PDF). web.mit.edu. Archived from the original (PDF) on 2013-11-01. Retrieved 2025-06-30.
  2. ^ Maurice Herlihy and J. Eliot B. Moss. Transactional memory: architectural support for lock-free data structures. Proceedings of the 20th annual international symposium on Computer architecture (ISCA '93). Volume 21, Issue 2, May 1993.
  3. ^ Nir Shavit and Dan Touitou. Software transactional memory. Distributed Computing. Volume 10, Number 2. February 1997.
  4. ^ ""software transactional memory" - Google Scholar". Retrieved 10 November 2013.
  5. ^ Peyton Jones, Simon. "Programming in the Age of Concurrency: Software Transactional Memory". Microsoft Developers Network: Channel 9. Retrieved 2007-06-09.
  6. ^ Jump up to: a b c Harris, T.; Marlow, S.; Peyton Jones, S.; Herlihy, M. (2005). "Composable memory transactions" (PDF). Proceedings of the tenth ACM SIGPLAN symposium on Principles and practice of parallel programming - PPoPP '05. p. 48. doi:10.1145/1065944.1065952. ISBN 1595930809. S2CID 53245159.
  7. ^ Concurrency_control#Methods
  8. ^ "Glasgow Haskell Compiler (GHC) Commentary: Software Transactional Memory (STM)". Haskell.org: GitLab.
  9. ^ "Software Transactional Memory in C++: Pure Functional Approach (tutorial)". GitHub.
  10. ^ "Refs and Transactions". Clojure.org.
  11. ^ "Poor man's STM in Node.js". Clojure.org.
  12. ^ "talhof8/kashmir". GitHub.
  13. ^ "Rust Package Registry". Crates.io.
  14. ^ "Introduction to Software Transactional Memory ZIO". Zio.dev.
  15. ^ "Kcas — STM based on lock-free MCAS". GitHub.
  16. ^ "Transactional memory (STM)". arrow-kt.io.