XCPC Wiki

Appearance

第六章：同步与互斥 ​

共享状态的正确维护贯穿各子系统。进程表、空闲页链表、文件偏移、缓存块和设备队列都可能被多个执行流访问。锁属于这些对象的访问协议，并不是另一个替它们工作的后台服务。

分析同步时，先写出共享对象必须保持的不变量，再确定哪些操作可能同时访问它。原子操作与锁约束更新和可见顺序；等待协议衔接条件检查与睡眠、唤醒；生命周期协议保证最后一个使用者退出后才回收对象。三者处理的问题不同。

例如队列的头、尾与长度必须相互一致，保护其中一个整数并不自动保护整条关系。原子操作、锁和条件等待分别约束更新、临界区访问与等待行为；对象回收还需保证没有执行流继续使用旧引用。

并发访问与互斥 ​

先确定原子性和不变量，再讨论用哪种原语实施保护。

正确性条件 ​

把递增抽象成读、加、写三步，两个执行流可能都读到 10，再分别写回 11，两次更新就丢了一次。一次递增需要像不可分割的整体一样发生，这叫原子性。这是交错执行的示意模型；实际 C/C++ 对未同步普通变量的并发读写会形成数据竞争，属于未定义行为。下一步还要考虑：前一个执行流完成的修改，后一个执行流怎样可靠地观察到？

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

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

互斥锁 ​

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

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

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

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

原子操作与锁的实现 ​

锁本身也有竞争；原子指令解决唯一获取，内存顺序保证临界区修改正确传递。

原子操作 ​

如果锁本身也用“先读是否空闲，再写成占用”实现，两个核心仍可能同时读到空闲，一起进入临界区。我们需要硬件提供不可被其他核心插入的读改写操作，才能把软件的互斥约定落实。

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

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

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

内存模型 ​

互斥还不足以解释全部同步需求。考虑下面的发布过程（示意伪代码；并发 C/C++ 实现中的 ready 需要原子访问或锁保护）：

c
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 更难复现。

xv6 自旋锁 ​

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

c
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 的重入。

条件同步与死锁 ​

无法推进的执行流需要等待；等待协议既要不丢通知，也要避免循环依赖。

睡眠锁 ​

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

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

条件变量 ​

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

c
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 可以帮助恢复或发现，却不自动让共享状态一致。破坏死锁后还要定义操作是否可重试、资源如何回滚。

Linux 同步机制与并发性能 ​

不同优化针对不同成本。比较时仍要核对原有正确性和进展保证。

Linux futex ​

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

无锁进展保证 ​

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

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

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

Linux RCU ​

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

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

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

伪共享 ​

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

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

同步与调度 ​

同步的对象是共享状态，阻塞则需要调度器参与。

原子操作用来实现不可分割的基础更新；锁把多步操作组织成临界区，维护对象不变量；条件变量或 sleep/wakeup 协议让暂时无法推进的执行流释放 CPU，等条件变化后重新检查。它们处于不同层次，可以在同一条路径中同时出现。

对于第五章的等待者：条件锁保护“队列是否为空”，等待协议衔接“检查条件”和“登记睡眠”，调度器负责让另一个执行流运行。设备完成处理同样可以更新条件并唤醒等待者。

实验 ​

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

bash
# 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. 队列的头、尾和长度都使用原子变量，为什么整个队列操作仍可能不正确？应先写出什么不变量？

  2. 一个对象已从共享链表删除，为什么仍不一定可以释放？锁、引用计数和 RCU 分别需要什么条件才能保证回收安全？

  3. xv6 acquire() 为什么既需要原子 test-and-set，又需要内存顺序约束？

  4. push_off() 为什么是自旋锁实现的一部分？它没有阻止其他 CPU 做什么？

  5. sleep(chan, lock) 如何避免“检查条件后、真正睡眠前”丢失唤醒？

  6. sleeplock 为什么可以等待，自旋锁却不应在持有时睡眠？

  7. Linux futex 和 RCU 分别把常见路径上的哪些工作移出了内核或临界区？

上次更新: