这是我做过印象最深的一个操作系统实验。理论课上听银行家算法觉得不就是几个数组来回比大小吗真到自己动手写代码、构造数据、跑安全序列的时候才发现里面的细节多得超乎想象尤其是安全性检查那一层循环稍不留神就给你死循环或者输出一个根本不合法的安全序列。这篇文章我把当时做实验的完整思路写出来从算法原理到数据结构设计从安全性检查的逐步推演到完整代码框架再到我踩过的几个坑。无论你是刚学到死锁这一章还是正在赶实验报告都应该能从中找到能直接用的东西。1. 实验前的理解银行家算法到底在解决什么问题先把这个实验的定位说清楚。操作系统里的死锁问题是老生常谈四个必要条件互斥、持有并等待、不可抢占、循环等待。针对这四个条件有死锁预防、死锁避免、死锁检测与解除几种思路。银行家算法属于死锁避免它的核心不是等死锁发生了再去解除而是在每次资源分配之前先模拟一下分配之后系统是否还处于安全状态如果不安全就拒绝分配。这个思路的源头是Dijkstra在1965年提出的本意是解决单种资源的银行信贷问题后来被推广到操作系统的多类资源分配场景。名字的由来很好记系统就像银行家进程就像客户银行家手里的资金就是系统的可用资源客户申请的贷款就是进程请求的资源。银行家不会把所有钱都贷出去总要留一部分保证在极端情况下也能让所有客户把钱还清对应到系统里就是分配资源后必须保证存在一个安全序列让所有进程都能顺利完成。我在做实验之前把死锁预防、避免、检测这三者的关系理了一遍这对理解实验目的帮助很大策略核心思想典型做法缺点死锁预防破坏四个必要条件之一资源一次性分配、资源有序分配资源利用率低进程并发性差死锁避免分配前判断是否安全银行家算法需要提前知道进程最大需求死锁检测与解除允许死锁发生发现后处理资源分配图、进程撤销检测时机难把握回收成本高银行家算法属于中间路线它不限制进程的资源申请方式也不要求进程一次性申请全部资源只是在每次分配时多做一次安全性预判。代价是需要每个进程提前声明自己对每类资源的最大需求量 Max这在某些场景下不太现实但在实验里是完全合理的假设。做这个实验之前建议你先别急着写代码把两个小问题想明白第一个是 Available、Max、Allocation、Need 这几个数据结构分别代表什么它们之间是什么关系第二个是资源分配算法和安全性算法到底是怎么嵌套在一起的。这两个问题想通了代码就是按部就班的事。1.1 安全性判断的本质存在一个可完成的进程序列银行家算法整个体系里安全性算法是灵魂。它的本质是给定当前系统的资源分配状况判断是否存在一个进程执行序列 P1, P2, ..., Pn使得按照这个顺序每个进程都能在系统剩余资源加上之前所有已完成进程释放的资源后获得自己所需的全部资源并顺利运行结束。这个判断过程不需要真实执行进程只需要在数据结构层面做模拟。系统维护一个 Work 向量初始等于当前可用资源 Available再维护一个 Finish 数组初始全为 false。然后反复扫描进程集合找出一个满足条件的进程它的 Finish 为 false并且它对每类资源的需求量 Need 都不超过当前的 Work。找到就把这个进程标记为 Finish true并把它的 Allocation 加到 Work 上然后继续扫描。如果某轮扫描找不到任何满足条件的进程但还有进程没有完成就说明系统处于不安全状态。这个逻辑用生活中的例子类比假设你有几个朋友分别要借不同数量的钱你手里的现金有限但他们借到钱后过一段时间会还钱并且还带利息。你每借出一笔就得盘算一下按照目前的现金流能不能找到一个顺序把所有朋友的需求都满足并且最终钱都能收回来。如果一个都满足不了那就一个都别借。我在理解这个算法的时候最大的感触是安全性判断强调的不是当前能满足谁的请求而是未来能不能找到一个可行的完成序列。一个看起来不能满足任何进程的瞬间可能只是因为资源集中在某个进程手里等它运行完释放资源后面就豁然开朗了。1.2 为什么实验中要模拟预分配银行家算法的资源分配过程里有一个很关键的操作叫预分配。当一个进程 Pi 发出资源请求 Request 向量时算法并不是直接拒绝或者直接分配而是先假设这次分配完成修改数据结构Available Available - RequestAllocation[i] Allocation[i] RequestNeed[i] Need[i] - Request修改完之后立刻调用安全性算法检查当前状态。如果检查结果是安全的说明这次假设性分配可行于是把假设变为现实如果检查结果是不安全的则撤销刚才的三步修改恢复原状并让进程等待。这个假设-检查-决定的流程正是银行家算法区别于其他资源分配算法的地方。我当时第一次看代码时容易犯一个错误就是忘了在安全性检查失败后恢复数据导致整个数组状态乱掉后续所有判断全是错的。写代码的时候一定要把数据的快照、恢复逻辑当成一等公民来处理而不是只在纸面上想想。2. 核心数据结构与参数设计代码层面银行家算法需要维护的数据结构并不复杂关键是每个数组的含义要非常清楚不能含糊。Available长度为 m 的一维数组Available[j] 表示当前系统中第 j 类资源的可用数量Maxn 行 m 列的矩阵Max[i][j] 表示进程 i 对第 j 类资源的历史最大需求Allocationn 行 m 列的矩阵Allocation[i][j] 表示进程 i 当前已分配到的第 j 类资源数量Needn 行 m 列的矩阵Need[i][j] 表示进程 i 还需要的第 j 类资源数量其中 Need 不一定要单独存储因为 Need Max - Allocation可以在需要时实时计算。但我强烈建议在实验代码里单独开一个 Need 数组理由有两个一是实验报告的代码可读性更好老师一目了然二是在预分配和恢复的过程中直接维护 Need 比每次临时计算更不容易出错。请求向量 Request每个进程发起一次资源请求时带上一个长度为 m 的向量Request[j] 表示要请求第 j 类资源的数量。如果一个进程想一次性申请多类资源Request 就是一个完整的向量而不是分别发多次请求。我在做设计的时候给每个资源类型都编了号例如 0 号资源、1 号资源、2 号资源分别用宏定义或者枚举类型表示。这个看起来是小事但后期测试不同的例子时需要频繁改资源数量和进程数量统一用常量定义会省很多事。2.1 典型测试用例的构造实验指导书一般会给出一个经典用例比如 5 个进程、3 类资源。我当年用的是这个例子初始状态如下进程Max (A B C)Allocation (A B C)Need (A B C)P07 5 30 1 07 4 3P13 2 22 0 01 2 2P29 0 23 0 26 0 0P32 2 22 1 10 1 1P44 3 30 0 24 3 1Available 初始为 (3 3 2)。这个例子的经典之处在于它既有足够的复杂度5 个进程、3 类资源又存在一个明显但不唯一的安全序列。我记得算出来的安全序列可以是 P1、P3、P4、P0、P2也可能是 P1、P3、P4、P2、P0取决于扫描顺序。自己构造测试数据的时候建议遵循几个原则初始 Allocation 的各列之和不能超过各类资源的总量这是基本约束Max 的每一项都必须大于等于 Allocation 的对应项否则数据本身矛盾Need 矩阵里至少要有一些进程的某些需求能立刻被 Available 满足否则系统一开始就是不安全状态后续分配无从谈起也可以故意构造一些边界情况比如某个进程的最大需求就是当前已分配的资源即 Need 为 0表示它只需要再运行一段时间就能释放资源或者某个进程的 Request 大于它的 Need从算法逻辑上就应该直接报错。2.2 资源总量、已分配总量与可用量的关系除了上面四个核心结构还可以额外设计两个辅助数组资源总量 Total 和已分配总量 AllocatedTotal。其中 AllocatedTotal[j] 是所有进程对第 j 类资源已分配的数量之和Total[j] 是系统中第 j 类资源的总数则 Available[j] Total[j] - AllocatedTotal[j]。有些实现会在初始化时直接读入 Available这就绕过了 Total 和 AllocatedTotal 的计算。但如果实验报告要求展示资源分配的全过程建议还是把 Total 数组引入让程序先读入 Total再读入 Max 和 Allocation然后自动计算 Need 和 Available。这样好处是数据一致性有保障万一你输入的 Allocation 加起来超过了 Total程序可以立即报错而不是带着错误数据往下跑。我当时就是吃了这个亏。一开始图省事直接从键盘输入 Available结果有一次测试数据敲错了Available 和 Allocation 之和明显对不上系统资源总量但程序没有任何反应跑出来的安全序列怎么都不对。后来改成从 Total 和 Allocation 反推 Available再在初始化时做一致性校验就再没出现过这种问题。3. 核心实现安全性检查与资源分配的双层结构银行家算法的完整流程分两层。第一层是资源请求处理第二层是安全性检查。我用伪代码把这个双层结构写出来银行家算法主流程 输入 Request 向量 if Request Need: 报错请求超过最大需求 else if Request Available: 让进程等待不分配 else: 预分配修改 Available、Allocation、Need 调用安全性算法 if 安全: 真正分配 else: 回滚预分配的修改进程等待安全性算法流程Work Available Finish 全部置为 false 循环: 找到一个进程 i满足: Finish[i] false 且 Need[i] Work 如果找到: Work Work Allocation[i] Finish[i] true 记录安全序列 如果找不到: break 检查是否所有 Finish 都为 true 是: 系统安全返回安全序列 否: 系统不安全这个双层结构里最容易出错的地方是安全性算法中找到一个进程这一步。注意是每一轮从头开始扫描而不是从上次找到的位置继续往后扫。因为某个进程在当前轮可能因为资源不足以被跳过但等前面某个进程释放资源后在下一轮扫描时它就变得可以满足了。如果只扫一遍就停止可能会误判系统不安全。我当时在实现安全性算法的时候用的是一层 while 循环套一层 for 循环。for 循环负责从 0 到 n-1 扫描所有进程找到第一个满足条件的就跳出本轮 for然后 while 判断本轮是否找到了新进程。如果一轮 for 下来一个都没找到说明没有办法继续推进了直接退出 while。3.1 一步一步推演安全性检查拿上面那个经典用例来手动推演一遍安全性检查把过程感受一下。初始状态Work Available (3 3 2)Finish 全为 false第一轮扫描P0Need (7 4 3)(7 4 3) (3 3 2)不满足P1Need (1 2 2)(1 2 2) (3 3 2)满足。Work (3 3 2) (2 0 0) (5 3 2)Finish[1] true安全序列记为P1第二轮扫描P0Need (7 4 3)(7 4 3) (5 3 2)不满足P2Need (6 0 0)(6 0 0) (5 3 2)不满足P3Need (0 1 1)(0 1 1) (5 3 2)满足。Work (5 3 2) (2 1 1) (7 4 3)Finish[3] true安全序列记为P1, P3第三轮扫描P0Need (7 4 3)(7 4 3) (7 4 3)满足。Work (7 4 3) (0 1 0) (7 5 3)Finish[0] true安全序列记为P1, P3, P0第四轮扫描P2Need (6 0 0)(6 0 0) (7 5 3)满足。Work (7 5 3) (3 0 2) (10 5 5)Finish[2] true安全序列记为P1, P3, P0, P2第五轮扫描P4Need (4 3 1)(4 3 1) (10 5 5)满足。Work (10 5 5) (0 0 2) (10 5 7)Finish[4] true安全序列记为P1, P3, P0, P2, P4所有进程 Finish 都为 true状态安全。这个推演过程看起来啰嗦但写实验报告的时候非常有用。我当时把每一步的 Work、Finish、安全序列都列了一张大表老师直接在报告上批了过程清晰。3.2 不安全状态的构造实例为了验证程序对不安全状态的判断是否正确我还专门构造了一个例子。假设系统有 3 个进程、2 类资源状态如下进程MaxAllocationNeedP0(6 5)(4 2)(2 3)P1(3 2)(1 0)(2 2)P2(4 3)(1 0)(3 3)Available (0 1)。这个状态下没有任何一个进程的 Need 能被当前 Available 满足P0 需要 (2 3)P1 需要 (2 2)P2 需要 (3 3)而可用资源只有 (0 1)。安全性检查直接判定为不安全所有请求都应该被拒绝。这种用例的价值在于检验程序的边界判断能力当 Available 不能满足任何一个进程时程序应当立刻报告不安全状态而不是陷入死循环或输出错误结果。3.3 C语言的参考实现用 C 语言实现银行家算法是一个经典做法。我提供一个简化但完整的参考框架重点展示初始化、请求处理和安全性检查的关键逻辑。#define MAX_PROCESS 10 #define MAX_RESOURCE 10 int n, m; // 进程数资源类型数 int Available[MAX_RESOURCE]; int Max[MAX_PROCESS][MAX_RESOURCE]; int Allocation[MAX_PROCESS][MAX_RESOURCE]; int Need[MAX_PROCESS][MAX_RESOURCE]; int SafeSequence[MAX_PROCESS]; // 记录安全序列 // 安全性检查安全返回 1不安全返回 0 int isSafe() { int Work[MAX_RESOURCE]; int Finish[MAX_PROCESS] {0}; int count 0; for (int j 0; j m; j) { Work[j] Available[j]; } while (count n) { int found 0; for (int i 0; i n; i) { if (Finish[i]) continue; int canAlloc 1; for (int j 0; j m; j) { if (Need[i][j] Work[j]) { canAlloc 0; break; } } if (canAlloc) { for (int j 0; j m; j) { Work[j] Allocation[i][j]; } SafeSequence[count] i; Finish[i] 1; found 1; } } if (!found) { return 0; // 本轮找不到可推进进程不安全 } } return 1; } // 处理进程 pid 的资源请求 request[] int requestResource(int pid, int request[]) { // 第一步判断 request 是否超过 Need for (int j 0; j m; j) { if (request[j] Need[pid][j]) { printf(错误请求超过最大需求\n); return -1; } } // 第二步:判断 request 是否超过可用资源 for (int j 0; j m; j) { if (request[j] Available[j]) { printf(资源不足进程等待\n); return 0; } } // 第三步预分配 for (int j 0; j m; j) { Available[j] - request[j]; Allocation[pid][j] request[j]; Need[pid][j] - request[j]; } // 第四步安全性检查 if (isSafe()) { printf(分配成功安全序列为: ); for (int i 0; i n; i) { printf(P%d , SafeSequence[i]); } printf(\n); return 1; } else { // 回滚 for (int j 0; j m; j) { Available[j] request[j]; Allocation[pid][j] - request[j]; Need[pid][j] request[j]; } printf(分配后系统进入不安全状态请求被拒绝\n); return 0; } }这段代码的关键点有三个第一个是在安全性检查的 while 循环里每轮都要从头开始扫描所有进程找到第一个可推进的进程就更新 Work第二个是回滚操作必须把 Available、Allocation、Need 三个数组全部还原少一个都不行第三个是安全序列的记录方式用一个一维数组按顺序记录最后输出。我在完成实验后把这段代码整理到了实验报告附录里。实际运行时把输入数据改成环境里指定的大小所有逻辑都不用变。3.4 资源回收与进程结束的模拟实验里还有一个细节当一个进程运行结束后它占用的资源应该被回收。理论上进程结束意味着它的 Allocation 全部返还给系统即 Available Allocation[i]同时把 Max[i]、Allocation[i]、Need[i] 对应行清零。资源回收这一步在银行家算法实验里通常不是重点因为安全性算法已经隐式地处理了资源释放Work Work Allocation[i] 就是在模拟进程结束后的资源归还。但如果你的实验要求模拟多个进程依次发起请求、运行、释放的完整过程那就需要单独实现一个 releaseResource 函数显式地把进程的资源释放回 Available。我在扩展实现的时候把进程状态分成了三个未开始、运行中、已完成。安全性算法里每找到一个满足条件的进程就相当于把它推到了运行中状态当它运行完释放资源就进入已完成状态。这样整个并发过程看起来更像真实操作系统。4. 实验中常见问题与排查方法做实验的时候遇到的报错和逻辑问题比想象中多很多。下面整理几个我当年踩过的坑。4.1 安全性检查误判把安全状态判成不安全这是最隐蔽的问题症状是输入一个教科书上明明安全的状态程序却输出系统不安全。排查思路很简单把安全性检查中间过程中每一轮的 Work 打印出来手动对照。通常问题出在 while 循环的推进逻辑上。比如有的同学用 for 循环只扫描了一遍就结束没有反复扫描还有的同学在找到一个进程后没有立即回到开头重新扫描导致漏掉了前面之前不满足、现在变满足的进程。这类问题通过打印中间变量基本都能定位。我当时养成了一个习惯就是写算法类代码时默认开启调试输出用一个 DEBUG 开关控制在终端打印关键中间结果跑完再关掉。省去了反复改代码加 printf 的麻烦。4.2 预分配后忘记回滚数据全乱如果第一次请求能通过安全性检查第二次请求开始各种怪异报错大概率是回滚逻辑没写对。回滚操作必须严格等价于预分配操作的逆操作。预分配做了三个减法Available 减、Need 减、Allocation 加回滚就要做三个加法/减法Available 加、Need 加、Allocation 减。少写一个后面就全乱。这里有一个很实用的防御性编程技巧在预分配前把三组数据保存到临时变量回滚时直接恢复而不是手动做加减运算。这样即使算法的逻辑不小心写错了回滚也是绝对正确的。4.3 测试数据构造不合理无法体现算法效果有的同学测试时输入的数据本身就是不安全的算法上去就报不安全然后误以为程序写错了。这个不算 bug但对测试用例的构造提出了要求。想要验证程序的安全分配路径就设计一个初始安全的状态想要验证拒绝分配路径就在安全状态的基础上让某个进程请求大量资源大到分配后系统进入不安全状态。两条路径都有用例覆盖实验报告才有说服力。4.4 数组越界和输入格式问题银行家算法涉及大量矩阵运算数组越界是家常便饭。尤其是循环变量范围写错比如 for (int i 0; i n; i)就会越界读到脏数据导致各种莫名其妙的判断。另一个常见问题是输入时进程编号和资源编号从 0 开始还是从 1 开始。我建议全程统一从 0 开始包括界面友好提示里也直接显示 P0、P1避免转换带来的混乱。还有一种情况是键盘输入时多敲了空格或回车scanf 读取失败变量没有被正确赋值。这个通常没什么好办法写程序时对 scanf 的返回值做一下检查输入失败就重新提示。4.5 死循环安全性检查卡住不动死循环一般出现在 while (!found) 和 while (count n) 的组合判断上。如果一轮扫描中找到了一个进程但 count 没有增加或者 found 标志没有正确重置就会死循环。我自己遇到过一种情况在 while 循环里找到进程后直接 continue 跳出本轮但 found 标志忘记置 1导致外层 while 判断认为本轮没有找到进程直接退出输出不安全。这个 bug 特别难发现因为逻辑看起来都对但就是少了一行赋值的代码。后来我习惯在关键分支处加断言式的打印问题才暴露出来。5. 实验报告撰写与程序演示的落地建议操作系统实验一般要求交一份报告里面得包含需求分析、概要设计、详细设计、程序代码、运行结果和实验总结。银行家算法这个实验的技术点很集中报告写起来有自己的套路。需求分析部分重点说清楚输入是进程数、资源类型数、各类资源总量、每个进程的最大需求和初始分配情况以及动态的请求序列输出是每次请求的分配结果如果分配成功则输出安全序列如果拒绝则说明原因。操作可行性方面强调算法的时间复杂度是可以接受的因为进程数和资源类型数在实验场景下都是小规模。概要设计部分建议画清楚模块划分。我当时分了三个模块初始化模块负责读入数据并校验资源请求模块负责处理每次请求执行预分配和回滚安全性检查模块负责判断状态是否安全。模块之间的调用关系就是主程序在收到请求后调用资源请求模块资源请求模块再调用安全性检查模块。详细设计部分除了给出代码还可以把关键的数据结构和函数说明列成表格。比如每个函数的功能、输入参数、输出结果、调用的子函数让老师在五分钟内就能看懂代码结构。运行结果部分至少应该包括三个场景场景一正常的资源请求分配成功输出安全序列场景二资源请求暂时无法满足进程等待场景三资源请求满足但分配后系统进入不安全状态请求被拒绝每个场景截一张运行截图附上输入数据和输出结果。最后再用一小段文字说明这个结果证明了算法的正确性。5.1 演示数据设计的小技巧演示数据不用太复杂但要有层次。第一个场景用经典的 5 进程 3 资源例子让老师看到熟悉的安全序列第二个场景可以用一个进程请求超过当前可用资源的数据展示等待分支第三个场景可以在安全状态的基础上构造一个接近极限的请求比如让当前 Available 刚好够分配但分配后没有进程能完成了展示拒绝分支。我记得当年最关键的一个演示是在 P1 已经运行结束并释放资源后再让 P4 请求 1 个 A 类资源和 1 个 B 类资源这个时候系统状态已经变化算法能正确响应。这个动态变化的场景比静态展示更能体现算法的价值。5.2 扩展思考从单次模拟到完整并发流程实验做完后如果还有余力可以想想怎么把程序扩展成一个支持多进程自动发起请求、运行、释放的模拟器。这就涉及更完整的数据结构设计每个进程要有状态字段记录它是就绪、运行、阻塞还是完成每个进程要有自己的指令序列比如先请求 A 资源运行 10 个时间单位再请求 B 资源最后释放全部资源。这样做之后实验报告的内容会丰富很多你可以展示一个完整的并发调度过程说明在哪些时间点发生了进程阻塞在哪些时间点银行家算法拒绝了请求。这个扩展不复杂但在课程设计的层面上会显得很有深度。我还见过有的同学用 Python 的 tkinter 库给银行家算法做了一个简易的图形界面左边显示每个进程的 Max、Allocation、Need 矩阵右边实时显示当前 Available下方是每次请求的日志。虽然不是必须的但确实帮助理解算法执行过程。我个人在实际操作中的体会是银行家算法是少数几个代码量不大但逻辑密度很高的实验。它考验的不是你写过多少代码而是你对数据结构的定义够不够清晰、对流程的边界情况考虑得够不够周全。做完这个实验以后我再看操作系统的其他资源管理算法比如哲学家就餐、读者写者问题思路都会清晰很多。最后再分享一个小技巧如果你在验证代码正确性的时候拿不准可以把课本上的经典例题原样输入看输出的安全序列是否和课本一致。如果一致基本可以放心程序的核心逻辑没问题如果不一致先检查是不是资源编号、进程编号的排序方式和课本不同比如课本的进程可能叫 P1 到 P5你的程序从 P0 开始编号输出的序列就会整体偏移一个编号。这种编号平移的问题最容易让人误以为算法写错了。