死锁的产生、防止、避免、检测和解除

死锁概念

在许多应用中进程需要以独占的方式访问资源，当操作系统允许多个进程并发执行时可能会出现进程永远被阻塞现象，如两个进程分别等待对方所占的资源，于是两者都不能执行而处于永远等待状态，此现象称为死锁。

死锁通常被定义为：如果一个进程集合中的每个进程都在等待只能由此集合中的其他进程才能引发的事件，而无限期陷入僵持的局面称为死锁。

死锁发生条件

• 互斥条件: 临界资源是独占资源，至少有一个资源是不可共享的，一次只能被一个进程占用。如果另一个进程想要使用该资源，必须等待当前进程释放它。
• 占有和等待条件: 一个进程已经拥有了至少一个资源，同时又在等待获取另一个被其他进程占用的资源, 同时不释放已占有资源。
• 不剥夺条件: 又称不可抢占，已获资源只能由进程自愿释放，不允许被其他进程剥夺。
• 循环等待条件: 又称环路条件，存在循环等待链，其中，每个进程都在等待链中等待下一个进程所持有的资源，造成这组进程处于永远等待状态。

死锁的解决方案

死锁的解决方案一般有4种类型

• 死锁预防: 破坏死锁的四个必要条件之一保证不会发生死锁
• 死锁避免: 动态检查资源分配状态，以确保永远不会进入不安全状态
• 死锁检测和恢复: 允许系统进入死锁状态，但会定期检测是否存在死锁, 并处理对应进程
• 死锁忽略: 不做任何预防或检测。当死锁发生时，让用户手动处理

死锁预防 (Deadlock Prevention)

通过破坏死锁的四个必要条件之一可以确保死锁永远不会发生。

例如，要求所有进程在开始执行前一次性请求所有所需的资源，或者为资源设定一个统一的顺序，所有进程必须按此顺序请求资源。

在实际生产中，最常见和最有效的方法是破坏“占有并等待”和“循环等待”条件。通过精心设计资源申请和分配的流程，可以从根本上减少死锁的发生，从而提高系统的稳定性和可靠性。

破坏互斥条件

使资源同时访问而非互斥使用，就没有进程会阻塞在资源上，从而不发生死锁。

将资源转化为可共享：如果可能，将资源从独占模式转变为共享模式。

只读数据文件、磁盘等软硬件资源均可采用这种办法管理；

但是许多资源是独占性资源，如可写文件、键盘等只能互斥的占有；

所以这种做法在许多场合是不适用的, 所以这是最难实现，也是最不常用的方法

应用案例：

这更多是软件设计层面的考量。例如，将一个独占式的资源服务化，多个客户端可以通过网络调用来共享这个服务，而不是直接访问底层资源。这可以有效减少因直接竞争资源而导致的死锁。然而，对于像数据库行锁这样的核心互斥资源，这种方法通常不适用。

破坏占有和等待条件

采用静态分配的方式，静态分配的方式是指进程必须在执行之前就申请需要的全部资源，且直至所要的资源全部得到满足后才开始执行。

实现简单，但是严重的减低了资源利用率。

因为在每个进程占有的资源中，有些资源在运行后期使用，有些资源在例外情况下才被使用，可能会造成进程占有一些几乎用不到的资源，而使其他想使用这些资源的进程等待。

应用案例：

这在数据库事务中很常见。当一个事务需要锁定多个表或行时，它通常会尝试在开始时就获取所有所需的锁。例如，使用 SELECT ... FOR UPDATE 语句一次性锁定多行。如果任何一个锁无法立即获取，整个操作就会等待或失败，而不是只占有一部分锁然后等待。

破坏不剥夺条件

剥夺调度能够防止死锁，但是只适用于内存和处理器资源。

• 方法一：占有资源的进程若要申请新资源，必须主动释放已占有资源，若需要此资源，应该向系统重新申请。
• 方法二：资源分配管理程序为进程分配新资源时，若有则分配；否则将剥夺此进程已占有的全部资源，并让进程进入等待资源状态，资源充足后再唤醒它重新申请所有所需资源。

应用案例：

这种方法在实时操作系统或嵌入式系统中比较常见，因为这些系统对响应时间有严格要求。

例如，一个高优先级的任务可能需要抢占一个低优先级任务正在使用的资源，以确保关键操作能够及时完成。但在通用的操作系统和数据库系统中，由于实现复杂且可能导致性能问题，这种方法相对较少使用。

