操作系统（OS）中的银行家算法

有一种称为银行家算法的算法，用于在处理计算机系统中向进程安全分配资源时消除死锁。它将所有资源分配给每个进程，并避免资源分配冲突。

银行家算法概述

• “S 状态”在决定是否应将资源分配给任何进程之前，会检查所有可能的测试或活动。
• 它使操作系统能够在所有进程之间共享资源，而不会产生死锁或任何危急情况。
• 该算法因其模仿了银行决定是否可以安全批准贷款的过程而得名。

现实生活中的例子

假设一家银行拥有 T 数量的资金和 n 个账户持有人。在某个时刻，当其中一个账户持有人请求贷款时

• 银行会从可用于任何进一步取款的总金额中提取所请求的现金金额。
• 银行会检查可供取款的现金是否足以满足所有未来的请求/取款。
• 如果有足够的可用资金（也就是说，可用现金大于 T），银行就会发放贷款。
• 这确保了银行在收到后续申请时不会遇到运营问题。

操作系统中的银行家算法

同样，在操作系统中

• 当一个新进程创建时，它需要提供所有重要信息，例如哪些进程计划很快运行、资源请求和潜在的延迟。
• 这些信息有助于操作系统决定需要按何种顺序执行进程以避免任何死锁。
• 由于为防止死锁而应发生的执行顺序是确定的，因此银行家算法通常被认为是操作系统中的死锁避免或死锁检测算法。

优点

以下是银行家算法的基本特征

1. 它包含满足每个进程要求的各种资源。
2. 每个进程都应向操作系统提供有关即将到来的资源请求、资源数量以及资源将持有多久的信息。
3. 它帮助操作系统管理和控制计算机系统中每种资源类型的进程请求。
4. 该算法有一个最大资源属性，表示每个进程可以在系统中持有的最大资源数量。
5. 这意味着在银行家算法中，只有在分配这些资源时没有死锁可能性的情况下，才会授予资源。因此，它确保了系统以最佳性能运行。
6. 该算法可以避免任何进程无意义地持有资源，因为它实际上会检查授予资源是否可行。
7. 由于银行家算法在分配资源之前会分析所有潜在问题，因此其实现使操作系统更加稳定和可靠。

缺点

1. 它需要固定数量的进程，并且在执行进程时不能在系统中启动其他进程。
2. 该算法不再允许进程在处理其任务时交换其最大需求。
3. 每个进程都必须事先知道并声明其对系统的最大资源需求。
4. 资源请求可以在有限的时间内被授予，但分配资源的期限为一年。
5. 管理该算法可能相当复杂，这在拥有大量进程和资源的系统中尤为突出。这因此会导致开销增加。
6. 在动态环境中，进程和资源需求经常变化，银行家算法被证明过于僵化，无法很好地处理动态资源分配。
7. 由于该算法在分配资源之前每一步都在检查安全状态，因此它往往非常消耗内存和处理能力，对于大型系统而言效率不高。

使用银行家算法时，它需要了解三件事

1. 每个进程可以为系统中的每种资源请求多少。它用 [MAX] 请求表示。
2. 每个进程当前在系统中持有多少资源。它用 [ALLOCATED] 资源表示。
3. 它表示系统中当前可用的每种资源的数量。它用 [AVAILABLE] 资源表示。

银行家算法中的重要数据结构

假设 n 是进程的数量，m 是计算机系统中使用的每种资源类型的数量。

1. Available（可用资源）：它是一个长度为 'm' 的数组，定义了系统中可用的每种资源类型。当 Available[j] = K 时，表示系统中有 'K' 个资源类型 R[j] 的实例可用。
2. Max（最大需求）：它是一个 [n x m] 矩阵，表示每个进程 P[i] 在系统中可以存储的最大资源 R[j]（每种类型）数量。
3. Allocation（已分配资源）：它是一个 m x n 阶的矩阵，表示当前分配给系统中每个进程的资源类型。当 Allocation [i, j] = K 时，表示进程 P[i] 当前在系统中分配了 K 个资源类型 R[j] 的实例。
4. Need（需求）：它是一个 M x N 矩阵序列，表示每个进程剩余的资源数量。当 Need[i] [j] = k 时，则进程 P[i] 可能需要 K 个更多的资源类型 Rj 的实例来完成分配的工作。
   Need[i][j] = Max[i][j] - Allocation[i][j]。
