死锁

## 什么是死锁

在两个或者多个并发进程中，**每个进程持有某种资源而又等待其它进程释放他们现在保持着的资源，在未改变这种状态之前都不能向前推进**，称这一组进程产生了死锁。

> 假设有线程 $A$ 与线程 $B$ 分别运行下面的 :point_down: 代码片段 `proc_A` 与 `proc_B`，这两个线程共享两把 **全局** 的互斥锁 $A$ 与 $B$。
>
> 线程 $A$ 先尝试获取锁 $A$，再尝试获取锁 $B$；而线程 $B$ 刚好相反。
>
> 假设在 $t_0$ 时刻，线程 $A$ 获取了锁 $A$，将要尝试获取锁 $B$；而线程 $B$ 刚好也获取了锁 $B$，等待获取锁 $A$。
>
> 但是由于两个线程都持有对方想要获取的锁，因此这两个线程都不能进入临界区继续执行，这种 **互相等待** 的僵持状态 :recycle: 我们称之为 **死锁** :lock:。
>
> ~~~c++
> void proc_A(void)
> {
> lock(A);
> lock(B);	// t0 时刻
> unlock(B);	// 临界区
> unlock(A);
> }
> 
> void proc_B(void)
> {
> lock(B);
> lock(A);	// t0 时刻
> unlock(A);	// 临界区
> unlock(B);
> }
> ~~~
>
>

## 死锁产生的必要条件

1. **互斥条件：** 一个资源每次只能被一个进程使用，即在**一段时间内某资源仅为一个进程所使用**，此时**如果有其它进程请求该资源**，则**请求进程只能等待**。
2. **请求与保持条件：** 进程中**已经保持了至少一个资源**，但**又提出新的资源请求**，而**该资源已经被其它进程占有**，此时**请求进程被阻塞**，但**对自己已经获得的资源保持不放**。
3. **不可剥夺条件：** 进程**未使用完的资源在未使用完毕之前**，**不能被其它进程强行夺走**，即**只能由获得该资源的进程自己来释放**。
4. **循环等待条件：** 若干进程间形成**首尾相接循环等待资源**的关系，在发生死锁时必然存在一个进程等待队列 $\{P_1,P_2,...,P_n\}$，其中 $P_1$ 等待 $P_2$ 占有的资源，$P_2$ 等待 $P_3$ 占有的资源，...，$P_n$ 等待 $P_1$ 占有的资源，形成一个进程等待环路，环路中**每一个进程所占有的资源同时被另一个申请**。

> :warning: 注意：
>
> 1. 上面的四个条件是死锁的**必要条件**，**只要发生死锁**，**这些条件必然成立**。
> 2. 但**只要**上述条件**有一条不满足**，**就不会发生死锁**。

## 死锁的处理方法

### 鸵鸟策略

1. 直接**忽略死锁**，因为**解决死锁问题的代价很高**，因此鸵鸟策略这种不采取任何措施的方案会**获得更高的性能**。
2. 当发生死锁时**不会对用户造成多大影响**，或**发生死锁的概率很低**，**可以采用鸵鸟策略**。

> :information_desk_person: 鸵鸟策略是指**当鸵鸟看到危险的时候，就把头埋在沙子里，装作看不到**。

### 死锁预防

> :information_desk_person: 死锁预防是通过设计合理的资源分配算法，从 **源头** 上预防死锁。

死锁预防的基本思想是**破坏形成死锁的四个必要条件**。

1. **破坏互斥条件：** 允许某些资源同时被多个进程访问，但是有些资源本身并不具备这种属性，因此这种方案实用性有限。

> * **只读数据文件**、**磁盘**等**软硬件资源**均**可采用这种办法管理**。
   > * **可写文件**、**键盘**等**独占性资源只能互斥的占有**，**不能采用这种办法管理**。

2. **破坏请求与保持条件：**

1. **实现资源预分配策略**，当一个进程**开始运行之前**，必须**一次性向系统申请他所需要的全部资源**，否则不运行。
   2. 这种方式的**缺点：**
      1. 很多时候**无法预知一个进程所需的全部资源**。
      2. 会**降低资源利用率**，**降低系统的并发性**，因为在每个进程占有的资源中，有些资源在**运行后期使用**，有些资源在**例外情况下使用**，所以可能造成进程**占有一些几乎用不到的资源**，而使**其它想使用这些资源的进程等待**。

