死锁的定义、必要条件和处理方法
- 死锁的定义
多个进程在执行过程中，因争夺同类资源且资源分配不当而造成的一种互相等待的现象，若无外力作用，它们都将永远无法继续执行，这种状态称为死锁，这些处于等待状态的进程称为死锁进程。
2、产生死锁的必要条件
- 互斥条件：进程对所分配到的资源进行排他性使用，即一段时间内，某资源只能被一个进程占用。如果此时还有其他进程请求该资源，则进程只能等待，直至占有资源的进程用毕释放。
- 请求和保持条件：进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源已经被其他进程占有，此请求进程被阻塞，但对自己已获得的资源保持不放。
- 不可抢占条件：进程已获得的资源在未使用完成之前不能被抢占，只能在进程使用完成时由自己释放。
- 循环等待条件：在发生死锁时，必存在一个进程——资源的循环链，即进程的集合{P0，P1，P2，…Pn}中的P0正在等待P1占用的资源，P1正在等待P2占用的资源，……Pn正在等待P0占用的资源。
3、处理死锁的方法
1.预防死锁：
这是一种较简单和直观的实现预防方法。该方法通过设置某些限制条件，去破坏产生死锁的四个必要条件中的一个或几个来预防产生死锁。预防死锁是一种较易实现的方法，已被广泛使用。
2.避免死锁：
同样是属于事先预防策略，但它并不是事先采取各种限制措施，去破坏产生死锁的四个必要条件，而是在资源的动态分配过程中，用某种方法防治系统进入不安全状态，从而可以避免发生死锁。
3.检测死锁：
这种方法无需事先采取任何限制性措施，允许进程在运行过程中发生死锁。但可以通过检测机构及时检测出死锁的发生，然后采取相应的措施，把进程从死锁中解脱出来。
4.解除死锁：
当系统检测到系统中已经发生了死锁时，就采取相应的措施，将进程从死锁状态中解脱出来。常用的方法就是撤消一些进程，回收他们的资源，将他们分配给已处于阻塞状态的进程，使其能继续运行。
预防死锁：
（1）破坏互斥条件
方法：
允许系统资源都能共享使用，则系统不会进入死锁状态。
缺点：
有些资源根本就不能被同时使用，如打印机资源，所以，破坏互斥条件而预防死锁的方法不太可行，而且在有的场合应该保护这种互斥性。
（2）破坏请求保持条件
方法：
釆用预先静态分配方法，即进程在运行前一次申请完它所需要的全部资源，在它的资源未满足前，不把它投入运行。一旦投入运行后，这些资源就一直归它所有，也不再提出其他资源请求，这样就可以保证系统不会发生死锁。
缺点：
系统资源被严重浪费，其中有些资源可能仅在运行初期或运行快结束时才使用，甚至根本不使用。而且还会导致“饥饿”现象，当由于个别资源长期被其他进程占用时，将致使等待该资源的进程迟迟不能开始运行。
（3）破坏不可抢占条件
方法：
当一个已保持了某些不可剥夺资源的进程，请求新的资源而得不到满足时，它必须释放已经保持的所有资源，待以后需要时再重新申请。这意味着，一个进程已占有的资源会被暂时释放，或者说是被剥夺了，或从而破坏了不可剥夺条件。
缺点：
该策略实现起来比较复杂，释放已获得的资源可能造成前一阶段工作的失效，反复地申请和释放资源会增加系统开销，降低系统吞吐量。这种方法常用于状态易于保存和恢复的资源，如CPU的寄存器及内存资源，一般不能用于打印机之类的资源。
（4）破坏循环等待条件
方法：
为了破坏循环等待条件，可釆用顺序资源分配法。首先给系统中的资源编号，规定每个进程，必须按编号递增的顺序请求资源，同类资源一次申请完。也就是说，只要进程提出申请分配资源Ri，则该进程在以后的资源申请中，只能申请编号大于Ri的资源。
缺点：
这种方法存在的问题是，编号必须相对稳定，这就限制了新类型设备的增加；尽管在为资源编号时已考虑到大多数作业实际使用这些资源的顺序，但也经常会发生作业使用资源的顺序与系统规定顺序不同的情况，造成资源的浪费；此外，这种按规定次序申请资源的方法，也必然会给用户的编程带来麻烦。
避免死锁：
判断系统安全状态
在该方法中，允许进程动态的申请资源，但系统进行资源分配之前，应先计算此次资源分配的安全性。若此次分配资源不会导致系统进入不安全状态，才可将资源分配给进程，否则，另进程等待。所谓安全状态，是指系统能按某种进程推进顺序{P0，P1，P2，…Pn}为每个进程Pi分配资源，直至满足每个进程对资源的最大需求，使每个进程都可以顺利地完成，此时{P0，P1，P2，…Pn}为安全序列。如果无法找到这样一个安全序列，则称系统处于不安全状态。虽然并非所有不安全状态都必然会转为死锁状态，但当系统进入不安全状态后，就有可能进入死锁状态，反之，只要系统处于安全状态，系统便不会进入死锁状态。因此避免死锁的实质在于，系统在资源分配时，应使系统不进入不安全状态。
利用银行家算法避免死锁：
1、申请的贷款额度不能超过银行现有的资金总额
2、分批次向银行提款，但是贷款额度不能超过一开始最大需求量的总额
3、暂时不能满足客户申请的资金额度时，在有限时间内给予贷款
4、客户要在规定的时间内还款
死锁的检测：
- 资源分配图
1.1画出资源分配图
系统死锁，可利用资源分配图来描述。如下图所示，用长方形代表一个进程，用框代表一类资源。由于一种类型的资源可能有多个，用框中的一个点代表一类资源中的一个资源。从进程到资源的有向边叫请求边，表示该进程申请一个单位的该类资源；从资源到进程的边叫分配边，表示该类资源已经有一个资源被分配给了该进程。
1.2简化资源分配图
第一步：
先看A资源，它有三个箭头是向外的，因此它一共给进程分配了3个资源，此时，A没有空闲的资源剩余。
第二步：
再看B资源，它有一个箭头是向外的，因此它一共给进程分配了1个资源，此时，B还剩余1个空闲的资源没分配。
第三步：
看完资源，再来看进程，先看进程P2，它只申请一个A资源，但此时A资源已经用光了，所以，进程P2进入阻塞状态，因此，进程P2暂时不能化成孤立的点。
第四步：
再看进程P1，它只申请一个B资源，此时，系统还剩余一个B资源没分配，因此，可以满足P1的申请。这样，进程P1便得到了它的全部所需资源，所以它不会进入阻塞状态，可以一直运行，等它运行完后，我们再把它的所有的资源释放。相当于：可以把P1的所有的边去掉，变成一个孤立的点，如下图所示：
第五步：
进程P1运行完后，释放其所占有的资源（2个A资源和1个B资源），系统回收这些资源后，空闲的资源便变成2个A资源和1个B资源，由于进程P2一直在申请一个A资源，所以此时，系统能满足它的申请。这样，进程P2便得到了它的全部所需资源，所以它不会进入阻塞状态，可以一直运行，等它运行完后，我们再把它的所有的资源释放。相当于：可以把P2的所有的边都去掉，化成一个孤立的点，变成下图：
若能消去图中所有的边，则称该图是可完全简化的，如上图
2.死锁定理
①如果资源分配图中没有环路，则系统没有死锁；
②如果资源分配图中出现了环路，则系统可能有死锁。
或者说：
当且仅当S状态的资源分配图是不可完全简化的时候，系统状态则是死锁状态。
死锁的解除：
1、资源剥夺法
挂起某些死锁进程，并抢占它的资源，将这些资源分配给其他的死锁进程。但应防止被挂起的进程长时间得不到资源，而处于资源匮乏的状态。
2、撤销进程法
强制撤销部分、甚至全部死锁进程并剥夺这些进程的资源。撤销的原则可以按进程优先级和撤销进程代价的高低进行。
3、进程回退法
让一（多）个进程回退到足以回避死锁的地步，进程回退时自愿释放资源而不是被剥夺。要求系统保持进程的历史信息，设置还原点。
参考：
操作系统第四版(西安电子科技大学出版社)
https://blog.csdn.net/jgm20475/article/details/81297819