软件事务内存

在计算机科学中，软件事务内存（Software transactional memory，缩写为STM），又译为交易内存，软件交换式内存，是一种并发控制机制，模拟数据库事务的机制，控制在并行计算时对共享内存的访问控制。它是锁的一种替代机制。在STM中，一个事务指的是一段读、写共享内存的代码。这些读写操作在逻辑上是一个独立的单元，其中间状态对于其它的事务而言，是不可见的。

## 性能

与现在许多多线程应用程序广泛使用的锁机制不同，STM是一种非常乐观的并发控制机制：一个线程独立完成对共享内存的修改，完全忽略可能会有其它的线程存在，但是线程在日志中记录对共享内容的每一个读写动作。其他的并发控制一般是在进行写操作时来保证与其他事务的一致性（不能修改已经被别的事务修改过的共享数据），STM在完成一个事务之后，再验证其它线程有没有并发的对共享内存进行或修改，从而保证事务是完整的。因此，STM事务的最后一个操作是验证，如果验证通过，则提交，否则取消，导致所有以前进行的修改动作回滚。如果一个事务不能够提交，一般的，事务将回滚，并且从入口开始重新执行。

采用这种乐观策略可以增加并发性能：任何线程无需等待一个资源，多个线程可以并行而且安全的修改同一数据结构的多个部分（如果采用锁，它们一般在同一个锁的保护之下）。除了在事务失败后需要重试而增加开销之外，在现实世界中，由于冲突是很罕见的，因此，实际上可以带来性能的提升。尤其是在多处理器的情况下。

不过，在一些实践中，在较少CPU（1-4）的系统上，基于STM的应用程序相对于一些精心调节的基于Lock的应用程序而言，会有一定的性能损失。主要的原因是在STM事务中，需要维持log，以及额外的花在提交事务上的时间。不过，即使在这种情况下，性能也不会低于50%。

相对而言，STM拥护者认为STM带来的优势更为明显。

理论上，在最糟糕的情况下，当n个并发事务同时运行，他们需要n倍的内存和处理器，实际的需要取决于具体的实现细节（比如说一个事务可以尽早的失败以避免后续额外的开销）。在某些应用场景下，基于Lock机制的算法会比基于STM机制的算法更好。

## 概念上的优势和劣势

除了性能上的优势之外，STM可以在概念上简化多线程应用的模型，使得程序与一些已知的抽象概念如对象、模块等相处更为融洽，从而变得更易为维护。基于Lock的软件开发在实践上存在如下的问题：

- 需要将一些相互交错、局部的操作理解成为一系列的独立的、关系不密切的代码，这对程序员而言，是一个艰巨而且很容易犯错的任务。
- 需要程序员采用一定的策略来避免死锁、活锁，以及其他可能的错误。这些策略是强制的，且很容易犯错的，当出现相关的问题时，难以重现、排错。
- 会导致优先级冲突。经常会出现一个高优先级的线程需要等待另外一个低优先级的线程。

相反的，STM的概念要简单得多，因为每一个事务可以理解为隔离的，就像只有单个线程进行操作一般。死锁等会完全避免，无需程序员担心这个问题。优先级冲突的问题仍然存在，但一个高优先级的事务可以令得其他低优先级的事务提前终止。

相应的，由于需要提前结束事务，也对STM的事务提出了一些限制：在事务中不能够操作那些不能回滚的动作，例如大部分的IO操作。这些限制在实际开发中是通过创建缓冲区，记录这些不可回滚的操作，然后在事务完成后，在事务之外一次性的执行。在Haskell语言中，编译器会利用类型信息，做这个强制性检查。

## 提议的语言支持

STM在概念上的简单性使得我们可以简单的扩展语言来描述这个概念，Tim Harris和Keir Fraser在"Language Support for Lightweight Transactions"（语言支持的轻量级事务）中提出了conditional critical region（条件关键区） (CCR)来表述一个事务.在最简单的形式下，使用一个"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;
 }
