锁与同步机制完全指南

一份从硬件基础到无锁数据结构、覆盖用户态与内核态的系统性参考。
阅读建议：第 1–3 部分是地基，务必读；第 4–8 部分按需查阅；第 10 部分（实践）和第 11 部分（延伸阅读）随时回看。

目录

1. 并发的根本问题
2. 硬件基础
3. 原子操作与无锁基础
4. 自旋锁家族
5. 阻塞锁
6. 读写分离
7. 协调原语
8. 无锁数据结构与内存回收
9. Linux 内核同步原语速览
10. 工程实践
11. 延伸阅读

1. 并发的根本问题

1.1 三个独立的问题：原子性、可见性、有序性

很多人把“线程安全”笼统看成一件事，其实并发 bug 来自三个互相独立的问题：

• 原子性（atomicity）：一个操作要么全做要么不做，中间状态不能被其他线程看到。counter++ 不是原子的——它是 load、add、store 三步，两个线程可能都读到旧值，各加一，最后只加了一次（更新丢失，lost update）。
• 可见性（visibility）：一个核写的值，另一个核什么时候能看到。由于每个 CPU 有自己的 store buffer 和 cache,A 核写了变量，B 核可能在相当长一段时间里还读到旧值。
• 有序性（ordering）：编译器和 CPU 都会为了性能重排指令。你写的 a=1; flag=1;，别的核可能先看到 flag=1 再看到 a=1，于是基于 flag 判断 a 已就绪的逻辑就崩了。

锁之所以“管用”，是因为它同时解决了这三个问题：临界区内的操作对外表现为原子；解锁带 release 语义保证写出去可见；acquire/release 语义阻止了关键重排。理解这一点，后面所有机制都能归位——它们无非是在这三个维度上做不同取舍。

1.2 竞态条件与临界区

竞态条件（race condition）：程序的正确性依赖于多个线程的相对执行时序。数据竞争（data race） 是其中一种：两个线程并发访问同一内存，至少一个是写，且没有同步——这是 C/C++/Rust 里的未定义行为（UB）。注意二者不等价：用原子操作可以消除 data race，但逻辑上的 race condition（比如 check-then-act 的 TOCTOU）仍可能存在。

临界区（critical section）：访问共享资源、必须互斥执行的代码段。同步的核心目标就是保护临界区。

1.3 互斥的形式化标准（Dijkstra）

一个正确的互斥机制必须满足三条：

1. 互斥（mutual exclusion）：任意时刻最多一个线程在临界区。
2. 前进（progress）：没有线程在临界区时，想进入的线程不能被无限期阻挡（不能因为无关线程而卡死）。
3. 有限等待（bounded waiting）：一个线程请求进入后，其他线程进入临界区的次数有上界（防饥饿，fairness）。

后面看 ticket lock vs TAS spinlock 的区别，本质就是 ticket lock 满足 bounded waiting 而朴素 TAS 不满足。

2. 硬件基础

不懂硬件就写不对锁。这一部分是后面一切的物理前提。

2.1 缓存一致性（cache coherence） 与 MESI

现代多核每个核有私有的 L1/L2 cache。同一份内存可能同时缓存在多个核里，缓存一致性协议保证大家看到的不会自相矛盾。主流是 MESI（及其变体 MESIF/MOESI），缓存行（cache line，通常 64 字节） 有四种状态：

• M (Modified)：本核独占且已修改，内存里是脏的。
• E (Exclusive)：本核独占，与内存一致。
• S (Shared)：多核共享只读副本。
• I (Invalid)：无效。

关键推论：写一个共享变量代价高。要写处于 S 状态的行，必须先发 invalidate 让其他核的副本失效，拿到 E/M 才能写。这就是为什么“多个核频繁写同一个变量”会极慢——cache line 在各核间反复弹跳（cache-line bouncing / ping-pong）。后面 TAS spinlock 的 TTAS 优化、ticket lock 的扩展性问题、rwlock 的 reader-count 抖动，全都是这一条的体现。

2.2 False Sharing（伪共享）

两个逻辑上无关的变量恰好落在同一条 cache line 上，即使线程各写各的，也会因为共享同一行而互相 invalidate，性能暴跌。解决办法是 cache line 对齐 / padding:

struct percpu_counter {
    atomic_long_t count;
    char pad[64 - sizeof(atomic_long_t)];  // 撑满一条 cache line
} __attribute__((aligned(64)));

C++ 里用 alignas(std::hardware_destructive_interference_size)。这是高性能并发代码里最常见也最隐蔽的坑之一。

2.3 内存模型（memory model）：强序 vs 弱序

CPU 允许把对不同地址的访存重排，各架构“允许重排到什么程度”就是它的内存模型。两类极端：

• x86 / x86-64:TSO (Total Store Order)，强序。只允许一种重排：StoreLoad（后面的 load 可能越过前面的 store，因为 store 进了 store buffer 还没刷出去）。LoadLoad / LoadStore / StoreStore 都不会重排。所以 x86 上很多“看起来没加屏障也能跑”的代码碰巧是对的。
• ARM / ARM64 / RISC-V / POWER：弱序（weakly ordered）。几乎所有重排都被允许（只保证同地址的依赖序、控制依赖等少数情况）。你必须显式插入屏障或用带语义的指令，否则就是错的——而且 bug 在 x86 上根本复现不出来，只在 ARM 上偶发，极难定位。

