事务内存

事务内存（英语：Transactional memory）是一种并行程式设计的方式，其来自于数据库管理系统（DBMS）中的事务（Transaction）概念。事务内存目前有两种实现方式，基于软件的软件事务内存（STM）和基于硬件的HTM（Hardware Transactional Memory）。

背景

采用任务并行时必须考虑线程间同步的问题：最初步也是最通常的方法是使用锁，只有获得了锁的线程在允许访问临界区，但是使用锁会发生一些问题，诸如优先级反转(Priority inversion)、死锁（Deadlock）、护航（Convoying）等问题；于是后来产生了无锁编程（Lockless programming）的概念，即使用原子操作（Atomic Operations）和同步路障（Memory barrier）来完成线程间同步的功能，这种方法规避了使用锁时出现的上述问题并极大的提高了并行度，但是面临着原子操作本身功能局限性和组合性(Compositionality)不佳的问题。原子操作的局限性使得无锁编程的算法设计很难，组合性则是指数个同步的原子对象组合应该也是一个同步的原子对象。

事务的概念

事务的概念源自于数据库管理系统（DBMS）中数据库事务的概念。在数据库管理系统中，事务必须满足ACID性质，即原子性，一致性，隔离性和持久性。原子性指的是事务中的动作要么全部执行，要么一个都不执行；一致性指的是任何时刻，数据库必须处于一致性状态，即必须满足某些预先设定的条件；隔离性是指一个事务不能看见其他未提交事务所涉及到的内部对象的状态，而持久性则是指一个已提交的事务对数据库系统的改变必须是永久的。

事务内存的分类和涉及到的基本术语

事务内存按照更新数据时的机制不同，可分为 延迟更新(deferred-update) 和 直接更新 (direct-update) 两大类。延迟更新软件事务内存的基本思想是一个线程仅改变属于自己的资料副本，如果未与其他线程发生冲突，最终的提交 (Commit) 动作则可顺利完成，副本内容抄到正本之上；如果失败则取消或回溯 (Abort / Rollback)，丢弃副本即可。直接更新则是一个线程暂时独占和直接更新资料正本，提交得到确认，只须解除独占设置，容许其他线程往后存取；直接更新需要资料的原始值作为副本，倘若运算最终无法完成，可作回溯之用。

根据在事务冲突时的处理机制不同，又可以分为 悲观和乐观的并发控制(pessimistic & optimistic concurrency control)两大类。在悲观的并发控制中，冲突一旦发生就必须要得到侦测并加以解决，而在乐观的并发控制里，冲突的侦测和解决可以延迟，只要是在事务提交之前进行就可以了。

事务还有粒度(granularity)的概念：最容易让程序员理解的粒度是对象粒度；在此粒度下，任何冲突发生的判决是在对象范围内进行的：即使两个事务修改的内存块不重合，只要他们是在同一个对象内，那么就可以判断这两个事务冲突。更精细的粒度是字粒度(word granularity)和字节粒度(byte granularity)，在这两种粒度下，冲突的检测更精细，更利于事务内存系统性能的提升，但是却会给程序员带来不小的麻烦。

软件事务内存（STM）

软件事务内存的实现包括原子对象（Atomic object）、冲突判决器（Conflict manager）。其中原子对象的实现是最重要的，它是各事务之间通信同步的介质。原子对象的实现又分为顺序性实现和事务实现：其中事务实现还要要求实现同步和恢复（recovery）功能，同步功能即意味着要求有检测事务冲突的能力，而恢复功能则意味着需要在事务失败的时候将对象回滚到事务执行之前的状态。目前提出的原子对象一般是基于读/写冲突(Read/Write conflict)的机制：原子对象提供两个接口，一个为读接口，一个为写接口，通过读接口可以得到一个可以读的对象，而通过写接口则可以得到一个可以写的对象。为了检测冲突（即多个事务并发时的同步情况），事务中可以设立两个集合，一个为读集（Read set）,一个为写集（Write set），分别记录该事务所要处理的读写原子对象集。如果一个事务的读集或写集与另一个事务的写集有交叉，则表明两个事务冲突，需要冲突判决器进一步采取决策。

硬件事务内存（HTM）

Sun微系统的Rock微处理器将支持硬件事务内存。

Azul Systems在2009年推出的 Vega 2 微处理器支持硬件事务内存。

相关的话题

• 内存一致性模型 （Memory consistency model）
• 无锁编程（Lockless programming）
• 任务并行
• 事务提升（Transactional boosting）

参考书目

1. Transactional Memory，Synthesis Lectures on Computer Architecture，Mark D. Hill, University of Wisconsin, Madison