Lecture 17: Transactional Memory (Part I)（日期：Dec 02）

目录 · ← l16 · l18 →

Lecture 17: Transactional Memory (Part I)（日期：Dec 02）

概述：本讲把同步的抽象层次再往上抬一层：从机器级原子指令（test-and-set、fetch-and-op、CAS、LL/SC）和软件层原语（锁、屏障、无锁结构），提升到事务内存（Transactional Memory, TM）。先讲清 memory transaction 的语义（atomicity、isolation、serializability）以及 atomic { } 与 lock/unlock 在语义上的本质区别；然后讨论 TM 实现的两大设计问题——data versioning policy（数据版本策略）与conflict detection policy（冲突检测策略）；最后分别给出乐观（optimistic）与悲观（pessimistic）两种冲突检测的行为与权衡。本讲末尾的”实现”内容（STM/HTM 细节）将在第 18 讲继续展开。

一、核心概念与定义

1. Memory Transaction（内存事务）

定义：一段原子且隔离的内存访问序列，灵感来自数据库事务（database transactions）。它有三个语义性质：
- Atomicity（原子性，all or nothing）：事务 commit（提交）时，事务内的所有内存写在同一时刻全部生效；事务 abort（中止）时，所有写都像从未发生过一样不可见。
- Isolation（隔离性）：在 commit 之前，任何其他处理器都观察不到本事务的写。
- Serializability（可串行化）：所有事务看起来是以某个单一串行顺序提交的；但语义不保证确切的提交顺序。
现实类比：银行转账——”从 A 扣钱 + 给 B 加钱”必须整体生效或整体不生效；你不可能看到”钱已扣但没到账”的中间状态。
公式/图示：

事务 T: 读 X, Y, Z；写 A, X
其他处理器要么看到 T 的【全部】读写结果，要么【一个都看不到】——
就好像这些读写在同一瞬间发生（幻灯片：effectively all happen at the same time）

幻灯片总结：我们在一致性系统里为单个地址维护的那些性质，事务把它推广到一组读写上。

2. Declarative vs. Imperative Abstraction（声明式 vs. 命令式抽象）

定义：声明式抽象只说明”做什么“（what），命令式抽象说明”怎么做“（how）。atomic { ... } 是声明式的：程序员声明”这段代码要原子执行”，不指定用锁、用无锁还是用其他机制；系统负责实现原子性。对比：命令式的做法是”获取这把锁、执行操作、释放锁”。
现实类比：点外卖时你说”我要一份宫保鸡丁”（声明式），而不是”请打电话给某饭店、下单、付款、等配送”（命令式）——后者是你替店家把实现细节全包了。
图例（幻灯片原例）：

声明式：执行这 1000 个相互独立的任务
命令式：spawn N 个工作线程；从一个共享任务队列取任务分配给线程
声明式：把这一组操作原子地执行
命令式：获取锁 → 执行操作 → 释放锁

3. `atomic { }` 与 `lock()/unlock()` 的语义差异

定义：atomic 是对原子性的高层声明，不规定实现方式；lock 是低层阻塞原语，本身不提供原子性或隔离性（它只是互斥手段）。要点：锁可以用来实现 atomic block，但锁的用途超出原子性（如生产者-消费者同步、排队、条件等待）；因此不能把所有锁用法都替换成 atomic 区域。反过来，用 atomic 编程消除了很多 data race，但仍可能犯 atomicity violation——例如程序员把本该一个原子块完成的序列错误地拆成两个 atomic 块。
现实类比：atomic 像”承诺书”（我承诺这段代码原子执行），lock 像”门闩”（把门锁上不让别人进）——承诺可以用门闩实现，但门闩还能用于别的场景（比如防止宠物跑出门），不能一看到门就以为必须承诺书。
反例（幻灯片）：用 synchronized + 两个 flag 做线程间握手（flagA = true; while (flagB == 0);）——这种”等待”语义是锁才有的，原子块不提供等待，不能直接替换。
反例（atomicity violation，幻灯片）：程序员把逻辑上原子的序列错误拆成两个 atomic 块，另一个线程就能在中间插入破坏性操作：

