操作系统中的银行家算法

---

在计算机系统中，银行家算法用于避免死锁，以便可以安全地将资源分配给每个进程。之所以这样命名，是因为它可以用于银行系统，以确保银行永远不会分配其可用现金，以至于无法满足所有客户的要求。

在本文中，我们将详细讨论银行家算法。但在那之前，让我们了解一个与其类似的现实世界情况。

银行家算法：它是如何工作的？

让我们假设一家银行有“n”个账户，“M”是银行的总现金。如果客户申请贷款，则银行首先从可用的总现金中减去贷款金额，然后验证现金差额必须大于总现金“M”才能批准贷款。此过程帮助银行在没有任何限制的情况下管理和执行所有银行业务。

同样，银行家算法在计算机系统的操作系统中也适用。在计算机系统中，当一个新进程进入系统时。然后，该进程必须声明其可能需要执行的最大数量的每种资源类型的实例。此数字不得超过系统中资源的总数。现在，当一个新进程请求资源时，系统必须计算分配请求的资源是否会使计算机系统处于安全状态。如果是，则进程将获得分配的请求资源，否则它必须等待直到其他一些进程释放请求的资源。

通过遵循此实践，银行家算法避免了死锁并安全地分配了资源。因此，在操作系统中它也被称为死锁检测算法或死锁避免算法。

银行家算法中使用的数据结构

在计算机系统中，如果进程数等于“n”，资源类型数等于“m”。实现银行家算法需要以下四种数据结构：

• Available（可用） - 它是一个长度为“m”的向量，指示系统中每种类型的可用资源数量。如果 Available [j] = k，则“k”为系统中可用资源类型 R_j 的实例数。

• Max（最大） - 它是一个 [n × m] 矩阵，定义每个进程的最大资源需求。当 Max [I, j] = k 时，进程 P_i 可以请求资源类型 R_j 的最大 k 个实例。

• Allocation（分配） - 它也是一个 [n × m] 矩阵，定义当前分配给每个进程的每种类型的资源数量。因此，如果 Allocation [i, j] = k，则进程 P_i 当前分配了资源类型 R_j 的“k”个实例。

• Need（需求） - 它是一个 [n × m] 矩阵，表示每个进程剩余的资源需求。当 Need [i, j] = k 时，进程 P_i 可能需要资源类型 R_j 的“k”个更多实例才能完成分配的任务。

• Finish（完成） - 它是一个长度为“m”的矩阵。它包含一个布尔值，即 TRUE 或 FALSE，以指示是否已将进程分配给所需的资源，或者在完成分配的工作后所有资源是否都已释放。

此外，需要注意的是，

Need [i, j] = Max [i, j] – Allocation [i, j]

银行家算法是两种算法的组合，即安全算法和资源请求算法。这两种算法共同控制进程并避免系统死锁。

Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.

安全算法

安全算法用于确定系统是否处于安全状态。它遵循银行家算法中的以下安全顺序：

步骤 1

• 考虑两个分别命名为 Work 和 Finish 的向量，长度分别为“m”和“n”。

• 初始化：Work = Available

• Finish [i] = false；对于 i = 0, 1, 2, 3, 4, 5 … n。

步骤 2

• 找到“i”，使得 Finish [i] = false 且 Needi ≤ Work

• 如果不存在这样的“i”，则转到步骤 4。

步骤 3

• Work = Work + Allocation

• Finish [i] = true

• 转到步骤 2。

步骤 4

• 如果 Finish [i] 对所有“i”都为 true，则表示系统处于安全状态，否则处于不安全状态。

• 该算法需要 (m × n2) 次操作才能确定状态是安全还是不安全。

现在，让我们讨论资源请求算法。

资源请求算法

此算法确定系统在进程请求系统中每种类型的资源时如何运行。

让我们考虑一个进程 P_i 的请求向量 Requesti。当 Requesti [j] = k 时，进程 P_i 需要资源类型 R_j 的 k 个实例。

当进程 Pi 请求资源时，将遵循以下顺序：

步骤 1

如果 Requesti ≤ Need_i，则转到步骤 2。否则，由于进程已超过其对资源的最大索取，因此给出错误。

步骤 2

如果 Requesti ≤ Available，则转到步骤 3。否则，进程 P_i 必须等待直到资源可用。

步骤 3

如果通过如下修改状态，将请求的资源分配给进程 Pi：

Available = Available – Requesti;
Allocationi = Allocationi + Requesti;
Needi = Needi – Requesti;

如果生成的资源分配状态安全，则将请求的资源分配给进程 P_i。如果新状态不安全，则进程 P_i 必须等待 Requesti，并且恢复旧的资源分配状态。