Lecture 16: Fine-Grained Locking and Lock-Free Programming（日期：Nov 20）

目录 · ← l15 · l17 →

Lecture 16: Fine-Grained Locking and Lock-Free Programming（日期：Nov 20）

概述：本讲前半部分从”实现锁”出发：先厘清死锁（deadlock）、活锁（livelock）、饥饿（starvation）三个易混淆术语，然后对比 test-and-set、test-and-test-and-set、ticket lock 等锁实现的性能特征（尤其是 cache coherence 流量）。后半部分转向”使用锁”：用细粒度锁（hand-over-hand locking）在有序链表中获得并行度，并介绍无锁（lock-free）数据结构的基础——单读单写队列、基于 CAS 的无锁栈，以及著名的 ABA 问题。本讲为下一讲”事务内存”（transactional memory）做铺垫：CAS 的本质作用就是检测”操作期间数据结构是否被其他线程修改过”。

一、核心概念与定义

1. Deadlock（死锁）

定义：系统中有若干操作尚未完成，但由于每个操作都持有着别的操作需要的资源，导致没有任何操作能继续推进的状态。死锁的必要条件有四条：mutual exclusion（互斥）、hold and wait（持有并等待）、no preemption（不可抢占）、circular wait（循环等待）。幻灯片强调：死锁和活锁关乎程序正确性；饥饿则主要是公平性问题。
现实类比：旧金山十字路口四辆车同时抢行、互不相让，谁都动不了（幻灯片原话：在 SF 死锁”happens all the time”）。更生动的例子是 National Geographic 那张蚂蚁围成圈的图：每只蚂蚁都在等前面的蚂蚁让路。
公式/图示：循环等待即资源依赖图中存在环：

线程 A ──持有──> 资源 R1 ──被 B 等待──> 线程 B ──持有──> 资源 R2 ──被 A 等待──> 线程 A
        （环！谁都无法继续）

计算机系统里的经典例子（幻灯片 Example 2）：两个线程互相往对方的有限 work queue 里塞消息，队满时发送方阻塞等待，于是 A 等 B 腾出空间、B 等 A 腾出空间，双双卡死。

2. Livelock（活锁）

定义：系统在不停地执行大量操作，但没有任何线程取得有意义的进展。典型计算机系统场景：操作不断 abort 然后重试（operations continually abort and retry），每次都失败。
现实类比：两个人面对面走在窄走廊里，同时向左让、又同时向右让，来回好几次谁也过不去——动作很多，但”让路”这件事毫无进展。
与死锁的区别：死锁是”谁也不动”；活锁是”大家都在动但白动”。两者都使程序无法完成，属于正确性问题。

3. Starvation（饥饿）

定义：系统整体在推进，但某些进程始终得不到资源、毫无进展的状态。幻灯片用交通图说明：黄车（左右方向）必须给绿车（上下方向）让路，绿车一辆辆通过，黄车一直停在原地。饥饿通常不是永久状态——绿车走完后黄车还能走。
现实类比：食堂打饭窗口永远被同一批人插队，后面的同学一直吃不上饭；但窗口总会轮到他们（只是可能很晚）。
与公平性的关系：饥饿是公平性问题而非正确性问题——程序最终能完成，只是某些线程被”饿”了很久。

4. Test-and-Set（测试并置位）

定义：一条原子指令 ts R0, mem[addr]：把 mem[addr] 的旧值装入 R0；如果旧值为 0，则把 mem[addr] 置为 1。它同时完成”读旧值 + 条件写”且不可被打断，是构建自旋锁的最小原语。
现实类比：食堂占座：看一眼座位是否空（读），如果空就立刻把书包甩上去占住（写）——”看一眼 + 占住”必须是瞬间完成的一个动作，否则两个人会同时坐下。
公式/图示：

ts R0, mem[addr]   // R0 = mem[addr];  if (mem[addr] == 0) mem[addr] = 1

5. Compare-and-Swap（CAS，比较并交换）

