**

现代操作系统笔记——死锁

**

笔记以cyc2018大佬的github地址为大纲，以《现代操作系统》为基础进行摘抄总结。

1.相关概念

（1）资源：某类需要排他性使用的对象，可以是硬件设备也可以是一组信息。通俗的来说，资源就是随着时间放入推移，必须能获得、使用以及释放的任何东西。
（2）资源分为两类：可抢占的和不可抢占的。
–可抢占资源：可以从拥有它的进程中抢占而不会产生任何副作用， 例如存储器。
–不可抢占资源：指在不引起相关的计算失败的情况下，无法把它从占有它的进程处抢占过来。例如：蓝光光盘刻录机。
**注意：****总的来说：死锁与不可抢占资源有关。**因为有关可抢占资源的死锁通常可以通过在进程之间重新分配资源而化解。
（3）死锁的规范定义：如果一个进程集合中的每个进程都在等待只能由该进程集合中的其他进程才能引发的事件，那么，该进程集合就是死锁。
（4）资源死锁：大多数情况下，每个进程所等待的事件是释放进程集合中其他进程所占有的资源。此类死锁称之为资源死锁。它不是唯一的一种死锁，却是最常见的一种。之后的介绍也都是围绕着它展开的。

2.（资源）死锁发生的四个必要条件：

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

3.死锁建模

可用有向图建立资源分配图。在有向图中有两类节点：用圆形表示进程，用方形表示资源。
从资源节点指向进程节点表示该资源已经被请求、授权并被进程占用。
从进程节点指向资源节点则表示当前节点正在请求该资源，并且该进程已经被阻塞，处于等待该资源的状态。

a)占有一个资源 b)请求一个资源 c)死锁

4.四种处理死锁的策略方法

–忽略该问题。——鸵鸟算法
–死锁检测和死锁恢复
–死锁避免
–死锁预防
（1）鸵鸟算法
把头埋在沙子里，假装根本没发生问题。
因为解决死锁问题的代价很高，因此鸵鸟策略这种不采取任务措施 的方案会获得更高的性能。当发生死锁时不会对用户造成多大影响，或发生死锁的概率很低，可以采用鸵鸟策略。
大多数操作系统，包括 Unix，Linux 和 Windows，处理死锁问题的办法仅仅是忽略它。
（2）死锁检测
系统并不试图阻止死锁的产生，而是当检测到死锁发生时，采取措施进行恢复。
–每种类型一个资源的死锁检测

在一张资源分配图中，如果图中包含了一个或者一个以上的环，那么死锁就存在。在此环中的任何一个进程就都是死锁进程。如果没有这样的环，系统就没有发生死锁。
图 a 可以抽取出环，如图 b，它满足了环路等待条件，因此会发生死锁。
每种类型一个资源的死锁检测算法是：通过检测有向图是否存在环来实现，依次将每一个节点作为一棵树的根节点，并进行深度优先搜索，对访问过的节点进行标记，如果访问了已经标记的节点，就表示有向图存在环，也就是检测到死锁的发生。
–每种类型多个资源的死锁检测
如果有多种相同的资源存在，就采用一种基于矩阵的算法来检测死锁。

上图中，有三个进程四个资源，每个数据代表的含义如下：

E 向量：资源总量
A 向量：资源剩余量
C 矩阵：每个进程所拥有的资源数量，每一行都代表一个进程拥有资源的数量
R 矩阵：每个进程请求的资源数量
进程 P1 和 P2 所请求的资源都得不到满足，只有进程 P3 可以，让 P3 执行，之后释放 P3 拥有的资源，此时 A = (2 2 2 0)。P2 可以执行，执行后释放 P2 拥有的资源，A = (4 2 2 1) 。P1 也可以执行。所有进程都可以顺利执行，没有死锁。

算法总结如下：

每个进程最开始时都不被标记，执行过程有可能被标记。当算法结束时，任何没有被标记的进程都是死锁进程。

