操作系统第 10 章复习：锁、条件变量与信号量设计

前言

这一章的主题是 Lock and Condition Variable Design，也就是“锁、条件变量与信号量的设计”。前面几章我们已经学过进程、线程、上下文切换、地址空间、TLB、缓存、缺页异常和调度。第 10 章开始进入操作系统中另一个非常核心的主题：并发同步。

这章要解决的问题可以用一句话概括：

多个线程共享数据时，调度器可能在任意时刻切换线程。程序怎样才能在任意调度顺序下都正确？

如果只看单线程程序，代码通常是从上到下执行的。但是在多线程程序中，两个线程的指令可能交错执行；在多核机器上，它们甚至可能真正同时执行。于是一个看起来很简单的操作，比如 x = x + 1，也可能因为被拆成 load / add / store 多条机器指令而出错。

这一章的主线是：

并发执行带来不确定性
        ↓
共享变量被交错访问会产生 race condition
        ↓
需要同步 synchronization
        ↓
先理解 atomic operation 原子操作
        ↓
只靠 load/store 实现同步非常痛苦
        ↓
引入 lock 保护 critical section
        ↓
引入 condition variable 表达“等待某个条件成立”
        ↓
引入 semaphore 同时表达资源计数、互斥和调度约束
        ↓
用 producer-consumer 生产者消费者问题综合练习

---

1. 调度复习：为什么同步问题会出现？

1.1 Round-Robin、SJF/SRTF

第 2 页先复习上一章的调度算法。

Round-Robin，轮转调度，就是让每个 ready thread 轮流获得一小段 CPU 时间。这个算法对短任务比较友好，因为短任务不用一直等长任务完全跑完。

SJF / SRTF 分别是：

• SJF：Shortest Job First，短任务优先；
• SRTF：Shortest Remaining Time First，最短剩余时间优先。

它们的思想是：谁剩下的计算量最少，就先运行谁。理论上它们能优化平均响应时间，但是缺点也明显：第一，操作系统很难提前知道一个任务还要运行多久；第二，如果短任务不断到来，长任务可能一直得不到运行，出现饥饿。

这页和同步的联系是：线程什么时候运行、什么时候被切走，不由程序员完全控制，而由调度器决定。

1.2 Lottery、MLFQ、实时调度

第 3 页复习了另外几类调度算法。

Lottery Scheduling，彩票调度，会给不同优先级的线程分配不同数量的彩票。调度时随机抽票，票越多，被选中的概率越大。

Multi-Level Feedback Queue，MLFQ，多级反馈队列，通过多个不同优先级的队列管理进程/线程。系统会根据线程行为自动升降优先级，以近似 SJF/SRTF 的效果。

Real-time Scheduling，实时调度，关注的是 deadline。实时系统的关键不只是平均性能，而是必须在截止时间前完成任务。课件提到了两个经典算法：

• EDF：Earliest Deadline First，最早截止时间优先；
• RM：Rate Monotonic，速率单调调度。

这些调度策略共同说明一件事：线程执行顺序并不固定。同步机制必须面对“任意调度顺序”。

1.3 Numbering from zero

第 4 页放了 Dijkstra 的文章 Why numbering should start at zero。这页不是本章同步机制的核心，主要是程序员文化和区间表达习惯。

从 0 开始编号的一个好处是区间更自然，例如：

for (int i = 0; i < n; i++) {
    // i 的取值正好是 0 到 n-1，一共 n 个元素
}

0 <= i < n 这个写法既能表达长度，又能避免边界混乱。

---

2. OS Conceptual Framework：从资源共享到同步

第 5 页把前面很多章串了起来。

课件的逻辑是：

物理地址是共享的
        → 所以需要进程和地址转换

CPU 必须被多个任务共享
        → 所以需要线程和调度

进程不可信
        → 所以需要 kernel/user split，即内核态和用户态隔离

线程可能不合作
        → 所以需要 timer interrupt 进行抢占式上下文切换

线程共享数据但调度不确定
        → 所以需要同步机制

这页非常重要，因为它告诉我们：操作系统的很多机制不是孤立的。

• 地址转换解决的是不同进程之间的内存隔离问题；
• 线程和调度解决的是 CPU 共享问题；
• 用户态/内核态解决的是信任边界问题；
• 同步机制解决的是多个线程共享数据时的正确性问题。

第 6 页给出本章目标：

1. 为什么 synchronization 很难；
2. Locks；
3. Condition Variables；
4. Semaphores。

---

3. 线程抽象与真实硬件之间的差距

3.1 程序员抽象：好像有无限多个 CPU

第 7 页回顾线程抽象。

程序员写多线程程序时，通常会把每个线程想象成一条独立的执行流，好像每个线程都有自己的 CPU，可以持续执行。

但是物理现实是：

• CPU 核心数量有限；
• 线程运行速度可能不同；
• 调度器可以在任意时刻暂停一个线程，再运行另一个线程；
• 在多核机器上，多个线程还可能真正并行运行。

