进程死锁的资源争夺根源剖析

进程死锁的基本概念

在操作系统中，进程是资源分配和调度的基本单位。多个进程在运行过程中需要竞争系统资源，如 CPU、内存、I/O 设备等。当多个进程彼此互相等待对方释放资源，而在得到对方释放的资源之前又都不会主动释放自己已占有的资源时，就会出现一种僵局，这就是进程死锁。

死锁一旦发生，相关进程会一直处于阻塞状态，无法继续推进，从而导致系统资源被无效占用，严重影响系统的性能和可用性。例如，在一个多线程的数据库应用程序中，线程 A 持有锁 L1 并等待锁 L2，而线程 B 持有锁 L2 并等待锁 L1，这就形成了死锁，使得数据库操作无法继续执行。

资源的分类与特性

可剥夺资源与不可剥夺资源

可剥夺资源：指系统可以将已分配给某个进程的资源强行收回，再分配给其他进程。例如 CPU 时间，操作系统可以通过调度算法暂停一个进程的执行，将 CPU 分配给其他进程。这类资源通常不会直接导致死锁，因为系统可以通过调度手段打破可能出现的僵持局面。
不可剥夺资源：一旦分配给某个进程，就不能被其他进程强行占用，只能由占有资源的进程自己主动释放。如打印机、磁带机等 I/O 设备，一旦进程获得并开始使用，其他进程必须等待该进程使用完毕并释放后才能获取。不可剥夺资源是死锁产生的重要因素之一，因为进程对这类资源的竞争容易导致互相等待的情况。

永久性资源与临时性资源

永久性资源：是指可供用户进程重复使用多次的资源，其性质是持续存在的，不会随进程的执行而消失。如内存空间、外存设备、打印机等。永久性资源的分配和回收遵循一定的规则，进程申请资源得到满足后使用，使用完毕后释放。如果在分配和回收过程中管理不当，就可能引发死锁。
临时性资源：也称为消耗性资源，是由某个进程产生，被另一进程使用一段时间后便无用的资源。最典型的例子是进程间通信时产生的消息，消息由发送进程产生，接收进程获取并处理后，该消息所占用的资源就可以被释放。临时性资源的使用和管理同样可能导致死锁，例如在消息传递系统中，如果消息的发送和接收顺序不当，就可能出现进程互相等待消息的死锁情况。

死锁产生的四个必要条件

互斥条件 进程对所分配到的资源进行排他性使用，即在一段时间内某资源只由一个进程占用。如果此时还有其他进程请求该资源，则请求者只能等待，直至占有资源的进程用毕释放。例如，打印机在某一时刻只能被一个进程使用，其他进程若要使用打印机，必须等待当前使用打印机的进程完成打印任务并释放打印机资源。互斥条件是资源本身的特性决定的，许多资源本身就具有排他性使用的要求，这是无法避免的。
占有并等待条件 一个进程已经占有了至少一个资源，但又提出了新的资源请求，而该资源已被其他进程占有，此时请求进程被阻塞，但对自己已获得的资源保持不放。比如，进程 A 已经获得了资源 R1，现在又请求资源 R2，而资源 R2 被进程 B 占有，进程 A 就会进入等待状态，但它并不会释放已经占有的资源 R1。这种情况下，如果多个进程都处于类似的占有并等待状态，就可能形成死锁。
不可剥夺条件 进程已获得的资源，在未使用完之前，不能被剥夺，只能在使用完时由自己释放。这与前面提到的不可剥夺资源相对应，如打印机一旦分配给某个进程，在该进程使用完毕之前，其他进程不能强行夺走。不可剥夺条件使得进程在持有资源的情况下可以持续占有，直到满足自己的需求后才释放，这在一定程度上增加了死锁发生的可能性。
循环等待条件 存在一种进程资源的循环链，链中的每一个进程已获得的资源同时被链中下一个进程所请求。例如，有三个进程 P1、P2、P3，P1 占有资源 R1 并请求资源 R2，P2 占有资源 R2 并请求资源 R3，P3 占有资源 R3 并请求资源 R1，这样就形成了一个循环等待的环，导致死锁。循环等待条件是死锁形成的直观表现，一旦检测到系统中存在这样的循环等待关系，就可以判断可能发生了死锁。

资源分配图与死锁检测