对做 ARM 平台（鲲鹏 / A800 等）的人：这是头号雷区。一段在 x86 上跑了十年的并发代码，移植到 ARM 可能就因为缺一个 barrier 而偶发崩溃。

2.4 内存屏障（memory barrier / fence）

屏障约束它两侧访存的重排：

• acquire 屏障：屏障之后的读写不能重排到屏障之前。典型用在“加锁 / 读取标志位发现资源就绪”之后，确保后续访问看到的是最新数据。
• release 屏障：屏障之前的读写不能重排到屏障之后。典型用在“解锁 / 置位就绪标志”之前，确保临界区的写已经完成并可见。
• full barrier (seq_cst)：两个方向都禁止重排，最强也最贵。

acquire/release 成对使用构成"happens-before"：线程 A 在 release 之前的所有写，对在对应 acquire 之后的线程 B 可见。这是无锁编程的基本积木。

底层指令：x86 的 mfence/lfence/sfence、lock 前缀；ARM 的 DMB/DSB/ISB，以及带 acquire/release 语义的 LDAR/STLR、LDAXR/STLXR。

2.5 原子指令：硬件提供的同步原语

所有锁最终都建立在几条硬件原子指令上：

• Test-and-Set (TAS)：原子地“把某地址置 1 并返回旧值”。最古老的互斥原语。
• Compare-and-Swap (CAS):CAS(addr, expected, new) —— 若 *addr == expected 则写入 new 并返回成功，否则失败。这是最通用的原子原语，无锁算法的核心。x86 是 cmpxchg。
• Fetch-and-Add (FAA)：原子地“加并返回旧值”。ticket lock 取号、计数器都用它。x86 是 xadd。
• Load-Linked / Store-Conditional (LL/SC):RISC 风格（ARM 的 LDXR/STXR、RISC-V 的 lr/sc）。LL 读并标记地址，SC 仅当期间无人写过该地址才写入成功。用一对 LL/SC 循环可以实现 CAS、FAA 等任意 RMW。
• ARM LSE (Large System Extensions, ARMv8.1+)：直接提供 LDADD/SWP/CAS 等单指令原子操作，在高竞争下比 LL/SC 循环扩展性好得多（LL/SC 在竞争时会反复 SC 失败重试）。鲲鹏等服务器芯片支持，编译时加 -march=armv8.1-a 或更高可让编译器生成 LSE 指令。

CAS 的本质局限是 ABA 问题(§3.4)，记住这一点。

3. 原子操作与无锁基础

3.1 原子类型与“轻量”的真正含义

atomic_t（内核）/ std::atomic<T>(C++)/ _Atomic(C11)把上面的硬件原子指令封装成可用的类型。所谓“原子操作轻量”，指的是无竞争时它就是几条 CPU 指令，不进内核、不切上下文。这点要和“等待策略”分开看：原子操作本身不提供“等待”能力，它只能告诉你状态、或一次性地改状态；一旦你需要等待，就得叠加自旋或睡眠，那是另一个维度的开销。

3.2 memory_order：C++/C11 的内存序

std::atomic 的每个操作都可以指定内存序，从弱到强：

经验法则：能用 acquire/release 就别用 seq_cst，尤其在 ARM 上 seq_cst 的屏障开销明显。但前提是你真的推理清楚了 happens-before；没把握时 seq_cst 是安全的保守选择。

3.3 CAS 循环：无锁的基本写法

无锁更新一个值的标准范式是“读—算—CAS—失败重试”:

// 无锁地对一个值做任意变换 f
uint64_t old, neo;
do {
    old = atomic_load_explicit(&v, memory_order_acquire);
    neo = f(old);                       // 基于旧值算出新值
} while (!atomic_compare_exchange_weak_explicit(
            &v, &old, neo,
            memory_order_acq_rel, memory_order_acquire));

compare_exchange_weak 允许“伪失败”（在 LL/SC 平台上即使值相等也可能 SC 失败），所以必须放在循环里；_strong 不会伪失败，但在循环里通常用 weak 性能更好。

3.4 ABA 问题

CAS 只比较值。如果一个线程读到值 A，期间另一线程把它改成 B 又改回 A，第一个线程的 CAS 会“成功”——但世界其实已经变了。在无锁链表/栈里这会导致已释放节点被复用、指针指向被回收的内存。

解决方案：

• Tagged pointer / 版本号：把指针和一个单调递增的计数打包（如用双字 CAS cmpxchg16b，或在指针高位塞 tag），每次修改 tag+1,A→B→A 时 tag 不同，CAS 失败。
• Hazard pointer / epoch-based reclamation：从根本上推迟内存回收，保证 CAS 期间节点不会被 free（见 §8.3）。

3.5 进展保证：lock-free vs wait-free vs obstruction-free

“无锁”是个被滥用的词，严格分三档（从弱到强）:

• Obstruction-free：若某线程单独运行（其他线程都暂停），它能在有限步内完成。最弱，可能活锁。
• Lock-free:整个系统总有线程能前进（不会全体卡死），但单个线程可能饿死（一直 CAS 失败重试）。M-S 队列、Treiber 栈属于这档。
• Wait-free:每个线程都能在有限步内完成，无饥饿。最强也最难实现，代价通常很高，实际用得少。

