第14讲 同步原语 I：从竞争条件到互斥锁

本文根据《第14讲 同步原语I.md》的对话转录整理而成。核心问题是：当多个线程或进程同时访问共享资源时，如何保证它们不会因为执行顺序不可控而破坏数据一致性。

1. 本讲要解决什么问题

前面学习 IPC 时，共享内存解决的是“多个进程能不能看到同一块数据”。但共享内存本身并不保证安全。

真正的问题是：

多个线程或进程同时访问同一份共享数据时，谁先读、谁先写、谁能修改、谁必须等待？

如果没有同步机制，就可能出现：

• 两个线程同时修改同一个变量；
• 两个生产者写入同一个缓冲区位置；
• 一个线程读到另一个线程写了一半的数据；
• 程序结果依赖不可预测的调度顺序。

所以本讲的主线是：

1
2
3
4
5
6
7
8
9
10
11
12
13

共享数据
  ↓
并发访问
  ↓
竞争条件
  ↓
临界区
  ↓
互斥访问
  ↓
同步原语
  ↓
互斥锁 / 自旋锁 / Ticket Lock

❗ 本节核心结论： 同步原语解决的不是“能不能共享数据”，而是“共享数据怎样被安全访问”。

2. 为什么 balance++ 会出错

很多人会误以为：

1

balance++;

是一条不可分割的语句。

但在机器层面，它通常会被拆成类似这样的步骤：

1
2
3

ldr  r3, [r2]      // 读取 balance
adds r3, r3, #1    // 加 1
str  r3, [r2]      // 写回 balance

也就是说，balance++ 本质上是：

1

读 → 改 → 写

这三个动作之间可能被其他线程插入。

假设初始：

1

balance = 10

两个线程同时执行 balance++：

1
2
3
4
5
6

线程 A：读 balance = 10
线程 B：读 balance = 10
线程 A：计算 11
线程 B：计算 11
线程 A：写回 11
线程 B：写回 11

最终结果是：

1

balance = 11

但正确结果应该是：

1

balance = 12

问题不在于加法本身复杂，而在于“读、改、写”不是原子的。

3. 竞争条件 Race Condition

竞争条件指的是：

多个线程同时访问共享数据，并且最终结果依赖于具体执行顺序。

它通常满足三个条件：

1. 存在多个并发执行流；
2. 它们访问同一份共享数据；
3. 至少有一个执行流会修改数据；
4. 程序结果依赖访问顺序。

例如：

1
2

buffer[buffer_write_cnt] = msg;
buffer_write_cnt = (buffer_write_cnt + 1) % 5;

如果两个生产者同时执行：

1
2
3
4

生产者 A 读到 buffer_write_cnt = 2
生产者 B 也读到 buffer_write_cnt = 2
生产者 A 写 buffer[2]
生产者 B 也写 buffer[2]

结果就是两个生产者写到了同一个缓冲区位置，导致数据覆盖。

竞争条件最麻烦的地方是：它不一定每次都出现。程序可能运行十次都正常，第十一次才出错。

因此：

程序“偶尔正确”，不代表程序没有并发问题。

❗ 本节核心结论： 竞争条件的本质是共享数据的最终状态依赖不可控的线程交错顺序。

4. 临界区 Critical Section

临界区是指：

访问共享资源，并且多个线程同时进入会导致错误的代码区域。

例如：

1
2

buffer[buffer_write_cnt] = msg;
buffer_write_cnt = (buffer_write_cnt + 1) % 5;

这段代码访问了共享的 buffer 和 buffer_write_cnt，如果多个线程同时进入，就可能发生覆盖。因此它应当被视为临界区。

但要注意：

不能简单断言“程序中互斥的区域就是临界区”。

更准确的说法是：

需要被互斥保护的共享资源访问区域，通常就是临界区。

也就是说，临界区的关键不是“它被加锁了”，而是：

• 它访问共享资源；
• 并发访问会出错；
• 所以它需要互斥保护。

如果你把一段完全不访问共享资源的代码也加锁，它虽然被互斥执行，但不一定是概念上真正的临界区。

5. 解决临界区问题的三个要求

一个合格的临界区解决方案通常要满足三个要求：

这三个要求不是一回事。

例如，普通自旋锁可以保证互斥访问，但不一定保证有限等待。因为多个线程抢锁时，某个线程可能运气很差，一直抢不到。

6. 为什么关闭中断在多核下不够

在单核系统中，关闭中断可以在一定程度上保护临界区。因为线程切换通常依赖时钟中断。关闭中断后，当前线程不会被调度器打断。

但在多核系统中，这种方法不够。

原因是：

关闭当前 CPU 核的中断，只能防止当前核被打断，不能阻止其他 CPU 核上的线程同时运行。

例如：

1
2