定义：原子地执行”若 dst 当前值等于 EAX，则把 dst 写成 src 并置标志位 ZF=1；否则把 EAX 更新为 dst 的当前值并置 ZF=0”。x86 上需加 lock 前缀才是原子的（lock cmpxchg dst, src）。它是几乎所有无锁算法的基础。
现实类比：对暗号开门：先报出你记忆中的暗号（期望值），如果门锁里的暗号没变，门就开了（且换成新暗号）；如果暗号变了，说明别人动过锁，你记下新暗号再试。
公式/图示（幻灯片原文语义）：

lock cmpxchg dst, src
if (dst == EAX) { ZF = 1; dst = src; }   // 比较成功：交换
else            { ZF = 0; EAX = dst; }   // 失败：把当前值读回 EAX

6. Fine-Grained Locking / Hand-over-Hand Locking（细粒度锁 / 手递手锁）

定义：把一把”全局数据结构锁”拆成每个节点一把锁；遍历链表时，先锁住前驱节点，再锁住下一个节点，然后释放前驱的锁——像攀岩者手递手抓住下一个握点才松开上一个（幻灯片配图正是 American Ninja Warrior）。这样两个线程可以同时操作链表的不同区域，获得并行度。
现实类比：山路上”手递手”接力护送：只有当前后两个路段都有人把守时才放行车辆；把守范围跟着车队移动，而不是整条山路只设一个关卡。
图示（线程 0 删除 11、线程 1 删除 10 时各持两把相邻锁）：

        [T0][T0]              [T1][T1]
3 → 5 → 10 → 11 → 18     3 → 5 → 10 → 18
      (T0: prev,cur)       (T1: prev,cur)

7. Ticket Lock（取号锁）

定义：维护 next_ticket（发号器）与 now_serving（当前叫号）两个计数器。获取锁 = 原子地 atomic_increment(&next_ticket) 取一个号，然后纯读地自旋等待 now_serving == my_ticket；释放锁 = now_serving++。获得锁的过程不再需要原子操作（只需要读），且严格 FIFO，天然公平。
现实类比：银行/医院取号叫号：进门先取号，然后坐着等叫号屏变成自己的号；办完业务下一个号自动顶上。所有人按取号顺序被服务，不会有人插队。
特点：每次释放锁只有一次失效（one invalidation per lock release），互连流量为 O(P)，远优于 test-and-set 族。

8. Blocking Algorithm（阻塞式算法）

定义：一个算法允许某个线程无限期地阻止其他线程完成对共享数据结构的操作。典型例子：线程 0 拿到链表某节点的锁后被操作系统换出（或被 page fault 卡住、崩溃、极慢），其他线程就再也无法操作该数据结构——尽管线程 0 并没有在修改它。只要用了锁，无论锁是自旋还是让出 CPU 实现，算法就是阻塞式的。
现实类比：一个人堵住唯一的门后去接电话，其他人只能在门外干等，哪怕他根本不在动那扇门。

9. Lock-Free（无锁）

定义：非阻塞算法中，若保证至少有一个线程（some thread）能推进（systemwide progress，系统级进展），则称该算法是 lock-free。关键点：不允许”某线程恰好在不巧的时刻被抢占而导致整个系统停止进展”。注意：这个定义不保证任何单个线程不被饿死——可能某个线程永远失败重试，但系统整体一直在前进。
现实类比：一扇双向弹簧门，多人同时推门：无论怎么抢，总有人能把门推开（可能同一人推开好多次，另一个人一直没成功——但”门在动”就是系统级进展）。
公式/图示：lock-free 的无锁栈 push/pop 见代码示例 4；核心不变量：”只要没有其他线程修改过栈顶，我的修改就可以成功落地”。

10. Single-Reader/Single-Writer Queue（单读单写队列）

定义：只允许一个生产者、一个消费者同时访问的队列。因为 head 只被消费者写、tail 只被生产者写，两个线程从不互相同步、从不等待对方：队列空时 pop 直接返回 false，队满时 push 直接返回 false。前提是顺序一致性内存（或加 fence，或用 C++11 atomic）。
现实类比：单车道隧道：只有一辆车能进、只有一辆车能出，出入口各自独立管理，进出的车不需要互相打招呼——只要各自看清”隧道里有没有位置/有没有车”。
图示（有界环形缓冲）：

        head                     tail
         │                        │
         ▼                        ▼
