并发经典问题：同步算法与模式（Concurrent Algorithm Design / Synchronization Theory）

这一份文档不讲具体 C++ API，而是从操作系统与并发理论角度，梳理一组在多种语言/教材中都会出现的经典并发问题。

可以把它们理解为：

训练如何设计正确同步机制的“标准题库”
用来练习 mutex / semaphore / condition variable / monitor 等工具的使用与组合。

一、这一类问题属于什么范围

这些问题属于并发体系中的一个子领域：

Concurrency Synchronization Patterns
或更广义的：Concurrent System Design

主要研究三件事：

如何协调多个线程 / 进程的行为；
如何避免数据竞争与状态破坏；
如何避免死锁、饥饿等系统级问题。

它们并不依赖某种具体语言（C、C++、Java、Go、Rust 都会讲），而是给出抽象问题模型，要求你用适当的同步原语构造出正确解法。

二、这些问题的共同结构与目标

典型结构：

多个线程或进程（哲学家、顾客、理发师、读者/写者等）；
一些共享资源（叉子、椅子、缓冲区、数据库记录）；
潜在访问冲突（同时读写、互相等待、抢占资源）；
某种公平或效率要求（不能让某一方永远等不到机会）。

问题的目标一般包括：

正确性：不破坏共享状态、不出现非法情况；
无死锁：系统不会陷入“大家互相等”完全停住的状态；
无饥饿：任何一个参与者不会被无限期推迟；
尽可能高的并行度：在安全前提下，让更多操作能同时进行。

换句话说：

不是“在某种调度下可以跑通”，而是“在任何可能的调度下都正确运行”。

三、这些问题在整个并发体系中的位置

如果把并发知识粗略分层，可以这样看：

第一层：线程与生命周期
- 线程创建 / join / detach / 生命周期管理
第二层：基础同步工具
- mutex / semaphore / condition variable / monitor
第三层：经典同步问题（本篇主题）
- producer–consumer, reader–writer, dining philosophers, sleeping barber, bounded buffer, cigarette smokers, 线程池等
第四层：并发架构
- thread pool, actor model, task scheduler, reactor/proactor 等
第五层：高性能并发
- lock-free / wait-free、cache 优化、NUMA、无锁队列等

你现在要学的这些“经典问题”主要位于 第三层：

站在“问题模型”的层面，训练如何用第二层的同步原语构造正确的并发协议。

四、逐个问题的核心意义（为何要练它）

4.1 Producer–Consumer（生产者–消费者）

问题模型：

一方生产数据（producer），一方消费数据（consumer）；
数据放入共享缓冲区（buffer），有容量上限；
缓冲区空：消费者必须等待；
缓冲区满：生产者必须等待。

训练点（你应该刻意关注）：

使用 mutex + condition_variable（或 semaphore）协调空/满状态；
保证：
- 不会从空 buffer 取数据；
- 不会往满 buffer 写数据；
- 在可能的情况下保持最大并行度（生产与消费尽量并行）。
这是条件变量 / 信号量最经典的入门练习题。

典型抽象接口（伪代码）：

void produce(Item x);：往缓冲区放入一个元素，必要时阻塞等待空位；
Item consume();：从缓冲区取出一个元素，必要时阻塞等待数据；

背后一般有：

一个有限容量的队列（数组 + head/tail 或 std::queue）；
一个互斥量 mutex；
两个条件变量 not_full / not_empty（或两个信号量 empty_slots / filled_slots）。

常见实现思路（条件变量风格）：

进入 produce / consume 时先 lock_guard<mutex> 上锁；
条件不满足时，使用 cond.wait(lock, predicate) 阻塞：
- 模式是 while (!predicate()) cond.wait(lock); 防止虚假唤醒；
修改队列后，唤醒对应的一方：
- 生产者入队一个元素 → not_empty.notify_one()；
- 消费者出队一个元素 → not_full.notify_one()。

常见错误：

用 if 替代 while 做条件检查（虚假唤醒下直接出错）；
在检查条件和实际操作之间没有保持锁定，导致竞态；
条件变量与互斥量错误组合（例如 wait 时没有持有对应的锁）；
错误唤醒：明明需要唤醒所有等待者，却只唤醒一个线程，导致部分线程长期饥饿。

可以练的变体：

多生产者、多消费者，而不仅是 1:1；
支持超时等待：consume_with_timeout()；
支持关闭队列：当系统退出时，优雅地让所有消费者结束。

4.2 Reader–Writer（读者–写者）

问题模型：

