bittern.cn
9多处理器编程艺术

事务内存

简化的并发编程

事务STM隔离

🎯 AI 时代的学习建议：不要只读理论。理解这一章的设计动机（为什么需要这个概念？）和边界条件（什么情况下会失效？）。当 AI 生成的代码涉及这些概念时，你能判断它是否用对了场景。AI 能帮你总结内容，但无法替代你亲手阅读、思考、建立直觉的过程。

第九章 事务内存 (Transactional Memory)

一、导读

1.1 本章学习目标

理解事务内存（Transactional Memory）的基本概念和设计动机

掌握事务的 ACID 属性在并发编程中的含义

了解事务内存的实现方式：硬件事务内存（HTM）与软件事务内存（STM）

学会使用事务内存来简化并发编程

理解事务内存的冲突检测机制和冲突解决策略

掌握事务内存的性能特征及其与锁机制的比较

了解事务内存在实际系统和编程语言中的应用

1.2 为什么本章如此重要

基于锁的并发编程面临几个根本性的挑战：死锁（多个线程互相等待对方持有的锁）、优先级反转（高优先级线程被低优先级线程间接阻塞）、convoy 效应（大量线程排队等待一把锁）。此外，锁的粒度选择是一个两难困境：粗粒度锁简单但并发度低，细粒度锁并发度高但容易死锁且编程复杂。

事务内存提供了一种根本性的替代方案：程序员只需要标注哪些代码块是"事务"（atomic block），系统自动保证事务的原子性和隔离性。程序员不需要显式地使用锁，也不需要担心死锁和锁粒度的问题。这种编程模型大大简化了并发编程的复杂性。

事务内存的思想来源于数据库系统的事务（Transaction）。数据库事务具有 ACID 属性：原子性（Atomicity，事务中的操作要么全部生效，要么全部不生效）、一致性（Consistency，事务保持数据的约束）、隔离性（Isolation，并发事务互不干扰）、持久性（Durability，事务完成后数据永久保存）。在并发编程中，事务内存主要关注原子性和隔离性。

事务内存的研究始于 1980 年代，但直到近年来才在工业界得到实际应用。Intel 的 TSX（Transactional Synchronization Extensions）提供了硬件事务内存支持；Java 和 C++ 社区也在探索软件事务内存的实现。虽然事务内存还没有完全取代锁机制，但它已经成为并发编程工具箱中重要的一员。

1.3 核心问题引导

事务内存解决了锁机制的哪些问题？它的基本思想是什么？

事务的 ACID 属性在并发编程中意味着什么？

硬件事务内存和软件事务内存各有什么优缺点？

事务内存如何检测和处理冲突？乐观策略和悲观策略有什么区别？

事务内存的性能在什么情况下优于锁？什么情况下不如锁？

事务内存的"开放嵌套"和"封闭嵌套"有什么区别？

二、核心概念详解

2.1 事务内存的基本概念

事务内存的核心思想是：将一段代码标记为"事务"（atomic block），系统保证事务内的所有内存操作作为一个原子单元执行。如果事务执行过程中没有与其他事务冲突，则事务成功提交（commit），所有修改对其他事务可见。如果检测到冲突，则事务中止（abort），所有修改被回滚（rollback），事务可以重试。

事务内存提供两个基本操作：atomic { ... } 标记一个代码块为事务，事务内的所有操作要么全部生效，要么全部不生效；retry / abort 允许事务主动中止。

事务内存的保证包括：原子性（Atomicity）——事务内的操作看起来是原子执行的，其他事务要么看到事务执行前的状态，要么看到事务执行后的状态，不会看到中间状态；隔离性（Isolation）——并发执行的事务互不干扰，每个事务看到的数据状态与其他事务的执行顺序无关。

2.2 硬件事务内存（HTM）

硬件事务内存（Hardware Transactional Memory，HTM）使用处理器硬件来支持事务的执行和冲突检测。

HTM 的工作原理：处理器为每个事务维护一个"读集"（Read Set）和"写集"（Write Set）。读集记录事务读取的所有缓存行，写集记录事务修改的所有缓存行。当事务提交时，处理器检查读集中的缓存行是否被其他处理器修改过（通过缓存一致性协议检测）。如果没有冲突，写集原子地提交到内存；如果有冲突，事务中止并重试。