“无锁”在工程语境通常指 lock-free。它的好处不是“一定更快”——高竞争下 CAS 重试可能比锁还慢——而是无死锁、无优先级反转、对不能阻塞的上下文友好（如中断里）。

4. 自旋锁家族

共同点：拿不到锁就忙等（busy-wait），不睡眠。适合临界区极短、不能 sleep 的上下文。共同代价：等待时烧 CPU，且持锁期间（内核里）通常关抢占。

4.1 朴素 TAS spinlock

typedef struct { atomic_int locked; } spinlock_t;   // 0=free 1=held

void spin_lock(spinlock_t *l) {
    while (atomic_exchange_explicit(&l->locked, 1, memory_order_acquire))
        ;                                            // 自旋直到换到旧值 0
}
void spin_unlock(spinlock_t *l) {
    atomic_store_explicit(&l->locked, 0, memory_order_release);
}

问题：所有 waiter 都在持续执行 exchange（一个写操作），每次都试图把锁行拉成 E/M 状态，导致 cache line 在所有等待核之间疯狂弹跳，竞争越激烈越慢。

4.2 TTAS(Test-and-Test-and-Set)

先只读自旋，看到锁可能空闲了才发起 exchange:

void spin_lock_ttas(spinlock_t *l) {
    for (;;) {
        while (atomic_load_explicit(&l->locked, memory_order_relaxed))
            cpu_relax();                             // 只读自旋,命中本地 S 副本
        if (!atomic_exchange_explicit(&l->locked, 1, memory_order_acquire))
            return;                                  // 抢到了
    }
}

只读自旋命中各核本地的 Shared 副本，不产生写流量；只有锁释放（invalidate 一次）后大家才去抢。cpu_relax() 在 x86 是 PAUSE、ARM 是 YIELD，降低功耗、缓解流水线、对 SMT 友好。这是写 spinlock 的最低标准。

4.3 Ticket lock

TTAS 仍不公平（锁释放时一拥而上，可能有线程长期抢不到）。ticket lock 用“取号—叫号”实现 FIFO:

typedef struct { atomic_uint next, owner; } ticketlock_t;

void ticket_lock(ticketlock_t *l) {
    unsigned my = atomic_fetch_add_explicit(&l->next, 1, memory_order_relaxed);
    while (atomic_load_explicit(&l->owner, memory_order_acquire) != my)
        cpu_relax();
}
void ticket_unlock(ticketlock_t *l) {
    unsigned next = atomic_load_explicit(&l->owner, memory_order_relaxed) + 1;
    atomic_store_explicit(&l->owner, next, memory_order_release);  // 只有持有者写 owner
}

公平、无饥饿。但所有 waiter 都自旋在同一个 owner 上，每次解锁（写 owner）会 invalidate 所有等待核的缓存，产生 O(N) 的缓存一致性流量。核数一多，handoff 延迟随核数线性上升。

4.4 MCS lock：可扩展自旋的关键

核心思想：让每个 waiter 自旋在自己私有的 cache line 上，排成一个隐式队列，解锁时只通知队首后继一个人。这样一次 handoff 只触碰一条 cache line，与核数无关。

typedef struct mcs_node {
    _Atomic(struct mcs_node *) next;
    atomic_int locked;          // 自己自旋的本地标志
} mcs_node_t;

typedef struct { _Atomic(mcs_node_t *) tail; } mcs_lock_t;

void mcs_lock(mcs_lock_t *l, mcs_node_t *me) {
    atomic_store_explicit(&me->next, NULL, memory_order_relaxed);
    mcs_node_t *prev = atomic_exchange_explicit(&l->tail, me, memory_order_acq_rel);
    if (prev) {                 // 队列非空,排到 prev 后面
        atomic_store_explicit(&me->locked, 1, memory_order_relaxed);
        atomic_store_explicit(&prev->next, me, memory_order_release);
        while (atomic_load_explicit(&me->locked, memory_order_acquire))
            cpu_relax();        // 自旋在自己的 locked 上
    }
}
void mcs_unlock(mcs_lock_t *l, mcs_node_t *me) {
    mcs_node_t *next = atomic_load_explicit(&me->next, memory_order_acquire);
    if (!next) {                // 看似没有后继
        mcs_node_t *expected = me;
        if (atomic_compare_exchange_strong_explicit(
                &l->tail, &expected, NULL,
                memory_order_acq_rel, memory_order_acquire))
            return;             // 确实没人排队
        while (!(next = atomic_load_explicit(&me->next, memory_order_acquire)))
            cpu_relax();        // 有人正在入队,等它填好 next
    }
    atomic_store_explicit(&next->locked, 0, memory_order_release);  // 放行后继
}

代价：调用者需要提供一个 mcs_node（通常在栈上）,API 不如普通 spinlock 干净。CLH lock 是它的近亲，区别在于自旋在前驱的节点上（MCS 自旋在自己节点上）;MCS 在无 cache 一致性的 NUMA 上更优，二者在不同硬件上各有胜场。

4.5 qspinlock：Linux 内核的生产级实现

Linux 内核的 spinlock_t 底层是 qspinlock(queued spinlock)，融合了多种思想：

