死锁的发生与预防

死锁的概念

在多线程环境下，为了避免资源的竞争，通常我们会给资源加上互斥锁，谁拿到这个锁谁就有资格享有这个资源。

当一个 A 进程申请资源时，如果这个时候没有可用的资源，那么这个进程会进入等待状态。如果所申请的资源被其他进程 B 占有，并且该进程也在等待进程 A 的资源，那么在这种各自都在等待对方释放锁，你等我，我等你的情况，就可能永远都无法释放锁。这种情况称为死锁（deadlock）。

死锁的必要条件

要发生死锁，那就需要同时满足四个条件：

• 互斥（mutual exclusion） ：同一个资源不可被多个进程所共享。
• 占有并等待（hold and wait） ：如果进程 A 发现想要的资源已经被进程 B 占有了，那么此时进程 A 应该等待进程 B 的资源释放，与此同时进程 A 所拥有的资源不应该释放，而是持续占有。
• 非抢占（no preemption）：已经被进程占有的资源，不可被其他进程强行抢占，只能等待该资源被所持有的进程主动释放。
• 循环等待（circular wait）：有一组等待进程 ， 等待的资源为 所占有， 等待的资源为 所占有， 等待的资源为 所占有。

死锁的预防

死锁需要成立需要同时满足四个条件。那么只需要确保至少有一个条件不成立就不会发生死锁。

互斥

互斥条件必须成立！

在多线程环境下，必须保证同一份共享资源只能同时给一个线程访问。

因为如果共享资源不要求互斥访问，那么就不会产生死锁，但同时也就没法保证数据的安全性。

占有并等待

打破这种条件的方案：

1. 每个线程在执行前就申请到所有资源。
2. 在线程没有资源时才申请资源，已有资源时则不再申请。也就是说，在申请更多其他资源之前，应该先释放线程本身已有的资源。

缺点：

• 资源利用率较低，因为一次分配到了所有所需资源，但并不是立刻使用，导致其他所需要这些资源的线程无法继续任务。
• 进程容易处于饥饿状态，因为一直申请不到全部资源。

非抢占

打破这种条件的方案：

• 如果一个线程所持有的资源，并同时申请另一个不能立即分配到的资源（也就是说，该线程应该等待该资源被释放），那么该线程所分配到的所有资源都可以被抢占！

具体的说，如果一个线程申请了一些资源，那么首先会检查资源是否可用：

• 如果资源可用，则分配他们。
• 如果资源不可用，那么就从持有该资源的等待线程（等待队列）中抢占，并分配给申请线程。如果没有从等待队列中找到持有该资源的线程，那么申请线程将进入等待队列。
• 只有当一个线程分配到申请的资源，并恢复在等待时被抢占的资源时，才能重新执行。

为什么只有等待队列中的线程可以被抢占？ 因为在等待队列中的线程还没有执行，所以被抢占了也不影响。

特别注意，这种破坏只适用于 CPU 寄出去、数据库事务这种状态可以轻松保存会恢复的资源。

• 为什么？因为在等待线程被抢占，那么就需要具备：当线程恢复了，不会对资源（现场）造成任何影响。
• 如果抢占了不具备状态恢复能力的资源，那么当线程恢复后，现场可能不一样。

不适用于互斥锁和信号量之类的资源，因为这些资源恰恰是最经常发生死锁的资源。

• 为什么？因为需要用到互斥锁和信号量的资源，那都是共享资源。
• 如果抢占了这类资源，那么临界区数据就会被破坏，如链表修改到一半，结果被抢占了，导致数据结构被破坏了。

循环等待

打破这种条件的方案：

• 为所有资源分配一个唯一整数编号，并对这些资源进行排序。
• 而且要求每个线程都要按照递增所需来申请资源。

由于资源只能按照编号递增申请，等待关系不可能形成环，因此循环等待不会发生。

例如：

P1 -> R1
P2 -> R3
P2 -> R4
P1 -> R2

每个进程已有的资源 ，在申请新的资源 时，必须满足 。

好处：

• 资源利用率相对于前面两种方式较高。（不会一次申请全部资源，也不会频繁释放）

缺点：

• 各类资源的顺序与系统规定的顺序有绝对影响

• 当程序使用资源的顺序与系统规定的不同的，就会造成资源浪费。

  例如，进程 A 要先使用打印机，然后才使用磁盘。（而系统规定顺序：） 那么进程 A 就必须先获取磁盘，而不能先获取打印机。此时，由于进程 A 提取占用了未来才使用到的资源，导致其他需要这个磁盘资源的进程无法继续任务，只能等待磁盘资源的释放。这就造成了资源浪费。

• 编程复杂，程序员必须要清楚系统所有资源的顺序，才可以编写高效的程序。

• 新设备编号引入可能会打乱原有资源的顺序。

死锁的预防所存在的问题

《死锁的预防》主要是通过“限制资源的申请方式”来预防死锁。这种限制确保了至少有一个死锁必要条件不会发生。而通过这种方式来预防死锁也有缺点：

• 设备利用率低
• 系统吞吐率低

另外一种避免死锁的方式，这种方法需要先知道一些信息，基于这些信息来预测以及避免死锁。

针对每次申请要求，系统在做决定时考虑如下资源情况：

• 现有可用资源
• 已经分配的资源
• 每个进程将来申请与释放的资源

安全状态

安全状态是死锁避免中很重要的一个概念。

• 安全状态（Safe State）：至少存在一个进程序列，按照这个序列申请资源，使得每个进程都能获得所需资源，完成执行、释放资源，从而允许其他进程最终完成而不进入死锁。
• 不安全状态（Unsafe State）：尽管系统仍然可以向某些进程分配资源，但无法保证所有进程都能完成而不可能引发死锁。

常见的两种算法

• 资源分配图算法
• 银行家算法