// 线程 1（错误写法：被拆成两个原子块）
atomic { ...; ptr = A; ... }      // 块 1：写指针
atomic { B = ptr->field; }        // 块 2：解引用指针
// 线程 2
atomic { ...; ptr = NULL; ... }   // 恰好在块 1 与块 2 之间执行 → 崩溃/错误

即使每个块自身原子，块与块之间仍可被插入，逻辑原子性照样被破坏——这是”atomic 也救不了程序员”的经典示例。

4. Optimistic Concurrency（乐观并发）

定义：系统默认事务之间不会有真正的冲突，只有在真正发生 contention（竞争）时才做串行化。幻灯片：TM 系统采用乐观并发——只在出现真实冲突（read-write 或 write-write 冲突）时才需要保证串行化；没有冲突的事务完全并行执行。
现实类比：多人同时编辑同一份在线文档的不同段落：系统假定大家改的是不同段落（乐观），只有两人确实改了同一段（冲突）时才需要协调（合并/回滚）。
对比：悲观并发（锁）是”先拿锁再干活”，乐观并发是”先干活，提交时再检查有没有撞车”。

5. Read-Write Conflict / Write-Write Conflict（读写冲突 / 写写冲突）

定义：read-write conflict（R-W）：事务 A 读了地址 X，而事务 B 未提交地写了 X；write-write conflict（W-W）：事务 A 与 B 都处于 pending（未提交）状态且都写了 X。注意：read-read 永远不冲突——两个事务读同一个地址可以安全并行。
现实类比：两个人同时改一份报表的同一个单元格（W-W），或一个人在看、另一个人在改同一个单元格（R-W）；两人只是同时”看”则毫无问题。
图例（幻灯片树形例子，credit: Austen McDonald）：

         1
        / \
       2   3
      /     \
     4       5       目标：线程安全地同时修改节点 3 和 4

事务 A: READ 1,2,3; WRITE 3     事务 B: READ 1,2,4; WRITE 4
→ 没有 R-W 也没有 W-W 冲突（没人写对方读/写的数据）→ 可并行提交

事务 A: READ 1,2,3; WRITE 3     事务 B: READ 1,2,3; WRITE 3
→ 两者都写节点 3 → 冲突存在 → 两个事务必须串行化

幻灯片用这个例子对比细粒度锁：hand-over-hand 锁在更新节点 3 时顺路锁住节点 1、2（遍历路径上的所有节点），可能延误另一个对节点 4 的更新——锁会阻碍本可并行的操作（locking can prevent concurrency）；而事务只记录”实际读/写了哪些节点”，只要两个事务的读集/写集不冲突就互不干扰。

6. Read Set / Write Set（读集 / 写集）

定义：系统为每个进行中的事务记录它访问过的地址集合：read set = 事务执行期间读过的地址，write set = 事务执行期间写过的地址。冲突检测正是基于”我的读/写集与别人的读/写集是否有交集”。
现实类比：每个人在超市购物时拿一个购物清单（写集）和试吃记录（读集）；结账（commit）时收银员核对有没有人和你买了同一件东西、或者有人试吃后又改了价格。

7. Data Versioning Policy（数据版本策略）

定义：TM 系统如何管理未提交（新）版本与已提交（旧）版本两份数据。两种基本策略：
- Eager versioning（undo-log based，基于撤销日志）：写内存时立即就地更新，同时在 undo log 里记下旧值，以备 abort 时回滚。
- Lazy versioning（write-buffer based，基于写缓冲）：写操作先进入事务的 write buffer，commit 时才真正更新内存；abort 只需清空缓冲。
现实类比：eager 像”先改账本、另记一本撤销账”（改得快，但万一要撤销得逐条回退）；lazy 像”先在便签上打草稿，定稿了才誊抄进账本”（撤销就是撕掉便签，但誊抄要花时间）。
权衡（幻灯片）：eager——每次 store 都要记 undo（per-store overhead），commit 快（数据已在内存）、abort 慢、有容错问题（事务中途崩溃时内存里是半成品）；lazy——abort 快（清日志即可）、无容错问题、commit 慢（要刷缓冲）。哲学：eager 是”立刻写内存，赌事务不会 abort”；lazy 是”只在不得不写的时候才写内存”。

8. Pessimistic Conflict Detection（悲观冲突检测，又称 eager）

定义：在每次 load/store 执行时立即检查是否与别的 pending 事务冲突。哲学（幻灯片原话）：”我怀疑冲突随时可能发生，所以每次内存操作后都检查一次……反正迟早要回滚，不如现在就发现，避免浪费更多工作。”检测到冲突时，由 contention manager（竞争管理器） 决定暂停（stall）还是中止（abort）该事务。
现实类比：开车时每过一个路口都停下来确认没有对向来车（哪怕大概率没有）——安全，但每个路口都要踩刹车。

9. Optimistic Conflict Detection（乐观冲突检测，又称 lazy/commit）

定义：只在事务尝试 commit 时才检测冲突。哲学：”先往最好的方向想，等提交时再集中处理冲突。”一旦提交事务与其他事务冲突，提交方优先，其他事务可能被 abort。
现实类比：一路畅行到目的地才在终点检查有没有违章——大多数时候什么事都没有，撞上了（冲突）再处理。

10. Contention Manager（竞争管理器）

定义：悲观检测中的仲裁组件：冲突发生时由它决定让谁 stall、让谁 abort、以及 abort 后何时重试。不同的策略服务于不同场景（幻灯片：various policies to handle common case fast）。幻灯片在悲观检测的第 4 个 case（双方反复 abort、毫无进展）下留问：如何避免 livelock？——答案是 contention manager 的仲裁策略（如随机退避、按年龄优先、写者优先等）。
现实类比：十字路口的交警（contention manager）：两车相持时由交警决定谁先走、谁倒车（abort）重来，避免两车永远互相让路（livelock）。

11. Failure Atomicity（失败原子性）

定义：事务系统把”异常处理”也纳入原子性：除了程序员显式管理的异常外，所有异常都导致事务 abort 并撤销内存更新——因为事务要么整体提交要么整体不存在，所以”失败线程持有的锁丢失”这类问题不会发生（失败恢复 = abort + restart）。
现实类比：网购下单流程中途断网：订单要么成功要么被系统整体回滚，绝不会出现”钱扣了、订单没生成”的中间态，也不需要你手动写”退款”补救代码。
对比（幻灯片）：手动同步 + try/catch 的写法要求程序员逐 case 提供 undo 代码（”undo code 1”、”undo code 2”…），还要追踪哪些副作用对其他线程可见；事务把这一切交给系统：

// 手动版本：每个异常都要手写撤销逻辑
void transfer(A, B, amount) {
    synchronized(bank) {
        try {
            withdraw(A, amount);
            deposit(B, amount);
        }
        catch (exception1) { /* undo code 1 */ }
        catch (exception2) { /* undo code 2 */ }
        ...
    }
}
// 事务版本：系统处理所有（程序员未显式管理的）异常
void transfer(A, B, amount) {
    atomic {
        withdraw(A, amount);
        deposit(B, amount);
    }
}

注意事务版本的额外好处：不存在”失败线程持有的锁丢失”——因为事务根本没有持锁，失败就是 abort + 内存回滚。

12. Composability（可组合性）

定义：把多个同步代码模块组合成更大的同步操作的能力。锁的组合需要全系统范围的锁顺序策略才能正确（否则 transfer(A,B) 与 transfer(B,A) 并发即死锁），这破坏软件模块化；事务天然可组合：程序员声明外层”transfer 原子执行”，内层的 withdraw/deposit 若有自己的事务会被外层事务吸收（subsume），最外层事务决定原子性边界；系统对冲突的事务做串行化（如 transfer(A,B) 与 transfer(B,A)），对不冲突的事务保持并发（如 transfer(A,B) 与 transfer(C,D)）。
现实类比：乐高积木：每个模块（withdraw、deposit）内部自己是完整的，拼成大结构（transfer）后整体依然是一个原子单元——而不是像锁那样”两个零件拼在一起需要额外胶水规则（锁顺序）”。

补充：动机回顾——HashMap 的三级演进（幻灯片主线例子）

幻灯片用 Java HashMap 串起整个动机链条，值得单独梳理：

