Lecture 16: Fine-Grained Synchronization, Lock-Free Programming

目录 · ← l15 · l17 →

Lecture 16: Fine-Grained Synchronization, Lock-Free Programming

1. 章节标题与概述

Lecture 16: Fine-Grained Synchronization, Lock-Free Programming（细粒度同步与无锁编程）

• 本讲核心问题：锁已经把并行程序写对了，但”一把大锁”把并行性又还回去了；那么能不能把”锁”拆细，或者干脆不要锁？ 上一讲（Implementing Synchronization）解决了”如何正确地实现一个锁”（原子原语、自旋 vs 阻塞、test-and-set/ticket lock 等）；本讲把问题从锁的实现推进到锁的使用与锁的替代：①细粒度同步（fine-grained synchronization）——把一把保护整个数据结构的锁，拆成”每节点一把锁”，让对不同数据区域的操作真正并行（链表 hand-over-hand 遍历）；②无锁编程（lock-free programming）——用 compare-and-swap（CAS，比较并交换）这类乐观并发（optimistic concurrency）原语，让线程在不持有任何锁的情况下完成对共享数据结构的修改，靠”检测到冲突就重试”来保证正确性。贯穿全讲的一条主线是：粒度（granularity）与开销（overhead）之间的权衡——细粒度降低争用却抬高单次操作成本，无锁消除锁的阻塞风险却引入 ABA、内存回收、CAS 重试等新问题。

• 涉及的主要硬件/软件机制：硬件侧是原子读-改-写指令（atomic read-modify-write, RMW）及其在缓存一致性协议上的落地——x86 的 lock 前缀（缓存中保留该行直到操作完成；总线上则持有总线；其它设计上可能对请求该行的其它请求回 NACK）、cmpxchg/cmpxchg8b/cmpxchg16b、ARM 的 LDREX/STREX（load-linked / store-conditional，LL/SC）、CUDA 的 atomicCAS/atomicAdd/atomicExch 等；以及由 MSI 一致性协议决定的”缓存行所有权在核间迁移”这一真实成本来源。软件侧是 GCC 内建原子函数（__sync_fetch_and_add 等）、C++11 std::atomic<T> 及其内存序（memory order）语义、以及建立在这些原语之上的数据结构设计：细粒度锁链表、单生产者单消费者（SPSC）队列、无锁栈、无锁链表，以及 ABA 问题的版本号（counter）解法、双字 CAS、hazard pointer（危险指针）内存回收方案。

• 在并行计算知识体系中的角色：本讲位于”同步”主题的收尾处，是从”硬件提供的原子性”走向”软件可用的并发数据结构”的桥梁。它把前面几讲的三条线索拧在一起：缓存一致性（CS149 supplement 出现的 MSI 状态机解释了为什么一个 lock xchg 会引发一次总线/目录事务）、同步原语（上一讲实现的锁在这里被当作”被批判的对象”）、性能模型（work-span、Amdahl、带宽/延迟）在本讲被用来判断”到底该用哪种粒度”。它是后续 Transactional Memory（事务内存） 的直接动机——正如讲义所指出的，”CAS 在无锁实现中的作用是判断’在我操作期间有没有别的线程改过数据结构’“，而事务内存把这种”乐观 + 可中止（abort）”的机制一般化、硬件化；它也是后续在真实系统里写并发容器（Java 的 ConcurrentSkipListMap、数据库与 Web 服务器的队列）时必须具备的判断力。

• 配套材料：

  • CMU 15-418/618 本讲讲义：已公开（可公开下载）。 文件为 17_lockfree.pdf（对应仓库路径 lectures/17_lockfree.pdf，40 页），位于公开目录 https://www.cs.cmu.edu/~418/lectures/ 之下。注意两点：①Fall 2026 的讲次编号是 Lecture 16（日程日期 Oct 2，标题 “Fine-Grained Synchronization, Lock-Free Programming”），而该 PDF 的文件名与首页沿用了历史学期的编号（首页写有 “Lecture 17”、学期写有 “Fall 2025”），这是讲义沿用的正常现象，不视为错误；②在 Fall 2026 的日程表 https://www.cs.cmu.edu/~418/schedule.html 中，本讲那一行的 slides/video 链接被 HTML 注释隐藏（注释原文说明 “slides/video from a previous offering; uncomment when posted for Fall 2026”），但 PDF 本体确实存在于公开目录中、可直接下载。
  • 已公开的姊妹课程（Stanford CS149）讲义抽取文本：已公开。 cs149_supp/finegrainedsync.txt（Stanford CS149 Fall 2025 Lecture 16 “Implementing Locks, Fine-Grained Synchronization, and (a short intro to) Lock-Free Programming”，66 页）。它是本讲内容最完整的公开文本来源：前半部分给出死锁/活锁/饥饿的术语体系与死锁四条件、MSI 状态迁移图、test-and-set 锁与其一致性流量、test-and-test-and-set 锁、ticket lock、用 CAS 构造锁、LL/SC，后半部分与 CMU 讲义高度重合（细粒度锁链表、SPSC 队列、无锁栈、ABA、hazard pointer、无锁链表、Hunt 2011 性能对比）。
  • 本笔记的事实基础：CMU extracted/17_lockfree.txt（40 页全文抽取）+ cs149_supp/finegrainedsync.txt（66 页全文抽取）。所有代码骨架、术语、结论均出自这两份文本；两份文本中未给出具体坐标数值的图表（如 Hunt 2011 的归一化运行时间图、Culler/Singh/Gupta 的锁竞争时间曲线）本笔记只沿用其定性结论与坐标轴含义，不虚构数值；本笔记中出现的数值算例均显式标注为”按给定假设推导”，不冒充讲义原文数据。
  • 未发布/需登录：Fall 2026 本讲的录像（YouTube/Panopto 链接）在日程表中同样被注释隐藏，属未发布；Ed 讨论区、Autolab、Canvas 均需登录。历史学期位于 /afs/cs/academic/class/15418-*/public/ 之下的若干讲义（Performance Analysis/Profiling、Transactional Memory、AI in System Design 等）需要 CMU 登录，属未公开。
  • 课程语境：Fall 2026 授课教师为 Brian Railing 与 Dimitrios Skarlatos；课程由 Kayvon Fatahalian 创建。本讲的前一讲是 Lecture 15 “Implementing Synchronization”（Sep 30，对应公开 PDF 16_synchronization.pdf），下一讲是 Lecture 17 “Transactional Memory”（Oct 5，Fall 2026 尚未发布讲义）。

2. 核心概念与硬件/软件架构图解

2.1 词汇地基：deadlock（死锁）、livelock（活锁）、starvation（饥饿）

定义与目的：在使用锁与无锁算法之前，必须先分清三种”不前进”的失败模式。讲义（CS149 supplement）给出的定义是：

• Deadlock（死锁）：系统中存在尚未完成的操作，但没有任何操作能取得进展。当每个操作都已持有另一个操作需要的共享资源时就会发生；除非某个操作主动让出资源（”倒车”），否则谁都动不了。死锁是正确性问题。
• Livelock（活锁）：系统正在执行大量操作，但没有任何线程取得有意义的进展。典型计算机系统例子是”操作不断中止并重试”——这恰好是无锁算法 CAS 循环在极端争用下的失效模式：所有人都在跑，没人到终点。
• Starvation（饥饿）：系统整体在前进，但某些进程完全得不到进展。讲义明确指出饥饿”通常不是永久状态”，本质上是公平性（fairness）问题，而不是正确性问题。

直观解释（”它是什么？”）：把共享数据结构的并发访问想象成一条只有一车宽的山路会车。

• 死锁 = 四辆车在十字路口互不相让：每个司机都占据了别人必须经过的那一小段路，并且都在等对方先退。这就是”死锁会发生，而且在线性链表的锁顺序上每天都在发生”的现实版。
• 活锁 = 两个人在狭窄走廊里左右闪避：两人都在不停地移动（CPU 100%），但谁也没能通过走廊（没有操作完成）。CAS 重试循环在极高争用下就是这一幕。
• 饥饿 = 主干道车流不断，支路口的车永远等不到空档：整体交通在前进（系统吞吐正常），但那辆支路车永远插不进去。这正是非公平锁（test-and-set 锁）的后果——讲义明确说它 “no provisions for fairness”。

死锁的四个必要条件（讲义原文给出，可用于代码审查）：

关键教学点：第 4 条给出了上一讲那个 hand-over-hand 链表代码”立即可以看出无死锁”的理由——所有线程都严格按 head→tail 的地址顺序获取锁，因此资源依赖图不可能有环。这也是工程中”锁序（lock ordering）”这一惯例的由来。

2.2 为什么”原子”在真实机器上是一件昂贵的事：从 MSI 到 lock 前缀

定义与目的：本讲所有算法都建立在”原子读-改-写”之上，而机器实现它的方式决定了算法的性能。讲义给出的机制描述是：

• x86 lock 前缀：如果内存位置已在缓存中，缓存会保留该行（保持独占）直到操作完成；如果不在缓存中，在总线上使用 lock 信号并占住总线直到操作完成；在其它设计上，处理器（很可能是）对任何请求该缓存行的请求回 NACK，直到操作完成。
• 附带的重要约束：操作必须作用于互不重叠的地址。
• CS149 supplement 补充了 lock cmpxchg 的精确语义：if (dst == EAX) { ZF = 1; dst = src; } else { ZF = 0; EAX = dst; }，其中 lock 前缀指定该操作原子。
• LL/SC（load-linked / store-conditional）：与 CAS 这种”单条原子指令”不同，它是一对配套指令——load_linked(x) 读地址，store_conditional(x, value) 仅当”自对应的 LL 以来没有任何处理器写过 x”时才写入。ARM 对应指令是 LDREX / STREX。它的实现方式正是”在缓存行上留下标记/监视位”，任何对该行的外部写都会清掉该标记。

直观解释（”它是什么？”）：把缓存行想象成一根只有一个人能举着的接力棒。读（BusRd）是”把棒借来抄一遍”，可以多人同时持有副本（Shared）；写/原子 RMW（BusRdX，read-for-ownership）是”把棒抢过来，并且要求所有人把手上的副本撕掉”。所谓”原子操作很贵”，贵的不是运算，而是抢棒过程中所有其它副本被作废，且此后每一个想读的人都必须重新排队。

图解 1：MSI 状态机与”原子操作如何变成一致性事务”

  A / B :  观测到动作 A 时执行动作 B
  PrRd = 本地读      PrWr = 本地写      flush = 把脏行写回

                        PrRd / BusRd
             +----------------------------------+
             |                                  v
        +---------+   PrWr / BusRdX       +---------+
        |    I    | --------------------> |    S    |
        | Invalid |                       | Shared  |
        +---------+ <-------------------- +---------+
             ^            BusRdX / --         |
             |                                |  PrWr / BusRdX
             |   BusRdX / flush               v
             |                          +---------+
             +------------------------- |    M    |
                        BusRdX / flush  |Modified |
                                        +---------+
                                             |
                                             |  BusRd / flush   (远端读：写回并降级)
                                             +----------------> S

  远端事务对 S 的影响：BusRd / --  =>  仍是 S（多一个共享者）
                        BusRdX / -- =>  I

MSI 状态迁移表（每条边都来自讲义状态图）：

关键操作与性能特征：一次 lock cmpxchg（或 atomicCAS）在无争用且行已独占时只需几个周期（命中 L1 并保持独占）；一旦行不在本地缓存，就退化为一次所有权获取（RFO），代价是：

• 延迟（latency）：同一 socket 内 L3 命中约 30–50 ns 量级，跨 socket / 远端 NUMA 约 100–200 ns 量级；
• 带宽/流量（traffic）：每次 RMW 都会作废所有其它副本，所以”有多少个自旋者在等这把锁”直接变成”每次锁交接要产生多少一致性事务”——这正是下一小节要量化的核心；
• 吞吐量（throughput）：同一缓存行的原子操作在本机器上被完全串行化，即该行的最大交接速率为 1 / 交接延迟，与核数无关。

图解 2：test-and-set 锁的一致性流量时间线（讲义 CS149 的核心图之一）

 时间 ──────────────────────────────────────────────────────────────────────>

 P1 (持锁)   [持有锁，做临界区]                                         [再次 T&S]
                │
                │  断言：P1 持有锁期间，它在本地缓存里独占该行
                v
 P2         T&S ──> BusRdX ──> 拿到行(独占) ──> 试图写入(1) => 失败
            T&S ──> BusRdX ──> 拿到行(独占) ──> 试图写入(1) => 失败
            T&S ──> BusRdX ──> 拿到行(独占) ──> 试图写入(1) => 失败   (又作废了 P1 的
                                                                     锁行副本!)
 P3         T&S ──> BusRdX ──> 拿到行(独占) ──> 试图写入(1) => 失败
                              ...
 结果：每一次 T&S 尝试 = 一次 BusRdX + 一次"作废其它所有人"的失效广播
       => 每完成一次"测试"就制造 O(P) 条一致性事务，且把持锁者 P1 的缓存行踢掉
 解锁时：P1 必须先把总线权限拿回来，才能把 0 写回去（"lock holder must wait to
         acquire bus to release"，讲义原话）=> 释放本身也被拖慢

test-and-test-and-set 的改进与其流量模型（讲义明确给出）：

 P2/P3 的等待循环变成：  while (*lock != 0);        <-- 本地缓存里的普通读（S 态，命中）
                         if (test_and_set(lock) == 0) return;
 于是：等待期间几乎零流量（本地 S 态反复读）；
       锁释放时，所有等待者各收到一次失效（Invalidate）
       => "One invalidation, per waiting processor, per lock release (O(P) invalidations)"
       => "This is O(P^2) interconnect traffic if all processors have the lock cached"
对比：test-and-set 锁 "generated one invalidation per waiting processor per test"
      —— 即每次测试就是 O(P)，而测试次数随 P 增长，总量是 O(P^2) 甚至更高