5. Finish（完成）：它是一个阶为 m 的向量。它包含一个布尔值（true/false），指示进程是否已被分配到请求的资源，并且在完成其任务后是否已释放所有资源。

银行家算法本质上是两个组成部分的组合

• 安全性算法：确定系统是否处于安全状态，这意味着所有进程最终都将被允许执行而不会出现任何死锁。
• 资源请求算法：它决定授予其他进程为自己分配更多资源的请求是否安全，且不违反安全性。

安全性算法

安全状态是指系统可以从该状态执行某个进程序列而不会发生死锁的状态。如果一个系统的所有进程都能以某种顺序安全地执行，那么该系统就是安全的。

这是一种安全性算法，用于检查系统是否处于安全状态或在银行家算法中遵循安全序列。

1. 在安全性算法中，有两个长度分别为 m 和 n 的向量 Work 和 Finish。

初始化

• Work：初始化 work = Available，其中 Available 是存储每种资源类型可用实例数量的数组。
• Finish：为每个进程初始化 Finish 数组，使得 Finish[i] = false；对于 i = 0, 1, 2, 3, 4… n - 1.，表示开始时没有进程完成。

2. 检查每种资源类型 [i] 的可用性状态，例如

如果 i 不存在，则转到第 4 步。

3. 如果进程 i 满足第 2 步中的条件，则通过更新 Work 向量来模拟分配

这将当前分配给进程 i 的资源加回到 Work 向量中，模拟进程完成后资源的释放。

返回第 2 步，检查下一个进程的资源可用性状态。

4. 如果 Finish[i] == true，则表示系统对所有进程都是安全的。

资源请求算法

资源请求算法描述了当进程请求资源时系统的行为。该算法将检查所请求的资源是否可以在不引起死锁的情况下分配。然后，该请求可以被描述为一个请求矩阵。

资源请求算法检查当一个进程对系统中的每种资源类型提出请求时，系统将如何表现，这表现为一个请求矩阵。

为每个进程 P[i] 创建一个资源请求数组 R[i]。如果资源请求_i [j] 等于 'K'，这意味着进程 P[i] 需要系统中资源类型 R[j] 的 'k' 个实例。

资源请求算法的步骤

1. 检查请求是否在进程的最大声明范围内

对于进程 P[i] 的每一次资源请求，算法都会检查请求的资源数量是否小于或等于该进程的需求（Need）。

如果条件成立，则继续下一步。否则，进程 P[i] 已超过其最大声明；请求被拒绝。

如果进程超过其最大声明，则违反了系统规则；该进程将不被允许继续进行。

2. 检查请求的资源是否可用

系统现在检查所请求的资源是否有足够的数量可用。这是通过将请求 [i] 与可用资源（Available）进行比较来完成的。

如果此条件满足，则继续下一步。如果不满足，则 P[i] 必须等待，直到所需资源变得可用。

这确保了系统不会分配它当前没有的资源，否则可能导致死锁或不安全状态。

3. 模拟资源分配

如果可用，系统会通过修改 Available、Allocation 和 Need 矩阵，将临时请求的资源分配给进程 P[i]。

4. 检查系统安全性

• 在分配所请求的资源后，系统运行安全性算法，以检查系统在该分配后是否仍然处于安全状态。
• 如果系统处于安全状态，则资源将永久分配给进程 P[i]。
• 假设系统进入不安全状态。在这种情况下，进程 P[i] 必须等待，并且系统必须通过恢复其 Available、Allocation 和 Need 矩阵的原始值来回滚到其先前的状态。