方案	线程安全	编程难度	性能
裸 `HashMap`（get 直接遍历 bucket 链表）	否（需要同步时是坑）	低	好（无同步时零锁开销）
`synchronized` 粗粒度包装层	是	低	差：全局锁限制并发、扩展性差
细粒度（每 bucket 一把锁）	是	高	好：减少争用（但不需要同步时也付出锁开销）
`atomic { return m.get(key); }`	是	低（和粗粒度一样简单）	取决于工作负载与 atomic 的实现（幻灯片原话）

关键洞察（幻灯片）：细粒度锁”即使不需要同步也付出锁开销”，而事务是乐观的——get 几乎总是只读（read-read 不冲突），在无竞争时按普通读执行，几乎零开销。配合第 16 讲回顾的图表（balanced tree 与 hash table 上 fine locks 优于 coarse locks），事务的目标是在简单性与并发度之间同时拿高分。

补充：TM 实现的设计空间小结（本讲范围）

本讲只展开两大设计轴，第 18 讲再叠加具体系统实例：

                    数据版本策略（Data Versioning）
        Eager（undo-log，写内存立即生效）      Lazy（write-buffer，提交时才写内存）
冲突   悲观（每次访存检查）     早发现、可 stall；无前进保证     每次访问都要查/写缓冲，开销更高
检测   乐观（提交时检查）       提交方优先；有前进保证           最自然的组合：写缓冲 + 提交校验

（HTM 的 cache 位元版本管理、STM 的时间戳方案、TCC/LogTM 等具体实例在第 18 讲展开。）

二、代码示例与详细解说（本讲重点）

示例 1：`deposit`——锁版本 vs 事务版本（C 风格伪代码）

// ---- 版本 A：用锁保证原子性 ----
void deposit(Acct account, int amount) {
    lock(account.lock);                // 先拿锁（悲观：先互斥再干活）
    int tmp = bank.get(account);       // 读
    tmp += amount;                     // 改
    bank.put(account, tmp);            // 写
    unlock(account.lock);
}

// ---- 版本 B：用事务保证原子性 ----
void deposit(Acct account, int amount) {
    atomic {                           // 声明式：只声明"这段要原子"，不说怎么实现
        int tmp = bank.get(account);   // 读
        tmp += amount;                 // 改
        bank.put(account, tmp);        // 写
    }
}

【代码做了什么？】

两个版本都实现同一个 read-modify-write 操作：读出余额、加金额、写回。版本 A 显式管理锁；版本 B 只声明 atomic { }，把同步的”如何做”完全交给系统（系统可以用锁实现 atomic，也可以用乐观并发实现）。
deposit 需要原子性，是因为它是”读-改-写”三连：两个线程同时执行时，若没有原子性，会出现经典的 lost update（两个线程都读到旧值、各自加钱、后写覆盖先写）。

【并行机制解说】

对应概念：memory transaction（概念 1）与声明式抽象（概念 2）。版本 B 的原子块语义是：提交时所有写一次性生效（atomicity）；提交前其他线程看不到（isolation）；两个并发 deposit 最终呈现某个串行顺序（serializability）。
幻灯片强调的语义区别（概念 3）：atomic 不承诺”怎么实现”——系统可以（幻灯片原话）”用锁实现 atomic { }”；而本讲讨论的实现采用乐观并发：只在真正出现 R-W 或 W-W 冲突时才做串行化。这正是事务与”锁住的临界区”的分水岭：锁是悲观地”先互斥后执行”，事务是乐观地”先执行、提交时再对账”。

示例 2：双链表 `PushLeft`——用 `atomic` 一行声明搞定（C）

typedef struct QNode {
    struct QNode *left, *right;
    int val;
} QNode;

// ---- 非线程安全版本 ----
void PushLeft(DQueue *q, int val) {
    QNode *qn = malloc(sizeof(QNode));
    qn->val = val;
    QNode *leftSentinel = q->left;       // 左哨兵
    QNode *oldLeftNode = leftSentinel->right;
    qn->left = leftSentinel;
    qn->right = oldLeftNode;
    leftSentinel->right = qn;            // 修改左哨兵的 right
    oldLeftNode->left = qn;              // 修改旧首节点的 left
}

// ---- 线程安全版本：整个操作包进 atomic ----
void PushLeft(DQueue *q, int val) {
    QNode *qn = malloc(sizeof(QNode));
    qn->val = val;
    atomic {
        QNode *leftSentinel = q->left;
        QNode *oldLeftNode = leftSentinel->right;
        qn->left = leftSentinel;
        qn->right = oldLeftNode;
        leftSentinel->right = qn;        // 两处指针写
        oldLeftNode->left = qn;          // 必须一起原子生效！
    }
}

