Appearance
同步原语
- 写作时间：
2026-03-04 首次提交，2026-07-13 最近修改 - 当前字符：
8935
线程说明了同一进程中的执行流怎样共享地址空间。共享只让多个线程能够访问同一对象，却没有规定它们以什么顺序访问，也没有保证一组读写在其他线程看来不可分割。同步原语负责补上这些约束。
来看两个线程分别执行一次 counter++。这条 C 表达式在语义上要先取得旧值、计算新值、再保存结果。如果两个线程都基于旧值 0 计算，它们可能先后写回 1，两个增量只留下一个。更严重的是，普通 C 对象上的这种并发读写构成数据竞争，编译器不必保留程序员设想的交错执行结果。
本课先通过 竞态与临界区确定要保护的共享不变量，再用 原子操作与内存序区分“单次更新不可分割”和“多次访问按什么顺序可见”。这些硬件与语言保证可以构造 锁；当线程等待的是状态变化而不是锁本身时，需要 条件等待。Linux 用户态库再用 Futex 连接用户态快速路径与内核阻塞路径，最后把这些机制放进 经典同步问题中组合使用。
竞态与临界区
竞态条件是程序正确性依赖并发操作相对时序的情况；临界区(critical section)是必须按同步协议访问共享状态的一段代码。
counter++ 的丢失更新可以用一次允许出现的交错说明：
| 顺序 | 线程 A | 线程 B | counter |
|---|---|---|---|
| 1 | 读取 0 | 0 | |
| 2 | 读取 0 | 0 | |
| 3 | 计算 1 | 0 | |
| 4 | 计算 1 | 0 | |
| 5 | 写入 1 | 1 | |
| 6 | 写入 1 | 1 |
这里展示的是源代码层面的读、改、写语义，不代表编译器一定生成三条固定指令。由于两个线程无同步地访问同一个非原子 C 对象，且至少一个访问是写入，这还构成数据竞争；C 语言把这种程序的行为定义为未定义，编译器可以进行普通单线程代码中合法、但破坏上述推演的优化。
竞态条件与数据竞争不是同义词。数据竞争是语言内存模型中的特定违规；竞态条件是更广的逻辑问题。即使每个变量的单次读写都不会暴露中间状态，下面的“先检查余额，再扣款”仍可能因两个线程都通过检查而违反余额不为负的业务不变量。单次读写不可分割，不代表跨多个步骤的决策不可分割。
临界区需要保护的通常不是某一行代码，而是共享不变量(invariant)。不变量是程序在每次受保护操作前后都必须成立的关系，例如“队列元素数量介于 0 和容量之间”或“账户余额与流水总额一致”。同步协议必须覆盖从读取旧状态到恢复不变量的完整区间。
经典临界区问题提出三个评价要求：
| 要求 | 含义 |
|---|---|
| 互斥(mutual exclusion) | 同一时刻至多一个参与者执行互斥临界区 |
| 进展(progress) | 临界区空闲且存在请求者时，系统最终允许某个请求者进入 |
| 有限等待(bounded waiting) | 一个请求者等待期间，其他参与者越过它的次数有上限 |
真实同步原语不一定同时承诺三项。例如，一把不公平 mutex 可以保证互斥与整体进展，却不保证每个等待线程都在有限次数内获得锁；某个线程可能发生饥饿，即系统整体仍在推进，但它长期得不到资源。选择原语时必须区分安全性“不会同时进入”和活性“等待最终会结束”。
volatile 不能修复数据竞争。它主要约束编译器对单个对象访问的省略与合并，常用于设备寄存器等场景，不会让整次读改写变得不可分割，也不会建立线程间顺序保证。
原子操作与内存序
原子操作(atomic operation)是在语言内存模型中不可被其他线程观察到中间状态的操作；内存序(memory ordering)规定多个内存操作允许以什么顺序被其他线程观察。
两者解决不同问题。原子读改写可以让两个线程对同一个计数器递增而不丢失更新；但若线程 A 先写数据再发布“ready”标志，线程 B 还需要顺序保证，才能在看到 ready 后读取到对应数据。
现代处理器提供原子读改写指令，编译器再通过 C11 _Atomic 和 <stdatomic.h> 暴露可移植接口。两种基础语义是：
| 操作 | 语义 |
|---|---|
| 测试并设置(Test-and-Set) | 原子地写入占用值，并返回旧值 |
| 比较并交换(Compare-and-Swap, CAS) | 当前值等于 expected 时原子替换为 desired，否则报告失败并返回实际值 |
CAS 适合实现“读取旧值、计算候选新值、尝试提交”的重试循环。若其他线程在提交前修改了对象，比较失败，调用者重新读取并计算。它只保证这一次比较与替换不可分割，不会自动证明整个数据结构正确，也不会自动保证无饥饿。
对于只需要精确计数、不负责发布其他数据的场景，可以使用 relaxed 原子读改写：
c
#include <stdatomic.h>
_Atomic unsigned long counter = 0;
void increment(void)
{
atomic_fetch_add_explicit(&counter, 1, memory_order_relaxed);
}memory_order_relaxed 保证 counter 更新本身原子，但不约束它与其他对象访问的先后关系。若一个线程要发布已经初始化的数据，常见协议是发布方使用释放(release)操作写入状态，读取方使用获取(acquire)操作观察状态。当 acquire 读取到 release 发布的状态值时，release 之前的操作与 acquire 之后的操作建立先行发生关系(happens-before)：语言保证前一方的效果按规定顺序对后一方可见。
锁通常把这套关系封装起来：成功加锁具有 acquire 语义，解锁具有 release 语义。持锁线程在解锁前写入的数据，对随后成功获取同一把锁的线程可见。顺序一致性(sequential consistency)则提供更强的全局单序模型，推理更直接，但可能限制部分优化。
内存屏障(memory barrier/fence)是约束屏障两侧内存操作顺序的低层机制。屏障不是锁，也不会把 counter++ 变成原子操作；它只建立指定方向的排序。Linux 内核用 smp_mb()、smp_rmb()、smp_wmb() 等架构无关接口表达全屏障、读屏障和写屏障，具体指令由目标架构的内存模型决定。屏障表达的是可观察顺序，不应简单理解成“前面的数据已经全部写回主存”。
应用代码应优先使用 C 原子类型、Pthreads 锁和条件变量，让编译器同时处理指令选择与编译期重排。直接拼硬件指令或只插入 CPU fence，容易遗漏语言内存模型对编译器的约束。
锁
锁(lock)是让执行流按照所有权或访问模式互斥进入临界区的同步原语。
自旋锁(spinlock)在锁不可用时反复检查状态，不主动阻塞当前线程。它避免了睡眠与唤醒，但等待期间持续占用 CPU，并会产生对锁缓存行的一致性流量。自旋适合持锁时间很短、持有者能够继续运行且当前上下文不能睡眠的场景；若持有者被抢占或临界区执行阻塞 I/O，等待者可能长期浪费处理器时间。
互斥锁是具有持有者语义的互斥原语，竞争路径可以把等待线程阻塞，锁释放后再唤醒。用户态 pthread_mutex_t 通常先用原子操作尝试无竞争快速路径，只有竞争时才进入内核等待；具体实现还可能短暂自旋，但“mutex 必然立刻睡眠”并不是接口保证。
| 特征 | 自旋锁 | mutex |
|---|---|---|
| 等待方式 | 活跃轮询 | 可以阻塞，并由内核唤醒 |
| 等待时 CPU | 持续消耗执行时间 | 可调度给其他任务 |
| 适合的临界区 | 很短且不能睡眠 | 持有时间不确定或允许睡眠 |
| 主要风险 | 持有者未运行时无效自旋 | 睡眠、唤醒和调度开销 |
不能用固定的微秒阈值决定选择。临界区时间分布、CPU 是否超额订阅、持有者是否可能被抢占、核心间拓扑和竞争程度都会改变结果。Linux 内核 mutex 的乐观自旋(optimistic spinning)会在合适条件下先等待正在运行的持有者，说明实际实现可以组合自旋与睡眠，而不是二选一。
锁的状态也需要正确的内存序。一个最小自旋锁可用原子 exchange 获取所有权，并在解锁时执行 release store；只把普通整数从 0 改成 1，即使操作看似不可中断，也可能缺少编译器和 CPU 所需的 acquire/release 约束。
读写锁(reader-writer lock)允许多个读者同时持有读锁，但写者必须独占。它适合读临界区明显占多数、持锁时间足以抵消管理开销的场景。读者计数、所有权转换和公平策略使它比普通 mutex 更复杂；持续到来的读者可能让写者饥饿，写者优先策略又可能延迟读者，因此接口或实现必须明确公平性取舍。
无论使用哪种锁，都应尽量缩短持锁范围，并在获取多把锁时规定一致顺序。死锁会分析锁顺序为什么影响系统能否继续推进。
条件等待
条件等待是线程在共享状态暂不满足要求时释放处理器，并在状态可能变化后重新检查的同步方式。
信号量(semaphore)维护可用许可数量。sem_wait() 在计数大于 0 时取得一个许可并减一，否则阻塞；sem_post() 增加许可并可能唤醒等待者。初始值为
二元信号量只有 0 和 1 两种许可数量，表面上接近 mutex，但语义不同。mutex 具有所有者，通常要求加锁线程解锁；信号量表示可传递许可，一个执行流可以 post 由另一个执行流 wait 的许可。需要保护共享不变量时优先使用 mutex，需要计数或跨执行流通知时才考虑 semaphore。
条件变量(condition variable)让线程等待某个由共享数据表示的谓词(predicate)可能变为真。谓词是可判断真假的状态表达式，例如 count > 0；条件变量本身不保存“缓冲区非空”这个状态，也不是会永久积累的事件计数器。
消费者等待有界缓冲区非空时，需要先持有保护 count 的 mutex，再在循环中检查谓词：
c
pthread_mutex_lock(&mutex);
while (count == 0)
pthread_cond_wait(¬_empty, &mutex);
item = remove_item();
pthread_cond_signal(¬_full);
pthread_mutex_unlock(&mutex);pthread_cond_wait() 在阻塞当前线程的同时原子地释放 mutex；返回前又重新获取 mutex。这里的“原子”针对等待者注册与 mutex 释放之间的关系：生产者不可能恰好在消费者释放锁但尚未成为等待者时发出一个导致消费者永久睡眠的通知。这避免了丢失唤醒(lost wakeup)。
wait 必须放在 while 而不是 if 中。POSIX 允许虚假唤醒(spurious wakeup)；即使唤醒对应真实通知，另一个消费者也可能先获得 mutex 并取走数据。通知的含义只是“状态可能变化，请重新检查”，只有受 mutex 保护的谓词才是是否继续执行的依据。
生产者应在持有同一 mutex 时修改 count，使谓词检查与状态更新形成一致顺序，然后调用 pthread_cond_signal() 唤醒至少一个候选等待者，或用 pthread_cond_broadcast() 唤醒所有等待者。若 signal 发生时无人等待，条件变量不会替未来线程保存通知；未来线程仍通过谓词判断是否需要等待。
Futex
快速用户空间互斥机制(fast userspace mutex, futex)是 Linux 让线程按一个 32 位用户空间值进行条件阻塞和唤醒的内核接口。
futex 不是完整的 mutex，也不规定共享整数中每一位的含义。线程库先在用户态用原子操作修改状态；只有需要阻塞或唤醒时才执行 futex 系统调用。无竞争加锁与解锁因而可以完全留在用户态，这就是名称中 fast 的来源。
两个基础操作是：
| 操作 | 内核语义 |
|---|---|
FUTEX_WAIT | 仅当 *uaddr 仍等于 expected 时，把调用线程加入该 futex 的等待集合并阻塞；不相等时返回 EAGAIN |
FUTEX_WAKE | 唤醒在 uaddr 上等待的至多 |
FUTEX_WAIT 的“比较并阻塞”相对于同一 futex 上的并发操作是原子的。假设用户态 CAS 发现 mutex 已占用，随后锁在进入内核前被释放：内核重新读取 futex word 时会发现它不再等于 expected，直接返回而不睡眠。若值仍相等，内核先把等待关系登记到受锁保护的队列，再真正调度出去；解锁方的 wake 不能越过这一步而永久丢失。
text
用户态快速路径 内核竞争路径
atomic try-lock 成功 ────────────→ 返回
atomic try-lock 失败 ────────────→ FUTEX_WAIT(uaddr, expected)
atomic unlock，无等待者 ─────────→ 返回
atomic unlock，可能有等待者 ─────→ FUTEX_WAKE(uaddr, 1)FUTEX_WAKE 不负责修改用户空间状态，wait 返回也不代表调用者已经获得高层锁。被唤醒线程必须回到用户态重试原子操作；wait 还可能因信号、超时或虚假唤醒返回，所以所有高层协议都需要循环检查自己的状态。
内核根据 futex key 把等待者组织进哈希桶，并用桶锁协调值检查、入队和唤醒。进程私有 futex 的 key 关联虚拟地址与地址空间；放在共享映射中的进程间共享(process-shared)futex 则需要根据共享后备对象建立跨进程一致的 key。桶数量和内部结构属于实现细节，不是用户态 ABI。
glibc 的普通 Pthreads mutex、条件变量、信号量和线程 join 都可以利用 futex，但每种原语在 futex word 中编码的状态不同。把某一版 glibc mutex 的 0/1/2 布局当成 futex 接口规范，会混淆库实现与内核 ABI。
经典同步问题
经典同步问题是把互斥、条件等待、资源计数和锁顺序组合成可重复分析的并发模式。
生产者-消费者包含一个容量有限的共享缓冲区。mutex 保护队列、读写位置和元素计数；not_empty 条件变量让消费者等待 count > 0，not_full 让生产者等待 count < capacity。mutex 维护不变量，条件变量避免在状态不满足时持锁忙等，二者不能互相替代。
c
/* producer */
pthread_mutex_lock(&mutex);
while (count == capacity)
pthread_cond_wait(¬_full, &mutex);
insert_item(item);
pthread_cond_signal(¬_empty);
pthread_mutex_unlock(&mutex);
/* consumer */
pthread_mutex_lock(&mutex);
while (count == 0)
pthread_cond_wait(¬_empty, &mutex);
item = remove_item();
pthread_cond_signal(¬_full);
pthread_mutex_unlock(&mutex);读者-写者要求多个读者可以并发访问，写者与任何其他访问互斥。读写锁直接表达这项策略，但仍要选择读者优先、写者优先或近似公平；策略不同会改变吞吐与饥饿风险。若读临界区很短或写入频繁，普通 mutex 可能更简单、更快。
哲学家就餐把每个参与者需要同时取得两个资源的情况抽象出来。若所有参与者都先取得左侧资源，再等待右侧资源，就可能形成环形等待。给所有资源规定全局顺序，并要求每个线程按同一顺序获取，可以破坏这个环；限制同时尝试的人数或使用集中协调者也能改变条件。死锁会把这种现象归纳为四个必要条件，并比较预防、避免、检测与恢复。
三个问题对应三种不同问题：生产者-消费者等待状态，读者-写者选择访问策略，哲学家就餐管理多资源顺序。看到“多个线程”时直接加一把锁并不构成完整设计，必须先判断要保护的不变量、要等待的谓词和可能形成的资源依赖。
小结
| 概念 | 说明 |
|---|---|
| 竞态与临界区 | 找出依赖时序的共享不变量，并规定受保护访问区间 |
| 数据竞争 | 没有先行发生关系的冲突非原子访问，在 C 中属于未定义行为 |
| 原子操作 | 对单个对象执行不可分割的读、写或读改写 |
| 内存序 | 规定多个对象的访问以什么顺序被线程观察 |
| 测试并设置 / CAS | 构造原子状态转换和重试循环的硬件语义 |
| 锁 | 用自旋、阻塞或读写模式互斥进入临界区 |
| 信号量 | 保存许可数量并在许可不足时阻塞 |
| 条件变量 | 配合 mutex 等待共享谓词可能变为真 |
| 丢失唤醒 | 状态检查与登记等待不原子时永久错过通知 |
| Futex | 按用户空间值比较后阻塞或按地址唤醒的 Linux 接口 |
| 经典同步问题 | 组合互斥、条件等待、计数和锁顺序的分析模式 |
同步不是“阻止线程同时运行”，而是为共享状态建立原子性、可见顺序与等待协议；只有先确定不变量和谓词，再选择原子操作、锁、条件变量或 futex 层级，才能同时解释程序为何正确以及等待为何能够结束。
Linux 源码与接口入口：
pthread_mutex_lock(3p)：POSIX mutex 所有权与错误语义pthread_cond_wait(3p)：原子释放、等待和重新加锁sem_wait(3)：POSIX semaphore 计数与阻塞futex(2)：futex word、WAIT、WAKE 与比较后阻塞- Linux kernel memory barriers：原子性、屏障与内存顺序
- Atomic types：Linux 内核原子读改写接口
kernel/futex/：futex key、哈希等待队列与唤醒路径kernel/locking/mutex.c：内核 mutex 的快速路径、等待队列与乐观自旋nptl/lowlevellock.c：glibc 低层锁的 futex 慢速路径