银行家算法

银行家算法 (Banker’s Algorithm) 详解

银行家算法是一种著名的死锁避免 (Deadlock Avoidance) 算法。它的核心思想是：在为进程分配资源之前，先“预演”一下分配后的情况，判断系统是否会进入一个不安全状态。如果分配不会导致不安全状态，则实施分配；否则，让请求资源的进程等待。

这个名字来源于银行家向客户放贷的场景：银行家在批准一笔贷款前，必须确保他手头的资金（可用资源）能满足所有客户在未来某个时刻提出的所有最大贷款需求（最大需求），从而保证银行不会因资金周转不开而破产（系统不会死锁）。

1. 核心数据结构

为了实现算法，系统需要维护以下几个核心数据结构（假设有 n 个进程和 m 种资源）：

• Available (可用资源向量)：一个长度为 m 的向量。Available[j] = k 表示系统中 Rj 类资源当前还有 k 个可用实例。
• Max (最大需求矩阵)：一个 n x m 的矩阵。Max[i, j] = k 表示进程 Pi 在整个运行周期中，最多需要 k 个 Rj 类资源。这个值在进程创建时就必须声明。
• Allocation (已分配矩阵)：一个 n x m 的矩阵。Allocation[i, j] = k 表示系统当前已分配给进程 Pi k 个 Rj 类资源。
• Need (需求矩阵)：一个 n x m 的矩阵。Need[i, j] = k 表示进程 Pi 要完成任务，还需要 k 个 Rj 类资源。这个矩阵不是凭空产生的，而是根据 Max 和 Allocation 计算得出： $$Need[i,j]=Max[i,j]-Allocation[i,j]$$

2. 核心算法

银行家算法包含两个主要的部分：安全性算法 和 资源请求算法。

A. 安全性算法

这个算法用来回答“当前系统状态是否安全？”。

输入：当前的 Available, Allocation, Need 状态。 目标：尝试找到一个安全序列 (Safe Sequence)。安全序列是指一个进程的排列 <P₁, P₂, ..., Pn>，按照这个顺序为每个进程分配其所需的全部资源，都能顺利执行完毕。

步骤：

1. 初始化：

   • 建立一个工作向量 Work，令 Work = Available。它表示在模拟过程中系统可支配的资源。
   • 建立一个布尔向量 Finish，长度为 n，所有元素初始化为 false。Finish[i] = false 表示进程 Pi 尚未“完成”。

2. 寻找可完成的进程：

   • 从所有进程中，寻找一个满足以下两个条件的进程 Pi：
     • Finish[i] == false (该进程还未完成)
     • Need[i] <= Work (该进程所需的所有资源都小于或等于系统当前可支配的资源)
   • 如果能找到这样的进程，则进入步骤3。如果找遍所有进程都找不到，则进入步骤4。

3. 模拟执行与资源释放：

   • 假设找到了满足条件的进程 Pi，我们模拟它获取资源并执行完毕，然后释放其占有的所有资源。
   • 更新 Work 向量：Work = Work + Allocation[i] (将 Pi 释放的资源加回到可支配资源中)。
   • 标记该进程为完成：Finish[i] = true。
   • 返回步骤2，继续寻找下一个可以完成的进程。

4. 判断最终状态：

   • 当步骤2再也找不到满足条件的进程后，检查 Finish 向量。
   • 如果 Finish 向量中所有元素都为 true，则说明所有进程都能在某个序列下完成，系统处于安全状态。这个过程中标记Finish为true的顺序就是一个安全序列。
   • 如果 Finish 向量中存在任何一个 false 元素，则说明无法让所有进程都完成，系统处于不安全状态。

---

B. 资源请求算法

这个算法用来回答“进程 Pi 的资源请求 Request_i 能否被批准？”。

输入：进程 Pi 的请求向量 Request_i。Request_i[j] = k 表示 Pi 请求 k 个 Rj 资源。

步骤：

1. 检查请求的合法性：

   • 判断 Request_i <= Need[i] 是否成立。
   • 如果不成立（请求的资源数超过了它声明还需要的资源数），则这是一个非法请求，应拒绝并报错。
   • 如果成立，则进入步骤2。

2. 检查系统可用性：

   • 判断 Request_i <= Available 是否成立。
   • 如果不成立（系统当前没有足够的资源满足该请求），则 Pi 必须等待。
   • 如果成立，说明资源暂时是够的，进入最关键的步骤3。

3. “预分配”并进行安全性检查：

   • 系统假定将资源分配给 Pi，并临时修改系统状态数据：
     • Available = Available - Request_i
     • Allocation[i] = Allocation[i] + Request_i
     • Need[i] = Need[i] - Request_i
   • 在这个临时的、修改后的新状态上，运行安全性算法。
   • 根据安全性算法的结果做决策：
     • 如果安全性算法返回“安全”，则说明这次分配是安全的。系统正式批准该请求，刚才的临时状态修改变为永久。
     • 如果安全性算法返回“不安全”，则说明这次分配可能导致未来发生死锁。系统拒绝该请求，并将刚才临时修改的状态全部撤销（回滚到修改前的状态），然后让进程 Pi 等待。

---

综合示例

问题：假设在 T0 时刻，系统中有5个进程 (P0-P4) 和3类资源 (A, B, C)，各类资源总数分别为 (10, 5, 7)。T0时刻的系统状态如下：

进程	Allocation (已分配)	Max (最大需求)
	A B C	A B C
P0	0 1 0	7 5 3
P1	2 0 0	3 2 2
P2	3 0 2	9 0 2
P3	2 1 1	2 2 2
P4	0 0 2	4 3 3

