死锁

• 死锁出现的原因
• 防止死锁的办法

6.1 资源

资源：需要排他性使用的对象。

6.1.1 可抢占资源和不可抢占资源

可抢占资源：可以从拥有它的进程中抢占而不会产生任何副作用。

不可抢占资源：指在不引起相关的计算失败的情况下，无法把它从占有他的进程处抢占过来。

死锁与不可抢占资源有关，有关可抢占资源的潜在死锁通常可以通过在进程之间重新分配资源而化解。是用一个资源所需要的事件顺序可以用抽象的形式表示如下：

• 请求资源
• 使用资源
• 获得资源

若请求时资源不可用，则请求进程被迫等待。在一些操作系统中，资源请求失败时进程会被自动阻塞，在资源可用时再唤醒它。在其他系统中，资源请求失败会返回一个错误代码，请求的进程会等待一段时间，然后重试。

6.1.2 资源获取

资源的三个步骤可以实现为信号量的down操作来获取资源，使用资源，最后使用up操作来释放资源。

如果进程需要两个以上的资源，通常都是连续获取。

如果只有一个进程，那么就没有必要慎重的使用资源，因为不存在资源竞争。考虑两个进程的情况，由于获取资源顺序的不确定，可能产生死锁：

6.2 死锁简介

死锁的规范定义：如果一个进程集合中的每个进程都在等待只能由该进程集合中的其他进程才能引发的事件，那么，该进程集合就是死锁的。

在大多数情况下，每个进程等待的事件是释放进程集合中其他进程所占有的资源。这种死锁是资源死锁。这是常见的类型，但不是唯一的类型。

6.2.1 资源死锁的条件

发生资源死锁的4个必要条件：

• 互斥条件。每个资源要么分配给了一个进程，要么就是可用的。
• 占有和等待条件。已经得到某个资源的进程可以再请求新的资源。
• 不可抢占条件。已经分配给一个进程的资源不能强制性的被抢占，只能被占有他的进程显式的释放
• 环路等待条件。死锁发生时，系统中一定有两个或者两个以上的进程组成的一条换路，该环路中的每个进程都在等待着下一个进程占有的资源。

死锁发生时，上述四个条件一定是都满足的。如果任何一个条件不成立，死锁就不会发生。

6.2.2 死锁建模

资源分配图是基于上述四个条件的模型的。有向图中有两类结点：

• 圆形：进程
• 方形：资源
• 资源指向进程的有向边：资源已经被请求、授权并被进程占用
• 进程指向资源的有向边：进程正在请求该资源

按照进程的次序执行不会引起死锁，但是程序也没有任何的并行性。进程在执行的过程中，不仅要请求和释放资源，还要做计算或者输入输出的工作。

资源分配图可以作为一种分析工具，考察对一个给定的请求/释放的序列是否会引起死锁。

有四种处理死锁的策略：

• 忽略该问题

• 检测死锁并恢复。

  让死锁发生，检测他们是否发生，一旦发生死锁，采取行动解决问题

• 仔细对资源进行分配，动态避免死锁

• 通过破坏引起死锁的4个条件之一，就能防止死锁的发生

6.3 鸵鸟算法

大多数的工程师不会以性能损失和可用性的代价去防止死锁。

6.4 死锁检测和死锁恢复

使用这种技术时，系统并不试图阻止死锁的发生，而是允许死锁发生，当检测到死锁发生后，采取措施进行恢复。

• 检测死锁的方法
• 恢复的方法

6.4.1 每种类型一个资源的死锁检测

从最简单的例子开始，每种资源类型只有一个资源。这样的系统可能有扫描仪、蓝光光盘刻录机、绘图仪和磁带机，但每种设备都不超过一个，即排除了同时有两台打印机的情况。

6.4.1.1 检测方法：资源分配图

对于每种类型只有一个资源的系统可以构造一张资源分配图。如果这张图包含了一个或者一个以上的环，那么死锁都存在；反之，不存在死锁。

检测有无环的方法：【深搜+数组】

6.4.2 每种类型多个资源的死锁检测

基于矩阵的运算来检测从$P_1$到$P_n$这$n$个进程中的死锁。假设资源的类型数量是$m$，$E_1$代表资源类型1，$E_2$代表资源类型2，$E_i$代表资源类型$i(1\le i\le m)$。

这些数据之间有一个恒等公式：
$$E_j=\sum _{i=1}^n{C}_{ij}+A_{ij}$$
换言之，如果将所有已经分配资源j的数量加起来再和所有可供使用的资源数相加，结果就是该类资源的总数。

死锁检测算法就是基于向量的比较。

6.4.3 从死锁恢复