所以并发程序必须满足一个非常强的要求：

不管调度器如何交错线程执行，程序都应该正确。

这比单线程程序难很多，因为你不能只考虑“代码顺序”，还要考虑“指令交错”。

3.2 Multiprocessing、Multiprogramming、Multithreading

第 8 页区分了三个概念。

Multiprocessing，多处理器/多核，指硬件上有多个 CPU、多个核心或超线程，可以真正同时执行多个指令流。

Multiprogramming，多道程序，指系统中同时存在多个作业或进程，操作系统通过调度让它们交替执行。

Multithreading，多线程，指一个进程内部有多个线程。

两个线程 “concurrently run” 不一定意味着它们物理上同时运行。更准确地说：

调度器可以用任意顺序、任意交错方式运行它们。

在单核上，并发是时间片切换造成的；在多核上，并发还可能变成真正的并行。

---

4. 为什么允许 cooperating threads？

第 9 页讲合作线程的好处。

4.1 共享资源

一个系统通常有很多资源需要共享。例如：

• 一台计算机服务多个用户；
• 一个银行账户可能被多个 ATM 访问；
• 机器人控制系统中，机械臂和机械手需要协调。

共享资源带来方便，也带来风险。多个线程如果同时修改同一份数据，就可能互相干扰。

4.2 提升性能

线程可以提升性能，尤其是在 I/O 和计算可以重叠的时候。

例如，一个线程等待磁盘读取时，另一个线程可以继续计算。文件系统常见的 read-ahead 就体现了这种思想：提前读取后续可能需要的数据，让 I/O 和计算重叠。

在多核机器上，还可以把一个大任务拆成多个小任务并行执行。

4.3 模块化

线程和进程还可以帮助我们把复杂系统拆成多个模块。课件举了编译流程：

cpp | cc1 | cc2 | as | ld

这是一条流水线。每个阶段做一件事，整体组合起来完成编译。模块化能让系统更容易扩展和维护。

所以，共享和合作是必要的，但它会引出同步问题。

---

5. 并发程序的正确性为什么难？

5.1 Independent Threads vs Cooperating Threads

第 10 页区分了独立线程和合作线程。

Independent Threads，独立线程，没有共享状态。它们通常是确定性的：输入确定，输出也确定。只要上下文切换本身正确，调度顺序一般不影响最终结果。

Cooperating Threads，合作线程，共享状态。它们可能是非确定性的、不可复现的。也就是说，同样的输入、同样的程序，每次运行结果可能不同。

这种 bug 有时被称为 Heisenbugs。它们很难调试，因为错误可能只在某些极端调度顺序下出现。你一加日志、一调试，执行时序改变了，bug 反而消失了。

5.2 看似独立的程序也可能交互

第 11 页强调，真正完全独立的程序很少。

不同进程即使没有共享普通变量，也可能共享：

• 文件系统；
• OS 内核资源；
• 网络；
• 设备驱动；
• 内存布局和缓存状态。

课件举了极端例子：一个有 bug 的设备驱动可能导致另一个“独立”线程崩溃。

所以，并发错误不仅难复现，而且交互范围可能很广。

---

6. 问题发生在最低层：共享变量与指令交错

6.1 两个线程写同一个变量

第 12 页从最简单的例子开始。

如果两个线程操作不同变量：

Thread A: x = 1;
Thread B: y = 2;

通常没有问题，因为没有共享状态冲突。

但是如果两个线程操作同一个变量：

// 初始 x = 12
Thread A: x = 1;
Thread B: x = 2;

最终 x 可能是 1，也可能是 2。这取决于最后谁写入。

课件还提到，如果某些写入本身不是原子的，甚至可能出现更奇怪的结果。例如一个线程写 0001，另一个线程写 0010，如果写入过程可以按位交错，极端情况下可能得到 0011，也就是 3。不过现代机器上 word 大小的普通 load/store 通常是原子的，所以这个极端例子主要用来说明“底层操作是否原子”非常重要。

6.2 x = x + 1 不是原子操作

第 13 页和第 14 页给了经典例子。

初始：

x = 0;

两个线程：

Thread A: x = x + 1;
Thread B: x = x + 2;

从源代码看，好像最终结果应该是 3。但机器层面上，这两句代码可能被拆成：

// Thread A
load r1, x
add  r2, r1, 1
store x, r2

// Thread B
load r1, x
add  r2, r1, 2
store x, r2

如果 A 完整执行完，再 B 执行，最终是：

x = 3

如果 A 和 B 都先读到 x = 0，然后 A 写 1，B 写 2，最终是：

x = 2

如果 A 和 B 都先读到 x = 0，然后 B 写 2，A 写 1，最终是：

x = 1

所以最终可能是 1、2、3。

这就是 race condition，竞态条件：结果取决于线程之间不可控的执行交错。

6.3 编译器重排序会让问题更复杂

