银行家算法 · Lumjiel

Dijkstra在1965年提出的银行家算法是著名的死锁避免算法，这个用于一个银行家给多个顾客贷款的算法可以直接用于操作系统给进程分配资源，这时只要把银行家换成操作系统，把顾客换成进程，把资金换成资源，把银行家决定是否放贷时所用的判断过程（即判断顾客是否有信誉和偿还能力）换成操作系统决定是否分配资源时所用的判断过程（即判断进程是否能及时归还资源）即可。

银行家算法的核心思想超接地气 —— 它就像银行给客户放贷时的 “风险评估”，只不过把 “银行” 换成了操作系统，“客户” 换成了进程，“资金” 换成了系统资源。

一、为什么需要银行家算法？

1. 生活中的 “死锁” 例子

你和朋友互相借东西：你拿着朋友的充电宝，非要先拿到他的数据线才肯还充电宝；朋友拿着你的数据线，非要先拿到你的充电宝才肯还数据线。结果就是俩人都卡着，谁也用不了 —— 这就是死锁。

2. 操作系统里的死锁

操作系统里有多个进程（比如 P1、P2、P3），共享有限的资源（比如打印机、内存、CPU 资源）。如果进程都像上面的例子一样 “占着资源等别人的资源”，系统就会卡死，所有进程都无法执行。

3. 银行家算法的核心目标

银行家算法的本质是：每次给进程分配资源前，先做 “风险评估”—— 确保分配后系统仍处于 “安全状态”，不会出现死锁。就像银行放贷前，要确认客户能还清贷款，且剩下的钱能满足其他客户的正常借贷需求，不会导致银行资金链断裂。

二、银行家算法的核心概念

先记住 4 个核心 “账本”（矩阵 / 向量），所有计算都围绕它们展开。我们用 “银行放贷” 和 “操作系统分配资源” 做对比.

概念	银行场景	操作系统场景
最大需求矩阵（Max）	每个客户最多要借的总资金（比如客户 A 最多借 3 万）	每个进程最多需要的各类资源数
分配矩阵（Allocation）	客户已经借到的资金	进程已经分配到的各类资源数
需求矩阵（Need）	客户还需要借的资金（Max - 已借）	进程还需要的各类资源数（Max-Allocation）
可用资源向量（Available）	银行当前能放贷的剩余资金	系统当前可分配的剩余资源数
安全序列	银行能收回所有贷款的客户还款顺序	系统能完成所有进程的执行顺序

关键补充：安全状态 vs 不安全状态

安全状态：存在一个 “安全序列”，按这个顺序让进程执行，所有进程都能完成（就像银行能按顺序收回所有贷款）。安全状态一定不会死锁。
不安全状态：没有安全序列，系统可能进入死锁（但不一定立刻死锁，只是有风险）。

三、银行家算法的执行步骤

当某个进程申请资源时，操作系统会按以下步骤判断是否分配：

步骤 1：检查请求是否 “合理”

先看两个条件是否都满足：

进程申请的资源数 ≤ 它的剩余需求（Need）—— 不能 “超额申请”（比如你最多借 3 万，已经借了 1 万，还想借 3 万，肯定不行）；
进程申请的资源数 ≤ 系统当前可用资源（Available）—— 系统得有足够的剩余资源。

步骤 2：“假设分配” 资源，更新账本

如果步骤 1 通过，先 “假装” 给进程分配资源，更新 3 个账本：

分配矩阵（Allocation）：对应进程的资源数 += 申请数；
需求矩阵（Need）：对应进程的资源数 -= 申请数；
可用资源向量（Available）：系统剩余资源 -= 申请数。

步骤 3：检查分配后是否 “安全”

判断更新后的系统是否存在安全序列：

如果存在 → 真的分配资源；
如果不存在 → 撤销 “假分配”（恢复账本），拒绝这次资源申请，让进程等待。

四、实例演示

已知条件

进程数：4 个（P1、P2、P3、P4）；
资源种类：3 类（R1、R2、R3），系统总资源：R1=9、R2=3、R3=6；
各矩阵初始值：

进程	Max（最大需求）	Allocation（已分配）	Need（剩余需求）=Max-Allocation
P1	[3,2,2]	[1,0,0]	[2,2,2]
P2	[6,1,3]	[5,1,1]	[1,0,2]
P3	[3,1,4]	[2,1,1]	[1,0,3]
P4	[4,2,2]	[0,0,2]	[4,2,0]