2.3 锁的实现谱系：从 T&S 到 ticket lock 到 LL/SC

定义与目的：讲义（CS149 supplement 第 17–31 页）系统地给出”如何用原子原语造一把锁”，并给出评价锁的五条理想特性：低延迟、低互连流量、可扩展性、低存储开销、公平性（理想情形是”按请求顺序获得锁”）。

五种锁实现的对比表（每列的定性结论均出自讲义原文或由其结论直接推出）：

注意讲义对 ticket lock 的精确表述：”No atomic operation needed to acquire the lock (only a read) —— Result: only one invalidation per lock release (O(P) interconnect traffic)”。也就是说，取号（atomic_increment）是原子操作，但真正的等待只是读 now_serving；相比之下 TTS 在每次释放都会引发”所有等待者重新读一遍”的流量。这就是票号锁比 TTS 更可扩展的根本原因。

用 CAS 构造其它原子操作（讲义留给学生的练习，是理解 CAS 循环的入口）：

// 讲义原题：如何用 atomicCAS 构造 atomic_max / atomic_min / atomic_increment / lock
int atomicCAS(int* addr, int compare, int val) {   // 原子地执行下面的逻辑
   int old = *addr;
   *addr = (old == compare) ? val : old;
   return old;
}
void atomic_max(int* addr, int x) {                // 循环 CAS（CAS loop / optimistic retry）
   int old = *addr;
   int new = max(old, x);
   while (atomicCAS(addr, old, new) != old) {      // 别人改过 => CAS 失败 => 重读重算
     old = *addr;
     new = max(old, x);
   }
}
void lock_cas(int* l)   { while (atomicCAS(l, 0, 1) == 1); }
void unlock_cas(int* l) { *l = 0; }                // 讲义给出的"可能更高效"的争用版本：
void lock_cas_cheap(int* l) {                      // while(1){ while(*l==1); if(CAS(l,0,1)==0) return; }
   while (1) { while (*l == 1); if (atomicCAS(l, 0, 1) == 0) return; }
}

直观解释（”它是什么？”）：把 CAS 想象成赌场里”把筹码换回现金”时的对账员。

• 你要把桌上一叠筹码（当前值 old）换成新的一叠（new）。对账员在你递上去的瞬间核对：”我记录的还是不是 old？”
• 是 → 换成功，你走人（CAS 返回 old）。
• 不是 → 说明别人在你算数的过程中动过这叠筹码，你刚才算的 new 已经作废。对账员把最新数字告诉你（CAS 返回真实当前值），你重新算一遍再来。这就是乐观并发：先假设不会有人打扰，被打扰就重试。

CUDA / GCC / C++11 三套原子原语的对应关系（讲义两张表合并）：

C++11 std::atomic<T> 的语义要点（讲义原文）：

• 为整个对象提供原子的读、写、读-改-写；若 T 是基本类型，原子性可以由处理器原子指令高效实现，否则（可能）由 mutex 实现。
• 为原子操作前后的操作提供内存序（memory ordering）语义；默认是顺序一致（sequential consistency），更多细节见 std::memory_order。
• bool b = i.is_lock_free(); 返回”原子性的实现是否无锁”——注意这句话的对偶含义：std::atomic 不等于无锁，用错大小/类型时它可能内部加锁。

atomic<int> i;
i++;                                   // 原子自增
int a = i;                             // 原子读
i.compare_exchange_strong(a, 10);      // 若 i 当前等于 a，则置为 10
bool b = i.is_lock_free();             // 实现是否 lock-free

关键操作与性能特征：原子 RMW 的”价格标签”由三件事决定——①行是否已在本地独占（命中则 ~10 周期级；否则一次 RFO，几十到几百 ns）；②有多少竞争者（决定每秒发生多少次所有权迁移）；③内存序（seq_cst 在 x86 上需要带 lock 前缀的 RMW 或 mfence，而 relaxed/acquire/release 在 x86 上通常只是编译屏障 + 普通访存，代价低一个数量级——这是”错误使用内存序”之所以是常见陷阱的原因，要么太弱导致正确性错误，要么太强导致性能损失）。

2.4 从”一把大锁”到”每节点一把锁”：粒度谱

定义与目的：讲义首先用排序链表说明为什么需要细粒度锁。数据结构通常大于一个内存位置（”Data structures are often larger than a single memory location”），因此必须回答”整个数据结构如何被保护”。

图解 3：三种粒度的软件执行模型（同一段 insert 代码在三种锁策略下的并发形态）

【粗粒度：每结构一把锁】            【细粒度 hand-over-hand：每节点一把锁】

 head->[3]->[5]->[10]->[11]->[18]    head->[3]->[5]->[10]->[11]->[18]
        |                                    Lt   Lt    Lt    Lt    Lt
        +-- lock(list->lock) 一把锁           (每节点一个 Lock 字段)
            T0: ████████████████████        T0: L(3) L(5) ... L(11) ... 逐个"放手"
            T1: ................... 等待     T1:      L(5) L(10) ...     可以跟在后面
            => 完全串行                     => 形成流水线：T1 紧跟在 T0 身后

【无锁：CAS 乐观重试】

 head->[3]->[5]->[10]->[11]->[18]   head(atomic<Node*>)
            T0: 读 head、读 next、算好 n->next、CAS(prev->next, cur, n)
            T1: 同时做同样的事 —— 谁先 CAS 成功谁赢，输的那个重读重试
            => 不持有任何锁，但共享同一"提交点"（此处是 prev->next）

直观解释（”它是什么？”）：

• 粗粒度锁 = 独木桥：安全、简单，但一次只能过一个人。讲义的评价一针见血：”Good: It is relatively simple to implement correct mutual exclusion；Bad: Operations on the data structure are serialized, may limit parallel application performance“。
• hand-over-hand 细粒度锁 = 攀岩时的”三点固定”：攀岩者每次只移动一只手或一只脚，始终抓住岩点（锁），沿着岩壁（链表）前进；两个人可以在同一面岩壁上相隔几个岩点同时攀爬，但谁都必须在抓住下一个岩点之后才能放开前一个——这就是”hand-over-hand”（交替手）这个名字的来源。
• 无锁 CAS = 抢座位游戏：所有人都盯着同一个空位（prev->next），裁判（硬件原子性）裁定谁坐下；没抢到的人退回去重新观察现场再抢一次。没有人”占着”座位不放，所以也就不存在”某人被换出导致全场停摆”。

hand-over-hand 的正确性不变量（本讲最值得记住的一条设计规约）：

   不变量：持有节点 P 的锁  ==>  保证 P->next 不会被别人修改，
                                因而保证 P->next 指向的那个节点的"身份"稳定。
   推论 1：读取 cur = cur->next 时，只要还持有 prev 的锁，就是安全的
           （否则 cur 可能已被别人摘链并 delete，形成悬空指针）。
   推论 2：加锁顺序必须严格沿 head -> tail 方向
           => 资源依赖图无环 => 无死锁（死锁第 4 条件的直接应用）。
   推论 3：任何时刻都要持有 >= 1 把锁；"先锁下一个，再放前一个"
           => 不会出现"手上没有任何锁"的窗口，避免指针失效。

讲义的”给学生的问题”及其答案：讲义在给出 fine-grained insert() 后提问——”insert() 的实现还有进一步改进的余地，是什么？“答案是：insert 只修改 prev->next 这一个指针，因此不需要在整条遍历路径上加锁。可以先不加锁地做只读遍历（纯读，无一致性流量）找到候选位置 prev/cur，然后只锁 prev，并重新验证 prev->next == cur；若验证失败（被别人改过）就放弃本次结果、回到遍历重新搜索。这把”每步两次原子 RMW”降为”整次操作一次原子 RMW”，同时保留了大部分并发度——注意这个结构与本讲后半部分的 CAS 循环在形式上完全一致，它正是”细粒度锁”通向”无锁”的那一步。

细粒度锁的代价（讲义原文列出，务必逐条记住）：

讲义的核心提示句：”What is a middle-ground solution that trades off some parallelism for reduced overhead? (hint: similar issue to selection of task granularity)”——同步粒度与任务粒度是同一个问题的两面：粒度过细，开销（这里是原子操作与缓存行迁移）吃掉并行收益；粒度过粗，并行度不足。判断依据永远是 work-span / Amdahl 的定量分析，而不是”越细越好”的直觉。

2.5 “阻塞 / 无锁 / 无等待”：进度保证的层次

定义与目的：讲义的第二个主题是无锁（lock-free），它首先给出严格的定性判据：

• Blocking algorithm / data structure（阻塞算法）：允许一个线程无限期地阻止其它线程完成对共享数据结构的操作。例子：线程 0 在我们的链表某节点上获取了锁，然后被 OS 换出、崩溃、或只是很慢（缺页），于是任何其它线程都无法完成操作——尽管线程 0 并没有在积极修改数据。
• 关键推论（讲义用粗体强调）：”An algorithm that uses locks is blocking, regardless of whether the lock implementation uses spinning or pre-emption“——自旋锁也是阻塞算法。这是一个极容易被误解的点：自旋看起来”没有让出 CPU”，但它依然制造了”一个线程可以卡住所有人”的可能性。
• Lock-free（无锁）：非阻塞算法如果保证某个线程（不指定哪个）必定取得进展，即”systemwide progress（系统级进展）“，就称为 lock-free。等价说法：不可能通过”在某个不巧的时刻抢占某个线程”来阻止系统其余部分取得进展。
• 注意讲义的补充：”this definition does not prevent starvation of any one thread”——lock-free 允许单个线程饥饿。这是 lock-free 与 wait-free 的分界。

进度保证层次表（lock-free 的定义来自讲义；其余为无锁编程的成熟公开知识，用于把讲义定义放到完整坐标系中）：

直观解释（”它是什么？”）：

• Blocking = 只有一个售票窗口，且窗口里的售票员可能突然去上厕所：队伍里所有人一起等，而且不知道要等多久。
• Lock-free = 自助售票机，大家都能按：即使某人按到一半走神（被换出），其他人照样能在同一台机器上把票买走（重试即可），系统总有票卖出去；但某个特别倒霉的人可能反复被人抢先、永远买不到（饥饿）——不过这不是系统性问题。
• Wait-free = 每人一个专属窗口：没人需要等别人，代价是窗口（硬件/算法复杂度）非常贵。

关键操作与性能特征：注意这里的”进度保证”与”性能”是正交的两件事。讲义在总结里明确写：”Note: a lock-free design does not eliminate contention — Compare-and-swap can fail under heavy contention, requiring spins.”（第 4 节会给这一步定量分析。）

2.6 无锁的软件执行模型：CAS 循环（乐观并发）

定义与目的：无锁数据结构的基本执行模式是”读-算-CAS-重试“：读取待修改位置的当前值 → 基于它计算新值 → 用 CAS 尝试”仅当值未变”时提交 → 失败则从头再来。核心思想（讲义对无锁栈的说明）：”as long as no other thread has modified the stack, a thread’s modification can proceed“（只要没有别的线程改过，本线程的修改就能进行）。

图解 4：CAS 循环的状态机与时间线

                           +------------------------------------+
                           |                                    |
                           v                                    |
   [READ]  读当前状态  +---------+  计算结果  +---------+  提交 CAS  +---------+
   快照    old = *p   |  SNAP   | ---------> | COMPUTE | ---------> | COMMIT  |
                           ^                          |             +---------+
                           |                          |               |      |
                     CAS 失败: 世界变了               |               | 成功 | 失败
                     (返回值 != old)                  |               |      |
                           |                          |               v      |
                           +--------------------------+----------  [DONE]     |
                                                                             |
        失败时的两种语义：                                                    |
        (a) 重读并重算（本讲所有代码的做法） <-------------------------------+
        (b) 放弃本次操作、向上层返回"失败"（如队列满/空时返回 false）

 时间 ─────────────────────────────────────────────────────────────────────>

 T0:  |--read A--|--compute--|--CAS(top:A->B) SUCCESS--|  DONE
 T1:       |--read A--|--compute--|--CAS(top:A->B) FAIL(当前是 B)--|
           |<----------------- 重读、重算、重试 ----------------->|--CAS(top:B->C) SUCCESS--|

 失败的原因不是"T0 抢了 T1 的座位"，而是"T1 基于的旧快照已经过期"。
 => CAS 循环把并发控制从"提前加锁"改成"提交时校验"，因此：
    优点：无锁持有期、无死锁、无优先级反转、持锁者被抢占不影响他人
    代价：失败重试是纯粹的浪费（Wasted work），且失败率随争用者数量上升

关键操作与性能特征：

• 成功路径（fast path）：一次原子读 + 一次 CAS，两者若命中本地独占行，代价与普通访存同量级（~10–20 周期）。
• 失败路径（slow path）：失败的 CAS 本身就是一次完整的 RFO——它已经把缓存行抢到本地了，但因为是”值不匹配”而没有完成语义上的提交。因此失败比成功还浪费：它既付出了行迁移的全部代价，又没有推进任何状态，还额外污染了其它人的副本。
• 活性：CAS 循环天然是 lock-free（每次行迁移必定有一个线程成功），但不是 wait-free（倒霉线程可以永远失败）。
• 一个必须记住的语义细节：compare_exchange 返回旧值，因此判断”我是否成功”的方法是 CAS(p, old, new) == old；而 atomicCAS(addr, compare, val) 返回旧值、只有”旧值 == compare”时才写入——两种接口的返回值语义不同，写代码时要看清是哪一种（讲义代码使用的是前者语义）。

2.7 单生产者-单消费者（SPSC）队列：无锁设计的”温柔区”

定义与目的：当访问者只有一个生产者 + 一个消费者时，可以有完全不需要同步等待的无锁队列。讲义给出两个版本，并反复强调前提：”Assume a sequentially consistent memory system for now (or the presence of appropriate memory fences, or C++11 atomic<>)“——即这些代码要在弱一致性硬件上正确，必须补上内存栅栏或使用 atomic<>。

