银行家算法是操作系统中用于资源分配和死锁避免的重要算法。它的核心思想是确保系统中至少存在一个进程序列，使得每个进程都能获得所需的资源，完成执行任务，
- 它有助于防止程序陷入卡顿无法完成任务的情况。
- 它负责追踪每个程序所需的资源量以及系统当前的可用资源。
银行家算法的组成要素
为了实现银行家算法，我们需要使用以下 数据结构：
假设系统中有 ‘n‘ 个进程，以及 ‘m‘ 种资源类型。
1. 可用资源向量
- 这是一个长度为 ‘m‘ 的一维数组，表示每种类型的资源当前有多少可用。
- Available[ j ] = k 意味着系统当前有 ‘k‘ 个 Rj 类型的资源实例可用。
2. 最大需求矩阵
- 这是一个大小为 ‘nm‘ * 的二维数组，定义了系统中每个进程对资源的最大需求量。
- Max[ i, j ] = k 意味着进程 Pi 最多可能请求 ‘k‘ 个 Rj 类型的资源实例。
3. 分配矩阵
- 这是一个大小为 ‘nm‘ * 的二维数组，定义了当前每个进程已分配到的各类资源数量。
- Allocation[ i, j ] = k 意味着进程 Pi 当前已分得 ‘k‘ 个 Rj 类型的资源实例。
4. 需求矩阵
- 这是一个大小为 ‘nm‘ * 的二维数组，表示每个进程尚需的额外资源数量。
- Need [ i, j ] = k 意味着进程 Pi 当前还需要 ‘k‘ 个 Rj 类型的资源实例。
- Need [ i, j ] = Max [ i, j ] – Allocation [ i, j ]
Allocation 指定了当前已分配给进程 Pi 的资源，而 Need 指定了进程 Pi 为了完成任务可能还需要请求的额外资源。
银行家算法的关键概念
- 安全状态： 存在至少一个进程序列，使得每个进程都能获得所需的资源，完成执行，释放其占用的资源，从而允许其他进程最终完成，而不会进入死锁。
- 不安全状态： 尽管系统仍可以向某些进程分配资源，但无法保证所有进程都能在不造成潜在死锁的情况下完成。
不安全状态示例
让我们考虑一个包含三个进程（INLINECODEa8011574, INLINECODE7448bdd4, P3）和某类资源共 6 个实例的系统。假设情况如下：
- 该资源的当前可用实例数为：1
- 进程当前的资源分配情况为：
P1: 2P2: 3P3: 1
- 最大需求（每个进程最终可能请求的最大资源数）为：
P1: 4P2: 5P3: 3
在这种情况下：
> 需求 = 最大需求 – 已分配
最大需求
需求
—
—
4
2
5
2
3
2- P1 可能需要再多 2 个资源才能完成。
P2可能需要再多 2 个资源才能完成。P3可能需要再多 2 个资源才能完成。
然而，系统中只有 1 个可用资源。尽管目前没有任何进程发生死锁，但系统处于不安全状态，因为不存在一种资源分配序列能保证所有进程都能完成。
银行家算法主要由安全性算法和资源请求算法组成。
银行家算法的类型
银行家算法由以下两部分组成：
- 安全性算法
- 资源请求算法
1. 安全性算法
安全性算法用于检查系统是否处于 安全状态——即所有进程都能在不造成死锁的情况下完成。
步骤：
- 初始化：
- Work = Available（当前可用资源）
- Finish[i] = false（对于所有进程，表示尚未完成）
- 寻找一个满足以下条件的进程 Pi：
- Finish[i] = false
- Need[i] ≤ Work（所需资源可以被满足）
- 如果找到这样的进程：
- 假设分配资源给它：Work = Work + Allocation[i]
- 标记该进程已完成：Finish[i] = true
- 对剩余进程重复步骤 2
- 如果所有进程都被标记为完成（所有 Finish[i] = true），则系统是 安全的。
> 本质上，该算法通过模拟进程的完成过程，来验证所有进程是否能安全结束。
2. 资源请求算法
该算法用于决定是否可以安全地批准一个进程的资源请求。
步骤：
1. 检查请求是否超过进程的最大需求： 如果 Request[i] ≤ Need[i]，则继续；否则，报 错。
2. 检查资源是否可用： 如果 Request[i] ≤ Available，则继续；否…