《操作系统导论》第 32 章：常见并发问题 - 深度知识架构

1. 核心矛盾 (The Crucial Problem)

在实际的复杂多线程程序中，究竟存在哪些高频触发的并发缺陷模式（非死锁与死锁），程序员和系统架构师应该如何预防、避免或从中恢复？

2. 核心概念 (Core Concepts)

• 违反原子性 (Atomicity Violation)：
  • 定义：本该作为一个原子操作（不可分割）执行的指令序列，在执行中途被其他线程打断或介入了。
  • 角色：最常见的非死锁缺陷之一，打破了程序员对某块代码处于互斥状态的假设。
• 违反顺序 / 错误顺序 (Order Violation)：
  • 定义：两个线程发生内存访问的顺序，与程序员预期的顺序发生了颠倒。
  • 角色：另一种常见的非死锁缺陷，打破了程序员对线程执行先后次序的假定。
• 死锁 (Deadlock)：
  • 定义：两个或多个线程由于互相持有对方需要的锁，并请求对方已持有的锁，导致循环等待，最终全部永久卡死的现象。
  • 角色：并发世界中破坏力极强的“冻结魔法”，它是系统设计复杂度和模块化带来的副作用。
• 无等待数据结构 (Wait-Free Data Structure)：
  • 定义：利用强大的硬件原子指令（如比较并交换，Compare-and-Swap, CAS），让线程完全不需要加锁就能更新共享状态的并发数据结构。
  • 角色：死锁的“免疫抗体”。没有锁就不会有死锁，这是完全避免互斥的极端方案。
• 全序 (Total Ordering) 与 偏序 (Partial Ordering)：
  • 定义：在系统中为所有的锁（或部分相关的锁）人为规定一个严格的获取顺序约定（如：必须先抢 L1，才能抢 L2）。
  • 角色：打破死锁“循环等待”条件的架构级防御机制。

3. 逻辑演进 (Logical Evolution)

针对真实世界中的并发缺陷（如 Lu 等人对 MySQL、Apache 等软件的研究），系统的应对逻辑演进如下：

• 应对非死锁缺陷（占总缺陷的大多数）：
  • 遇到的问题：多线程下不可控的调度，轻易打破了对代码原子性和顺序性的直觉假设。
  • 成熟的方案：回归我们在前几章学过的基础原语。对于“违反原子性”，用锁 (Locks) 强制将临界区保护起来；对于“违反顺序”，用条件变量 (Condition Variables) 强制实现状态的检查与等待，约束执行次序。
• 应对死锁缺陷（占比少但后果致命）：
  • 最初的困惑：既然只要大家按同样顺序抢锁就不会死锁，为什么死锁还总是发生？因为现代软件极其庞大，子系统交互极其复杂（比如虚拟内存要调文件系统，文件系统又要调虚拟内存），而且软件工程过度提倡“封装”，隐藏了锁的细节，导致调用者不知不觉就引发了交叉等待。
  • 演进方案 1（死锁预防 - Prevention）：在代码规范上，建立锁获取的全序或偏序，彻底消除循环等待的可能。 或者更进一步，设计无等待数据结构，彻底消灭互斥。
  • 演进方案 2（死锁避免 - Avoidance）：在调度层面下手。利用调度器（如 Dijkstra 的银行家算法），如果发现两个线程可能会争抢同一组锁，就不让它们同时运行，强行让它们在同一个中央处理器 (Central Processing Unit, CPU) 上串行执行。
  • 最终务实方案（死锁检测与恢复 - Detect and Recover）：既然完美预防死锁成本太高，干脆允许它偶尔发生。系统定期运行死锁检测器（构建资源图查找环路），一旦发现死锁，就直接重启系统 (Reboot) 或终止某个线程。这是数据库系统常用的兜底手段。

4. 机制与策略 (Mechanisms vs. Policies)

• 底层的“实现手段”（机制 - Mechanisms）：
  • 硬件原子指令（如 Compare-and-Swap）是实现无等待（无锁）数据结构的底层驱动力。
  • 操作系统底层的锁和条件变量，是修复违反原子性和违反顺序这两种非死锁缺陷的基础机制。
  • 死锁检测器（定期构建并遍历有向资源图来寻找环路）是死锁发现的机制。
• 上层的“决策逻辑”（策略 - Policies）：
  • 锁排序策略：在代码库中制定偏序或全序获取规则，是纯粹的人为工程策略。
  • 保守调度策略：系统调度器根据线程对锁的需求（如有先验知识），人为决定将本可并行的线程强行串行化调度的策略。
  • 容忍与恢复策略：决定系统是应该“不惜一切代价预防死锁”，还是采取“让它死锁大不了重启”的宽容策略（这取决于应用场景，比如 Web 服务 vs 航天飞机）。

5. 设计折衷 (Design Trade-offs)

• 牺牲“软件模块化与封装”，换取“死锁的安全防御”：软件工程一向教导我们要隐藏实现细节（封装），但这对于并发编程却是致命的。隐藏锁的细节使得外部调用者很容易无意间造成锁的循环依赖。为了避免死锁，我们通常不得不破坏封装，让底层锁的获取顺序暴露在架构设计中。
• 牺牲“多核并发性能”，换取“绝对的无死锁”：通过调度器来避免死锁的方法（如让可能产生竞争的线程排队在同一个 CPU 上运行），虽然保证了安全，但却因为无法将任务分散到多个空闲 CPU 上，付出了巨大的性能代价。
• 牺牲“理论上的完美正确”，换取“工程上的极简与实用”：这是极其重要的折衷。完美预防和避免死锁通常会导致代码极度复杂或性能低下，因此工程师往往选择容忍低概率的死锁，用简单的“检查并重启”来对付它。

6. 关键洞察 (Key Insights)

• 面向对象的封装是并发编程的死敌：不要盲目迷信封装。当涉及到锁时，如果你不知道一个函数内部抢了什么锁，你就如同蒙着眼睛在雷区穿行，随时可能与外层的锁形成循环依赖导致死锁。
• 不要总是追求完美 (Tom West 定律)：“不是所有值得做的事情都值得做好” (Not everything worth doing is worth doing well)。如果坏事（如死锁）很少发生，并且造成的影响很小（重启就能解决），那么花费大量心智负担和性能去“完美预防”是不划算的。有时候，笨拙的重启反而是最高明的工程智慧。
• 彻底摆脱锁的泥潭，也许需要换个赛道：虽然无等待 (Wait-Free) 数据结构从理论上消灭了死锁，但它构建起来实在太复杂了。解决并发困境的真正出路，或许根本不是发明更高级的锁，而是开发全新的并发编程模型（如 Google 的 MapReduce），让程序员从源头上就不需要手动去管理锁。

7. 死锁 (Deadlock) 的图论证明：资源依赖环

导师的下一步建议：

恭喜！我们已经系统掌握了各类并发缺陷及其应对策略。传统多线程虽然强大，但手动加锁带来的心智负担和潜在 Bug 让许多开发者苦不堪言。下一章将介绍一种另辟蹊径的并发模型——基于事件的并发，它通过避免多线程来彻底规避锁问题，在高性能网络服务器领域大放异彩。

MOC · 下一章：Ch33 基于事件的并发