可用资源向量 Available：[1,1,2]

第一步：检查初始状态是否安全（找安全序列）

初始化：

Work（临时可用资源）= Available = [1,1,2]；
Finish（进程完成标记）= [0,0,0,0]（0 = 未完成，1 = 完成）。

第一轮找可执行进程

遍历所有未完成进程，看 Need ≤ Work：

P1：Need [2,2,2] > Work [1,1,2] → 不行；
P2：Need [1,0,2] ≤ Work [1,1,2] → 可以！

标记 P2 完成：Finish [1]=1；

释放 P2 的资源：Work = Work + Allocation [P2] = [1+5,1+1,2+1] = [6,2,3]；

安全序列暂存：P2。

第二轮找可执行进程

Finish=[0,1,0,0]，Work=[6,2,3]：

P1：Need [2,2,2] ≤ Work [6,2,3] → 可以！

标记 P1 完成：Finish [0]=1；

释放 P1 的资源：Work = [6+1,2+0,3+0] = [7,2,3]；

安全序列更新：P2→P1。

第三轮找可执行进程

Finish=[1,1,0,0]，Work=[7,2,3]：

P3：Need [1,0,3] ≤ Work [7,2,3] → 可以！

标记 P3 完成：Finish [2]=1；

释放 P3 的资源：Work = [7+2,2+1,3+1] = [9,3,4]；

安全序列更新：P2→P1→P3。

第四轮找可执行进程

Finish=[1,1,1,0]，Work=[9,3,4]：

P4：Need [4,2,0] ≤ Work [9,3,4] → 可以！

标记 P4 完成：Finish [3]=1；

释放 P4 的资源：Work = [9+0,3+0,4+2] = [9,3,6]；

安全序列最终：P2→P1→P3→P4。

所有进程都完成（Finish 全为 1），说明初始状态安全！

第二步：模拟进程申请资源（比如 P1 申请 [1,0,1]）

我们假设 P1 申请资源 [1,0,1]，按算法判断是否分配：

检查请求合理性：
- 申请数 [1,0,1] ≤ P1 的 Need [2,2,2] → 满足；
- 申请数 [1,0,1] ≤ Available [1,1,2] → 满足；
假装分配，更新账本：
- Allocation[P1] = [1+1,0+0,0+1] = [2,0,1]；
- Need[P1] = [2-1,2-0,2-1] = [1,2,1]；
- Available = [1-1,1-0,2-1] = [0,1,1]；
检查新状态是否安全（方法同上），最终能找到安全序列，因此允许分配。

五、完整代码解析

1. 全局变量定义

// p=进程数，r=资源种类数
int p ;
int r ;
int maxs[10][10]; // 最大需求矩阵
int allocation[10][10]; // 分配矩阵
int need[10][10];   // 需求矩阵
int available[10]; // 可用资源向量
int request[10];   // 进程的资源申请向量

👉 注：数组大小设为 10 是为了兼容大部分场景，实际可根据需求调整。

2. 输入函数（infInput）

作用：读取用户输入的 4 个核心矩阵 / 向量，为后续计算做准备。

void infInput()
{
    int i,j;
    cout<<"请输入最大需求矩阵max\n";
    for(i=0; i<p; i++)
    {
        for(j=0; j<r; j++)
        {
            cin>>maxs[i][j];
        }
    }
    cout<<"请输入分配矩阵allocation\n";
    for(i=0; i<p; i++)
    {
        for(j=0; j<r; j++)
        {
            cin>>allocation[i][j];
        }
    }
    cout<<"请输入需求矩阵need\n";
    for(i=0; i<p; i++)
    {
        for(j=0; j<r; j++)
        {
            cin>>need[i][j];
        }
    }
    cout<<"请输入可用资源向量available\n";
    for(i=0; i<r; i++)
    {
        cin>>available[i];
    }
}

3. 比较函数（compare）

作用：判断数组 m 的每个元素是否都≥数组 n（比如检查可用资源是否满足进程需求）。

int compare(int m[],int n[])
{
    int i;
    for(i=0; i<r; i++)
    {
        if(m[i]<n[i])
        {
            return 0; // 有一个元素小，返回0（不满足）
        }
    }
    return 1; // 全部满足，返回1
}

4. 安全性检测函数（stest）

核心函数！作用是判断当前系统是否存在安全序列。

