Lecture 4: 并发（Concurrency）

目录 · ← l2 · l4 →

Lecture 4: 并发（Concurrency）

概述

当多个线程共享状态时，执行顺序会影响结果——这就是并发编程困难的根源。本讲从”独立线程 vs 协作线程”出发，引入竞态条件（race condition）、原子操作（atomic operation）、临界区（critical section）与互斥（mutual exclusion）等核心概念，并用经典的”买牛奶问题（Too Much Milk）”演示：仅靠原子读/写无法解决同步问题，从而引出下一讲的锁与条件变量。

核心概念与系统机制图解

独立线程（Independent Threads）vs 协作线程（Cooperating Threads）

• 独立线程：不共享状态，彼此既不能影响也不能被影响。优点：确定性（结果只取决于输入）、可复现、调度顺序无关。例如同时运行两个互不相干的程序。
• 协作线程：共享状态。缺点：非确定性、不可复现、结果依赖执行顺序、调度顺序至关重要。例如多线程银行账户、Web 服务器。

为什么要允许线程协作？

1. 资源共享：一块磁盘上很多文件；一个银行账户文件被很多 ATM 访问；
2. 性能：多核并行执行；I/O 与计算重叠。
3. 结论：并发是必要的，不能回避。

竞态条件（Race Condition）

• 定义：多个线程访问共享数据，且至少一个线程在写，而访问顺序影响结果的情形。

线程 #1:           线程 #2:
A = 1;             B = 1;         → 顺序无关, 无竞态
A = B + 1;         B = 2 * B;     → 顺序相关, 有竞态

原子操作（Atomic Operation）

• 定义：对其它线程而言”看起来瞬间完成”的操作——不可分割（indivisible），无法被观察到执行到一半。
• 通常是原子的：单字读取、单字写入（A = B; 要么读到旧值要么新值，绝不会是半新半旧的位）。
• 通常不是原子的：x++（读-改-写三步）、结构体拷贝、多步操作。
• 关键结论：如果没有硬件提供的原子原语，你无法用软件凭空造出一个来——必须由硬件提供原子读改写指令（Lecture 6 详述）。

临界区与互斥

• 同步（Synchronization）：用原子操作保证协作线程的正确性。
• 临界区（Critical Section）：一次只允许一个线程执行的代码段。
• 互斥（Mutual Exclusion）：强制实现临界区的机制，通常用某种锁实现。

买牛奶问题（Too Much Milk）——软件尝试的演化

问题设定：两个室友分别检查冰箱，若没牛奶就去买，然后置 milk = 1。目标是安全性（绝不买太多牛奶）与活性/可用性（需要时一定有人买）。

尝试1(朴素):                        尝试2(加便条note, 先查milk后写note):
if (milk == 0) {                   if (milk == 0) {
    buy_milk();                        if (note == 0) {
    milk = 1;                              note = 1;
}                                        buy_milk();
   两个线程同时检查milk==0           note = 0;
   → 都去买 → 牛奶过多                 }
                                       }
                                       两个线程可能同时通过 if(note==0) → 仍过多

尝试3(轮流):                        尝试4(各自便条+忙等):
A: if (note == 0) { ... }          A: noteA = 1;
B: if (note == 1) { ... }             if (noteB == 0) { if (milk==0) buy; }
   → 安全, 但A永远等B或B永远等A        noteA = 0;
   (饥饿, 活性失败)                  B: noteB = 1;
                                     while (noteA == 1) {}   // 忙等
                                     if (milk == 0) buy_milk();
                                     noteB = 0;
                                     → 正确! 但不对称 + 忙等浪费CPU

• 对称且正确的软件解法是 Peterson 算法，但本课的重点是：这些尝试都太复杂、太微妙——我们需要更好的原语：锁 和 条件变量（下一讲）。

代码示例与系统调用解说

示例：无同步的计数器（演示竞态）

#include <iostream>
#include <thread>
#include <vector>

int counter = 0;   // 全局共享变量

void increment(int n) {
    for (int i = 0; i < n; i++) {
        counter++;   // 读-改-写, 非原子!
    }
}

int main() {
    std::vector<std::thread> threads;
    for (int t = 0; t < 4; t++) {
        threads.emplace_back(increment, 100000);
    }
    for (auto& t : threads) t.join();
    std::cout << "counter = " << counter << " (期望 400000)\n";
    return 0;
}

【代码做了什么？】 4 个线程各自对共享全局变量 counter 执行 10 万次 counter++，最后打印结果。

【系统机制透视】

• counter++ 在机器层面是三条指令：load counter; add 1; store counter。两个线程可能交错执行（如 T1 load 后、store 前，T2 也 load 到同一旧值），导致两次增量只生效一次。
• 运行结果通常小于 400000 且每次不同——这正是”协作线程非确定性”的直接体现。
• 修复方向（预告）：用 std::mutex 保护临界区，或用 std::atomic<int>（硬件原子指令）。

关键要点

1. 协作线程共享状态 → 执行顺序影响结果 → 竞态。
2. 原子操作 = 对其它线程”不可分割”的操作；单字读写是原子的，多步操作不是。
3. 硬件必须提供原子原语；软件只能在其之上构建更高层的同步构造。
4. 正确同步需同时满足安全性（坏事绝不发生）与活性（好事最终发生）。
5. 买牛奶问题说明：手工软件同步极易出错——这是引入锁与条件变量的动机。

常见陷阱与注意事项

• 假设 x++ 是原子的——它不是。
• 只检查一个条件就进入临界区：检查与修改之间必须是一个原子步骤，否则两个线程都能通过检查。
• 忙等待（busy waiting）：空转循环浪费 CPU；应阻塞（后续用条件变量解决）。
• 只保证安全性而忽略活性（如轮流方案导致的饥饿）。

思考题

1. 问题：A = B;（单字赋值）是原子的吗？A = B + 1; 呢？
   • 答案：A = B; 是单字读+单字写，通常原子；A = B + 1; 至少是”读 B → 计算 → 写 A”，中间步骤可被其它线程交错，不是原子的。
2. 问题：为什么说”如果硬件没有原子操作，软件无法创建一个”？
   • 答案：任何软件”原子化”方案本质上都要靠”读-判断-写”序列，而这些步骤本身需要原子性来防止交错；因此原子性必须由硬件指令（如 x86 的 xchg、lock 前缀）在最底层提供。