寻找一个没有标记的进程 Pi，它所请求的资源小于等于 A。
如果找到了这样一个进程，那么将 C 矩阵的第 i 行向量加到 A 中，标记该进程，并转回 1。
如果没有这样一个进程，算法终止。
（3）死锁恢复
–利用抢占恢复
–利用回滚恢复
将进程复位到一个更早的状态，那时它还没取得所需的资源，接着就把这个资源分配给一个死锁进程。如果复位后的进程试图重新获得对该资源的控制，它就必须一直等到该资源可用时为止。
–通过杀死进程恢复
一共有两种方法。
法1：杀掉环中的一个进程。如果这样做行不通的话，就需要继续杀死别的进程直到打破死锁为止。
法2：选一个环外的进程作为牺牲品以释放该进程的资源。应该选择正好持有环中某些进程所需资源的进程，最好杀死可以从头重新运行而且不会带来副作用的进程。如编译进程。
（4）死锁避免
—安全状态
图 a 的第二列 Has 表示已拥有的资源数，第三列 Max 表示总共需要的资源数，Free 表示还有可以使用的资源数。从图 a 开始出发，先让 B 拥有所需的所有资源（图 b），运行结束后释放 B，此时 Free 变为 5（图 c）；接着以同样的方式运行 C 和 A，使得所有进程都能成功运行，因此可以称图 a 所示的状态时安全的。

**安全状态定义：**如果没有死锁发生，并且即使所有进程突然请求对资源的最大需求，也仍然存在某种调度次序能够使得每一个进程运行完毕，则称该状态是安全的。
注意：不安全状态并不一定引起死锁。

安全状态的检测与死锁的检测类似，因为安全状态必须要求不能发生死锁。下面的银行家算法与死锁检测算法非常类似，可以结合着做参考对比。
—单个资源的银行家算法
一个小城镇的银行家，他向一群客户分别承诺了一定的贷款额度，算法要做的是判断对请求的满足是否会进入不安全状态，如果是，就拒绝请求；否则予以分配。

上图 c 为不安全状态，因此算法会拒绝之前的请求，从而避免进入图 c 中的状态。
—多个资源的银行家算法

上图中有五个进程，四个资源。左边的图表示已经分配的资源，右边的图表示还需要分配的资源。最右边的 E、P 以及 A 分别表示：总资源、已分配资源以及可用资源，注意这三个为向量，而不是具体数值，例如 A=(1020)，表示 4 个资源分别还剩下 1/0/2/0。

检查一个状态是否安全的算法如下：

查找右边的矩阵是否存在一行小于等于向量 A。如果不存在这样的行，那么系统将会发生死锁，状态是不安全的。
假若找到这样一行，将该进程标记为终止，并将其已分配资源加到 A 中。
重复以上两步，直到所有进程都标记为终止，则状态时安全的。
如果一个状态不是安全的，需要拒绝进入这个状态。
在实际中，只有极少的系统使用银行家算法来避免死锁，，因为很少有进程能够在运行前就知道其所需资源的最大值，而且进程数往往也是变化的。
使用银行家算法之类的启发式算法：当缓冲区利用率达到70%以上时，网络会实现自动节流，此时网络预计剩余的30%就足够用户完成任务并返回资源。
（5）死锁预防
在程序运行之前破坏死锁产生的四个条件。
1. 破坏互斥条件
例如假脱机打印机技术允许若干个进程同时输出，唯一真正请求物理打 印机的进程是打印机守护进程。
2. 破坏占有和等待条件
一种实现方式是规定所有进程在开始执行前请求所需要的全部资源。
一种实现方式是当一个进程请求资源时，先暂时释放其当前占用的所有资源，然后在尝试一次获得所需的全部资源。
3. 破坏不可抢占条件
4. 破坏环路等待
（1）给资源统一编号，进程只能按编号顺序来请求资源。
（2）保证每一个进程在任何时刻只能占用一个资源，如果要请求另外一个资源，它必须先释放第一个资源

5.其他问题

（1）两阶段加锁
在很多数据库系统中，一个经常发生的操作是请求锁住一些记录，然后更新所有锁住的记录。当同时有多个进程进行的时候就有出现死锁的危险。
这时候最常用的就是两阶段加锁。
在第一阶段，进程试图对所有所需的记录进行加锁，一次锁一个记录。如果第一阶段加锁成功，就开始第二阶段，完成更新然后释放锁。在第一阶段并没有做实际的工作。
如果在第一阶段某个进程需要的记录已经被加锁，那么该进程释放它所用加锁的记录，然后重新开始第一阶段。
（2）活锁与饥饿
活锁和死锁的问题有些相似，那就是他可以停止所有的转发进程，但是二者的技术不同，由于活锁包含了一些实际上并没有锁住的进程，因此可以通过先来先服务的分配策略来避免饥饿。