• 4 字节锁字就能编码锁状态 + 等待队列（对内核里海量的 spinlock 实例，内存占用很关键）。
• 无竞争快路径：单个 CAS 拿锁，和普通 spinlock 一样快。
• 单 waiter 时用一个 pending 位避免动用 MCS 队列。
• 多 waiter 时退化为 per-CPU 的 MCS 节点数组排队，获得可扩展性。

它是“既要无竞争时的轻量，又要高竞争时的可扩展”的工程典范。值得读源码：kernel/locking/qspinlock.c。

4.6 何时用自旋锁

• 临界区极短（几十~几百纳秒级，如更新一个链表指针）。
• 在不能睡眠的上下文：硬中断、softirq/tasklet、持有其他 spinlock 时、关抢占/关中断区间。
• 单核机器上自旋锁等于灾难（持锁者被你抢占走了，你却在原地自旋等它，永远等不到）——所以内核 spinlock 在持有期间关抢占。

5. 阻塞锁

共同点：拿不到锁就让出 CPU 去睡眠，由释放者唤醒。适合临界区较长、可以睡眠的上下文。

5.1 mutex 的本质 = 原子快路径 + 睡眠慢路径

一个误区是把“原子”和"mutex"对立。实际上现代 mutex 本身就是“原子 + 睡眠”：无竞争时一个 CAS 在用户态搞定（不进内核），有竞争时才陷入内核睡眠。所以“用原子变量 + sleep 实现同步”不是异端，而是 mutex 的标准结构，只是你自己实现的版本通常更专用、更轻（省掉了通用 mutex 的递归检测、错误检查、PI 等）。

5.2 futex：用户态锁的内核支撑

Linux 的 futex (fast userspace mutex) 是 pthread 锁的地基。设计精髓：无竞争时完全在用户态用原子操作完成，只有需要阻塞/唤醒时才系统调用。

• FUTEX_WAIT(addr, val)：原子地检查 *addr == val，若是则睡眠；否则立刻返回（避免 lost wakeup）。
• FUTEX_WAKE(addr, n)：唤醒最多 n 个等在该地址上的线程。

Drepper 的经典三态 mutex:

// 0=unlocked, 1=locked无waiter, 2=locked有waiter
void mutex_lock(atomic_int *m) {
    int c = 0;
    if (atomic_compare_exchange_strong(m, &c, 1)) return;  // 快路径:一个 CAS
    if (c != 2) c = atomic_exchange(m, 2);                  // 标记"有 waiter"
    while (c != 0) {
        futex(m, FUTEX_WAIT, 2, NULL);                     // 睡到被唤醒
        c = atomic_exchange(m, 2);
    }
}
void mutex_unlock(atomic_int *m) {
    if (atomic_fetch_sub(m, 1) != 1) {     // 1→0 无 waiter,免唤醒
        atomic_store(m, 0);
        futex(m, FUTEX_WAKE, 1, NULL);     // 有 waiter,唤醒一个
    }
}

注意“是否有 waiter”这个状态位：它让无人等待时的解锁能跳过昂贵的 FUTEX_WAKE 系统调用。这种“只在必要时进内核”的设计是高性能同步的通用套路。详见 Drepper《Futexes Are Tricky》。

5.3 adaptive mutex / optimistic spinning

纯睡眠 mutex 在“锁马上就会释放”的场景下，睡眠+唤醒的上下文切换开销反而成了浪费。自适应锁：先有界自旋一小会儿，自旋失败再睡。

关键优化是 Linux 内核的 optimistic spinning(osq_lock):只在锁的当前持有者正运行在另一个 CPU 上时才自旋——因为这种情况下锁很可能马上释放，自旋划算；一旦发现持有者已被调度下 CPU（短期内不会释放），立刻转入睡眠。这让 mutex 在低竞争时接近 spinlock 的延迟，高竞争时不浪费 CPU。

用户态对应：glibc 的 PTHREAD_MUTEX_ADAPTIVE_NP。有睡眠条件时，自适应 mutex 通常是最优默认互斥选型。

5.4 优先级反转（priority inversion） 与优先级继承（PI）

实时系统的经典陷阱：低优先级线程 L 持锁，高优先级线程 H 等这把锁，而中优先级线程 M（不需要锁）抢占了 L 一直跑，导致 H 被 M 间接阻塞——高优先级反而被低优先级拖死（火星探路者号就栽在这上面）。

优先级继承（PI）:H 等 L 的锁时，临时把 L 的优先级提到 H，让 L 尽快跑完释放锁。pthread_mutexattr_setprotocol(PTHREAD_PRIO_INHERIT)、内核 rt_mutex 提供此能力。这是“别手搓生产锁”的一个重要理由——这类细节你自己实现几乎一定会漏。

5.5 可重入锁 / 递归锁（recursive mutex）

记录持有者 TID 和递归深度，同一线程可重复加锁，深度归零才真正释放。

重要提醒：需要递归锁通常是设计气味——说明你的临界区边界没划清楚，或者一个持锁函数里又调了另一个会加同一把锁的函数。优先重构成“持锁的薄壳 + 不持锁的核心逻辑”。另外递归锁与条件变量配合有坑：cond_wait 只释放一层，而非全部递归层，容易死锁。

6. 读写分离

当读远多于写时，让多个读者并发能大幅提升吞吐。三种机制在“读者代价”上逐级降到极致。