CPU0：线程 A 关闭中断，进入临界区
CPU1：线程 B 仍然可以运行，也进入同一个临界区

这样仍然会破坏互斥访问。

所以，多核系统需要跨 CPU 生效的同步机制，例如互斥锁、原子操作、自旋锁等。

❗ 本节核心结论： 关闭中断只能控制当前 CPU 的调度行为，不能阻止其他 CPU 核并发访问共享资源。

7. Peterson 算法：软件层面的临界区门卫

Peterson 算法是一种经典的软件互斥算法，主要用于两个线程。

它使用两个变量：

1
2

flag[i] = true;  // 表示线程 i 想进入临界区
turn = j;        // 表示如果冲突，就让线程 j 先进

线程 0 的逻辑大致是：

1
2
3
4
5
6
7
8
9

flag[0] = true;
turn = 1;

while (flag[1] == true && turn == 1)
    ;

进入临界区;

flag[0] = false;

线程 1 类似，只是编号反过来。

Peterson 算法的思想不是“谁抢得快谁进”，而是“如果双方都想进，就通过 turn 谦让”。

可以这样理解：

如果只有线程 0 想进入，flag[1] == false，线程 0 可以直接进入。

如果两个线程都想进入，就看 turn。turn 只能是 0 或 1，因此最终只会允许一个线程进入，另一个等待。

所以，Peterson 算法可以理解为：

解决“谁可以进入临界区”的软件门卫算法。

它不是处理临界区里面的业务逻辑，而是处理临界区入口处的进入控制问题。

8. Peterson 算法为什么受现代 CPU 限制

Peterson 算法依赖一个重要前提：

程序中的读写操作严格按照代码顺序执行，并且其他 CPU 看到的顺序也符合这个顺序。

但现代 CPU 可能进行乱序执行 out-of-order execution。

8.1 什么是乱序执行

程序顺序可能是：

1
2
3
4

flag[0] = true;
turn = 1;
while (flag[1] && turn == 1)
    ;

程序员以为 CPU 一定按下面顺序执行：

1
2
3

1. 写 flag[0]
2. 写 turn
3. 读取 flag[1] 和 turn

但现代 CPU 为了提高性能，可能在不影响单线程结果的前提下调整执行顺序。

例如：

• 写操作可能先进入 store buffer，尚未立刻被其他 CPU 看到；
• 后面的读操作可能先执行；
• 不同 CPU 核看到内存变化的时间可能不同。

于是，在另一个线程看来，可能出现：

1
2

线程 0 还没真正让其他 CPU 看到 flag[0] = true
线程 0 已经开始检查 flag[1]

这样两个线程都可能误以为对方没有申请进入临界区，最终同时进入临界区。

8.2 为什么 CPU 要设计乱序执行

原因很简单：

CPU 很快，内存很慢。

如果 CPU 必须严格等每条指令完成后再执行下一条，会经常空等。

例如：

1
2

a = load_from_memory();  // 很慢
b = 1 + 2;               // 很快，且不依赖 a

如果 b = 1 + 2 不依赖 a，CPU 可以先算 b，不必等待内存加载完成。

乱序执行的好处包括：

• 提高流水线利用率；
• 隐藏访存延迟；
• 增加指令级并行性；
• 提高单核性能。

但并发算法往往依赖“其他线程看到的内存顺序”。这就使裸 Peterson 算法在现代硬件上不可靠。

现代系统通常使用：

• 硬件原子操作；
• 内存屏障 memory barrier；
• C/C++ std::atomic；
• 操作系统提供的互斥锁。

❗ 本节核心结论： Peterson 算法依赖严格内存顺序，而现代 CPU 的乱序执行和缓存机制可能破坏这种顺序假设。

9. 原子操作 Atomic Operation

原子操作指的是：

不可被打断、不会被其他线程看到中间状态的操作。

它强调 all-or-nothing：

1
2
3

要么完整发生
要么完全没发生
不会出现执行一半的可见状态

原子操作常用于构造锁和无锁数据结构。

9.1 CAS

CAS，即 Compare-And-Swap，可以理解为一个原子的“读—比较—条件写”操作。

伪代码如下：

1
2
3
4
5
6

int CAS(int *addr, int expected, int new_value) {
    int old = *addr;
    if (*addr == expected)
        *addr = new_value;
    return old;
}

语义是：

1. 读取 addr 中的旧值；
2. 判断旧值是否等于 expected；
3. 如果相等，就写入 new_value；
4. 返回旧值。

虽然逻辑上包含多个步骤，但硬件保证它作为一个整体原子执行。

因此，CAS 不是“只能把两个动作合并成原子操作”。更准确地说：

CAS 是一个原子的读—比较—条件写操作。

9.2 FAA

FAA，即 Fetch-And-Add，可以理解为：

1. 读取旧值；
2. 加上某个数；
3. 写回新值；
4. 返回旧值。

