一、交替打印 FooBar（LeetCode 1115）
问题：两个线程交替打印 “foo” 和 “bar”，共 N 次。保证 foo 总是在 bar 之前。
解法 1：条件变量（std::condition_variable）
思路：
线程 A (打印 foo) 线程 B (打印 bar)
│ │
│ wait(turn==foo) │ wait(turn==bar)
│ print foo │ print bar
│ turn=bar │ turn=foo
│ notify B │ notify A
│ ... │ ...
整体操作流程（条件变量版）：
- 初始化：创建互斥锁
mtx、条件变量cv、布尔标志foo_turn = true（表示当前该打印 foo）。 - foo 线程：循环 N 次：获取锁 →
cv.wait等待foo_turn == true（如果为 false 则阻塞释放锁）→ 打印 foo → 设置foo_turn = false→cv.notify_one唤醒 bar 线程 → 释放锁。 - bar 线程：循环 N 次：获取锁 →
cv.wait等待foo_turn == false（如果为 true 则阻塞）→ 打印 bar → 设置foo_turn = true→cv.notify_one唤醒 foo 线程 → 释放锁。 - 核心机制：
cv.wait在阻塞前会自动释放锁，被唤醒后重新获取锁并检查条件，保证"foo 总是在 bar 之前"的交替顺序。
class FooBar {
private:
int n;
mutex mtx;
condition_variable cv;
bool foo_turn = true; // true: 该打印 foo, false: 该打印 bar
public:
FooBar(int n) : n(n) {}
void foo(function<void()> printFoo) {
for (int i = 0; i < n; i++) {
unique_lock<mutex> lock(mtx); // ① 获取互斥锁
cv.wait(lock, [this] { return foo_turn; });// ② 等待轮到 foo
// 如果 foo_turn==false，
// 释放锁并阻塞，被唤醒后重查条件
printFoo(); // ③ 打印 foo
foo_turn = false; // ④ 标记轮到 bar
cv.notify_one(); // ⑤ 唤醒 bar 线程
} // ⑥ 解锁（unique_lock 析构）
}
void bar(function<void()> printBar) {
for (int i = 0; i < n; i++) {
unique_lock<mutex> lock(mtx); // ① 获取互斥锁
cv.wait(lock, [this] { return !foo_turn; });// ② 等待轮到 bar
printBar(); // ③ 打印 bar
foo_turn = true; // ④ 标记轮到 foo
cv.notify_one(); // ⑤ 唤醒 foo 线程
}
}
};
关键理解：
cv.wait(lock, pred)等价于while (!pred()) { cv.wait(lock); }。pred是条件检查，防止虚假唤醒（spurious wakeup）。- 锁保护
foo_turn的读写。
解法 2：原子变量（无锁自旋）
整体操作流程（原子自旋版）：
- 初始化：创建原子布尔变量
foo_turn{true}（true 表示该打印 foo）。 - foo 线程：循环 N 次：自旋等待直到
foo_turn == true（每次检查后yield让出 CPU）→ 打印 foo → 原子写入foo_turn = false（使用memory_order_release确保之前操作对其他线程可见）。 - bar 线程：循环 N 次：自旋等待直到
foo_turn == false→ 打印 bar → 原子写入foo_turn = true。 - 内存序说明：
acquire保证本线程能看到其他线程release之前的所有写入；release保证本线程的写入在其他线程acquire后可见。
class FooBar {
private:
int n;
atomic<bool> foo_turn{true}; // ① 原子变量，初始轮到 foo
public:
FooBar(int n) : n(n) {}
void foo(function<void()> printFoo) {
for (int i = 0; i < n; i++) {
while (!foo_turn.load(memory_order_acquire)) {// ② 自旋等待 foo_turn==true
this_thread::yield(); // ③ 让出 CPU 避免忙等
}
printFoo(); // ④ 打印 foo
foo_turn.store(false, memory_order_release);// ⑤ 标记轮到 bar（release 保证可见性）
}
}
void bar(function<void()> printBar) {
for (int i = 0; i < n; i++) {
while (foo_turn.load(memory_order_acquire)) {// ② 自旋等待 foo_turn==false
this_thread::yield();
}
printBar(); // ③ 打印 bar
foo_turn.store(true, memory_order_release); // ④ 标记轮到 foo
}
}
};
解法 1 vs 解法 2 怎么选？
| 对比 | 条件变量 | 原子自旋 |
|---|---|---|
| CPU 占用 | 阻塞时不占 CPU | 自旋时占 CPU |
| 延迟 | 有内核切换开销（~1μs） | 无内核切换（~20ns） |
| 适用场景 | 交替间隔长（>1μs） | 交替间隔极短（<1μs） |
| 实现复杂度 | 稍复杂（需要锁+cv） | 简单（一个 atomic） |
一句话：两个线程紧密交替（如 N 很大且每次打印很快）用原子自旋；间隔长或有 I/O 操作用条件变量。
二、哲学家就餐问题
问题：5 个哲学家围坐，每人左右各一根筷子。只有同时拿到左右两根筷子才能吃饭。吃完了放下筷子让给其他人。如何保证不产生死锁？
经典死锁场景
所有哲学家同时拿起左边的筷子：
线程1: 拿筷子1 (成功) → 等待筷子2
线程2: 拿筷子2 (成功) → 等待筷子3
线程3: 拿筷子3 (成功) → 等待筷子4
线程4: 拿筷子4 (成功) → 等待筷子5
线程5: 拿筷子5 (成功) → 等待筷子1
每个人都拿了一根筷子等着别人放下 → 死锁！
整体操作流程：
- 限制上桌人数：使用
counting_semaphore<4>保证最多 4 个人同时拿起筷子（5 个人每人拿一根筷子就会死锁，4 个人不会）。 - 等待上桌：
table.acquire()阻塞直到桌上有空位（信号量计数 < 4）。 - 按序拿筷子：先拿编号小的筷子，再拿编号大的筷子（
lock函数同时锁住两个 mutex，避免死锁）。 - 吃饭：两根筷子都拿到后，执行
eat()。 - 释放资源：
table.release()释放信号量，让下一个人上桌。 - 死锁预防：两个措施——① 信号量限制最多 4 人同时拿筷子；② 按固定顺序（小号→大号）拿筷子，破坏循环等待条件。
class DiningPhilosophers {
private:
mutex forks[5];
counting_semaphore<4> table{4}; // ① 最多 4 人上桌（C++20）
public:
void philosopher(int id, function<void()> eat) {
int left = id; // ② 左边的筷子编号 = 哲学家编号
int right = (id + 1) % 5; // ③ 右边的筷子编号
while (true) {
think(); // ④ 哲学家思考
table.acquire(); // ⑤ 上桌（信号量 -1，已达上限则阻塞）
lock(forks[min(left, right)], forks[max(left, right)]);// ⑥ 按小→大顺序拿筷子
lock_guard<mutex> l1(forks[min(left, right)], adopt_lock);
lock_guard<mutex> l2(forks[max(left, right)], adopt_lock);
eat(); // ⑦ 同时拿到两根筷子 → 吃饭
table.release(); // ⑧ 下桌（信号量 +1）
} // ⑨ lock_guard 析构时自动放筷子
}
};
为什么 4 个人就不会死锁？
- 5 个人每人拿一根筷子 → 5 根筷子全占满 → 没人能拿到第二根 → 死锁。
- 4 个人最多拿 4 根筷子 → 必然至少有一根筷子空闲 → 至少一个人能拿到两根。
为什么"先拿编号小的筷子"也能防死锁？
- 所有人按照"先小号后大号"顺序拿筷子，就不可能出现"循环等待"（每个人等另一个人释放资源）。这是资源有序分配法。
三、面试追问 Q&A
Q1：cv.wait(lock, pred) 的底层执行顺序？
A：先检查 pred，如果 true 直接返回。如果 false，unlock 并阻塞当前线程（线程进入等待队列）。被 notify 唤醒后，重新 lock 并检查 pred。因为存在虚假唤醒，所以必须用 while 或 pred 重新检查。
Q2：this_thread::yield() 和 this_thread::sleep_for(1ms) 哪个好？
A：yield 只是让出当前时间片（还是就绪状态），很快又被调度回来。sleep_for 会让线程进入睡眠，至少 1ms 后才被唤醒。短时间自旋用 yield，较长时间等待用条件变量或 sleep_for。