版本 A：有界队列（bounded queue）

struct Queue { int data[N]; int head;  /* 队首 */ int tail; /* 下一个空位 */ };
push: 若 tail == MOD_N(head - 1) 表示满 -> 返回 false
      q->data[q->tail] = value;  q->tail = MOD_N(q->tail + 1);  返回 true
pop : 若 head != tail（非空）
      *value = q->data[q->head]; q->head = MOD_N(q->head + 1);  返回 true
      否则返回 false

两个线程是同一变量空间的两个”所有者”：生产者只写 tail 和 data[tail] 槽位，消费者只写 head 并读 data[head] 槽位。没有人写别人拥有的变量，因此不需要任何原子 RMW——只需要保证”我写的 tail 你能看见”（release/acquire 语义）。

版本 B：无界队列（unbounded queue）与 reclaim 指针

 tail 指向最后加入的元素；head 指向队首元素之前的那个元素；
 节点的分配与删除都由同一个线程（生产者）执行。
 push:  n = new Node; n->next=NULL; n->value=v;
        q->tail->next = n;  q->tail = q->tail->next;
        while (q->reclaim != q->head) { tmp = q->reclaim; q->reclaim = q->reclaim->next; delete tmp; }
 pop:   if (q->head != q->tail) { *value = q->head->next->value; q->head = q->head->next; return true; }
        return false

图解 5：无界队列的 head / tail / reclaim 演进（对应讲义的那张状态图）

 初始:      head,tail,reclaim -> [dummy]                      队列为空
            ^^^^^^^^^^^^^^^^^^^ 三者指向同一个哑节点

 push 3:    reclaim,head -> [dummy] -> [3] <- tail
 push 10:   reclaim,head -> [dummy] -> [3] -> [10] <- tail

 pop -> 3:  reclaim -> [dummy]     head -> [3]        [10] <- tail
            （head 前进一格：它始终指向"队首元素之前的那个节点"，
              因此队首元素是 head->next = [10]）
            队列内容 = [10]，[dummy] 仍不可回收（reclaim 还指着它）

 pop -> 10: reclaim -> [dummy]   head, tail -> [10]
            队列内容为空（head == tail）

 pop -> false (empty)          消费者不删除任何节点

 push 5:    生产者在这里触发回收循环：
            n=[5]; tail([10])->next = [5]; tail = [5];
            while (reclaim != head) { tmp=reclaim; reclaim=reclaim->next; delete tmp; }
              iter1: reclaim=[dummy] != head=[10] -> delete [dummy]; reclaim=[3]
              iter2: reclaim=[3]     != head=[10] -> delete [3];     reclaim=[10]
              iter3: reclaim=[10] == head=[10] -> 停止
            结果: reclaim, head -> [10] -> [5] <- tail

 关键设计：生产者从不删除 head 及其之后的节点，消费者从不删除任何节点
           => 每个节点只被一个线程 delete，不存在"引用已释放内存"的竞态

关键操作与性能特征：

• 延迟：快路径上没有任何原子 RMW、没有任何自旋，只是一次普通读 + 一次普通写，几乎与单线程数组操作同价。
• 吞吐量：生产者与消费者形成流水线，稳态吞吐由较慢的一方决定（典型的 producer-consumer 瓶颈分析）。
• 回收的滞后性（这一点最容易被忽略）：reclaim 指针是刻意落后于 head 的（正因为落后，才能保证被删的节点确实不可能再被消费者访问），因此内存峰值使用量可能远高于队列的稳态长度；reclaim 的推进是摊销（amortized）的——一次 push 可能一次删除很多节点，导致尾部延迟（tail latency）尖峰。

2.8 无锁栈与 ABA 问题

定义与目的：讲义用”无锁栈”作为第一个多生产者多消费者的无锁数据结构例子。

struct Stack { Node* top; };
push(s, n):  while (1) { old_top = s->top; n->next = old_top;
                         if (CAS(&s->top, old_top, n) == old_top) return; }
pop(s):      while (1) { old_top = s->top; if (!old_top) return NULL;
                         new_top = old_top->next;
                         if (CAS(&s->top, old_top, new_top) == old_top) return old_top; }

与细粒度锁的本质区别（讲义原文）：”In fine-grained locking, the implementation locked a part of a data structure. Here, threads do not hold lock on data structure at all.”

ABA 问题（本讲最著名的陷阱）：CAS 只比较值（这里是地址），而值相同不代表状态没变。讲义的时间线如下：

图解 6：ABA 问题的完整时间线（A/B/C/D 是节点地址，不是节点里存的值）

 初始:                     top -> A -> B -> C

 T0: begin pop()
     (局部变量 old_top = A, new_top = B)          <-- T0 读到了快照 (top==A)
     ---- T0 被抢占 / 变慢 ----

 T1: begin pop()  读到 old_top == A
 T1: complete pop()  返回 A           => top -> B -> C
 T1: 修改节点 A（例如 A->value = 42）
 T1: begin push(A); complete push(A)  => top -> A -> B -> C
 T1: begin push(D); complete push(D)  => top -> D -> A -> B -> C

 T0: 恢复执行，执行 CAS(&top, A, B):
     CAS 比较 top == A ?  成立！（此刻 top 确实是 A） => CAS 成功，把 top 设为 B
 T0: complete pop()  返回 A

 结果:  top -> B -> C
        节点 D 从栈里消失了（丢失），栈结构被破坏！
 注意:  T0 的 CAS 语法上完全正确，错的是"ABA 相等"的语义假设：
        地址 A 回来了，但"A 被 A 引用时的那个"世界已经不存在了。

解法 1：计数器 / 版本号（讲义给出）——给栈再加一个 pop_count，用双字比较并交换（DCAS / doubleword CAS）同时校验 top 与计数：

pop:  loop { pop_count = s->pop_count; top = s->top; if (!top) return NULL;
             new_top = top->next;
             if (double_compare_and_swap(&s->top, top, new_top,
                                        &s->pop_count, pop_count, pop_count+1)) return top; }

解法 2：x86 的”宽 CAS”——讲义专门澄清：x86 的 cmpxchg8b / cmpxchg16b 并不是上面代码需要的通用 DCAS，但只要保证 top 与 pop_count 在内存中连续，就可以用一条 64 位 / 128 位的单条 CAS 指令同时比较两个字段（”compare and exchange eight/sixteen bytes”，可用于两个 32 位 / 两个 64 位值的 CAS）。这个”把要一起校验的字段打包进一个字”的技巧是无锁编程中最常用的工程手段。 解法 3：讲义也指出可以”通过谨慎的节点分配与元素复用策略“解决 ABA——例如节点从不真正释放（用内存池 + 索引 + 打包版本号），地址空间足够大以至于不会回绕。

另一个独立问题：引用已释放内存（referencing freed memory）——即使解决了 ABA，pop 中的 old.top->next 也可能在读取时节点已被别人弹出并 delete，从而访问已释放内存（use-after-free）。讲义给出两个层次的处理：

图解 7：Hazard pointer（危险指针）+ retire list（退休链表）

 每个线程两份私有数据：
   hazard   : 本线程"正在查看，因此不能被别人 delete"的节点指针
   retireList / retireListSize : 本线程已移除、但还不能确定能安全 delete 的节点

 pop 循环:
   1. old.top = s->top
   2. hazard = old.top              <== 【先发布】"我正在用这个节点"
   3. old.top == s->top ?           <== 【再校验】发布后节点没被换掉
   4. new.top = old.top->next
   5. doubleword_CAS(s, old, new)
        成功 -> value = old.top->value; retire(old.top); return value
        失败 -> hazard = NULL; 重试
   6. 后续 push 若成功，则 CAS 完成为止

 retire(ptr):
   push(retireList, ptr); retireListSize++;
   if (retireListSize > THRESHOLD)                    <== 摊销：批量清理
      for each n in retireList:
          if (n 不等于任何线程的 hazard 指针) { 从链表移除 n; delete n; }

 安全性论证：节点 n 从结构中摘除（CAS 成功）之后，任何线程想再获得对 n 的引用，
             都必须先读 head/top 并沿链走；而 n 已不可达 => 只要在"扫描时刻"没有
             任何 hazard == n，就再也没有线程会引用 n（除持有者自己，而持有者正是
             执行 retire 的线程），于是可以安全 delete。

关键操作与性能特征：hazard pointer 把”内存回收”变成一次批量的、读所有线程 hazard 槽位的扫描（O(线程数) 的读，且是只读，不产生一致性流量风暴，因为 hazard 槽位是各线程私有的、被频繁写但几乎不被别人读——反过来，如果 hazard 槽位与高频写字段伪共享，就会付出巨大代价）。THRESHOLD 的选择是经典的时间/空间权衡：太小则扫描频繁（每次 retire 都 O(P) 扫描），太大则内存占用与尾延迟上升。

2.9 无锁链表：插入容易，删除很难

定义与目的：讲义最后给出无锁链表的插入与删除，并用一句话点出复杂度鸿沟——”Supporting lock-free deletion significantly complicates data-structure“。

// 在指定节点之后插入（讲义简化版：假设只有 insert 操作）
void insert_after(List* list, Node* after, int value) {
   Node* n = new Node; n->value = value;
   Node* prev = list->head;
   while (prev->next) {
     if (prev == after) {
       while (1) { Node* old_next = prev->next; n->next = old_next;
                   if (compare_and_swap(&prev->next, old_next, n) == old_next) return; }
     }
     prev = prev->next;
   }
}

与细粒度锁相比的两项收益（讲义原文）：”No overhead of taking locks; No per-node storage overhead“——每走一步不再有两次原子 RMW，也不必给每个节点再加一个指针字段（节点更小 ⇒ 缓存密度更高）。

图解 8：无锁删除的经典难题（B 被删除的同时 E 被插到 B 之后）

   初始:        A -> B -> C -> D

   并发操作:  T0 删除 B（CAS 成功在 A->next 上，把 A->next 指向 C）
              T1 在 B 之后插入 E（CAS 成功在 B->next 上，把 B->next 指向 E）

   结果:        A -> C -> D          (T0 的意图实现)
                     B -> E          (B 已不在链表中，却指向 E！)

   问题:
     - E 实际上"挂"在一个不可达节点上 => 逻辑丢失（E 不在列表里）
     - B 若被回收，E 也随之成为垃圾
     - 若 T0 先删除 B、T1 后 CAS B->next，则 T1 的 CAS 甚至作用在已释放内存上
   讲义给出的进一步阅读:
     - Harris 2001, "A Pragmatic Implementation of Non-blocking Linked-Lists"
     - Fomitchev 2004, "Lock-free linked lists and skip lists"

关键操作与性能特征：无锁链表的插入在低争用下非常快（纯粹的读遍历 + 一次 CAS）；在高争用下，遍历本身依旧要读指针链（受内存延迟支配），而”提交点”集中在被修改的那一个 next 指针上，所以操作的正确性靠单点 CAS，性能上限则由内存延迟与 CAS 失败率共同决定。删除之所以难，本质原因是：一次逻辑删除需要修改两个指针（前驱的 next、后继的链接），而 CAS 只能原子地改一个字——这就是后面 Transactional Memory 要解决的结构性问题。

2.10 现实检验：无锁一定更快吗？

讲义给出的判断（三段式），值得逐字记住：

1. 在”只有你的程序在用这台机器”的场景下（科学计算、图形学、数据分析等课程内的优化场景），写得好的加锁代码可以与无锁代码一样快，甚至更快（”well written code with locks can be as fast (or faster) than lock-free code”），而且通常简单得多。
2. 讲义引用的量化证据是 Hunt 2011, “Characterizing the Performance and Energy Efficiency of Lock-Free Data Structures”：图中纵轴是相对 pthread mutex 运行时间的归一化值（1.0 = 与 pthread mutex 持平，<1 表示更快），横轴是线程数，曲线分为 lf（lock free） 与 fg（fine grained lock） 两组，覆盖 Queue / Linked List / Dequeue 三类结构。（注：讲义抽取文本中不含该图的坐标数值，本笔记不虚构具体倍数。）
3. 但确实存在加锁代码会遭遇”棘手的性能问题”的场景：多道程序（multi-programmed）环境中，线程在临界区内可能缺页、被抢占等，从而产生 priority inversion（优先级反转）、convoying（护航效应）、在临界区内崩溃 等在操作系统课里讨论的问题。这正是数据库、Web 服务器这类”程序里有很多线程、又无法独占机器”的场景需要无锁/非阻塞结构的原因。

讲义的总结四条：

• 用细粒度锁降低共享数据结构操作上的争用（最大化并行度），但细粒度会增加代码复杂度（易错）与执行开销。
• 无锁数据结构是非阻塞方案，用于避免锁的一些开销与陷阱；但实现微妙（在无锁设定下保证正确性本身有自己的开销）。
• 在现代的宽松一致性（relaxed consistency）硬件上，仍需要恰当的内存栅栏（讲义在 SPSC 队列、栈代码处反复标注 “Assume a sequentially consistent memory system for now”）。
• 无锁设计并不能消除争用：重争用下 CAS 会失败，需要自旋重试。

3. 代码示例与性能分析

3.1 示例 1：细粒度（hand-over-hand）锁链表 vs 单一全局锁

代码做什么？：实现同一个有序单链表（支持 insert），提供两种加锁策略：CoarseList（一把 std::mutex 保护整个链表）与 FineList（每节点一把 std::mutex，hand-over-hand 遍历）。主程序用相同的随机操作序列分别跑两种实现，报告吞吐（ops/s）与”整条链表被串行化的比例”。

