2025-05-11-银行家算法分析

post on 11 May 2025 about 9108words require 31min
CC BY 4.0 （除特别声明或转载文章外）
如果这篇博客帮助到你，可以请我喝一杯咖啡~

银行家算法分析

参考资料

• 操作系统——银行家算法(Banker's Algorithm) - 王陆 - 博客园
• 操作系统 - 《银行家算法》_1、银行家算法的应用,根据题目要求能够找到某种状态下的安全序列,当进程请求资源-CSDN 博客
• 银行家算法详解与实现-CSDN 博客
• GitHub - TCL606/BankerAlgorithm: 银行家算法示例

概述

• 面试官:什么是死锁?怎么排查死锁?怎么避免死锁? - 小林 coding - 博客园
• 死锁解析-CSDN 博客

持有并等待条件导致的死锁

在多进程或多线程并发访问资源的场景下，死锁（Deadlock）是一种让人头疼的问题：几个任务相互等待，谁也拿不到继续执行的机会。银行家算法（Banker’s Algorithm）就是荷兰计算机科学家 Dijkstra 提出的一套“贷款”式资源分配方案，保证系统不陷入死锁。

---

为什么需要银行家算法

想象一家银行有一笔总资金，多个客户（进程）可能随时来申请贷款（资源）。如果不加以控制，一旦所有客户都拿走部分贷款，却留下一些客户的需求得不到满足，就可能让银行陷入“钱不够分”又“谁也不肯还款”的窘境。操作系统中的资源（内存块、I/O 通道、锁等）同理：若乱放行，很可能出现死锁，各进程互相等待而永远卡住。

在银行中，客户申请贷款的数量是有限的，每个客户在第一次申请贷款时要声明完成该项目所需的最大资金量，在满足所有贷款要求时，客户应及时归还。银行家在客户申请的贷款数量不超过自己拥有的最大值时，都应尽量满足客户的需要。在这样的描述中，银行家就好比操作系统，资金就是资源，客户就相当于要申请资源的进程。

银行家算法的核心思想是：

在满足安全条件的前提下才分配资源，永远确保系统处于“安全状态”——即总能找到一种方式，让所有进程依次完成。

---

算法流程

算法需要管理的“账本”

银行家算法维护四张表/向量，仿佛银行的“账本”：

1. Available（可用资源向量）

系统当前还剩余多少个各类资源可以分配。

1. Max（最大需求矩阵）

每个进程一生中最多可能向系统请求多少该类资源，事先必须申报。

1. Allocation（已分配矩阵）

系统已发给每个进程多少资源。

1. Need（需求矩阵）

每个进程还“差”多少资源才算满足最大需求，它等于

$$\text{Need}[i][j] = \text{Max}[i][j] - \text{Allocation}[i][j].$$

只有在 Request ≤ Need 且 Request ≤ Available 的条件下，才会尝试分配。更重要的是，真正分配前还要做一次“安全性检查”（Safety Check）。

---

什么是“安全状态”？

“安全状态”意味着：即便所有进程都提出最坏请求，系统依然能保证按某种顺序让它们一个个拿到资源、干完活再归还。

要检测这一点，算法会模拟一个“假设执行”过程：

1. 复制一份可用资源 Work = Available，并标记所有进程 Finish[i] = false。
2. 找到一个 Finish[i]==false 且其 Need[i] ≤ Work 的进程 $P_i$（说明它现在提出最大需求也能满足）。
3. 假设让它拿到所需资源并执行完毕：把它手里原本的 Allocation[i] 全部“还给”Work (Work += Allocation[i])，并把 Finish[i]=true。
4. 重复第 2、3 步，直到没有可满足的进程为止。
5. 如果最后所有 Finish[i] 都变成了 true，说明系统处于安全状态；否则，不安全。

---

分配资源前的“试探”与回滚

当某个进程 $P_i$ 发出一笔资源请求 Request[i] 时，银行家算法按照以下步骤执行：

合法性检查

• 若 Request[i][j] > Need[i][j] ——进程请求超过申报最大值，直接报错；
• 若 Request[i][j] > Available[j] ——当前可用资源不足，让进程等待。

试探性分配

Available   := Available - Request[i]
Allocation[i] := Allocation[i] + Request[i]
Need[i]      := Need[i] - Request[i]

安全性检测

• 如果“假设执行”后仍处于安全状态，就真正批准这笔分配；
• 否则回退到分配前的状态，让进程继续等待。

这样，系统永远不会进入一个“一旦分配就死锁”的局面。

---

一步步示例演示

假设有 5 个进程 $P_0…P_4$，3 类资源 $A,B,C$，初始数据如下：

Available = [3, 3, 2]   // 还空闲的 A、B、C 实例数

Max =
P0: [7, 5, 3]  
P1: [3, 2, 2]
P2: [9, 0, 2]
P3: [2, 2, 2]
P4: [4, 3, 3]

Allocation =
P0: [0, 1, 0]
P1: [2, 0, 0]
P2: [3, 0, 2]
P3: [2, 1, 1]
P4: [0, 0, 2]

Need = Max − Allocation =
P0: [7,4,3]
P1: [1,2,2]
P2: [6,0,0]
P3: [0,1,1]
P4: [4,3,1]

安全性检查示例

1. Work = [3,3,2]
2. 找到 $P_1$（Need [1,2,2] ≤ Work）→ “假设”它执行并还资源 →

Work = [3,3,2] + Alloc[P1]=[2,0,0] = [5,3,2]
Finish[P1] = true

1. 再找 $P_3$（Need [0,1,1] ≤ [5,3,2]），放行并还：

Work = [5,3,2] + [2,1,1] = [7,4,3]
Finish[P3] = true

1. 然后 $P_0$, $P_2$, $P_4$ 依次被发现、安全、放行……最终所有 Finish[] 都是 true，说明系统安全。

进程发请求示例

若 $P_1$ 再请求 [1,0,2]：

1. Request ≤ Need && ≤ Available（[3,3,2]），合法；
2. 暂时分配后 Available’=[2,3,0]，Alloc[1]=[3,0,2]，Need[1]=[0,2,0]；
3. 再用安全性检查，仍找得一条完成序列 → 批准；

反之，若分配后安全性检查失败，就拒绝这次请求并回滚，保证系统永不死锁。

---

代码实现

C++ 版本

#include <vector>
#include <iostream>
using namespace std;

// 安全性检查
bool isSafe(vector<int> Available,
            vector<vector<int>>& Max,
            vector<vector<int>>& Alloc) {
    int n = Max.size(), m = Available.size();
    vector<int> Work = Available;
    vector<bool> Finish(n, false);

    // 计算 Need
    vector<vector<int>> Need(n, vector<int>(m));
    for (int i = 0; i < n; ++i)
      for (int j = 0; j < m; ++j)
        Need[i][j] = Max[i][j] - Alloc[i][j];

    // 模拟放行
    for (int k = 0; k < n; ++k) {
        bool found = false;
        for (int i = 0; i < n; ++i) {
            if (!Finish[i]) {
                bool ok = true;
                for (int j = 0; j < m; ++j)
                    if (Need[i][j] > Work[j]) { ok = false; break; }
                if (ok) {
                    for (int j = 0; j < m; ++j) Work[j] += Alloc[i][j];
                    Finish[i] = true;
                    found = true;
                }
            }
        }
        if (!found) break;
    }
    // 全能放行才安全
    for (bool f : Finish) if (!f) return false;
    return true;
}

// 请求资源接口
bool requestResource(int pid, vector<int> Request,
                     vector<int>& Available,
                     vector<vector<int>>& Max,
                     vector<vector<int>>& Alloc) {
    int m = Available.size();
    // 合法性检查
    for (int j = 0; j < m; ++j)
        if (Request[j] > Max[pid][j] - Alloc[pid][j]
         || Request[j] > Available[j]) return false;

    // 试探性分配
    for (int j = 0; j < m; ++j) {
        Available[j] -= Request[j];
        Alloc[pid][j]   += Request[j];
    }

    // 安全检测：通过就保留，否则回滚
    if (isSafe(Available, Max, Alloc)) return true;
    for (int j = 0; j < m; ++j) {
        Available[j] += Request[j];
        Alloc[pid][j]   -= Request[j];
    }
    return false;
}

int main(){
    vector<int> Available{3,3,2};
    vector<vector<int>> Max{
        {7,5,3},{3,2,2},{9,0,2},{2,2,2},{4,3,3}
    };
    vector<vector<int>> Alloc{
        {0,1,0},{2,0,0},{3,0,2},{2,1,1},{0,0,2}
    };

    cout << "初始安全? " << (isSafe(Available, Max, Alloc) ? "是\n" : "否\n");

    vector<int> req{1,0,2};
    cout << "P1 请求 [1,0,2]: "
         << (requestResource(1, req, Available, Max, Alloc) ? "批准\n":"拒绝\n");
}

Python 版本

def is_safe(available, max_d, alloc):
    n, m = len(max_d), len(available)
    work = available[:]
    finish = [False]*n
    need = [[max_d[i][j]-alloc[i][j] for j in range(m)]
            for i in range(n)]

    while True:
        found = False
        for i in range(n):
            if not finish[i] and all(need[i][j] <= work[j] for j in range(m)):
                for j in range(m):
                    work[j] += alloc[i][j]
                finish[i] = True
                found = True
        if not found: break
    return all(finish)

def request_resource(pid, req, available, max_d, alloc):
    m = len(available)
    # 合法性检查
    for j in range(m):
        if req[j] > max_d[pid][j]-alloc[pid][j] or req[j] > available[j]:
            return False
    # 试探分配
    for j in range(m):
        available[j] -= req[j]
        alloc[pid][j] += req[j]
    if is_safe(available, max_d, alloc):
        return True
    # 回滚
    for j in range(m):
        available[j] += req[j]
        alloc[pid][j] -= req[j]
    return False

if __name__ == "__main__":
    avail = [3,3,2]
    max_d = [[7,5,3],[3,2,2],[9,0,2],[2,2,2],[4,3,3]]
    alloc = [[0,1,0],[2,0,0],[3,0,2],[2,1,1],[0,0,2]]
    print("初始安全?", is_safe(avail, max_d, alloc))
    print("P1 请求 [1,0,2]:",
          "批准" if request_resource(1, [1,0,2], avail, max_d, alloc) else "拒绝")

Go 版本

package main

import "fmt"

_// BankersAlgorithm 结构体定义了银行家算法所需的数据结构_
_// available: 可用资源向量_
_// max: 最大需求矩阵_
_// allocation: 分配矩阵_
_// need: 需求矩阵_
type BankersAlgorithm struct {
 **available**  []int
 **max**        [][]int
 **allocation** [][]int
 **need**       [][]int
}

_// NewBankersAlgorithm 初始化银行家算法_
_// 参数:_
_//   - available: 系统可用资源向量_
_//   - max: 进程最大需求矩阵_
_//   - allocation: 当前分配矩阵_
_// 返回: 初始化后的银行家算法实例_
func NewBankersAlgorithm(available []int, max [][]int, allocation [][]int) *BankersAlgorithm {
 _// 创建新的银行家算法实例_
 ba := &BankersAlgorithm{
  **available**:  make([]int, len(available)),
  **max**:        make([][]int, len(max)),
  **allocation**: make([][]int, len(allocation)),
  **need**:       make([][]int, len(max)),
 }

 _// 复制可用资源向量_
 copy(ba.available, available)
 
 _// 复制最大需求矩阵_
 for i := range max {
  ba.max[i] = make([]int, len(max[i]))
  copy(ba.max[i], max[i])
 }
 
 _// 复制分配矩阵_
 for i := range allocation {
  ba.allocation[i] = make([]int, len(allocation[i]))
  copy(ba.allocation[i], allocation[i])
 }

 _// 计算需求矩阵 need = max - allocation_
 for i := range max {
  ba.need[i] = make([]int, len(max[i]))
  for j := range max[i] {
   ba.need[i][j] = max[i][j] - allocation[i][j]
  }
 }

 return ba
}

_// RequestResources 处理进程的资源请求_
_// 参数:_
_//   - processID: 请求资源的进程ID_
_//   - request: 请求的资源向量_
_// 返回: 请求是否成功_
func (ba *BankersAlgorithm) RequestResources(processID int, request []int) bool {
 _// 检查请求是否超过最大需求_
 for i := range request {
  if request[i] > ba.need[processID][i] {
   fmt.Printf("进程 %d 请求的资源超过最大需求\n", processID)
   return false
  }
 }

 _// 检查系统是否有足够的可用资源_
 for i := range request {
  if request[i] > ba.available[i] {
   fmt.Printf("资源不足，进程 %d 需等待\n", processID)
   return false
  }
 }

 _// 试探性分配资源_
 for i := range request {
  ba.available[i] -= request[i]
  ba.allocation[processID][i] += request[i]
  ba.need[processID][i] -= request[i]
 }

 _// 检查分配后系统是否安全_
 if !ba.isSafe() {
  fmt.Println("分配后系统处于不安全状态，撤销分配")
  _// 撤销分配，恢复原状态_
  for i := range request {
   ba.available[i] += request[i]
   ba.allocation[processID][i] -= request[i]
   ba.need[processID][i] += request[i]
  }
  return false
 }

 fmt.Println("资源分配成功，系统处于安全状态")
 return true
}

_// isSafe 检查系统是否处于安全状态_
_// 返回: 系统是否安全_
func (ba *BankersAlgorithm) isSafe() bool {
 _// 初始化工作向量和完成向量_
 work := make([]int, len(ba.available))
 copy(work, ba.available)
 finish := make([]bool, len(ba.max))

 _// 寻找可以完成的进程_
 for {
  found := false
  for i := range ba.max {
   if !finish[i] && ba.canFinish(work, ba.need[i]) {
    _// 进程i可以完成，释放其资源_
    for j := range work {
     work[j] += ba.allocation[i][j]
    }
    finish[i] = true
    found = true
   }
  }

  if !found {
   break
  }
 }

 _// 检查是否所有进程都能完成_
 for _, f := range finish {
  if !f {
   return false
  }
 }

 return true
}

_// canFinish 检查进程是否能够完成_
_// 参数:_
_//   - work: 当前可用资源向量_
_//   - need: 进程需求向量_
_// 返回: 进程是否可以完成_
func (ba *BankersAlgorithm) canFinish(work []int, need []int) bool {
 for i := range work {
  if need[i] > work[i] {
   return false
  }
 }
 return true
}

func main() {
 _// 初始化系统资源数据_
 available := []int{3, 3, 2}  _// 可用资源向量_
 max := [][]int{              _// 最大需求矩阵_
  {7, 5, 3},
  {3, 2, 2},
  {9, 0, 2},
  {2, 2, 2},
  {4, 3, 3},
 }
 allocation := [][]int{       _// 当前分配矩阵_
  {0, 1, 0},
  {2, 0, 0},
  {3, 0, 2},
  {2, 1, 1},
  {0, 0, 2},
 }

 _// 创建银行家算法实例_
 ba := NewBankersAlgorithm(available, max, allocation)

 _// 模拟进程1请求资源_
 processID := 1
 request := []int{0, 2, 0}

 _// 处理资源请求_
 if ba.RequestResources(processID, request) {
  fmt.Println("资源分配成功")
 } else {
  fmt.Println("资源分配失败")
 }
}

---

算法效率与适用场景

• 时间复杂度：每次请求都要调用一次安全性检查，最坏 $O(n^2 \times m)$（$n$ 是进程数，$m$ 是资源种类数）。
• 优点：只要需求申报准确，能彻底避免死锁；逻辑清晰，易于理解与实现。
• 缺点：

1. 计算量较大，不适合大量进程和资源同时在线的场景；
2. 要求进程提前申报最大需求，有时难以预估；
3. 如果申报过高就浪费资源，过低又可能限制并发度。

典型应用：

嵌入式实时系统、小型操作系统、数据库连接池管理等场景——进程/线程数目不多、资源类型有限、死锁成本高，正好适合使用银行家算法来保证系统健康运行。

---

总结

银行家算法用“银行发放贷款”这一比喻，把死锁避免转化为“安全性检查 + 试探性分配 + 回滚”三步走。理解它的核心，就是：

1. 维护 Available/Max/Allocation/Need 这四张“账本”；
2. 安全性检测：模拟最坏情况看系统是否还能让所有进程“还清”资源；
3. 只在安全状态下正式分配，否则拒绝并回滚。

这样的设计保证了系统永不进入死锁，但也带来了计算开销和使用局限。在实际工程中，我们要根据并发规模与实时性要求，权衡是否使用这一经典算法。希望本文的通俗讲解和示例代码，能让你对银行家算法有清晰而深入的理解。

Related posts

• 2025-06-08-大模型底层技术分析 08 Jun 2025
• 2025-06-05-智能体平台及关键技术分析 05 Jun 2025
• 2025-06-04-低代码平台及相关技术介绍应用 04 Jun 2025