进程管理中的死锁问题与解决方法

进程管理中的死锁问题

死锁的定义

在多道程序系统中，由于多个进程的并发执行，改善了系统资源的利用率并提高了系统的处理能力。然而，若多个进程因竞争资源而造成一种僵局（Deadlock），若无外力作用，这些进程都将无法向前推进。具体来说，死锁是指在一组进程中的各个进程均占有不会释放的资源，但因互相申请被其他进程所占用不会释放的资源而处于的一种永久等待状态。

例如，假设有两个进程 P1 和 P2，系统中有两个资源 R1 和 R2。P1 已经占用了 R1，并且申请 R2；而 P2 已经占用了 R2，并且申请 R1。此时，P1 和 P2 都在等待对方释放自己所需的资源，从而陷入死锁。

死锁产生的原因

竞争资源 系统中存在一些不可剥夺的资源，如打印机、磁带机等。当多个进程竞争这些资源时，如果分配策略不当，就可能导致死锁。例如，进程 A 和进程 B 都需要使用打印机和扫描仪，进程 A 先获得了打印机，进程 B 先获得了扫描仪，然后进程 A 申请扫描仪，进程 B 申请打印机，此时就可能产生死锁。
进程推进顺序不当 进程在运行过程中，请求和释放资源的顺序不当也可能导致死锁。例如，有三个进程 P1、P2、P3，以及三个资源 R1、R2、R3。进程 P1 占用 R1 并请求 R2，进程 P2 占用 R2 并请求 R3，进程 P3 占用 R3 并请求 R1。如果按照这种顺序推进，就会形成死锁。

死锁产生的必要条件

互斥条件 进程对所分配到的资源进行排他性使用，即在一段时间内某资源只由一个进程占用。如果此时还有其他进程请求该资源，则请求者只能等待，直至占有该资源的进程用毕释放。例如，打印机在某一时刻只能被一个进程使用，其他进程若要使用，必须等待正在使用打印机的进程释放。
占有并等待条件 进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源已被其他进程占有，此时请求进程被阻塞，但对自己已获得的资源保持不放。比如，进程在已经获得一部分内存空间的情况下，又请求磁盘空间，而磁盘空间被其他进程占用，该进程就会等待磁盘空间，同时不释放已占有的内存空间。
不可剥夺条件 进程已获得的资源，在未使用完之前，不能被剥夺，只能在使用完时由自己释放。例如，一个进程已经获得了一个文件的写权限，其他进程不能强行剥夺其写权限，除非该进程主动释放。
循环等待条件 在发生死锁时，必然存在一个进程——资源的环形链，即进程集合{P0，P1，P2，…，Pn}中的 P0 正在等待一个 P1 占用的资源；P1 正在等待 P2 占用的资源，……，Pn 正在等待已被 P0 占用的资源。

死锁的处理策略

死锁预防

死锁预防是通过破坏死锁产生的必要条件来防止死锁的发生。

破坏互斥条件 在某些情况下，可以通过允许资源共享来破坏互斥条件。然而，对于一些资源，如打印机，本质上就需要互斥使用，这种方法适用性有限。但对于一些数据资源，可以通过采用可重入代码等技术，允许多个进程同时访问，从而破坏互斥条件。
破坏占有并等待条件 一种方法是要求进程在开始执行前一次性申请它所需要的所有资源。例如，一个进程需要使用打印机和磁盘空间，那么在进程启动前就申请这两个资源，如果其中任何一个资源无法获取，则该进程不启动。这种方法虽然简单，但可能导致资源浪费，因为进程可能在很长时间内都不需要使用所有申请的资源。另一种方法是，当进程请求新的资源时，它必须先释放已占有的所有资源，然后重新申请所需的所有资源。例如，进程已经占用了内存空间，当它请求磁盘空间时，先释放内存空间，然后同时申请内存空间和磁盘空间。
破坏不可剥夺条件 允许操作系统剥夺死锁进程所占有的资源。例如，当一个进程占用了打印机资源但长时间不使用，而其他进程又急需使用打印机时，操作系统可以剥夺该进程的打印机资源分配给其他进程。实现这种方法需要确定剥夺资源的标准和方式，例如根据进程的优先级等。
破坏循环等待条件 对资源进行线性排序，并规定进程只能按照顺序申请资源。例如，系统中有资源 R1、R2、R3，规定进程只能先申请 R1，再申请 R2，最后申请 R3。如果一个进程需要 R2 和 R3，则必须先申请 R1（即使它可能并不需要使用 R1），这样可以避免循环等待。但这种方法可能会限制进程对资源的合理使用顺序，并且在实际系统中资源的排序可能并不容易确定。