【代码做了什么？】

在双链表头部插入一个新节点需要同时更新两个指针：leftSentinel->right 和 oldLeftNode->left。若这两步被并发线程打断，链表会出现只挂了一半的不一致状态（如：从左向右能遍历到 qn，从右向左却遍历不到）。
用锁实现需要精细决定锁哪些节点（细粒度锁的正确性难题，正是第 16 讲内容）；用 atomic 只需要把整个序列包起来。

【并行机制解说】

对应概念：memory transaction（概念 1）。这里的”原子性”覆盖多个不同地址的写——这正是事务相对单地址原子指令的价值：CAS 只能原子地改一个地址，而事务把”改 leftSentinel->right + 改 oldLeftNode->left”这两个地址的写当作一个整体提交。
若两个线程同时 PushLeft：它们的写集（哨兵、旧首节点）重叠 → 检测到冲突 → 系统让其中一个 abort 重来，保证最终一致性；若两个线程操作不同的双链表（不同节点集合），无冲突，完全并行——这就是幻灯片说的”事务提供 automatic fine-grained concurrency”。

示例 3：`transfer`——锁的组合死锁 vs 事务的组合（C 伪代码）

// ---- 锁版本：组合出死锁 ----
void transfer(A, B, amount) {
    synchronized(A) {
        synchronized(B) {
            withdraw(A, amount);   // 先锁 A 再锁 B
            deposit(B, amount);
        }
    }
}
// 线程 0: transfer(A, B, 100)
// 线程 1: transfer(B, A, 200)
// → 线程 0 持 A 等 B，线程 1 持 B 等 A → DEADLOCK！

// ---- 事务版本：组合优雅 ----
void transfer(A, B, amount) {
    atomic {
        withdraw(A, amount);   // withdraw 内部若有原子块，被外层吸收
        deposit(B, amount);    // 最外层 atomic 定义原子性边界
    }
}
// 线程 0: transfer(A, B, 100) 与 线程 1: transfer(B, A, 200)
// → 系统检测到写集冲突，串行化这两个事务（而不是死锁）
// → transfer(A, B, 100) 与 transfer(C, D, 200) 无冲突，并行执行

【代码做了什么？】

锁版本：transfer 要保证”从 A 取钱给 B”整体原子，最直接的做法是同时锁 A 和 B。但两个转账方向相反的线程会互相持锁等待——教科书式死锁。幻灯片还展示另一个变体：两个线程各自锁 B 再锁 A（transfer(B, A, amount) 把锁顺序写成 synchronized(B) { synchronized(A) }）同样死锁。
事务版本：transfer 外层一个 atomic，内部的 withdraw/deposit 即使是独立模块（各自带锁或原子块），其原子性诉求会被外层事务吸收，最外层决定边界。

【并行机制解说】

对应概念：composability（概念 12）。锁的组合需要”全系统锁顺序策略”，而策略往往要跨模块约定、破坏模块化；事务把”组合时的串行化决策”交给系统：冲突对串行化，无冲突对并行。幻灯片原话：“Transactions compose gracefully (in theory)”——程序员只需声明全局意图（transfer 原子执行），无需知道全局实现策略。
这正是 TM 的生产力论点（slides 承诺清单之一）：事务用接近粗粒度锁的简单性，获得接近细粒度锁的性能（见示例 4 的性能对比图），还能自动适配核心数（4 核最优的锁方案未必是 64 核最优的——performance portability）。

示例 4：悲观 vs 乐观冲突检测行为对比（伪代码时间线）

======== 悲观检测（eager）：每次 load/store 后立即检查 ========
Case 1（无冲突）: T0 rd A ─ wr B ─ wr C ─ commit     T1 rd A ─ commit   → 两者都成功
Case 2（提前发现）: T0 wr A ...（check 发现 T1 也在动 A）→ T0 stall 等待 → 之后 commit
Case 3（中止）: T0 rd A；T1 wr A → check 冲突 → T1（或 T0）abort → 重执行
Case 4（无进展）: T0 wr A / T1 wr A 反复 check 互相 abort restart → livelock！
                （幻灯片提问：如何避免？→ 需要 contention manager 仲裁）

