第六章：共享内存并发

当多个线程在不同核心执行时，编译器重排、处理器乱序执行、缓存一致性协议和调度都会影响共享内存的观察结果。源码中的语句顺序只约束单线程抽象机，不自动规定其他线程的观察顺序。

并发程序需要通过语言内存模型和同步原语建立必要的原子性与 happens-before 关系。

xv6 自旋锁

xv6 的第一个同步原语是 struct spinlock。锁状态只有 locked、名字和持有它的 CPU。acquire() 的核心路径是：

push_off();
while (__sync_lock_test_and_set(&lk->locked, 1) != 0)
  ;
__sync_synchronize();
lk->cpu = mycpu();

编译到 RISC-V 后，原子交换通常落到带 acquire 语义的 AMO 指令；release() 在清理 owner 后以 release 顺序把 locked 写回 0。原子交换保证只有一个 hart 从 0 改成 1，acquire/release 顺序保证临界区内的普通访存不会越过锁边界。

push_off() 关闭当前 hart 的中断并支持嵌套。原因不是“多核锁天然要求关中断”，而是 xv6 可能在持锁时被本 hart 中断处理程序打断；若 handler 再拿同一把锁，这个 hart 会和自己死锁。锁解决 hart 之间的竞争，关中断解决同一 hart 的重入。

正确性条件

counter++ 通常是读、加、写三步。两个线程可同时读到 10，最后都写回 11。这是原子性问题。

即使某次写入本身不可撕裂，另一个核心也未必立即看到，这是可见性问题。即使最终能看到，不同位置的写入也可能以不同顺序被观察，这是有序性问题。

锁和原子操作可同时提供其中多项保证，但某个变量的原子访问不自动规定周围普通内存访问的顺序。

内存模型

考虑发布数据：

data = 42;
ready = 1;

另一个线程先读 ready 再读 data。所需性质是：观察到 ready == 1 时，data 必须为 42。但编译器可能重排指令，CPU 具有 store buffer 和乱序执行能力，cache coherence 通常只保证单个缓存行的一致顺序，不自动为不同地址建立上述关系。

语言内存模型和体系结构内存模型共同规定允许的观察结果。使用 release 写发布 ready，并使用 acquire 读观察它，可以建立 happens-before，使发布前的写入对观察方可见。

这些词最终会落到编译结果上。RISC-V 可用 AMO 的 aq/rl 位或 fence 建立顺序；x86-64 的普通 load/store 顺序较强，acquire load 和 release store常不需要额外指令，sequentially consistent RMW 则常生成带 LOCK 前缀的 cmpxchg、xadd。不能只看 C 源码猜硬件顺序，应查看目标架构汇编，并以语言内存模型而不是某台 CPU 的偶然强序作为正确性依据。

volatile 通常只限制编译器对某次访问的处理，不提供线程间原子性和完整顺序。用它修并发 bug，往往只是让 bug 更难复现。

原子操作

原子 read-modify-write 指令能在多核竞争下完成 compare-and-swap、fetch-add 等操作。它们是锁和无锁结构的基础，但使用时必须选择内存顺序：relaxed、acquire、release、顺序一致等。

较弱的内存顺序允许更多编译器和处理器优化，同时增加正确性证明的复杂度。在缺少性能证据时，应优先使用语义清晰、顺序较强的协议。

compare-and-swap 循环还会遇到 ABA：值从 A 变成 B 又回到 A，数值相同不代表对象没变。版本号、hazard pointer、epoch 等技术都在解决对象身份和回收时机，而不仅是一次原子更新。

互斥锁

互斥锁保证同一时刻只有一个线程进入临界区。若所有共享状态都在锁保护下，执行结果可以像这些临界区按某种顺序串行发生一样推理。

锁的价值不只是“挡住第二个人”，还在 unlock 与后续 lock 间建立内存顺序。锁内普通读写因此能被下一位持锁者正确观察。

临界区应保护不变量，而不是机械地“一个变量一把锁”。例如队列的头、尾和长度必须一起满足关系，拆成三把锁可能每个字段都没有数据竞争，整体却处于不可能状态。

竞争不激烈时，用户态原子指令即可拿锁；竞争时继续自旋会浪费 CPU，线程应进入内核睡眠。Linux futex 的关键思想就是 fast userspace、contended kernel：无竞争不系统调用，有竞争才让内核负责等待和唤醒。

Linux futex

具体地说，锁字位于用户内存。获取方先用原子 compare-exchange 把它从 0 改为 1；失败后才执行 futex(FUTEX_WAIT, expected)。内核再次比较锁字，仍等于 expected 才把线程加入等待队列，从而堵住“检查失败后、真正睡眠前发生解锁”的 lost wakeup。释放方先原子写回 0，确认可能存在 waiter 时再执行 FUTEX_WAKE。内核实现可从 kernel/futex/ 继续追踪。

睡眠锁

自旋锁适合很短且不能睡眠的临界区。xv6 的 sleeplock 用一把 spinlock 保护 locked/pid 状态；发现已占用时调用 sleep(lk, &lk->lk)，释放时清除状态并 wakeup(lk)。等待者不再持续执行原子指令，而是让出 CPU。