6.1 读写锁（rwlock / rwsem）

多读并发、写独占。加读锁 / 加写锁是两种操作。

两个经典陷阱：

• 写者饥饿：读者源源不断时，写者永远等不到所有读者退出。解决：写者优先策略（Linux rwsem 带 writer bias），但增加读侧开销。读者优先 vs 写者优先是 rwlock 实现的核心抉择，要根据负载选。
• reader-count 的 cache 抖动：每次加读锁都要原子地修改共享的 reader 计数，大核数下这个计数所在的 cache line 在所有读核间反复弹跳，读吞吐不升反降。读极多时，rwlock 可能还不如普通 mutex，此时应上 seqlock 或 RCU。

6.2 seqlock（顺序锁）

写者优先且读侧极轻的方案。一个序列号 seq:

// 写者
void write_begin(seqlock_t *s) { s->seq++; smp_wmb(); }   // 变奇数 + 写屏障
void write_end(seqlock_t *s)   { smp_wmb(); s->seq++; }   // 写屏障 + 变偶数

// 读者
T read(seqlock_t *s) {
    unsigned start; T val;
    do {
        start = s->seq;            // 读前取序列号
        smp_rmb();
        val = shared_data;         // 读数据
        smp_rmb();
    } while (start & 1 || start != s->seq);  // 写中(奇)或期间被改 → 重试
    return val;
}

读者不修改任何共享状态（零原子 RMW、零 cache 争用），只做重试。Linux 用它读 jiffies、clock_gettime 等超高频时钟变量。

注意：seqlock 只让读侧无锁，写者之间仍必须互斥——上面的 write_begin/write_end 只画了序列号部分，真实实现（如 Linux write_seqlock()）内部还嵌了一把 spinlock 来串行化写者。

三条硬性禁忌（满足任一就不能用）:

1. 读侧有指针解引用——重试期间旧指针可能已被 free,deref 就是 UAF。
2. 读者不能重试——读到的值已经产生了外部副作用。
3. 数据量大——重试代价高。

6.3 RCU (Read-Copy-Update)：读侧零开销的极致

内核里读多写极少场景的杀手锏。读者几乎零成本：进入读侧临界区只需 rcu_read_lock()（在非抢占内核里甚至是空操作 / 只标记一下，无任何原子指令、无锁、无屏障开销）。

写者流程：

1. Copy：复制要改的数据结构。
2. Update：在副本上修改。
3. 原子替换指针：用 rcu_assign_pointer()（带 release 语义）把旧指针换成新副本。新读者看到新版本，老读者继续用旧版本。
4. 等待 grace period:synchronize_rcu()（同步等）或 call_rcu()（注册回调异步）等待所有“在替换之前就进入读侧临界区”的老读者全部退出。
5. 回收:grace period 过后，旧版本确定无人引用，安全 free。

读者侧 rcu_dereference() 读指针（带依赖序保证）。核心权衡：把代价从读者转移到写者（写者要复制+等待 grace period）。所以 RCU 只适合：读侧在 datapath 上、对延迟极敏感、写频率很低、且数据可以“整体替换”。Linux 的路由表、dcache、模块/设备列表大量用它。用户态有 liburcu。

一句话记住三者的演进：rwlock（读者要改计数）→ seqlock（读者只读+重试）→ RCU（读者连重试都几乎没有，代价全压给写者）。

7. 协调原语

这些严格说不全是“锁”，而是更广义的同步原语，但实际系统里和锁配合使用，必须一起理解。

7.1 信号量（semaphore）

一个计数器 + 两个原子操作：P/down（减一，为零则阻塞）、V/up（加一并唤醒一个等待者）。

• 计数信号量（counting）：初值 N，表示 N 份可用资源。用于资源池限流（连接池、线程槽位，最多 N 个并发）。
• 二值信号量（binary）:N=1，行为类似 mutex。

与 mutex 的关键语义差别：信号量的 V 可以由非持有者线程调用。这让它能表达“一个线程等待另一个线程发出的事件”(producer V,consumer P)，是跨线程信号传递的工具。反过来，正因为没有“持有者”概念，它不适合当 mutex 来保护临界区（缺少所有权语义，也无法做 PI）。

7.2 条件变量（condition variable） 与 Monitor

条件变量解决“等待某个条件成真”。必须与一把 mutex 配合:

// 等待方
pthread_mutex_lock(&m);
while (!condition)                 // 必须是 while,不是 if!
    pthread_cond_wait(&cv, &m);    // 原子地"解锁 m + 睡眠",醒来后重新持 m
/* 此时条件成立且持有 m */
pthread_mutex_unlock(&m);

// 通知方
pthread_mutex_lock(&m);
condition = true;
pthread_cond_signal(&cv);          // 唤醒一个;cond_broadcast 唤醒全部
pthread_mutex_unlock(&m);

两个必须记住的点：

• 永远用 while 循环包裹等待，不能用 if。原因：① 虚假唤醒（spurious wakeup） 客观存在；② 被唤醒到重新拿锁之间，条件可能又被别人改变（Mesa 语义，主流实现都是 Mesa 而非 Hoare）。
• signal 唤醒一个，broadcast 唤醒全部。乱用 broadcast 会造成惊群（thundering herd）：一堆线程被唤醒却只有一个能拿到锁，其余白白竞争一轮又睡回去。