第 15 页进一步说明，线程交错不是唯一问题，编译器优化也可能改变指令顺序。

例如：

// Thread A
p = funcA();
pInitialized = true;

// Thread B
while (!pInitialized) {
    // wait
}
q = funcB(p);

程序员以为 Thread A 一定是先初始化 p，再把 pInitialized 设为 true。但是编译器可能为了优化指令级并行，把没有单线程依赖冲突的指令重排。

也就是说，在没有同步机制约束时，编译器只保证单线程语义正确，不保证跨线程观察到的顺序符合你的直觉。

这也是为什么真实系统中还需要 atomic、memory barrier、volatile 等机制。不过本章主要从锁、条件变量和信号量入手。

---

7. Atomic Operation：同步的基础

第 16 页定义 Atomic Operation，原子操作。

原子操作是指：

一个操作要么完整执行完，要么完全不执行；中间不能被打断，状态也不能被其他线程在中间修改。

它的关键词是 indivisible，不可分割。

为什么原子操作重要？因为如果没有任何原子操作，线程之间就没有可靠的协作基础。

课件指出，大多数机器上：

• word 大小的内存读是原子的；
• word 大小的内存写是原子的。

但是很多操作不是原子的，例如：

• x++；
• x = x + 1；
• 双精度浮点写入；
• 复杂的数组复制指令。

考试中很容易问：

x++ 是原子操作吗？

一般答案是：不是。因为它至少包括读取、加一、写回三步。

---

8. Too Much Milk：用生活例子理解同步

8.1 问题背景

第 17 页用 “Too Much Milk” 例子解释同步。

两个人回家后发现冰箱没有牛奶，都去商店买，结果买了两份。这个生活问题对应到计算机就是：多个线程基于共享状态做决策，但没有协调。

时间线可以理解为：

A 看冰箱：没牛奶
B 看冰箱：没牛奶
A 去买
B 去买
A 回来放牛奶
B 回来放牛奶

问题不是“买牛奶”本身，而是“检查状态”和“执行动作”之间缺少同步。

8.2 同步、互斥、临界区

第 18 页给出三个核心概念。

Synchronization，同步：使用原子操作来保证线程之间正确合作。

Mutual Exclusion，互斥：保证同一时刻只有一个线程执行某件事。

Critical Section，临界区：只能被一个线程同时执行的一段代码。

三者关系可以这样理解：

同步是目标
互斥是一种常见同步方式
临界区是被互斥保护的代码区域

例如：

lock.acquire();
x = x + 1;   // critical section
lock.release();

这里 x = x + 1 就是临界区。

8.3 Lock 的直观含义

第 19 页引入 Lock。

Lock 的使用方式是：

lock.Acquire();
// critical section
lock.Release();

含义是：进入临界区之前先拿锁；离开临界区后释放锁；如果锁已经被别人拿着，就等待。

课件用冰箱钥匙类比：谁要去买牛奶，先拿冰箱钥匙。有钥匙的人负责检查和买，其他人不能同时做这件事。

不过这页也提醒：现在我们还不知道如何实现 lock。第 10 章重点是如何使用这些同步原语，第 11 章才会进一步讲实现。

---

9. Too Much Milk 的正确性条件

第 20 页非常重要。它强调，写并发程序时不要先急着写代码，而要先写清楚正确性要求。

Too Much Milk 问题的正确性条件是：

1. Never more than one person buys：最多一个人买，不能买多；
2. Someone buys if needed：如果确实需要牛奶，必须有人去买。

第一个是 safety property：坏事不要发生。第二个是 liveness property：好事最终要发生。

这一页还限制我们暂时只能使用 atomic load 和 store。也就是说，还没有真正的 lock，只能靠普通读写模拟同步。

---

10. Too Much Milk 的几种尝试

10.1 Solution #1：用一个 note 模拟锁

第 21 页提出第一个方案：用 note 避免买多。

伪代码是：

if (noMilk) {
    if (noNote) {
        leave Note;
        buy milk;
        remove note;
    }
}

直觉上：

• leave Note 像上锁；
• remove Note 像解锁；
• 如果看到 note，就不买。

第 22 页把这个方案放到两个线程上。两个线程都可能先看到：

noMilk == true
noNote == true

然后都进入买牛奶逻辑。

第 23 页给结论：这个方案仍然会买多，只是偶尔发生。线程可能在检查完 noMilk 和 noNote 后、真正留下 note 前被切走。另一个线程也检查到没有 note，于是两个线程都会买。

这种错误很可怕，因为它不是每次发生，而是偶尔发生，非常难调试。

10.2 Solution #1.5：先留 note

第 24 页尝试修复：既然检查后再留 note 不够阻塞，那就先留 note。

伪代码类似：

leave Note;
if (noMilk) {
    if (noNote) {
        buy milk;
    }
}
remove Note;

但这个方案在计算机里会导致没人买。因为线程自己刚刚留下 note，再检查 noNote 时当然发现有 note，于是不会买。