任务一：判断 T0 时刻系统是否安全

4. 计算 Need 矩阵 和 Available 向量

   • Need = Max - Allocation
     • Need(P0) = (7,5,3) - (0,1,0) = (7,4,3)
     • Need(P1) = (3,2,2) - (2,0,0) = (1,2,2)
     • Need(P2) = (9,0,2) - (3,0,2) = (6,0,0)
     • Need(P3) = (2,2,2) - (2,1,1) = (0,1,1)
     • Need(P4) = (4,3,3) - (0,0,2) = (4,3,1)
   • 已分配总数 = (0+2+3+2+0, 1+0+0+1+0, 0+0+2+1+2) = (7, 2, 5)
   • Available = 总资源 - 已分配总数
   • Available = (10, 5, 7) - (7, 2, 5) = (3, 3, 2)

5. 运行安全性算法

   • 初始状态: Work = (3, 3, 2), Finish = [F, F, F, F, F]

   • (轮次1) 寻找 Need <= Work 的进程：

     • P0: Need(7,4,3) > Work(3,3,2) (不满足)
     • P1: Need(1,2,2) ⇐ Work(3,3,2) (满足！)
     • P2: Need(6,0,0) > Work(3,3,2) (不满足)
     • P3: Need(0,1,1) ⇐ Work(3,3,2) (满足！)
     • P4: Need(4,3,1) > Work(3,3,2) (不满足)
     • 我们选择P1（也可以选P3）。
     • 执行P1: Work = Work + Allocation(P1) = (3,3,2) + (2,0,0) = (5,3,2)。 Finish = [F, T, F, F, F]。

   • (轮次2) 继续寻找 Need <= Work 的进程 (Work = (5,3,2))：

     • P0: Need(7,4,3) > Work(5,3,2) (不满足)
     • P2: Need(6,0,0) > Work(5,3,2) (不满足)
     • P3: Need(0,1,1) ⇐ Work(5,3,2) (满足！)
     • P4: Need(4,3,1) ⇐ Work(5,3,2) (满足！)
     • 我们选择P3。
     • 执行P3: Work = Work + Allocation(P3) = (5,3,2) + (2,1,1) = (7,4,3)。 Finish = [F, T, F, T, F]。

   • (轮次3) 继续寻找 (Work = (7,4,3))：

     • P0: Need(7,4,3) ⇐ Work(7,4,3) (满足！)
     • P2: Need(6,0,0) ⇐ Work(7,4,3) (满足！)
     • P4: Need(4,3,1) ⇐ Work(7,4,3) (满足！)
     • 我们选择P4。
     • 执行P4: Work = Work + Allocation(P4) = (7,4,3) + (0,0,2) = (7,4,5)。 Finish = [F, T, F, T, T]。

   • (轮次4) 继续寻找 (Work = (7,4,5))：

     • P0: Need(7,4,3) ⇐ Work(7,4,5) (满足！)
     • 我们选择P0。
     • 执行P0: Work = Work + Allocation(P0) = (7,4,5) + (0,1,0) = (7,5,5)。 Finish = [T, T, F, T, T]。

   • (轮次5) 继续寻找 (Work = (7,5,5))：

     • P2: Need(6,0,0) ⇐ Work(7,5,5) (满足！)
     • 我们选择P2。
     • 执行P2: Work = Work + Allocation(P2) = (7,5,5) + (3,0,2) = (10,5,7)。 Finish = [T, T, T, T, T]。

6. 最终结论

   • 所有进程的 Finish 标志都为 true。
   • 因此，T0时刻系统是安全的。 一个安全序列是 <P1, P3, P4, P0, P2>。

任务二：若P1请求资源(1, 0, 2)，能否实施？

7. 检查合法性: P1的请求 Request(P1) = (1, 0, 2)。

   • Need(P1) = (1, 2, 2)。
   • Request(P1) ⇐ Need(P1) 成立（(1,0,2) ⇐ (1,2,2)）。请求合法。

8. 检查可用性: T0时刻 Available = (3, 3, 2)。

   • Request(P1) ⇐ Available 成立（(1,0,2) ⇐ (3,3,2)）。资源可用。

9. 预分配并进行安全性检查:

   • 假设分配，更新系统状态：
     • Available = (3,3,2) - (1,0,2) = (2,3,0)
     • Allocation(P1) = (2,0,0) + (1,0,2) = (3,0,2)
     • Need(P1) = (1,2,2) - (1,0,2) = (0,2,0)
   • 在新状态下运行安全性算法:
     • 初始状态: Work = (2, 3, 0), Finish = [F, F, F, F, F]
     • (轮次1) 寻找 Need <= Work:
       • P0: Need(7,4,3) > Work(2,3,0)
       • P1: Need(0,2,0) ⇐ Work(2,3,0) (满足！)
       • P2: Need(6,0,0) > Work(2,3,0)
       • P3: Need(0,1,1) > Work(2,3,0)
       • P4: Need(4,3,1) > Work(2,3,0)
       • 只能选择P1。
       • 执行P1: Work = Work + Allocation(P1) = (2,3,0) + (3,0,2) = (5,3,2)。 Finish = [F, T, F, F, F]。
     • (轮次2) (Work = (5,3,2))：和任务一的轮次2一样，可以找到P3，然后是P4，P0，P2… 最终可以找到一个安全序列。

10. 最终结论 * 因为预分配后系统仍然是安全的，所以可以实施P1的这次资源申请。系统状态将正式更新为预分配后的状态。

reference