死锁

发表于 2019-06-08 分类于技术，操作系统，进程管理阅读次数：本文字数： 3.6k 阅读时长 ≈ 3 分钟

死锁的定义

在多道程序系统中，由于多个进程的并发执行，改善了系统资源的利用率并提高了系统的处理能力。然而，多个进程的并发执行也带来了新的问题——死锁。所谓死锁是指多个进程因竞争资源而造成的一种僵局（互相等待），若无外力作用，这些进程都将无法向前推进。

先看生活中的一个实例，在一条河上有一座桥，桥面很窄，只能容纳一辆汽车通行。如果有两辆汽车分别从桥的左右两端驶上该桥，则会出现下述的冲突情况。此时，左边的汽车占有了桥面左边的一段，要想过桥还需等待右边的汽车让出桥面右边的一段；右边的汽车占有了桥面右边的一段，要想过桥还需等待左边的汽车让出桥面左边的一段。此时，若左右两边的汽车都只能向前行驶，则两辆汽车都无法过桥。
在计算机系统中也存在类似的情况。例如，某计算机系统中只有一台打印机和一台输入设备，进程P1正占用输入设备，同时又提出使用打印机的请求，但此时打印机正被进程P2 所占用，而P2在未释放打印机之前，又提出请求使用正被P1占用着的输入设备。这样两个进程相互无休止地等待下去，均无法继续执行，此时两个进程陷入死锁状态。

产生死锁的四大必要条件

①资源互斥/资源不共享
每个资源要么已经分配给了一个进程，要么是可用的，只有这两种状态，资源不可以被共享使用，所以所谓的互斥是指：资源不共享，如果被使用，只能被一个进程使用。

②占有和等待/请求并保持
已经得到资源的进程还能继续请求新的资源，所以个人觉得叫占有并请求也许更好理解。

③资源不可剥夺
当一个资源分配给了一个进程后，其它需要该资源的进程不能强制性获得该资源，除非该资源的当前占有者显示地释放该资源。

④环路等待
死锁发生时，系统中一定有由两个或两个以上的进程组成的一条环路，环路上的每个进程都在等待下一个进程所占有的资源。

解决死锁的方法

预防死锁（破坏产生死锁的条件）
避免死锁（银行家算法）
检测死锁（资源分配图）
解除死锁

第三条与第四条一般联合使用

防止死锁的方法

①防止死锁的发生只需破坏死锁产生的四个必要条件之一即可。
②下面的方法开销非常之大，目前没有一个操作系统可以实现。
③因此，目前使用的方法是避免死锁，而不是防止死锁。
④这部分的内容大致浏览简单了解一遍即可，只要能在某些选择题中判断出选项对应的是下面四个方法中的哪个就可以了。

破坏互斥条件

方法：如果允许系统资源都能共享使用，则系统不会进入死锁状态。
缺点：有些资源根本不能同时访问，如打印机等临界资源只能互斥使用。所以，破坏互斥条件而预防死锁的方法不太可行，而且在有的场合应该保护这种互斥性。

破坏请求并保持条件

方法：釆用预先静态分配方法，即进程在运行前一次申请完它所需要的全部资源，在它的资源未满足前，不把它投入运行。一旦投入运行后，这些资源就一直归它所有，也不再提出其他资源请求，这样就可以保证系统不会发生死锁。
缺点：系统资源被严重浪费，其中有些资源可能仅在运行初期或运行快结束时才使用，甚至根本不使用。而且还会导致“饥饿”现象，当由于个别资源长期被其他进程占用时，将致使等待该资源的进程迟迟不能开始运行。

破坏不可剥夺条件

方法：当一个已保持了某些不可剥夺资源的进程，请求新的资源而得不到满足时，它必须释放已经保持的所有资源，待以后需要时再重新申请。这意味着，一个进程已占有的资源会被暂时释放，或者说是被剥夺了，或从而破坏了不可剥夺条件。
缺点：该策略实现起来比较复杂，释放已获得的资源可能造成前一阶段工作的失效，反复地申请和释放资源会增加系统开销，降低系统吞吐量。这种方法常用于状态易于保存和恢复的资源，如CPU的寄存器及内存资源，一般不能用于打印机之类的资源。

破坏循环等待条件