这说明并发同步设计很微妙：一个看似合理的小改动，可能解决了一个问题，又引入另一个问题。

10.3 Solution #2：labeled notes

第 25 页和第 26 页提出第二个方案：给 note 加标签。A 留 note A，B 留 note B。

伪代码大概是：

// Thread A
leave note A;
if (noNote B) {
    if (noMilk) {
        buy milk;
    }
}
remove note A;

// Thread B
leave note B;
if (noNote A) {
    if (noMilk) {
        buy milk;
    }
}
remove note B;

这个方案避免了两个线程使用同一个 note 的混乱，但仍然不正确。

如果调度顺序刚好是：

A leave note A
B leave note B
A 看到 note B，认为 B 会买
B 看到 note A，认为 A 会买

结果是：没人买。

这违反了“Someone buys if needed”。课件强调，这种情况可能极其罕见，但真实系统里罕见 bug 往往会在最糟糕的时候出现。

10.4 Solution #3：two-note solution

第 27 页和第 28 页给出了一个可行的两张 note 方案。

伪代码可以理解为：

// Thread A
leave note A;
while (note B) {      // X
    do nothing;
}
if (noMilk) {
    buy milk;
}
remove note A;

// Thread B
leave note B;
if (noNote A) {       // Y
    if (noMilk) {
        buy milk;
    }
}
remove note B;

这里 A 和 B 的代码不完全对称。它的逻辑是：

• 在 X 处，如果 A 没看到 note B，A 可以安全地买；如果看到 note B，就等 B 做完决定；
• 在 Y 处，如果 B 没看到 note A，B 可以安全地买；如果看到 note A，说明 A 要么会买，要么正在等 B 退出。

这个方案可以保证：要么当前线程安全地买，要么另一个线程会买，当前线程可以退出。

10.5 Solution #3 的两个证明 case

第 29 页到第 34 页证明 Solution #3 的正确性。

Case 1：leave note A 发生在 B 的 if (noNote A) 之前。

这时 B 检查时能看到 note A，于是 B 不买。A 如果看到 note B，就等待 B 移除 note B。B 移除后，A 继续检查是否没有牛奶，如果没有就买。所以不会买多，也不会没人买。

Case 2：B 的 if (noNote A) 发生在 A 的 leave note A 之前。

这时 B 检查不到 note A，所以 B 可以进入买牛奶逻辑。之后 A 留 note A，并看到 note B，于是 A 等待 B 结束。B 如果买了，A 后面再检查 noMilk 时就不会再买。

这几页想表达的是：并发算法必须覆盖所有可能交错，不能只凭直觉。

10.6 Solution #3 为什么不满意？

第 35 页总结了 Solution #3 的问题。

虽然它正确，但很不满意：

1. 太复杂。买牛奶这么简单的问题，都需要仔细分 case 证明；
2. A 和 B 的代码不一样。如果有很多线程，代码会越来越难写；
3. A 等待时一直执行 while (note B) { do nothing; }，浪费 CPU。这叫 busy-waiting，忙等。

所以我们需要更好的同步原语。

10.7 Solution #4：真正的 Lock

第 36 页给出最终版本：

milklock.Acquire();
if (nomilk) {
    buy milk;
}
milklock.Release();

这就是 lock 的价值：它把复杂的底层同步细节封装起来。程序员只需要表达：这段代码同一时刻只能有一个线程执行。

Acquire 和 Release 之间的代码就是 critical section，临界区。

---

11. 从硬件原子操作到高级同步原语

第 37 页展示同步机制的分层。

底层硬件提供一些基本原子能力：

• Load/Store；
• Disable Interrupts；
• Test&Set；
• Compare&Swap。

在这些基础上，系统或运行库实现更高级的同步原语：

• Locks；
• Semaphores；
• Monitors；
• Send/Receive。

程序员再用这些高级 API 写并发程序。

这页的思想是：

硬件提供少量原子能力
        ↓
OS / runtime 封装成同步原语
        ↓
程序员用高级同步原语写并发程序

第 10 章主要讲如何设计和使用这些高级原语，第 11 章会进一步讲这些原语如何实现。

---

12. Lock 的正式性质

第 38 页给出 Lock 的三个正式性质。

12.1 Mutual Exclusion，互斥

同一时刻最多一个线程持有锁。

这保证临界区不会被多个线程同时执行。

12.2 Progress，进展性

如果没有线程持有锁，并且有线程试图获取锁，那么最终应该有某个线程成功获取锁。

这避免大家都卡住。

12.3 Bounded Waiting，有界等待

如果线程 T 尝试获取锁，那么在 T 成功之前，其他线程成功获取锁的次数应该有上界。

也就是说，T 不能永远等下去。

注意：有界等待不等于 FIFO。它不保证先来的线程一定先拿到锁，只保证不会无限等待。

---

13. Lock 到底能保证什么？