data: [ ][ ][ 3 ][ 10 ][ ][ ]...（N 个槽位，环形）
       空: head == tail；满: tail == MOD_N(head - 1)

11. ABA Problem（ABA 问题）

定义：CAS 只比较”值”，无法区分”值从头到尾没变过”与”值从 A 变到 B 又变回 A”。在无锁栈中，线程 0 读到 old_top = A 后被抢占；期间其他线程弹出 A、修改 A、再把 A 压回去、又压入 D；线程 0 恢复后 CAS 发现 top 仍等于 A 而成功，把 top 设成了 B，导致 D 被静默丢失、栈结构被破坏。注意幻灯片特别提醒：这里的 A、B、C、D 是节点地址，不是节点里存的值；且不要与 ABBA 问题混淆。
现实类比：你确认”门是开着的”就走进去，却没注意到门在你确认之后被关上又打开了——你以为状态没变，其实世界已经转了一圈。
图示：见代码示例 5 的完整时间线图。

12. Hazard Pointer（危险指针）

定义：无锁数据结构中避免 use-after-free 的高级技巧：每个线程维护一个”当前正在访问、绝不能被释放”的指针（hazard pointer）；被弹出的节点不立即 delete，而是进入每线程的 retire list；当 retire list 超过阈值时，扫描其中所有节点，只有没有任何线程的 hazard pointer 指向的节点才真正释放。
现实类比：工地上给正在施工的墙挂”施工中，请勿拆除”的警示牌：拆墙前先确认所有警示牌都没指着这面墙。
用途：解决无锁栈中”另一个线程可能已经 free 掉我即将解引用的 old_top”的悬垂引用问题。

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

示例 1：从 test-and-set 到 ticket lock——三种锁实现对比（C）

// ---- 1) test-and-set 自旋锁：每次尝试都发 BusRdX，流量巨大 ----
typedef int lock;
void Lock1(lock* l) {
    while (test_and_set(l) != 0);   // 一直尝试：原子"读+写1"
}
void Unlock1(lock* l) {
    *l = 0;                          // 直接写 0 释放
}

// ---- 2) test-and-test-and-set 锁：先自旋"读"，读到 0 才尝试原子获取 ----
void Lock2(lock* l) {
    while (1) {
        while (*l != 0);             // 纯读自旋：锁被持有时只读本地缓存
        if (test_and_set(*l) == 0)   // 锁释放了，才发一次原子尝试
            return;
    }
}
void Unlock2(lock* l) {
    *l = 0;
}

// ---- 3) ticket lock：取号 + 等叫号，FIFO 公平 ----
struct lock {
    int next_ticket;
    int now_serving;
};
void Lock3(lock* l) {
    int my_ticket = atomic_increment(&l->next_ticket); // 原子取号
    while (my_ticket != l->now_serving);               // 纯读等待叫号
}
void Unlock3(lock* l) {
    l->now_serving++;                                  // 叫下一个号
}

【代码做了什么？】

Lock1 是最朴素的 test-and-set 锁：每次循环都执行原子”测试并置位”。幻灯片用 coherence 流量图展示了它的灾难：当 P1 持有锁时，P2、P3 等每个等待者每尝试一次就发一次 BusRdX（把锁变量所在 cache line 置为 1 并失效别人的副本），导致互连网络上无效化请求风暴。
Lock2 先做一次普通读自旋（while (*l != 0)），只有当观察到锁被释放（读到 0）时才真正发一次 test_and_set。幻灯片分析：每个等待者每次锁释放只产生一次失效，共 O(P) 次失效；若所有处理器都把锁缓存了，则总流量是 O(P²)。
Lock3 把”抢锁”变成”取号 + 等号”：atomic_increment 是唯一需要原子性的操作；等号阶段是纯读（my_ticket != l->now_serving 不产生原子流量），释放时 now_serving++ 产生一次失效，互连流量仅 O(P)，且保证先来先服务。

【并行机制解说】