这正好分离两层机制：内部 spinlock 保证“检查状态并登记睡眠”不丢失唤醒，外部 sleeplock 允许持锁代码阻塞。xv6 inode 使用 sleeplock，因为读取磁盘可能睡眠；调度器和中断路径中的短状态更新则使用 spinlock。

条件变量

消费者要等“队列非空”，正确模式是：

lock(mutex);
while (queue_empty())
    cond_wait(&cv, &mutex);
item = pop();
unlock(mutex);

cond_wait 原子地释放锁并睡眠，醒来后重新拿锁。必须用 while，因为可能虚假唤醒，条件也可能在获得锁前又被其他线程改变。

条件变量不保存事件计数。没有等待者时，signal 可以不产生后续可见状态；持久状态是由互斥锁保护的条件。收到通知的线程仍必须在持锁状态下重新检查条件，以处理虚假唤醒和并发状态变化。

xv6 没有单独的用户态 condition-variable API，但 sleep(chan, lock) 与 wakeup(chan) 已展示同一内核协议。chan 只是等待条件的身份，真正的条件仍位于 pipe、inode 或 buffer 的状态字段中，醒来后必须重新检查。

死锁

经典死锁需要互斥、持有并等待、不可抢占和环路等待。实践中最有效的预防通常是全局锁顺序：所有路径都按同一顺序获取锁，等待图就无法成环。

但死锁不只发生在 mutex：

• 线程池所有 worker 都同步等待同一池中的新任务；
• 持锁等待 I/O，而完成路径也需要这把锁；
• 进程间 RPC 形成调用环；
• 内存分配在隐蔽路径重入已有锁。

try-lock、超时和 watchdog 可以帮助恢复或发现，却不自动让共享状态一致。破坏死锁后还要定义操作是否可重试、资源如何回滚。

无锁进展保证

lock-free 保证系统整体总有某个操作推进，不保证当前线程不饿死；wait-free 才要求每个操作在有界步骤内完成。它们是进展保证，不是“代码里没有 mutex”的表面特征。

无锁结构仍可能在缓存行上激烈争用，并面临最难的问题：何时释放已经从结构中移除、但其他线程可能仍持有指针的对象。引用计数本身有争用，hazard pointer 需显式公布引用，epoch 回收则等待所有旧读者离开。

无锁结构适用于阻塞不可接受或锁竞争已被测量为瓶颈的场景。其他场景中，基于锁的实现通常更易验证，其性能也可能更好。

Linux RCU

Read-Copy-Update 适合读多写少、读路径极其敏感的内核结构。读者进入轻量读侧临界区并读取指针；更新者复制并发布新版本；旧版本要等一个 grace period，确认先前读者都退出后才能释放。

reader:   读旧指针 ─────────→ 离开
writer:        发布新指针 ──等待 grace period──→ 释放旧对象

RCU 把读写互斥改成版本共存和延迟回收。它没有消灭同步，只把成本从高频读路径转移到更新和生命周期管理。读者若把指针带出保护区，仍会 use-after-free。

伪共享

两个线程更新不同变量，若变量落在同一 cache line，cache coherence 仍会让整条缓存行在核心间来回转移。这叫 false sharing。程序没有数据竞争，性能却像在抢锁。

按 cache line 对齐和分片计数器可以改善，但会增加内存占用和最终聚合成本。并发性能优化必须观察硬件共享粒度，而不只是源码对象边界。

实验

先在 xv6 的 acquire() 中统计成功获取次数和 test-and-set 失败次数。比较单核、多核，以及一个全局锁和分片锁；再故意删掉 push_off()，构造持锁时发生中断并由中断处理程序重入同一把锁的情形。下面的 Linux 工具用于观察更完整的并发实现。

# ThreadSanitizer 更适合找 C/C++ 数据竞争
cc -O1 -g -fsanitize=thread race.c -pthread && ./a.out

# 观察锁、调度与缓存事件（具体事件依 CPU 而异）
perf stat -e context-switches,cache-misses ./worker

# 查看系统中的 futex 调用
strace -f -e futex ./worker

让多个线程分别更新“相邻计数器”和“按 cache line 填充的计数器”，比较吞吐。这个实验能把 cache coherence 从抽象名词变成明显性能差距。

本章涉及的 Linux 原语语义可对照 memory barriers 和 atomic types。前者还分别列出了 CPU—CPU、CPU—DMA 与 CPU—MMIO 所需的不同 barrier，不能把一种 volatile 或 fence 当成通用同步方法。

练习

1. xv6 acquire() 为什么既需要原子 test-and-set，又需要内存顺序约束？
2. push_off() 为什么是自旋锁实现的一部分？它没有阻止其他 CPU 做什么？
3. sleep(chan, lock) 如何避免“检查条件后、真正睡眠前”丢失唤醒？
4. sleeplock 为什么可以等待，自旋锁却不应在持有时睡眠？
5. Linux futex 和 RCU 分别把常见路径上的哪些工作移出了内核或临界区？

上一章：CPU 调度 · 下一章：设备 I/O →