操作系统死锁的预防策略设计

死锁的基本概念与原理

死锁的定义

在操作系统中，死锁是指多个进程（或线程）在执行过程中，因争夺资源而造成的一种互相等待的现象，若无外力作用，这些进程（或线程）都将无法推进下去。例如，进程 A 持有资源 R1 并请求资源 R2，而进程 B 持有资源 R2 并请求资源 R1，此时 A 和 B 相互等待对方释放资源，从而陷入死锁状态。

死锁产生的四个必要条件

互斥条件：资源在某一时刻只能被一个进程所使用。例如，打印机在同一时间只能被一个进程占用进行打印任务，其他进程必须等待。
占有并等待条件：一个进程在请求新的资源的同时保持对某些资源的占有。比如，进程已经持有了部分内存空间，同时又请求磁盘空间，在获取磁盘空间之前，不会释放已占有的内存空间。
不可剥夺条件：进程已获得的资源，在未使用完之前，不能被其他进程强行剥夺，只能由该进程自己主动释放。例如，一个进程已经打开了一个文件进行读写操作，其他进程不能直接抢走这个文件的控制权。
循环等待条件：存在一个进程 - 资源的循环链，链中的每个进程都在等待下一个进程所占用的资源。假设有进程 P1、P2、P3，P1 等待 P2 占有的资源，P2 等待 P3 占有的资源，P3 又等待 P1 占有的资源，这就形成了一个循环等待，可能导致死锁。

死锁的影响

死锁的发生会严重影响操作系统的性能和稳定性。它不仅会使参与死锁的进程无法继续执行，浪费系统资源，而且可能导致整个系统的瘫痪。特别是在一些对实时性要求较高的系统中，如航空交通管制系统、医疗监护系统等，死锁的出现可能会带来灾难性的后果。

死锁预防策略的总体思路

死锁预防策略的核心思想是通过破坏死锁产生的四个必要条件中的一个或多个，来防止死锁的发生。由于互斥条件在很多情况下是资源本身的特性决定的，难以改变，例如打印机的独占使用特性，因此通常从占有并等待、不可剥夺和循环等待这三个条件入手设计预防策略。

破坏占有并等待条件

静态分配策略

策略描述：静态分配策略要求进程在启动之前一次性申请它所需要的全部资源。只有当系统能够满足该进程的所有资源请求时，才会分配资源并允许进程开始执行。在进程执行过程中，不会再请求新的资源。例如，一个进程需要使用打印机、内存空间和磁盘空间，在进程启动前，系统检查这些资源是否足够，如果足够则一次性分配给该进程，进程在运行期间不再申请其他资源。
实现方式：在操作系统的资源管理模块中，可以维护一个资源分配表，记录每个进程申请的资源以及系统中可用的资源。当一个进程请求资源时，系统首先检查自身的资源分配表，判断是否有足够的资源满足该进程的全部请求。如果有，则将相应的资源分配给该进程，并更新资源分配表；如果没有，则该进程进入等待队列，直到有足够的资源可用。
优点与缺点
- 优点：这种策略简单直接，能够有效地破坏占有并等待条件，从而预防死锁的发生。因为进程在开始执行前已经获得了所有需要的资源，运行过程中不会出现一边占有资源一边等待其他资源的情况。
- 缺点：它可能导致资源利用率低下。例如，一个进程可能在很长时间内只使用部分已分配的资源，而其他进程因为资源被占用而无法运行。同时，对于一些无法提前确定所需全部资源的进程，这种策略可能无法适用。

资源分配图算法实现（以银行家算法为例）

算法背景：银行家算法是一种经典的资源分配与死锁预防算法，由 Dijkstra 于 1965 年提出。它模拟银行系统的资源分配过程，确保系统处于安全状态，避免死锁的发生。
数据结构定义
- 可利用资源向量 Available：这是一个数组，记录系统中每种资源的可用数量。例如，Available = [3, 3, 2] 表示系统中有 3 个资源类型 1，3 个资源类型 2 和 2 个资源类型 3 可供分配。
- 最大需求矩阵 Max：一个二维数组，Max[i][j] 表示进程 i 对资源类型 j 的最大需求数量。
- 分配矩阵 Allocation：也是一个二维数组，Allocation[i][j] 表示进程 i 当前已分配到的资源类型 j 的数量。
- 需求矩阵 Need：由 Max 和 Allocation 计算得出，Need[i][j] = Max[i][j] - Allocation[i][j]，表示进程 i 还需要的资源类型 j 的数量。
算法步骤
- 安全状态检测：系统初始时处于安全状态。首先，假设存在一个进程序列 <P1, P2, …, Pn>，使得每个进程 Pi 的 Need[i] <= Available。如果能找到这样一个序列，则系统处于安全状态；否则，系统处于不安全状态。
- 资源请求处理：当进程 Pi 请求资源时，假设请求向量为 Request[i]，系统按以下步骤进行处理：
  - 如果 Request[i] <= Need[i]，表示进程 Pi 的请求在其最大需求范围内，继续下一步；否则，报错，因为进程的请求超过了它声明的最大需求。
  - 如果 Request[i] <= Available，表示系统中有足够的资源满足进程 Pi 的请求，继续下一步；否则，进程 Pi 等待，因为资源不足。
  - 系统尝试分配资源，即 Available = Available - Request[i]；Allocation[i] = Allocation[i] + Request[i]；Need[i] = Need[i] - Request[i]。
  - 分配后，系统再次检测是否处于安全状态。如果是，则分配成功；如果不是，则撤销刚才的分配操作，进程 Pi 等待。