Monitor（管程） 是“mutex + 一组条件变量 + 封装数据”的高层抽象，Java 的 synchronized + wait/notify、Python 的 threading.Condition 都是 monitor 的体现。

相比“固定 sleep 轮询”，条件变量是精确唤醒——没有轮询的延迟粒度和空转。任何“等条件成真”的逻辑都应优先用 condvar 而非 sleep 循环。内核对应 wait_queue + wait_event()（宏已帮你写好了 while 循环）。

7.3 屏障（barrier） 与 latch

• barrier (pthread_barrier):N 个线程都到达某点后才一起继续。用于分阶段并行计算（所有 worker 完成第 i 阶段才进入第 i+1 阶段）。
• latch / countdown：计数归零后放行（一次性），如“等 N 个初始化任务全完成再启动主逻辑”。C++20 有 std::latch / std::barrier。

注意区分内存屏障（memory barrier） 和线程屏障（thread barrier），中文都叫“屏障”但完全是两回事。

8. 无锁数据结构与内存回收

完全基于原子操作（CAS/FAA），不用任何锁。难点不在“怎么改”，而在“何时安全回收内存”。

8.1 Treiber 栈（无锁栈）

最简单的无锁结构，基于 CAS 头指针：

void push(stack *s, node *n) {
    node *head;
    do {
        head = atomic_load(&s->top);
        n->next = head;
    } while (!atomic_compare_exchange_weak(&s->top, &head, n));
}
node *pop(stack *s) {
    node *head, *next;
    do {
        head = atomic_load(&s->top);
        if (!head) return NULL;
        next = head->next;          // ⚠️ 这里读 head->next 时,head 可能已被另一线程 pop 并 free → UAF + ABA
    } while (!atomic_compare_exchange_weak(&s->top, &head, next));
    return head;
}

pop 的注释指出了无锁结构的核心难题：读取一个可能正被并发回收的节点。这正是为什么无锁编程的真正门槛是内存回收（§8.3），而不是 CAS 本身。

8.2 Michael-Scott 队列（MPMC 无锁队列）

最经典的多生产者多消费者无锁队列（1996），用 head/tail 两个指针分别 CAS 推进，带一个 dummy 头节点简化边界。Java 的 ConcurrentLinkedQueue 即其实现。要点：enqueue 时先 CAS tail->next，再 CAS tail（两步，允许中间状态，其他线程会帮忙“推进”未完成的 tail——这叫 helping）。同样面临 ABA 和回收问题。

8.3 内存回收：无锁结构的真正难点

锁能天然界定“没人在用这块内存了”，无锁不能。三种主流方案：

• Hazard Pointer（风险指针）：每个线程把它“正在访问的指针”登记到一个全局可见的 hazard 数组。回收前先扫描所有 hazard 指针，若目标仍被某线程登记，就推迟回收。读侧有少量开销但有界。
• Epoch-Based Reclamation (EBR)：用全局 epoch（纪元）划分时间。线程进入临界区时记录当前 epoch，退出时更新。只有当所有线程都越过某个 epoch，该 epoch 之前退役的内存才能回收。读侧几乎零开销，但一个长期不退出临界区的线程会阻塞所有回收（和 RCU 的 grace period 同理）。crossbeam(Rust)、folly 都用 EBR。
• QSBR (Quiescent-State-Based Reclamation):RCU 的用户态形态，靠线程周期性声明“静止状态”推进回收。

RCU 本质上就是内核里的 EBR/QSBR。理解了无锁回收，就理解了 RCU 为什么长这样。

8.4 环形缓冲区：SPSC 与 Disruptor

• SPSC ring buffer（单生产单消费）：最轻量的无锁队列。一个数组 + 读写两个 index,只靠 memory barrier 就正确，连 CAS 都不需要（因为生产者只动 write index、消费者只动 read index，无写冲突）。Linux kfifo 是教科书实现（用 2 的幂大小 + 位掩码取模）。中断 handler → worker thread 传事件的首选。
• LMAX Disruptor:pre-allocated 环形数组 + sequence number，多生产者共享一个 sequencer 用 CAS 协调。极高吞吐（单机百万级 TPS），金融低延迟系统经典。代价：buffer 固定大小、内存预分配、API 复杂、场景特化。其设计文档本身就是一份关于 cache、false sharing、memory barrier 的优秀教材。

9. Linux 内核同步原语速览

内核的上下文约束比用户态严格得多：原子上下文（中断、softirq、持 spinlock、关抢占）绝对不能睡眠。选错原语 = "scheduling while atomic" panic。

几个要点：

• spinlock 的变体要选对：spin_lock_irqsave()（关本地中断，中断里也访问该锁时必须用）、spin_lock_bh()（关 softirq）、spin_lock()（只关抢占）。选错 → 死锁。
• per-CPU + local_lock 是内核避免竞争的主力思路：把数据拆成每 CPU 一份，大部分访问根本不需要跨 CPU 同步。
• completion 比手搓“标志位 + 轮询”或“信号量”更清晰，专门用于“A 等 B 干完某事”。
• lockdep（见 §10.5）是内核的死锁检测器，开发内核代码必开。

10. 工程实践

10.1 选型决策（口诀：能不锁就不锁）