破坏循环等待条件

给系统的所有资源编号，规定进程请求所需资源的顺序必须按照资源的编号依次进行。

采用层次分配策略，将系统中所有的资源排列到不同层次中

• 一个进程得到某层的一个资源后，只能申请较高一层的资源
• 当进程释放某层的一个资源时，必须先释放所占有的较高层的资源
• 当进程获得某层的一个资源时，如果想申请同层的另一个资源，必须先释放此层中已占有的资源

应用案例：

这个方法在需要访问多个共享资源的系统中非常有效。

数据库：许多数据库系统（如 MySQL InnoDB）在内部会对行锁进行排序，当一个事务需要获取多个行锁时，会按照行主键的顺序来获取，从而避免因不同事务以不同顺序加锁而导致的死锁。

多线程编程：在多线程应用中，当线程需要获取多个互斥锁（Mutex）时，可以为这些锁定义一个全局的获取顺序，比如 lock_a 必须在 lock_b 之前获取。如果所有线程都遵循这个规则，就不会形成循环等待。

死锁避免 (Deadlock Avoidance)

各种死锁预防方法能够防止发生死锁，但必然会降低系统并发性，导致低效的资源利用率。

在运行时动态检查资源分配状态，以确保永远不会进入不安全状态（即可能导致死锁的状态）。

死锁避免是一种运行时的、动态的方法。它不阻止四个必要条件的出现，而是在每次分配资源时，都通过算法动态检查是否会进入“不安全状态”。

工作原理：死锁避免算法（如银行家算法）会评估每一个资源请求。只有当本次分配后系统仍然处于一个安全状态（即存在一个进程执行序列，能让所有进程最终都能完成）时，才会满足该请求。如果分配会导致不安全状态，则该请求会被拒绝，进程进入等待。

这种方法更加灵活，因为它允许四个必要条件存在。它试图在满足进程请求的同时，找到一个安全的分配路径，从而提高资源利用率。

然而，它的缺点也很明显：它需要预先知道每个进程可能需要的最大资源量，这在许多实际应用中是很难实现的。此外，动态的检查也会带来一定的额外开销。

死锁避免和死锁预防是两种不同的策略，它们都旨在阻止死锁的发生，但采用的方式和时机不同。

死锁预防和死锁避免主要区别如下:

	死锁预防 (Prevention)	死锁避免 (Avoidance)
策略	事前、静态	运行时、动态
目标	破坏死锁的四个必要条件	确保系统不会进入不安全状态
实现方式	严格的规则，例如： 一次性申请所有资源、按顺序申请资源	复杂的算法，例如：银行家算法
优点	简单、有效	资源利用率高、并发性好
缺点	降低资源利用率和并发性	需要预知进程最大需求，且有额外开销
应用场景	适用于简单、资源竞争不复杂 的系统或编程规范	适用于对资源利用率要求高的特定系统 （如某些数据库）

银行家算法 (Banker’s Algorithm)

银行家算法是由荷兰计算机科学家 Edsger Dijkstra 在 1965 年提出的。它的核心思想是模拟银行贷款的过程：银行家在发放贷款（分配资源）之前，会检查是否能确保所有客户（进程）最终都能还清贷款（完成执行）。如果本次分配可能导致银行无法收回所有贷款，那么这次请求就会被拒绝。

算法的工作原理：

银行家算法需要系统维护三个关键的数据结构来判断是否处于安全状态：

• Available: 一个向量，记录每种资源类型当前可用的实例数量。
• Max: 一个矩阵，记录每个进程可能需要的最大资源实例数量。
• Allocation: 一个矩阵，记录每个进程当前已经分配了的资源实例数量。
• Need: 一个矩阵，表示每个进程还需要多少资源才能完成（Need = Max - Allocation）。

算法的两个核心步骤：