代码示例（以 Python 为例）

# 定义资源数量和进程数量
resource_num = 3
process_num = 5

# 可利用资源向量
available = [3, 3, 2]

# 最大需求矩阵
max_need = [
    [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]
]

# 计算需求矩阵
need = []
for i in range(process_num):
    need.append([max_need[i][j] - allocation[i][j] for j in range(resource_num)])


def is_safe():
    work = available.copy()
    finish = [False] * process_num
    safe_sequence = []

    while True:
        found = False
        for i in range(process_num):
            if not finish[i] and all(need[i][j] <= work[j] for j in range(resource_num)):
                work = [work[j] + allocation[i][j] for j in range(resource_num)]
                finish[i] = True
                safe_sequence.append(i)
                found = True
        if not found:
            break
    return finish == [True] * process_num, safe_sequence


def request_resources(process_id, request):
    if all(request[j] <= need[process_id][j] for j in range(resource_num)):
        if all(request[j] <= available[j] for j in range(resource_num)):
            available[:] = [available[j] - request[j] for j in range(resource_num)]
            allocation[process_id][:] = [allocation[process_id][j] + request[j] for j in range(resource_num)]
            need[process_id][:] = [need[process_id][j] - request[j] for j in range(resource_num)]
            is_safe_state, sequence = is_safe()
            if is_safe_state:
                print(f"资源分配成功，安全序列: {sequence}")
            else:
                # 撤销分配
                available[:] = [available[j] + request[j] for j in range(resource_num)]
                allocation[process_id][:] = [allocation[process_id][j] - request[j] for j in range(resource_num)]
                need[process_id][:] = [need[process_id][j] + request[j] for j in range(resource_num)]
                print("分配后系统处于不安全状态，分配失败")
        else:
            print("资源不足，进程等待")
    else:
        print("进程请求超过最大需求，报错")


# 示例请求
request_resources(0, [0, 1, 0])

优点与缺点
- 优点：银行家算法能够在资源分配过程中动态地检测系统是否处于安全状态，避免死锁的发生。它允许进程动态地请求资源，相比静态分配策略，资源利用率有所提高。
- 缺点：算法需要记录每个进程的最大需求、已分配资源和需求资源等信息，增加了系统的开销。同时，它假设每个进程的最大资源需求是已知的，这在实际应用中可能不太现实，对于一些无法提前确定最大需求的进程，该算法的应用受到限制。

破坏不可剥夺条件

剥夺式分配策略

策略描述：剥夺式分配策略允许操作系统在必要时剥夺进程已占有的资源。当一个进程请求资源而系统资源不足时，操作系统可以选择从其他已占有资源的进程中剥夺部分资源，分配给请求进程。例如，在一个多进程的系统中，进程 A 持有一些内存资源，进程 B 由于更紧急的任务需要更多内存资源，操作系统可以从进程 A 中剥夺一部分内存资源给进程 B。
实现方式：在操作系统内核中，可以为每个资源类型设置一个优先级队列。当一个进程请求资源时，如果资源不足，系统检查是否可以从其他进程中剥夺资源。它会遍历所有持有该资源的进程，根据一定的优先级规则（如进程的优先级、进程已使用资源的时间等）选择一个进程进行资源剥夺。被剥夺资源的进程会被挂起，直到它重新获得足够的资源继续执行。
优点与缺点
- 优点：这种策略能够在一定程度上提高资源的利用率，及时满足紧急进程对资源的需求，避免因资源竞争导致的死锁。
- 缺点：实现较为复杂，需要合理设计资源剥夺的优先级规则，否则可能导致某些进程长期得不到足够的资源而饥饿。同时，频繁的资源剥夺会增加系统的开销，影响系统的性能。

破坏循环等待条件

资源分配顺序策略

