简介操作系统银行家算法常见于操作系统课程中的死锁避免章节这份实验资料包面向本科阶段学习并发控制与资源分配的学生用于理解迪杰斯特拉在1965年提出的经典安全性检查思想。压缩包共5个文件以两个cpp实现主逻辑配合h头文件声明类接口docx实验报告讲解算法原理与运行结果txt文件提供初始化数据整体体积仅452KB便于下载与本地编译调试。内容覆盖银行家算法的四大核心数据结构——最大需求矩阵、可用资源向量、已分配矩阵与需求矩阵并通过初始化、请求、安全性检查、资源分配与释放的完整流程模拟资源调度。源代码内含进程管理、资源申请与释放及模拟循环代码注释清晰可自行修改初始化数据验证不同安全序列。实验报告还讨论了资源分配不当、资源泄露及错误安全性检查等典型问题能够帮助读者加深对死锁预防的感性认识。已有5248人学习下载适合操作系统课程设计或期末复习时对照参考。1. 银行家算法把死锁风险掐死在资源分配之前操作系统实验里最折磨人的不是写进程调度而是调资源分配。一组请求发下去系统当场卡死你连是哪个进程在等哪类资源都查不出来。银行家算法就是用来在分配前做安全检查的每次请求都先模拟分配验证系统还能不能找到一条安全序列找不到就拒绝。这套「实验报告 源代码」就是干这个的适合操作系统课设、考研复试和面试手撕算法的同学。代码用 Python 写不依赖第三方库进程数和资源类型数都可以自己调实验报告里把原理、数据结构、流程和结果分析都补齐了拿回去改成自己的实验环境就能交。读完这篇你能独立写出安全检测函数也能解释清楚为什么同一组数据里 P1 可以先执行而 P0 必须等。2. 核心数据结构与安全检测先看懂四个矩阵再动手2.1 四个数据结构Available、Max、Allocation、Need 各管什么银行家算法的全部状态都压在四个数据结构上代码写错大多是因为对这四个家伙的理解是糊的而不是语法问题。先把它们摆开数据结构维度含义来源 / 更新时机Available1 × m 向量当前系统中各类资源还剩多少可用系统维护分配时扣除、释放时累加Maxn × m 矩阵每个进程运行结束前对各类资源的总需求上限进程启动时声明之后不再变化Allocationn × m 矩阵每个进程当前已占用的各类资源数每次成功分配后累加Needn × m 矩阵每个进程还需要的各类资源数不独立输入Need Max - Allocation注意 Need 是推导出来的列不是抄进去的。实验里最常见的第一类错误就是把 Max、Allocation、Need 三个矩阵当成三份独立输入往代码里塞结果手算的 Need 和代码算出来的对不上。任何一个进程的 Allocation 大于 Max这套数据就是非法的初始化阶段直接抛异常比后面查半天强得多。还有一个细节Available 的初值在教科书例题里是直接给的但真实实验里它应该等于资源总量减去所有进程 Allocation 的列和。我在做实验时习惯在初始化最后打印一次三矩阵对照表确认每行满足 Allocation ≤ Max每列满足 Allocation 列和 ≤ 资源总量再往下走。这一步多花三十秒后面省掉的是半小时的排错时间。2.2 安全性检查银行家凭什么敢放贷银行家算法的核心是安全性检查思路可以类比银行放贷银行不会一次性把所有钱借光它要保证任何时候手里剩下的钱至少能支撑一个客户把贷款还清这个客户还清后银行手里钱变多再去找下一个能还清的客户。如果所有客户都能按某个顺序还清说明当前账目是安全的继续放贷不会引发挤兑。对应到系统里就是Work 向量初始化为当前 AvailableFindish 数组初始全为 false每轮从头扫描找出一个仍未完成、且 Need 每一类资源都不超过 Work 的进程模拟它运行完毕把它的 Allocation 加回 Work标记完成。重复直到所有进程都完成或某轮扫描没有任何进程能满足——后者说明系统找不到安全序列处于不安全状态。这里的关键是模拟进程释放资源而不是从别的进程手里抢占这是死锁避免和死锁检测的本质区别。这里要拎清两个概念面试和实验报告里都常被追问安全状态一定不会死锁不安全状态不一定立刻死锁只是存在死锁风险。银行家算法因为假设每个进程最终会申请完整个 Max判断比实际运行更保守所以可能拒绝一些实际能跑通的请求这是算法固有的代价不是代码 bug。3. 源代码实现从数据结构到请求回退的完整流程3.1 数据组织与初始化把校验写进构造函数我一般把银行家算法封装成一个 Banker 类构造函数接收 Available、Max、Allocation 三份数据Need 在内部推导同时做数据合法性校验。下面这份代码和资源包里的核心逻辑一致可以直接用。class Banker: def __init__(self, available, max_matrix, allocation): self.n len(max_matrix) # 进程数 self.m len(available) # 资源类型数 self.available available[:] # 拷贝避免外部修改 self.max [row[:] for row in max_matrix] self.allocation [row[:] for row in allocation] # 数据校验任何进程的已分配资源不能超过最大需求 for i in range(self.n): for j in range(self.m): if self.allocation[i][j] self.max[i][j]: raise ValueError(fP{i} 的 Allocation 大于 Max数据非法) # Need Max - Allocation逐元素相减 self.need [[self.max[i][j] - self.allocation[i][j] for j in range(self.m)] for i in range(self.n)] # 初始化后打印对照表方便人工核对 for i in range(self.n): print(fP{i} Max{self.max[i]} Alloc{self.allocation[i]} Need{self.need[i]})这段代码有个容易忽略的点三个矩阵全部做了拷贝。Python 里直接 self.available available 只是多了一个引用外部列表被改类内部也跟着变。数据校验放在构造函数里输入用例有问题能第一时间暴露而不是等到安全性检查跑出诡异结果才回头查数据。3.2 安全性检查十几行代码里的核心逻辑安全性检查是整套算法的题眼。我用显式循环加 break 的写法不用 all() 一行式原因很简单实验阶段你需要能在每个分支打印中间结果一行式在排查时很难插桩。def safety_check(self): work self.available[:] # Work 初值 当前 Available finish [False] * self.n # 所有进程都未完成 sequence [] # 记录安全序列 while len(sequence) self.n: progress False # 本轮是否找到了可推进的进程 for i in range(self.n): if finish[i]: continue # 判断 Need 的每一类资源是否都不超过 Work can_alloc True for j in range(self.m): if self.need[i][j] work[j]: can_alloc False break if can_alloc: # 模拟进程运行完毕释放它占用的全部资源 for j in range(self.m): work[j] self.allocation[i][j] finish[i] True sequence.append(fP{i}) progress True if not progress: # 一轮扫描下来没有进程能被满足系统不安全 return False, [] return True, sequence逻辑说明外层 while 控制总轮数每轮都从 0 号进程重新扫描这不是重复劳动而是因为前面进程释放资源后 Work 变大了之前不满足的进程可能这轮就满足了。内层三个 if 分别对应三种情况已完成的跳过、需求不满足的跳过、满足就模拟释放并记入序列。progress 标记是本轮是否有进展一旦某轮完全找不到可推进进程说明剩下的进程都卡在资源上直接判定不安全。这个函数不改动任何成员变量只是读数据做判断所以它可以在请求分配前被反复调用。3.3 请求处理试探性分配加现场回退请求处理是银行家算法和朴素分配的最大区别先假装分配跑一遍安全性检查不安全就把现场还原。这里的回退必须做完整三个矩阵一个都不能漏。def request(self, pid, req): # 第一步请求不能超过进程还需要的量 if any(req[j] self.need[pid][j] for j in range(self.m)): return False, 请求超过 Need非法请求 # 第二步请求不能超过当前可用资源 if any(req[j] self.available[j] for j in range(self.m)): return False, 请求超过 Available进程需等待 # 第三步试探性分配先备份现场 save_avail self.available[:] save_alloc [row[:] for row in self.allocation] # 二维列表必须逐行拷贝 save_need [row[:] for row in self.need] for j in range(self.m): self.available[j] - req[j] self.allocation[pid][j] req[j] self.need[pid][j] - req[j] # 第四步安全性检查决定是否回退 safe, seq self.safety_check() if not safe: self.available save_avail self.allocation save_alloc self.need save_need return False, 分配后系统不安全已回退 return True, f分配成功安全序列: { - .join(seq)}参数说明pid 是发起请求的进程编号req 是和资源类型等长的请求向量。前两步是合法性检查顺序不能换——超过 Need 的请求是逻辑非法超过 Available 是暂时不可行两种拒绝理由在实验报告里要分开写。备份用的是逐行拷贝而不是浅拷贝这是三维数据回退最容易踩的坑后面避坑章节会展开。整个请求函数的关键设计是只有通过安全性检查试探性分配才会保留否则一切归零对外部调用者来说系统状态就像从未发生过这次请求。主程序入口只需要构造用例和调用请求if __name__ __main__: available [3, 3, 2] max_matrix [ [7, 5, 3], [3, 2, 2], [9, 0, 2], [2, 2, 2], [4, 3, 3], ] allocation [ [0, 1, 0], [2, 0, 0], [3, 0, 2], [2, 1, 1], [0, 0, 2], ] banker Banker(available, max_matrix, allocation) print(初始安全序列:, banker.safety_check()[1]) print(banker.request(1, [1, 0, 2])) print(banker.request(0, [0, 2, 0]))这段代码在 Ubuntu 或任何 Linux 终端里直接python3 banker.py就能跑不需要装任何依赖。下面的章节会用这份代码跑出完整输出再讲实验报告怎么把结果写成老师愿意给高分的样子。4. 跑通实验教科书用例与实验报告的写法4.1 教科书用例5 进程、3 类资源跑出安全序列资源包的代码默认带的就是《计算机操作系统》教材里的经典用例5 个进程、3 类资源数据如下进程MaxAllocationNeed Max - AllocationP0(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)初始 Available (3,3,2)。运行后的预期输出是初始安全序列: P1 → P3 → P4 → P0 → P2 P1 请求 (1,0,2) 分配成功安全序列: P1 → P3 → P4 → P0 → P2 P0 请求 (0,2,0) 分配后系统不安全已回退为什么第一轮选中的是 P1 而不是 P0因为 Work 初值是 (3,3,2)P1 的 Need 是 (1,2,2)每类都够P0 的 Need 是 (7,4,3)第一类资源就要 7 个当前只有 3 个。顺着这个逻辑手推一遍整个序列P1 释放后 Work 变成 (5,3,2)P3 的 (0,1,1) 满足P3 释放后 Work 变成 (7,4,3)P4 的 (4,3,1) 满足再往后 P0、P2 依次满足。第二个输出值得注意P0 请求 (0,2,0) 时Available 是 (2,3,0)单项上够用试探分配后 Work 变成 (2,1,0)此时没有任何进程的 Need 能被满足系统进入不安全状态于是回退。这就是银行家算法宁可拒绝也不冒险的典型表现。安全序列不唯一只要从不同进程开始扫描可能得到不同顺序但判定结果只有安全和不安全两种。实验报告里可以主动写一句安全序列不唯一本实验从编号最小进程开始扫描免得老师质疑你和其他同学序列不一样。4.2 实验报告的四段式写法与老师追问实验报告我建议按四个部分写别堆砌。第一部分写实验目的核心一句话理解死锁避免思想掌握银行家算法的数据结构与安全性检查流程。第二部分写实验原理把四个数据结构的含义、Need 的推导关系、安全检测的步骤用文字加伪代码描述清楚这里不需要很长但必须把模拟分配、检查、回退这条主线点出来。第三部分贴运行结果包括初始三矩阵打印、安全序列输出、P1 请求成功的输出、P0 请求被拒的输出。第四部分写结果分析重点解释 P0 为什么被拒试探分配后 Work 无法推进任何进程说明这次分配会让系统进入不安全状态。报告里最容易被追问的还有三个点。第一银行家算法为什么保守因为它假设每个进程最终会申请完整个 Max而实际进程可能永远用不到那么多所以它可能拒绝实际安全的请求。第二不安全状态和死锁什么关系不安全不一定立刻死锁但存在演进成死锁的风险银行家算法要避免的正是进入这种状态。第三算法有什么局限需要预先知道每个进程的最大需求、进程数和资源数固定这两条在真实操作系统里都很难满足所以它更多是教学和理论价值。这三个问题在实验报告的结论部分主动写上去基本能堵住大多数追问。5. 避坑排查银行家算法实验的五个典型翻车点5.1 三条最容易翻车的代码错误翻车点一Need 矩阵出现负数安全检测永远失败。现象初始化后打印 Need出现 -2、-1 之类的负值或者安全性检查第一轮就找不到任何可推进的进程但手算明明有安全序列。原因把公式写反了Need Allocation - Max或者输入用例本身就有问题某个进程的 Allocation 大于 Max。教科书数据一般不会错错的基本都是公式方向。解决在构造函数里加校验发现 allocation[i][j] max[i][j] 直接抛异常同时把 Max、Allocation、Need 三张矩阵完整打印出来人工核对一遍再往下走。这套代码里已经内置了校验和打印你只需要确认输出和你手算的一致。翻车点二安全序列前半段正常后半段突然断裂。现象前两三个进程能顺利进序列到第四个、第五个时突然找不到能满足的进程系统报不安全可你拿笔在纸上推明明是安全的。原因Work 向量的更新写错了把work[j] allocation[i][j]写成了work[j] allocation[i][j]累加变成了覆盖。Work 是越滚越大的一旦被覆盖成某个进程的 Allocation后面所有判断全部失真。解决在每轮扫描结束后打印 Work 的变化安全序列生成过程中 Work 必须单调不减。只要看到 Work 回退不用怀疑就是累加写成了赋值。翻车点三拒绝分配后下一轮数据全乱。现象第一次请求被拒后再发起新的请求Available 或 Allocation 对不上号甚至矩阵内容越变越离谱。原因回退时只还原了 available忘了还原 allocation 和 need或者是浅拷贝问题Python 里[:]只拷贝了列表外层二维列表的内层行仍然是同一个引用回退时把原始数据一并改了。解决备份时必须逐行拷贝[row[:] for row in self.allocation]或者直接从 copy 模块导入 deepcopy。回退时三个结构一起还原顺序不要乱。这套代码里已经把备份和还原写成对称的三行就是让你一眼能看出哪三个东西在联动。5.2 两条概念性错误翻车点四把逐资源比较写成总量比较。现象请求 (1,0,2) 时Available 是 (2,1,0)第二类资源其实不够但用sum(request) sum(available)判断3 不大于 3误判为可以分配。原因资源类型是相互独立的(1,0,2) 和 (0,2,1) 对系统是完全不同的两回事不能把各类资源加总后做比较。解决所有涉及资源比较的地方不管是请求合法性、可用性判断还是安全性检查里的 Need 与 Work 比较都必须逐资源类型判断。代码里统一用any(req[j] available[j] for j in range(self.m))就是为了避免总量比较这种思维惯性。翻车点五把死锁避免写成死锁检测。现象实验报告的结论部分写系统检测到死锁于是剥夺 P2 的资源进行恢复被老师批概念错误。原因银行家算法是死锁避免策略用的是事前检查死锁检测是另一套机制事后发现死锁再做资源剥夺或进程回退。安全性检查失败不等于系统已经死锁它只是说明当前状态不安全存在死锁风险。解决实验报告结论统一写通过安全性检查拒绝不安全请求使系统始终处于安全状态。分析部分补一句不安全状态不一定立即死锁但可能演化为死锁故应避免进入这句到位了老师就知道你是真懂而不是背的。6. 进阶验证随机用例压测安全序列的正确性实验交上去之前我习惯给银行家算法做一轮随机压测用程序生成几百组合法用例跑安全性检查并校验输出满足不变量。这套代码如果你要改造成自己的版本压测是验证改动没改坏的最快方式。import random def gen_case(n, m, total): 生成 n 个进程、m 类资源的一组 Max 与 Allocation max_m, alloc_m [], [] for _ in range(n): alloc [random.randint(0, total[j]) for j in range(m)] # 保证 Max 每个分量不小于 Allocation max_row [alloc[j] random.randint(1, 5) for j in range(m)] max_m.append(max_row) alloc_m.append(alloc) return max_m, alloc_m def stress(times1000, n5, m3, total[10, 8, 7]): for seed in range(times): random.seed(seed) max_m, alloc_m gen_case(n, m, total) # Available 资源总量 - 各列 Allocation 之和不能为负 avail [total[j] - sum(alloc_m[i][j] for i in range(n)) for j in range(m)] if any(x 0 for x in avail): continue banker Banker(avail, max_m, alloc_m) safe, seq banker.safety_check() if safe: # 校验安全序列里的每个进程在加入时 Need 都满足 work avail[:] for pid_str in seq: pid int(pid_str[1:]) assert all(banker.need[pid][j] work[j] for j in range(m)) for j in range(m): work[j] banker.allocation[pid][j] assert len(seq) n if safe else True print(f压测完成 {times} 组未发现不变量被破坏)压测校验的核心是两条不变量一是安全序列中每个进程被选中时它的 Need 必须能被当时的 Work 满足二是序列长度必须等于进程数。只要这两条在几百组随机数据上都不被破坏安全性检查的正确性就有底气了。生成的用例里故意让 Max 比 Allocation 大至少 1避免出现 Need 全零的边界干扰。还有一个比压测更直接的技巧把安全序列的生成过程打印出来按当前 Work → 选中 P_i → 释放后 Work的格式输出然后拿纸笔对教材例题手推一遍两者对得上代码基本不会有问题。我记得第一次手推时发现打印里的 Work 和纸上差了一个数排查半天结果是备份还原时把 allocation 的引用搞混了从那以后我每次写完银行家算法都强制走一遍随机压测加手推核对确认序列合法才敢拿去交实验。希望帮到你。本文还有配套的精品资源点击获取