死锁避免

死锁避免不像死锁预防那样通过破坏死锁的必要条件来防止死锁，而是在资源分配过程中，根据系统当前状态，通过某种算法来预测系统是否会进入不安全状态，从而避免死锁的发生。

系统安全状态 安全状态是指系统能按某种顺序如<P1，P2，…，Pn>（安全序列）为每个进程分配其所需资源，直至最大需求，使每个进程都可以顺利完成。若系统不存在这样一个安全序列，则称系统处于不安全状态。例如，系统中有三个进程 P1、P2、P3，它们对资源 R 的最大需求分别为 7、5、3，当前系统中资源 R 的可用数量为 3。进程 P1 已占用 2 个资源，进程 P2 已占用 1 个资源，进程 P3 已占用 0 个资源。此时，系统处于安全状态，因为可以先分配 1 个资源给 P3，P3 完成后释放 3 个资源，再分配给 P2，P2 完成后释放 5 个资源，最后分配给 P1，这样所有进程都能完成。
银行家算法 银行家算法（Banker's Algorithm）是一种最具有代表性的死锁避免算法。该算法的基本思想是：把操作系统比作银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。假设有 n 个进程{P1，P2，…，Pn}，m 类资源{R1，R2，…，Rm}。定义以下数据结构：

Available：长度为 m 的数组，表示当前各类资源的可用数量。
Max：n×m 的矩阵，表示每个进程对各类资源的最大需求。
Allocation：n×m 的矩阵，表示每个进程当前已分配到的各类资源数量。
Need：n×m 的矩阵，表示每个进程还需要的各类资源数量，Need[i][j] = Max[i][j] - Allocation[i][j]。

当进程 Pi 提出资源请求 Requesti 时，银行家算法按如下步骤进行检查： - 如果 Requesti[j] <= Need[i][j]，表示进程 Pi 申请的资源未超过其最大需求，继续下一步；否则，报错，因为进程 Pi 已经超出最大需求。 - 如果 Requesti[j] <= Available[j]，表示系统中有足够的资源满足进程 Pi 的请求，继续下一步；否则，进程 Pi 等待。 - 假设系统把资源分配给进程 Pi，即进行如下操作： - Available[j] = Available[j] - Requesti[j]； - Allocation[i][j] = Allocation[i][j] + Requesti[j]； - Need[i][j] = Need[i][j] - Requesti[j]； - 然后调用安全性算法检查系统是否处于安全状态。如果是安全状态，则真正分配资源；否则，撤销上述假设，进程 Pi 等待。

安全性算法步骤如下： - 设置两个向量：Work = Available，Finish[n] = false。 - 寻找一个满足以下条件的进程 i： - Finish[i] == false； - Need[i][j] <= Work[j] 对所有 j = 0，1，…，m - 1。 - 如果找到这样的进程 i，则： - Work[j] = Work[j] + Allocation[i][j]； - Finish[i] = true； - 回到第 2 步。 - 如果所有进程的 Finish[i] 都为 true，则系统处于安全状态；否则，系统处于不安全状态。

下面是银行家算法的简单代码示例（以 Python 语言为例）：

def is_safe(available, max_demand, allocation):
    need = [[max_demand[i][j] - allocation[i][j] for j in range(len(available))] for i in range(len(max_demand))]
    work = available.copy()
    finish = [False] * len(max_demand)
    count = 0

    while count < len(max_demand):
        found = False
        for i in range(len(max_demand)):
            if not finish[i] and all(need[i][j] <= work[j] for j in range(len(available))):
                work = [work[j] + allocation[i][j] for j in range(len(available))]
                finish[i] = True
                found = True
                count += 1
        if not found:
            break

    return all(finish)