Ticket Lock 常用 FAA 来发号。

所以，原子操作并不限于“两个动作”。硬件可以提供不同形式的原子读改写指令。

但要注意：

CAS 不是万能事务机制。

如果你想让任意多行 C 代码整体互斥执行，通常不是靠一个 CAS 包住所有代码，而是使用锁：

1
2
3
4
5

lock(&mutex);

// 多行临界区代码

unlock(&mutex);

10. 互斥锁 Mutex

互斥锁提供两个基本操作：

1
2

lock(&mutex);
unlock(&mutex);

典型使用方式是：

1
2
3
4
5
6

lock(&buffer_lock);

buffer[buffer_write_cnt] = msg;
buffer_write_cnt = (buffer_write_cnt + 1) % 5;

unlock(&buffer_lock);

10.1 为什么同一把锁能保护共享资源

核心原因是：

锁本身是一个共享状态，并且加锁操作会原子地改变这个状态。

假设锁变量有两个状态：

加锁可以用 CAS 实现：

1
2

while (CAS(lock, 0, 1) != 0)
    ;

含义是：

• 如果 lock == 0，当前线程把它改成 1，成功进入临界区；
• 如果 lock == 1，说明已有线程在临界区，当前线程等待。

因为 CAS 是原子的，所以不可能两个线程同时成功把 lock 从 0 改成 1。

因此，只要满足三个前提：

1. 所有访问同一组共享资源的代码都使用同一把锁；
2. 没有任何代码绕过锁直接访问共享资源；
3. 锁本身实现正确；

那么这些访问就会被串行化。

也就是说，同一时刻最多只有一个线程能进入由这把锁保护的临界区。

10.2 锁保护的是一组共享状态

一把锁保护的不是某一行代码，而是一组共享状态。

例如，生产者消费者缓冲区中要一起保护：

• buffer
• buffer_write_cnt
• buffer_read_cnt
• 其他相关计数变量

如果写操作用了 buffer_lock，但读操作没用，仍然会出错。
如果写操作用 lockA，读操作用 lockB，也不能保证互斥。

❗ 本节核心结论： 互斥锁通过原子地改变锁状态，让所有使用同一把锁访问同一组共享资源的代码串行执行。

11. 自旋锁 Spin Lock

自旋锁是一种互斥锁实现方式。

它的特点是：

拿不到锁时，不睡眠，而是一直循环检查锁是否释放。

典型代码：

1
2
3
4
5
6
7
8

void lock(int *lock) {
    while (atomic_CAS(lock, 0, 1) != 0)
        ;
}

void unlock(int *lock) {
    *lock = 0;
}

自旋锁的执行过程是：

1
2
3
4
5
6
7
8
9
10

线程 A：CAS(lock, 0, 1) 成功
线程 A：进入临界区

线程 B：CAS(lock, 0, 1) 失败
线程 B：持续循环等待

线程 A：释放锁，lock = 0

线程 B：CAS(lock, 0, 1) 成功
线程 B：进入临界区

自旋锁的优点是：

• 实现简单；
• 响应快；
• 临界区很短时效率高；
• 避免线程睡眠和唤醒的上下文切换开销。

但它的缺点也很明显：

• 等待期间持续占用 CPU；
• 锁持有时间长时浪费严重；
• 普通自旋锁不保证公平；
• 可能导致某些线程长期抢不到锁。

所以，自旋锁适合：

临界区非常短、锁竞争不严重、线程睡眠唤醒成本高的场景。

12. Ticket Lock：给自旋锁加上排队秩序

普通自旋锁的问题是：谁能抢到锁比较随机，不保证先来先服务。

Ticket Lock，即排号自旋锁，用“拿号—叫号”的方式实现公平性。

它通常包含两个变量：

1
2
3
4

struct lock {
    volatile int owner;
    volatile int next;
};

含义是：

加锁过程：

1
2
3
4

int my_ticket = FAA(&lock->next, 1);

while (lock->owner != my_ticket)
    ;

解锁过程：

1

lock->owner++;

执行过程如下：

1
2
3
4
5
6
7
8

线程 A 拿到 3 号，owner = 3，进入临界区
线程 B 拿到 4 号，等待 owner == 4
线程 C 拿到 5 号，等待 owner == 5

线程 A 退出，owner++
owner = 4

线程 B 进入临界区

Ticket Lock 的本质是：

把进入临界区的问题变成 FIFO / FCFS 排队问题。

它解决了普通自旋锁不公平的问题。只要前面的线程会在有限时间内释放锁，后面的线程就能在有限等待后进入。

但 Ticket Lock 仍然是自旋锁。没轮到自己的线程仍然会循环检查 owner，所以它没有解决忙等浪费 CPU 的问题。

❗ 本节核心结论： Ticket Lock 用排号机制保证公平性和有限等待，但仍然保留自旋等待的 CPU 消耗。

