Software　Transactional Memory(STM，软件事务内存)是一种与数据库的事务类似的并发控制结构，用于控制并发 计算中对共享内存的访问，是基于锁的同步的一种替代机制。STM在软件层面实现，而不是基于硬件部件。当一段代码需要读或者写共享的 内存区域时，就产生了一次事务。 1986年，Tom Knight 提出了这一理论，Nir Shavit 和 Dan Touitou 在 1995 年发表的论文 Software Transactional Memory 使得STM开始流行起来，越来越多地收到人们的关注。

Lock-based programming sucks

Lock-based programming 存在很多众所周知的问题：

  • Taking too few locks
  • Taking too many locks
  • Taking the wrong locks
  • Taking locks in the wrong order
  • Error recovery
  • Lost wake-ups and erroneous retires.

事务性的定义

我们知道，在数据中，事务性必须满足ACID(Atomicity, Consistency, Isolation, Durability)， 而软件事务内存又是怎样体现这些事务性的要求的呢？

  • 原子性(atomicity)：在其他的事务看来，当前事务的作用要不都发生，要不都不发生。
  • 隔离性(ioslation)：多个事务可以同时运行，但多个事务同时运行的结果应该与串行这些事务的结果相一致。
  • 一致性(consistency)：事务的一系列校验中任何一个失败，那么所有的修改都不发生。
  • 持久性(durability)

STM

STM借鉴了数据库中的Optimistic execution的思想，一个进程在读写共享内存时不需要考虑其他进程的行为和状态，并记录日志，若 成功，提交结果，若失败，重置日志并重试。Language Support for Lightweight Transactions 和 Proposed the Idea of Using th Classical Conditional Critical Region(CCR) to Represent Transactions 两篇论文提出 了原子块(atomic block)的方式来描述事务，例如：

// 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.

CCR(Conditional Critical Region)也允许 guard condtion:

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

当条件不满足时，还可以一直重试事务，知道其他的事物产生一次commit并影响到当前事务的条件：

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. 同时，在事务的提交阶段，Commitment Ordering也非常重要，用来依次提交事务。

STM在实现上有两种不同的思路：encounter-time locking 和 commit-time locking(Transactional Locking II)， 下面将详细分析第二种方法。

在Transactional locking II scheme中，系统中存在一个全局版本锁（global version lock，实际上，这个锁是用来记录共享 变量的状态的，每次共享变量更新，version value都增大），一个并发任务的完成分为两个阶段：执行阶段和提交阶段。 每一个事务开始在开始执行时就记录这个当前的版本锁的值作为read-version，然后在事务执行过程中，每一次读/写共享变量（这些 读/写操作并没有真正改变物理内存中共享变量的值，而是记录了日志），都检查当前global version lock的值，如果比 read-version大，事务异常终止（说明在这个事务执行过程中，其他线程修改了共享内存，出现了不一致）。在提交阶段，将会被写入的 位置都被加锁，并再次检查此次事务读/写涉及到的内存位置的version number，如果不一致，事务异常终止。接着，日志中记录的 此次事务产生的新值被写入内存，同时更新global version lock的值（增大）。

STM in Haskell

Haskell 中使用TVar来表示STM中的共享变量，对于一个事务，在一开始执行时就产生一个空的日志(thread-local transactional log, initially empty)，每一次对共享变量的写操作(writeTVar)都将新的值写进日志，而不是直接写 共享变量本身。每一次对共享变量的读操作(readTVar)，先检查日志，看是否有新值，如果有，直接使用，如果没有，就读取 TVar本身，并且将TVar的值和读到的值都写入到日志中。完成事务的所有动作后就进入事务的提交阶段，如果对日志的校验 成功，则提交日志，将日志中所有的写操作都作用到相应的TVar上。提交阶段的校验会检查日志中记录的所有TVar的值与 TVar当前的值是否一致，目的是为了确保在当前事务执行期间没有其他事务修改共享变量。

