竞态条件与临界区：并发的本质问题

一句话定义

竞态条件（race condition）指程序结果依赖于多个执行流的相对时序；访问共享资源且不允许交错执行的代码段称为临界区（critical section），并发正确性的目标就是让临界区互斥地执行。

为什么重要

这是全库最重要的一类 bug：平时跑得好好的，上线偶发数据损坏。它无法靠测试可靠复现，只能靠原理性设计消除。内核里遍布共享数据结构（就绪队列、文件表），没有临界区纪律，操作系统本身一天都跑不稳。

前置知识

kp-008（多线程共享地址空间）；kp-006（中断与调度可在任意指令边界切换）。

核心概念

• 原子性（atomicity）：操作要么全部完成、要么不发生，中间状态不可见。
• 临界区：访问共享资源的代码段，同一时刻至多一个执行流进入。
• 互斥（mutual exclusion）：不同时进入临界区的性质。
• 前进（progress）与有限等待（bounded waiting）：不能无限阻塞想进临界区的人、不能无限饿死某个执行流。
• 数据竞争（data race）：两个流无同步地访问同一内存且至少一个是写——C/C++ 标准定义为未定义行为。

原理与机制

counter++ 不是原子操作，它编译为三条指令。两个线程各执行一次的交错：

线程A: load counter -> 寄存器        counter = 50
线程B: load counter -> 寄存器        counter = 50   (读到旧值!)
线程A: add; store counter           counter = 51
线程B: add; store counter           counter = 51   (更新丢失，应为 52)

丢失更新发生在任意交错下，于是"跑一万次结果都对、生产环境丢数据"。Dijkstra 归纳出正确解法必须同时满足互斥、前进、有限等待三条件；Peterson 算法用两个标志位加 turn 变量在纯软件层面实现互斥：

共享: flag[2] = {false,false}; turn;
线程i 进入区:
  flag[i] = true; turn = j;            // 礼让对方
  while (flag[j] && turn == j) ;       // 忙等对方让出
  ... 临界区 ...
  flag[i] = false;                     // 退出区

Peterson 算法证明了互斥可以不靠硬件，但它在现代乱序 CPU 上必须配合内存屏障才正确（伏笔见 kp-015）；实践中使用的都是硬件原子指令方案（kp-012）。

图示

无保护:  A[load 50][add][store 51]      结果 51  <-- 错
         B      [load 50].....[add][store 51]
加锁后:  A[lock][load 50][add][store 51][unlock]
         B      [lock 等待].......[lock][load 51][add][store 52]  正确

直观类比

临界区像单人洗手间：门锁（互斥原语）保证同时只有一人在内；"前进"要求里面没人时别人能进去；"有限等待"要求排队的人终能轮到，不能被永远插队。

实例或案例

可复现实验（C，多线程无锁计数器）：

/* gcc -pthread race.c && ./a.out  预期 2000000，实际通常更小且每次不同 */
#include <pthread.h>
static long counter = 0;
void* add(void* a){ for(long i=0;i<1000000;i++) counter++; return NULL; }
int main(void){ pthread_t t[2];
  pthread_create(&t[0],NULL,add,NULL); pthread_create(&t[1],NULL,add,NULL);
  pthread_join(t[0],NULL); pthread_join(t[1],NULL);
  printf("%ld\n", counter); return 0; }

观察结果小于 2000000 且逐次不同，即丢失更新的直接证据；给 counter++ 包上互斥锁后结果稳定（锁的实现见 kp-012）。

常见误区

• 认为单条语句是原子的：counter++、甚至 64 位变量赋值在 32 位平台都不是。
• 认为加锁只是"以防万一"性能优化：数据竞争在语言标准层面是未定义行为，优化器可以基于它做出任何变换。
• 认为测试通过就是线程安全：竞态依赖时序，测试只能证明 bug 存在，不能证明不存在。

与其他知识点的关系

kp-012 提供可用的锁实现；kp-013 展示用信号量协调多临界区的模式；kp-015 讲为什么纯软件方案在现代 CPU 上还差一口气。

延伸阅读

《操作系统导论》并发章节开篇；man 7 pthreads 对数据竞争的正式定义。

自测题

1. 竞态条件、数据竞争、临界区三者的关系？

答：临界区是访问共享资源的代码段；缺少互斥的临界区执行产生数据竞争；数据竞争的外在表现与后果即竞态条件（结果依赖时序）。

1. Peterson 算法满足了哪三个条件？

答：互斥、前进、有限等待；其正确性依赖加载/存储的顺序性，在需要内存屏障的现代 CPU 上必须补屏障才能成立。

1. 为什么"测试多次都正确"不能证明没有竞态？

答：竞态由特定交错触发且概率性出现，测试覆盖的时序是全部可能交错中的极小样本。