2.8 进程死锁

1. 进程死锁概念与条件

2. 进程死锁的预防机制

3. 进程死锁的避免机制

4. 进程死锁检测与解决

5. 进程死锁问题的思考

一、进程死锁概念与条件

（1）背景： 多道进程的并发执行改善系统的资源利用率，但也可能进程互相等待对方释放资源才能继续运行；

（注意，单道环境下是不会出现死锁的情况的，因为进程独占计算机资源）

死锁：系统中多个进程无限期地等待永不会满足的条件，而处于停滞状态，成为进程死锁；

（2) 死锁场景

申请同类资源(如内存，多个进程同时占满内存，但进程还需要更多内存资源时，会产生进程互相的无限等待）

申请不同类资源（如打印机、扫描仪等临界资源，两个进程由于并发执行导致互相占有一个临界资源，同时又在等待对方占有的临界资源，也会互相无限等待）

（3）死锁条件（必要条件， 不是充分条件）

1、互斥使用（资源独占）： 资源每次只能给一个进程使用；

2、不可抢占（不可剥夺）：资源申请者不能强行从占有者手中夺取资源，只能由占有者自愿释放；

3、请求保持：进程在申请新资源的同时，保持对原有资源的占有；

4、循环等待：系统中存在一个进程的等待队列，队列中的进程互相等待对方占有的资源，并形成等待闭环；

二、进程死锁的预防机制

（1）预防机制原理

预先确定资源的分配，保证系统中绝对不会发生死锁；

一般通过破坏死锁的4个必要条件之一来实现；

破坏“互斥使用”之一必要条件不现实（比如打印机等资源是绝对要互斥使用的）；

（2）解决方案

1、 破坏“不可抢占”：

允许进程动态申请资源；

进程在申请新资源不能得到满足二变为等待状态之前，必须释放已占有资源，若需要资源需要重新申请分配；

2、破坏“请求保持”：

不允许进程动态申请资源；

进程运行前必须一次性申请所需的所有资源；

进程所需要资源均可满足的时候要给予一次性分配；

（这个方法有明显缺陷，大多数进程一开始并不知道自己会需要多少资源，很难一次分配。即使一次性分配了，也很有可能降低计算机资源的利用率）

3、 破坏”循环等待“：

采用资源有序分配法：

给系统中所有资源编号；

进程必须严格按照资源编号的递增次序申请资源；

违反以上规则的操作，系统不予分配；

（该方法不太灵活，如果有进程一开始就需要编号大的资源，则它会将所有需要的编号小的资源一次性全都申请，但不会立刻使用，从而导致这些资源处于闲置状态）

三、进程死锁的避免机制

（1）避免机制原理

系统并非一开始就分配好资源以预防死锁，而是对进程在执行过程中发出的每一个资源申请进行动态检查；

根据检查结果决定是否分配资源；

若分配后可能发生死锁，则不予分配，否则分配；

（2）银行家算法（又一个dijkstra发明的算法，yyds）

银行家有一笔周转资金

客户要求分期贷款，如果客户能得到各期贷款，就一定能够还贷，否则就一定不能归还贷款（不考虑利息hh）

银行家要谨慎贷款，防止坏账；

银行家采用的具体方法 是看是否有足够的剩余资金来满足某一顾客，如此反复下去；

如果所有投资最终都被收回，则请求可以批准

对应到系统中，银行家就是操作系统，周转资金就是系统管理的资源，而客户就是进程；

银行家算法的实质就是要设法保证系统动态分配资源后不进入不安全状态，以避免可能产生的死锁。

1、单种资源情况：

假设有四个进程（对应四个人名），系统共有十个资源，（a）是所有进程都没开始时预计需要的资源情况；
过了一段时间，系统处于（b）的情况，系统还剩两个资源，为了检测此时状态是否会发生死锁，我们将剩余资源同进程还需要的资源进行比对。
可以发现，只要我们将两个剩下的资源都给Marvin进程，该进程达到资源需求进程完成结束后会释放四个资源，再将四个资源给Barbara，之后我们会由五个剩余资源，然后再把五个资源给Andy，最后再给Suzanne，这样系统中的进程就不会处于死锁状态（也可以是别的分配方式）。

因此（b）状态并没有死锁问题，我们称其为安全状态；

假设Barbara又要申请一个资源，系统先尝试着分配，假设把需要的资源给进程，系统会不会由安全状态变为死锁状态；

（c）是尝试分配了之后的系统资源状态，此时系统剩余的资源不足以满足任意进程的剩余要求，既然不能满足进程需求，进程也就不能执行完毕，也就不能把占有的资源全部释放，也就变为了死锁状态。
因此，对于Barbara的申请，系统要拒绝。（也就是阻塞掉Barbara进程，等资源充足了之后再唤醒Barbara进程）

2、多种资源情况：

E = （6342）表示：系统总共由六个磁带机资源，三个绘图仪资源，四个打印机资源和两个ROM资源，P和A的表示同理；

多种资源的银行家算法，就是将单种资源的整数运算变为了向量运算；

步骤：

查找右边矩阵是否有一行，其未被满足的资源数均小于或等于向量A。 如果找不到，死锁发生。

若找到这样一行， 假设它获得所需的资源并运行结束，将该进程标记为结束，并将资源加到向量A上。

重复以上两步，直到所有进程都标记为结束，则状态是安全的，否则将发生死锁；

四、进程死锁检测与解决

（1）机制原理

系统允许死锁发生；

系统不断监视进展情况， 判断死锁是否发生；

一旦死锁发生则采取专门的措施，解除死锁并以最小的代价恢复运行；

（2）检测时机

定时检测（每隔一段时间就检测一次）

进程等待（当系统中有大量进程等待时开始检测）

资源利用率下降（当系统中有大量进程但CPU等资源的利用率下降时开始检测）

（3）检测手段

进程-资源分配图（其思想也是源自于银行家算法）：

方框表示资源类；

黑圆点表示资源实例；

圆圈中加进程名表示进程；

资源实例指向进程的一条有向边来表示分配边；（资源分配给该进程）

进程指向资源类的一条有向边表示申请边；（进程还需要指向资源中的某一实例）

检测“进程-资源分配图”是否可完全简化；

（4）检测步骤：

①找一个只有分配边的非孤立进程结点,去掉分配边将其变为孤立结点;若找不到则转③

②将资源分配给一个等待资源的进程，将某进程的申请边变为分配边，转①

③图中有进程不是孤立结点,则此图不可完全简化，满足死锁的充分条件，系统为死锁状态

上面第一个进程-资源分配图为死锁状态，而下图状态则是一个安全状态；

（5）死锁解除：

1、资源剥夺法：

从其他进程那里剥夺足够多的资源给死锁进程，以解除死锁

2、撤销进程法：

撤销全部死锁进程，恢复到正常状态，简单但代价太大；也可以逐个撤销死锁进程，直到资源足够；

五、进程死锁问题的思考

（1）死锁原因

系统资源不够充分

进程运行推进的顺序不合适（主要）

资源分配不当（主要）

（2）解决原则

单独使用死锁预防、避免、检测与解除并不能全面解决操作系统中遇到的所有死锁问题；

可将系统中的进程、资源分为若干类，对每一类进程、资源使用最适合它的办法解决死锁；

也就是说要综合的使用各类方法处理死锁问题；