资源分配图的定义 资源分配图（Resource Allocation Graph，RAG）是描述系统中进程和资源之间关系的一种有向图。它由节点和边组成，节点分为两类：进程节点（用圆圈表示）和资源节点（用方框表示）。边也分为两类：请求边（从进程节点指向资源节点，表示进程请求该资源）和分配边（从资源节点指向进程节点，表示该资源已分配给此进程）。例如，假设有进程 P1 和 P2，资源 R1 和 R2，若 P1 已分配到 R1 且请求 R2，P2 已分配到 R2 且请求 R1，那么在资源分配图中，就会有从 P1 到 R1 的分配边，从 P1 到 R2 的请求边，从 P2 到 R2 的分配边以及从 P2 到 R1 的请求边。
利用资源分配图检测死锁 通过对资源分配图进行化简来检测死锁。如果在资源分配图中，能够找到一个既不阻塞又非孤立的进程节点（即该进程的所有请求边都能通过分配现有资源来满足，且该进程不是孤立存在没有任何边与之相连），则可以消除与该进程相关的所有边，使该进程成为孤立节点。不断重复这个过程，如果最终所有进程节点都成为孤立节点，那么该资源分配图是可完全化简的，系统不存在死锁；反之，如果无法使所有进程节点都成为孤立节点，即存在不可化简的部分，那么系统就处于死锁状态。例如，在上述 P1、P2、R1、R2 的例子中，由于 P1 和 P2 相互请求对方已占有的资源，无法对资源分配图进行完全化简，所以系统处于死锁状态。

死锁预防策略

破坏互斥条件 由于许多资源本身的性质决定了其具有互斥性，如打印机、磁带机等 I/O 设备，很难真正破坏互斥条件。但在某些情况下，可以通过改变资源的使用方式来避免因互斥导致的死锁。例如，对于一些可以共享访问的文件资源，可以采用共享访问的模式，允许多个进程同时读取文件，而不是每次只允许一个进程访问，从而减少互斥使用带来的死锁风险。不过这种方法并不适用于所有资源，对于一些必须互斥使用的资源，此方法无法实施。
破坏占有并等待条件

静态分配策略：进程在启动前一次性申请它所需要的全部资源，只有当系统能够满足进程的所有资源请求时，才将这些资源分配给该进程，进程才能开始执行。这样就避免了进程在运行过程中因请求新资源而出现占有并等待的情况。例如，一个进程需要使用打印机、内存和磁盘空间，在启动前就一次性申请这些资源，如果系统资源不足无法满足其全部需求，则该进程等待，直到系统有足够资源分配给它。静态分配策略虽然能有效预防死锁，但会导致资源利用率降低，因为进程可能在很长时间内并不需要使用所有已分配的资源，却一直占用着，造成资源浪费。
逐步分配策略改进：进程在运行过程中可以逐步申请资源，但在申请新资源时，必须释放它已经占有的所有资源。例如，进程 A 已经获得了资源 R1，当它请求资源 R2 时，需要先释放 R1，若系统有 R2 资源，则分配给进程 A，进程 A 再重新申请并获取 R1。这种方法虽然能减少死锁发生的可能性，但实现起来较为复杂，并且进程在重新申请已释放资源时可能会面临资源竞争，导致性能下降。

破坏不可剥夺条件

高优先级剥夺策略：当一个进程占有了某些资源且请求新资源得不到满足时，系统可以剥夺该进程已占有的资源，分配给其他优先级更高的进程。例如，在实时操作系统中，对于一些紧急任务（如处理外部中断的进程）具有较高优先级，当这些高优先级进程需要资源时，系统可以强行剥夺低优先级进程已占有的资源。但这种方法可能导致低优先级进程长时间得不到资源，出现“饥饿”现象。
资源抢占与恢复策略：系统可以在一定条件下抢占进程占有的资源，但需要提供机制来恢复被抢占进程的执行状态。比如，在数据库系统中，当一个事务长时间占用锁资源且影响到其他重要事务执行时，系统可以抢占其锁资源，并记录该事务的执行状态，以便后续恢复该事务的执行。这种策略实现难度较大，需要精确记录进程的状态信息，并且恢复进程执行时可能会遇到数据一致性等问题。

破坏循环等待条件

