经典同步问题¶

经典同步问题的价值不在背诵几段伪代码，而在训练一种可迁移的方法：列出参与者和共享状态，写出不变量，区分互斥条件与等待条件，再检查所有可能交错和退出路径。

通用建模步骤¶

面对同步问题，可以依次回答：

谁是并发参与者？
哪些状态真正共享且可变？
必须始终成立的不变量是什么？
哪些操作必须原子化？
参与者在什么谓词不成立时等待？
谁改变该谓词，改变后通知谁？
是否可能死锁、饥饿、活锁或惊群？
关闭、超时和异常时怎样释放资源？

只要这些问题没有明确答案，代码能通过短测试也不能说明协议正确。

生产者—消费者¶

问题¶

多个生产者向容量为 \(C\) 的缓冲区加入对象，多个消费者取走对象。不变量：

\[ 0\le count\le C. \]

需要解决两个不同问题：

互斥：队列结构不能被并发破坏。
条件同步：满时生产者等待，空时消费者等待。

信号量方案¶

empty = C
full = 0
mutex = 1

producer:
    wait(empty)
    wait(mutex)
    enqueue(item)
    post(mutex)
    post(full)

consumer:
    wait(full)
    wait(mutex)
    item = dequeue()
    post(mutex)
    post(empty)

empty + full = C 表示资源计数不变量，mutex 保护队列内部结构。

背压的直觉¶

缓冲区不是为了让生产者永不等待，而是吸收短时速率波动。若长期平均生产速率 \(\lambda_p\) 大于消费速率 \(\lambda_c\)，任何有限缓冲最终都会满：

\[ \lambda_p>\lambda_c\quad\Longrightarrow\quad\text{backlog grows}. \]

正确系统必须把压力传回上游、降级或丢弃，而不是无限扩容。

读者—写者¶

问题¶

读操作可并发，写操作必须独占，并且写时不能有读者。基本不变量：

writer_active -> reader_count == 0
reader_count > 0 -> writer_active == false

读者优先¶

只要已有读者，新读者也可加入。读吞吐高，但持续到来的读者可能让写者永久等待。

写者优先¶

一旦写者等待，阻止新读者进入，让已有读者退出后尽快执行写者。写者延迟改善，但读者可能在写入负载高时饥饿。

公平方案¶

按到达顺序或阶段批处理读者和写者，试图限制两侧等待。公平通常要维护额外队列和状态，吞吐可能低于偏向某侧的方案。

读写锁只有在以下条件下更可能胜过普通互斥锁：

读操作占绝大多数。
临界区足够长，允许并发读的收益超过锁内部管理成本。
写者饥饿策略符合需求。

短临界区或频繁写入时，普通互斥锁可能更快、更简单。

哲学家就餐¶

朴素方案为什么死锁¶

五位哲学家围坐，每人先拿左叉再拿右叉。如果所有人同时拿起左叉，就形成环形等待：每人持有一把叉并等待邻居手中的另一把。

P0 等 P1
P1 等 P2
P2 等 P3
P3 等 P4
P4 等 P0

方案一：全局资源顺序¶

为所有叉编号，每位哲学家总是先拿编号较小的，再拿编号较大的。这样等待边只能沿编号单调增大，不可能形成环。

这个思想可推广到内核锁：定义全局锁层级，跨对象操作按固定顺序获取。

方案二：限制同时竞争者¶

只允许最多四位哲学家进入拿叉阶段，至少留出一个打破环路的机会。可用计数信号量表达。

方案三：服务员集中分配¶

哲学家先向服务员申请两把叉，服务员只在二者都空闲时一次性授予。这消除了“占有一部分再等待另一部分”，但服务员成为集中协调点。

正确但不公平¶

打破死锁不自动避免饥饿。某位哲学家可能每次都在竞争中失败。若需求包含有界等待，还要增加排队或公平策略。

睡眠理发师¶

理发店有一位理发师、一把理发椅和 \(N\) 把等待椅：

没顾客时理发师睡眠。
顾客到达，有空等待椅则入队并唤醒理发师。
无空位时顾客离开。

共享状态包括等待队列、空椅数量和理发师状态。这个问题强调“事件发生在无人等待时怎么办”：顾客入队这一持久状态不能只用一次瞬时通知表示。

可以用：

customers 计数信号量表示等待顾客数量。
barber_ready 表示理发师可接待。
互斥锁保护等待椅和队列。

屏障同步¶

并行计算常分为多个阶段，每个线程必须完成第 \(g\) 轮后，所有线程才能进入第 \(g+1\) 轮。

最小状态：

arrived：本轮到达数量。
generation：当前轮次。
条件变量：等待轮次变化。

最后一个到达者把 arrived 清零、递增 generation 并广播。等待者必须检查轮次，而不只检查计数，否则快速线程进入下一轮后可能与上一轮唤醒混淆。

优先级反转¶

低优先级线程 L 持锁，高优先级线程 H 等待该锁；中优先级线程 M 不需要锁，却持续抢占 L。结果 H 间接被 M 延迟，看起来优先级关系反转。

优先级继承让 L 在持有 H 所需锁期间临时继承更高优先级，以便尽快完成临界区。它缓解特定阻塞链，但增加调度与锁实现复杂度；嵌套锁还需要传播继承关系。

从题目迁移到工程¶

经典问题	工程对应
生产者—消费者	任务队列、日志管线、网络缓冲
读者—写者	配置快照、路由表、元数据缓存
哲学家就餐	多锁顺序、事务资源获取
睡眠理发师	有限服务台与拒绝策略
屏障	并行迭代、批同步计算

经典问题把复杂系统压缩到最少角色，使错误更容易看见。工程系统还要加上取消、超时、失败、动态参与者和分布式边界。

常见错误检查表¶

等待前是否持有保护谓词的锁？
等待是否在循环中重新检查？
状态改变后是否通知了正确等待者？
获取多个资源时是否有全局顺序？
阻塞等待时是否错误地持有其他人需要的锁？
关闭时所有等待者是否都能醒来并观察关闭状态？
公平性是否满足业务，而不只是没有死锁？

自测¶

生产者—消费者为什么同时需要互斥和条件同步？
读者优先方案可能让谁饥饿？
全局叉编号怎样破坏哲学家问题的环形等待？
可重用屏障为什么需要 generation？
优先级继承解决的是死锁、饥饿还是优先级反转？

参考思路

队列结构需互斥，空/满需条件等待。读者优先可能饿死写者。固定顺序让资源等待图不能成环。generation 区分相邻轮次。优先级继承针对低优先级持锁者阻塞高优先级任务的反转现象。