1 Overview and motivation
1.1 Need for concurrency control
In parallel computing, multiple threads access shared memory concurrently. Without coordination, races can lead to inconsistent states (e.g., lost updates, corrupted data structures). Concurrency control mechanisms ensure that threads operate safely, preserving program correctness while exploiting parallelism.
1.2 Limitations of lock‑based synchronization
Traditional lock‑based synchronization (mutexes, semaphores) suffers from several drawbacks: deadlock, lock convoying, priority inversion, and the difficulty of composing locked operations. Fine‑grained locking can improve concurrency but increases programming complexity. Coarse‑grained locks degrade performance. Furthermore, lock‑based code is prone to human error, such as forgetting to release a lock or acquiring locks in an inconsistent order.
1.3 Core idea: atomicity and isolation
Software transactional memory (STM) borrows the concepts of atomicity and isolation from database transactions. A sequence of memory operations is grouped into a transaction that either commits (all effects become visible atomically) or aborts (no effect is visible). If a transaction aborts, it can be retried automatically. This abstraction frees the programmer from explicit lock management, reducing the risk of concurrency bugs.
2 Fundamental concepts
2.1 Transactions
2.1.1 Atomic operations
A transaction appears to execute as a single, indivisible step. Intermediate states are not visible to other threads. If two transactions conflict (e.g., both try to write the same memory location), the system may abort one and retry it.
2.1.2 Isolation and consistency
Isolation ensures that concurrent transactions do not interfere with each other; each sees a consistent snapshot of memory. Consistency guarantees that the system moves from one valid state to another, as defined by the program’s invariants.
2.2 Conflict detection
2.2.1 Optimistic vs. pessimistic approaches
Optimistic conflict detection assumes few conflicts: transactions proceed without locking and validate at commit time. Pessimistic detection locks accessed locations immediately, preventing conflicts proactively. Most STM implementations use optimistic read and pessimistic write (or variants) to balance overhead and throughput.
2.2.2 Read‑write and write‑write conflicts
A read‑write conflict occurs when one transaction reads a location that another writes, while a write‑write conflict occurs when two transactions write the same location. STM must detect both to ensure correctness.
2.3 Transactional memory systems
2.3.1 Software vs. hardware transactional memory
STM is implemented entirely in software (runtime libraries or language runtime), offering flexibility but incurring bookkeeping overhead. Hardware transactional memory (HTM) uses processor support (e.g., Intel TSX) for lower overhead and better performance, but typically has limitations such as limited transaction size and limited conflict resolution.
2.3.2 Hybrid approaches
Hybrid transactional memory combines STM and HTM: the system tries to use HTM first and falls back to STM if the transaction exceeds hardware capacity or conflicts too often. This aims to get the performance benefits of HTM where possible and the flexibility of STM otherwise.
3 Implementation techniques
3.1 Transactional data structures
3.1.1 Word‑based STM
Word‑based STM tracks memory at the granularity of individual words or small blocks. Each word has an associated metadata entry (e.g., version number or lock). It allows fine‑grained conflict detection but may require careful management of memory layout.
3.1.2 Object‑based STM
Object‑based STM works at the level of language objects (e.g., Java objects or Clojure refs). Each object has a version or lock. This approach integrates naturally with garbage‑collected languages and simplifies aliasing detection.
3.2 Version management
3.2.1 Timestamp‑based versioning
Each memory location holds a timestamp indicating the last committing transaction’s logical time. A transaction reads the timestamps to obtain a consistent snapshot; if timestamps change during the transaction, it aborts. This method is typical in optimistic STMs.
3.2.2 Lock‑based versioning
Locks are associated with memory locations. A transaction acquires locks on its write set at commit time. If it cannot acquire all locks, it aborts. Lock‑based versioning is common in pessimistic or encounter‑time locking STMs.
3.3 Contention management
3.3.1 Greedy and polite policies
A greedy contention manager aborts the other transaction immediately upon conflict. A polite manager may wait or yield before aborting, reducing wasted work. The choice affects throughput and fairness.
3.3.2 Backoff and abort strategies
Exponential backoff (increasing wait time after each abort) helps avoid repeated conflicts. Some STMs use randomized abort selection to avoid livelock. Others employ priority‑based schemes.
4 Semantics and correctness
4.1 Serializability
The standard correctness criterion for transactions is serializability: the result of concurrent transactions must be equivalent to some serial execution (one after the other). STM implementations guarantee serializability to ensure predictable program behavior.
4.2 Opacity
4.2.1 Preventing speculative reads
Opacity strengthens serializability by ensuring that even aborted transactions never observe an inconsistent state. This prevents “zombie” threads from causing errors (e.g., infinite loops or bad side effects). Most STMs enforce opacity by validating reads during the transaction’s execution.
4.3 Strong vs. weak atomicity
Strong atomicity treats all memory accesses (transactional and non‑transactional) as part of the same consistency model; non‑transactional reads/writes can cause races. Weak atomicity only guarantees isolation among transactional accesses, leaving non‑transactional code unprotected. Most practical STMs adopt strong atomicity to prevent subtle bugs.
4.4 Progress guarantees
4.4.1 Obstruction freedom, lock freedom, wait freedom
These theoretical properties define how transactions guarantee progress. Obstruction freedom: a transaction eventually commits if it runs alone (no other transactions contending). Lock freedom: the system as a whole makes progress, even if individual transactions starve. Wait freedom: each transaction makes progress within a finite number of steps. Most STMs are obstruction‑free or lock‑free for the common case, but full wait‑freedom is often impractical.
5 Language and library support
5.1 Haskell STM
5.1.1 TVar, TMVar, and retry/orElse
Haskell’s STM monad provides transactional variables (TVar) and transactional queues (TMVar). The retry combinator blocks until a TVar changes; orElse allows composing alternatives. This expressive interface makes it easy to build concurrent data structures without locks.
5.2 Clojure’s ref‑based STM
Clojure implements STM using Refs (reference types). Transactions are explicit with dosync blocks. The system uses software transactional memory with a multiversion concurrency control (MVCC)‑like approach: reads see a snapshot, and writes are validated at commit. It also supports alter and commute for different consistency guarantees.
5.3 C++ transactional memory proposals
5.3.1 Transactional Language Constructs (TLS)
The C++ standards committee has considered adding synchronized blocks and atomic blocks. GCC and some compilers provided experimental support. However, the proposal was not adopted into C++17; instead, transactional memory remains a library‑level feature (e.g., Intel TBB, Boost).
5.4 Java (Deuce STM, Multiverse)
Java has several STM libraries. Deuce STM uses bytecode instrumentation to implement transactions. Multiverse provides transaction support with a focus on performance and integration with existing code. These libraries typically rely on optimistic concurrency and versioning.
6 Performance considerations
6.1 Overhead of transaction bookkeeping
STM adds runtime overhead for version checks, logging, and validation. Each read and write may incur costs (e.g., reading metadata, updating logs). This overhead can be 2-10× slower than lock‑based code for uncontended cases.
6.2 Scalability on multicore systems
STM can scale well under low contention because transactions run in parallel without locking. Under high contention, conflicts cause aborts and retries, which can degrade performance. Tuning contention managers and transaction sizes is crucial.
6.3 Interaction with garbage collection
Many STM implementation allocate transaction logs and metadata dynamically. GC pauses can interfere with transaction execution (e.g., causing long delays that increase conflict windows). Generational and concurrent GCs help, but careful design is needed.
6.4 Benchmarks and typical bottlenecks
Common benchmarks (e.g., STAMP, Lee’s routing, Red‑Black tree) measure throughput and abort rates. Bottlenecks often include validation overhead (especially for large read sets) and contention on commit‑time lock acquisition. Optimizations like read‑set filtering and commit‑time parallel validation are active research areas.
7 Advanced topics
7.1 Nested transactions
7.1.1 Flat vs. open nesting
Flat nesting treats inner transactions as part of the outer transaction; if the inner aborts, the outer aborts too. Open nesting allows inner transactions to commit independently, even if the outer aborts, enabling finer‑grained isolation but requiring careful compensation.
7.1.2 Closed nesting
Closed nesting treats inner transactions as subtransactions that can abort without aborting the outer transaction; the outer sees the effects only if the inner commits. This supports modular reasoning and composition.
7.2 I/O within transactions
Performing irreversible I/O (e.g., writing to a file or network) inside a transaction is problematic because aborted transactions cannot undo the side effects. Solutions include buffering I/O until commit, using compensation actions, or restricting I/O outside transactions.
7.3 Transactional memory and persistent memory
Emerging persistent memory (e.g., Intel Optane DC) requires transactions that survive crashes. Persistent transactional memory (PTM) combines STM with logging and checkpointing to ensure atomic durability, making it suitable for fault‑tolerant applications.
7.4 Compiler optimization and static analysis
Compilers can optimize transactional code by eliding redundant checks, merging transactions, and using static analysis to reduce bookkeeping overhead. For example, a compiler can identify read‑only transactions and skip write validation.
8 Research directions and open challenges
8.1 Integration with hardware transactional memory
Hybrid systems that combine STM and HTM remain an active area. Challenges include handling aborts due to HTM capacity limits, ensuring forward progress, and coordinating between software and hardware conflict detectors.
8.2 Energy‑aware transactional execution
Transactional execution can be designed to minimize energy consumption by reducing unnecessary retries, using low‑power conflict detection, or dynamically scaling voltage/frequency based on contention levels.
8.3 STM for distributed and heterogeneous systems
Extending STM to distributed memory (e.g., with replicated data and distributed commit protocols) or heterogeneous systems (CPU+GPU) introduces new consistency models and communication overhead. Research explores trade‑offs between performance and transparency.
9 See also
- Hardware transactional memory
- Concurrent programming
- Lock (computer science)
- Non‑blocking algorithm
- ACID (database transactions)
10 References
(Note: In a real encyclopedia, references would be listed here. For brevity, we omit them in this expansion.)
11 Further reading
(Note: In a real encyclopedia, further reading suggestions would be provided. For brevity, we omit them in this expansion.)