CS149 笔记：Transactional Memory

这节课讨论如何进一步提高并行程序的同步抽象：程序员不再手动选锁、定义加锁粒度和规定加锁顺序，而是用 atomic 声明“这组内存操作必须作为一个整体执行”，由系统负责实现原子性。

核心思想是：锁预先约束“谁可以进入”，事务则让系统有机会先并发执行，只在真正的数据冲突出现时才撤销或串行化。

事务内存的语义

一个内存事务是一段原子且隔离的内存访问序列，它需要提供三个基本性质：

• Atomicity（原子性）：要么全部提交，要么全部撤销，不会留下部分更新。
• Isolation（隔离性）：提交之前，其他处理器不能观察到事务的中间写入。
• Serializability（可串行化）：并发事务的结果必须等价于它们按某个单一顺序依次提交，但语义不保证具体顺序。

每个事务都有一个读集（read set）和写集（write set）。当两个事务对同一数据产生读写冲突或写写冲突时，系统必须使其串行化；读读不构成冲突。

因此，两个线程可以同时遍历树的共享路径，并分别修改不同叶子；但如果它们写入同一节点，或一方写入了另一方正在读取的节点，就必须冲突处理。这比手递手锁更接近程序真正的数据依赖。

atomic 不等于 lock() + unlock()

atomic 是声明式抽象：程序员说明“什么必须是原子的”，系统自行选择锁、乐观执行或其他实现。

锁是命令式的阻塞原语：程序员必须明确指定“如何互斥”。单独的加锁和解锁并不自动保证业务操作的原子性与隔离性。

两者也不能机械替换：锁还可用于等待、通知等非事务型同步；而事务只能保证已正确划定的边界。如果程序员把本应一体化的操作拆成两个 atomic 区域，仍然会出现原子性错误。

事务内存解决了什么

显式锁迫使程序员在正确性和并发度之间手动取舍：粗粒度锁容易正确但限制并发，细粒度锁可以提高性能，却容易产生竞争、死锁和组合问题。

事务内存的主要价值是：

• 自动挖掘并发性：没有读写或写写冲突的事务可以并行，不必被同一把粗锁拦住。
• 失败原子性：受事务管理的内存更新在异常时可直接 abort，避免手写复杂的撤销逻辑和遗留锁。
• 可组合性：内层事务可以被外层事务统一包含，最外层边界定义整体原子性，不需要全局统一加锁顺序。

这些是 TM 的承诺，不是无条件性能保证。实际收益取决于工作负载的冲突率、事务长度和底层实现。

实现的两个核心选择

TM 必须解决两个相互独立的问题：如何保存未提交的新数据，以及何时检测并发事务之间的冲突。

数据版本管理

• Eager versioning（急切版本管理）：写入立即更新内存，同时保存 undo log。提交快，但每次写入都有日志开销，abort 时需要回滚。
• Lazy versioning（惰性版本管理）：新值先留在 write buffer，提交时才写回内存。abort 只需丢弃缓冲区，但 commit 必须集中发布所有写入。

冲突检测时机

• Pessimistic detection（悲观检测）：在每次 load/store 时立即检查，冲突发现早、无效工作少，但检查位于访存关键路径，细粒度通信多，还可能缺少前进保证。
• Optimistic detection（乐观检测）：先执行，到 commit 时再集中检查。它适合冲突较少的工作负载，但冲突发现晚时可能撤销大量已完成的工作。

“版本怎么存”与“冲突什么时候查”是两条不同的设计轴，可以组合成不同的软件 TM、硬件 TM 或混合方案，并没有对所有场景都最优的唯一组合。

冲突检测粒度

系统还要决定用多大的数据单位记录事务状态：

• 对象粒度的元数据少、映射快，但对象内不同字段也会产生假冲突。
• 字段或字粒度能减少假冲突、提高并发度，但时间和空间开销更高。
• cache line 粒度与硬件缓存一致性机制自然匹配，元数据较少，但也可能因同一 cache line 内的无关数据发生假冲突。

这个取舍与 false sharing 很相似：粒度越粗，跟踪成本越低，但误判冲突的概率越高。

Software TM 如何工作

STM 通过编译器或运行时把普通内存访问改写为 tmRd、tmWr、tmTxnBegin 和 tmTxnCommit 等操作，从而插入记账、验证、提交和回滚逻辑。

它主要维护两类数据结构：

• 每线程的事务描述符：保存读集、写集、undo log 或 write buffer，用于 commit 和 abort。
• 每份共享数据的事务记录：保存版本号、读者状态或写者所有权，用于发现冲突。

课件的 STM 示例采用“急切版本管理 + 乐观读 + 悲观写”：读操作直接取值并验证版本，写操作先取得所有权并记录旧值；提交时通过全局与本地时间戳再次验证读集，然后发布新版本并释放写权。

硬件 TM 解决的仍是同一类问题，只是将读写集跟踪和冲突检测放到硬件中。它通常以 cache line 为粒度，并复用缓存一致性中的共享/独占权思路。

核心理解

事务内存不是一种新的互斥锁语法，而是把“如何保证原子性”从程序员手中移交给系统。系统通过记录读写集、检测真实数据冲突，让无冲突事务并行，让冲突事务撤销、等待或串行化。

一条完整的主线是：声明 atomic 边界 → 跟踪读集与写集 → 检测冲突 → 无冲突则并发 → commit 一次性可见，abort 完整回滚。