操作系统 银行家算法

银行家算法是一种在计算机系统中安全地分配资源给每个进程，同时避免死锁的算法。’S-State’检查每个进程的分配是否应该允许，它还帮助操作系统成功地在所有进程之间共享资源。银行家算法的命名是因为它检查一个人是否应该获得贷款金额，以帮助银行系统安全地模拟资源分配。在本节中，我们将详细了解银行家算法，并解决基于银行家算法的问题。为了理解银行家算法，我们首先将看一个实际示例。

假设某个银行的账户持有人数量为’n’，银行的总金额为’T’。如果一个账户持有人申请贷款，首先银行从总金额中减去贷款金额，然后估计现金差额是否大于T，以批准贷款金额。采取这些步骤是因为如果另一个人申请贷款或从银行提取一些金额，它可以帮助银行在银行系统的功能方面没有任何限制地管理和操作所有事务。

同样，它在操作系统中也起作用。当在计算机系统中创建一个新进程时，该进程必须向操作系统提供各种信息，如即将到来的进程、资源请求、计数和延迟。根据这些标准，操作系统决定应该执行或等待哪个进程序列，以避免系统中发生死锁。因此，它也被称为死锁避免算法或死锁检测算法。

优势

银行家算法具有以下重要特点：

1. 它包含满足每个进程需求的各种资源。
2. 每个进程应向操作系统提供即将到来的资源请求、资源数量和资源持有时间的信息。
3. 它帮助操作系统管理和控制计算机系统中每种类型资源的进程请求。
4. 该算法具有最大资源属性，表示每个进程在系统中可以持有的最大资源数量。

劣势

1. 它需要固定数量的进程，在执行进程的同时不能启动其他进程。
2. 该算法不允许进程在处理任务时更改其最大需求。
3. 每个进程必须事先知道并声明它们的最大资源需求。
4. 资源请求可以在有限的时间内被授予，但分配资源的时间限制为一年。

在使用银行家算法时，需要了解以下三件事：

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 = Available，Finish[i] = false，对于i = 0, 1, 2, 3, 4… n – 1。

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

Need[i] <= Work，Finish[i] false。如果i不存在，则转到步骤4。

3. Work = Work + Allocation(i) // 获取新的资源分配

Finish[i] = true

转到步骤2，检查下一个进程的资源可用性状态。

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

资源请求算法

资源请求算法检查系统在进程对系统的每种资源发出请求时的行为。

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

1. 当每种类型的 请求资源 数量小于 需求 资源时，转到步骤2，如果条件不满足，这意味着进程P[i]超出了其资源的最大申请。根据表达式：

如果 Request(i) <= Need，则转到步骤2；

2. 当每种类型的请求资源数量小于每个进程的可用资源时，转到步骤（3）。根据表达式：

如果 Request(i) <= Available，则进程P[i]必须等待资源，因为资源不可用。

3. 当请求的资源通过改变状态分配给进程时：

Available = Available – Request Allocation(i) = Allocation(i) + Request (i) Need i = Need i - Request i

当资源分配状态是安全的时候，它的资源会被分配给进程P(i)。如果新状态是不安全的，则进程P(i)必须等待每种类型的请求R(i)并恢复旧的资源分配状态。

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

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

1. 需求矩阵的引用是什么？
2. 确定系统是否安全。
3. 如果进程P1的资源请求（1, 0, 0）可以立即被系统接受，会发生什么？

答案2： 需求矩阵的上下文如下所示：

需求[i] = 最大需求[i] – 已分配[i] P1的需求：(7, 5, 3) – (0, 1, 0) = 7, 4, 3 P2的需求：(3, 2, 2) – (2, 0, 0) = 1, 2, 2 P3的需求：(9, 0, 2) – (3, 0, 2) = 6, 0, 0 P4的需求：(2, 2, 2) – (2, 1, 1) = 0, 1, 1 P5的需求：(4, 3, 3) – (0, 0, 2) = 4, 3, 1

因此，我们创建了需求矩阵的上下文。

答案2：应用银行家算法：

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

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

步骤1： 对于进程P1：

Need <= Available

7, 4, 3 <= 3, 3, 2 条件是 false 。

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

步骤2： 对于进程P2：

Need <= Available

1, 2, 2 <= 3, 3, 2 条件 true

新的可用资源=可用资源+分配资源

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

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

步骤3： 对于进程P3：

P3 Need <= Available

6, 0, 0 < = 5, 3, 2 条件是 false 。

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

步骤4： 对于进程P4：

P4 Need <= Available

0, 1, 1 <= 5, 3, 2 条件是 true

新的可用资源=可用资源+分配资源

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

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

步骤5： 对于进程P5：

P5 Need <= Available

4, 3, 1 <= 7, 4, 3 条件是 true

新的可用资源=可用资源+分配资源

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

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

步骤6： 对于进程P1：

P1 Need <= Available

7, 4, 3 <= 7, 4, 5 条件是 true

新的可用资源=可用资源+分配资源

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

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

步骤7： 对于进程P3：

P3需要 <= 可用资源

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

新的可用资源 = 可用资源 + 已分配资源

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

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

答案为3： 为了满足请求（1, 0, 2），首先我们必须检查 **请求 <= 可用资源 ** ，即（1, 0, 2）<=（3, 3, 2），由于条件为真，所以进程P1立即得到请求。