第 39 页和第 40 页用一个小例子说明 Lock 的保证范围。

代码如下：

int x = 0;

// T1: can we ensure x = 0 here?
lock.acquire();

// T2: can we ensure x = 0 here?
x = 1;

// T3: can we ensure x = 1 here?
lock.release();

// T4: can we ensure x = 1 here?
x = 2;

// T5: can we ensure x = 2 here?

前提是：x 是线程共享变量，其他线程也只在持有同一把 lock 的情况下访问 x。

关键结论是：

If a lock is not held, nothing can be guaranteed.

也就是说，锁只保护它包住的临界区。

在 lock.acquire() 和 lock.release() 之间，如果所有线程都遵守同一把锁的规则，那么其他线程不能同时修改 x。但是释放锁之后，如果再访问 x，就不再受保护。

所以正确使用锁的原则是：

所有访问同一个共享变量的地方，都必须使用同一把锁。

如果有的地方加锁，有的地方不加锁，锁就无法保证正确性。

---

14. Condition Variable：条件变量

14.1 条件变量是什么？

第 41 页引入 Condition Variable，条件变量。

条件变量可以理解为：

一个线程队列，里面放的是正在等待某个条件成立的线程。

它的关键思想是：

允许线程在临界区中睡眠，并在睡眠时原子地释放锁。

条件变量有三个主要操作：

Wait(&lock)
Signal()
Broadcast()

含义分别是：

• Wait(&lock)：原子地释放 lock，并让当前线程睡眠；线程以后被唤醒时，会在返回前重新获取 lock；
• Signal()：唤醒一个等待线程，如果有的话；
• Broadcast()：唤醒所有等待线程。

这里要注意，cv.wait(&lock) 不是“等待 lock”，而是：

释放 lock → 睡眠等待条件变量 → 被唤醒后重新拿回 lock

14.2 条件变量的标准模式

第 42 页给出标准写法：

FuncA_wait() {
    lock.acquire();

    // read/write shared state here
    while (!testOnSharedState()) {
        cv.wait(&lock);
    }

    assert(testOnSharedState());
    lock.release();
}

另一个线程改变共享状态后负责唤醒：

FuncB_signal() {
    lock.acquire();

    // read/write shared state here
    // If state has changed that allows another thread to make progress,
    // call signal or broadcast.
    cv.signal();

    lock.release();
}

这里有两个关键点。

第一，条件变量必须和 lock 一起使用。因为条件本身通常来自共享状态，而共享状态必须受锁保护。

第二，等待条件时必须用 while，不要用 if。因为被唤醒只表示“有人通知你了”，不保证条件现在仍然成立。另一个线程可能已经抢先改变了状态。

---

15. 用条件变量实现 bounded queue

第 43 页给出一个具体例子：有界队列，也就是 producer-consumer 问题。

类结构：

class bounded_queue {
    Lock lock;
    CV itemAdded;
    CV itemRemoved;
    void insert(int item);
    int remove();
}

插入操作：

void bounded_queue::insert(int item) {
    lock.acquire();

    while (queue.full()) {
        itemRemoved.wait(&lock);
    }

    add_item(item);
    itemAdded.signal();

    lock.release();
}

含义是：

• 如果队列满了，生产者不能插入，于是等待 itemRemoved；
• 消费者取走 item 后，会 signal itemRemoved，告诉生产者现在可能有空位了；
• 插入成功后，生产者 signal itemAdded，告诉消费者现在可能有 item 了。

对应的 remove 可以写成：

int bounded_queue::remove() {
    lock.acquire();

    while (queue.empty()) {
        itemAdded.wait(&lock);
    }

    int item = remove_item();
    itemRemoved.signal();

    lock.release();
    return item;
}

第 44 页总结条件变量的两个原则：

1. CV is always used with lock acquired.
2. CV is put in a while loop.

条件变量必须在持锁时使用；等待条件必须放在 while 循环里。

---

16. Semaphores：信号量

16.1 信号量的定义

第 45 页引入 Semaphore，信号量。

信号量是一种 generalized lock，广义的锁。它最早由 Dijkstra 在 20 世纪 60 年代提出，也是早期 UNIX 里的主要同步原语。

信号量内部维护一个非负整数，并提供两个原子操作：

P()
V()

P() 的含义是：等待信号量变为正数，然后把它减 1。可以理解为 wait、down、acquire。

V() 的含义是：把信号量加 1，并唤醒一个等待的 P，如果有的话。可以理解为 signal、up、release。

P 和 V 来自荷兰语：

• P：proberen，测试；
• V：verhogen，增加。

16.2 Semaphore 和普通整数的区别

第 46 页说明，信号量像整数，但不是普通整数。

区别是：

1. 信号量不会变成负数；
2. 初始化之后，不能随意读写它的值，只能通过 P 和 V 操作；
3. P 和 V 必须是原子的。