HTM 的优势：性能高（硬件实现的冲突检测比软件快得多）；与现有代码兼容（不需要修改编译器或运行时）。HTM 的劣势：事务容量有限（受限于缓存大小，通常为几十 KB 到几百 KB）；不支持长事务（事务执行时间不能太长，否则缓存行可能被替换）；不支持 I/O 操作和系统调用（这些操作不能被回滚）。

Intel 的 TSX（Haswell 及以后）提供了两种 HTM 接口：RTM（Restricted Transactional Memory，受限事务内存，提供基本的 atomic 块）和 HLE（Hardware Lock Elision，硬件锁消除，可以透明地将锁优化为事务）。

2.3 软件事务内存（STM）

软件事务内存（Software Transactional Memory，STM）使用软件机制来实现事务的原子性和隔离性。它不需要特殊的硬件支持，可以在任何处理器上运行。

STM 的基本实现：为每个共享变量维护一个版本链（Version Chain）。事务开始时记录一个全局时间戳。读取变量时，从版本链中找到事务开始时有效的版本。写入变量时，创建一个新的版本但不立即提交。事务提交时，通过 CAS 操作原子地更新版本链的头指针。

STM 的冲突检测：乐观策略——事务执行时不检查冲突，在提交时检查。如果读集中的变量的版本在事务执行期间被修改，则冲突，事务中止。悲观策略——每次读写时都检查冲突，发现冲突立即中止。

STM 的优势：不受事务容量限制（可以处理任意大小的事务）；支持长事务；可以处理 I/O 操作。STM 的劣势：性能低于 HTM（软件实现的开销较大）；需要编译器或运行时的支持。

2.4 冲突检测与解决

事务内存的核心机制是冲突检测和解决。

冲突检测的方式：基于缓存行的检测（HTM 常用）——以缓存行为粒度跟踪读写集，粒度粗但硬件实现简单。基于变量的检测（STM 常用）——以变量为粒度跟踪读写集，粒度细但开销较大。

冲突解决的策略：Eager（悲观）——检测到冲突时立即中止其中一个事务，优势是快速释放资源，劣势是可能中止不必要的事务。Lazy（乐观）——事务执行时不检查冲突，在提交时检查，优势是避免了虚假冲突，劣势是可能浪费大量工作在最终会中止的事务上。

冲突时选择哪个事务中止：通常中止"较新"的事务（后开始的事务），因为它做的工作较少。更高级的策略考虑事务的优先级、已做的工作量等因素。

2.5 事务内存的嵌套

事务嵌套是指在一个事务内部开始另一个事务。嵌套的处理方式有两种：

封闭嵌套（Closed Nesting）：内层事务在外层事务提交之前必须先提交或中止。如果内层事务中止，只有内层的修改被回滚，外层事务继续执行。这种模式类似于数据库中的子事务。

开放嵌套（Open Nesting）：内层事务可以独立于外层事务提交。一旦内层事务提交，其修改就对外层事务可见，即使外层事务最终中止。这种模式适用于需要"部分提交"的场景，如预订机票——座位预订一旦确认就不应该因为后续步骤失败而取消。

三、深入分析与讨论

3.1 事务内存 vs 锁机制

事务内存和锁机制是两种不同的并发控制策略，各有优劣。

事务内存的优势：编程简单（不需要显式管理锁）；无死锁（因为不使用锁）；组合性好（不同事务可以安全地组合）；自动处理锁粒度问题。

锁机制的优势：可预测性高（锁的行为确定，不会随机中止）；支持复杂的协调逻辑（如条件等待、通知）；性能稳定（不会因冲突重试而波动）。

在低争用场景下，事务内存和锁机制的性能相当。在高争用场景下，事务内存可能因为频繁中止和重试而性能下降。在需要复杂协调的场景下（如生产者-消费者），锁机制（配合条件变量）更合适。

3.2 事务内存的正确性

事务内存的正确性标准通常是串行化（Serializability）：并发事务的执行等价于某种顺序执行。这与数据库事务的正确性标准相同。

更弱的一致性标准包括：提交快照隔离（Committed Snapshot Isolation，CSI）——每个事务看到事务开始时已提交的数据快照；可重复读（Repeatable Read）——事务内多次读取同一变量返回相同的值。