三个版本都依赖 cache coherence 协议来传播锁状态（这正是幻灯片先复习 MSI 状态转移图的原因）：test_and_set 本质是”读-改-写”，必须以 BusRdX 形式独占 cache line 才能原子完成，因此每次尝试都会把其他处理器持有的副本失效。
对应概念：本示例对应核心概念 4（test-and-set）、6（细粒度锁的”降低流量”动机）、7（ticket lock）。幻灯片给出的锁的理想特征清单是评价标准：低延迟（无竞争时快速获取）、低互连流量（高竞争时依次获取）、可扩展（流量随处理器数合理增长）、低存储开销、公平（按请求顺序获取，避免饥饿）。简单 test-and-set：低竞争下延迟低、但流量高、扩展性差、存储仅一个 int、无公平性条款；ticket lock 补上了公平性。

示例 2：hand-over-hand 细粒度锁——有序链表插入（C）

struct Node {
    int   value;
    Node* next;
    Lock* lock;        // 每节点一把锁
};

struct List {
    Node* head;        // 哨兵节点
    Lock* lock;        // 列表级锁：只用于"取第一个节点"的瞬间
};

void insert(List* list, int value) {
    Node* n = new Node;
    n->value = value;
    // （幻灯片为简洁省略了"插入表头"的边界处理）

    Node* prev, *cur;
    lock(list->lock);
    prev = list->head;
    lock(prev->lock);          // 锁住第一个节点
    unlock(list->lock);        // 列表级锁立刻释放

    cur = prev->next;
    if (cur) lock(cur->lock);  // 锁住第二个节点（手递手第一步）

    while (cur) {
        if (cur->value > value)
            break;             // 找到插入位置
        Node* old_prev = prev;
        prev = cur;
        cur = cur->next;
        unlock(old_prev->lock); // 释放身后的锁
        if (cur) lock(cur->lock);// 锁住前面的新节点
    }
    n->next = cur;             // 在 prev 与 cur 之间插入
    prev->next = n;
    unlock(prev->lock);
    if (cur) unlock(cur->lock);
}

【代码做了什么？】

遍历从哨兵 head 开始，全程保证手里最多握着两把相邻节点的锁（prev 和 cur）。
每前进一步：先锁住下一个节点，再释放上一个节点的锁——”手递手”。
找到插入点后：n->next = cur; prev->next = n; 完成插入，最后释放手里两把锁。
注意 list->lock 只保护”从 head 出发”这一个瞬间（防止并发线程同时从表头开始遍历），一旦锁住第一个节点就立即释放。

【并行机制解说】

对应概念：细粒度锁（概念 6）。它和示例 1 的”全局锁”对比：全局单锁把所有链表操作串行化（幻灯片：single global lock——简单正确但操作被串行化，限制并行性能）；细粒度锁让操作链表不同区域的线程并行推进。
为什么一定不会死锁（幻灯片留给学生的自检题）：所有线程都沿着同一个方向（表头→表尾）按一致的顺序获取锁，且一次最多持有两把、总是”先获取更靠前的锁，再获取更靠后的锁”。因此资源依赖图不可能出现环，circular wait 条件不成立——立刻就能断定代码无死锁。
代价：每步遍历都要取锁/放锁（额外指令，且遍历变成”带内存写”的操作）、每节点多一份锁的存储；幻灯片提示的折中方案：像选择任务粒度一样，把链表分成若干段、每段一把锁，用部分并行度换更低的锁开销。
幻灯片还留了一个挑战题：insert() 其实可以进一步优化——插入操作只修改 prev->next，并不需要修改 cur，因此可以不必持有 cur 的锁（delete 才需要两把锁）。

示例 3：单读单写有界队列——零同步的无锁队列（C）

#define N 1024                       // 队列容量（2 的幂）
#define MOD_N(x) ((x) & (N - 1))     // 环形下标取模

struct Queue {
    int data[N];
    int head;   // 队头：下一个要取出的元素位置（仅消费者写）
    int tail;   // 队尾：下一个空闲槽位（仅生产者写）
};

void init(Queue* q) { q->head = q->tail = 0; }

