产生死锁的必要条件

互斥使用：进程对其申请的资源进行排他控制，其他申请资源的进程必须等待。
不可剥夺：占用资源的进程只能自己释放资源，不能被其他进程强迫释放，即使该进程处于阻塞状态，它所占有的资源也不能被其他进程使用，其他进程只能等待该资源的释放。
零散请求：进程可以按需要逐次申请资源，而不是集中性一次请求所有资源。这样，进程在已经占有资源的情况下，又申请其它资源而得不到满足时，并不释放已占有的资源。
循环等待:等待资源的进程形成了一个封闭的链，链上的进程都在等待下一个进程占有的资源，造成了无止境的等待状态。

以上4个条件是产生死锁的必要条件，而非充分条件。也就是说，如果破坏上述4个条件之一，就可以防止死锁的产生。

死锁的处理

有三种处理死锁的策略:

预防死锁。限制请求,保证前文提到的四个死锁条件中至少有一个不能发生, 从而预防死锁；
避免死锁。如果结果状态是安全的, 就将资源动态地分给进程。如果至少有一个执行序列使所有的进程都能完成运行, 那么这个状态就是安全的；
检测死锁和从死锁中恢复, 允许死锁发生, 然后发现并解除死锁。

死锁预防和避免采用一种悲观方法，即认为死锁会经常发生并试图阻止或避免它。虽然死锁避免策略在集中式系统中广为应用，并且有许多算法，但是在分布式系统中很少使用。这是因为在分布式系统中没有全局时钟，检查安全性状态会涉及到大量进程和资源的计算，从而引起昂贵的开销。死锁检测和恢复使用乐观方法，然而这种方法对于死锁发生频繁的应用程序可能并不有效。

死锁的预防

算法

死锁预防算法通过限制进程的资源请求方法来预防死锁。死锁预防通常通过下列方法之一来实现。它们都基于打破四个死锁条件中的一种：

破坏互斥条件:

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

破坏“不可剥夺”条件:

允许进程剥夺也应当包括剥夺自己的“请求”，也就是进程申请资源得不到满足时，进程可以收回请求，转去做其他的工作。当一个已保持了某些不可剥夺资源的进程，请求新的资源而得不到满足时，它必须释放已经保持的所有资源，待以后需要时再重新申请。这意味着，一个进程已占有的资源会被暂时释放，或者说是被剥夺了，或从而破坏了不可剥夺条件。

该策略实现起来比较复杂，释放已获得的资源可能造成前一阶段工作的失效，反复地申请和释放资源会增加系统开销，降低系统吞吐量。为了保存进程放弃资源的现场以及以后的再次恢复，往往要耗费很多时间和存储空间。这种方法常用于状态易于保存和恢复的资源，如CPU的寄存器及内存资源，一般不能用于打印机之类的资源。

破坏“零散请求”条件:

釆用预先静态分配方法，即进程在运行前一次申请完它所需要的全部资源，在它的资源未满足前，不把它投入运行。一旦投入运行后，这些资源就一直归它所有，也不再提出其他资源请求，这样就可以保证系统不会发生死锁。

这种方式实现简单，但缺点也显而易见，系统资源被严重浪费，其中有些资源可能仅在运行初期或运行快结束时才使用，甚至根本不使用。而且还会导致“饥饿”现象，当由于个别资源长期被其他进程占用时，将致使等待该资源的进程迟迟不能开始运行。

破坏“循环等待”条件:

为了破坏循环等待条件，可釆用顺序资源分配法。首先给系统中的资源编号，规定每个进程，必须按编号递增的顺序请求资源，同类资源一次申请完。也就是说，只要进程提出申请分配资源Ri，则该进程在以后的资源申请中，只能申请编号大于Ri的资源。

这种方法存在的问题是，编号必须相对稳定，这就限制了新类型设备的增加；尽管在为资源编号时已考虑到大多数作业实际使用这些资源的顺序，但也经常会发生作业使甩资源的顺序与系统规定顺序不同的情况，造成资源的浪费；此外，这种按规定次序申请资源的方法，也必然会给用户的编程带来麻烦。

死锁的避免

死锁的预防策略是以破坏死锁产生的必要条件为目的，对资源的申请加以限制的。虽然这对死锁的预防有一定的效果，但是几种方法都降低了系统的效率和资源的利用率。

死锁的避免策略有所不同，它用动态的方法判断资源的使用情况和系统的状态，在分配资源之前，系统将判断假若满足事务的要求是否会发生死锁，如果会，资源就不予分配，从而避免死锁的发生。

系统的状态分为安全状态和不安全状态。所谓安全状态，是指当多个事务动态地申请资源时，系统将按照某种顺序逐次地位每个事务分配所需资源，使每个事务都可以在最终得到最大需求量后，依次顺利地完成。反之，如果不存在这样一种分配顺序使得事务都能顺利完成，则称系统处于不安全状态。

不安全状态不一定发生死锁，但死锁一定处于不安全状态。

资源分配不当引起的死锁

若系统中有五台打印机，有多个事务均需要使用两台，规定每个事务一次仅允许申请一台，则在不发生死锁的情况下至多允许__个事务参与竞争

答案：4

解析：如果一个事务有m个资源它就能够结束，不会使自己陷入死锁中。因此最差情况是每个事务有m-1个资源并且需要另外一个资源。如果留下有一个资源可用，那么其中某个事务就能够结束并释放它的所有资源，使其它事务也能够结束。所以避免死锁的条件是：r≥p(m-1)+1。

银行家算法

系统给当前事务分配资源时，先检查是否安全：

在满足当前的事务X资源申请后，是否还能有足够的资源去满足下一个距最大资源需求最近的事务（如某事务最大需要5个单位资源，已拥有1个，还尚需4个），若可以满足，则继续检查下一个距最大资源需求最近的事务，若均能满足所有事务，则表示为安全，可以允许给当前事务X分配其所需的资源申请，否则让该事务X进入等待。

（注：检查过程中，每拟满足一个事务，则进行下个检查时，当前可用资源为回收上一个事务资源的总值，每满足一个事务表示此事务已结束，资源可回收。）

银行家算法在避免死锁角度上非常有效，但是需要在事务运行前就知道其所需资源的最大值，且事务数也通常不是固定的，因此使用有限，但从思想上可以提供了解，可以转换地应用在其他地方

分布式系统的死锁处理

文章目录