Haskell实现的STM另一大特点是Composable Memeory Transactions，可以不用修改本来的代码实现方式，而通过 Combinator来将多个atomic代码块组合成一个大的atomic代码块，整体上作为一个原子操作。

Lock-based vs. STM

由STM的实现机制可以看出，在锁机制中，由写者(writer)来保证在修改共享内存时不对其他的线程产生不利的影响，而在STM中， 这一责任落在了读者(reader)上面。完成一次事务后，reader会验证没有其他线程正在对共享内存进行并发修改，如果验证成功， 将会产生一次提交(commit)，将结果写入共享内存，made permanent。否则，这次事务便会终止(abort)，撤销在这期间 的所有更改，然后这次事务会再次从头开始执行(retry, re-execute)直到取得成功。

STM的好处在于提高了程序的并发度，每个线程都不用等待对一个资源的访问，不同的线程可以同时安全地修改共享内存中不相交的 部分(类似于并发地修改数据库中的不同记录)。然而，在实践中，在小数量(1-4，取决于应用程序)的处理器上运行时， 与调度良好的锁机制相比，STM遇到了性能问题，这种要是由于维护日志导致和花费在提交的时间上导致的。 但在最坏情形下，根据Simon Peyton-Jones的演讲Programming in the Age of Concurrency: Software Transactional Memory， 性能损失也不会超过两倍。理论上，n 个并发事务(transactions)的所需要的时间和空间都为O(n)。

使用STM来编写并发程序可以极大地减小程序的逻辑复杂度，从而减少出现bug的可能性，同时，与存在逻辑缺陷的的 locked-based程序带来的风险和性能损失相比，STM在性能上极小的overhead显得微不足道。此外，多个原子性 的事务可以组合成一个更大的原子事务，而在lock-based programming中，这是不可能的。

但是，需要终止失败的事务也限制了事务的行为，这些事务不能有不可撤销的行为，例如IO。在实践中，这些问题可以通过创建buffer， 用于queue up程序中的irreversible operations来解决。在Haskell中，pure和type system用来保证事务满足这一限制( permits only side effects on TVars)。

STM的实现与应用

STM在多种编程语言中都有实现。 Haskell中，有基于论文Composable Memory Transactions实现的Control.Concurrent.STM以及对应的Monad：Control.Monad.STM。 University of Cambridge 的研究人员基于论文 Language Support for Lightweight Transactions 以及其他的理论研究，使用 C 语言实现了一套 lock-free 的数据结构 Pratical lock-free data structures。 Python的JIT解释器pypy也通过STM机制克服Python的 Global interpreter lock(GIL，全局解释器锁)带来的问题，实现了pypy-stm以更加充分地利用CPU资源，提高程序的运行效率。 在JVM上，Clojure语言通过标识和状态分离机制实现了STM，以便于更好地服务于并发程序。而 Multiverse和源自于Scala的Akka框架的成功也将STM带入了Java语言。Akka使用了提交屏障(CommitBarrier，基于Java的倒计时锁存器建立)这一概念来使不同线程上的多个事务能够像一个单一的原子操作块般被管理，在跨越多个线程的所有事务之间，设置一个单一的、共同的屏障点，一旦屏障被触及，所有的事务均将自动提交。 而在硬件方面，Inter Haswell 架构的CPU已经开始通过Transactional Synchronization Extensions (TSX)机制对Tansactional Synchronization 提供硬件级别的支持，以使得能够在软件层次更好、更方便、更高效地实现事务性内存访问和同步。

STM使用示例

模拟银行账户

银行账户的存款/取款操作要求高并发，同时要保证极强的一致性。使用传统的基于锁的模型来表达这一需求的程序逻辑 非常复杂，而使用STM可以实现一个很完美的解决方案。

import Control.Concurrent.STM

type Account = TVar Int