======== 乐观检测（lazy/commit）：只在 commit 时检查 ========
Case 1（无冲突）: 两个事务都跑到 commit → 检查通过 → 都成功
Case 2（提交方优先）: T1 先 commit（写 A）→ check 时发现 T0 读/写了 A → T0 abort 重来
Case 3/4: 冲突事务被 abort 后 restart → 有 forward progress 保证

【代码做了什么？】

这是两段”行为时间线”伪代码，归纳幻灯片第 47、49 页的四种 case：悲观检测下，Case 2 能把 abort 提前变成 stall（省掉已做的无用功），Case 4 则可能因双方互踩而毫无进展（需要仲裁避免 livelock）；乐观检测下，提交方总是赢，被 abort 的事务 restart，系统有前进保证（forward progress）。

【并行机制解说】

对应概念：pessimistic（概念 8）与 optimistic（概念 9）检测、contention manager（概念 10）。幻灯片给出的权衡表：
- 悲观：好——冲突发现早（少撤销无用工作、部分 abort 变成 stall）；坏——无前进保证、某些 case 反而更多 abort、每次 load/store 都要检查（细粒度通信）、检测在关键路径上。
- 乐观：好——前进保证、批量（bulk）通信与批量冲突检测（提交时一次检查）；坏——冲突发现晚、仍有公平性问题（总是后提交者吃亏）。
幻灯片在悲观 Case 4 的注释：图示假设”激进（aggressive）的 contention manager：写者赢”，即谁先写谁占上风，其他事务 abort——这解释了为什么 Case 4 会反复 restart。
性能预告：幻灯片给出”locks vs. transactions”对比图：在 balanced tree 与 HashMap 两个基准上，TCC（Stanford 的硬件事务内存系统，第 18 讲详述）不仅超过 coarse locks，也优于 fine locks——这支撑了”事务常常达到细粒度锁的性能”这一承诺。但注意这是理想化结果，真实收益取决于冲突率（见第四节陷阱 4）。

示例 5：HTM 风格伪代码预览——`xbegin`/`xend`（伪汇编）

; 硬件事务内存（HTM）风格的 begin/end 伪代码（第 18 讲详述）
    xbegin  fallback       ; 开始事务；若 abort，跳转到 fallback 地址执行
    ; ---- 事务体：普通 load/store 即可 ----
    ld   R1, [A]
    ld   R2, [B]
    st   [C], 5            ; 写入暂存（硬件在 cache 里维护写集）
    xend                    ; 提交：所有写一次性生效
    ret
fallback:
    ; abort 路径：例如退化为自旋锁保护的重试路径（Intel RTM 的典型做法）
    call  acquire_spinlock
    ...                    ; 用锁重做事务体
    call  release_spinlock
    ret

【代码做了什么？】

xbegin 让硬件开始一个事务（保存寄存器检查点）；事务体内的普通 load/store 被硬件记录到读集/写集；xend 提交。若发生冲突（或其他原因），硬件跳转到 fallback。
本讲只做”预告”，细节在第 18 讲（HTM 的 cache 位元、coherence 冲突检测、Intel Haswell RTM 的 xbegin/xend/xabort）。

【并行机制解说】

对应概念：memory transaction（概念 1）+ 乐观并发（概念 4）。事务把”同步”从软件抬进硬件：程序员只需写普通代码 + 声明边界，硬件通过 cache coherence 协议自动检测冲突、自动回滚。
幻灯片在讲完 deposit 的锁版本后专门设了一个 self-check：atomic { } ≠ lock() + unlock()——前者是声明，后者是底层原语；锁能实现原子块，但锁还能做原子性之外的事（如示例 3 的握手等待），所以并非所有锁都能被原子块替换。

三、关键要点