策略描述：资源分配顺序策略为系统中的资源类型分配一个全局唯一的序号，规定进程只能按照序号递增的顺序请求资源。例如，系统中有资源 R1、R2、R3，分别分配序号 1、2、3，进程在请求资源时，只能先请求 R1，再请求 R2，最后请求 R3，不能逆序请求。这样就避免了循环等待条件的出现，因为按照递增顺序请求资源不可能形成循环。
实现方式：在操作系统的资源管理模块中，维护一个资源序号表。当进程请求资源时，系统检查请求的资源序号是否大于该进程已占有的所有资源的序号。如果是，则允许分配；否则，拒绝分配。例如，进程已经占有资源 R1（序号 1），现在请求资源 R2（序号 2），系统检查通过，允许分配；若请求 R0（假设序号 0），则拒绝分配。
优点与缺点
- 优点：这种策略简单易行，实现成本较低，能够有效地破坏循环等待条件，预防死锁。
- 缺点：它可能限制进程对资源的合理使用顺序，降低资源的利用率。例如，某些进程可能在逻辑上更适合先使用序号较大的资源，但由于该策略的限制，不得不先请求序号较小的资源，导致资源使用效率低下。同时，对于一些动态添加或删除资源类型的系统，维护资源序号表可能会变得复杂。

层次分配策略

策略描述：层次分配策略将资源划分为不同的层次，每个进程在获取资源时，必须先获取较低层次的资源，然后才能获取较高层次的资源。同一层次内的资源获取遵循一定的规则（如先来先服务）。例如，将系统资源分为硬件资源层、软件资源层，硬件资源层又可细分为 CPU、内存等，软件资源层可分为文件系统资源、数据库资源等。进程必须先获取 CPU、内存等硬件资源，才能获取文件系统资源等软件资源。
实现方式：操作系统维护一个资源层次结构表，记录每个资源所属的层次。当进程请求资源时，系统首先检查该资源的层次是否高于进程已占有的所有资源的层次。如果是，则检查同一层次内的资源分配规则（如是否有足够的空闲资源、是否符合先来先服务等），若满足条件则分配资源；否则拒绝分配。
优点与缺点
- 优点：这种策略相对灵活，既可以破坏循环等待条件预防死锁，又能在一定程度上适应不同进程对资源的使用逻辑。它通过层次划分，使资源分配更具结构性，便于管理。
- 缺点：确定合理的资源层次结构需要对系统和应用有深入的了解，划分不当可能导致资源利用率降低。同时，实现该策略需要额外的系统开销来维护资源层次结构表和处理不同层次间的资源分配逻辑。

不同死锁预防策略的综合比较与选择

资源利用率比较

静态分配策略：资源利用率较低，因为进程需要一次性申请所有资源，可能导致部分资源长时间闲置。
银行家算法：相比静态分配策略，资源利用率有所提高，它允许进程动态请求资源，只要系统处于安全状态就进行分配。
剥夺式分配策略：在满足紧急进程需求方面有优势，能提高资源的整体利用率，但频繁剥夺可能带来额外开销。
资源分配顺序策略和层次分配策略：这两种策略可能会因为限制资源请求顺序而降低资源利用率，尤其是资源分配顺序策略，对进程资源使用顺序的限制较为严格。

系统开销比较

静态分配策略：系统开销相对较小，只需要在进程启动前检查资源是否足够并进行一次性分配。
银行家算法：系统开销较大，需要维护多个数据结构（如 Available、Max、Allocation、Need），并在每次资源请求时进行复杂的安全状态检测。
剥夺式分配策略：实现复杂，需要维护资源优先级队列，进行资源剥夺和进程挂起恢复操作，系统开销较大。
资源分配顺序策略和层次分配策略：资源分配顺序策略实现简单，系统开销较小；层次分配策略需要维护资源层次结构表，处理不同层次资源分配逻辑，系统开销相对较大。

适用场景比较

静态分配策略：适用于进程所需资源能够提前确定且资源使用时间较短的场景，如一些简单的批处理作业。
银行家算法：适用于进程资源需求相对稳定且可预测的系统，如一些传统的数据库管理系统。
剥夺式分配策略：适用于对实时性要求较高的系统，如航空交通管制系统，能够及时满足紧急任务对资源的需求。
资源分配顺序策略：适用于资源类型相对固定且进程对资源请求顺序有一定规律的系统。
层次分配策略：适用于资源具有明显层次结构的系统，如大型企业级应用系统，其中硬件资源和软件资源有清晰的层次划分。

在实际操作系统设计中，需要根据系统的特点、应用场景以及对性能、稳定性的要求，综合选择合适的死锁预防策略，或者结合多种策略来达到更好的效果。例如，在一个既有实时任务又有常规任务的混合系统中，可以对实时任务采用剥夺式分配策略，对常规任务采用银行家算法或资源分配顺序策略，以兼顾实时性和资源利用率。