资源分配顺序法：为系统中的资源分配一个线性顺序，例如为打印机、内存、磁盘等资源分别编号为 R1、R2、R3。进程在申请资源时，必须按照资源编号从小到大的顺序进行申请。假设进程 A 需要打印机（R1）和磁盘（R3），那么它必须先申请 R1，再申请 R3，而不能先申请 R3 再申请 R1。这样就不会形成循环等待的情况，从而预防死锁。这种方法实现相对简单，但可能会限制进程对资源的合理使用顺序，因为有些进程可能按照实际需求并不适合按照这种固定顺序申请资源，而且资源顺序的确定也需要综合考虑系统中各种资源的使用情况和依赖关系。

死锁避免策略

银行家算法的基本原理 银行家算法是一种经典的死锁避免算法，它基于系统资源分配的安全性检测。该算法把操作系统看作是银行家，操作系统管理的资源相当于银行家拥有的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。银行家在给用户贷款时，要考虑这笔贷款是否能保证用户最终能归还贷款，同时不会使银行陷入无法满足其他用户合理贷款需求的困境。同样，操作系统在分配资源给进程时，要检查此次分配是否能保证系统处于安全状态，即是否存在一种资源分配序列，使得所有进程都能在有限时间内完成任务。
银行家算法的数据结构

可利用资源向量 Available：它是一个含有 m 个元素的数组，其中的每一个元素代表一类可利用的资源数目，m 是系统中资源的种类数。例如，Available = [3, 3, 2] 表示系统中有 3 个 R1 资源、3 个 R2 资源和 2 个 R3 资源可供分配。
最大需求矩阵 Max：它是一个 n×m 的矩阵，定义了系统中 n 个进程对 m 类资源的最大需求。Max[i][j] 表示进程 i 对资源 j 的最大需求数量。比如，Max[2][1] = 5 表示进程 2 对资源 1 的最大需求是 5 个。
分配矩阵 Allocation：也是一个 n×m 的矩阵，反映当前系统中每类资源已分配给各个进程的数量。Allocation[i][j] 表示进程 i 当前已获得的资源 j 的数量。例如，Allocation[1][3] = 2 表示进程 1 已经获得了 2 个资源 3。
需求矩阵 Need：同样是 n×m 的矩阵，Need[i][j] = Max[i][j] - Allocation[i][j]，表示进程 i 还需要的资源 j 的数量。例如，已知 Max[3][2] = 7，Allocation[3][2] = 3，则 Need[3][2] = 4，即进程 3 还需要 4 个资源 2。

银行家算法的实现步骤

安全性检测：系统首先检查是否存在一个安全序列。安全序列是指系统按照某种顺序为每个进程分配资源，使得每个进程都能在有限时间内获得所需的全部资源并完成任务。具体做法是在当前状态下，寻找一个进程 Pi，使得 Need[i] <= Available，即进程 i 所需的资源小于等于当前可用资源。如果找到这样的进程，就假设将资源分配给它，即 Available = Available - Allocation[i]，Allocation[i] = Allocation[i] + Need[i]，Need[i] = 0，然后重复这个过程，检查是否能使所有进程的 Need 都变为 0。如果能找到这样一个序列，使得所有进程都能依次完成，那么系统处于安全状态，否则系统处于不安全状态。
资源请求处理：当进程 Pi 发出资源请求 Request[i] 时，系统首先检查 Request[i] <= Need[i]，即请求的资源不能超过它还需要的资源。然后检查 Request[i] <= Available，即请求的资源不能超过当前可用资源。如果这两个条件都满足，系统暂时将资源分配给进程 Pi，即 Available = Available - Request[i]，Allocation[i] = Allocation[i] + Request[i]，Need[i] = Need[i] - Request[i]。接着进行安全性检测，如果分配后系统仍然处于安全状态，则实际分配资源；否则，撤销此次分配，进程 Pi 等待。例如，假设有三个进程 P0、P1、P2，资源类型有 R0、R1、R2，Available = [3, 3, 2]，Max = [[7, 5, 3], [3, 2, 2], [9, 0, 2]]，Allocation = [[0, 1, 0], [2, 0, 0], [3, 0, 2]]，此时进程 P0 发出请求 Request[0] = [0, 1, 0]。首先检查 Request[0] <= Need[0]（Need[0] = Max[0] - Allocation[0] = [7, 4, 3]）且 Request[0] <= Available，满足条件。暂时分配后 Available = [3, 2, 2]，Allocation[0] = [0, 2, 0]，Need[0] = [7, 3, 3]。然后进行安全性检测，若能找到安全序列，则实际分配，否则恢复原状态，P0 等待。