按这个顺序问自己：

1. 能不能根本不共享？ —— per-CPU / per-thread 数据、sharding、消息传递。最快的锁是不存在的锁。
2. 能不能用单个原子操作搞定？ —— 计数器、标志位、一次性 init(CAS 三态机)→ 直接 atomic，不要上锁。
3. 是读多写少吗？ —— 是 → RCU（读侧极敏感）/ seqlock（小数据、可重试）/ rwlock（一般情况）。
4. 临界区在什么上下文？ —— 不能睡（中断/持 spinlock）→ spinlock；能睡 → mutex。
5. 临界区多长？ —— 极短 → spinlock 或 adaptive mutex 的自旋阶段；较长 → mutex。
6. 竞争多激烈、核数多少？ —— 高竞争高核数 → MCS/qspinlock（自旋类）、分段锁/sharded lock（降低单锁竞争）。

10.2 死锁（deadlock）：四个必要条件与对策

死锁同时满足四条（Coffman 条件）：互斥、持有并等待、不可剥夺、循环等待。破坏任一条即可避免：

• 破坏循环等待 → 锁排序（lock ordering）：最常用。规定全局统一的加锁顺序，所有人都按地址/ID 从小到大加锁，就不可能成环。
• 破坏持有并等待 → 一次性获取所有锁，或用 trylock 拿不到就回退释放已持有的锁再重试。
• 还有 livelock（活锁）：线程不停响应彼此而无人前进（两人过道互相让）;优先级反转(§5.4)。

实用建议：① 临界区内绝不调用可能再加锁的外部回调；② 持锁时不做 I/O、不睡眠（在能睡的锁里也尽量短）;③ 需要多把锁时严格遵守锁序并写进注释。

10.3 锁竞争分析与优化

发现锁是瓶颈后，按收益从大到小：

1. 缩小临界区：把不需要保护的计算（尤其是内存分配、I/O、日志）挪到锁外。
2. 降低加锁频率：批量处理（攒一批再加一次锁），或用 per-CPU 计数 + 定期汇总。
3. 拆分锁（lock splitting / sharding）：一把大锁拆成多把（如按 hash 分桶，每桶一把锁）。
4. 换更细粒度或读写分离的机制：读多写少 → rwlock/RCU。
5. 换无锁结构：确认竞争极高且其他手段不够时再考虑，注意它带来的回收复杂度和调试难度。
6. 消除共享（终极）：重新设计数据布局，让线程各管各的。

注意 false sharing(§2.2)——有时“竞争”根本不是逻辑竞争，只是两个无关变量挤在同一 cache line。

10.4 常见 bug 模式

• 忘加屏障（尤其 ARM）:x86 上跑得好，ARM 上偶发崩溃。
• double-checked locking 写错：经典的 if (!inst) { lock; if (!inst) inst = new... } 在缺少 acquire/release 时会让别的线程看到“构造了一半”的对象。必须用 acquire/release 原子操作。
• lost wakeup：先检查条件、后睡眠之间窗口里被 signal，导致永久睡眠。futex/condvar 的 while 循环 + 原子检查就是为防这个。
• TOCTOU:check 和 act 之间状态变了（如『先判断某个 init 槽位是否空闲、再去占用』，两步之间槽位可能已被别的线程抢走）。要把 check+act 合成一个原子操作（CAS）。
• 递归/重入死锁：持锁函数间接又调了加同一把锁的函数。
• 在原子上下文睡眠：内核里持 spinlock 时调用了可能睡眠的函数(kmalloc(GFP_KERNEL)、copy_to_user、mutex_lock)。

10.5 调试与验证工具

• ThreadSanitizer (TSan):-fsanitize=thread，动态检测 data race,用户态并发 bug 的首选利器，误报极低。强烈推荐对所有多线程代码跑一遍。
• Helgrind / DRD (Valgrind)：检测 data race、锁序违反、API 误用。比 TSan 慢但不需重编。
• lockdep （内核）:CONFIG_PROVE_LOCKING，运行时检测潜在死锁（锁序违反、在原子上下文睡眠等），内核开发必开。
• perf lock / perf lock contention：分析锁竞争热点，看哪把锁、被谁、等了多久。
• /proc/lock_stat（内核）：锁竞争统计。
• GDB 多线程:info threads、thread apply all bt 看所有线程栈；分析死锁时看每个线程卡在哪把锁的等待上，顺着 owner 找环。
• 形式化验证：对核心无锁算法，可用 CppMem / herd7（基于公理化内存模型验证小段代码的所有可能执行）、TLA+（验证协议层正确性）。McKenney 的书里有大量 litmus test 例子。

10.6 设计原则总结

1. 能不共享就不共享；能不锁就不锁。
2. 临界区越短越好，锁外做重活。
3. 选对上下文对应的原语（能否睡眠是第一约束）。
4. 别手搓生产锁——pthread/内核的实现替你处理了内存序、公平性、PI、自适应等一堆细节。手搓只在两种情况值得：做无锁数据结构，或像一次性 init 这种一个 CAS 就能精确表达的轻量状态机。
5. 多线程代码一律过 TSan / lockdep。
6. 内存序拿不准时用 seq_cst（慢但安全），想清楚了再降到 acquire/release。

11. 延伸阅读