6.4.3.1 利用抢占恢复

某些情况下可能会临时将某个资源从它的当前所有者那里转移到另一个进程。许多情况下，尤其是对运行在大型处理机上的批处理系统来说，需要人工进行干预。

在不通知原进程的情况下，将资源从一个进程取走给另一个进程使用，接着又送回，这种做法取决于资源本身的特性。

6.4.3.2 利用回滚恢复

若系统设计人员了解到死锁可能发生，那么可以周期性对进程进行检查点检查（checkpoint）。将进程复位到一个更早的状态，这个时候它还没有取得所需的资源，接着把进程分配给死锁进程。若复位后的进程试图重新获得对资源的控制，他必须一直等待到该资源可用为止。

6.4.3.3 通过杀死进程恢复

最简单最直接的方法：杀死一个或者多个进程。

杀死环中的一个进程。如果不行的话，那么继续杀死别的进程直到打破死锁。

但是中途杀死进程并非总是安全的。

6.5 死锁避免

是否存在算法总能对分配资源是否安全做出判断。

6.5.1 资源轨迹图

系统一旦进入$I_1$、$I_2$、$I_5$和$I_6$组成的矩形区域，那么最后一定会到达$I_2$和$I_6$的交叉点，此时产生死锁。

6.5.2 安全状态和不安全状态

安全状态：

• 没有死锁发生
• 并且即使所有进程突然请求对资源的最大需求

也仍然存在某种调度次序能够使得每一个进程运行完毕，那么该状态是安全的。

EXAMPLE：资源总数为10，现有7个资源已经分配，还有3个资源空闲。

下图(a)为安全状态

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-0JpsLBGw-1662600920744)(https://cdn.jsdelivr.net/gh/Holmes233666/blogImage@main/img/image-20220906231346519.png)]

下图(b)为不安全状态：

6.5.3 单个资源的银行家算法

Dijkstra提出了一种能够避免死锁的调度算法，称为银行家算法。

算法：判断对请求的满足是否会导致进入不安全状态。如果是，就拒绝请求；如果满足了请求系统仍是安全的，那么予以分配。

不安全状态不一定是死锁的。

6.5.4 多个资源的银行家算法

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-0bseFeuz-1662600920745)(https://cdn.jsdelivr.net/gh/Holmes233666/blogImage@main/img/image-20220906234513822.png)]

6.6 死锁预防

死锁避免从本质上来说是不可能的，因为它需要获知未来的请求，而这些请求是不可知的。

实际避免死锁，保证四个条件中至少有一个不成立。

6.6.1 破坏互斥条件

如果资源不被一个进程独占，那么不会死锁。

Example：打印机的守护进程的例子。

6.6.2 破坏占有并等待的条件

禁止已经持有资源的进程再等待其他资源便可以消除死锁。

一种实现方法是规定所有进程在开始执行前请求所需的全部资源。如果所需的全部资源可用，那么就分配给这个进程，于是该进程肯定能够运行结束。如果有一个或者多个资源正在被使用，那么不进行分配，进程等待。

问题：

• 很多进程到运行时才会知道它需要多少资源，且如果已知，可以使用银行家算法
• 资源利用率不是最高的

另一种方案是，当一个进程请求资源时，先暂时释放其当前的占用的资源，然后再尝试一次获得所需的全部资源。

6.6.3 破坏不可抢占条件

对资源进行虚拟化。

EXAMPLE：打印机守护进程

6.6.4 破坏环路等待条件

消除环路等待的办法：

• 保证每一个进程在任何时刻只能占用一个资源，如果要申请另一个资源，它必须先释放第一个资源
• 将所有资源统一编号；进程可以在任何时刻提出资源请求，但是所有的请求必须按照资源编号的顺序（升序）提出

但是，基本找不出一种有效的顺序。

6.7 其他问题

6.7.1 两阶段锁

两阶段锁：第一阶段试图对所有的记录加锁。第二个阶段：释放锁。

6.7.2 通信死锁

资源死锁是最普遍的一种类型，但是不是唯一的一种。另一种死锁发生在通信网络中：ACK丢失

解决的方案是超时策略

6.7.3 活锁

某些情况下：进程意识到他不能获得所需的下一个锁时，会释放目前已有的锁。这个过程中并没有进程阻塞，然而进程并不会往下执行，可以称为活锁。

6.7.4 饥饿

定义：在动态运行的系统中，在任何时刻都可能会有请求资源的情况。这就需要一些策略来决定什么时候谁获得什么资源。虽然这个策略在表面上很有道理，但是依然有可能会有一些进程永远得不到服务，虽然他们并不是死锁进程。