def request_resources(available, max_demand, allocation, process, request):
    if any(request[j] > max_demand[process][j] - allocation[process][j] for j in range(len(available))):
        print("进程已超出最大需求")
        return False
    if any(request[j] > available[j] for j in range(len(available))):
        print("资源不足，进程等待")
        return False

    available = [available[j] - request[j] for j in range(len(available))]
    allocation[process] = [allocation[process][j] + request[j] for j in range(len(available))]
    max_demand[process] = [max_demand[process][j] - request[j] for j in range(len(available))]

    if is_safe(available, max_demand, allocation):
        print("分配成功，系统处于安全状态")
        return True
    else:
        print("分配后系统不安全，撤销分配")
        available = [available[j] + request[j] for j in range(len(available))]
        allocation[process] = [allocation[process][j] - request[j] for j in range(len(available))]
        max_demand[process] = [max_demand[process][j] + request[j] for j in range(len(available))]
        return False


# 示例数据
available = [3, 3, 2]
max_demand = [
    [7, 5, 3],
    [3, 2, 2],
    [9, 0, 2],
    [2, 2, 2],
    [4, 3, 3]
]
allocation = [
    [0, 1, 0],
    [2, 0, 0],
    [3, 0, 2],
    [2, 1, 1],
    [0, 0, 2]
]

# 进程 0 请求资源 [0, 1, 0]
request_resources(available, max_demand, allocation, 0, [0, 1, 0])

死锁检测与解除

死锁检测 死锁检测是在系统运行过程中，定期检查系统是否出现死锁。当系统资源的分配和释放比较频繁时，死锁检测算法需要能够快速准确地检测到死锁。死锁检测算法通常基于资源分配图算法。资源分配图是一种有向图，其中顶点分为两类：进程顶点和资源顶点。从进程顶点到资源顶点的有向边表示进程请求资源，从资源顶点到进程顶点的有向边表示资源分配给进程。死锁检测算法通过对资源分配图进行简化来判断是否存在死锁。如果经过一系列简化后，所有进程顶点都成为孤立顶点（即没有边与之相连），则系统不存在死锁；否则，系统存在死锁，并且死锁进程就是那些未被简化为孤立顶点的进程。
死锁解除 一旦检测到死锁，就需要采取措施解除死锁。
- 资源剥夺法：从其他进程剥夺足够数量的资源给死锁进程，以解除死锁状态。例如，从优先级较低的进程剥夺资源给死锁进程。但这种方法可能会影响被剥夺资源进程的运行。
- 撤销进程法：撤销一些死锁进程，直至死锁解除。可以选择撤销优先级较低的进程，或者撤销占用资源较多的进程。这种方法可能会导致被撤销进程的工作丢失，需要谨慎选择撤销的进程。
- 进程回退法：让一个或多个死锁进程回退到足以解除死锁的地步。这需要系统具有记录进程运行状态和资源分配历史的功能，以便能够回退到合适的状态。

不同处理策略的比较

死锁预防

死锁预防通过破坏死锁产生的必要条件来防止死锁，这种方法比较简单直接。然而，它往往是以牺牲系统资源利用率和进程并发性为代价的。例如，一次性申请所有资源的策略可能导致资源长时间闲置，而对资源进行线性排序可能限制了进程对资源的合理使用顺序。

死锁避免

死锁避免算法如银行家算法，能够在资源分配过程中动态地判断系统是否处于安全状态，从而避免死锁的发生。这种方法相对死锁预防来说，对系统资源利用率和进程并发性的影响较小。但是，银行家算法需要额外维护较多的数据结构，并且每次资源请求时都要进行复杂的计算和判断，增加了系统的开销。

死锁检测与解除

死锁检测与解除策略允许系统在运行过程中出现死锁，然后通过检测算法发现死锁并采取解除措施。这种方法不需要像死锁预防那样对资源分配进行严格限制，也不需要像死锁避免那样在每次资源请求时进行复杂的计算。但是，死锁检测算法本身也有一定的开销，并且死锁发生后对系统造成的影响可能已经比较严重，例如导致部分进程长时间等待，数据丢失等。

在实际的操作系统设计中，需要根据系统的特点和需求来选择合适的死锁处理策略。对于一些对数据一致性和可靠性要求极高的系统，可能更倾向于采用死锁预防或死锁避免策略；而对于一些对资源利用率要求较高，允许一定程度上出现死锁的系统，可以采用死锁检测与解除策略。同时，也可以综合使用多种策略，以达到更好的效果。例如，在系统初始化时采用死锁预防策略，在运行过程中结合死锁避免和死锁检测与解除策略，从而在保证系统稳定性的同时，提高资源利用率和进程并发性。