这很重要。假设 S = 1，两个线程同时执行 P(S)，不能出现两个线程都通过的情况。P() 必须原子地完成“检查是否大于 0”和“减 1”。

同理，一个线程在 P 里准备睡眠时，不能错过另一个线程的 V 唤醒。这也是信号量能避免 lost wakeup 的原因。

16.3 信号量的两个用途

第 47 页给出信号量的两个经典用途。

用途 1：互斥。

初值设为 1：

semaphore.P();
// critical section
semaphore.V();

这叫 binary semaphore，二元信号量，相当于一把锁。

用途 2：调度约束。

初值设为 0，用来表示“等待某个事件发生”。例如实现 ThreadJoin：

// 初始 semaphore = 0
ThreadJoin {
    semaphore.P();
}

ThreadFinish {
    semaphore.V();
}

Join 线程先执行 P，因为初值是 0，会睡眠。目标线程结束时执行 V，Join 线程才可以继续。

所以可以记住：

semaphore 初值 = 1：常用于互斥
semaphore 初值 = 0：常用于等待事件发生

---

17. Producer-Consumer with a Bounded Buffer

17.1 问题定义

第 48 页引入生产者消费者问题。

问题是：

• Producer 把 item 放入共享 buffer；
• Consumer 从共享 buffer 中取 item；
• buffer 是固定大小的。

约束是：

• buffer 满时，producer 必须等待；
• buffer 空时，consumer 必须等待；
• producer 和 consumer 不需要严格一步一同步，可以通过固定大小 buffer 解耦。

课件举了两个例子：

GCC 编译流水线：cpp | cc1 | cc2 | as | ld
自动售货机：补货者放 Coke，消费者取 Coke

17.2 正确性约束

第 49 页列出三个约束。

第一，consumer constraint：如果没有 full slot，消费者必须等。

第二，producer constraint：如果没有 empty slot，生产者必须等。

第三，mutual exclusion：同一时刻只能一个线程操作 buffer queue。

课件给出一个很有用的经验法则：

Use a separate semaphore for each constraint.

所以我们需要三个信号量：

Semaphore fullSlots;   // consumer 的约束：有没有可取的 item
Semaphore emptySlots;  // producer 的约束：有没有可用空位
Semaphore mutex;       // 互斥：保护 buffer 队列本身

17.3 完整信号量解法

第 50 页先让我们填写初值，第 51 页给出完整答案：

Semaphore fullSlots = 0;       // Initially, no coke
Semaphore emptySlots = bufSize; // Initially, num empty slots
Semaphore mutex = 1;           // No one using machine

原因是：

• 一开始 buffer 里没有 item，所以 fullSlots = 0；
• 一开始所有位置都是空的，所以 emptySlots = bufSize；
• 一开始没有线程正在操作 buffer，所以 mutex = 1。

Producer：

Producer(item) {
    emptySlots.P();   // 等待有空位，并预定一个空位
    mutex.P();        // 等待独占 buffer
    Enqueue(item);
    mutex.V();        // 释放 buffer
    fullSlots.V();    // 告诉消费者多了一个 item
}

Consumer：

Consumer() {
    fullSlots.P();    // 等待有 item，并预定一个 item
    mutex.P();        // 等待独占 buffer
    item = Dequeue();
    mutex.V();        // 释放 buffer
    emptySlots.V();   // 告诉生产者多了一个空位
    return item;
}

这里要理解三个信号量的职责不同：

emptySlots：管理空位数量
fullSlots：管理已占用槽位数量
mutex：保护 buffer 的内部数据结构

17.4 为什么 Producer 和 Consumer 不对称？

第 52 页解释不对称性。

Producer 做：

emptySlots.P();
fullSlots.V();

含义是：生产者消耗一个空槽，增加一个满槽。

Consumer 做：

fullSlots.P();
emptySlots.V();

含义是：消费者消耗一个满槽，增加一个空槽。

所以它们刚好相反。这不是随便写的，而是资源数量变化决定的。

17.5 P 的顺序为什么重要？

第 53 页和第 54 页讨论 P 和 V 的顺序。

课件问：P 的顺序重要吗？答案是：重要，错误顺序可能导致死锁。

错误写法：

Producer(item) {
    mutex.P();
    emptySlots.P();
    Enqueue(item);
    mutex.V();
    fullSlots.V();
}

假设 buffer 已满：

emptySlots = 0

Producer 先拿到了 mutex，然后执行 emptySlots.P()。因为没有空位，它睡眠等待。但它睡眠时还持有 mutex。

Consumer 想消费一个 item，必须先执行：

mutex.P();

但 mutex 被 Producer 拿着，所以 Consumer 进不去，也就不能执行 emptySlots.V() 释放空位。

结果是：

Producer 等 emptySlots
Consumer 等 mutex
emptySlots 只有 Consumer 消费后才能增加
Consumer 又拿不到 mutex
=> 死锁

所以正确顺序是：先等待资源条件，再进入互斥区。

emptySlots.P();
mutex.P();

