Software Transactional Memory (STM)

Software transactional memory groups shared-memory changes into an atomic block that either commits in full or aborts and retries [ST95].

The programmer wraps operations in atomic { ... }; the runtime handles conflict detection and rollback. Covered in ECE459 L13.

Why use STM?

The programming model is far simpler than locks. Stick shared ops in an atomic block and the runtime figures out conflicts. No lock ordering, no deadlock.

Rust (rust-stm library):

let x = atomically(|trans| {
    var.write(trans, 42)?;
    var.read(trans)
});

Bank transfer example

struct Account { balance: TVar<f32> }
 
fn transfer_funds(sender: &mut Account, receiver: &mut Account, amount: f32) {
    atomically(|tx| {
        let sb = sender.balance.read(tx)?;
        let rb = receiver.balance.read(tx)?;
        sender.balance.write(tx, sb - amount)?;
        receiver.balance.write(tx, rb + amount)?;
        Ok(0)
    });
}

Locking alternatives: one big global lock (slow, serial) or a lock per account (deadlock-prone, high overhead). STM avoids both.

Drawbacks

• I/O: you can’t roll back a screen write or a network send
• Nested transactions: committing inner while aborting outer makes a mess. Rust’s library panics if you nest
• Transaction size: hardware-only implementations cap transaction size, which is bad for programmability

Implementation

Typically optimistic: buffer the changes, roll back if needed. Hardware-assisted versions use cache hardware to store uncommitted changes. Combining hardware plus software avoids size limits.

Data races still bite

Atomic blocks roll back on conflict, but they don’t protect against intermediate states becoming visible to non-transactional readers.

// initially x == y. This can loop forever in C/C++ STM.
atomically(|t| {
    if x.read(t)? != y.read(t)? { loop { /* cursed */ } }
    Ok(0)
});

Where STM actually lives

Production STM exists where the type system enforces transaction purity:

• Haskell (STM monad) and Clojure (refs)
• C/C++/Java attempts mostly died: runtime can’t block I/O or non-transactional access

Real blockers are performance (bookkeeping loses to fine-grained locks under contention) and retry livelock, not the idea itself.

Related

• Transactional Memory
• Lock-Free Programming
• Value Speculation