示例： 考虑一个包含五个进程 P1、P2、P3、P4、P5 和三种资源类型 A、B 和 C 的系统。资源类型如下：A 有 10 个实例，B 有 5 个实例，资源类型 C 有 7 个实例。

使用银行家算法回答以下问题

1. Need 矩阵的内容是什么？
2. 确定系统是否安全。
3. 如果进程 P1 发出资源请求 (1, 0, 0)，系统能否立即接受此请求？会发生什么？

答 1：Need 矩阵的内容如下

Need [i] = Max [i] - Allocation [i]
P1 的需求 (Need)：(7, 5, 3) - (0, 1, 0) = 7, 4, 3
P2 的需求 (Need)：(3, 2, 2) - (2, 0, 0) = 1, 2, 2
P3 的需求 (Need)：(9, 0, 2) - (3, 0, 2) = 6, 0, 0
P4 的需求 (Need)：(2, 2, 2) - (2, 1, 1) = 0, 1, 1
P5 的需求 (Need)：(4, 3, 3) - (0, 0, 2) = 4, 3, 1

因此，我们创建了 Need 矩阵的内容。

答 2：应用银行家算法

A、B 和 C 的可用资源分别为 3、3 和 2。

现在我们检查每个进程的每种资源请求是否可用。

步骤 1：对于进程 P1

Need <= Available

7, 4, 3 <= 3, 3, 2 条件为假。

因此，我们检查另一个进程 P2。

步骤 2：对于进程 P2

Need <= Available

1, 2, 2 <= 3, 3, 2 条件为真

新的可用资源 (New available) = 可用资源 (available) + 已分配资源 (Allocation)

(3, 3, 2) + (2, 0, 0) => 5, 3, 2

同样，我们检查另一个进程 P3。

步骤 3：对于进程 P3

P3 Need <= Available

6, 0, 0 < = 5, 3, 2 条件为假。

同样，我们检查另一个进程 P4。

步骤 4：对于进程 P4

P4 Need <= Available

0, 1, 1 <= 5, 3, 2 条件为真

新的可用资源 (New Available resource) = 可用资源 (Available) + 已分配资源 (Allocation)

5, 3, 2 + 2, 1, 1 => 7, 4, 3

同样，我们检查另一个进程 P5。

步骤 5：对于进程 P5

P5 Need <= Available

4, 3, 1 <= 7, 4, 3 条件为真

新的可用资源 (New available resource) = 可用资源 (Available) + 已分配资源 (Allocation)

7, 4, 3 + 0, 0, 2 => 7, 4, 5

现在，我们再次为进程 P1 和 P3 检查每种类型的资源请求。

步骤 6：对于进程 P1

P1 Need <= Available

7, 4, 3 <= 7, 4, 5 条件为真

新的可用资源 (New Available Resource) = 可用资源 (Available) + 已分配资源 (Allocation)

7, 4, 5 + 0, 1, 0 => 7, 5, 5

因此，我们检查另一个进程 P2。

步骤 7：对于进程 P3

P3 Need <= Available

6, 0, 0 <= 7, 5, 5 条件为真

新的可用资源 (New Available Resource) = 可用资源 (Available) + 已分配资源 (Allocation)

7, 5, 5 + 3, 0, 2 => 10, 5, 7

因此，我们执行银行家算法以找到安全状态和安全序列，如 P2、P4、P5、P1 和 P3。

答 3：系统是否能满足资源请求 (1,0,0)

对于进程 P1，可以使用银行家算法进行检查，如下所示

1. 检查请求是否在 P1 的最大声明范围内

如果请求的资源：(1,0,0) 小于或等于 P1 的需求（Need），则继续；否则，拒绝。

2. 检查系统是否有足够的可用资源来处理该请求

(1,0,0)。如果资源可用，则继续；否则，P1 应该等待。

3. 模拟资源分配

将资源临时分配给 P1，并使用安全性算法检查系统是否安全。如果系统安全，则授予请求。否则，取消分配并让 P1 等待。