Abstract

transactional memory 是一种新的多处理器架构，主要是为了高效实现无锁同步，并像以往基于锁的方案一样可靠。

1. Introduction

无锁数据结构的含义是指数据结构上的操作不需要互斥。无锁可以避免在高并发系统中出现的一些因为锁竞争带来的问题：

• 优先级反转。一个高优先级的进程需要一把被低优先级的进程锁持有的锁，导致高优先级的进程反而排在低优先级的进程的后面。
• Convoying。持有锁的进程因为某种原因失去被 CPU 执行，进入 ready 队列或 wait 队列，而其它需要锁的进程也因为拿不到锁而无法执行。
• 死锁。 无顺序请求多个锁可能导致死锁。

软件层面实现的无锁数据结构，有个新的问题：在上述问题不存在的时候，额外带来的开销反而导致性能没有基于锁的传统方案好。这个很好理解，无锁必定会有一些额外的机制，这个机制在竞争不强的时候，相比于加锁/解锁操作反而效率更低。

2. Transactional Memory

这里的 transaction 定义有点不一样：单进程执行的一个有穷机器指令序列，满足:

• Serializability: 有点类似于 sequential consistency 的概念，执行过程中，transaction 的各步不会与其它事务交错。不同的处理器观察到已提交的事务都是相同的执行顺序。

这里不确定是严格意义上的不准交错，还是允许重排，但是对外表现出不交错。

• Atomicity: 原子性，这个好理解

假设一个进程一个时间点只执行一个事务。虽然这个假设模型可以扩展以支持 overlapping 也即交错，或逻辑嵌套事务，但是作者认为没有实际业务场景需要这样。

感觉这个有点牵强？overlapping 后处理器可以更好的并行啊，嵌套事务在 Spring 中用的还算多。

2.1 Instructions

• Load-transactional (LT)
  读一个共享内存的地址到一个私有寄存器里
• Load-transactional-exclusive (LTX)
  读一个共享内存的地址到一个私有寄存器里，hinting (提示）这个地址可能被更新
• Store-transactional (ST)
  临时将一个私有寄存器里的值写到共享内存里。这个新值直到事务成功提交后才对核可见。

这种可见性是怎么实现的？

一个事务的 read set 是 LT 读到的所有地址集合，write set 是 LTX 或 ST 访问的所有地址集合，data set 是 read set 并上 write set。
transactional memory 还提供如下指令来操作事务状态：

• Commit 尝试使事务的临时修改持久化。成功的条件是 data set 里的每个地址没有被任何其它事务修改，write set 没有被任何其它事务读过。也就是说，保证每个事务的隔离性，同时不产生脏读。只有成功后，修改的内容才会对其它处理器可见，否则，所有临时修改并不会持久化。
• Abort 手动关闭一个事务，让其失败。
• Validate 测试当前事务的状态是否已经 aborted。

以往操作内存只能一次操作一个 word，通过组合这些指令，可以对任意范围的内存提供自定义的 read-modify-write 操作，也即事务访问内存。作者也提供非事务的内存访问指令，load 和 store。
文中没有阐明一下几个问题：

• 事务和非事务访问同一个地址时，怎样交互

注释中提了一个方案，就是把 load 和 store 也当作一个事务，且这个事务永远会 commit，如果检测到冲突就 abort。

• 具体什么情况下会导致事务提交失败，而把具体实现交给开发人员自己定义，比如 page falut, context switches, 或者违背了 serialization。

2.2 Intended Use

主要是替换一些 短临界区。基于锁访问临界区的流程一般是：申请获取锁，做一些工作，释放锁。而基于 transactional memory 的无锁算法是：

1. 用 LT 或 LTX 读一些要操作的变量的地址。
2. 用 Validate 检查是否一切 OK 可以继续。如果失败，回到1。
3. 用 ST 来修改这些地址
4. 用 Commit 尝试提交这些修改。如果失败，回到1。

复杂点的事务可能需要排列组合一下 LT 和 Validate，如果竞争很高，最好加个 backoff 策略即回退，这个策略很常见，如以太网中用的二进制指数回退。

Validate 指令源于对软件工程的考虑。
orphan 孤儿事务是指在被 abort 掉之后继续执行的事务（比如 read set 被其它已提交事务给改了)。如前面提到的算法所示，4 失败后会回到 1 重来，如果没有 2 步骤，这就是个死循环。虽然孤儿事务不会被提交，但是可能会遇到一些访问到一些非正常的错误。比如，本来按原程序的逻辑，绝对不会出现除以 0 的情况的，但是因为 data set 被改了，这个时候处以 0 了，就会出错。或者覆写了一个不属于它的地址。
很难去检测到孤儿事务，因为不清楚尝试有限次后会退出还是永远不会。

Implementation