死锁检测与恢复策略

死锁检测算法

基于资源分配图算法：如前文所述的资源分配图化简法，通过对资源分配图进行不断化简来检测死锁。在实际系统中，需要定期或在特定事件发生时（如资源请求长时间得不到满足）对资源分配图进行检测。这种方法直观易懂，但对于大型复杂系统，资源分配图的维护和化简计算量较大。
基于状态向量算法：系统维护一个全局的状态向量，记录每个进程的资源请求和分配情况。通过分析状态向量中进程之间的依赖关系来检测死锁。例如，记录每个进程已占有的资源、请求的资源以及其他进程对这些资源的分配情况，通过比较和分析这些信息，判断是否存在循环等待等死锁条件。这种方法相对资源分配图算法，在数据结构和计算方式上有所不同，适用于不同的系统架构和应用场景。

死锁恢复策略

终止进程法：当检测到死锁后，选择终止一个或多个死锁进程来打破死锁。可以选择终止那些优先级较低、已运行时间较短、占用资源较少的进程，以减少系统的损失。例如，在一个多任务系统中，若检测到死锁，发现某个后台辅助进程参与了死锁，且该进程优先级较低，那么可以终止该进程，释放其占有的资源，使其他进程能够继续执行。但这种方法可能会导致被终止进程的任务无法完成，需要根据具体应用场景进行权衡。
资源剥夺法：从参与死锁的进程中剥夺部分或全部资源，分配给其他进程，以打破死锁。与死锁预防中破坏不可剥夺条件类似，但这里是在死锁已经发生后进行的操作。例如，在数据库系统中，从死锁的事务中剥夺锁资源，分配给其他等待的事务，同时需要记录被剥夺资源进程的状态，以便后续恢复。资源剥夺法实现较为复杂，需要处理资源状态的保存和恢复以及数据一致性等问题。

代码示例

以下以 Python 为例，模拟一个简单的多进程资源竞争场景，可能会出现死锁情况，然后通过修改代码来预防死锁。

import multiprocessing
import time


# 模拟资源
class Resource:
    def __init__(self, name):
        self.name = name
        self.is_available = True


# 进程函数
def process(resource1, resource2):
    while True:
        if resource1.is_available:
            resource1.is_available = False
            print(f"{multiprocessing.current_process().name} 获得 {resource1.name}")
            time.sleep(1)
            if resource2.is_available:
                resource2.is_available = False
                print(f"{multiprocessing.current_process().name} 获得 {resource2.name}")
                # 模拟使用资源
                time.sleep(2)
                resource2.is_available = True
                print(f"{multiprocessing.current_process().name} 释放 {resource2.name}")
            resource1.is_available = True
            print(f"{multiprocessing.current_process().name} 释放 {resource1.name}")
        time.sleep(1)


if __name__ == '__main__':
    res1 = Resource('R1')
    res2 = Resource('R2')
    p1 = multiprocessing.Process(target=process, args=(res1, res2))
    p2 = multiprocessing.Process(target=process, args=(res2, res1))
    p1.start()
    p2.start()
    p1.join()
    p2.join()

在上述代码中，两个进程 p1 和 p2 分别尝试获取 res1 和 res2 资源，由于获取顺序不一致，很可能会出现死锁。

为了预防死锁，可以采用资源分配顺序法，为资源设定顺序，进程按照顺序申请资源。修改后的代码如下：

import multiprocessing
import time


# 模拟资源
class Resource:
    def __init__(self, name):
        self.name = name
        self.is_available = True


# 进程函数
def process(resource1, resource2):
    while True:
        # 按照固定顺序申请资源
        if resource1.name < resource2.name:
            first, second = resource1, resource2
        else:
            first, second = resource2, resource1
        if first.is_available:
            first.is_available = False
            print(f"{multiprocessing.current_process().name} 获得 {first.name}")
            time.sleep(1)
            if second.is_available:
                second.is_available = False
                print(f"{multiprocessing.current_process().name} 获得 {second.name}")
                # 模拟使用资源
                time.sleep(2)
                second.is_available = True
                print(f"{multiprocessing.current_process().name} 释放 {second.name}")
            first.is_available = True
            print(f"{multiprocessing.current_process().name} 释放 {first.name}")
        time.sleep(1)


