死锁

关于死锁

概念

当一组进程内的每个进程都在等待一个事件，而此事件只能由这组进程的另一个进程引起，那么这组进程处于死锁状态。死锁时，进程永远不能完成。

死锁达成的条件

以下条件同时成立，死锁达成。

互斥：至少有一个资源为非共享的，一次仅供一个进程使用。

占有并等待：一个进程占有至少一个资源，并等待另一个资源，其被其他进程占有。

非抢占：资源不能被抢占

循环等待：一组进程中，一个进程占有一个资源并申请下一个被其他进程占有的资源，形成环时，就导致了循环等待。

资源分配图

设Pi为进程，Vi为资源，Vi中的原点代表其中的实例个数。

Pi->Vi称为申请边，Vi->Pi称为分配边。

![image-20201125225056516]

当每个资源仅有一个实例时，出现环即说明出现死锁（或者说以原点为节点出现环时，出现死锁）。

如何避免死锁

一种方法是使得死锁的四个必要条件之一不成立，另一种方法通过对资源的调度预防死锁。

1.如何避免以下条件成立

互斥：互斥条件必须成立，因为可共享的资源不要求互斥访问，也就不会参与死锁。

占有并等待：保证进程申请一个资源时，它不能占有其他资源。

​ 方法一：在进程执行前申请并获得所有资源，如申请不到，等待。

​ 方法二：使进程没有持有资源时才可申请，即一个占有资源的进程要申请剩下的资源，需要释放自身持有的资源。

无抢占：把资源设置为可被抢占的，被抢走的资源的进程必须获得原有资源以及申请的新资源才可重新执行。

循环等待：对所有资源进行排序，要求每个进程按照顺序来申请资源。

​ 使用F()来表示资源的优先级。

​ 假设Pi占有Ri-1(P0占有Rn)，Pi申请Ri，且当F(Ri)>F(Ri-1)时，申请可以成功。通过反证法可以证明，这样一种协议可以保证死锁不成立。

![image-20201125230345298]

假设申请全都可以成功，通过递推可以知道，此时的被P0占有的R3的优先级大于P0想要申请的R0，即申请不能成功，如此就破解了资源分配图的环。

通过以上方法即限制申请资源来预防死锁通常导致设备使用率和系统吞吐率低。

2.通过对资源的调度来避免死锁

通过构造算法，动态检查资源分配状态，以便确保循环等待条件不能成立。这种方法通常要求更多的额外信息，如进程如何申请资源。

安全状态: 如果系统可以按照一定顺序为每个进程分配资源且避免死锁，则系统状态为安全。安全状态一定不会死锁，而不安全状态可能导致死锁。

资源分配图算法：在之前的资源分配图基础上引入需求边，用Pi->Rj表示，然后将原来的申请边（近似，并不等于申请边）改为虚线表示，当Pi申请Rj，需求边Pi->Rj变成申请边，当Pi释放Rj，分配边Rj->Pi变成需求边Pi->Rj.

其算法的本质是，当进程Pi申请Rj时，需求边变成申请边，若此时Rj被分配给Pi将导致环的出现（即进入非安全状态），拒绝分配。

如图，P2申请R2，虽然R2目前可用，但不能分配给P2，因为如此将导致环的出现，是系统进入非安全状态。![image-20201125232211029]

银行家算法：当新进程进入系统时，它应当声明可能需要的每种类型资源实例的最大数量，这一数量不能超过系统资源的总和。当用户申请一组资源，系统应确定分配是否会导致非安全状态，若是，进程应等待。

略。

死锁检测

一个系统若不采用死锁预防也不采用死锁避免，死锁可能出现，所以系统需要提供某些方法来应对：

1.检查系统是否存在死锁的算法

2.从死锁恢复的算法

单个实例的资源类型：可以定义一个死锁检测算法，使用资源分配图的变形，等待图（去掉资源分配图的资源节点，合并适当的边）。当且仅当等待图中有一个环，系统死锁。

![image-20201125233105516]

算法周期检测环的存在来检查死锁是否存在。

多个实例的资源类型：我反正搞球不懂。

何时来调用检测算法呢？这取决于死锁可能发生的频率和死锁带来的影响。

死锁恢复

通过人工处理或是系统自动恢复，这里探讨自动回复。

进程终止：分为一次性终止所有进程或是一个一个终止直到死锁消除。

选择哪一种方法取决于代价，有很多因素影响着这个代价（进程的优先级，进程完成的程度，进程使用了多少资源，需要终止多少资源，进程是交互的还是批处理的），我们需要最小化代价。

资源强制：不断抢占一些进程的资源来给其他进程使用，直到打破死锁。

当然也是有代价的，如何来处理这个问题要考虑三个因素。

如何选择牺牲进程；

如何回滚；

这是否导致饥饿。

总之依然需要考虑最小化代价。