-- transfer `amount` from account `a` to `b`.
transfer :: Account -> Account -> Int -> IO ()
transfer a b amount = atomically $ do
    deposit b amount
    withdraw a amount

withdraw :: Account -> Int -> STM ()
withdraw x amount = do
    balances <- readTVar x
    writeTVar x (balances - amount)

deposit :: Account -> Int -> STM ()
deposit x amount = withdraw x (-amount)

此外，对于基于锁的程序，当账户余额不足时，需要等待，实现这一需求需要使用轮询等策略，而在STM中，可以将当前线程挂起，直到有 其他的线程修改了相关的TVar的值，线程才会被重新唤醒，效率很高。

limitWithdraw :: Account -> Int -> STM ()
limitWithdraw x amount = do
    balances <- readTVar x
    if amount > 0 && amount > balances
        then retry
        else writeTVar x (balances - amount)
    -- or:
    -- check (amount > 0 && amount > balances)
    -- writeTVar x (balances - amount)

哲学家进餐问题(Dining Philosopher Problem)

对于传统的程序解决哲学家进餐问题，必须建立一个全局唯一的加锁顺序，否则存在死锁的风险。而使用STM可以得到一个更加优美的解决 方案。

首先，定义一个binary semaphores来表示对筷子的占用(锁)，实现相应的P、V操作：

type Semaphore = TVar Bool

newSem :: Bool -> IO Semaphore
newSem val = newTVarIO val

p :: Semaphore -> STM ()
p sem = do
    readTVar sem >>= check
    writeTVar sem False

v :: Semaphore -> STM ()
v sem = writeTVar sem True

然后定义哲学家的行为：

philosopher :: Int -> Semaphore -> Semaphore -> IO ()
philosopher n left right = do
    -- thinking.
    randomDelay
    atomically $ do { p left; p right }
    -- eating.
    randomDelay
    atomically $ do { v left; v right }
    -- continue.
    philosopher n left right
    where randomDelay = randomRIO (100000, 500000) >>= threadDelay

最后，创建 n 支筷子，开始运行程序：

simulate n = do
    forks <- replicateM n (newSem True)
    mapM_ (\i -> forkIO (philosopher i (forks !! i) (forks !! ((i+1) `mod` n)))) [0..n-1]

为了观察程序运行的具体过程和状态，建立一个buffer：

type Buffer a = TVar [a]

newBuffer :: IO (Buffer a)
newBuffer = newTVarIO []

push :: Buffer a -> a -> STM ()
push buffer item = readTVar buffer >>= writeTVar buffer . (++ [item])

pop :: Buffer a -> STM a
pop buffer = readTVar buffer >>= \x -> case x of
    []     -> retry
    (x:xs) -> writeTVar buffer xs >> return x

output buffer = atomically (pop buffer) >>= putStrLn >> output buffer

然后，在thinking和eating这两个delay中加入一些输出信息：

    -- thinking.
    atomically (push output $ "Philosopher " ++ show n ++ " is thinking.")
    randomDelay
    -- eating.
    atomically (push output $ "Philosopher " ++ show n ++ " is eating.")
    randomDelay

将主程序修改为

simulate n = do
    chopsticks <- replicateM n (newSem True)
    bufout <- newBuffer
    let thead i = philosopher i (chopsticks!!i) (chopsticks!!((i+1) `mod` n))
    mapM_ (\i -> forkIO (thead i bufout)) [0..n-1]
    output bufout

示例输出：

Philosopher 0 is thinking.
Philosopher 1 is thinking.
Philosopher 2 is thinking.
Philosopher 3 is thinking.
Philosopher 1 is eating.
Philosopher 3 is eating.
Philosopher 1 is thinking.
Philosopher 1 is eating.
Philosopher 3 is thinking.

完整程序：Philosopher.hs

参考

  1. Software Transactional Memory (STM)
  2. Chapter 10. Software Transactional Memory
  3. Beautiful Concurrency by Simon Peyton Jones