// 编译: g++ -O3 -std=c++17 -pthread fg_list.cpp -o fg_list
//      （务必用 -O3：-O0 下同步以外的开销会掩盖细粒度锁的真实收益/代价）
// 运行: ./fg_list 8 50000
//      参数 <线程数> <总操作数>。默认值域为 0..4095（链表最多 4096 个节点），
//      使示例能在秒级跑完；若把值域改成 1<<20（链表会长到几十万节点），
//      细粒度版本会因为"每步 2 次原子 RMW × 极长遍历"而慢到不可用 ——
//      这正是 4.3 节要定量说明的那个结论。

#include <cstdio>
#include <cstdlib>
#include <cstdint>
#include <thread>
#include <mutex>
#include <vector>
#include <atomic>
#include <chrono>
#include <random>
#include <algorithm>

// ---------------------------------------------------------------------------
// 方案 A：粗粒度 —— 一把锁保护整个链表
// ---------------------------------------------------------------------------
struct CNode { int value; CNode* next; };

struct CoarseList {
    CNode* head;                 // 哨兵节点（值 = INT_MIN）
    std::mutex m;
    void init() { head = new CNode{INT32_MIN, nullptr}; }
    bool insert(int value) {
        std::lock_guard<std::mutex> g(m);          // 整个遍历 + 插入都在临界区内
        CNode* prev = head;
        CNode* cur  = prev->next;
        while (cur && cur->value < value) { prev = cur; cur = cur->next; }
        if (cur && cur->value == value) return false;   // 去重
        prev->next = new CNode{value, cur};
        return true;
    }
};

// ---------------------------------------------------------------------------
// 方案 B：细粒度 —— 每节点一把锁，hand-over-hand 遍历
//   不变量：持有 prev->m  ==> prev->next 及其指向节点的身份不会被改动
//   锁序：  永远沿 head -> tail 方向加锁 ==> 资源依赖图无环 ==> 无死锁
// ---------------------------------------------------------------------------
struct FNode { int value; FNode* next; std::mutex m; };

struct FineList {
    FNode* head;                  // 哨兵节点，其锁同样遵守不变量
    void init() { head = new FNode{INT32_MIN, nullptr, {}}; }
    bool insert(int value) {
        FNode* n = new FNode{value, nullptr, {}};
        FNode* prev = head;
        prev->m.lock();                      // 从 head 开始，锁序固定
        FNode* cur = prev->next;
        if (cur) cur->m.lock();
        while (cur && cur->value < value) {  // 只要还持有 prev 的锁，读 cur->next 就是安全的
            prev->m.unlock();                // 放开"身后"的锁：hand-over-hand
            prev = cur;
            cur  = cur->next;
            if (cur) cur->m.lock();          // 先锁下一个，再进入下一轮
        }
        bool ok = true;
        if (cur && cur->value == value) {
            ok = false;                      // 已存在
        } else {
            n->next = cur;
            prev->next = n;                  // 只改 prev->next，因此只需持有 prev 的锁
        }
        prev->m.unlock();
        if (cur) cur->m.unlock();
        if (!ok) delete n;
        return ok;
    }
};

// ---------------------------------------------------------------------------
// 驱动：T 个线程各自随机插入 N/T 个值
// ---------------------------------------------------------------------------
template <typename F>
static double run(const char* name, F&& body, int T, int per_thread) {
    std::atomic<bool> go{false};
    std::vector<std::thread> ts;
    auto t0 = std::chrono::steady_clock::now();
    for (int t = 0; t < T; ++t)
        ts.emplace_back([&, t] {
            while (!go.load(std::memory_order_acquire)) {}       // 同时起跑
            std::mt19937 rng(1234 + t);
            std::uniform_int_distribution<int> d(0, (1 << 12) - 1);   // 值域 4096
            for (int i = 0; i < per_thread; ++i) body(d(rng));
        });
    go.store(true, std::memory_order_release);
    for (auto& th : ts) th.join();
    double s = std::chrono::duration<double>(std::chrono::steady_clock::now() - t0).count();
    printf("%-28s T=%-3d  time=%8.3f s   throughput=%10.0f ops/s\n",
           name, T, s, (double)(T * per_thread) / s);
    return (double)(T * per_thread) / s;
}

int main(int argc, char** argv) {
    int T = (argc > 1) ? atoi(argv[1]) : 8;
    int total = (argc > 2) ? atoi(argv[2]) : 50000;
    int per = total / T;

    CoarseList cl; cl.init();
    run("coarse: one global lock", [&](int v) { cl.insert(v); }, T, per);

    FineList fl; fl.init();
    run("fine: hand-over-hand",     [&](int v) { fl.insert(v); }, T, per);
    return 0;
}

【代码做什么？】

1. 两个结构都使用哨兵头节点（值为 INT32_MIN）——这让”在表头之前插入”这一特殊情况消失，insert 中不再需要单独的头部处理分支，也保证 prev 永不为 NULL，从而”每节点一把锁”的方案总能先锁到 prev。
2. CoarseList::insert 在整个遍历 + 插入期间持有唯一一把锁：逻辑简单、绝对安全、但所有线程在一条队列上排队。
3. FineList::insert 的关键循环是 hand-over-hand：prev->m.unlock(); prev = cur; cur = cur->next; if (cur) cur->m.lock();
   • 释放”身后”的锁（prev 变成下一轮的”更后面的那个节点”），使得另一个线程可以从被释放的位置继续前进；
   • 先锁下一个再进入下一轮，因此该线程始终至少持有一把锁，绝不会出现”手上无锁而手上指针可能失效”的窗口；
   • 读取 cur->next 时持有的是 prev 的锁，而 prev->next 由该锁保护，所以 cur 的身份是稳定的（这就是 2.4 节的不变量）。
4. 驱动代码用 go 标志让所有线程同时起跑，否则第一个线程可能在其它线程创建前就跑完，测量结果会严重失真（这是并行基准测试最常见的错误之一）。

【并行机制与性能解说】

设平均每次插入的遍历长度为 L（本示例随机值域约 2^20，随着链表增长 L 上升；稳态下 L ≈ n/2，n 为不同值数量），操作数 M = T × per，节点数为 n。

• Work（总工作量）：
  • 粗粒度：W_coarse = Θ(M·L) 次节点访问 + M 次锁获取（每次是 1 次原子 RMW + 1 次普通写）。
  • 细粒度：W_fine = Θ(M·L) 次节点访问 + Θ(M·L) 次锁获取与释放，即每个遍历步多了 2 次原子 RMW。这是本示例最核心的成本项：L ≈ 2^19/2 ≈ 260 K（当 n 很大时）时，每次插入的原子操作数从 1 次变成约 5×10^5 次，代价高到足以让细粒度版本慢几个数量级。
• Span（关键路径）：单次插入的串行链是”沿链表走 L 步”，每步依赖前一步的 next 读取（依赖链，无法乱序跨越），因此 Span_op = Θ(L) 步；每一步在细粒度版本里是”锁获取 + 读 + 锁释放”，在粗粒度版本里是”读”。整体 Span = Θ(M·L + (锁交接总时长))。
• 并行度 = Work/Span：单次操作内部 Θ(M·L)/Θ(L) = Θ(M) 看起来很高，但这个数字具有误导性：真正的并行度受限于”不同操作能不能同时推进“。在细粒度方案里，两个操作的进度被它们之间的节点锁耦合；L 个线程在链表上形成流水线（pipeline），稳态吞吐上界为

  Throughput_fine <= 1 / t_hop          其中 t_hop ≈ (锁获取 + 释放) ≈ 2 次缓存行交接
  

  而粗粒度方案的吞吐上界是 1 / (t_lock + t_critical)，其中 t_critical 包含整条遍历 —— 从量级上看，细粒度把”每次操作一段长临界区”变成”每一步一小段临界区”，把长临界区拆成流水线，这正是它的价值。

• 瓶颈诊断：
  1. 每步原子操作（本示例的主导瓶颈）：若 t_hop ≈ 40 ns（同 socket L3 命中、无争用），仅锁开销就是 L × 40 ns；若 L = 1000，单次插入 = 40 µs，吞吐上限 25 K ops/s/线程。在长链表上，细粒度锁的 hop 成本是纯遍历成本的 10–100 倍。
  2. 伪共享（false sharing）：FNode 中 value/next/m 同在几十字节内，相邻节点常常落在同一 64 B 缓存行。两个线程锁的是不同节点、却争同一缓存行 ⇒ 完全违背了”细粒度”的初衷，实测可能比粗粒度还慢。工程修正：把锁字段与数据分离（两个平行数组/结构体），或让每把锁独占一个缓存行（alignas(64)），代价是内存占用暴涨。
  3. 负载不均：std::uniform_int_distribution 让插入位置均匀分布，因此越靠表头附近的节点锁越热（所有操作都必须从 head 出发，head 的锁是全局热点）。这个”head 锁串行化”与任务粒度过粗造成的串行化在数学上是同一件事。
  4. 内存延迟：cur->next 是典型的指针追逐（pointer chasing），每步几乎必然 L2/LLC/DRAM 缺失，t_hop 中真正的大头常常是内存延迟而不是原子操作本身。这也是为什么本示例测出来的”吞吐”随链表变长而急剧下降——它是延迟受限（latency-bound）的。

可扩展性上限的结论：细粒度锁不改变单次操作 Θ(L) 的延迟（指针追逐的依赖链无法并行化），它改变的是吞吐——把串行临界区变成流水线。因此在本例这种”值域极宽、链表极长”的设定下，细粒度锁带来的原子操作开销会压过流水线收益；而在”链表较短、操作集中在不同区域”的设定下（工程中的真实场景），细粒度才明显占优。这个结论正是讲义”middle-ground solution”提示的定量依据。

本示例的实际输出（直接观察”细粒度反而更慢”）：

$ ./fg_list            # 默认 T=8，总操作 50000，值域 0..4095
coarse: one global lock      T=8    time=   0.512 s   throughput=     97730 ops/s
fine: hand-over-hand         T=8    time=   4.329 s   throughput=     11551 ops/s

细粒度版本比单把大锁慢 8.5 倍。 这不是代码写错了，而是 2.4 节那张”代价表”的直接后果：链表稳态长度约 4000 个节点（值域 4096），平均遍历 L ≈ 2000 步 ⇒ 每次插入在细粒度版本里要付出 约 4000 次原子 RMW（每步 lock + unlock），而粗粒度版本只付出 1 次锁获取。遍历本身的指针追逐（每步几纳秒，因为整个链表只有约 100 KB、基本常驻 L2）远小于原子操作的开销，所以同步成本完全主导。 这个实测结果也提醒我们注意与 4.3 节数值算例的假设差异：4.3 假设”每次节点访问 90 ns（DRAM 延迟）”，而本例的链表小到能放进 L2，节点访问只要几纳秒——在”遍历很便宜”的情形下，细粒度锁的额外开销占比更大，输得更惨；只有在”遍历很贵（大表、随机分布、频繁缺页）”且”线程访问区域分散”时，细粒度锁拆出的流水线才可能赢回来。 换句话说：是否值得细粒度，取决于”每次操作省下的等待时间”与”每一步多付的原子操作代价”哪个更大——这正是 work-span 与 Amdahl 要算的东西，而不是靠”锁越小越好”的直觉。

3.2 示例 2：无锁栈 —— 用”索引 + 版本号打包”彻底解决 ABA

代码做什么？：实现一个多生产者 / 多消费者的无锁栈。为避免 ABA 与 use-after-free 两个问题，示例采用讲义所述的第三种解法思路：节点来自预分配数组（永不 delete），栈顶指针用一个 64 位字打包 (tag:32 \| index:32)，其中 tag 是版本号（对应讲义代码里的 pop_count），于是一次 64 位 CAS 就能同时校验”栈顶是谁”和”栈自我们读取以来有没有变过”——这正是讲义所说”保证两个字段在内存中连续，用单条宽 CAS 即可”的工程落地。

// 编译: g++ -O3 -std=c++17 -pthread lf_stack.cpp -o lf_stack
// 运行: ./lf_stack 8 2000000          # 8 个线程，总共 200 万次 push + 200 万次 pop

#include <cstdio>
#include <cstdlib>
#include <cstdint>
#include <atomic>
#include <thread>
#include <vector>
#include <chrono>
#include <algorithm>

// ---- 打包格式： [ tag:32 | index:32 ]，index=0xFFFFFFFF 表示空栈 ----
static constexpr uint32_t NIL = 0xFFFFFFFFu;
static inline uint64_t pack(uint32_t tag, uint32_t idx) { return ((uint64_t)tag << 32) | idx; }
static inline uint32_t tag_of(uint64_t v) { return (uint32_t)(v >> 32); }
static inline uint32_t idx_of(uint64_t v) { return (uint32_t)(v & 0xFFFFFFFFu); }

static constexpr uint32_t CAP = 1u << 22;      // 约 419 万个节点槽位（预分配，永不释放）

struct Node { uint32_t next; int value; };     // next 用索引而非指针：可以用一条 CAS 打包

struct LFStack {
    Node*               pool;                  // 节点池（只分配一次）
    std::atomic<uint64_t> head;                // 打包的 (tag, index)

    void init() {
        pool = (Node*)std::malloc(sizeof(Node) * CAP);
        head.store(pack(0, NIL), std::memory_order_relaxed);
    }
    // 返回 false 表示节点池耗尽（本示例中容量足够，用于演示边界）
    bool push(uint32_t idx, int value) {
        uint64_t old = head.load(std::memory_order_relaxed);
        for (;;) {
            pool[idx].next  = idx_of(old);                 // 只在本地可见前先接好链
            pool[idx].value = value;
            uint64_t desired = pack(tag_of(old) + 1, idx); // tag++ ：让 ABA 永远不可能相等
            if (head.compare_exchange_weak(old, desired,
                                           std::memory_order_release,
                                           std::memory_order_relaxed))
                return true;                               // 成功；失败时 old 已被刷新
        }
    }
    // 返回 -1 表示空栈；否则返回被弹出节点的索引
    int64_t pop() {
        uint64_t old = head.load(std::memory_order_acquire);
        for (;;) {
            uint32_t idx = idx_of(old);
            if (idx == NIL) return -1;
            uint32_t nxt = pool[idx].next;
            uint64_t desired = pack(tag_of(old) + 1, nxt);
            if (head.compare_exchange_weak(old, desired,
                                           std::memory_order_acquire,
                                           std::memory_order_relaxed))
                return idx;                                // 只有我能返回这个 idx
        }
    }
};

