并发原语 入门

并发 bug 共享 3 个根本原因:

• 竞态条件(race condition) —— 结果取决于线程调度的交错。 经典:共享计数器上的 x++ 是 load → add → store, 两线程竞争产出的计数器小于 increment 次数,因为它们的读 / 写交错了。
• 原子性违反 —— 看起来像一步、实际不是的操作。 check-then-act(「if (cache.contains(k)) cache.get(k)」)能在 check 和 act 之间被驱逐。大多数并发 bug 是躲在语言表达性抽象后面的原子性 bug。
• 内存可见性问题 —— 一个线程写一个值,另一个线程之后读、 看到老值(或撕裂的中间态)。cache-coherence primer 讲为啥这能在硬件层面发生; 修法是第 4 节的内存序机制。

共享状态问题

同一地址空间(process-thread primer)的两个线程共享堆和全局内存的每一字节。 没有显式同步,内核可以按任何交错调度它们 —— CPU 可以在每个线程内部重排它们的指令, 只要保留单线程程序顺序。

3 个应对策略涌现:

• 避免共享。最干净的方法。每线程状态、跨线程通信用 channel、 不可变数据结构。Erlang、Rust(不用 unsafe)、Go(用 channel)把这个推成默认。
• 锁住共享状态。把每次读和写包在 mutex 里。 写起来容易、难扩展(锁争用)、出现另一种 bug(死锁)。
• 无锁原子。用硬件原子原语(CAS、fetch-add)不锁更新共享状态。 最高吞吐、最难写对。这里第 4 节的内存序规则避不开。

为啥「直接用 mutex」有时是错的

锁好 reason about —— 临界区里一次一个线程。3 个失败模式在规模上打它们:争用(很多线程等同一把锁、调度器 thrash)、死锁(两个线程各持一把锁、互等对方的)、优先级反转(低优先级线程持着高优先级线程要的锁)。 每个都有自己的缓解(无锁、锁排序、优先级继承 mutex), 但根本约束不变:全局锁把吞吐封顶在每单 CPU 延迟一次临界区完成。

内核能帮什么、不能帮什么

内核能挂起线程(通过 mutex / condvar / sleep)、内核能送唤醒、内核能调度优先级。 内核不能强制你的代码按正确顺序释放锁、不重复 free 共享内存、 不在另一个线程写之前读一个值。这些是应用拥有的正确性合同 —— 语言 runtime 只能帮这么多(Rust 的 borrow checker 是把这些做成编译时错误的最激进尝试)。

Mutex

Mutex(mutual exclusion lock,互斥锁)确保任时只有一个线程在它临界区里。 操作:lock(获取;被别人持着就阻塞)和 unlock(释放)。实现:

• Spinlock —— 忙循环直到锁空。烧 CPU 但避开睡觉的 syscall 代价。 内核里给短临界区用,或者无锁库里给很短的争用用。
• 睡眠 mutex(pthread_mutex) —— 试着获取(常先 spin); 争用就 syscall 到内核在 futex 上睡(下一节)。标准用户态 mutex。
• 自适应 mutex —— 先 spin 几千周期、然后睡。 争用短就便宜;不短也对。

Mutex 争用是最常见的扩展瓶颈。perf lock、jstack线程 dump 分析、或 pprof 的 mutex profile 这些工具能找出哪把锁热。

Semaphore

Semaphore 是泛化到 N 的 mutex —— 同时最多 N 个线程在临界区里。 操作:wait(计数减 1;0 就阻塞)和 signal(计数加 1;有 waiter 就唤一个)。 用于限速(比如只允许 N 个并发连接到慢服务)、有界 buffer、资源池。

Condition variable

condvar 让一个线程等条件变真,由另一个线程信号。关键是它总跟 mutex 配对 —— condvar 协议是:

// waiter
lock(mtx);
while (!condition) {
    cond_wait(cv, mtx);  // 原子地释放 mtx 并睡;
                         // 唤醒时重新获取 mtx
}
// 这里条件为真
unlock(mtx);

// signaller
lock(mtx);
make_condition_true();
cond_signal(cv);  // 唤一个 waiter(或 cond_broadcast 全部)
unlock(mtx);