多个线程读取共享数据（readers）；
少数线程写入数据（writers）；
需求：
- 多个 reader 可以同时读取（不互相干扰）；
- 任意写操作必须独占访问（不能与其他 reader/writer 同时进行）。

训练点（你应该刻意关注）：

设计 reader–writer lock（读写锁） 的同步协议：
- 允许多读；
- 写时独占；
- 还要考虑 “reader 优先” vs “writer 优先” vs “公平策略”。
学会用计数器 + 互斥量 + 条件变量，显式建模“当前有多少 reader / writer 在场”，并围绕这些状态设计等待 / 唤醒逻辑。

典型状态变量：

int active_readers;：当前正在读取的 reader 数量；
int waiting_writers;：正在排队等待写入的 writer 数量；
bool writer_active;：当前是否有 writer 正在写；
一个保护这些变量的 mutex；
两个条件变量：ok_to_read / ok_to_write。

常见策略示例：

reader 优先：
- 只要没有 writer 正在写，新的 reader 都可以进来；
- 吞吐量高，但容易造成 writer 长期饥饿。
writer 优先：
- 一旦有 writer 在等待，就阻止新的 reader 进入；
- 保证 writer 不饥饿，但 reader 延迟可能变大。
公平策略：
- 所有请求（读 / 写）放在一个队列里，严格按到达顺序调度。

常见错误：

忘记在最后一个 reader 离开时唤醒 writer；
写结束时只唤醒一个 reader，导致读方吞吐不足；
没有统计 waiting_writers，导致名义上“writer 优先”但实现上依然被 reader 抢占；
把“读锁”和“写锁”拆成两个互不协调的 mutex，产生死锁或数据竞争。

现实对应：

数据库 / 缓存系统：大量读取、少量写入；
配置中心 / 缓存中的读多写少访问模式；
C++17 的 std::shared_mutex 就是这个问题的库级实现，可以对照它的语义反推你自己的设计。

4.3 Dining Philosophers（哲学家就餐问题）

问题模型：

N 个哲学家围圆桌而坐，每人左右各有一根叉子；
吃饭需要同时拿到左右两根叉子；
若所有人先拿左叉子，再等右叉子 → 可能造成环形等待，从而死锁。

训练点（你应该刻意关注）：

复习并具体体会 死锁四条件：
- 互斥（每根叉子同一时刻只能一个人拿）；
- 占有并等待（先拿到一根叉子，再等另一根）；
- 不可抢占（不能强行从别人手里把叉子抢走）；
- 循环等待（每个人都在等别人手上的资源）；
学会通过设计策略破坏其中至少一个条件，避免死锁：
- 尤其是“循环等待（circular wait）”与“资源有序分配”。

常见建模方式：

每根叉子是一个互斥量：std::mutex forks[N];
第 i 个哲学家是一个线程，循环执行：
- 思考（think()）
- 拿起左叉子 → 拿起右叉子
- 吃饭（eat()）
- 放下右叉子 → 放下左叉子

关键问题在于：以什么顺序拿叉子 / 放叉子，是否需要额外的约束。

典型解法策略：

资源有序分配：
- 给每根叉子编号（0 ~ N-1），规定哲学家总是“先拿编号小的，再拿编号大的”；
- 这样就不存在环形等待（资源获取顺序是全局一致的）。
打破对称性：
- 例如让编号为偶数的哲学家“先左后右”，奇数哲学家“先右后左”；
- 消除“大家动作完全一样”带来的死锁。
限制并发进餐人数：
- 例如引入一个计数信号量，最多允许 N-1 个哲学家同时尝试拿叉子；
- 确保至少有一个人能拿到两根叉子，从而打破僵局。

常见错误：

朴素实现：所有哲学家都“先左后右”拿叉子，直接构成环形等待 → 程序偶发或必现死锁；
只关注“死锁”而忽略“活锁”：大家同时很礼貌地放下叉子、同时再试，结果谁也吃不到饭；
没有统一考虑“加锁顺序”，在更复杂的多资源场景里很容易写出难以发现的死锁。

可以练的变体：

把“两个叉子”推广为“多个资源”：每个哲学家需要 3 种甚至更多资源，看如何扩展“资源有序分配”策略；
引入“服务生（waiter）”线程：
- 哲学家先向服务生申请用餐许可，拿到许可才能去拿叉子；
- 练习“集中式仲裁（centralized arbiter）”这种模式；
把叉子抽象成“锁 / 文件句柄 / 设备”，在真实代码中按照“资源 ID 排序”统一加锁顺序，减少死锁风险。

4.4 Sleeping Barber（理发师睡觉问题）

问题模型：