1. 安全性检查算法 (Safety Algorithm)

   这是银行家算法的主体，用来判断当前系统状态是否安全。一个系统处于安全状态意味着存在一个安全序列，能让所有进程最终都能完成执行。

   • 初始化两个向量：Work（可用资源）和 Finish（标记进程是否完成）。
   • 寻找一个未完成的进程 $ P_i $,（即 Finish[i] 为假），且其所需资源 Need[i] 小于等于 Work。
   • 如果找到了这样的进程，就假设它完成执行，并释放其所有资源。将 Work 更新为 Work + Allocation[i]，并标记 Finish[i] 为真。
   • 重复步骤 2 和 3，直到找不到满足条件的进程。
   • 判断：如果所有进程的 Finish 标记最终都变为真，说明找到了一个安全序列，系统处于安全状态。否则，系统处于不安全状态。

2. 资源请求算法 (Resource-Request Algorithm)

   当一个进程 $ P_i $ 请求资源时，系统会执行这个算法来决定是否批准请求。

   • 首先，检查请求的资源量 Request[i] 是否超过了该进程的最大需求 Need[i]。如果超过，说明请求无效。
   • 然后，检查请求的资源量 Request[i] 是否小于等于当前可用资源 Available。如果不是，进程需要等待。
   • 如果以上两个条件都满足，系统会预先假设资源被分配：
     • Available = Available - Request[i]
     • Allocation[i] = Allocation[i] + Request[i]
     • Need[i] = Need[i] - Request[i]
   • 最后，运行安全性检查算法。
     • 如果结果是安全状态，那么本次资源分配是安全的，可以真正执行。
     • 如果结果是不安全状态，那么系统会回滚之前的假设，不进行资源分配，进程 $ P_i $ 需要等待。

银行家算法的优缺点

优点：

• 高资源利用率：相比死锁预防，它允许更高的并发性，因为它只在必要时才阻止请求。
• 有效避免死锁：它能从根本上避免死锁的发生，前提是能获取所有必要信息。

缺点：

• 需要预知最大需求：这是最大的局限性。在实际系统中，很难预先知道每个进程可能需要的最大资源量。
• 性能开销：每次请求都需要运行一次安全性检查，这会增加系统的开销。
• 进程数量和资源类型固定：算法要求系统中进程和资源类型数量相对固定，不适合频繁创建和销毁进程的动态系统。 **

由于这些限制，银行家算法在通用操作系统中很少被直接实现。然而，它的思想（即通过检查安全性来避免死锁）被广泛应用于数据库系统等对资源管理要求较高的特定领域，或者作为教学和理解死锁避免概念的经典案例。

死锁检测和恢复 (Deadlock Detection and Recovery)

这种方法允许系统进入死锁状态，但会定期运行算法来检测是否存在死锁，一旦发现，则采取措施解除死锁，比如终止一个或多个进程，或者剥夺某些进程的资源，直到死锁解除。

工作原理：

• 死锁检测：系统维护一个资源分配图，定期（或当资源请求失败时）检查图中是否存在循环。如果存在，则表明发生了死锁。
• 死锁恢复：一旦检测到死锁，可以采取以下一种或多种方法来解除它：
• 终止进程：终止所有死锁进程，或者选择性地终止一个或多个进程，直到死锁解除。选择终止的进程通常基于一些标准，如优先级、已经执行的时间、剩余完成时间等。
• 资源剥夺：从一个或多个死锁进程中抢占（剥夺）资源，然后将这些资源分配给其他进程。被剥夺资源的进程需要回滚到之前的安全状态并重新开始。

优点：不需要任何先验信息，且资源利用率高。

缺点：检测和恢复需要额外的开销，且终止进程或剥夺资源可能会导致工作丢失。在许多系统中，这种方法被用于处理一些非关键性的死锁。

死锁检测算法

• 如果进程 - 资源分配图中无环路，此时系统没有发生死锁。
• 如果进程 - 资源分配图中有环路，则可分为以下两种情况：
  • 每种资源类中仅有一个资源，则系统发生了死锁。此时，环路是系统发生死锁的充分必要条件，环路中的进程就是死锁进程。
  • 每种资源类中有多个资源，则环路的存在只是产生死锁的必要不充分条件，系统未必会发生死锁。

每种资源类中仅有一个资源的死锁检测

上图为资源分配图，其中方框表示资源，圆圈表示进程。资源指向进程表示该资源已经分配给该进程，进程指向资源表示进程请求获取该资源。

图 a 可以抽取出环，如图 b，它满足了环路等待条件，因此会发生死锁。

比如：进程D需要的资源是U、T；进程G需要的资源是V、U；进程E需要的资源是T、V

此时进程D占有资源U，进程E占有资源T，进程G占有资源V