方法：为了破坏循环等待条件，可釆用顺序资源分配法。首先给系统中的资源编号，规定每个进程，必须按编号递增的顺序请求资源，同类资源一次申请完。也就是说，只要进程提出申请分配资源Ri，则该进程在以后的资源申请中，只能申请编号大于Ri的资源。
缺点：这种方法存在的问题是，编号必须相对稳定，这就限制了新类型设备的增加；尽管在为资源编号时已考虑到大多数作业实际使用这些资源的顺序，但也经常会发生作业使用资源的顺序与系统规定顺序不同的情况，造成资源的浪费；此外，这种按规定次序申请资源的方法，也必然会给用户的编程带来麻烦。

避免死锁的算法

判断“系统安全状态”法

在进行系统资源分配之前，先计算此次资源分配的安全性。若此次分配不会导致系统进入不安全状态，则将资源分配给进程；否则，让进程等待。

银行家算法

1、申请的贷款额度不能超过银行现有的资金总额
2、分批次向银行提款，但是贷款额度不能超过一开始最大需求量的总额
3、暂时不能满足客户申请的资金额度时，在有限时间内给予贷款
4、客户要在规定的时间内还款

一句话

当一个进程申请使用资源的时候，银行家算法通过先试探分配给该进程资源，然后通过安全性算法判断分配后的系统是否处于安全状态，若不安全则试探分配作废，让该进程继续等待。

一张图

首先是银行家算法中的进程：包含进程Pi的需求资源数量（也是最大需求资源数量，MAX）
已分配给该进程的资源A（Allocation）
还需要的资源数量N（Need=M-A）
Available为空闲资源数量，即资源池（注意：资源池的剩余资源数量+已分配给所有进程的资源数量=系统中的资源总量）

假设资源P1申请资源，银行家算法先试探的分配给它（当然先要看看当前资源池中的资源数量够不够），若申请的资源数量小于等于Available，然后接着判断分配给P1后剩余的资源，能不能使进程队列的某个进程执行完毕，若没有进程可执行完毕，则系统处于不安全状态（即此时没有一个进程能够完成并释放资源，随时间推移，系统终将处于死锁状态）。

若有进程可执行完毕，则假设回收已分配给它的资源（剩余资源数量增加），把这个进程标记为可完成，并继续判断队列中的其它进程，若所有进程都可执行完毕，则系统处于安全状态，并根据可完成进程的分配顺序生成安全序列（如{P0，P3，P2，P1}表示将申请后的剩余资源Work先分配给P0–>回收（Work+已分配给P0的A0=Work）–>分配给P3–>回收（Work+A3=Work）–>分配给P2–>······满足所有进程）。

如此就可避免系统存在潜在死锁的风险。

死锁的检测

该部分讲述如何判断是否产生死锁

画出资源分配图

系统死锁，可利用资源分配图来描述。如下图所示，用长方形代表一个进程，用框代表一类资源。由于一种类型的资源可能有多个，用框中的一个点代表一类资源中的一个资源。从进程到资源的有向边叫请求边，表示该进程申请一个单位的该类资源；从资源到进程的边叫分配边，表示该类资源已经有一个资源被分配给了该进程。

简化资源分配图

第一步：先看A资源，它有三个箭头是向外的，因此它一共给进程分配了3个资源，此时，A没有空闲的资源剩余。
第二步：再看B资源，它有一个箭头是向外的，因此它一共给进程分配了1个资源，此时，B还剩余一个空闲的资源没分配。
第三步：看完资源，再来看进程，先看进程P2，它只申请一个A资源，但此时A资源已经用光了，所以，进程P2进入阻塞状态，因此，进程P2暂时不能化成孤立的点。
第四步：再看进程P1，它只申请一个B资源，此时，系统还剩余一个B资源没分配，因此，可以满足P1的申请。这样，进程P1便得到了它的全部所需资源，所以它不会进入阻塞状态，可以一直运行，等它运行完后，我们再把它的所有的资源释放。相当于：可以把P1的所有的边去掉，变成一个孤立的点，如下图所示：

第五步：进程P1运行完后，释放其所占有的资源（2个A资源和1个B资源），系统回收这些资源后，空闲的资源便变成2个A资源和1个B资源，由于进程P2一直在申请一个A资源，所以此时，系统能满足它的申请。这样，进程P2便得到了它的全部所需资源，所以它不会进入阻塞状态，可以一直运行，等它运行完后，我们再把它的所有的资源释放。相当于：可以把P2的所有的边都去掉，化成一个孤立的点，变成下图：