// 队列满时返回 false（tail 紧跟在 head 后面一格）
bool push(Queue* q, int value) {
    if (q->tail == MOD_N(q->head - 1))
        return false;
    q->data[q->tail] = value;
    q->tail = MOD_N(q->tail + 1);
    return true;
}

// 队列空时返回 false（head 追上 tail）
bool pop(Queue* q, int* value) {
    if (q->head != q->tail) {
        *value = q->data[q->head];
        q->head = MOD_N(q->head + 1);
        return true;
    }
    return false;
}

【代码做了什么？】

push 先检查是否满：tail == MOD_N(head - 1)（环形缓冲里 tail 紧贴在 head 后面一格表示满）；不满则写数据、推进 tail。
pop 检查是否空：head != tail；不空则读出 data[head]、推进 head。
全程没有任何锁、没有原子操作、没有等待：满/空时直接返回失败，由调用方决定重试或放弃。

【并行机制解说】

对应概念：单读单写队列（概念 10）。为什么零同步也安全？因为 head 只有一个写者（消费者）、tail 只有一个写者（生产者），两个线程从不写同一个变量；读对方的变量（生产者读 head 判断满、消费者读 tail 判断空）在顺序一致性（或正确 fence / C++11 atomic）下看到的是完整的最新值。这就是”单读单写”约束的价值：它把共享状态拆成两半，各归一方写，从而消除竞争。
幻灯片强调：这里假设顺序一致内存（或加适当 memory fences，或用 C++11 atomic<>）；现代弱一致性硬件上不能裸奔。这属于无锁编程（概念 9）的特例——两个线程互不阻塞对方。
幻灯片还给出无界版本（Dr. Dobbs 来源）：head 指向队首元素之前的节点，tail 指向最后加入的元素，生产者 push 时顺带用 reclaim 指针回收已经越过 head 的节点——节点的分配与释放都由生产者线程完成，这是它能保持无锁的关键。

示例 4：基于 std::atomic 的无锁栈 push/pop（C++11）

#include <atomic>

struct Node {
    Node* next;
    int   value;
};

class LockFreeStack {
public:
    void push(Node* n) {
        while (true) {
            Node* old_top = top.load(std::memory_order_relaxed);
            n->next = old_top;                 // 新节点指向当前栈顶
            if (top.compare_exchange_weak(old_top, n))
                return;                        // CAS 成功：栈顶没被改过
            // CAS 失败：有其他线程动过 top，重读再试
        }
    }

    Node* pop() {
        while (true) {
            Node* old_top = top.load(std::memory_order_relaxed);
            if (old_top == nullptr)
                return nullptr;                // 空栈
            Node* new_top = old_top->next;     // 预读下一个节点
            if (top.compare_exchange_weak(old_top, new_top))
                return old_top;                // CAS 成功：弹出 old_top
        }
    }

private:
    std::atomic<Node*> top{nullptr};
};

【代码做了什么？】

push(n)：把新节点的 next 指向当前 top，然后 CAS 把 top 从 old_top 换成 n；若 CAS 失败说明读 top 之后有别的线程改了栈，循环重试。
pop()：读 top 得 old_top（空栈返回 nullptr），预读 old_top->next 作为 new_top，CAS 把 top 换成 new_top；成功则返回弹出的节点。
主思想（幻灯片原话）：只要没有其他线程修改过栈，这个线程的修改就可以进行——CAS 就是”检查是否被修改过”的那一步。

【并行机制解说】

对应概念：lock-free（概念 9）与 CAS（概念 5）。与细粒度锁的关键区别（幻灯片特别指出）：细粒度锁是”锁住数据结构的一部分”，而无锁实现根本不对数据结构加锁——线程通过 CAS 的返回值来确认自己的操作是否基于最新状态。
正确性论证：任何时候最多只有一个线程的 CAS 能成功，因此栈的”全局进展”有保证（失败者会重试，系统不会被某个被抢占的线程卡死）；但该定义不保证单个线程不饿死。
幻灯片给出的注意事项，这里必须诚实标注：std::memory_order_relaxed 在实际代码中通常不够，需要 acquire/release 语义或 fence 来保证 n->next = old_top 的可见性；此外本实现还没有处理 ABA 问题与内存回收（见示例 5 与核心概念 12）。可以用 is_lock_free() 检查当前平台上 atomic<Node*> 是否真的由硬件原子指令实现（否则可能退化为 mutex）。