所以此时导致进程D、E、G所申请的资源不能得到全部满足，陷入死锁。

死锁检测算法：

每种类型一个资源的死锁检测算法是通过检测有向图是否存在环来实现，从一个节点出发进行深度优先搜索，对访问过的节点进行标记，如果访问了已经标记的节点，就表示有向图存在环，也就是检测到死锁的发生。

示例的实现代码如下

// 资源分配图的表示，可以是一个邻接列表或矩阵
Graph {
    nodes: list of all Processes and Resources
    edges: list of (source, destination) pairs
}

// 进程和资源的状态
enum Status {
    UNVISITED,  // 未访问
    VISITING,   // 正在访问（表示在当前递归路径上）
    VISITED     // 已访问
}

Map<Node, Status> visitedStatus;

// 主函数，用于检测整个图中是否存在死锁
function detectDeadlock(graph):
    // 初始化所有节点状态为 UNVISITED
    for each node in graph.nodes:
        visitedStatus[node] = UNVISITED

    // 遍历所有节点，从每个未访问的节点开始进行深度优先搜索
    for each node in graph.nodes:
        if visitedStatus[node] == UNVISITED:
            // 如果DFS返回true，说明找到了一个环，即死锁
            if isCyclic(node, graph):
                return true
    
    // 遍历结束，没有找到环路
    return false

// 递归函数，用于在图中寻找环路
function isCyclic(currentNode, graph):
    // 将当前节点标记为 VISITING，表示它在当前的遍历路径上
    visitedStatus[currentNode] = VISITING

    // 遍历当前节点的所有邻居
    for each neighbor in graph.neighbors(currentNode):
        // 如果邻居是 VISITING 状态，说明我们回到了一个正在访问的节点，形成了一个环
        if visitedStatus[neighbor] == VISITING:
            return true
        
        // 如果邻居是 UNVISITED 状态，继续递归搜索
        if visitedStatus[neighbor] == UNVISITED:
            if isCyclic(neighbor, graph):
                return true

    // 当前节点的所有邻居都已访问过，且没有找到环，将当前节点标记为 VISITED
    // 并从当前递归路径中移除
    visitedStatus[currentNode] = VISITED
    return false

每种资源类中有多个资源的死锁检测

每个资源类用一个方框表示，方框中的原点表示此资源类中的各个资源；

每个进程用一个圆圈来表示，用有向边表示进程申请资源和资源分配情况。

约定方框→圆圈表示资源分配，圆圈→方框表示申请资源。

这种情况下，图3-6 发生了死锁，而图3-7没有发生死锁。

每种资源类中有多个资源的死锁检测情况下，死锁检测算法需要考虑资源的实例数量，而不仅仅是简单的请求和分配关系。

之前提到的基于图的环路检测算法（深度优先搜索）适用于资源类中只有一个实例的场景。但当资源有多个实例时，一个进程请求的资源可能会被另一个进程释放，从而打破死锁循环。

银行家算法思想的死锁检测

处理资源类中有多个实例的死锁问题，最常见且有效的方法是借鉴银行家算法的思想。这个方法不是通过寻找环路来判断死锁，而是通过检查是否存在一个安全的进程执行序列。

核心思想是：如果系统中所有进程都能在某个时间点得到所有所需的资源并完成执行，那么系统就是安全的，没有死锁。反之，如果无法找到这样的序列，则系统处于死锁状态。

下面是一个针对这种多实例资源情况的死锁检测伪代码实现。

数据结构

我们需要三个主要的数据结构来跟踪资源和进程的状态：

• Available[m]：一个大小为 m 的向量，表示每种资源类型当前可用的实例数量。
• Allocation[n][m]：一个大小为 n x m 的矩阵，表示每个进程当前已经分配了多少实例的资源。
• Request[n][m]：一个大小为 n x m 的矩阵，表示每个进程当前正在请求多少实例的资源。

n 是进程的数量。

m 是资源类型的数量。