选择哪种一致性标准取决于应用需求。金融交易通常需要串行化；社交媒体的计数器可以接受更弱的一致性。

3.3 事务内存的实际应用

事务内存在实际系统中的应用正在增长。

数据库系统：现代数据库（如 PostgreSQL、MySQL）使用多版本并发控制（MVCC）来实现事务隔离，本质上是一种软件事务内存。

操作系统内核：Linux 内核在某些子系统（如 cgroups、namespace）中探索使用事务内存来替代锁。

编程语言支持：Haskell 的 STM 库是最成熟的软件事务内存实现；Java 的 Multiverse 和 Scala 的 STM 库提供了 JVM 上的事务内存支持。

硬件支持：Intel TSX 在服务器和工作站处理器上广泛可用，为数据库和虚拟化等应用提供硬件加速的事务支持。

四、实践案例

4.1 使用事务内存实现链表插入

使用锁的链表插入：

java
void insert(Node node) {
  lock.acquire();
  Node prev = findPrev(node);
  node.next = prev.next;
  prev.next = node;
  lock.release();
}

使用事务内存的链表插入：

java
void insert(Node node) {
  atomic {
    Node prev = findPrev(node);
    node.next = prev.next;
    prev.next = node;
  }
}

事务内存版本不需要显式管理锁，代码更简洁。系统自动保证插入操作的原子性。

4.2 银行转账的事务实现

使用事务内存实现银行转账：

java
void transfer(Account from, Account to, int amount) {
  atomic {
    from.balance -= amount;
    to.balance += amount;
  }
}

事务保证了转账的原子性：要么两个账户的余额都更新，要么都不更新。不会出现"扣款成功但存款失败"的情况。

五、常见误区与注意事项

5.1 认为事务内存可以替代所有锁

事务内存适用于"数据冲突"场景（多个线程修改共享数据），但不适用于"协调"场景（如生产者-消费者中的等待和通知）。对于需要复杂协调的场景，锁和条件变量仍然是更好的选择。

5.2 忽视事务中止的开销

事务中止不是免费的——它需要回滚所有修改，可能涉及大量的内存操作。在高争用场景下，频繁的事务中止可能导致性能急剧下降。应该尽量减少事务的大小和冲突概率。

5.3 在事务中执行不可撤销的操作

事务中的操作必须是可撤销的（可以回滚）。I/O 操作、网络请求、文件写入等不可撤销的操作不应该在事务中执行。如果必须在事务中执行这些操作，需要使用"补偿事务"来撤销。

5.4 忽视 HTM 的容量限制

HTM 的事务容量受限于处理器的缓存大小。如果事务访问的数据超过缓存容量，事务会因"容量中止"而失败。对于大事务，应该使用 STM 或将事务拆分为多个小事务。

六、本章小结

本章介绍了事务内存的概念、实现和应用。事务内存通过 atomic 块简化了并发编程，自动保证原子性和隔离性。HTM 使用硬件实现，性能高但容量有限；STM 使用软件实现，灵活但开销较大。冲突检测和解决是事务内存的核心机制，有乐观和悲观两种策略。事务内存适用于数据冲突场景，不适用于复杂协调场景。在实际系统中，事务内存正在数据库、操作系统和编程语言中得到越来越广泛的应用。

七、思考题与练习

使用事务内存重写一个基于锁的并发数据结构（如并发栈或队列）。比较代码复杂度和性能。

分析 HTM 和 STM 在以下场景中的适用性：（a）短小的计数器更新；（b）大规模数据结构的修改；（c）包含文件 I/O 的事务。

实现一个简单的软件事务内存系统，支持 atomic、read 和 write 操作。

设计一个场景来演示事务内存的"活锁"问题（事务不断中止和重试，永远无法提交）。

比较事务内存和锁机制在以下场景中的性能：（a）低争用的计数器更新；（b）高争用的哈希表插入；（c）链表遍历和修改。

解释封闭嵌套和开放嵌套的区别，给出各自适用的场景。

研究 Intel TSX 的工作原理，分析其容量限制对程序设计的影响。

讨论：事务内存是否会在未来完全取代锁机制？给出你的分析和论据。

9/10事务内存
0%