示例 5：ABA 问题完整时间线演示（C++ 伪代码 + 注释）

// 演示 ABA 问题：CAS 只比较"值"，分不清"一直没变"与"变了又变回来"。
// 注意：A、B、C、D 是节点的【地址】，不是节点里的值！

// 初始栈：top → A → B → C
// 线程 0 开始 pop()：
Node* old_top = top;        // 线程 0 读到 old_top = A（地址）
Node* new_top = old_top->next;   // new_top = B
// 【此刻线程 0 被抢占！】

// 线程 1 执行 pop()：
//   CAS(&top, A, B) 成功  → top → B → C          （A 被弹出）
//   线程 1 修改节点 A：A->value = 42             （复用被弹出的节点！）
//   线程 1 执行 push(A)：
//     CAS(&top, B, A) 成功 → top → A → B → C     （A 又被压回去）
//   线程 1 执行 push(D)：
//     CAS(&top, A, D) 成功 → top → D → A → B → C

// 【线程 0 恢复执行】：
//   CAS(&top, A, B)  →  top 的当前值【又是 A】！CAS 成功！
//   → top → B → C   （节点 D 被静默丢失，栈被破坏！）

【代码做了什么？】

这是一段”叙述式”演示：把示例 4 的 pop() 拆开，逐行标注线程 0 被抢占期间线程 1 做了什么。关键在最后一步：线程 0 的 CAS 比较的期望值是地址 A，而 top 恰好又等于 A（因为 A 被弹出去又压回来了），于是 CAS 误判”没人动过栈”而成功。

【并行机制解说】

对应概念：ABA 问题（概念 11）。它揭示 CAS 的语义盲区：CAS 无法区分”对象没变”与”对象变了又变回原样”。ABA 的名字来自值的变化轨迹 A → B → A。
幻灯片给出的两条解决路径：
1. 计数器方案：给栈加一个 pop_count，每次 pop 都递增；用 double compare-and-swap（DCAS）或 doubleword CAS 同时比较 (top, pop_count) 两个值，只有两者都未变才算成功。x86 支持 cmpxchg8b（一次比较两个 32 位值）和 cmpxchg16b（两个 64 位值），把 top 和 pop_count 连续放置即可用一条指令实现。
2. 节点分配/复用策略：精心设计分配器，保证”被弹出的节点地址不会这么快被重新压回栈顶”（例如不立即复用、延迟回收）。
幻灯片还补充了另一个问题：即使解决了 ABA，pop() 里 old.top->next 可能在解引用前已被其他线程 delete——即引用已释放内存。进阶解法就是 hazard pointer（概念 12）：弹出的节点先进 retire 列表，只有确认没有任何线程的 hazard pointer 指向它时才真正 delete。

三、关键要点

死锁四条件缺一不可：mutual exclusion、hold and wait、no preemption、circular wait。锁实现/使用中的死锁都可通过”破坏其中一条”来避免，例如细粒度锁中”所有线程按同一方向、一致顺序获取锁”直接消灭循环等待。
锁的性能关键在于 coherence 流量：test-and-set 每次尝试都发 BusRdX（流量灾难）；test-and-test-and-set 把每次锁释放的失效降到 O(P)、总流量 O(P²)；ticket lock 每次释放仅一次失效（O(P) 流量）且天然公平——但公平性之外的理想特征还包括低延迟、低流量、可扩展、低存储。
细粒度锁以复杂度换并行度：hand-over-hand 让不同链表区域的操作并行，代价是每步的锁开销、每节点的存储开销和正确性难度；折中方案（分段锁）与”任务粒度选择”是同一个权衡。
lock-free ≠ 无竞争：lock-free 保证”系统级进展”（至少一个线程推进），但不保证单个线程不饿死；无锁设计并不消除竞争——高竞争下 CAS 会反复失败导致自旋重试（幻灯片 Summary 原话）。
CAS 是”我操作期间别人动过没有”的探测器：这正是下一讲事务内存的伏笔——事务内存把这个机制推广为”推测整个操作能成功，若被其他线程修改则 abort 重来”。