一个理发师、一个理发椅、若干等候座位；
没有顾客时，理发师睡觉；
顾客到来：
- 若有空位，则坐下等待；
- 若无空位，则直接离开；
- 若理发师在睡觉，叫醒他开始工作。

训练点（你应该刻意关注）：

这是带有有限队列 + 动态到达的生产者–消费者变体；
练习如何用条件变量 / 信号量实现事件驱动的等待 / 唤醒：
- 谁在什么条件下睡（阻塞）；
- 谁在什么条件下被唤醒；
- 如何表达“等待室已满 / 有顾客等待 / 没有顾客”等状态。

典型状态建模：

常量 N：等待室座位数量；
int waiting_customers;：当前等待的顾客数量；
一个互斥量 mutex 保护上述状态和等待队列；
条件变量示例：
- cond_customer：顾客到达时唤醒理发师；
- 有时还会建 cond_barber：通知顾客开始理发。

顾客线程的典型逻辑（示意）：

进入店里，上锁检查：
- 若 waiting_customers == N：等待室满 → 直接离开；
- 否则：waiting_customers++，加入等待队列；
如果理发师正在睡（可用状态变量标记），唤醒理发师；
在被叫到理发椅之前，可以在某个条件变量上等待；
真正开始理发 / 理完发的时机由理发师线程通过唤醒来驱动。

理发师线程的典型逻辑（示意）：

无限循环：
- 上锁检查 waiting_customers：
  - 若为 0：在 cond_customer 上等待（睡觉）；
  - 若 > 0：从等待队列里取一个顾客，waiting_customers--；
- 解锁后为该顾客理发（模拟耗时）；
- 理完发后可以通过条件变量通知顾客离开（视建模细节而定）。

常见错误：

顾客到来时没有正确唤醒理发师，导致理发师永远睡着；
使用忙等（while + 空循环）代替条件变量，浪费 CPU；
等待 / 唤醒配合不当：例如唤醒前没更新状态，导致被唤醒方再次看到“条件不满足”而继续睡；
没有正确处理“店要关门”的情况，理发师线程无法优雅退出（一直阻塞在 wait）。

可以练的变体：

多个理发师、多把理发椅 → 需要在等待队列和理发椅分配间做更复杂调度；
增加“不同服务类型 / 不同优先级顾客”，思考如何在等待队列里体现优先级；
将此模型映射到现实场景：
- 比如“线程池 worker 等待任务”、“服务器空载时挂起、请求到来再唤醒”等。

本质上是 Producer–Consumer 的标准形式：

重点在“有限容量”这个约束；
经典教材中通常把它作为 signal/wait（P/V 操作）与条件变量的综合练习。

训练点（你应该刻意关注）：

设计多生产者、多消费者共享固定大小环形缓冲区的同步协议；
正确使用两个计数信号量（或两个条件变量）：
- “空槽位数” 与 “已用槽位数”；
熟悉环形队列（circular buffer） 的下标运算方式（head / tail 以及 % capacity）。

典型信号量版思路：

semaphore empty_slots(capacity);：当前还能放多少元素；
semaphore filled_slots(0);：当前有多少元素可供消费；
mutex m;：保护实际数组和 head / tail 下标。

生产者伪代码：

wait(empty_slots)：先抢占一个空位；
lock(m) → 在 tail 位置写入数据、更新 tail → unlock(m)；
signal(filled_slots)：告诉消费者“有新数据了”。

消费者伪代码：

wait(filled_slots)：先确保有数据可读；
lock(m) → 在 head 位置读出数据、更新 head → unlock(m)；
signal(empty_slots)：释放一个新的空位。

常见错误：

把 head / tail 更新放在加锁区外，导致数据竞争；
环形队列判空 / 判满条件写错，出现“假满 / 假空”；
只在单线程下调试，通过后就自信上线，没有真正考虑多线程调度下的 interleaving。

4.6 Cigarette Smokers（抽烟者问题）

问题模型：

有三个抽烟者，每人无限量地持有某一种材料（烟草 / 纸 / 火柴）；
桌上有一个代理（agent），每次随机放下其中两种材料；
拥有第三种材料的抽烟者被唤醒，拿走材料并卷烟抽。

训练点（你应该刻意关注）：

这是一个经典的 复杂条件同步 题目：
- 不同的“材料组合”应该唤醒不同的抽烟者；
练习用多个条件变量 / 信号量，表达“谁在什么条件下可以继续执行”；
学会把“组合条件”拆成更容易管理的一组状态与事件。

典型角色建模：

一个 agent 线程：循环做“放材料”的动作；
三个 smoker 线程：
- smoker_tobacco：拥有无限烟草；
- smoker_paper：拥有无限纸；
- smoker_match：拥有无限火柴。