3. **破坏不可剥夺条件：** 剥夺调度能够**防止死锁**，但是**只适用于内存和处理器资源**。

1. **占有资源的进程**若要**申请新资源**，必须**主动释放已占有资源**，若**需要此资源**，应该**向系统重新申请**。
   2. 资源分配管理程序**为进程分配新资源**时，**若有则分配**，**否则**将**剥夺此进程已占有的全部资源**，并**让进程进入等待资源状态**，**资源充足后再唤醒它重新申请所需的资源**。

4. **破坏循环等待条件：**

1. 给系统的**所有资源编号**，规定进程**请求所需资源的顺序必须按照资源的编号依次进行**。
      1. 一个进程得到某一层的资源后，只能申请较高一层的资源。
      2. 当进程释放某一层的资源时，必须先释放所占有的较高层的资源。
      3. 当进程获得某层的一个资源时，如果想申请同层的另一个资源，必须先释放此层中已占有的资源。

### 死锁避免

#### 什么是死锁避免

> :information_desk_person: 死锁避免是通过在系统运行时 **跟踪资源分配过程** 来避免出现死锁。

1. 动态地检测资源分配状态，以确保系统处于 **安全状态**，只有处于安全状态时才会进行资源的分配。

> :thinking: 什么是 **安全状态** 与 **非安全状态**？
>
> - **安全状态**：
>   - 安全状态是指系统中存在 **至少一个** :point_up: 安全序列 $\{ T_1, T_2, ..., T_n \}$，如果系统按照这个序列调度线程执行，即可避免资源不足的情况发生。
>   - 在这种系统中，每一次线程需要获取资源时，系统就会找到这个序列，并按照这个序列继续推进。
>   - 死锁避免算法就是让系统在 **每一次分配资源后都处于安全状态** :thumbsup: ，如果分配之后不能处于安全状态，则不分配资源给线程 :open_mouth:。
> - **非安全状态**：
>   - 如果系统中不存在上面提到的 :point_up_2: 安全序列，则称之为非安全状态。
>   - 在非安全状态下，系统一定找不到一种分配资源的顺序，让所有线程都得到满足，因此 **必定** 会产生死锁 :lock: 。

#### 银行家算法

