死锁是多个并发进程（或者线程）竞争多个互斥资源时发生循环等待导致无限等待。

简单的说就是 进程A持有资源N，但即将使用资源M，进程B持有资源M但即将使用资源N，此时A会等待B释放M而陷入阻塞，B也在等待A释放N而陷入阻塞，因此AB会无限阻塞下去。其中M和N都是不可抢占的互斥资源。

 

- 对比死锁和饥饿

共同点：最终结果都是进程无法往下执行，进入无限等待的状态。

区别：死锁是由于进程竞争互斥资源形成循环等待导致的无限等待；饥饿是由于不公平算法导致一些进程一直能得到资源，另一些进程一直得不到资源而进入无限等待；

状态：死锁和饥饿都会一直得不到CPU（死锁的进程一定处于阻塞态，饥饿的进程处于阻塞态（得不到IO设备）或就绪态（得不到CPU））。

 

- 死锁发生的４个必要条件

互斥条件

对互斥资源竞争才会导致死锁（如哲学家的筷子、打印机等）。

 

请求并占有条件

进程占有至少一个其他进程要申请的资源，同时该进程又因为要请求另一个进程正在占用的资源而等待。

 

不可抢占条件

进程要申请的是不可抢占的资源。

 

循环等待条件

互相等待的进程关系成环。

 

 

- 死锁的预防

死锁预防指破坏死锁的4个必要条件使死锁不会发生。

 

破坏互斥条件

只需将互斥资源通过虚拟化技术改造为共享资源就可以破坏互斥条件。

例如：SPOOLing技术将独占设备在逻辑上改造成共享设备。

该策略的缺点：不是所有的资源都可以改造为共享资源。

 

破坏占有且请求条件

预分配资源，在进程开始执行之前就将其所需的全部资源都分配给它。

1. 难以实现，一个进程在执行前不可能知道它所需的全部资源，因为进程执行是动态的，不可预测的。

2. 资源利用率低，因为进程会全程占有多个资源，但进程并非执行的全程都在使用所有资源，可能某个过程执行用到资源A，某个过程用到资源B，这样一来这些资源就被浪费。

3. 降低并发性，进程需要全程占用它所需的所有资源，意味着期间其他需要某个资源的进程要等待。

 

破坏不可抢占条件

方案一：进程A请求新的资源得不到满足时（被阻塞），它立刻释放自己持有的所有资源，以后有机会在申请。

方案二：进程A请求新的资源得不到满足时，让操作系统帮忙将其他进程持有的资源强行剥夺给A。这种方式一般要考虑各进程的优先级。

 

该策略的缺点：

1.释放已获得的资源可能造成前一阶段工作失效。

2.反复申请和释放资源会增加系统开销（处理外设的中断），降低系统吞吐量，而且可能造成饥饿。

 

破坏循环等待条件

可以实行资源有序分配策略，也就是把所有资源指定一个从1开始递增的整型编号，所有进程要按序号递增的次序申请资源。进程A执行过程要用到资源r1和r3，那么A必须先申请r1在申请r3。

该方法可以有效破坏循环等待条件，可以用反证法证明。

缺点：

1、不方便增加新设备，增加需要重新编号；

2、按次序申请资源会增加开发成本；

3、为了遵循按编号申请的次序，暂不使用的资源也要提前申请（例如先用r3后用r1，进程就需要提前申请r1），增加了进程对资源的占用时间。

 

 

- 死锁的避免

死锁的避免是指操作系统根据算法得到分配给多个进程多个资源的最优顺序，使死锁不会发生。

 

安全序列

安全序列是指系统按照某种顺序分配资源，则每个进程都能成功申请资源，此时系统就是安全状态，不会发生死锁。如果找不到一个安全序列，则系统就处于不安全状态，意味着可能发生死锁。

 

银行家算法

银行家算法的核心思想是：在资源分配之前先判断本次分配是否会导致系统进入不安全状态（如果分配之后能找到一个安全序列则说明不会进入不安全状态），从而决定是否答应资源分配请求。

 

具体思路如下：

1. 将系统中所有的资源的数量表示为一个一维向量。

例如：计算机中有R0~R2 这3种资源，他们的数量分别是10, 5, 7。表示为向量(10, 5, 7)。

2. 将系统中所有在申请资源的进程对资源的总需求量、已分配量 和 还需要的量表示为一维向量。

如下所示：

3. 遍历所有进程的“还需要的资源量”的向量A，与总的剩余资源量的向量B((3,3,2))对比。如果找到一个 A

然后继续重复上述遍历过程，直到可以找到一个安全序列，此时系统分配资源给一开始的进程A；或者找不到一个安全序列，系统将回溯到上一步，继续步骤3。

其实银行家算法找安全序列，其本质是使用“回溯算法”来深度优先遍历决策树，找到决策树中任意一条可以到达叶子节点的路径。

甚至于系统还可以结合贪心算法进行优化，优先选择将资源分配给“还需要的资源量”最少，且“已分配的资源量（这些资源会归还给系统）”最多的进程。例如上图中，系统可以给P1和P3先分配资源，但是最好先给P3分配资源。

 

银行家算法例子

以这个图为例：

