跳转至

竞态、原子性与锁

并发错误难以复现，因为它不只由输入决定，还由调度、缓存和硬件执行时序决定。理解并发的第一步，是把一行源代码拆成可能交错的基本动作。

最小例子：丢失更新

两个线程共享 counter = 0，各执行一次：

counter++;

这行代码通常可抽象为读取、加一、写回：

时刻 线程 A 线程 B 内存中的 counter
1 读到 0 0
2 读到 0 0
3 计算 1 0
4 计算 1 0
5 写入 1 1
6 写入 1 1

期望结果是 2，实际可能是 1。每个线程局部计算都没错，错误来自复合操作的交错。

三个相关但不同的概念

  • 数据竞态：多个执行流并发访问同一内存位置，至少一个写入，且缺少语言或系统要求的同步。
  • 竞态条件：结果依赖事件顺序，且某些顺序违反需求。它比数据竞态更广，例如两个安全原子操作也可能组成错误的“先检查再执行”。
  • 原子性违反：本应作为不可分割整体观察的操作被其他执行流插入。

无数据竞态不自动等于业务正确。假设余额查询和扣款各自是原子的，两个线程仍可能都先看到余额足够，再分别扣款，破坏“余额不为负”的复合不变量。

临界区与不变量

临界区是访问共享状态、必须按同步协议执行的代码区域。设计锁时不应从“哪几行要加锁”出发，而应先写出不变量。

例如有界队列：

\[ 0\le count\le capacity. \]

队头、队尾和元素计数必须作为一个一致状态更新。只锁住 count++，却不锁数组写入和尾指针移动，仍然错误。

一个基本临界区方案希望满足：

  1. 互斥：同一时刻至多一个参与者进入。
  2. 进展：无人处于临界区时，等待者最终可被选择。
  3. 有界等待：某个参与者不会永远被其他人插队。

具体原语可能只直接保证其中一部分，公平性还依赖调度器和实现。

硬件原子指令

锁最终需要硬件提供某种不可分割的读—改—写能力，例如交换、比较并交换或 load-linked/store-conditional。

比较并交换可抽象为：

CAS(address, expected, desired):
    atomically:
        if *address == expected:
            *address = desired
            return success
        return failure

一个简单自旋锁可以反复尝试把状态从 0 改为 1：

while (!compare_exchange(&lock, 0, 1)) {
    cpu_relax();
}

/* critical section */

store_release(&lock, 0);

这只是概念代码。真实实现还要处理内存序、公平性、抢占、NUMA 流量和调试信息。

自旋锁与互斥锁

自旋锁

等待者持续占用 CPU 检查锁。适合：

  • 临界区非常短。
  • 持锁者正在另一个核心运行。
  • 当前上下文不能睡眠。

不适合长临界区或单核上持锁者无法运行的情形。大量等待者同时写锁变量会制造缓存一致性风暴，成熟实现常使用退避或队列锁。

可睡眠互斥锁

竞争时，等待线程进入内核等待队列并让出 CPU；释放锁时再唤醒。它避免长时间空转，但阻塞和唤醒涉及调度开销。

粗略地，设预计等待时间为 \(t_w\)，阻塞加唤醒成本为 \(t_b\)：

  • 当 \(t_w\ll t_b\) 时，自旋可能更便宜。
  • 当 \(t_w\gg t_b\) 时，睡眠通常更合适。

真实选择还受核心数、优先级、功耗和临界区可抢占性影响。

最小正确例子

用 POSIX 互斥锁保护复合更新：

#include <pthread.h>

static long counter = 0;
static pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;

void increment(void) {
    pthread_mutex_lock(&mutex);
    counter += 1;
    pthread_mutex_unlock(&mutex);
}

关键不只是 counter += 1 被包住，而是所有访问 counter 的线程都遵守同一协议。若另一个线程无锁读取，仍可能违反语言内存模型。

锁与内存可见性

现代编译器和 CPU 可以在不改变单线程结果的前提下重排操作；多核还各自拥有缓存。同步原语因此同时承担：

  1. 互斥或原子更新。
  2. 建立跨线程的可见性和顺序关系。

典型的 release—acquire 关系表示：释放前的写入，对成功获取同一同步对象后的读取可见。

volatile 通常不提供这种跨线程同步语义。它可能限制某些编译优化或用于设备寄存器，但不能替代互斥锁或语言定义的原子类型。

锁粒度

粗粒度锁

一个锁保护大块状态，优点是协议简单、不变量集中、死锁风险较低。缺点是无关操作也互相阻塞，限制多核并行。

细粒度锁

按对象、桶或区间加锁能提高并行度，却增加：

  • 锁顺序与死锁风险。
  • 对象销毁和引用管理难度。
  • 跨多个对象维护不变量的复杂度。
  • 锁本身的内存和缓存开销。

“锁越细越快”并不成立。低竞争工作负载下，复杂同步可能比受保护工作更贵。

常见错误

检查后执行

if (!queue_empty()) {
    item = queue_pop();
}

若检查和弹出不在同一临界区，其他线程可在两者之间改变队列。

错误路径忘记解锁

多个提前返回会让锁永久保持。结构化清理、作用域锁或统一退出路径可以降低风险。

持锁执行未知代码

回调、阻塞 I/O 或可能再次获取锁的函数会放大临界区，并引入重入和死锁风险。常见做法是在锁内复制必要状态，解锁后再执行外部操作，但前提是对象生命周期安全。

双重检查缺少安全发布

“先无锁看指针，空时再加锁初始化”需要语言内存模型支持，不能只凭源代码顺序判断对象已经完整可见。优先使用一次性初始化原语。

原子操作能否替代锁

单个计数器、标志或指针有时适合原子操作。涉及多个字段、复杂不变量或需要等待条件时，锁通常更易证明正确。

无锁算法避免一个暂停线程持锁阻塞所有人，但不等于无等待，也不保证更快。它还要处理 ABA、内存回收和更复杂的内存序。选择无锁结构应基于测量和明确进展需求，而不是因为“没有锁”听起来先进。

历史联系

早期互斥算法尝试只用普通读写协调少量参与者，后来硬件原子指令提供更可靠基础。多核和 NUMA 让锁实现从简单测试—设置发展到退避、排队和分层锁。语言内存模型则明确了编译器优化下何种跨线程观察是合法的。

自测

  1. counter++ 为什么不是天然原子操作？
  2. 没有数据竞态的程序是否一定没有竞态条件？
  3. 自旋锁在持锁线程被抢占时可能发生什么？
  4. 为什么所有访问者都必须遵守同一锁协议？
  5. 原子计数器何时合适，何时应使用锁？
参考思路

自增包含多步读改写。原子操作之间仍可能形成错误的检查—执行顺序。持锁者不运行时，等待者只会浪费 CPU。无锁读取可能破坏可见性和一致性。单字段独立统计适合原子，多字段不变量或条件等待更适合锁。