1. [银行家算法](https://en.wikipedia.org/wiki/Banker%27s_algorithm) 是一种具体的死锁避免算法，由 [Edsger Dijkstra](https://en.wikipedia.org/wiki/Edsger_W._Dijkstra) 提出，该算法通过 **模拟** 分配资源后的状态，来判断在分配某个资源后系统是否还处于安全状态。

2. 为了描述系统中的供给 / 需求关系，银行家算法使用了一系列数据结构来保存这些关系，假设我们的系统中存在 $M$ 类资源，而线程有 $N$ 个，则这些数据结构为以下四种：

1. **全局可利用资源**：`Available[M]`，该数组代表某一时刻系统中每一类元素的可用个数，这个数组在初始化时被设置为系统中拥有的 $M$ 类资源的 **总量**。
   2. **每个线程的最大需求量**：`Max[N][M]`，该矩阵包含所有 $N$ 个线程对 $M$ 类资源的**最大需求量**。
   3. **已分配资源数量**：`Allocation[N][M]`，该矩阵包含 **已经分配** 给所有 $N$ 个线程的 $M$ 类资源的数量。
   4. **还需要的资源数量**：`Need[N][M]`，该矩阵包含所有 $N$ 个线程对 $M$ 类资源 **还需要** 的资源数量。

3. 此外，我们还需要保证以下前提，银行家算法才能正确工作：

1. 系统中的 **供给关系** 必须是 **固定** 的，比如系统中的资源类别数 $M$、线程总数 $N$、整个系统中 $M$ 类资源的可用数量，以及每个线程所需要的不同种类资源的数量都是固定的。
   2. 任意线程对任意资源的最大需求量 **不能超过** 系统的资源总量。
   3. 线程在获得了其需要的所有资源之后，能够在 **有限时间** 内完成工作，并且 **释放** 已经获得的资源。

4. 对于满足这些前提的系统，我们可以利用银行家算法保证该系统一直处于安全状态，正如之前所述，银行家算法的核心是模拟分配某个资源之后，检察系统是否还处于安全状态，从而保证系统能够始终处于安全状态，这个检查算法被称为 **安全性检查算法**，其执行流程如下：

1. 创建一个临时数组 `Available_sim`，其初始值与数组 `Available` 一致，用于记录在接下来的模拟执行中系统可用资源数量。
   2. 找到系统当前剩余资源能够满足的线程，即找到一个线程 $x$，对于 `Available_sim` 中任意成员 $m$，都满足 `Available[m] >= Need[x][m]`，如果无法找到这样的线程，则代表系统处于 **非安全状态**。

5. 下面我们结合一个具体例子来详细描述安全性检查算法的具体执行过程：

1. 假设系统中一共有 $T_1$、$T_2$、$T_3$ 三个线程，他们均需要 $A$、$B$ 这两类资源，在某一个时刻，银行家算法中各个数据结构的状态如下图所示，此时我们执行安全性检查算法，检查在该时刻系统是否是安全的，安全性检查算法首先找到当前可以 **满足需求** 的线程，并假设将资源 **全部分配** 给该线程，在这个例子中，我们发现该时刻可以满足需求的线程为 $T_2$，因此假设满足 $T_2$ 的需求，$T_2$ 应当拿到资源并在有限时间内执行完成，然后释放自己已经拥有的资源。

![image-20220721210902105](https://notebook.ricear.com/media/202207/2022-07-21_210904_8750260.5895362226090322.png)

2. 此时系统的状态如下图所示，对比上图可以发现，除了将 $T_2$ 的 **需求清除** 之外，$T_2$ 还 **释放** 了自己的资源，并且将该资源 **放到了 `Available` 中**。

![image-20220721211312940](https://notebook.ricear.com/media/202207/2022-07-21_211315_2772730.025036486317489892.png)

3. 此时 $T_1$ 的请求可以得到满足，同理我们进一步假设将资源分配给 $T_1$，并在他执行完成后释放其已经分配的资源，在 $T_1$ 执行 结束后，$A$ 与 $B$ 全局可用的资源数量分别为 $ 3 + 2 = 5 $ 与 $ 2 + 8  = 10 $，而这刚好可以满足 $T_3$ 的需求，让 $T_3$ 能够顺利执行。

4. 因此，我们可以得到一个安全序列 $\{ T_2, T_1, T_3 \}$，该序列能够让系统顺利运行完所有的线程，其表明该系统处于安全状态。

> :information_desk_person: 银行家算法就是在 **每次** 分配给线程新的资源时都进行安全性检查，保证这次分配不会导致系统进入非安全状态。例如在上面的 :point_up_2: 例子中，假设此时 $T_1$ 发出请求申请资源 $A$，申请数量为 1，虽然剩余的资源数量大于这个请求，但是若将 $A$ 资源分配给 $T_1$，系统将无法找到一个可以满足的线程，因此会处于 **非安全状态**。此时，系统会安排 $T_1$ **等待**，直到其他线程（如 $T_2$）顺利获取了资源并释放了其占有的资源时才再次进行安全性检查，只有在安全性检查通过 :white_check_mark: 之后，线程的请求才能够得到满足。

> :thinking: 针对我们前面提到的产生死锁的例子中，我们该如何使用死锁避免算法来消除死锁呢？
   >
   > 我们可以把代码片段中的锁 $A$ 与 锁 $B$ 都当成仅有 1 份的资源，而线程 $A$ 与线程 $B$ 都需要获取锁 $A$ 与锁 $B$：
   >
   > - 如果线程 $A$ 先获取其中的锁 $A$，此时线程 $B$ 向系统申请锁 $B$，系统就会检查如果把锁 $B$ 分配给线程 $B$，是否会导致系统处于非安全状态 🫠。
   > - 显然，如果此时分配给线程 $B$，那么系统将无法找到一个安全序列 ❌ 。
   > - 因而系统不会立刻将锁 $B$ 分配给线程 $B$，而是待线程 $A$ 结束执行后才分配，避免了死锁的产生 :white_check_mark: 。

### 死锁检测与死锁恢复

#### 死锁检测

> :information_desk_person: **循环等待** 是检测死锁的关键 :key:。

1. 为了确认系统中是否存在循环等待，需要获取系统中 **资源分配** 与 **线程等待** 的相关信息。

2. 系统通过两个表来记录这些数据（**资源分配表** 与 **线程等待表**）：

![image-20220721215029984](https://notebook.ricear.com/media/202207/2022-07-21_215032_5464010.8898017844357492.png)

1. 如上图所示 :point_up_2:，假设现在有四个线程 $T_1 \sim T_4$，而他们之间共享三个资源 $O_1 \sim O_3$。
   2. 资源分配表记录着当前不同资源被 **占有** 的情况，而线程等待表记录着线程 **等待** 不同资源的情况，根据这两张表，可以画出上面左边的图：
      1. 其中从资源指向线程的 **实线** 箭头 :arrow_right: 代表该线程占有该资源，而从线程指向资源的 **虚线** 箭头 :link: 代表该线程等待着该资源。
      2. 对于其中的任意一个 **资源**，指向其的虚线箭头与从其指出的实线箭头构成了 **一对** 线程间的等待关系，如对于资源 $O_1$，他有从 $T_4$ 与 $T_2$ 指向其的虚线箭头，也有指向 $T_1$ 的实线箭头，因此 $T_4$ 与 $T_1$、$T_2$ 与 $T_1$ 均构成了等待关系。
   3. 在图中如果出现了 **环**，就代表出现了 **循环等待**，在上图中，线程 $T_1$、$T_3$、$T_4$之间就形成了这样的一个环，出现了循环等待，因此我们可以判断此时出现了 **死锁** :lock:。

> :thinking: 操作系统应该何时开始做死锁检测呢？
>
> 1. 从我们介绍的算法可以发现，检测死锁并不是一个轻松的工作，操作系统需要构建一个十分复杂的图并在其中寻找环，因此频繁的死锁检测会造成严重的 **性能开销**。
> 2. 操作系统往往选用更加 **被动** 的策略来触发死锁检测，避免暴露巨大的开销在关键路径上，以减少其对正常执行时应用程序性能的影响，其通常选用的策略有：
>    1. **定时监测** :alarm_clock: ：如每运行 24 小时检测一次。
>    2. **超时等待检测** :timer_clock: ：等待在某资源上超过一个限定的时间就检测一次。

#### 死锁恢复

1. **死锁剥夺法**： 
   1. 找到这个环中 **任意** 的线程作为受害者，直接 **终止** :stop_sign: 该线程并 **释放** :outbox_tray: 其占有的资源。
   2. 如果由于分配 / 等待关系过于复杂，在终止一个线程后依旧成环，就继续选择下一个线程并释放其占有的资源。
   3. 通过一步步终止环中的线程，可以打破循环等待，恢复正常运行 :thumbsup:。

2. **进程回退法：** 
   1. 根据系统保存的**检查点**让**所有的进程回退**，直到**足已解除死锁**，这种措施要求系统**建立保存检查点、回退及重启机制**。
   2. 由于死锁的出现往往是由于 **特定的调度** 和 **触发时机** 而导致的，再次运行很大概率不会出发死锁。

3. **进程撤销法：**
   1. **撤销陷入死锁的所有进程**，**解除死锁，继续运行**。
   2. **逐个撤销陷入死锁的进程**，**回收其资源并重新分配**，**直至死锁解除**。
   3. 可选择符合下面条件之一的先撤销：
      1. **CPU消耗时间最少**者。
      2. 产生的**输出量最小**者。
      3. **预计剩余执行时间最长**者。
      4. **分得的资源数量最少**者。
      5. **优先级最低**者。
4. **系统重启法：** 结束所有进程的执行并**重新启动操作系统**，这种**方法很简单**，但先前的工作全部作废，**损失很大**。

## 参考文献

1. 《现代操作系统：原理与实现》
2. [什么是死锁？](https://github.com/wolverinn/Waking-Up/blob/master/Operating%20Systems.md#%E4%BB%80%E4%B9%88%E6%98%AF%E6%AD%BB%E9%94%81)
3. [死锁概念，死锁产生的四个必要条件，如何避免和预防死锁](https://blog.csdn.net/ZWE7616175/article/details/79881236)。
4. [计算机操作系统 - 死锁](https://github.com/CyC2018/CS-Notes/blob/master/notes/%E8%AE%A1%E7%AE%97%E6%9C%BA%E6%93%8D%E4%BD%9C%E7%B3%BB%E7%BB%9F%20-%20%E6%AD%BB%E9%94%81.md)。
5. [死锁的产生、防止、避免、检测和解除](https://zhuanlan.zhihu.com/p/61221667)。