int main(int argc, char** argv) {
    int T   = (argc > 1) ? atoi(argv[1]) : 8;
    long N  = (argc > 2) ? atol(argv[2]) : 2000000;
    LFStack s; s.init();

    // 每线程负责一段不重叠的节点槽位，避免"节点同时被两个线程 push 两次"
    std::vector<uint32_t> base(T);
    for (int t = 0; t < T; ++t) base[t] = (uint32_t)((uint64_t)N * t / T);

    std::atomic<long> pushed{0}, popped{0};
    std::atomic<long long> sum{0};
    std::vector<std::thread> ts;
    auto t0 = std::chrono::steady_clock::now();

    for (int t = 0; t < T; ++t) {
        ts.emplace_back([&, t] {
            long per = N / T;
            uint32_t cursor = base[t];
            for (long i = 0; i < per; ++i) { s.push(cursor + (uint32_t)i, (int)(cursor + i)); pushed++; }
            // 第一阶段：所有线程 push 完毕后（本示例用 join 分阶段），再统一 pop
        });
    }
    for (auto& th : ts) th.join();
    double t_push = std::chrono::duration<double>(std::chrono::steady_clock::now() - t0).count();
    printf("push done : %ld ops in %.3f s  => %.1f M ops/s\n", N, t_push, N / t_push / 1e6);

    // 第二阶段：并发 pop，直到栈空；统计弹出的元素个数与校验和
    ts.clear();
    auto t1 = std::chrono::steady_clock::now();
    for (int t = 0; t < T; ++t) {
        ts.emplace_back([&] {
            for (;;) {
                int64_t idx = s.pop();
                if (idx < 0) break;
                sum += s.pool[idx].value;
                popped++;
            }
        });
    }
    for (auto& th : ts) th.join();
    double t_pop = std::chrono::duration<double>(std::chrono::steady_clock::now() - t1).count();

    long long expect = 0;                       // 校验和：所有 push 过的值之和
    for (long i = 0; i < N; ++i) expect += i;
    printf("pop  done : %ld ops in %.3f s  => %.1f M ops/s\n", (long)popped, t_pop, (double)popped / t_pop / 1e6);
    printf("pushed=%ld popped=%ld  %s   (checksum %s)\n",
           (long)pushed, (long)popped, pushed == popped ? "COUNT OK" : "COUNT MISMATCH",
           (long long)sum == expect ? "OK" : "MISMATCH");
    return (long long)sum == expect && pushed == popped ? 0 : 1;
}

【代码做什么？】

1. 打包（packing）：head 是单个 64 位原子字，高 32 位是版本号 tag，低 32 位是栈顶节点在 pool 中的索引。NIL = 0xFFFFFFFF 表示空栈。
2. push：load 当前栈顶 → 把新节点 next 指向它 → 计算 desired = (tag+1, idx) → compare_exchange_weak。注意 tag 每次都自增：即使 idx 因为节点被复用而”转了一圈回到同一个值”，tag 也不会相同，因此“ABA 相等”永远不可能发生——这等价于讲义里”用 pop_count 校验”的方案，但不需要机器提供通用 DCAS，因为两个字段被塞进了同一个字。
3. compare_exchange_weak 的失败语义：失败时它会把内存当前值写回 old，所以循环里不需要再手动 load 一次（这是 C++ 与手写 atomicCAS 的一个重要区别；手写版本必须显式 old = *addr 重读，正如讲义 atomic_max 的代码那样）。
4. 内存序：push 用 release 成功序（保证”写好的 pool[idx].next/value 在被别人看到栈顶指针之前可见”），pop 用 acquire（保证读到栈顶指针之后看到的是初始化完成的数据），失败路径用 relaxed（失败不需要任何排序语义，这是最常见的性能优化点）。
5. 无 use-after-free：节点永不释放（pool 只 malloc 一次），从根上消除了”读取已释放内存”的问题。代价是内存占用固定且无法回收（CAP 个节点），这也是讲义所说”用谨慎的节点分配/复用策略解决 ABA”的真实代价。
6. 正确性自检：popped == pushed 与 sum == expect 两个断言能抓住绝大多数（虽然不是全部）无锁逻辑错误——无锁数据结构的测试必须包含这种计数 + 校验和式的全局不变量检查。
7. 驱动方式说明：本示例把 push 与 pop 分成两个阶段（中间 join），是为了让校验和可判定（如果 push/pop 完全混跑，只要每个节点最终被弹出一次，校验和仍然成立——读者可以自行把两阶段改成混跑并验证这一点）。不允许两个线程 push 同一个槽位，所以每个线程使用互不重叠的槽位区间。

【并行机制与性能解说】

设线程数 P、总操作数 N。

• Work（总工作量）：每次成功操作 = 1 次原子读 + 若干次失败的 CAS + 1 次成功 CAS。在完全无争用时 W = Θ(N)；在 P 个线程全部争抢同一个 head 时，总 CAS 尝试次数 ≈ P(P+1)/2 每次”一人成功一轮”（推导见 4.2 节），即每次操作的期望尝试次数 ≈ Θ(P)。因此 W = Θ(N·(1 + 争用失败次数)) = Θ(N·P)（最坏情况下是 P 的线性倍）。
• Span（关键路径）：pop/push 的算法关键路径是 Θ(1)——一次读 + 一次 CAS，不依赖任何其它线程。这是无锁结构最漂亮的性质：算法层面没有串行链。
• 并行度 = Work/Span：形式上 Θ(N·P)，但真正决定吞吐的是硬件：所有 head 的 CAS 都落在同一个缓存行上，而该行的所有权迁移被硬件完全串行化。因此稳态吞吐的物理上界是

  Throughput_max ≈ 1 / (t_line · E[attempts per op])   （t_line = 该缓存行的单次交接延迟）
  

  而不是”线性于线程数”。

• 瓶颈诊断：
  1. 缓存行乒乓（cache-line ping-pong）：head 所在的那一行在 P 个核的 L1 之间来回迁移。P=8 且 t_line ≈ 80 ns 时，即使每次只尝试一次 CAS，理论上界也只有 1/(8 × 80ns) ≈ 1.5 M ops/s（每核约 190 K ops/s）——远低于单线程无争用时的 CAS 速率（~50 M ops/s）。
  2. 失败尝试是纯浪费：失败者付出了完整的一次行迁移代价（把行抢到自己缓存），却没有推进状态，还顺手把成功者的副本作废了。这就是讲义那句”a lock-free design does not eliminate contention”的硬件解释。
  3. 内存序的代价：把成功序从 acquire/release 换成 seq_cst（C++ 默认）在 x86 上会让 push/pop 各多一条 lock 前缀指令或屏障，实测吞吐下降通常可观；但省错内存序会造成正确性错误——这是本讲最常见的”两难陷阱”。
  4. 栈的 LIFO 与缓存局部性：pool 里的节点按分配顺序排列，LIFO 弹出顺序对缓存局部性反而友好（刚 push 的节点最近被访问过，很可能还在 L1/L2）；而 FIFO 队列会让生产/消费两端访问相隔很远的内存，这是队列与栈在内存系统上的不对称性。
  5. 性能是”机器的性质”，正确性是”算法的性质”：本示例的输出中，COUNT OK / checksum OK 是算法正确性的判据（在任何机器、任何线程数下都必须成立）；而 M ops/s 的绝对值高度依赖机器与当前负载——在同一台共享节点上重复运行，吞吐可以在几 M ops/s 到几十 M ops/s 之间波动。因此无锁数据结构的工程实践应当把”正确性自检”做成常驻的断言（每次测试都跑），而把”性能数字”当作需要在受控环境下重测的量。本示例的意义正在于：把 4.2 节那个”P²/2 次尝试”的抽象模型落成一个可运行的、正确性可自动判定的程序，读者可自行改变线程数观察吞吐曲线的形状。

3.3 示例 3：锁实现微基准 —— T&S vs TTS vs ticket lock（把一致性流量测出来）

代码做什么？：用同一台机器、同一段临界区，测量三种锁在 T 个线程下的”每次加解锁耗时”和”每次成功获取锁所需的原子尝试次数“。第二个指标是本示例的关键：它直接把讲义”O(P) 失效 vs 每次测试都失效”的论证变成一个可测量的数字。

// 编译: g++ -O3 -std=c++17 -pthread lockbench.cpp -o lockbench
// 运行: ./lockbench 16 200000 0         # 16 线程，20 万次 lock/unlock，临界区长度参数 = 0
//      第三个参数 = 临界区里做多少次"依赖整数加法"（每次约 0.3 ns，用来把临界区变长）
//
// 两条必须遵守的测量纪律：
//  (1) 计数器必须放在"每线程私有"的位置（见 bench 中的 lr/la）。若把 long reads 写进
//      锁对象所在的缓存行，自旋时的 reads++ 会不断抢走锁所在行的所有权
//      => 观测仪器自己制造伪共享 => 实测性能被测坏（本示例实测恶化约 10 倍）。
//  (2) 锁内部"两个热变量"（如 ticket lock 的 next 与 serving）必须分处不同缓存行。
//      否则每次取号（写 next）都会作废所有在 serving 上自旋的等待者的副本。
//      => 见 TicketLock 中的 alignas(64)。

#include <cstdio>
#include <cstdlib>
#include <atomic>
#include <thread>
#include <vector>
#include <chrono>
#include <mutex>

static long g_cs_iters = 0;    // 临界区长度参数（依赖加法次数），由 argv[3] 设置

// 模拟临界区里的工作：依赖加法链，编译器无法并行化/消除
static inline long critical_section(long iters) {
    long a = 1;
    for (long i = 0; i < iters; ++i) a = a * 3 + 1;   // 约 1 周期/次 ≈ 0.3 ns/次
    return a;
}

// ---------------- 1. test-and-set 锁：每次尝试都是原子 RMW ----------------
struct alignas(64) TASLock {
    std::atomic<int> flag{0};
    void lock(long& /*reads*/, long& attempts) {
        while (flag.exchange(1, std::memory_order_acquire) == 1) attempts++;
    }
    void unlock() { flag.store(0, std::memory_order_release); }
};

// ---------------- 2. test-and-test-and-set 锁：先本地读，再尝试 RMW ----------------
struct alignas(64) TTSLock {
    std::atomic<int> flag{0};
    void lock(long& reads, long& attempts) {
        for (;;) {
            while (flag.load(std::memory_order_relaxed) == 1) reads++;      // 本地缓存里的普通读
            if (flag.exchange(1, std::memory_order_acquire) == 0) return;  // 抢占
            attempts++;                                                    // 抢失败
        }
    }
    void unlock() { flag.store(0, std::memory_order_release); }
};

// ---------------- 3. ticket lock：取号是原子操作，等待只是读 ----------------
//   next 与 serving 必须分处不同缓存行：它们被不同角色（取号者 / 所有人）高频访问
struct alignas(64) TicketLock {
    alignas(64) std::atomic<unsigned> next{0};      // 只被"取号"这一动作写
    alignas(64) std::atomic<unsigned> serving{0};   // 被所有等待者读、被持有者写
    void lock(long& reads, long& /*attempts*/) {
        unsigned my = next.fetch_add(1, std::memory_order_relaxed);
        while (serving.load(std::memory_order_acquire) != my) reads++;     // 只读，不产生 RMW
    }
    void unlock() { serving.fetch_add(1, std::memory_order_release); }
};

// ---------------- 4. 基准线：pthread mutex ----------------
struct alignas(64) MutexLock {
    std::mutex m;
    void lock(long& /*reads*/, long& /*attempts*/) { m.lock(); }
    void unlock() { m.unlock(); }
};

std::atomic<long> g_sink{0};    // 防止临界区被优化掉（多线程累加，必须原子）

template <typename L>
static void bench(const char* name, int T, long total) {
    L lock;
    std::vector<long> reads(T, 0), attempts(T, 0);
    std::atomic<bool> go{false};
    std::vector<std::thread> ts;
    long per = total / T;

    auto t0 = std::chrono::steady_clock::now();
    for (int t = 0; t < T; ++t) {
        ts.emplace_back([&, t] {
            while (!go.load(std::memory_order_acquire)) {}
            long lr = 0, la = 0, local_sink = 0;      // 每线程私有计数器（不与锁共享缓存行）
            for (long i = 0; i < per; ++i) {
                lock.lock(lr, la);
                local_sink += critical_section(g_cs_iters);   // "临界区"
                lock.unlock();
            }
            g_sink.fetch_add(local_sink, std::memory_order_relaxed);
            reads[t]    = lr;
            attempts[t] = la;
        });
    }
    go.store(true, std::memory_order_release);
    for (auto& th : ts) th.join();
    double s = std::chrono::duration<double>(std::chrono::steady_clock::now() - t0).count();

    long R = 0, A = 0;
    for (int t = 0; t < T; ++t) { R += reads[t]; A += attempts[t]; }
    long done = per * T;
    printf("%-14s T=%-3d cs=%-6ld %8.0f ns/op-air   attempts/acq=%7.2f  reads/acq=%9.2f\n",
           name, T, g_cs_iters, s / done * 1e9, (double)A / done, (double)R / done);
}

int main(int argc, char** argv) {
    int  T     = (argc > 1) ? atoi(argv[1]) : 8;
    long total = (argc > 2) ? atol(argv[2]) : 200000;
    g_cs_iters = (argc > 3) ? atol(argv[3]) : 0;
    bench<MutexLock> ("pthread-mutex", T, total);
    bench<TASLock>   ("test-and-set",  T, total);
    bench<TTSLock>   ("test-and-test", T, total);
    bench<TicketLock>("ticket",        T, total);
    return 0;
}

