银行家算法

c++

银行家算法（Banker's Algorithm）是一种著名的用于避免死锁的资源分配算法。它由 Edsger Dijkstra 提出，并因其模拟银行家借贷的行为而得名。银行家算法的核心思想是仅在系统处于安全状态时分配资源，以确保系统不会进入死锁状态。

银行家算法的基本概念包括以下几个关键点：

银行家算法通过以下步骤来决定是否分配资源：

为了检查系统是否处于安全状态，银行家算法使用以下步骤：

初始化：
- 定义向量 Work 表示当前可用资源。
- 定义向量 Finish 表示每个进程是否完成。
寻找可满足进程：
- 寻找一个满足条件的进程 i：Finish[i] == false 且 Need[i] <= Work。
- 如果找到这样的进程，则假定将所有资源分配给该进程，使其完成，然后释放资源，即：
  - Work = Work + Allocation[i]
  - Finish[i] = true
检查完成状态：
- 如果所有进程都能完成（即所有 Finish[i] 都为 true），则系统处于安全状态；否则，不安全。

当进程 i 请求资源时，银行家算法执行以下步骤：

检查请求合法性：
- 如果 Request[i] > Need[i]，则出错，因为请求超过了最大需求。
- 如果 Request[i] > Available，则等待，因为当前没有足够的资源。
试探性分配资源：
- 试探性地分配资源：
  - Available = Available - Request[i]
  - Allocation[i] = Allocation[i] + Request[i]
  - Need[i] = Need[i] - Request[i]
安全性检查：
- 执行安全性检查算法。如果系统处于安全状态，则正式分配资源；否则，撤销试探性分配，并让进程等待。

下面是一个示例，演示银行家算法如何避免死锁。

假设系统有如下资源和进程：

资源分配表如下：

进程	最大需求 (Max)	已分配 (Allocation)	需要 (Need = Max - Allocation)
P0	(7, 5, 3)	(0, 1, 0)	(7, 4, 3)
P1	(3, 2, 2)	(2, 0, 0)	(1, 2, 2)
P2	(9, 0, 2)	(3, 0, 2)	(6, 0, 0)
P3	(2, 2, 2)	(2, 1, 1)	(0, 1, 1)
P4	(4, 3, 3)	(0, 0, 2)	(4, 3, 1)

当前可用资源：

A	B	C
3	3	2

初始状态：

找到 P1 满足 Need[1] <= Work，完成 P1：
- Work = Work + Allocation[1] = (3, 3, 2) + (2, 0, 0) = (5, 3, 2)
- Finish[1] = true
找到 P3 满足 Need[3] <= Work，完成 P3：
- Work = Work + Allocation[3] = (5, 3, 2) + (2, 1, 1) = (7, 4, 3)
- Finish[3] = true
找到 P0 满足 Need[0] <= Work，完成 P0：
- Work = Work + Allocation[0] = (7, 4, 3) + (0, 1, 0) = (7, 5, 3)
- Finish[0] = true
找到 P2 满足 Need[2] <= Work，完成 P2：
- Work = Work + Allocation[2] = (7, 5, 3) + (3, 0, 2) = (10, 5, 5)
- Finish[2] = true
找到 P4 满足 Need[4] <= Work，完成 P4：
- Work = Work + Allocation[4] = (10, 5, 5) + (0, 0, 2) = (10, 5, 7)
- Finish[4] = true

所有 Finish[i] 均为 true，系统处于安全状态。

银行家算法通过安全性检查确保系统不会进入死锁状态。通过模拟资源分配，检查是否存在一个顺序，使得所有进程都能顺利完成，从而决定是否进行资源分配。银行家算法适用于需要严格避免死锁的系统，但由于其复杂性和计算开销，通常在资源有限且系统规模较小时使用。

版权属于：

鱼一的博客 ◡̈

本文链接：

https://yuyi.monster/archives/237/（转载时请注明本文出处及文章链接）

作品采用：