waiter 侧的 while 循环是必需的 —— 假唤醒(waiter 没有对应 signal 就醒)被 POSIX 允许, 而且多 waiter 情况下,另一个线程可能在这个轮到检查之前消费了 signal 的状态变化。 经典的「等、查、睡、再查」循环就是模式。

Condvar 是 Java 的 BlockingQueue、Go 的 sync.Cond、 Rust 的 channel 这些高层构造在底下怎么工作的。

RWLock

读写锁允许多个并发读者 OR 一个独占写者。读远多于写时有用 (缓存、配置),但簿记比普通 mutex 贵 —— 而且单个写者能被持续的读者流饿死 (大多数实现以公平为度优先写者)。

死锁

锁获取在两个线程各持一把锁、又需要对方的时,能死锁。经典 Coffman 4 条件: 互斥、hold-and-wait、不可抢占、循环等待。标准修法是锁排序 —— 总按固定全局顺序获取锁。静态分析工具(clang-tidy、Java 的 @GuardedBy 注解) 抓一些情况;运行时检测(gdb 的 mutex tracker、Java ThreadMXBean)抓另外的。 最干净的修法是完全不嵌套锁。

硬件原子操作

CPU 暴露一小组操作,相对其他核原子地 read-modify-write 一个内存位置。 x86 上,大多数编码为普通指令带 LOCK 前缀:

• LOCK XADD —— 原子 fetch-and-add。返回旧值、加。原子计数器用。
• LOCK CMPXCHG —— 原子 compare-and-swap。如果内存等于期望,设新值; 返回是否换了。每个无锁算法的基础。
• LOCK BTS / BTR —— 原子位置位 / 位清。一些锁实现里当轻量信号用。
• 合适对齐的 MOV —— x86 上自然对齐的 1/2/4/8 字节 store 本身就原子 (不需要 LOCK),但你仍需要内存序注解给其他核的可见性。

ARM 用不同机制:LDREX(load-exclusive)保留一条 cache line,STREX 试着写 —— 只在 LDREX 之后没别的核碰过这条 line 时成功。 CAS 变成小重试循环。ARMv8.1 加了直接 CASAL / SWPAL指令,简单情况下作为更快的替代。

代价(cache-coherence primer):不争用原子 ~10-25 cycle、争用每弹跳 ~100 ns。 无锁不是免费的。

Futex —— 快用户态 mutex

Futex(Fast Userspace muTEX)是 Linux 内核原语, 让用户态用最少内核卷入实现锁。关键洞察:锁不争用时不需要 syscall —— 就在用户态做一次原子 compare-and-swap。只在争用时内核需要把 waiter 放睡。

Futex syscall(futex(addr, op, val, ...))操作:

• FUTEX_WAIT —— 「原子地检查 *addr == val,是的话睡到在这 addr 上被唤」。 原子检查防止 lost-wakeup 竞态。
• FUTEX_WAKE —— 唤这 addr 上等的 N(通常 1)个 waiter。
• FUTEX_REQUEUE —— 唤一些、把别的搬到不同 futex。 pthread_cond_broadcast 用以避免惊群问题。

pthread_mutex 怎么用 futex

现代 pthread_mutex_lock 实现大致:

int* state;  // 0 = 未锁、1 = 锁、2 = 锁-有-waiter

// 快路径:compare-and-swap 0 → 1
if (CAS(state, 0, 1) == 0) return;  // 无争用、完成 —— 无 syscall

// 争用路径:标成 locked-with-waiters 然后睡
while (true) {
    int v = atomic_exchange(state, 2);  // 标成有 waiter
    if (v == 0) return;                 // 拿到了
    futex_wait(state, 2);               // 睡到被唤
}

// unlock
if (atomic_exchange(state, 0) == 2) {   // 之前是 locked-with-waiters?
    futex_wake(state, 1);                // 唤一个 waiter
}

快路径是一条原子指令 —— 无 syscall、~10 ns。 慢路径是一次 futex_wait syscall —— ~1 μs。所以 mutex 不争用时非常便宜、 争用时也合理便宜;最坏情况(很多线程持续争用)被弹跳 state cache line 的代价主导。

无锁数据结构

