基于锁的并发问题

即使所有共享数据操作都用锁保护好了，基于锁的并发仍有四类问题：死锁 (Deadlock)、活锁 (Livelock)、饥饿 (Starvation)、优先级反转 (Priority Inversion)。哲学家就餐问题集中体现了它们。GEA 由此总结出经验法则：全局排序、事务式算法、尽量减少争用；并反对把所有接口都做成「100% 线程安全」，主张正视并发、少用锁。

死锁（卷 I 4.7.1）

系统中没有任何线程能前进，程序挂起：所有线程都处于阻塞态等资源，而没有可运行线程去释放资源。至少需要两个线程和两个资源，例如线程 1 持有 A 的锁去等 B，线程 2 持有 B 的锁去等 A（两段代码 lock 顺序相反）。本质是线程与资源之间的循环依赖。
分析方法：画线程-资源依赖图，去掉资源节点只保留「线程等线程」的边，图中有环即死锁。

下面的图示意最简单的环：

flowchart LR
  T1["线程 1 持有 A"] -- "等待 B" --> T2["线程 2 持有 B"]
  T2 -- "等待 A" --> T1

严格说环还不够，死锁的充要条件是四个 Coffman 条件：(1) 互斥：资源可被单个线程独占；(2) 持有并等待：线程持有一把锁时去睡眠等另一把；(3) 不可抢占：没人（包括内核）能强行打破睡眠线程持有的锁；(4) 循环等待：依赖图中存在环。
- 原书问题：书中称这四条是「充分必要」条件。按 Coffman、Elphick、Shoshani《System Deadlocks》（ACM Computing Surveys, 1971）及 Silberschatz《Operating System Concepts》的标准表述，四条是死锁的必要条件；只有当每类资源只有一个实例（如每把互斥锁）时，资源分配图中的环才同时是充分条件；资源有多个实例（如计数信号量）时，有环也不一定死锁。对只涉及互斥锁的场景，书中结论成立。
避免死锁就是破坏其中至少一条。破坏 1 和 3 算「作弊」，所以通常针对 2 和 4：
- 减少锁的数量来避免持有并等待：A、B 用同一把锁 L 保护，就不会死锁。
- 全局加锁顺序来避免循环等待：规定总是先锁 A 再锁 B。

活锁（卷 I 4.7.2）

另一种避免死锁的办法是用 pthread_mutex_trylock() 尝试加锁，失败就短暂睡眠后重试。但线程可能把全部时间都花在解决冲突上，做不了真正的工作，这就是活锁，类似象棋里的僵局。例：两个线程拿不到锁就释放已有的锁并等待固定超时再试，超时相同时同样的局面无限重复。
解决：采用非对称的死锁解决算法，例如只让一个线程（随机选或按优先级）在检测到死锁时采取行动。

饥饿（卷 I 4.7.3）

一个或多个线程得不到 CPU 时间。可能因高优先级线程不让出 CPU；活锁也是一种饥饿。避免优先级饥饿的做法是确保高优先级线程不会运行很久：理想的多线程程序由一池低优先级线程公平共享 CPU，偶尔有高优先级线程快速处理完事务后结束。调度规则见进程、线程与纤程。

优先级反转（卷 I 4.7.4）

低优先级线程 L 持锁后被高优先级线程 H 抢占，H 请求同一把锁而睡眠，于是 L 在 H 可运行时仍在运行，违背优先级原则。另一种情况：中优先级线程 M 抢占持锁的 L，L 无法释放锁，H 拿不到锁只能睡，M 的优先级实际上与 H 反转了。
后果可能可以忽略（L 很快释放锁），极端情况下会导致死锁或系统失效，例如高优先级线程错过关键截止时间。
解决：(1) 避免高低优先级线程共用锁（常不可行）；(2) 给互斥锁本身设很高的优先级，持锁线程临时提升到该优先级，持锁期间不会被抢占；(3) 随机优先级提升：随机提升正持锁线程的优先级直到它离开临界区，Windows 调度模型采用此法。

哲学家就餐问题（卷 I 4.7.5）

五位哲学家围坐圆桌，每两人之间一根筷子，吃饭需要两根，思考不需要。目标是设计行为规则，使他们交替思考与进餐而不死锁、活锁或饥饿（哲学家代表线程，筷子代表互斥锁）。

解法	做法	破坏的条件/效果
全局顺序	每根筷子编号，总先拿编号小的	消除循环依赖，避免死锁
中央仲裁者（「服务员」）	要么给两根，要么一根不给	消除持有并等待
Chandy-Misra（书中写作 Chandra-Misra）	筷子标记脏/干净，哲学家互发消息请求筷子	消息传递方案
N−1 位哲学家	用整数信号量限制最多 N−1 人同时拿筷子	至少一人能拿到两根，解决死锁和活锁；但除非引入公平性准则，仍可能有人饥饿

并发的经验法则（卷 I 4.8）

全局排序规则：并发程序中事件顺序不由指令顺序决定，需要顺序就必须在所有线程间全局施加。这是双向链表不是并发数据结构的原因之一：它的设计目的是在任意位置快速插入/删除，并假设程序顺序等于数据顺序。（原书问题：书中把这种「快速」插删写成 O(N)；已知位置时双向链表的插删是 O(1)，O(N) 是查找的复杂度。）单线程中「在 C 前插 D，再在 C 前插 E」得到 {A, B, D, E, C}；两个线程各做一次插入，可能得到 {A,B,D,E,C}、{A,B,E,D,C}，或者没保护好时链表损坏（D 和 E 的 next 都指向 C）。应先问顺序是否重要：不重要就用单链表并总在头部插入（可加锁或无锁可靠实现）；重要就找一个与事件发生顺序无关的稳定排序准则（按字母、按优先级等），再据此选数据结构。让多个线程并发修改双向链表就像把方钉塞进圆孔。
事务式算法：中央仲裁者成对发筷子就是事务——不可分割的资源/操作包，要么全部成功，要么全部失败；失败的线程反复重新提交（可短暂等待）。事务是多数无锁数据结构和算法的基础（见无锁编程与内存序）。
最小化争用：例如多个线程都往一个中央仓库写数据，可以给每个线程一个私有仓库，最后由中央线程汇总。相当于给每位哲学家两根筷子——没有共享就没有并发。现实中无法消除所有共享，但应尽量减少。
线程安全：任何线程都能安全调用的类或 API 叫线程安全，通常在函数开头进入临界区、返回前离开；全部函数都线程安全的类有时叫监视器 (monitor)（这个词也指内部用条件变量让调用者睡眠等待资源的类）。代价：单线程或只被一个线程使用时开销是浪费；可重入调用有问题——线程安全的 A() 和 B() 不能互相调用。解法是可重入锁，或先实现「不安全」版本、外面包一层只负责进出临界区的线程安全版本，内部调用不安全版本。
作者观点：试图靠 100% 线程安全的类和接口来处理并发是坏主意，这会让接口过重，并鼓励程序员忽视自己身处并发环境。应正视并发，设计显式处理并发的数据结构和算法，目标是尽量减少线程间的争用、依赖和锁的使用。完全无锁很难做对，但朝少用锁的方向努力，远好于滥用锁去造「滴水不漏」的接口。

与其他来源的关系

UE5 任务系统文档记录了一个具体的死锁案例：旧的忙等待在等待时会执行别的任务，可能挑到反过来依赖当前等待任务的任务，在同一调用栈上形成无法解开的循环依赖；5.5 起改用超额订阅。这正是 GEA 所说的「循环等待」在任务系统中的表现。