课件还问：V 的顺序重要吗？一般不影响正确性，但可能影响调度效率。

如果有两个 producers 或两个 consumers，需要改代码吗？通常不需要，因为 mutex 已经保护了 buffer 队列，而 emptySlots 和 fullSlots 控制资源数量。

---

18. 一些锁使用建议与 Double-Checked Locking

18.1 锁的使用建议

第 55 页给出建议：

Always acquire the lock at the beginning of a method and release it right before the return.

也就是尽量在方法开头拿锁，在返回前释放锁。

好处是：

• 行为一致；
• 程序更容易写；
• 代码更容易读；
• 更容易调试；
• 不容易忘记释放锁。

这不是绝对规则，但对初学并发来说非常有帮助。

18.2 Double-Checked Locking

第 56 页讲 double-checked locking。

不安全版本：

Singleton* Singleton::instance() {
    if (pInstance == NULL) {
        pInstance = new Instance();
    }
    return pInstance;
}

多个线程可能同时看到 pInstance == NULL，于是创建多个实例。

安全版本：

Singleton* Singleton::instance() {
    lock.acquire();
    if (pInstance == NULL) {
        pInstance = new Instance();
    }
    lock.release();
    return pInstance;
}

所谓“优化”版本：

Singleton* Singleton::instance() {
    if (pInstance == NULL) {
        lock.acquire();
        if (pInstance == NULL) {
            pInstance = new Instance();
        }
        lock.release();
    }
    return pInstance;
}

这个写法的问题是，编译器或 CPU 可能重排序对象创建过程。对象创建可能被拆成：

分配内存
把地址赋给 pInstance
执行构造函数

如果地址赋值先于构造完成被其他线程看见，另一个线程会发现 pInstance != NULL，然后返回一个尚未初始化完成的对象。

所以课件想强调：不要随便为了优化减少锁。并发优化很容易引入非常隐蔽的 bug。

---

19. 真实系统中的并发 Bug

第 57 页引用 ASPLOS’08 论文 Learning from mistakes: a comprehensive study on real world concurrency bug characteristics。研究统计了 MySQL、Apache、Mozilla、OpenOffice 等真实大型系统中的并发 bug。

课件里的统计表说明：真实系统中并发 bug 非常普遍，其中既有 deadlock bug，也有 non-deadlock bug，而且非死锁 bug 的数量更多。

这一部分的重点不是背具体数字，而是理解：

并发 bug 不是理论玩具，而是真实大型系统中非常常见的问题。

19.1 Atomicity-Violation Bugs

第 58 页和第 59 页讲 Atomicity-Violation Bugs，原子性违反 bug。

典型模式是：一段本应该不可分割的操作，被另一个线程插入破坏。

例如没有锁时：

// Thread 1
if (thd->proc_info) {
    fputs(thd->proc_info, ...);
}

// Thread 2
thd->proc_info = NULL;

Thread 1 先检查 thd->proc_info 不是 NULL，但在它调用 fputs 之前，Thread 2 可能把 thd->proc_info 改成 NULL。于是 Thread 1 后面使用时可能出错。

修复方式是用同一把锁保护所有访问：

pthread_mutex_t proc_info_lock = PTHREAD_MUTEX_INITIALIZER;

// Thread 1
pthread_mutex_lock(&proc_info_lock);
if (thd->proc_info) {
    fputs(thd->proc_info, ...);
}
pthread_mutex_unlock(&proc_info_lock);

// Thread 2
pthread_mutex_lock(&proc_info_lock);
thd->proc_info = NULL;
pthread_mutex_unlock(&proc_info_lock);

核心是：

check + use 必须放在同一个临界区里

只锁 fputs 不够，只锁赋值也不够，所有访问同一个共享变量的地方必须使用同一把锁。

19.2 Order-Violation Bugs

第 60 页和第 61 页讲 Order-Violation Bugs，顺序违反 bug。

这类 bug 不是两个线程同时修改一个变量，而是：某个操作本来必须先发生，但程序没有保证这种先后顺序。

例如：

// Thread 1
void init() {
    mThread = PR_CreateThread(mMain, ...);
}

// Thread 2
void mMain(...) {
    mState = mThread->State;
}

问题是 Thread 2 可能在线程创建后马上运行。如果 Thread 1 还没有完成必要初始化，Thread 2 就访问 mThread->State，会出错。

修复方式通常是用条件变量表达“初始化完成后才能继续”：

pthread_mutex_t mtLock = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t mtCond = PTHREAD_COND_INITIALIZER;
int mtInit = 0;

// Thread 1
pthread_mutex_lock(&mtLock);
mtInit = 1;
pthread_cond_signal(&mtCond);
pthread_mutex_unlock(&mtLock);

// Thread 2
pthread_mutex_lock(&mtLock);
while (mtInit == 0) {
    pthread_cond_wait(&mtCond, &mtLock);
}
pthread_mutex_unlock(&mtLock);

