死锁、活锁和饥饿

Pattern

---

死锁

又是一个老生常谈的问题，所谓死锁，自并发模式出现就伴随而生的老大难问题。

来自 wiki 的描述简洁易懂：当两个以上的运算单元，双方都在等待对方停止运行，以获取系统资源，但是没有一方提前退出时，就称为死锁。

先来回顾下发生死锁的四要素：

1. 互斥，资源不可共享
2. 持有与等待
3. 不可剥夺，不能强占别人的资源
4. 环路等待

死锁避免的几种思路：

顺序获取

死锁之所以会产生，其根本是因为有竞争资源的存在，这种避免死锁方法的思路就是打破 环路等待 ，其做法是这样的

把所有竞争资源列出来，按照一定的顺序排序（这个顺序本身不是要关注的重点），然后规定要获取资源的进程/线程必须按照顺序来获取，比如现有竞争资源

$$\begin{array}{cc} \mathrm{rs}\\ \hline \\ \mathrm{A} \\ \mathrm{B} \\ \mathrm{C} \\ \mathrm{D} \\ \mathrm{E} \\ \end{array}$$

规定资源获取顺序为 E -> A
有请求者需要获取资源 (B, D, E) 来处理请求，那么它必须按照 E -> D -> B 依次获取需要的资源，从而打破 环路等待

这种方法的缺点是你必须要罗列出所有的竞争资源（非独立资源）

超时处理

这种思路很简单，就是规定持有的资源的最大时间，超过这个时间就释放这个资源

银行家算法

此算法是一个著名的避免死锁算法，其核心思想概括下来就是在可满足的情况下一次性分配请求者所需全部资源并在结束时回收

$$\begin{array}{cc} \mathrm{} & \mathrm{A} & \mathrm{B} & \mathrm{C}\\ \hline \\ \mathrm{P_1} & 1 & 0 & 3 \\ \mathrm{P_2} & 0 & 4 & 2 \\ \mathrm{P_3} & 2 & 2 & 5 \\ \mathrm{P_4} & 1 & 1 & 1 \\ \mathrm{P_5} & 3 & 2 & 3 \\ \end{array}$$

（经典算法，就不展开详细解释了）
需要注意的是，你可能需要设置优先级队列来避免当一直有新的请求者进来时，可能会出现的饥饿进程出现

活锁

所谓活锁，简单描述来就是进程/线程处在活跃状态，但是却无法完成对自身任务的处理。
活锁的情况有很多种，比如在这样的一种情境下：线程 P1 和 P2 ，P1 拥有资源 A，P2 拥有资源 B，P1 请求资源 B 发现被锁于是释放 A，P2 请求资源 A 发现被锁于是释放 B，然后两个线程重复获取-释放的过程

还有其实无限 retry 也是活锁的一种，一个线程要执行一个任务，失败了 retry 然后重复这个过程。虽然线程处于活跃状态，但是却无法推进任务的完成

饥饿

饥饿是指一个线程所需的资源一直被强占，从而一直得不到执行的一种状态。
饥饿主要是由于资源调度分配不公导致的，解决方法可以考虑优先级队列、公平策略