13. 临界区入口也可以看成调度问题

当多个线程都想进入临界区时，锁需要决定：

下一个获得锁的是谁？

这其实和调度问题有相似之处。

例如：

因此，可以把“进入临界区”理解成一种资源调度问题。

但它和 CPU 调度也有区别：

• CPU 调度分配的是 CPU 时间片；
• 锁调度分配的是临界区进入权；
• 临界区通常应该尽快执行完并释放锁；
• 不适合像 RR 那样“临界区执行一半，换另一个线程进来”。

因为临界区执行一半时，共享状态可能正处于中间状态。如果强行换另一个线程进入，会破坏一致性。

所以，锁竞争更常见的是 FIFO、公平锁、非公平锁、优先级锁，而不是严格意义上的 RR。

14. volatile：防编译器优化，不保证线程安全

volatile 是本讲最容易混淆的概念之一。

在 C/C++ 语境中，volatile 的核心作用是：

告诉编译器：这个变量可能被当前控制流之外的东西改变，所以每次访问都要真正读写内存，不要随意优化掉。

例如：

1

volatile int flag;

编译器看到 volatile 后，不应把：

1
2

while (flag == 0) {
}

优化成：

1
2
3
4

if (flag == 0) {
    while (true) {
    }
}

因为 flag 可能被硬件、中断处理程序或其他执行上下文修改。

14.1 volatile 能解决什么

它主要防止编译器做某些优化，例如：

• 把变量长期缓存到寄存器；
• 认为变量不会变化；
• 把多次读取优化成一次读取；
• 删除看似无用的读写。

常见用途包括：

• 内存映射 I/O；
• 硬件寄存器访问；
• 某些中断相关变量。

14.2 volatile 不能解决什么

volatile 不能保证：

• 原子性；
• 互斥；
• 线程安全；
• x++ 安全；
• 足够的跨 CPU 内存同步；
• 正确的并发访问顺序。

例如：

1
2

volatile int balance = 0;
balance++;

即使 balance 是 volatile，balance++ 仍然可能被拆成：

1
2
3

读 balance
加 1
写回 balance

两个线程同时执行时，仍然可能丢失更新。

所以：

volatile 不是锁，也不是原子操作。

可以用一句话区分：

❗ 本节核心结论： volatile 主要约束编译器优化，不负责互斥、原子性和完整线程安全。

15. 重要对比表

15.1 竞争条件、临界区、互斥锁

15.2 Peterson 算法、原子操作、互斥锁

15.3 普通自旋锁 vs Ticket Lock

16. 易混点整理

17. 复习清单

学完本讲后，应能回答：

• 为什么 balance++ 在多线程环境下可能出错？
• 什么是竞争条件？
• 竞争条件需要满足哪些关键条件？
• 什么是临界区？
• 临界区和共享变量是什么关系？
• 为什么不能说“所有互斥区域都是临界区”？
• 解决临界区问题的三个要求是什么？
• 为什么关闭中断在多核系统中不够？
• Peterson 算法中的 flag[] 表示什么？
• Peterson 算法中的 turn 为什么体现“谦让”？
• 为什么现代 CPU 的乱序执行可能破坏 Peterson 算法？
• 什么是原子操作？
• CAS 的核心语义是什么？
• CAS 和普通多条语句有什么区别？
• 为什么同一组共享资源要用同一把锁保护？
• 普通自旋锁为什么可能导致饥饿？
• Ticket Lock 中 owner 和 next 分别表示什么？
• Ticket Lock 如何体现 FIFO / FCFS？
• volatile 能解决什么问题？
• 为什么 volatile 不能保证 x++ 线程安全？

最终总结

同步原语 I 的核心可以压缩为一句话：

多个线程同时访问共享资源时，程序的正确性不能依赖偶然的执行顺序，而必须通过临界区和同步原语强制建立安全访问规则。

balance++ 出错说明简单语句也可能包含非原子的读—改—写；生产者消费者模型说明共享缓冲区和共享下标都需要保护；竞争条件描述了并发错误的根源；临界区标记了必须互斥访问的代码范围；Peterson 算法展示了软件互斥思想；CAS、FAA 等原子操作为现代锁实现提供硬件基础；互斥锁把底层原子操作封装成易用抽象；自旋锁适合短临界区但可能浪费 CPU；Ticket Lock 用排号机制改善公平性；volatile 则只约束编译器优化，不能替代锁或原子操作。

真正理解本讲，不是记住某个锁的代码，而是能判断：

• 哪些共享状态需要保护；
• 哪些代码属于临界区；
• 哪些访问路径必须使用同一把锁；
• 哪种锁适合当前场景；
• 哪些机制只解决可见性，不解决原子性；
• 哪些方案保证互斥，但不保证公平或有限等待。