if __name__ == '__main__':
    res1 = Resource('R1')
    res2 = Resource('R2')
    p1 = multiprocessing.Process(target=process, args=(res1, res2))
    p2 = multiprocessing.Process(target=process, args=(res2, res1))
    p1.start()
    p2.start()
    p1.join()
    p2.join()

通过这种方式，无论进程以何种顺序启动，都按照固定的资源顺序申请资源，从而避免了循环等待导致的死锁。

不同策略的应用场景与比较

死锁预防策略的应用场景

破坏互斥条件：适用于那些原本需要互斥使用，但可以通过技术手段改变为共享使用的资源，如某些文件系统资源。在分布式文件系统中，可以采用一些一致性协议，使得多个进程能够同时读取文件，减少因互斥访问文件带来的死锁风险。
破坏占有并等待条件：静态分配策略适用于对资源需求明确且资源使用时间较短的进程，如一些简单的批处理任务，它们在启动前可以确定所需的全部资源，并且运行时间相对较短，采用静态分配不会过多浪费资源。逐步分配策略改进适用于对资源需求有阶段性特点的进程，这些进程在运行过程中逐步申请资源，但又希望减少死锁风险。
破坏不可剥夺条件：高优先级剥夺策略适用于实时系统，在实时系统中，高优先级任务需要及时响应，通过剥夺低优先级进程的资源来保证高优先级任务的执行。资源抢占与恢复策略适用于对数据一致性要求较高的系统，如数据库系统，在保证数据一致性的前提下，通过抢占和恢复资源来避免死锁。
破坏循环等待条件：资源分配顺序法适用于资源种类相对固定且资源使用顺序有一定规律的系统。例如，在一个工业自动化控制系统中，设备资源的使用顺序相对固定，通过为设备资源编号并按照编号顺序申请资源，可以有效预防死锁。

死锁避免策略的应用场景 银行家算法适用于系统资源数量相对稳定，进程对资源的需求可以预先估计的场景。例如，在一些科学计算集群系统中，用户提交的计算任务对资源的需求在任务提交时可以明确告知系统，系统可以采用银行家算法来分配资源，避免死锁的同时提高资源利用率。但银行家算法需要系统实时维护大量的状态信息，对于资源动态变化频繁、进程数量众多的系统，计算开销较大。
死锁检测与恢复策略的应用场景 死锁检测与恢复策略适用于那些死锁发生概率较低，但一旦发生死锁对系统影响较大的系统。例如，在航空交通管制系统中，死锁发生的可能性较小，但如果发生死锁可能会导致严重的后果，因此可以采用死锁检测与恢复策略，定期检测死锁并及时恢复系统。死锁检测算法中的基于资源分配图算法适用于资源关系相对直观的系统，而基于状态向量算法适用于资源关系复杂但易于通过状态向量描述的系统。死锁恢复策略中的终止进程法适用于对进程任务完整性要求不高，死锁发生后希望尽快恢复系统运行的场景；资源剥夺法适用于对数据一致性要求较高，希望在恢复系统运行的同时尽量保留进程执行状态的场景。
策略比较 死锁预防策略通过限制资源分配方式来避免死锁的发生，优点是能够从根本上杜绝死锁，但可能会降低资源利用率和系统性能。例如，静态分配策略可能导致资源长时间被占用而不使用。死锁避免策略在资源分配过程中通过安全性检测来避免进入不安全状态，从而防止死锁，它在一定程度上提高了资源利用率，但计算开销较大，需要维护复杂的数据结构和进行频繁的安全性检测。死锁检测与恢复策略允许系统在运行过程中可能出现死锁，但通过检测和恢复机制来处理死锁，这种策略对系统正常运行的干扰较小，资源利用率相对较高，但检测和恢复操作本身也需要一定的开销，并且可能会对进程任务造成一定影响，如终止进程法可能导致进程任务无法完成。在实际应用中，需要根据系统的特点、资源的性质、进程的需求以及对系统性能和可靠性的要求等多方面因素综合选择合适的死锁处理策略。