```

在这个块结束时，事务会被提交，或者失败然后重试。CCR也容许事务等待一定的条件满足，这样的话，事务会一直等待，直到条件满足时，才开始事务。

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

如果条件不满足，事务管理器将等待，直到另外的一个事务提交，使得当前事务的条件得以满足。这种松耦合相对于需要在线程之间显式的进行信号通讯更简单。“Composable Memory Transaction”（组合内存事务）在这个基础上走得更远：通过retry命令，在事务的任何时候，终止当前事务，并且进行重试。比如：

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

这种在事务过程中终止事务，并且进行重试的方式可以简化并发开发，并且带来新的编程视角。

一个存在的问题是如何处理那些传播出去的异常，在"Composed Memory Transaction"中，作者决定在这种情况下，这个事务将失败。

## 事务的锁机制

STM可以通过不使用锁或者使用锁来实现。有两种锁的模式：遭遇战模式（encounter-time）下，所有内存的写操作需要首先得到一个访问锁，而后修改值，而后记录操作在undo日志中。提交模式下则仅在提交事务时获得一个访问锁。

提交模式在Dice、Shalev中实现。Shavit使用了一个全局版本时钟，每个事务开始时读到当前的版本号，并且将其作为读的版本号。然后，在每次读写访问时，访问内存的版本号会和读版本号比较，如果内存的版本号更大的话，表示这个内存已经被其他事务修改过，当前事务将失败。这就可以保证当前事务执行的所有代码都工作在一个独立的内存瞬间映像之上。在提交时，所有的写地址都将锁住，所有读写地址的版本号会重新检查。最后，全部版本号增加，所有新写入的内存将从日志中重新写入到内存中，并且更新其新的版本号。

## 参考资料

- Nir Shavit and Dan Touitou. Software Transactional Memory . Proceedings of the 14th ACM Symposium on Principles of Distributed Computing, pp. 204–213. August 1995. The paper originating STM.
- Maurice Herlihy, Victor Luchangco, Mark Moir, and William N. Scherer III. Software Transactional Memory for Dynamic-Sized Data Structures. Proceedings of the Twenty-Second Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing（PODC）, 92–101. July 2003.
- Tim Harris and Keir Fraser. Language Support for Lightweight Transactions . Object-Oriented Programming, Systems, Languages, and Applications, pp. 388–402. October 2003.
- Tim Harris, Simon Marlow, Simon Peyton Jones, and Maurice Herlihy. Composable Memory Transactions . ACM Conference on Principles and Practice of Parallel Programming 2005 (PPoPP'05). 2005.
- Robert Ennals. Software Transactional Memory Should Not Be Obstruction-Free (dead link). Archived: Software Transactional Memory Should Not Be Obstruction-Free.
- Michael L. Scott et al. Lowering the Overhead of Nonblocking Software Transactional Memory gives a good introduction not only to the RSTM but also about existing STM approaches.
- Torvald Riegel and Pascal Felber and Christof Fetzer, A Lazy Snapshot Algorithm with Eager Validation introduces the first time-based STM.
- Dave Dice, Ori Shalev, and Nir Shavit. Transactional Locking II.
- Knight, TF, An architecture for mostly functional languages, ACM Lisp and Functional Programming Conference, August, 1986.
- Knight, TF, System and method for parallel processing with mostly functional languages, US Patent 4,825,360, April, 1989.
- Ali-Reza Adl-Tabatabai, Christos Kozyrakis, Bratin Saha, Unlocking concurrency, ACM Queue 4, 10 (December 2006), pp 24–33. Ties multicore processors and the research/interest in STM together.
- James R Larus, Ravi Rajwar, Transactional Memory, Morgan and Claypool Publishers, 2006.

## 外部链接

- Cambridge lock-free group
- Software transactional memory Description; Derrick Coetzee
- Transactional Memory Bibliography
- Introduction to STM by Cyprien NOEL If you like it, there is a more detailed explanation in this free eBook (pdf).