只用原子原语而不用锁构建队列 / 栈 / 哈希表。好处:没线程能被慢同伴阻塞 (没死锁、没优先级反转)。代价:正确实现它们是出了名的难、ABA 问题让朴素 CAS 循环错、 回收移除节点的内存是它自己的问题(hazard pointer、基于 epoch 的回收、RCU)。 Java 的 ConcurrentLinkedQueue、C++ Boost.lockfree、Rust 的 crossbeam 是生产就绪的实现。

单线程里,as-if 规则保证程序按程序顺序看到自己的操作 —— 编译器只要可观察结果相同,内部能重排它们。跨线程,无此保证。 线程 B 读两个线程 A 写的值,可能以任一顺序、任一交错看到它们 —— 除非语言和 CPU 同意强制特定顺序。

你要懂的 4 个内存序

• relaxed —— 只有原子性、无顺序保证。 原子操作作为单步完成(无撕裂读),但 CPU 和编译器可以自由跨它重排周围操作。 用于只 care 最终总数不 care 顺序的计数器。
• acquire —— load 屏障。这个 load 返回之后, 这个线程里所有后面的操作都保证之后发生 —— 没有重排到前面。 跟另一个线程上的 release 配对。
• release —— store 屏障。这个线程里 release 之前的所有操作, 保证对任何在同一个原子上 acquire 的线程可见。没有重排过 release。
• seq_cst(顺序一致) —— 最强、是 C++ 默认。 加上:所有线程上所有 seq_cst 操作对一个单一全局总序达成一致。 比 acquire-release 强,给少数你需要的情况(Peterson 算法、某些无锁构造)。

acquire-release 模式

Producer-consumer 场景是经典用法:

// producer
data = compute();                   // 可以 relaxed 或非原子
flag.store(true, memory_order_release);

// consumer
while (!flag.load(memory_order_acquire)) {}
use(data);                          // 看到 producer 写的 data

Producer store 上的 release + consumer load 上的 acquire 建立 happens-before 关系: Producer 在 release 之前做的一切,在 acquire 之后对 consumer 可见。 每个引用计数、每个 wait-free 信号、每个 spsc 队列建在这之上。

为啥这随架构变

x86 是 TSO(Total Store Order):免费的、每个 load 都像 acquire、 每个 store 都像 release —— 只允许不同地址间的 store-load 重排。 意思是「x86 上 work」的无锁代码可能在 ARM 上坏,ARM 弱得多。 真实例子:朴素 C++ 里的 data; flag = true; 在 x86 上即便没原子也 work, 但 ARM 上编译器 / CPU 能自由重排,consumer 可能在 data 之前看到 flag。

seq_cst 在 x86 上额外花钱(每个 seq_cst store 一个 MFENCE)、ARM 上更多 (load 和 store 都要 DMB ISH)。性能感知的选择是用给你需要的保证的最弱的序: counter 用 relaxed、signal 用 acquire-release、只在你真需要跨地址全局序时才 seq_cst。

经典错误

因为「更快」就默认 relaxed。Relaxed 序不建立任何跟其他操作的 happens-before 关系。 给 per-thread 统计用 counter.fetch_add(1, relaxed) 的代码没事; 给 signal「数据就绪」用 flag.store(true, relaxed), 在弱序硬件上会悄无声息腐蚀 consumer 对 data 的视图。 经验法则:如果别的代码依赖原子之前做的,你需要 release;依赖之后来的,需要 acquire。

Code review 红旗

• 没 while 循环的 condvar wait。POSIX 允许假唤醒;没循环的话,你醒了对一个可能不真的状态动作。
• 跨线程 signal 用 memory_order_relaxed。x86 上 work、ARM 上坏。任何建立可见性关系的东西至少用 acquire-release。
• 不同路径里以不同顺序获取多把锁。等着死锁。建立并文档化全局锁序;用静态分析断言。
• 跨 syscall 持着 mutex。syscall 阻塞(read、write、文件 open 等等),想要同一 mutex 的其他线程都干等。 重构成在临界区外做 syscall。
• 手写无锁数据结构。总是 bug。 用库(Java 的 java.util.concurrent、C++ Boost.lockfree、Rust crossbeam) 或者退化到 mutex。