mState = mThread->State;

这里再次出现 while。被唤醒不代表条件一定成立，所以必须重新检查。

可以这样总结：

Atomicity violation：本来应该连在一起的操作被插队破坏
常用 lock 修复

Order violation：本来应该先后发生的操作顺序没有被保证
常用 condition variable 或 semaphore 修复

---

20. 本章核心代码汇总

20.1 Lock 保护临界区

lock.acquire();
// critical section
lock.release();

20.2 Condition Variable 标准写法

lock.acquire();
while (!condition) {
    cv.wait(&lock);
}
// condition is true here
lock.release();

20.3 Bounded Queue：条件变量版本

void bounded_queue::insert(int item) {
    lock.acquire();
    while (queue.full()) {
        itemRemoved.wait(&lock);
    }
    add_item(item);
    itemAdded.signal();
    lock.release();
}

int bounded_queue::remove() {
    lock.acquire();
    while (queue.empty()) {
        itemAdded.wait(&lock);
    }
    int item = remove_item();
    itemRemoved.signal();
    lock.release();
    return item;
}

20.4 Semaphore 版本生产者消费者

Semaphore fullSlots = 0;
Semaphore emptySlots = bufSize;
Semaphore mutex = 1;

Producer(item) {
    emptySlots.P();
    mutex.P();
    Enqueue(item);
    mutex.V();
    fullSlots.V();
}

Consumer() {
    fullSlots.P();
    mutex.P();
    item = Dequeue();
    mutex.V();
    emptySlots.V();
    return item;
}

---

21. 本章最重要的考试点

21.1 并发程序必须在任意调度下正确

不能只考虑你测试出来的顺序。调度器可以在任意时刻切换线程。

21.2 x = x + 1 不是原子操作

它通常会被拆成：

load
add
store

所以两个线程同时执行时，结果可能丢失更新。

21.3 Lock 的三个性质

Mutual exclusion
Progress
Bounded waiting

21.4 锁只保护临界区

如果没有持锁，什么都不能保证。所有访问同一个共享变量的地方必须使用同一把锁。

21.5 Condition Variable 必须配合 lock 和 while

标准写法：

lock.acquire();
while (!condition) {
    cv.wait(&lock);
}
lock.release();

21.6 Semaphore 的 P/V 含义

P：等待信号量为正，然后减 1
V：信号量加 1，并唤醒等待者

21.7 信号量初值

生产者消费者中：

fullSlots = 0;
emptySlots = bufSize;
mutex = 1;

21.8 P 的顺序可能导致死锁

错误顺序：

mutex.P();
emptySlots.P();

如果 buffer 满，Producer 拿着 mutex 等 emptySlots，Consumer 又拿不到 mutex，就死锁。

---

22. 典型小测题

题 1：下面程序最终 x 可能是多少？

x = 0;

Thread A: x = x + 1;
Thread B: x = x + 2;

答案：可能是 1、2、3。

原因是 x = x + 1 和 x = x + 2 都不是原子操作，会被拆成 load、add、store。

题 2：为什么 condition variable 要写在 while 里？

因为被唤醒只表示有人 signal/broadcast，不保证条件现在一定成立。其他线程可能抢先改变了共享状态，所以 wait 返回后必须重新检查条件。

题 3：cv.wait(&lock) 是等待 lock 吗？

不是。它等待的是条件变量。它会原子地释放 lock 并睡眠，被唤醒后在返回前重新获取 lock。

题 4：生产者消费者问题中三个信号量初值是什么？

fullSlots = 0;
emptySlots = bufSize;
mutex = 1;

题 5：为什么 emptySlots.P() 不需要先拿 mutex？

因为 P() 本身是原子操作。它原子地完成“检查 emptySlots 是否大于 0”和“减 1”。mutex 的作用不是保护 emptySlots，而是保护真正的 buffer 队列结构。

题 6：Atomicity violation 和 Order violation 的区别是什么？

Atomicity violation 是本来应该不可分割的一组操作被其他线程插队破坏。例如 if (p) use(p) 中间被别人把 p 改掉。

Order violation 是本来应该先发生的操作没有被保证先发生。例如初始化还没完成，另一个线程就开始使用。

---

23. 总结

第 10 章的核心不是背 API，而是理解并发同步背后的问题。

多线程程序的难点在于：线程的执行顺序不受程序员控制，共享状态可能被任意交错访问。因此，我们需要同步机制来限制不安全的交错。

这一章从 Too Much Milk 这个简单例子出发，说明只靠普通 load/store 很难写出正确同步算法。于是我们引入 Lock 来保护临界区，引入 Condition Variable 来等待条件成立，引入 Semaphore 来表达资源数量和线程调度约束。

最后要记住一句话：

并发同步的本质，就是把“任意调度下可能出错的交错”，限制成“只有安全的交错能发生”。

如果能理解这句话，那么 lock、condition variable、semaphore 的用法就都能串起来。