int stest()
{
    int i,j,k,l,flag=0;
    int finish[p]; // 进程完成标记
    int work[r];   // 临时可用资源（模拟分配过程）
    // 初始化：所有进程未完成，work=available
    for(i=0; i<p; i++) finish[i]=0;
    for(i=0; i<r; i++) work[i]=available[i];
    
    cout<<"分配序列：\n";
    cout<<"            allocation            need              avilable"<<endl;
    
    // 遍历所有进程，找安全序列
    for(k=0; k<p; k++)
    {
        for(i=0; i<p; i++)
        {
            if(finish[i]==1) continue; // 跳过已完成进程
            // 检查可用资源是否满足进程剩余需求
            if(compare(work,need[i]))
            {
                finish[i]=1; // 标记进程完成
                cout<<'\n'<<"进程"<<i+1<<'\t';
                flag=1;
                // 打印分配矩阵（可视化）
                for (j =0; j<r; j++) printf("  %2d ", allocation[i][j]);
                cout<<"     ";
                // 打印需求矩阵（可视化）
                for (j = 0; j < r; j++) printf("  %2d ", need[i][j]);
                cout<<"     ";
                // 打印分配后的可用资源（可视化）
                for (j = 0; j <r; j++) printf("  %2d ", work[j] +allocation[i][j]);
                // 释放进程资源，更新work
                for(l=0; l<r; l++) work[l]=work[l]+allocation[i][l];
                break;
            }
        }
        if(flag==1) break;
    }
    // 检查是否所有进程都完成
    for(l=0; l<p; l++)
    {
        if(finish[l]==0) return 0; // 有进程未完成，无安全序列
    }
    return 1; // 所有进程完成，有安全序列
}

5. 资源请求处理函数（rtest）

作用：处理进程的资源申请，判断是否分配。

void rtest(int n) // n是申请资源的进程编号（从1开始）
{
    int j;
    // 检查请求是否合法：可用资源≥申请数 且 进程剩余需求≥申请数
    if(compare(available,request)&&compare(need[n-1],request))
    {
        // 假装分配资源，更新账本
        for(j=0; j<r; j++)
        {
            allocation[n-1][j] += request[j];
            need[n-1][j] -= request[j];
            available[j] -= request[j];
        }
        // 检查分配后是否安全
        if(stest()) cout<<"允许"<<n<<"进程申请资源！\n";
        else
        {
            // 不安全，撤销分配（回滚账本）
            cout<<"不允许"<<n<<"进程申请资源！\n";
            for(j=0; j<r; j++)
            {
                allocation[n-1][j] -= request[j];
                need[n-1][j] += request[j];
                available[j] += request[j];
            }
        }
    }
    else
    {
        cout<<"申请资源量越界！\n";
    }
}

6. 主函数（main）

作用：程序入口，协调所有功能。

int main()
{
    int i,n;       // n=申请资源的进程编号
    cout<<"请输入进程数：";
    cin>>p;
    cout<<"请输入资源种类数：";
    cin>>r;
    infInput();// 输入核心矩阵/向量
    // 检查初始状态是否安全
    if(stest()==1) cout<<"存在安全序列，初始状态安全。\n";
    else cout<<"不存在安全序列，初始状态不安全。\n";
    // 处理进程的资源申请
    cout<<"请输入发出请求向量request的进程编号：";
    cin>>n;
    cout<<"请输入请求向量request\n";
    for(i=0; i<r; i++) cin>>request[i];
    rtest(n);
    return 0;
}

7. 测试数据输入 & 运行结果

运行后会输出：

初始状态的安全序列（比如 P2→P1→P3→P4）；
提示 “存在安全序列，初始状态安全”；
若输入进程 1 申请 [1,0,1]，会提示 “允许 1 进程申请资源！”。

七、总结

核心思想：银行家算法通过 “先评估、后分配” 的方式避免死锁，核心是判断分配后系统是否存在安全序列；
关键步骤：检查请求合法性 → 假设分配 → 安全检测 → 决定是否真分配；
核心账本：Max（最大需求）、Allocation（已分配）、Need（剩余需求）、Available（可用资源），其中 Need=Max-Allocation；
安全序列：能让所有进程完成的执行顺序，只要存在安全序列，系统就不会死锁。

银行家算法是操作系统中死锁避免的经典算法，看似复杂，实则是 “银行放贷逻辑” 的翻版。