function detectDeadlock(processes, resources):
    // 1. 初始化工作向量和完成标志
    // work: 拷贝当前可用资源数量
    // finish: 跟踪每个进程是否能完成，初始都为 false
    Work = Available
    Finish = array of booleans, size n, all initialized to false

    // 2. 寻找一个可以完成的进程
    // 循环 n 次，确保我们尝试了每个进程
    for i = 0 to n-1:
        // 寻找一个未完成的进程 (Finish[j] == false)
        // 且它请求的资源量小于等于当前可用资源 (Request[j] <= Work)
        for j = 0 to n-1:
            if Finish[j] == false and Request[j] <= Work:
                // 3. 如果找到这样的进程，模拟资源分配和释放
                // 将该进程已分配的资源加到可用资源中
                Work = Work + Allocation[j]
                // 标记该进程可以完成
                Finish[j] = true
                // 跳出内层循环，从头开始寻找下一个可以完成的进程
                // 确保我们可以检查所有进程
                j = 0 

    // 4. 检查所有进程是否都能完成
    // 遍历所有进程的完成标志
    for k = 0 to n-1:
        // 如果有任何一个进程的标志仍然是 false，说明它无法完成
        // 并且系统中存在死锁
        if Finish[k] == false:
            // 返回 true，并指出哪些进程处于死锁状态
            return true, "Deadlocked processes: " + list of deadlocked processes
    
    // 如果所有进程都能完成，则没有死锁
    return false, "No deadlock"

死锁恢复方案

死锁恢复方案一般有终止进程、剥夺资源、回滚、系统重启法这4种，但在实际的操作系统和数据库系统中，最常用的死锁恢复方法是终止进程。

数据库管理系统（DBMS）：由于数据库事务需要保持原子性和一致性，当发生死锁时，通常会选择一个或多个事务作为“牺牲品”并将其回滚（这本质上是一种终止），从而释放锁并解除死锁。

操作系统：当用户程序陷入死锁时，操作系统通常会检测到资源请求超时，然后强制终止该进程，并向用户报告错误。

虽然剥夺资源和回滚提供了更精细的控制，但它们的实现复杂性高，且可能导致性能问题。因此，在许多通用系统中，简单的“检测到死锁，然后终止进程”是性价比最高的解决方案。

终止进程

这是最直接也最常用的死锁恢复方法，通过牺牲一个或多个进程来解除死锁。

• 终止所有死锁进程：这是最简单粗暴的方法，直接终止所有参与死锁的进程。这会立即打破所有循环等待，解除死锁。
• 选择性地终止进程：系统可以根据一定的标准，选择性地终止一个或几个进程，直到死锁解除。终止的进程通常是那些“代价最小”的。选择标准可以包括：
  • 进程优先级：终止优先级较低的进程。
  • 已执行时间：终止已经执行了很长时间或刚开始执行的进程。
  • 已占用资源数量：终止已占用资源最少或最多的进程。
  • 所需资源数量：终止需要更多资源的进程，因为它们可能无法在短时间内完成。

剥夺资源

这种方法是强制从某个进程手中夺取资源，并将其分配给另一个死锁进程。被剥夺资源的进程通常需要回滚到之前的安全状态。

• 选择被剥夺资源的进程：系统需要选择一个合适的“牺牲品”进程，从它手中剥夺资源。选择标准类似于终止进程，通常基于优先级、已占用资源等。
• 回滚：被剥夺资源的进程不能简单地继续执行，因为它的状态可能已经不一致。因此，它必须回滚到检查点（checkpoint），即一个预先保存的、没有被剥夺资源的安全状态。然后，它才能从该点重新开始执行。

这种方法比较复杂，因为它需要操作系统有强大的状态保存和回滚机制。如果频繁发生回滚，会带来巨大的开销，因此在实践中不如终止进程常见

回滚

回滚是一种更通用的方法，它可以作为剥夺资源的一个组成部分，也可以单独用来恢复死锁。

• 完全回滚：当检测到死锁时，系统可以强制所有参与死锁的进程都回滚到它们执行之前的初始状态。这会立即释放所有已占用的资源，打破死锁。
• 部分回滚：只让某个“牺牲品”进程回滚，而不是全部。这通常和剥夺资源方法结合使用。

系统重启法

结束所有进程的执行并重新启动操作系统。这种方法很简单，但先前的工作全部作废，损失很大。一般不常用

死锁忽略 (Deadlock Ignorance)

这是大多数操作系统（如 Windows 和 macOS）采取的策略。它假设死锁极少发生，因此不做任何预防或检测。当死锁真的发生时，用户通常需要手动重启受影响的程序或系统来解决。

参考

• 死锁的产生、防止、避免、检测、解除