死锁

重点内容，需熟练掌握死锁的产生条件、处理策略、预防方法以及银行家算法，在选择题中会考察，偶尔也在大题中考察。

死锁产生的必要条件

只有以下四个条件同时满足，死锁才会发生：

  1. 互斥条件 （Mutual Exclusion）: 指的是至少有一个资源必须处于非共享模式，也就是说，一次只有一个线程可以使用资源。如果其他线程请求该资源，那么请求的线程必须等到该资源的持有者释放该资源。
  2. 占有并等待 （Hold and Wait）: 指的是一个线程因请求资源而阻塞时，对当前获得的资源保持不放。换句话说，线程至少已经持有一个资源，但又申请新的资源；由于其他线程持有这些资源，所以它现在是阻塞的。
  3. 非抢占 （No Preemption）: 资源不能被抢占，也就是说，只有资源的持有者才可以释放它。资源在完全自愿的基础上被释放，不能被强行从持有线程中夺走。
  4. 循环等待 （Circular Wait）： 存在一个线程资源的等待链，链中的每一个线程都在等待下一个线程所持有的资源。这导致了一个循环的等待链。

为了避免死锁，需要破坏上述的任意一个条件。

死锁处理策略

  1. 死锁预防：设置限制条件，破坏产生死锁的 4 个必要条件之一。
  2. 死锁避免：在资源的动态分配过程中，用某种算法避免系统进入不安全状态。
  3. 死锁的检测和解除：允许线程在运行过程中发生死锁，通过系统检测机构及时检测出死锁的发生，然后采取某种措施解除死锁。

死锁预防

死锁预防是通过确保系统永远不会满足死锁产生的四个必要条件中的某些条件，从而避免死锁的发生：

  1. 破坏互斥条件
    • 互斥条件在某些情况下是不可避免的，例如打印机等硬件资源。但在某些场景下，通过资源复制或虚拟化技术，可以尝试减少资源的互斥使用。
  2. 破坏占有并等待
    • 要求线程在开始时一次性申请其需要的所有资源。只有当所有资源都可用时，线程才被分配资源并开始执行。这样，线程在执行期间不会等待其他资源。
    • 另一个方法是，如果线程申请新资源而被拒绝，则它必须释放所有已分配的资源，再重新申请。
  3. 破坏非抢占
    • 当一个线程需要的资源被另一个线程所占有时，它可以抢占另一个线程的资源。
  4. 破坏循环等待
    • 对线程申请资源的顺序进行限制

死锁避免

死锁避免是系统级的算法，需要对系统的资源和实体进行抽象，进行统筹规划，其中最经典的算法是银行家算法。

银行家算法

这里首先说一下次算法的命名，为什么叫“银行家”。一般而言，银行家都具备以下特点：

  • 掌管金库（即资源），可以放贷（即满足线程申请的资源）
  • 理性地作出决策，避免银行破产（即系统进入不安全状态）

相对于银行家的就是客户（即线程），线程需要申请一定量的资源。 但是线程可能不会立即申请全部的资源，线程也许会依次申请所有请求资源中的一部分， 当线程申请完全部的资源之后，它才会释放这些资源。

为了对刚刚描述的过程进行建模，我们需要定义如下的 数据结构：

  • 系统
    • Available：表示每种资源的可用数量。
  • 线程
    • Max：表示每个线程对每种资源的最大需求量。
    • Allocation：表示已经分配给每个线程的资源数量。
    • Need：表示每个线程还需要的资源数量，Need = Max - Allocation

算法步骤：

  1. 初始化：为每个线程和每种资源设置 Max、Allocation 和 Need。
  2. 当一个线程请求资源时，检查请求的资源数量是否小于等于 Need，如果大于则请求失败。
  3. 检查请求的资源数量是否小于等于 Available，如果大于则请求失败。
  4. 如果请求合法（满足上述两个条件），则模拟分配资源给该线程（预分配），即将资源从系统的 Available 减去，加到线程的 Allocation 中，并从线程的 Need 中减去相应数量的资源。
  5. 然后，进行安全性检查，判断是否存在一种 安全分配序列，使得所有线程都能顺利执行完成。
  6. 如果存在安全分配序列，则执行资源分配，否则拒绝请求，因为分配资源可能导致死锁，并且回收预先模拟分配的资源。
  7. 当线程完成任务时，释放已分配的资源，将它们从 Allocation 减去，加到 Available 中。

什么是安全分配序列：

安全分配序列是线程的一个排列，它保证了对于序列中的每个线程，当这些线程都申请 Need 中的全部资源时，系统都能够满足这些需求。

如果系统存在一个安全分配序列，则系统处于 安全状态。

注意：不安全状态不意味着死锁，但它意味着有死锁的风险。不安全状态只是死锁的一个先兆，但不是死锁本身。

如何判断是否存在安全分配序列

假设系统中存在 N 个线程的话，则最多进行 N 轮遍历，每一轮至少找到一个 need 小于或等于 available 的线程，如果可以找到的话，就回收这些线程的 allocation，并将其加入 available 中，直到回收了所有线程的资源。如果有一轮存在这种情况：剩余的线程（任务未完成的线程）中的每一个 need 都大于 available，那么则说明无法找到一个安全分配序列，系统处于不安全状态。

这种判断方式的背后具有这样的逻辑：因为线程必须申请完所有需要的资源（即max）才能返还已申请的资源，所以系统在当下肯定是尽量满足那些可以返还资源的线程，因为只有回收了一些资源之后，才能满足之前可能无法满足的线程。

但是如果在某一个时刻，剩余的线程的资源一个都无法回收了，那么系统就进入了不安全状态。

这里还要需要注意的是，在实际的算法中，我们需要用 work 替代 available 来帮助我们完成安全性检查的过程，因为检查只是一种 “逻辑推演”，我们并不希望实际修改系统中的资源情况，具体的代码实现可以参考如下链接：

银行家算法代码实现

死锁的检测和删除

为了能对系统是否已发生了死锁进行检测，必须：

  1. 用某种数据结构来保存资源的请求和分配信息：
  2. 提供一种算法， 利用上述信息来检测系统是否已进入死锁状态。

一般来说，一种简单的建模方式是使用资源分配图：

  • 将系统中的所有资源和进程表示为图中的节点。
  • 如果进程 P1 请求资源 R1，绘制从 P1 到 R1 的有向边。
  • 如果资源 R1 分配给了进程 P2，绘制从 R1 到 P2 的有向边。

在构建完资源分配图，可以通过使用 DFS 检查图中是否存在环路以判断是否存在死锁。

视频讲解