Software transactional memory
Encyclopedia
In computer science
, software transactional memory (STM) is a concurrency control
mechanism analogous to database transaction
s for controlling access to shared memory
in concurrent computing
. It is an alternative to lock-based synchronization
. A transaction in this context is a piece of code that executes a series of reads and writes to shared memory. These reads and writes logically occur at a single instant in time; intermediate states are not visible to other (successful) transactions. The idea of providing hardware support for transactions originated in a 1986 paper and patent by Tom Knight. The idea was popularized by Maurice Herlihy
and J. Eliot B. Moss
. In 1995 Nir Shavit
and Dan Touitou extended this idea to software-only transactional memory (STM). STM has recently been the focus of intense research and support for practical implementations is growing.
techniques used in most modern multithreaded applications, STM is very optimistic
: a thread
completes modifications to shared memory without regard for what other threads might be doing, recording every read and write that it is performing in a log. Instead of placing the onus on the writer to make sure it does not adversely affect other operations in progress, it is placed on the reader, who after completing an entire transaction verifies that other threads have not concurrently made changes to memory that it accessed in the past. This final operation, in which the changes of a transaction are validated and, if validation is successful, made permanent, is called a commit. A transaction may also abort at any time, causing all of its prior changes to be rolled back or undone. If a transaction cannot be committed due to conflicting changes, it is typically aborted and re-executed from the beginning until it succeeds.
The benefit of this optimistic approach is increased concurrency: no thread needs to wait for access to a resource, and different threads can safely and simultaneously modify disjoint parts of a data structure that would normally be protected under the same lock.
However, in practice STM systems also suffer a performance hit relative to fine-grained lock-based systems on small numbers of processors (1 to 4 depending on the application). This is due primarily to the overhead associated with maintaining the log and the time spent committing transactions. Even in this case performance is typically no worse than twice as slow. Advocates of STM believe this penalty is justified by the conceptual benefits of STM.
Theoretically, the worst case
space and time complexity of n concurrent transactions is O
(n). Actual needs depend on implementation details (one can make transactions fail early enough to avoid overhead), but there will also be cases, albeit rare, where lock-based algorithms have better time complexity than software transactional memory.
In contrast, the concept of a memory transaction is much simpler, because each transaction can be viewed in isolation as a single-threaded computation. Deadlock and livelock are either prevented entirely or handled by an external transaction manager; the programmer need hardly worry about it. Priority inversion can still be an issue, but high-priority transactions can abort conflicting lower priority transactions that have not already committed.
On the other hand, the need to abort failed transactions also places limitations on the behavior of transactions: they cannot perform any operation that cannot be undone, including most I/O. Such limitations are typically overcome in practice by creating buffers that queue up the irreversible operations and perform them at a later time outside of any transaction. In Haskell
, this limitation is enforced at compile time by the type system.
, and Maurice Herlihy
described an STM system built on Concurrent Haskell
that enables arbitrary atomic operations to be composed into larger atomic operations, a useful concept impossible with lock-based programming. To quote the authors:
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's unclear to the caller, who is unaware of the implementation details of the component methods, when they 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. This facility, comparable to features such as the 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
.
// 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. 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" 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", 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.
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 and patents utilizing "commit order" have already been published.
(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:
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").
Provided x=y initially, neither transaction above alters this invariant, but it's possible 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.
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, software transactional memory (STM) is a concurrency control
Concurrency control
In information technology and computer science, especially in the fields of computer programming , operating systems , multiprocessors, and databases, concurrency control ensures that correct results for concurrent operations are generated, while getting those results as quickly as possible.Computer...
mechanism analogous to database transaction
Database transaction
A transaction comprises a unit of work performed within a database management system against a database, and treated in a coherent and reliable way independent of other transactions...
s for controlling access to shared memory
Shared memory
In computing, shared memory is memory that may be simultaneously accessed by multiple programs with an intent to provide communication among them or avoid redundant copies. Depending on context, programs may run on a single processor or on multiple separate processors...
in concurrent computing
Concurrent computing
Concurrent computing is a form of computing in which programs are designed as collections of interacting computational processes that may be executed in parallel...
. It is an alternative to lock-based synchronization
Lock (computer science)
In computer science, a lock is a synchronization mechanism for enforcing limits on access to a resource in an environment where there are many threads of execution. Locks are one way of enforcing concurrency control policies.-Types:...
. A transaction in this context is a piece of code that executes a series of reads and writes to shared memory. These reads and writes logically occur at a single instant in time; intermediate states are not visible to other (successful) transactions. The idea of providing hardware support for transactions originated in a 1986 paper and patent by Tom Knight. The idea was popularized by Maurice Herlihy
Maurice Herlihy
Maurice Herlihy is a computer scientist active in the field of multiprocessor synchronization. Herlihy has contributed to the design of concurrent algorithms, and in particular to the exposition and quantification of the properties and uses of hardware synchronization operations...
and J. Eliot B. Moss
J. Eliot B. Moss
J. Eliot B. Moss is a computer scientist active in the fields of garbage collection and multiprocessor synchronization. He is currently a professor of computer science at University of Massachusetts Amherst, and is on the executive committee of SIGPLAN, the Special Interest Group for programming...
. In 1995 Nir Shavit
Nir Shavit
Nir Shavit is a Professor in the Computer Science Department at Tel Aviv University.Nir Shavit received B.Sc. and M.Sc. degrees in Computer Science from the Technion - Israel Institute of Technology in 1984 and 1986, and a Ph.D. in Computer Science from the Hebrew University of Jerusalem in 1990...
and Dan Touitou extended this idea to software-only transactional memory (STM). STM has recently been the focus of intense research and support for practical implementations is growing.
Performance
Unlike the lockingLock (computer science)
In computer science, a lock is a synchronization mechanism for enforcing limits on access to a resource in an environment where there are many threads of execution. Locks are one way of enforcing concurrency control policies.-Types:...
techniques used in most modern multithreaded applications, STM is very optimistic
Optimistic concurrency control
In the field of relational database management systems, optimistic concurrency control is a concurrency control method that assumes that multiple transactions can complete without affecting each other, and that therefore transactions can proceed without locking the data resources that they affect...
: a thread
Thread (computer science)
In computer science, a thread of execution is the smallest unit of processing that can be scheduled by an operating system. The implementation of threads and processes differs from one operating system to another, but in most cases, a thread is contained inside a process...
completes modifications to shared memory without regard for what other threads might be doing, recording every read and write that it is performing in a log. Instead of placing the onus on the writer to make sure it does not adversely affect other operations in progress, it is placed on the reader, who after completing an entire transaction verifies that other threads have not concurrently made changes to memory that it accessed in the past. This final operation, in which the changes of a transaction are validated and, if validation is successful, made permanent, is called a commit. A transaction may also abort at any time, causing all of its prior changes to be rolled back or undone. If a transaction cannot be committed due to conflicting changes, it is typically aborted and re-executed from the beginning until it succeeds.
The benefit of this optimistic approach is increased concurrency: no thread needs to wait for access to a resource, and different threads can safely and simultaneously modify disjoint parts of a data structure that would normally be protected under the same lock.
However, in practice STM systems also suffer a performance hit relative to fine-grained lock-based systems on small numbers of processors (1 to 4 depending on the application). This is due primarily to the overhead associated with maintaining the log and the time spent committing transactions. Even in this case performance is typically no worse than twice as slow. Advocates of STM believe this penalty is justified by the conceptual benefits of STM.
Theoretically, the worst case
Worst Case
Worst Case is the 3rd book in the Michael Bennett series from James Patterson and Michael Ledwidge.-Plot summary:NYPD Detective Mike Bennett and his new partner FBI Special Agent Emily Parker are on the trail of Francis Mooney, a Manhattan trusts and estates lawyer with terminal lung cancer...
space and time complexity of n concurrent transactions is O
Big O notation
In mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...
(n). Actual needs depend on implementation details (one can make transactions fail early enough to avoid overhead), but there will also be cases, albeit rare, where lock-based algorithms have better time complexity than software transactional memory.
Conceptual advantages and disadvantages
In addition to their performance benefits, STM greatly simplifies conceptual understanding of multithreaded programs and helps make programs more maintainable by working in harmony with existing high-level abstractions such as objects and modules. Lock-based programming has a number of well-known problems that frequently arise in practice:- It requires thinking about overlapping operations and partial operations in distantly separated and seemingly unrelated sections of code, a task which is very difficult and error-prone.
- It requires programmers to adopt a locking policy to prevent deadlockDeadlockA deadlock is a situation where in two or more competing actions are each waiting for the other to finish, and thus neither ever does. It is often seen in a paradox like the "chicken or the egg"...
, livelock, and other failures to make progress. Such policies are often informally enforced and fallible, and when these issues arise they are insidiously difficult to reproduce and debug. - It can lead to priority inversionPriority inversionIn computer science, priority inversion is a problematic scenario in scheduling when a higher priority task is indirectly preempted by a lower priority task effectively "inverting" the relative priorities of the two tasks....
, a phenomenon where a high-priority thread is forced to wait for a low-priority thread holding exclusive access to a resource that it needs.
In contrast, the concept of a memory transaction is much simpler, because each transaction can be viewed in isolation as a single-threaded computation. Deadlock and livelock are either prevented entirely or handled by an external transaction manager; the programmer need hardly worry about it. Priority inversion can still be an issue, but high-priority transactions can abort conflicting lower priority transactions that have not already committed.
On the other hand, the need to abort failed transactions also places limitations on the behavior of transactions: they cannot perform any operation that cannot be undone, including most I/O. Such limitations are typically overcome in practice by creating buffers that queue up the irreversible operations and perform them at a later time outside of any transaction. In Haskell
Haskell (programming language)
Haskell is a standardized, general-purpose purely functional programming language, with non-strict semantics and strong static typing. It is named after logician Haskell Curry. In Haskell, "a function is a first-class citizen" of the programming language. As a functional programming language, the...
, this limitation is enforced at compile time by the type system.
Composable operations
In 2005, Tim Harris, Simon Marlow, Simon Peyton JonesSimon Peyton Jones
Simon Peyton Jones is a British computer scientist who researches the implementation and applications of functional programming languages, particularly lazy functional languages...
, and Maurice Herlihy
Maurice Herlihy
Maurice Herlihy is a computer scientist active in the field of multiprocessor synchronization. Herlihy has contributed to the design of concurrent algorithms, and in particular to the exposition and quantification of the properties and uses of hardware synchronization operations...
described an STM system built on Concurrent Haskell
Concurrent Haskell
Concurrent Haskell extends Haskell 98 with explicit concurrency. The two main concepts underpinning Concurrent Haskell are:* A primitive type MVar α implementing a bounded/single-place asynchronous channel, which is either empty or holds a value of type α....
that enables arbitrary atomic operations to be composed into larger atomic operations, a useful concept impossible with lock-based programming. To quote the authors:
Perhaps the most fundamental objection [...] is that lock-based programs do not compose: correct fragments may fail when combined. For example, consider a hash table with thread-safe insert and delete operations. Now suppose that we want to delete one item A from table t1, and insert it into table t2; but the intermediate state (in which neither table contains the item) must not be visible to other threads. Unless the implementor of the hash table anticipates this need, there is simply no way to satisfy this requirement. [...] In short, operations that are individually correct (insert, delete) cannot be composed into larger correct operations.
—Tim Harris et al., "Composable Memory Transactions", Section 2: Background, pg.2
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's unclear to the caller, who is unaware of the implementation details of the component methods, when they 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. This facility, comparable to features such as the 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
Glasgow Haskell Compiler
The Glorious Glasgow Haskell Compilation System, more commonly known as the Glasgow Haskell Compiler or GHC, is an open source native code compiler for the functional programming language Haskell. The lead developers are Simon Peyton Jones and Simon Marlow...
.
Proposed language support
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. 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
Loose coupling
In computing and systems design a loosely coupled system is one where each of its components has, or makes use of, little or no knowledge of the definitions of other separate components. The notion was introduced into organizational studies by Karl Weick...
between producers and consumers enhances modularity compared to explicit signaling between threads. "Composable Memory Transactions" 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", 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
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
Transactional memory
Transactional memory attempts to simplify parallel programming by allowing a group of load and store instructions to execute in an atomic way. It is a concurrency control mechanism analogous to database transactions for controlling access to shared memory in concurrent computing.-Hardware vs...
, and especially in STM, is Commitment ordering
Commitment ordering
In concurrency control of databases, transaction processing , and related applications, Commitment ordering is a class of interoperable Serializability techniques, both centralized and distributed. It allows optimistic implementations...
(also called Commit ordering; CO). It is utilized for achieving serializability
Serializability
In concurrency control of databases, transaction processing , and various transactional applications , both centralized and distributed, a transaction schedule is serializable, has the serializability property, if its outcome In concurrency control of databases, transaction processing (transaction...
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 and patents utilizing "commit order" have already been published.
(Zhang et al. 2006) is a US patent
Patent
A patent is a form of intellectual property. It consists of a set of exclusive rights granted by a sovereign state to an inventor or their assignee for a limited period of time in exchange for the public disclosure of an invention....
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").
Implementation issues
One problem with implementing software transactional memory with optimistic reading is that it's 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's 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":
|
Provided x=y initially, neither transaction above alters this invariant, but it's possible 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.
Implementations
A number of STM implementations (on varying scales of quality and stability) have been released, many under liberal licenses. These include:C/C++
- TBoost.STM (formerly DracoSTM) A joint effort from CU-Boulder and the Boost Libraries Group to build an industrial strength C++ STM library primarily authored by Justin E. Gottschlich and Jeremy G. Siek.
- TinySTM a time-based STM and Tanger to integrate STMs with C and C++ via LLVM.
- The Lightweight Transaction Library (LibLTX), a C implementation by Robert Ennals focusing on efficiency and based on his papers "Software Transactional Memory Should Not Be Obstruction-Free" and "Cache Sensitive Software Transactional Memory".
- LibCMT, an open-source implementation in C by Duilio Protti based on "Composable Memory Transactions". The implementation also includes a C# binding.
- TARIFA is a prototype that brings the "atomic" keyword to C/C++ by instrumenting the assembler output of the compiler.
- Intel STM Compiler Prototype Edition implements STM for C/C++ directly in a compiler (the Intel Compiler) for Linux or Windows producing 32 or 64 bit code for Intel or AMD processors. Implements atomic keyword as well as providing ways to decorate (declspec) function definitions to control/authorize use in atomic sections. A substantial implementation in a compiler with the stated purpose to enable large scale experimentation in any size C/C++ program.
- stmmap An implementation of STM in C, based on shared memory mapping. It is for sharing memory between threads and/or processes (not just between threads within a process) with transactional semantics. The multi-threaded version of its memory allocator is in C++.
- CTL An implementation of STM in C, based on TL2 but with many extensions and optimizations.
- The TL2 lock-based STM from the Scalable Synchronization research group at Sun Microsystems Laboratories, as featured in the DISC 2006 article "Transactional Locking II".
- Several implementations by Tim Harris & Keir Fraser, based on ideas from his papers "Language Support for Lightweight Transactions", "Practical Lock Freedom", and an upcoming unpublished work.
- RSTM The University of RochesterUniversity of RochesterThe University of Rochester is a private, nonsectarian, research university in Rochester, New York, United States. The university grants undergraduate and graduate degrees, including doctoral and professional degrees. The university has six schools and various interdisciplinary programs.The...
STM written by a team of researchers led by Michael L. ScottMichael L. ScottMichael Lee Scott is a professor of computer science at the University of Rochester in Rochester, New York.-Education and teaching:...
.
C#
- SXM, an implementation of transactions for C# by Microsoft ResearchMicrosoft ResearchMicrosoft Research is the research division of Microsoft created in 1991 for developing various computer science ideas and integrating them into Microsoft products. It currently employs Turing Award winners C.A.R. Hoare, Butler Lampson, and Charles P...
. Documentation, [ftp://ftp.research.microsoft.com/downloads/fbe1cf9a-c6ac-4bbb-b5e9-d1fda49ecad9/SXM1.1.zip Download page]. - LibCMT, an open-source implementation in C by Duilio Protti based on "Composable Memory Transactions". The implementation also includes a C# binding.
- NSTM, .NET Software Transactional Memory written entirely in C# offering truly nested transactions and even integrating with System.Transactions.
- MikroKosmos A Verification-Oriented Model Implementation of an STM in C#.
- ObjectFabric cf. Java implementations.
Common Lisp
- CL-STM is a multi-platform STM implementation for Common Lisp.
Haskell
- The STM library, as featured in "Composable Memory Transactions", is part of the Haskell PlatformHaskell PlatformThe Haskell Platform is a collection of software-packages, tools and libraries, which is to create a common platform for using and developing applications in Haskell. With the Haskell Platform, Haskell follows the same principle as Python: "Batteries included"...
.
Java
- SCAT research group's implementation of AtomJava.
- JVSTM implements the concept of Versioned Boxes proposed by João Cachopo and António Rito Silva, members of the Software Engineering Group - INESC-ID
- Deuce A runtime environment for Java Software Transactional Memory using byte code manipulation.
- Multiverse Is a Java 1.6+ based Software Transactional Memory (STM) implementation that uses Multi Version Concurrency Control (MVCC)Multiversion concurrency controlMultiversion concurrency control , in the database field of computer science, is a concurrency control method commonly used by database management systems to provide concurrent access to the database and in programming languages to implement transactional memory.For instance, a database will...
as concurrency control mechanism. - DSTM2 Sun Lab's Dynamic Software Transactional Memory Library
- ObjectFabric is an open source implementation for Java and .NET. It can be turned into a Distributed STM through an extension mechanism. Other extensions allow logging, change notification, and persistence.
OCaml
- coThreads, a concurrent programming library of OCaml, offers STM (originally STMLib) as a module. Just like any other components in this library, the STM module can be used uniformly with VM-level threads, system threads and processes.
Perl
- STM for Perl 6Perl 6Perl 6 is a major revision to the Perl programming language. It is still in development, as a specification from which several interpreter and compiler implementations are being written. It is introducing elements of many modern and historical languages. Perl 6 is intended to have many...
has been implemented in PugsPugsPugs is a compiler and interpreter for the Perl 6 programming language, started on February 1, 2005 by Audrey Tang.Pugs development is now placed on hiatus, with most Perl 6 implementation efforts now taking place on Rakudo; however, its source repository is still used for storing the official Perl...
via the Glasgow Haskell CompilerGlasgow Haskell CompilerThe Glorious Glasgow Haskell Compilation System, more commonly known as the Glasgow Haskell Compiler or GHC, is an open source native code compiler for the functional programming language Haskell. The lead developers are Simon Peyton Jones and Simon Marlow...
's STM library.
Python
- Durus is a simple, yet mature, complete and fast, STM implementation for Python, allowing both STM inside a single process and STM in a server/multiple clients architecture. In addition to its built-in storage format, there are others available such as one based on Berkeley DBBerkeley DBBerkeley DB is a computer software library that provides a high-performance embedded database for key/value data. Berkeley DB is a programmatic software library written in C with API bindings for C++, PHP, Java, Perl, Python, Ruby, Tcl, Smalltalk, and most other programming languages...
available here. - Fork of CPython with atomic locks - Armin Rigo explains his patch to CPython in an email to the pypy-dev list.
Scala
- scala-stm An implementation of a software transactional memory framework in Scala
- ScalaSTM A draft proposal for an STM to be included in the Scala standard library
- Akka STM the Akka framework contains support for STM in both Scala & Java
Smalltalk
- GemStone/S http://www.gemstone.com/products/smalltalk/ A Transactional Memory Object Server for Smalltalk.
other languages
External links
- Cambridge lock-free group
- Software transactional memory Description; Derrick Coetzee
- Transactional Memory Bibliography
- Critical discussion of STM in conjunction with imperative languages
- JVSTM – Java Versioned Software Transactional Memory
- Deuce - Java Software Transactional Memory
- Blog about STM and the TLII algorithm
- Flexviews - materialized views act like software transactional memory for database relations