四、常见陷阱与注意事项

把 ABA 误当成”不可能发生”或”只是理论问题”：ABA 在节点被弹后又压回（地址复用）的真实场景中极易发生；幻灯片特意注明 A/B/C/D 是地址而非值，并提醒不要与 ABBA 问题混淆。
无锁代码忘记内存回收/内存顺序：只写 CAS 循环还不够——old_top->next 可能指向已释放内存（需要 hazard pointer 等方案），现代弱一致性硬件上还必须有 fence 或 C++11 acquire/release 语义；幻灯片明确”仍然需要 appropriate memory fences on modern relaxed consistency hardware”。
CAS 循环在高竞争下”活锁”：所有线程同时抢栈顶时 CAS 反复失败、不断重试，系统在”执行大量操作”但推进缓慢——这正是 livelock 的雏形（幻灯片对 livelock 的计算机系统例子就是”operations continually abort and retry”）。
细粒度锁的正确性想当然：要精确判断”哪些步骤必须互斥”（例如删除节点必须同时锁 prev 和 cur，插入只需锁 prev）；否则会出现幻灯片演示的两类损坏：两个 insert 同时算得相同 prev/cur 导致一次插入丢失，insert 与 delete 并发导致插入节点指向已删除节点。
以为无锁一定更快：幻灯片引用 Hunt 2011 的测量：无锁队列/链表的运行时间以 pthread mutex 为基准归一化后可能高于 1——在”只有你的程序使用这台机器”的典型优化场景（科学计算、图形、ML、数据分析）里，写得好、带锁的代码常常与无锁一样快甚至更快、而且简单得多；无锁的价值主要出现在大量线程、critical section 内可能发生 page fault/被抢占的场合（数据库、web server），因为锁在那里会引发 priority inversion、convoying、临界区内崩溃等问题。

五、思考题（带答案）

Q1：幻灯片问：在 test-and-set 锁的 coherence 流量图中，运行在 P1 上的线程持有锁多长时间？P1 的 cache 在哪些时刻含有锁变量的有效副本？ A1：P1 从它那次成功的 test-and-set（BusRdX 把线置 1 并获得锁）开始持有锁，直到它执行 st mem[addr], #0 释放锁。P1 的 cache 在成功获得锁的那次 BusRdX 之后到其他处理器发起 BusRdX 使它失效之前，含有有效副本；之后它的副本被置为 Invalid，直到它再次读/写锁变量（释放时重新获得独占）。这也解释了为什么 P1 释放锁时还要”等总线”——互连争用会延长锁转移时间。

Q2：为什么 hand-over-hand 链表代码”立刻就能断定无死锁”？如果把遍历方向改成”有的线程从表头往表尾、有的线程从表尾往表头”，还会无死锁吗？ A2：因为所有线程都按表头→表尾的同一顺序获取锁（先锁更靠前的节点），且一次最多持有两把、总是先获取下一把再释放上一把，资源依赖图不可能成环（circular wait 不成立）。若允许反向遍历，两个相向而行的线程可能各自持有一把”对方下一步需要”的锁，循环等待成立，就可能死锁——这正是”系统级锁顺序策略”（lock ordering）要解决的问题。

Q3：为什么 ticket lock 的”等号”阶段不需要原子操作？它相比 test-and-test-and-set 还多了什么好处、代价是什么？ A3：等号阶段只读 now_serving（读操作天然安全，多个线程可同时读）；唯一需要原子性的是取号时的 atomic_increment(&next_ticket)。好处：每次释放只产生一次失效（O(P) 流量）且 FIFO 公平、无饥饿。代价：比 test-and-test-and-set 多一个计数器（存储开销略增），且每个线程都要先取号——在竞争极低时多了一次原子自增的开销。

Share on

Bluesky Facebook LinkedIn Mastodon X (formerly Twitter)

Runguo Li