【代码做什么？】

1. 四种锁共用同一段可忽略的临界区，测量的是”纯同步开销”（与讲义引用的 Culler/Singh/Gupta 基准同一思路：”Critical section time removed so graph plots only time acquiring/releasing the lock”）。
2. TASLock 每次循环都执行 exchange（原子 RMW ⇒ 一次所有权获取），attempts 直接计数这类昂贵操作。
3. TTSLock 分两层：内层 load 是本地缓存里的普通读（只要行还在 S 态就一直命中，几乎零流量），外层 exchange 才产生所有权获取。reads 与 attempts 分别是”廉价读”和”昂贵 RMW”的计数——两者的比例就是讲义那套流量论证的实验证据。
4. TicketLock 的等待路径只有 load（讲义原文：”No atomic operation needed to acquire the lock (only a read)”），因此它的 attempts 永远保持 0，而 reads 是自旋读次数——“昂贵 RMW = 0”正是票号锁的全部卖点。
5. MutexLock 作为基准线（现代 glibc 的 pthread_mutex 在无争用时走 futex 快路径，几乎与一条 CAS 同价；有争用时进入内核挂起，从而把”自旋浪费”换成”上下文切换开销”）。

6. 计数器必须传成”每线程的栈上局部变量”（lock.lock(lr, la)）。如果把 long reads 写成锁结构体的成员，reads++ 就会写在锁所在的那条缓存行上：每个自旋迭代都让等待者把该行的所有权抢过来，从而作废所有其它等待者的 S 态副本——观测仪器自己制造了伪共享。这一条在实测中被明确验证过：把计数器放进锁对象时，各锁的耗时普遍恶化（自旋次数最多的 ticket lock 恶化接近 10 倍）。这是”伪共享”最有教育意义的一个实例：连”用来观测同步开销的代码”都会改变同步开销。 同理，TicketLock 里的 next 与 serving 也必须用 alignas(64) 分处不同缓存行——否则每次取号（写 next）都会作废所有在 serving 上自旋的等待者的副本。

7. 应该观察什么（可复现的定性趋势）：
   • test-and-set 的 attempts/acq 随临界区长度显著上升：临界区为空时约等于 1（几乎没有等待者），把 cs 参数增大到千次依赖加法时上升到上百次。这与 4.1 节模型”每次获取期间的尝试次数 ∝ 持锁时长”的预测一致——这是对”T&S 无谓消耗互连带宽”最直接的实验证据。
   • test-and-test-and-set 的 attempts/acq 始终接近 0，而 reads/acq 很大：等待全部由本地缓存里的普通读承担，昂贵的 RMW 只在真正尝试抢占时发生。这正是讲义”每次释放 O(P) 次失效（而不是每次测试都 O(P)）”的实测体现。
   • ticket 的 attempts/acq 恒为 0：等待路径上完全没有原子 RMW（”只有一次读”），这一点由代码结构保证。
   • 不要从一次运行里读绝对值下结论：本示例在一台共享的登录节点上运行时，同一配置的重复测量可以相差数倍（例如 pthread-mutex 在 29 ns 与 400 ns 之间波动），而 ticket 的绝对耗时在该机器上并不比 TTS 更好——这说明”O(P) 互连流量“（讲义对 ticket lock 的论断）与”最低的交接延迟“是两个不同的评价轴：ticket lock 用严格 FIFO 把交接彻底串行化，一旦某位持票者被抢占/变慢（convoying），后面所有人都要等它，这在多道程序的共享机器上会放大成微秒级延迟。要在自己的机器上得到可信结论，必须：①把线程绑定到独占的物理核（taskset），②多轮取最小值，③把临界区长度当作自变量扫一遍。 这也是讲义在”desirable lock performance characteristics”里把低延迟与低互连流量并列为两条独立目标的原因。

【并行机制与性能解说】

设 P 个线程各做 N 次 lock/unlock，总操作数 M = P·N。

• Work：W = Θ(M) 次”锁协议步骤”，但每次步骤的成本差异极大：TAS 的每一步是原子 RMW，TTS 的”读”步骤是普通 load（便宜 10–100 倍），ticket 的”读”步骤同样是普通 load。
• Span：关键路径 = 所有临界区的串行化链：Span = Θ(M · t_handoff)，其中 t_handoff 是”锁从一个线程交接给下一个线程”的延迟。这是本示例最重要的洞察：M 次操作必须全部串行，因为互斥的语义就是”一次一个”。
• 并行度 = Work/Span = Θ(1)。形式上的并行度是 1 —— 这个微基准在算法层面完全不可并行，因此”加线程能不能变快”的答案取决于 t_handoff 是否随 P 变化：如果实现是好的，加线程不该让每次加解锁变慢；如果是 TAS，t_handoff 随 P 增长（O(P) 条失效事务），于是总时间随 P 超线性上升。这正是讲义图（时间 vs 处理器数）所展示的现象。
• 瓶颈诊断：
  1. 互连争用（interconnect contention）：讲义明确写道”Interconnect contention increases amount of time to transfer lock (lock holder must wait to acquire bus to release)”，并补充”contention also slows down execution of the critical section”（未在该图中显示）。本示例中可观察到的对应现象是：TAS 的 attempts/acq 随 cs（持锁时长）增大而上升（实测从”临界区为空”时的约 1 上升到上千次依赖加法时的上百次），即等待者的每一次无效 RMW 都在消耗互连带宽。
  2. attempts/acq 与 reads/acq 的分离：TTS 与 TAS 的差异不会体现在”代码行数”上，而体现在这两个计数器的量级上——TAS 的失败尝试数随争用增长，TTS 的昂贵 RMW 数始终被压在”每次释放一次”的水平。这是把讲义里 O(P)/O(P²) 的论断落到自己机器上验证的方法。
  3. 公平性与延迟是两个轴：ticket lock 是 FIFO 的，等待路径没有任何原子 RMW（attempts/acq 恒为 0），但它把交接彻底串行化：任何一位持票者变慢，后面所有人都要等（convoying）。因此在本示例这类”临界区极短、线程数少”的场景里，ticket lock 未必最快——“低互连流量”不等于”低交接延迟”（讲义把这两条并列为独立的锁评价目标）。相反，TAS/TTS 无公平性保证，可能出现某线程长时间抢不到（饥饿），实测表现为各线程完成时间的巨大方差（可扩展示例统计每线程耗时）。
  4. 测量纪律（本示例最实用的收获）：①g_sink 用于防止空临界区被完全消除，且必须用 -O3；②计数器必须每线程私有、锁的热字段必须分处不同缓存行（见第 2、6 条脚注）；③线程应绑定到独占物理核、多轮取最小值——在共享机器上单次运行的绝对值可以相差数倍，任何”某某锁更快”的结论都必须附带测量条件。

4. 性能模型与复杂度分析

本节的所有数字都基于一组显式假设（量级取自现代多核服务器上普遍观测到的水平，用于建立直觉；读者可用 3.3 的微基准在自己的机器上实测替换）。工作、跨度、并行度的定义遵循课程使用的 work-span 模型。

假设参数表（下文所有算例共用）：

4.1 算例 A：锁的互连流量模型（T&S / TTS / ticket）与数值结论

模型（直接来自讲义结论）：

• T&S 锁：每一次”测试”都是一次原子 RMW ⇒ 每次测试产生一次行所有权获取，并把其它所有人的副本作废。P-1 个等待者以自旋速率 r = 1/t_line 反复测试，于是每秒产生的事务数约为

  Traffic_TAS ≈ (P - 1) / t_line       (单位：次/秒)
  每次成功获取锁期间的尝试次数 ≈ (P - 1) × (持锁时长 / t_line)
  

• TTS 锁：等待期间是本地缓存里的普通读（几乎零流量）；锁释放时的失效让每个等待者各读一次 ⇒ 每次释放 O(P) 次失效/读；P 次获取构成一轮 ⇒ 每轮 O(P²) 次事务。
• ticket lock：等待者都是普通读，每次释放只有一次失效广播（O(P) 的到达，但只有 1 次广播事务），且下一个持锁者就在本地缓存里升级 ⇒ 每次获取 ≈ 1–2 次行交接。

数值算例（P = 32，t_line = 80 ns）：

1. T&S 每次获取的尝试次数：设持锁者做临界区需要 t_c = 500 ns。持锁者刚拿到行时，等待者的副本被作废；它们很快各抢一次，行在”等待者们”之间乱窜。在最坏（经典）模型下，持锁期间约 (P-1)/2 ≈ 15.5 个等待者每人抢 t_c / (P·t_line) 次……为了给出可复核的数字，采用讲义给出的保守替代模型：每次获取期间的总尝试次数 ≈ (P-1)（每个等待者至少抢一次）。则
   • 每次获取的额外事务数 = 31，每次事务 80 ns ⇒ 每次锁交接 ≈ 31 × 80 ns = 2.48 µs 的纯一致性流量（在 500 ns 的临界区之上）。
   • 稳态吞吐上限 = 1 / (t_c + 31·t_line) = 1 / (500 + 2480) ns ≈ 336 K 次/秒。
2. ticket lock：每次获取 ≈ 2 次行交接 = 160 ns ⇒ 吞吐上限 = 1 / (500 + 160) ns ≈ 1.52 M 次/秒。
   • 比值 ≈ 4.5×。而这个比值随 P 线性增长（T&S 的成本 ∝ P，ticket 的成本 ∝ 1），这正是”可扩展性（scalability）”这一锁评价维度的量化含义。
3. 纯同步开销（按本模型推算，临界区 ≈ 0）：P = 32 时
   • ticket：理想情况下 2 × 80 = 160 ns/op-air ⇒ 单线程视角 6.25 M ops/s（总吞吐仍是 6.25 M/s，因为全串行）；
   • T&S：31 × 80 = 2.48 µs/op-air ⇒ 0.40 M ops/s；
   • 单线程无争用时两者都 ≈ 2 × 6 ns = 12 ns（行常驻本地独占）。
   • 结论：模型给出的退化幅度约 200 倍；T&S 的退化完全来自一致性流量，而不是临界区本身。
   • 模型的重要前提（务必注意）：”每次获取期间尝试 P-1 次”这个假设成立的前提是临界区足够长、等待者真的在等待（t_c ≫ t_line）。如果临界区短到接近 0，锁在大部分时刻是空闲的，大多数获取一次尝试就成功（3.3 节的微基准在临界区为空时实测 attempts/acq ≈ 1，随临界区变长才上升到上百次）。因此”尝试次数”不是常数，而是 ≈ min(P-1, t_c / t_line × 常数)——它随持锁时长增长并渐近到 P-1。 这也解释了讲义那张”时间 vs 处理器数”的图为什么在临界区被”移除”（置为极短）后仍然会随 P 上升：因为真正的成本来自等待者制造的流量，而不是临界区本身。
4. TTS 的位置：P-1 = 31 个等待者，每次释放产生 31 次失效 + 31 次读 ⇒ 一轮 32 次获取共约 32 × 31 = 992 次事务 ⇒ 每轮 O(P²) = 1024 量级，即每次获取 ≈ 31 次事务（与 T&S 同阶）；但 TTS 在持锁期间的等待是零流量的，所以它比 T&S 好的地方在于不会在持锁期间把持锁者的缓存行踢来踢去（讲义：T&S “Update line in cache” 的失败尝试会不断作废持锁者的行）。实测上 TTS 通常优于 T&S，且代码代价仅为多一层内层读循环。

4.2 算例 B：CAS 循环的争用模型 —— 一个”无锁却不可扩展”的定量证明

模型：P 个线程争抢同一个原子字（无锁栈的 head），每个线程各执行 1 次操作（共 P 次）。硬件把该缓存行上的 CAS 完全串行化：每 t_line 时间恰好有 1 个 CAS 原子地生效。

• 设当前有 k 个线程尚未完成。在这一轮”行所有权窗口”中，恰好有 1 个线程的 CAS 成功（其余 k-1 个失败）。因此从 k 降到 k-1 所需的尝试次数服从几何分布，期望为 k 次尝试（每次尝试耗 t_line）。
• 于是完成全部 P 次操作所需的总尝试次数

  E[attempts] = Σ_{k=1..P} k = P(P+1)/2 ≈ P²/2
  

  每次成功操作的平均尝试次数 ≈ P/2。

数值算例（P = 32，t_line = 80 ns）：

• 总尝试次数 ≈ 32 × 33 / 2 = 528 次；总串行时间 ≈ 528 × 80 ns = 42.2 µs 完成 32 次操作 ⇒ 每操作 1.32 µs，吞吐 ≈ 758 K ops/s（若为 push+pop 各一次则为 379 K “完整操作”/s）。
• 对比单线程、无争用：行独占，CAS ≈ t_cas_local = 6 ns ⇒ 167 M ops/s。
• 退化倍数 ≈ 220×。而且这个退化是结构性的（∝ P²），完全符合讲义总结的那句”a lock-free design does not eliminate contention“。
• 延长验证（P = 64）：总尝试 ≈ 64 × 65/2 = 2080 次 ⇒ 166 µs 完成 64 次操作 ⇒ 每操作 2.6 µs，吞吐 ≈ 385 K ops/s。吞吐几乎减半（758 K → 385 K），说明”加线程”在高争用 CAS 上是负收益。
• 工程缓冲手段：
  • 消除冲突点：换用 Treiber 栈 + 每线程局部队列（由持有者批量转移）或 消除式（elimination）栈，把”每操作一次全局 CAS”变成”每批一次”；
  • 分摊（batching）：每个线程先在本地累积 K 个操作，再一次性 CAS 提交，把总尝试次数从 P²/2 降到约 (P/K)²/2 · K = P²/(2K)；
  • 退避（backoff）：失败后随机延迟（指数退避），降低”同时抢行”的概率，把几何分布的参数从”必然冲突”推向”串行化”；
  • 换结构：SPSC 队列（2.7 节）在 1 生产 1 消费下完全不需要原子 RMW，是没有争用就没有代价的极端例子。

