锁、死锁和竞态条件
锁、死锁和竞态条件
两个人同时去银行转账，A 把 1000 元转给 B，B 同时把 500 元转给 A。如果银行系统设计不当，这两笔操作可能互相干扰：先读后写、两边同时扣款导致余额错误，甚至钱凭空消失。这就是竞态条件（Race Condition）——程序的结果取决于多个线程执行的先后顺序，而这个顺序是不确定的。
并发 bug 是软件中最难复现、最难调试的一类 bug。它们在测试时不出现，在生产环境偶尔发生，而且每次重现时行为可能都不同。理解并发的陷阱，是成为高级工程师的必经之路。
Level 1：建立直觉
竞态条件：定时是问题所在
// 两个线程同时对银行账户转账
int balance = 1000;
// 线程1：存入100元
void deposit(int amount) {
int temp = balance; // 读余额
temp = temp + amount;
balance = temp; // 写余额
}
// 线程2：取出200元
void withdraw(int amount) {
int temp = balance; // 读余额
temp = temp - amount;
balance = temp; // 写余额
}
如果两个线程同时执行，可能发生：
时间轴：
T1: temp1 = balance(1000)
T2: temp2 = balance(1000) ← 也读到 1000！
T1: temp1 = 1000 + 100 = 1100
T2: temp2 = 1000 - 200 = 800
T1: balance = 1100
T2: balance = 800 ← 覆盖了 T1 的结果！
最终余额：800（而不是正确的 900）
损失了 100 元！
这就是**写后写（Write After Write）**的竞态，也叫"丢失更新（Lost Update）"。
锁：给共享资源上锁
解决竞态的最直接方法：互斥锁（Mutex）——同一时刻只允许一个线程进入"临界区"。
#include <pthread.h>
int balance = 1000;
pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;
void deposit(int amount) {
pthread_mutex_lock(&lock); // 进门：如果锁被占用，等待
int temp = balance;
temp = temp + amount;
balance = temp;
pthread_mutex_unlock(&lock); // 出门：释放锁，唤醒等待者
}
void withdraw(int amount) {
pthread_mutex_lock(&lock);
int temp = balance;
temp = temp - amount;
balance = temp;
pthread_mutex_unlock(&lock);
}
现在，临界区内只有一个线程，竞态消失了——但代价是，一个线程等待时，另一个被阻塞，并发度降低。
死锁：互相等待，永无止境
锁解决了竞态，但引入了新问题：死锁（Deadlock）。
pthread_mutex_t lock_A = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t lock_B = PTHREAD_MUTEX_INITIALIZER;
// 线程1：先拿 A，再拿 B
void thread1() {
pthread_mutex_lock(&lock_A);
sleep(1); // 让线程2有机会拿到 lock_B
pthread_mutex_lock(&lock_B); // 等待 lock_B，但它被线程2持有！
// ... 做某事 ...
pthread_mutex_unlock(&lock_B);
pthread_mutex_unlock(&lock_A);
}
// 线程2：先拿 B，再拿 A
void thread2() {
pthread_mutex_lock(&lock_B);
sleep(1); // 让线程1有机会拿到 lock_A
pthread_mutex_lock(&lock_A); // 等待 lock_A，但它被线程1持有！
// ... 做某事 ...
pthread_mutex_unlock(&lock_A);
pthread_mutex_unlock(&lock_B);
}
死锁示意图：
线程1 持有 A → 等待 B
↑ ↓
线程2 持有 B → 等待 A
循环依赖，两个线程永远等待对方。
死锁的四个必要条件（Coffman 条件，1971年）：
- 互斥：资源不能同时被多个线程持有
- 持有并等待：持有资源的同时等待其他资源
- 不可剥夺：持有的资源不能被强制取走
- 循环等待：线程形成循环的等待链
打破任意一个条件即可预防死锁。
活锁和饥饿
活锁（Livelock）：线程都在"动"，但没有进展：
想象两个人在走廊相遇，互相让路：
甲左闪 → 乙也左闪 → 甲右闪 → 乙也右闪 → 循环...
饥饿（Starvation）：某个线程因为优先级低，一直得不到锁（别的线程总是比它先抢到）。
Level 2：原理剖析
互斥锁的底层实现
操作系统如何实现"只允许一个线程进入"？
自旋锁（Spinlock）：
// 原子 CAS（Compare-And-Swap）实现自旋锁
typedef atomic_flag SpinLock;
void spin_lock(SpinLock* lock) {
// 循环直到成功把 flag 从 false 改为 true
while (atomic_flag_test_and_set(lock)) {
// 在等待时不断循环（"自旋"）
// CPU 一直在忙，只是做无用功
}
}
void spin_unlock(SpinLock* lock) {
atomic_flag_clear(lock);
}
自旋锁适合锁持有时间极短的场景（微秒级），避免了线程睡眠/唤醒的开销。Linux 内核大量使用自旋锁（因为内核不能在持有自旋锁时睡眠）。
互斥锁（Mutex）：如果锁被占用，线程睡眠（让出 CPU），等待被唤醒：
mutex_lock 流程：
1. 尝试原子获取锁
2. 成功 → 进入临界区
3. 失败 → 把自己加入等待队列
→ 设置状态为 WAITING
→ 调用调度器（让出 CPU）
→ ... 等待 ...
4. 锁释放时 → 唤醒等待队列中的一个线程
→ 该线程回到 RUNNABLE 状态
睡眠比自旋节省 CPU，但涉及两次系统调用（睡眠 + 唤醒），开销约 2-10µs。
混合策略（Adaptive Mutex）：先短暂自旋（几十个周期），如果还没拿到锁则睡眠。Linux 的 pthread_mutex 在竞争激烈时会自动转为自旋等待。
读写锁（Read-Write Lock）
很多场景是"多读少写"：多个线程可以同时读，但写时必须独占。
pthread_rwlock_t rwlock = PTHREAD_RWLOCK_INITIALIZER;
// 多个读线程可以同时进行
void reader() {
pthread_rwlock_rdlock(&rwlock); // 共享读锁
// 读操作...
pthread_rwlock_unlock(&rwlock);
}
// 写线程需要独占访问
void writer() {
pthread_rwlock_wrlock(&rwlock); // 独占写锁
// 写操作...
pthread_rwlock_unlock(&rwlock);
}
读写锁对只读操作完全没有竞争，大大提高读密集型系统的并发度（如数据库索引查询）。
条件变量：等待特定条件
有时线程不是等待锁，而是等待某个"条件"成立：
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t cond = PTHREAD_COND_INITIALIZER;
int ready = 0;
// 等待方
void waiter() {
pthread_mutex_lock(&mutex);
while (!ready) { // 必须用 while 而不是 if（防止虚假唤醒）
pthread_cond_wait(&cond, &mutex);
// wait 原子地：释放 mutex + 睡眠
// 被唤醒后：重新获取 mutex
}
// 处理 ready 状态...
pthread_mutex_unlock(&mutex);
}
// 通知方
void notifier() {
pthread_mutex_lock(&mutex);
ready = 1;
pthread_cond_signal(&cond); // 唤醒一个等待者
// pthread_cond_broadcast(&cond); // 唤醒所有等待者
pthread_mutex_unlock(&mutex);
}
内存序（Memory Order）和 happens-before
Java 的 Doug Lea 和 C++ 委员会花了多年定义内存模型：什么时候，线程 A 写入的值对线程 B 可见？
happens-before 关系：
如果操作 X happens-before 操作 Y，则 X 的结果对 Y 可见。
建立 happens-before 的方式：
1. 程序顺序（同一线程，前面的 happens-before 后面的）
2. mutex 的 unlock happens-before 下次 lock
3. volatile 写 happens-before 下次 volatile 读（Java）
4. atomic_store(release) happens-before atomic_load(acquire) 读到该值时
5. thread.start() happens-before 线程第一条指令
6. 最后一条指令 happens-before thread.join() 返回
不建立 happens-before 就没有可见性保证——即使物理上已经写入内存，另一个线程也可能读到旧值（因为 CPU 缓存、编译器优化）。
Level 3 · 规范怎么定义的（资深）
并发正确性的形式化理论
互斥（Mutual Exclusion）问题的形式化定义可以追溯到 Edsger Dijkstra 1965 年的经典论文 "Solution of a Problem in Concurrent Programming Control"。Dijkstra 定义了互斥的三个必要条件：（1）安全性——任意时刻最多一个进程在临界区；（2）活性——如果没有进程在临界区且有进程想进入，最终某个进程能进入；（3）公平性——每个请求进入的进程最终都能进入。
Leslie Lamport 在 1977 年提出了 Bakery 算法，证明了不依赖原子硬件指令也能实现互斥——但代价是需要 N 个共享变量（N 为进程数）和 O(N) 的进入/退出开销。现代互斥锁依赖硬件原子指令（如 x86 的 LOCK CMPXCHG、ARM 的 LDXR/STXR），在无竞争情况下只需一条原子指令即可获取锁。
内存一致性模型方面，x86 架构使用 TSO（Total Store Order） 模型——Intel 在 SDM 中用"happens-before"关系的集合形式化定义了 TSO 的保证：所有存储（store）操作按程序顺序对其他核心可见，但存储可以被后续的加载（load）"超越"。ARM 和 RISC-V 使用弱序模型，几乎不保证跨核心的操作顺序，必须通过显式的屏障指令（DMB/DSB/ISB）或原子操作来建立顺序。C++11/C11 的原子操作库（<atomic>）提供了可移植的内存序抽象，编译器负责在不同架构上插入正确的屏障指令。
Level 4 · 边界与陷阱（所有人）
陷阱 1：TOCTOU 竞态——检查和使用之间的时间窗口
"先检查再操作"（Time-of-Check to Time-of-Use, TOCTOU）是最常见的竞态模式。典型例子：先 access() 检查文件权限，再 open() 打开文件——但在两步之间，攻击者可能用符号链接替换了文件，导致程序打开了不该打开的文件（如 /etc/shadow）。Linux 的 openat() 系列调用和 O_NOFOLLOW 标志可以缓解这一问题，但完全消除 TOCTOU 需要将检查和操作合并为一个原子操作。数据库中的"SELECT 后 INSERT"也是同类问题——正确做法是使用 INSERT ... ON CONFLICT 或事务隔离级别来保证原子性。
陷阱 2：自旋锁在抢占式调度下可能导致活锁
自旋锁（spinlock）在等待锁释放时不会让出 CPU，而是不断循环检测。如果持锁线程被操作系统抢占（调度走了），等锁线程会白白自旋一个完整的时间片（数毫秒），浪费 100% 的 CPU。更糟糕的是，在单核系统上，持锁线程被抢占后，自旋线程占据唯一的 CPU 核心，持锁线程永远无法被调度执行来释放锁——形成活锁。Linux 内核的自旋锁在持锁期间会禁用抢占（preempt_disable()），但用户态的自旋锁没有这个保护。用户态代码应优先使用 pthread_mutex（在竞争时会让出 CPU），只在确定锁持有时间极短（小于一次上下文切换的开销）时才考虑自旋。
陷阱 3：双重检查锁定（DCLP）在没有内存屏障时是错误的
单例模式的经典实现——"先检查指针是否为空，如果为空则加锁再检查一次"（Double-Checked Locking Pattern）——在 C++ 11 之前是未定义行为。原因是编译器和 CPU 可能重排指令：对象的构造函数可能尚未执行完毕，但指针已经被赋值。另一个线程看到非空指针就直接使用，访问到了半构造的对象。C++11 的 std::atomic 和 Java 5 的 volatile 关键字通过引入 acquire/release 语义修复了这个问题，但老版本代码中（以及不正确使用 volatile 的 C 代码中）这仍然是一个陷阱。