事务 = 原子 + 隔离 + 可串行化：提交时所有写一次生效；提交前无人可见；整体呈现某个串行提交顺序（但顺序本身不保证）。”对一个地址维护的性质”被推广到”对一组读写”。
atomic 是声明，lock 是原语：atomic { } 不规定实现；锁可以用于实现原子块，也可以用于原子性之外的目的（等待/握手/排队），因此不能把所有锁换成 atomic；而错误地把一个逻辑原子序列拆成两个 atomic 块会造成 atomicity violation。
事务的目标是”鱼与熊掌兼得”：像粗粒度锁一样好写（声明式），像细粒度锁一样快（自动读-读并发、细粒度并发、性能可移植性），外加失败原子性与可组合性。
实现的两大设计轴：数据版本策略（eager/undo-log vs lazy/write-buffer）× 冲突检测策略（悲观/每次访存检查 vs 乐观/提交时检查）；再叠加检测粒度，就构成 TM 设计空间。
乐观检测有前进保证，悲观检测发现早：悲观把部分 abort 变成 stall 但可能 livelock（需要 contention manager）；乐观”提交方优先”，牺牲公平性换取 forward progress。

四、常见陷阱与注意事项

以为 atomic 就是”自动加锁”：语义上它只是声明原子性；系统可以完全不互斥（乐观并发下两个无冲突事务并行执行）。同时要记住锁能做 atomic 做不了的事（如轮询等待 flag），”全换成 atomic”会写出错误程序（幻灯片 flagA/flagB 握手例子）。
把原子块切碎：本该一个原子序列被程序员误拆成两个 atomic 块（如”ptr = A“与”B = ptr->field“分开），另一个线程在中间把 ptr 置 NULL——atomicity violation。atomic 消除 data race，但不消除程序员造成的原子性错误。
以为事务内没有冲突就万事大吉：事务的正确性取决于 commit 时能否串行化；事务里的读必须是”一致的快照”——若事务读到了别人未提交的写，检测机制必须能抓住它（这正是 read set 验证的意义，第 18 讲展开）。
用锁的思维去度量事务性能：事务在无冲突时开销很低（乐观），但冲突率升高时 abort 重试会带来放大效应；性能好不好取决于工作负载与 atomic 的实现（幻灯片在事务化 HashMap 处原话：performance and scalability depend on the workload and implementation）。
忽略”提交顺序不保证”：serializability 只要求存在某个串行顺序，不代表按时间先后提交；依赖特定提交顺序（比如”先到先得”）的程序逻辑是不可移植的。

五、思考题（带答案）

Q1：为什么说”用锁实现原子块”可行，但”把锁替换成原子块”不可行？请各举一例。 A1：可行方向：deposit 的锁版本与 atomic 版本语义等价——锁是实现原子性的手段之一，系统完全可以用锁来落实 atomic { }。不可行方向：生产者-消费者/线程握手场景，如线程 1 在锁内 flagA = true; while (flagB == 0); 等待线程 2 置位 flagB——原子块提供的是”原子+隔离”，不提供等待/阻塞语义，替换后语义就变了；这类同步只能由锁等低层原语完成。

Q2：悲观检测的 Case 4（两个事务反复写同一地址、互相 abort）如何避免 livelock？乐观检测为什么天然不存在这个 Case？ A2：悲观检测需要 contention manager 仲裁：例如随机退避（abort 后随机延迟再试）、优先级/年龄策略（老事务优先）、写者优先等，打破”双方同时 abort 又同时重试”的同步节奏。乐观检测天然避免：因为冲突只在 commit 时裁决且提交方优先——任何时刻至少有一个事务（先提交的那个）能成功完成，其余 abort 后重试，因此系统有前进保证（forward progress）；它付出的代价是公平性（晚提交者可能被反复 abort）。

Q3：给定两个并发事务：T1 读 x、写 y；T2 读 y、写 x。请问它们是否冲突？若在一个乐观检测系统里，可能发生什么？ A3：冲突：T1 写了 y 而 T2 读了 y（R-W 冲突，T2 读到了 T1 未提交的 y），T2 写了 x 而 T1 读了 x（R-W 冲突）。若两个都提交，读集/写集验证会失败。在乐观检测下，先到达 commit 的事务（比如 T1）成功提交；后提交的 T2 在验证时发现其读集（y）被 T1 写过、或写集（x）与 T1 的读集冲突而被 abort、重执行——重执行后读到 T1 的提交值，两个事务最终呈现 T1→T2 的串行顺序。

Share on

Bluesky Facebook LinkedIn Mastodon X (formerly Twitter)

Runguo Li