4.3 算例 C：细粒度锁的 Work / Span / 并行度与流水线吞吐上界

场景：链表节点数 n = 1000，P = 32 个线程，每个线程做 M_per = 10^4 次 insert，随机值域使得平均遍历长度 L ≈ n/2 = 500 个节点。

• Work：
  • 粗粒度：节点访问 W_visit = 32 × 10^4 × 500 = 1.6 × 10^8 次；锁操作 W_lock = 3.2 × 10^5 次。
  • 细粒度：节点访问相同；锁操作 W_lock = 32 × 10^4 × 500 × 2 = 3.2 × 10^8 次原子 RMW（每步一次 lock + 一次 unlock）。
  • 成本的量级对比：粗粒度的一次锁操作在无争用时 ≈ 12 ns（两次本地独占 RMW），400 次获取……；细粒度把 3.2×10^8 次原子操作插入执行流，即便全部命中本地独占（6 ns/次，含释放在内取 12 ns 一对），也要 1.6 × 10^8 × 12 ns ≈ 1.9 s 的纯同步时间（未计缓存行争用，实际更高）。在长链表上，细粒度锁是明确的自杀式优化。
• Span：单次操作的关键路径 = L 步指针追逐 + L 对锁交接。纯指针追逐部分是不可并行化的依赖链：

  Span_visit(1 op) ≈ L × t_dram = 500 × 90 ns = 45 µs      （每步都缺 L1/L2，L3 也大概率缺）
  Span_lock(1 op)  ≈ L × t_hop  = 500 × 40 ns = 20 µs      （无争用时行在本地或近邻，取 40 ns）
  

• 并行度 = Work / Span：1.6×10^8 / (500 × (90+40) ns) ≈ 1.6×10^8 / 65 µs ≈ 2460。这个数字说明：理论上最多有约 2460 个”操作步”可以同时在飞，但单次操作的延迟是 65 µs，且被指针追逐主导，无法通过更多线程缩短。
• 吞吐上界（推荐用这个而不是 Work/Span 来评估）：

  细粒度:  Throughput ≤ min( P / t_lockhop ,  1 / t_hop ) ——受"锁交接流水线"限制
  粗粒度:  Throughput ≤ 1 / (t_critical + t_handoff)，t_critical ≈ 45 µs
  

  • 粗粒度：1 / (45 µs + 160 ns) ≈ 22.2 K ops/s（32 个线程合计，与 P 无关！）——这就是”单一全局锁串行化”的代价：加线程完全无效。
  • 细粒度：若锁交接能被流水化到 t_hop = 40 ns，则理论吞吐上限 = 1/40 ns = 25 M ops/s，比粗粒度好 3 个量级。但前提是”每步 2 次原子操作不产生缓存行争用”，而当 n = 1000 个节点（每个几十字节）分布在约 1000 × 64 B ≈ 64 KB 内时，32 个线程同时在不同节点 lock/unlock 会产生大量跨核缓存行迁移，实际 t_hop 会从 40 ns 恶化到 200–400 ns，吞吐降到 2.5–5 M ops/s——依然远好于粗粒度，但比理想值差 5–10 倍。这个”理想 25 M vs 现实 3 M”的差距，就是伪共享与行迁移的账单。
• Amdahl 视角：设程序总时间中”必须串行的部分”占 s，则可扩展性 Speedup ≤ 1/(s + (1-s)/P)。粗粒度锁把这个串行比例推到 s → 1（性能由临界区串行时间决定），因此无论 P 多大，加速比都趋近 1；细粒度锁把 s 压到”每步锁交接时间 / 每步总时间”的水平，从而恢复可扩展性。结论：细粒度同步的收益不是”更快地做同一件事”，而是”把不可扩展的程序变成可扩展的程序”。

4.4 算例 D：带宽、延迟与 Little’s Law —— 无锁数据结构真正的天花板

算术强度与 Roofline 脊点（本机假设）：

  峰值浮点吞吐 = P × f × W × k = 32 × 3.0 GHz × 8 × 2 = 1536 GFLOPS
  内存带宽 BW = 20 GB/s
  Roofline 脊点 = 1536 / 20 = 76.8 FLOP/byte
  ==> 算术强度 < 76.8 时受带宽限制；> 76.8 时受计算限制

数值算例 1（讲义示例的量级）：一个 256 MB 的数组，单次遍历读 256 MB：

  时间下界 = 256 MB / 20 GB/s = 0.256 GB / 20 GB/s = 12.8 ms

这就是”任何需要额外扫一遍 256 MB 内存的簿记操作，至少要 12.8 ms 的地板价”。把它用到数据结构上：

• 若把链表节点的锁字段与数据分离（为了消除伪共享而做），你可能把原来一次顺序扫描变成两次（数据数组 + 锁数组），于是每次遍历的带宽需求翻倍，纯带宽时间从 12.8 ms 变成 25.6 ms；
• 若为了消除伪共享给每把锁加 alignas(64) 填充，而锁只有 1 字节有用信息，则内存放大 64 倍（假设原节点 32 B），一个 256 MB 的结构的锁数组会膨胀到 512 MB，带宽与 TLB 双重恶化。

数值算例 2（Little’s Law：要多少并发才能填满带宽）：

  Little's Law:  并发量 = 吞吐 × 延迟
  要维持 BW = 20 GB/s，且 DRAM 延迟 = 90 ns：
      在途字节数 = 20 GB/s × 90 ns = 1800 B
      在途缓存行数 = 1800 B / 64 B ≈ 28.1 条
  ==> 一个核最多支持 ~10-12 条未完成缺失（MSHR 有限），因此至少需要 3 个核
      同时满负荷发缺失，才能把 DRAM 带宽打满。

把这个结论用到无锁 vs 有锁上：

• 无锁 CAS 循环是”一次一条缓存行在途”的极端：每个线程在任一时刻只关心一个地址（head），并发度 = 1（因为行被串行化），因此在途字节数 ≈ 64 B，能达到的”有效带宽”只有 64 B / 80 ns = 0.8 GB/s ——仅为机器带宽的 4%。这说明无锁 CAS 点争用是彻底的延迟受限（latency-bound）场景，与带宽毫无关系。
• 细粒度锁链表是”指针追逐 + 行迁移”混合体：每个 hop = 一次 90 ns 的节点读 + 可能的行迁移，在途字节数同样只有几十字节，t_hop 由延迟决定而不由带宽决定。
• 什么时候带宽才会成为瓶颈：当数据结构操作变成批量顺序访问时（例如哈希桶数组的 rehash、队列底层环形缓冲的批量入队、数组式的图遍历），此时 BW 才是限制，12.8 ms / 256 MB 是必须付的地板价。
• 结论：同步结构的性能模型通常由延迟与串行化决定，而不是带宽；反之，遍历型/批处理型代码才需要 Roofline 与算术强度。混淆这两类模型是最常见的性能误判来源。

4.5 模型选择速查表

5. 关键要点

1. 同步粒度是一维谱（spectrum），不是一个二选一：单把大锁 → 每桶/每节点锁（hand-over-hand）→ 无锁 CAS → 无等待。向右移动的每一步都用”更高的单步实现成本 + 更大的正确性论证负担”换取”更低的争用与更好的可扩展性”；判断往哪边移动的唯一依据是 work-span / Amdahl / 一致性流量的定量分析，而不是”越细越好”或”无锁一定更快”。
2. “用锁就是阻塞算法”，而”无锁不等于没有争用”：讲义的两条硬结论——①任何使用锁的算法都是阻塞的，无论自旋还是抢占（一个被换出/缺页/崩溃的持锁者可以无限期阻止所有其它线程）；②lock-free 只保证系统级进展（某个线程必定完成），它不排除单个线程饥饿，也不消除争用——CAS 在重争用下的失败重试使吞吐按 ∝ 1/P 恶化（4.2 节的 P²/2 模型）。
3. 原子操作的成本由”缓存行所有权的迁移”决定，而不是由指令本身决定：x86 的 lock 前缀意味着”缓存保留该行直到完成 / 占住总线 / 对其它请求回 NACK”；因此同一缓存行上的原子操作被硬件完全串行化，性能指标是”每秒能交接多少次该行”。由此推出的三条工程规则：①让热的原子变量独占缓存行、让锁与数据分离（避免伪共享）；②减少原子操作的次数（hand-over-hand 的 hop 成本、CAS 失败重试都算在这里）；③能用一次原子操作办成的事，不要拆成两次（ticket lock 的等待只需普通读，就是这条规则的典范）。
4. 无锁编程的三个”必须一起解决”的难题：ABA（CAS 只比较值，比较不出”世界变过又变回来”——用版本号打包进同一个字，或用 cmpxchg8b/16b 打包相邻字段，或用节点分配/复用策略）；内存回收（use-after-free 与 ABA 是两个独立问题——hazard pointer / epoch / 内存池）；内存序（讲义在所有无锁代码处都标注 “assume a sequentially consistent memory system for now”，在真实弱一致性硬件上必须补栅栏或使用 atomic<>，且要选对 acquire/release 而不是无脑 seq_cst）。
5. 在”独占机器”的性能优化场景里，锁通常是最好的选择；无锁的价值主要在”无法独占机器”的场景：讲义明确说，写得好的加锁代码可以与无锁代码一样快甚至更快，而且通常简单得多；无锁（非阻塞）真正不可或缺的场合是多道程序环境（数据库、Web 服务器）——线程可能在临界区内被抢占、缺页、优先级反转、护航（convoying），此时”任何人卡住都不会卡住系统”这一性质本身就是价值。

6. 常见陷阱与注意事项

• 陷阱 1：把”细粒度”理解成”把锁变小”，却忽略了每步加锁的开销。 hand-over-hand 让每次遍历步从”一次普通读”变成”读 + 两次原子 RMW”，在长链表上（4.3 节的 n = 1000、L = 500）这会让原子操作数量爆炸到 10^8 量级，最终比单把大锁还慢。正确做法：只在真正要修改的位置加锁（讲义”insert 还有改进空间”的答案——只读遍历 + 锁 prev + 重新验证 prev->next == cur），或用锁条带化（striping）折中。
• 陷阱 2：忽略伪共享（false sharing），让细粒度锁退化成”更慢的粗粒度锁”。 每节点一把锁会让相邻节点的锁落在同一 64 B 缓存行上，两个线程锁不同节点却争同一行 ⇒ 一致性流量与粗粒度锁同量级，而代码复杂度和原子操作次数都更高。识别方法：用 PMU 计数器（HITM / 缓存行迁移计数）或把锁字段改为 alignas(64) 对比测量。修正手段：锁与数据分离成两个数组、把锁字段填充到独占缓存行、或用”按桶分摊锁”。
• 陷阱 3：误以为 std::atomic<T> 就等于无锁，或误以为无锁就等于更快。 std::atomic 的原子性”可能由 mutex 实现”，必须用 is_lock_free() 确认；反过来，无锁实现在重争用下会因为 CAS 失败重试而比加锁慢（4.2 节：P=32 时每操作 1.32 µs，而单线程无争用只要 6 ns）。正确心态：先测量争用程度，再决定是否值得上无锁。
• 陷阱 4：忽略 ABA 问题与”引用已释放内存”是两个独立的问题。 加了 pop_count/版本号解决了 ABA，并不会解决 old.top->next 可能读取已释放节点的问题（use-after-free）；反之用内存池（永不 delete）解决了 use-after-free，也不会解决 ABA（地址会被复用）。必须分别处理：ABA 用”版本号打包 / 宽 CAS / 不复用地址”，回收用”hazard pointer / epoch / 内存池”，并注意两者对内存占用的联合影响。
• 陷阱 5：在弱一致性硬件上漏掉内存栅栏，或把内存序设得过强。 讲义在 SPSC 队列与无锁栈的代码处都明确标注”Assume a sequentially consistent memory system for now (or the presence of appropriate memory fences, or C++11 atomic<>)“。漏栅栏会导致”生产者写完 data[tail] 但消费者看到新 tail 却读到旧数据”这类极难复现的错误；无脑用 seq_cst 则在 x86 上为每次原子操作多付 lock 前缀/屏障代价。正确做法是：release 用在”发布新状态的那一次写”（push 成功），acquire 用在”读取状态的第一次读”（pop 开头），失败路径用 relaxed。
• 陷阱 6：把”无锁”当作”无争用”写进性能预算，忽略负载不均与热点。 无锁栈的所有操作都争抢同一个 head（单点热点），无锁链表的所有操作都要从 head 出发遍历（head 附近的锁最热）。这与”任务粒度选择”是同构问题。缓解办法：batching（本地累积后一次提交）、backoff（随机退避）、消除（elimination）、分片（sharding）、以及换成 SPSC 结构（没有任何共享 RMW）。

7. 思考题（带答案）

问题 1（细粒度锁的正确性与死锁）：下面是讲义 hand-over-hand 链表 insert() 的核心循环：

FNode* prev = list->head;  lock(prev->lock);  FNode* cur = prev->next;
if (cur) lock(cur->lock);
while (cur && cur->value < value) {
    Node* old_prev = prev;  prev = cur;  cur = cur->next;
    unlock(old_prev->lock);  if (cur) lock(cur->lock);
}

请回答三个问题：(a) 为什么这段代码一定无死锁？(b) 为什么”先 unlock(old_prev) 再 lock(cur)“这个看似危险的顺序其实不会造成悬空指针？(c) 讲义提问”insert() 还可以怎样进一步改进”，请给出改进方案与它对本讲后半部分的意义。