11.1 书籍（按推荐优先级 + 你的方向）

首选（系统、深入、和内核/存储方向最契合）:

• Paul E. McKenney，《Is Parallel Programming Hard, And, If So, What Can You Do About It？》 —— 免费（作者官网 perfbook 持续更新）。RCU 作者写的，内核风格并发的“圣经”：内存屏障、各种锁、RCU、无锁、内存回收、性能、验证，极其详尽，还有海量 litmus test。对做内核/存储的人是最该读的一本。
• Maurice Herlihy & Nir Shavit，《The Art of Multiprocessor Programming》 —— 并发算法领域的经典教科书。互斥算法、自旋锁（含 MCS/CLH）、无锁/wait-free 数据结构、进展保证的理论基础，讲得最系统。偏算法理论。
• Michael L. Scott，《Shared-Memory Synchronization》 —— MCS 锁作者写的，专注同步机制本身，从硬件原语到各类锁到无锁，深度和广度都好，比上一本更聚焦“锁”这个主题。

实践与平台向：

• Anthony Williams，《C++ Concurrency in Action》（2nd ed.） —— C++ 内存模型、std::atomic、各种内存序、无锁结构的最佳实践，代码向，讲 memory_order 讲得很透。
• OSTEP《Operating Systems: Three Easy Pieces》并发部分 —— 免费。锁、条件变量、信号量的入门讲解，清晰友好，适合补地基或给团队新人。
• Robert Love，《Linux Kernel Development》 + 《Understanding the Linux Kernel》 —— 内核同步原语章节，讲 spinlock/mutex/seqlock/RCU 在内核里怎么用、上下文约束。
• Michael Kerrisk，《The Linux Programming Interface》 —— POSIX 线程、mutex、条件变量、信号量、futex 的权威参考。

11.2 论文与在线资料（都值得精读）

• Ulrich Drepper，《Futexes Are Tricky》 —— futex 和 mutex 实现的必读，§5.2 的三态 mutex 出处。
• Ulrich Drepper，《What Every Programmer Should Know About Memory》 —— cache、内存层级、false sharing 的经典长文。
• Mellor-Crummey & Scott (1991)，《Algorithms for Scalable Synchronization on Shared-Memory Multiprocessors》 —— MCS 锁原始论文。
• Michael & Scott (1996)，《Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms》 —— M-S 队列原始论文。
• Jeff Preshing 的博客（preshing.com） —— 内存序、acquire/release、无锁、原子操作讲得极其清楚直观，墙裂推荐当入门到进阶的桥梁。代表文："An Introduction to Lock-Free Programming"、"Acquire and Release Semantics"、"The Synchronizes-With Relation"。
• Linux 内核文档:Documentation/memory-barriers.txt（内存屏障权威解释）、Documentation/locking/（各类锁）、Documentation/RCU/(RCU 系列)、tools/memory-model/(LKMM,Linux 内核内存模型 + herd7 工具)。
• LWN.net 的 locking / RCU 系列文章 —— 跟踪内核同步演进的最佳来源（搜 "qspinlock"、"RCU"、"locking" 等）。
• C++ 标准内存模型:cppreference 的 std::memory_order 页面，作为查阅手册。

11.3 值得读源码的开源项目

• Linux 内核 kernel/locking/ —— qspinlock.c（可扩展自旋锁）、mutex.c（含 optimistic spinning）、rwsem.c、rtmutex.c(PI 实现);include/linux/seqlock.h;kernel/rcu/(RCU 实现)。工业级实现的最高水准。
• glibc nptl/ —— pthread_mutex_lock.c 等，看 POSIX 锁如何基于 futex 实现（含 PI、robust、自适应）。
• Folly(Facebook)folly/synchronization/ —— 现代 C++ 同步设施，注释详尽：DistributedMutex、MicroLock、Hazptr(hazard pointer)、Rcu。学习现代无锁工程的好材料。
• Abseil(Google)absl/synchronization/ —— Google 的 Mutex 实现，设计文档值得读。
• liburcu —— 用户态 RCU 的参考实现。
• Concurrency Kit (ck) —— C 语言无锁/同步原语库，实现了大量学术算法（各种锁、无锁队列/栈/哈希、hazard pointer、EBR），代码干净，是“把论文变成 C 代码”的活字典。
• crossbeam(Rust) —— 现代无锁库，crossbeam-epoch 是 EBR 的优秀实现，crossbeam-channel 是高性能 channel。
• Boost.Lockfree / Boost.Atomic —— C++ 无锁队列/栈、可移植原子操作。

11.4 一条学习路径建议

1. 先用 Jeff Preshing 博客 + OSTEP 并发章节 把内存序和基本锁的直觉建起来。
2. 读 McKenney 的 perfbook（免费），边读边对照 Linux 内核源码。
3. 想补算法理论深度，穿插读 Herlihy & Shavit 或 M. Scott。
4. 实践中对所有并发代码跑 TSan，内核代码开 lockdep；遇到具体机制（qspinlock、RCU、futex）回头读对应源码 + LWN 文章。
5. ARM 内存序细节，精读内核 memory-barriers.txt + LKMM 文档，用 herd7 跑 litmus test 验证理解。

全文完。RCU、内存模型、无锁内存回收等任一主题，均可作为独立专题进一步展开。