1、第一次遍历：检索到 P1 所需资源（1,2,2） 满足 系统剩余可用资源 (3,3,2)。将P1加入安全序列（不是真的把资源分配给P1）。 P1归还所有资源后，系统剩余可用资源为（5,3,2）。

安全序列为：{P1}

2、第二次遍历：检索到 P3 所需资源（0,1,1） 满足 系统剩余可用资源 (5,3,2)。将P3加入安全序列。 P3归还所有资源后，系统剩余可用资源为（7,4,3）。

安全序列为：{P1，P3}

3、第三到五次遍历：得到安全序列为{P1，P3，P0，P2，P4}

于是可以得到安全序列，因此系统会将资源分配给P1进程。

又例如，对于下面这个例子，是无法找到安全序列的，因此系统不会分配给他们任何资源，但它不一定会死锁，只是可能死锁。

 

 

 

 

- 死锁的检测和恢复

由于进程并发和随机不可预测的特性，通过预防的手段排除死锁是很困难的，会加大系统开销且不能充分利用资源（正如上面说的几种预防死锁的方法的缺点）。

死锁的检测和恢复指系统检测进程是否发生死锁，并且在发现死锁后通过外力破坏死锁。

死锁的检测依赖于资源分配图。

 

 

资源分配图

资源分配图用于描述资源在各个进程间分配的情况，图中有2种节点：Ｐ（代表进程的节点）和R（代表资源的节点）。

p(i)->r(j) 表示进程p(i)申请一个单位的r(j)资源，r(j)->p(i) 表示进程p(i)正占有一个单位的r(j)资源。

如图所示：

 

如果系统的某类资源只有一个单位（如一台打印机），称为单体资源类，反之就是多体资源类。

如果图的R节点都是单体资源的情况下，当图出现环则肯定死锁，且此时边的方向是同一方向（顺时针或逆时针）。

如果R节点存在多体资源且出现环，则可能发生死锁，但不确定。

如图：

 

1. 对单体资源的死锁检测

如果系统所有类型的资源都只有一个单位，可以使用“等待图”检测，它是从资源分配图去掉资源节点得到的。如下所示：

如果等待图成环则存在死锁。该算法检测环需要n^2数量级的操作，n是节点数，即进程数。

 

2. 对多体资源的死锁检测

以下面的资源分配图为例：

 

图中有两种边：分配边（绿色） 和 请求边（蓝色）。

逻辑如下：

1）在资源分配图中，找出既不阻塞又不是孤点的进程 Pi（如果一个进程的有 向边对应资源的申请数量小于等于系统中已有空闲资源数量，这个进程就是我们想要的Pi。如图中，R1没有空闲资源，R2有 一个空闲资源。若所有的连接该进程的边均满足上述条件，则这个进程能继续运行直至完成，然 后释放它所占有的所有资源）。消去它所有的请求边和分配变，使之变为孤立的结点。

在图中， P1 是满足这一条件的进程结点，于是将P1的所有边消去。

2）进程 Pi 所释放的资源，可以唤醒某些因等待这些资源而阻塞的进程，原来的阻塞进程可能变 为非阻塞进程，找到这样的进程（其实就是找资源节点的相邻节点，并按1)步骤验证该节点）。

在图中，P2 就满足这样的条件。

3）重复上述步骤，若能消 去图的所有边，则称该图是可完全简化的，则没有死锁。

 

该算法本质是一个图的拓扑排序的升级版，是一个图的广度优先算法。这就是死锁检测算法。

用一句话概括死锁检测算法：依次消除不阻塞进程的边，直到无边可消。

 

用死锁检测算法化简资源分配图后，还连着边的进程就是死锁进程。

 

检测死锁的频率会影响CPU运行进程的效率，因为死锁检测算法的复杂度较高，CPU必须分出一部分时间用于检测死锁。一种方法是每次有资源请求都做检测，这样可以第一时间发现是否出现死锁，但会占用大量CPU时间；另一种方法是定时检测，每个若干分钟查一次。

 

 

- 从死锁恢复

当检测算法发现死锁后，需要外力干预解脱死锁。主要有3个方式：抢占资源和杀死进程两种方式。

 

1. 通过抢占资源恢复

将一个死锁进程挂起暂时放到外存，把资源从某个死锁进程抢占并分给其他死锁进程。这取决于资源的属性是否支持中途暂停并转到其他任务。

 

2. 杀死进程

两种方法：杀死所有死锁进程，但这意味着所有这些进程的工作都要从头再来；一次终止一个进程直到解除死锁，这意味着每终止一个进程都要执行一次死锁检测算法。

 

选择对哪个死锁进程下手执行上面2种操作：

1.进程优先级

2.已经执行多长时间

3.进程还有多久完成

4.进程已经用了多少资源（优先对占用资源多的进程下手）

5.前台进程还是后台进程

 

- 活锁（死循环）

活锁是指一个或多个进程轮询的等待某个不可能为真的条件为真，导致其一直重复尝试并失败，失败在尝试的过程。活锁的出现往往是因为算法和程序编写的不合理造成的，也可能是人为的设置为死循环。

活锁状态相当于一直在忙等待，会一直消耗CPU时间使系统性能大大降低。

活锁是忙等待，进程在运行完时间片之前不会让出CPU；饥饿则是让出CPU并无限期的等待，处于阻塞队列中无法被唤醒。