常见同步设计思路：

对每个 smoker 准备一个专属信号量 / 条件变量：
- sem_for_tobacco_smoker、sem_for_paper_smoker、sem_for_match_smoker；
agent 逻辑（示意）：
- 随机选择一种“缺的材料”；
- 在桌上放下另外两种材料；
- 唤醒对应的 smoker；
- 等待 smoker 抽完烟后再进入下一轮（比如通过另一个 sem_agent 控制节奏）。
smoker 逻辑（示意）：
- 在自己的信号量上等待；
- 被唤醒后，拿走桌上的两种材料，开始卷烟 / 抽烟；
- 完成后清理桌面状态，并通知 agent 可以继续。

关键难点：

任一时刻“桌上材料状态”必须与“谁被唤醒”相匹配；
agent 不能在 smoker 还没处理完桌上材料时就再次放材料；
需要一个清晰的状态机来保证：
- “桌上空 / 桌上有两种材料 / 正在被某个 smoker 使用”等状态之间的转换是受控的。

常见错误：

所有 smoker 共享一个条件变量，结果唤醒到错误的线程；
忘记在 smoker 完成后清理桌面状态，下一轮 agent 放材料时状态混乱；
用一堆松散的 bool 变量拼状态，没有统一的不变量约束，导致推理困难、容易出 bug。

可以练的变体：

把材料种类从 3 种扩展到 N 种，agent 每次放下 K 种，思考如何一般化唤醒逻辑；
让 agent 不再“随机”，而是根据某种策略（轮询 / 优先级）选择下一个 smoker；
把场景类比到真实系统：
- 例如“一个任务只有在集齐多种资源后才能执行”的调度问题。

4.7 Thread Pool（线程池）

问题模型：

一组长期存在的 worker 线程；
一个任务队列（可能有优先级）；
外部系统向队列投放任务，由线程池调度执行。

训练点：

线程生命周期与任务生命周期解耦：
- 线程数固定/缓慢变化，任务数动态变化；
正确使用：
- 任务队列的 mutex + condition_variable；
- 任务分发与线程关闭时机；
处理：
- 高负载下的任务排队；
- 关闭池时如何安全停止 worker。

现实中几乎所有服务器/引擎系统都会有某种“线程池 + 任务队列”的实现，是工程实践中最重要的并发模式之一。

五、为什么这些问题值得花时间练

这些问题本身并不是“真实业务”，但它们扮演的角色类似于：

在算法学习中的：
- two-sum、binary search、graph traversal；
在数据结构学习中的：
- stack、queue、heap、BST 基础题。

通过这些经典问题可以系统训练：

同步机制的正确使用：
- mutex / semaphore / condition_variable / monitor 等的组合；
死锁与饥饿的识别与规避；
在保持正确性的前提下提升并发度：不会因为“过度串行化”而丢掉多核优势。

换句话说，它们让你练的是：

“在任何调度顺序下都正确的并发协议设计能力”，而不仅是“在自己电脑上跑一跑好像没问题”的经验代码。

六、这些问题在真实系统中的映射

这些模型都能在真实系统中找到对应：

Producer–Consumer / Bounded Buffer
- 日志系统写入；
- 网络 I/O 的接收缓冲区；
- 视频解码管线中的各级 buffer。
Reader–Writer
- 数据库读写锁；
- 配置中心 / 缓存中的读多写少访问模式。
Dining Philosophers
- 多资源分配场景（多个锁、多个设备、多个文件句柄）；
- 任意“多个参与者需要同时获得多种资源”的问题。
Sleeping Barber / Cigarette Smokers
- 事件驱动服务器中的等待/唤醒问题；
- 复杂条件触发下的任务派发。
Thread Pool
- Web 服务器；
- 交易撮合系统；
- 各种任务调度器、Actor 运行时。

理解这些抽象问题，有助于你在看到真实业务场景时，马上在脑子里匹配到已经练习过的“题型”。

七、一句话总结

这些并发经典问题属于：

并发同步算法（Concurrency Synchronization Algorithms）与模式（Patterns）

它们是用来训练你如何：

使用 mutex / semaphore / condition_variable / monitor 等同步机制；
设计不会发生 data race / 死锁 / 饥饿的并发协议；
在保证正确性的前提下，让系统保持尽可能高的并行度。

等你熟练掌握这些问题的建模与解法，再去实现线程池、Actor 模型、lock-free 结构，你会发现很多看似复杂的并发架构，背后都能拆成这些基础问题的组合与变形。