【答案】 (a) 无死锁的原因是全局锁序（global lock ordering）：所有线程都从 list->head 出发、沿 next 指针方向（head → tail）依次加锁，并且在持有一把锁的同时只尝试获取沿同一方向的下一把锁。于是”资源等待图”中所有边都指向同一方向，不可能出现环（这正是死锁第 4 个必要条件”circular wait”被破坏）。因此不需要超时、不需要重试、也不需要任何死锁检测。注意这条论证的脆弱性：只要有一个操作（例如”从表尾向前查找”或”删除时同时锁前驱与后继之外的第三个节点”）逆序加锁，无死锁的保证立即失效。

(b) 关键在于”我始终持有前驱的锁“这一不变量。循环里 old_prev 是上上轮的 prev，而当前的 prev（= 上一轮的 cur）从上一轮起就已经被锁住且尚未释放。所以 unlock(old_prev); lock(cur); 的那一刻：

• 线程手上仍然持有 prev->lock；
• 而 cur 是从 prev->next 读出来的，prev->next 由 prev->lock 保护，所以任何想摘掉 cur 的线程都必须先获得 prev->lock（而它拿不到）⇒ cur 的身份在这段窗口内是稳定的，lock(cur->lock) 作用于一个仍然在链表中的节点，不会悬空。
• 附带结论：该线程在任何时刻都至少持有一把锁（prev->lock），这也保证了不会出现”手上没有任何锁、局部指针随时失效”的窗口。
• 反例：如果写成 unlock(prev); prev = cur; cur = cur->next; lock(cur);（先把 prev 的锁也放掉），就丢掉了这个不变量，别的线程可以在空窗期把 cur 摘链并 delete，随后对已释放内存加锁 = use-after-free。

(c) 改进方案：把”只读遍历”与”加锁修改”分离（乐观遍历 + 加锁验证）。因为 insert 最终只修改一个指针 prev->next，遍历过程本身不需要互斥：先用纯读（无锁、无原子操作、无一致性流量）找到插入位置 prev/cur；然后只锁 prev；拿到锁后重新验证 prev->next == cur（以及 cur 仍在链上、prev->value < value <= cur->value 或不变量成立）：验证通过就执行 n->next = cur; prev->next = n; 并解锁，验证失败就放弃本轮结果、回到遍历重新搜索。

• 收益：每次操作从 Θ(L) 次原子 RMW 降到 O(1) 次原子 RMW 加一次失败重试，这正好回应了讲义”细粒度锁的开销（每步加锁、额外存储）是否可以折中”的提问。
• 对本讲后半部分的意义：这个”读快照 → 计算 → 在提交点校验 → 失败重试“的结构，与无锁 CAS 循环在形式上完全同构（只是一次校验的对象从”值”变成”指针 + 结构不变量”）。因此无锁编程不是与锁对立的另一套技术，而是”把校验点从临界区边界压缩到一个原子操作”的延续——这也正是讲义在结尾预告 Transactional Memory 时所说的：”CAS 的作用是判断在我操作期间有没有别的线程改过数据结构”，而事务内存把这种”乐观 + 可中止”的机制一般化。

问题 2（ABA 与内存回收）：某同学写了下面这个无锁 pop（单链表栈，节点用 new/delete）：

Node* pop(Stack* s) {
    while (1) {
        Node* old_top = s->top;
        if (old_top == NULL) return NULL;
        Node* new_top = old_top->next;
        if (CAS(&s->top, old_top, new_top) == old_top) {
            int v = old_top->value;  delete old_top;  return old_top;   // (X)
        }
    }
}

他指出”我已经在 CAS 成功后才 delete，所以不存在 use-after-free，也不需要 hazard pointer”。请指出他至少两处错误，并说明为什么专门加一个 pop_count 计数器仍不能解决全部问题，最后给出一个完整可行的方案（可以是组合方案）。

【答案】

错误 1：CAS 成功并不意味着可以立刻 delete（仍然存在 use-after-free 的读取窗口）。 虽然执行 delete 的线程是唯一弹出了这个节点的线程，但其它线程可能仍然持有指向它的局部指针。具体路径：线程 T1 执行了 old_top = s->top（得到 A）并在计算 new_top = A->next 之前被抢占；与此同时 T0 弹出 A、delete A；T1 恢复后执行 A->next ⇒ 读取已释放内存。加锁版本之所以没有这个问题，恰恰因为”持有锁”隐含地告诉其它人”别碰这个节点”；无锁版本没有这种保护，因此需要 hazard pointer / epoch / 内存池 之类的回收协议来延迟释放。注意 delete 的位置（CAS 成功之后）根本不能解决这个竞态——竞态发生在别的线程的读上，而不是发生在执行 delete 的线程上。

错误 2：ABA 问题依然存在，且 delete 让 ABA 更危险。 CAS 只比较指针值：T0 读到 old_top = A 后被抢占；T1 弹出 A、释放 A、又 new 出一个新节点（很可能就是同一地址 A，因为 glibc 的分配器会复用最近释放的块）、再 push(A)（此时 A 里存的是完全不同的数据）；T0 恢复后 CAS(&s->top, A, B) 成功（此刻 top 确实等于 A），于是把 top 设为 B —— 丢失了 T1 新压入的节点，栈结构被破坏，而 T0 返回的 A 里装的是别人的数据。更糟的是：如果被 delete 的地址被分配器交给了另一个数据结构（例如 O(1) 大小的对象被 malloc 复用），这个 CAS 会破坏完全无关的内存。

为什么单加 pop_count 不够：(1) 它只能消除 ABA（版本号让”C 等于 A”不再成立），对 use-after-free 毫无帮助——A->next 仍然可能读已释放内存，或者读到一个被复用的、完全不相关的对象；(2) 讲义指出，使用 pop_count 需要双字 CAS（DCAS），或者机器支持”把两个字段打包进一个字”的宽 CAS（cmpxchg8b/cmpxchg16b，或者 std::atomic<__int128>）；如果没有这样的硬件支持，就要退回到”用单个字打包 (tag, index)”的技巧，而这只在节点来自预分配池、地址可以压缩成小整数索引时才方便。(3) 即便版本号解决了 ABA，“何时可以释放”仍然是一个独立的、必须用额外协议解决的问题。

完整可行的方案（任选其一，或组合）：

• 方案 A（讲义解法一 + 内存池）：节点从预分配池（pool[idx]）中取，永不 free；栈顶用一个 64 位字打包 (tag:32, idx:32)；每次成功的 CAS 都把 tag 加一。一箭双雕：tag 使 ABA 不可能（相同 idx 必然伴随不同 tag），地址不复用使 use-after-free 不可能（内存从不归还）。代价：内存占用固定不可回收；tag 只有 32 位，理论上跑满 2^32 次操作后会回绕（工程上可用 48/16 位划分、定期检查，或承认其概率极低）。
• 方案 B（版本号 + hazard pointer，讲义解法二 + 解法三）：pop 时先发布 hazard = old_top，再重新校验 s->top == old_top，然后才读 old_top->next 并 CAS；CAS 成功后不直接 delete，而是 retire(old_top) 放进每线程的退休链表；当 retireListSize > THRESHOLD 时遍历所有线程的 hazard 槽位，只 delete 那些不等于任何 hazard 的节点（并且要在扫描后重新确认——因为 hazard 可能在扫描过程中被更新，标准实现会做第二遍扫描或用 -Wpedantic 级别的严格版本）。pop 失败路径上必须把 hazard = NULL。为什么安全：节点一旦被 CAS 摘链就不可达，任何线程要再引用它都必须先读 top 再沿链走，因此”扫描时刻没有 hazard 指向它”就意味着将来也不会有人引用它。
• 方案 C（工程折中）：如果不想处理回收，就把数据结构设计成”节点不回收“的形式（内存池 + 索引 + 版本号），或者干脆放弃无锁——讲义明确指出，在能独占机器的性能优化场景里，写得好的加锁代码可以与无锁代码一样快甚至更快，而且简单得多；只有在无法独占机器（数据库、Web 服务器）时才值得为 lock-free 的正确性论证付出这笔复杂性成本。

问题 3（定量判断：该不该改成细粒度/无锁？）：某服务维护一条有序链表，节点数 n = 1000，稳态下每个线程每次操作平均遍历 L = 500 个节点，共 P = 32 个线程，总操作数 M = 3.2×10^5 次插入。当前实现使用一把全局锁，测得吞吐约 22 K ops/s。有人建议改成：(i) 每节点一把锁（hand-over-hand）；(ii) 无锁 CAS 插入。已知参数：单线程无争用时一次锁操作（lock+unlock）≈ 12 ns，一次缓存行交接 t_line ≈ 80 ns，节点访问（指针追逐）≈ 90 ns/次且为依赖链。请分别给出两种方案的定量上界，判断哪个方案更可能有效，并指出必须先测量的两个量。

【答案】

先算当前实现的基线（验证”加线程无效”来自哪里）：

单次操作的关键路径 = L 次指针追逐 = 500 × 90 ns = 45 µs
（加上一次锁交接 ~160 ns，可忽略）
吞吐上界 = 1 / 45 µs ≈ 22.2 K ops/s   —— 与 P 无关！

算出来的 22.2 K ops/s 与实测的 22 K ops/s 完全吻合，这直接证明：当前的瓶颈不是”锁”，而是单次操作 Θ(L) 的依赖链延迟（指针追逐）；P = 32 个线程全部在同一个临界区里排队，加线程对吞吐毫无帮助（这正是 Amdahl 的串行部分 s → 1 的情形）。

(i) 每节点一把锁（hand-over-hand）：

Work（同步部分） = M × L × 2 次原子 RMW = 3.2e5 × 500 × 2 = 3.2e8 次
若每次原子 RMW 命中本地独占（无争用理想值）≈ 6 ns：
    纯同步时间 ≈ 3.2e8 × 6 ns = 1.92 s
即使把 lock+unlock 一对压到 12 ns 且完全并行（32 线程）：
    1.92 s / 32 ≈ 60 ms  —— 仍然远超"45 µs × M / (有效并发)"的乐观估计
吞吐上界（流水线模型）= min( P / (L·t_hop), 1 / t_hop )
    取 t_hop = 40 ns（乐观，无争用时）: 1/40 ns = 25 M ops/s（理想上界）
    取 t_hop = 240 ns（考虑 1000 个节点锁在 32 核间反复迁移，现实值）: ≈ 4.2 M ops/s

结论：理想上界（25 M ops/s）看着很美，比基线好 3 个量级；但它建立在”每步 2 次原子操作几乎零成本”的假设上，而该假设在本场景（n = 1000 个节点、锁字段与数据同行、32 核同时迁移缓存行）几乎必然被打破。因此方案 (i) 的现实收益是数量级级别的改善（4 M vs 22 K，约 190×），但远达不到理想值，而且风险在于伪共享：如果不做”锁与数据分离 / alignas(64)“处理，t_hop 可能恶化到 400 ns 以上，收益缩水到 30× 左右，并且代码复杂度与死锁论证成本显著上升。

(ii) 无锁 CAS 插入：

Work：遍历仍是 Θ(M·L) 次读（纯读，无原子操作），加上每操作一次成功 CAS + 期望失败次数
     插入点集中在 prev->next 这"一个"提交点上，故平均尝试次数 ≈ P/2 = 16（4.2 节模型）
     ⇒ M × 16 × 80 ns = 3.2e5 × 16 × 80 ns ≈ 0.41 s 的 CAS 争用时间
Span：单次操作 = L × 90 ns（指针追逐，不变）= 45 µs
吞吐上界 ≈ 1 / (Span 中的 CAS 提交部分) ；由于遍历本身并行，稳态吞吐 ≈ 1/(2×80 ns) ≈ 6.25 M ops/s

结论：方案 (ii) 比 (i) 更可能有效，原因有三：①遍历路径上没有原子操作（Θ(M·L) 次读全部是纯读，不产生一致性流量，也不破坏其它核的缓存行）；②提交点只有 prev->next 一处，即使有 16 次平均重试，其成本也只与 P 有关而与 L 无关；③不需要为每个节点增加锁字段，节点更小、缓存密度更高（讲义对无锁插入的总结：”No overhead of taking locks; No per-node storage overhead”）。但要注意：(ii) 如果只做插入而不做删除，实现简单；一旦要支持无锁删除，问题立刻变得极其困难（讲义：”Supporting lock-free deletion significantly complicates data-structure”，见 2.9 的图解 8 与 Harris 2001 / Fomitchev 2004），因此这个方案适用于”只插入”或”删除极少”的场景。

必须先测量的两个量：

1. 真实的 L（平均遍历长度）与节点访问延迟：用 PMU 计数器测每次操作的 LLC/DRAM 缺失数与平均内存延迟。如果 L × t_dram 确实主导总时间（本例中 45 µs vs 锁的 160 ns），那么两个方案的收益上限都被”指针追逐”锁死，真正的优化方向应该是换数据结构（哈希表 / B 树 / 跳表：把 L 从 500 降到 3–10），而不是改变同步方式——这是本题最重要的一条结论：当瓶颈是依赖链延迟时，改同步是治标，改数据结构才是治本。
2. 一致性流量 / 缓存行迁移次数（HITM 或 “cache line transfers” 计数）：它直接决定方案 (i) 中真实的 t_hop（是否存在伪共享）与方案 (ii) 中 CAS 的失败率（是否争用过度、是否需要 batching/backoff）。没有这个数字，就无法判断”25 M ops/s 的理想上界”和”4 M ops/s 的现实”之间那 5–10 倍的差距到底来自哪里。

补充判断（讲义的实践结论）：如果这个服务能独占机器（例如它是某个批处理任务），那么按讲义的观点，“写得好的加锁代码可以与无锁代码一样快（或更快），而且简单得多”——此时最该做的是换数据结构 + 保持粗粒度锁（先测量再优化）；只有在这个服务是多道程序环境（数据库/Web 服务器，线程会在临界区内被抢占、缺页、产生优先级反转与护航）时，为 lock-free 付出的复杂度才是划算的。