银行家算法实验报告与源码：死锁避免、安全序列及回滚实现-北京尧图网络

简介操作系统银行家算法实验报告与配套源代码面向学习操作系统课程、需要理解死锁避免与资源分配策略的高校学生及自学者。资源围绕Dijkstra提出的银行家算法展开可用于课程实验、算法复现与安全性检查练习。压缩包共5个文件以C源文件与头文件为主另含实验报告文档和初始化数据文本整体约452KB便于直接编译运行并对照报告梳理Max、Available、Allocated、Needs等数据结构的关系。已有5251人学习说明其在同类实验资料中具有较高参考价值。配套代码覆盖进程管理、资源申请与释放、模拟循环及安全性检查能帮助读者观察安全序列构造过程并针对资源分配不当、资源泄露、安全性检查错误等常见问题形成排错思路实验报告还对算法原理、数据结构定义和测试结果作了整理。1. 从一次真实的死锁翻车说起这套银行家算法实验要交付什么操作系统课设里死锁这一章最容易糊弄过去也最容易在答辩现场翻车概念背得滚瓜烂熟真给一组资源快照让手推安全序列笔尖就顿住了。这套银行家算法实验报告与源代码解决的就是这个断层——把 Available、Max、Allocation、Need 这几个抽象矩阵变成一个能读入快照、能打印安全序列、能对每次资源请求给出“准予/阻塞/拒绝”结论的可运行程序同时配一份结构完整的实验报告。它适合正在做操作系统课程设计、需要当场演示的读者也适合想把死锁避免从“背算法”改成“跑算法”的教学场景。下面按需求、数据结构、核心算法、交互与报告、避坑、验收六段拆开讲。2. 数据结构与状态建模把“银行家”翻译成四个矩阵加一个向量银行家算法的代码量其实不大一百多行就能跑通但它对状态一致性极为敏感——任何一个矩阵在某个分支里漏更新一次后面所有安全性判断就全成了玄学。因此这一章不讲算法本身先讲清楚“状态存在哪、由谁维护、什么时候重算”这是整份实验报告里最能体现设计能力的部分。2.1 先写清楚前提假设再动代码银行家算法不是通用的死锁解决方案它成立依赖一组很强的假设这些假设必须写在报告的问题分析一节里而不是藏在代码注释中每个进程在进入系统前就必须声明它对每类资源的最大需求量运行过程中这个数字不能改进程之间相互独立不存在因为同步顺序才产生的循环等待系统资源总量固定运行期间不增加也不销毁。这三条只要缺一条安全性检查算出来的“安全”就只是幻觉。我一般会在报告里用三行字点明假设再补一句“本实验处理的是进程数固定、需求预声明、多类资源单实例的情形”这样后面所有结论都有了适用范围。还有一个必须提前说明的点安全序列通常不唯一。同一组快照从不同的进程下标开始扫描可能得到 P1→P3→P4→P0→P2也可能得到 P1→P3→P4→P2→P0。两条都合法程序只需要输出其中一条报告里要写明“本实现按进程编号升序扫描故输出的是字典序最小的一条”否则答辩时被问一句“为什么和我算的不一样”就要卡壳。2.2 四个矩阵一个向量各自由谁写入这一层用一张表说清楚比写十行注释管用名称维度含义写入时机Available1×m系统当前各类空闲资源数初始快照读入每次分配成功或回收后更新Maxn×m每个进程对每类资源的最大需求只在初始快照读入时写一次之后只读Allocationn×m每个进程当前已持有的资源初始快照读入试探分配与回滚时更新Needn×m每个进程还需要的资源Need Max − Allocation由前两者推导随分配同步维护Request_i1×m第 i 个进程本次的请求向量每次请求时由交互层输入这里有个高频错误把 Need 当成独立输入让使用者手工敲一遍。短期看没毛病一旦 Max 或 Allocation 在测试过程中被改动Need 立刻和它们对不上程序就开始输出莫名其妙的安全序列。稳妥的做法是二选一——要么 Need 只读由一个recompute_need()在每次打印状态和每次安全性检查之前重算要么维护 Need但把所有会改动它的语句收敛到try_allocate()和rollback()两个函数里别的地方一律不许碰。提示报告里的“数据结构设计”小节建议直接放这张表再配一句“Need 为推导量不单独作为输入”这是评审最容易认可的设计说明。2.3 接口与快照文件格式把数据结构和接口单独放在一个头文件里好处是报告里可以按“数据结构—功能函数—主流程”三层讲代码截图也不会糊成一坨/* banker.h —— 数据与接口声明报告第四章可直接引用 */ #define PROC_NUM 5 /* 进程数报告里需说明为何取 5 */ #define RES_NUM 3 /* 资源类数对应 A/B/C 三类 */ extern int Available[RES_NUM]; extern int Max[PROC_NUM][RES_NUM]; extern int Allocation[PROC_NUM][RES_NUM]; extern int Need[PROC_NUM][RES_NUM]; int read_snapshot(const char *path); /* 读初始快照成功返回 0 */ void recompute_need(void); /* Need Max - Allocation */ void print_state(void); /* 打印四张表供报告截图 */ int is_safe(int seq[]); /* 安全性检查安全返回 1 */ int request(int pid, const int req[]);/* 处理一次资源请求返回状态码 */PROC_NUM和RES_NUM用宏而不是硬编码数字是因为测试环节要换快照——把 5 进程 3 资源换成 4 进程 2 资源做对照实验时只改这两个宏即可函数体一行都不用动。这一点写进报告能加不少分。初始状态不从终端一个个敲改成读文本文件。原因是答辩现场要临时改数据改文件里一行再重跑比在终端连敲 15 个数字再祈祷没敲错靠谱得多5 3 3 3 2 7 5 3 3 2 2 9 0 2 2 2 2 4 3 3 0 1 0 2 0 0 3 0 2 2 1 1 0 0 2第一行是进程数与资源类数第二行是 Available接下来 5 行 Max最后 5 行 Allocation。读取时用fscanf的返回值做校验读到一半失败就报错退出不要让半截数据进内存int read_snapshot(const char *path) { FILE *fp fopen(path, r); if (!fp) return -1; int n, m; if (fscanf(fp, %d %d, n, m) ! 2) { fclose(fp); return -1; } /* 文件声明的规模必须和编译期常量一致否则直接拒绝 */ if (n ! PROC_NUM || m ! RES_NUM) { fclose(fp); return -2; } for (int j 0; j RES_NUM; j) if (fscanf(fp, %d, Available[j]) ! 1) { fclose(fp); return -1; } for (int i 0; i PROC_NUM; i) for (int j 0; j RES_NUM; j) if (fscanf(fp, %d, Max[i][j]) ! 1) { fclose(fp); return -1; } for (int i 0; i PROC_NUM; i) for (int j 0; j RES_NUM; j) { if (fscanf(fp, %d, Allocation[i][j]) ! 1) { fclose(fp); return -1; } if (Allocation[i][j] Max[i][j]) { fclose(fp); return -3; } } fclose(fp); recompute_need(); return 0; }这段的关键不在读取而在两个校验规模校验拦住“文件写了 4 个进程、程序按 5 个分配”的越界Allocation Max校验拦住让 Need 变成负数的非法快照。少了这两处后面安全性检查会读出负数然后神奇地判定“安全”查起来相当痛苦。3. 核心算法实现安全性检查与请求处理的两段式结构整份代码真正有含金量的只有两个函数。安全性检查回答“当前这个状态还能不能走通”请求处理回答“这个请求能不能给”。前者是后者的子过程把两者的边界划清楚代码就不会互相污染。3.1 安全性算法的推演过程安全性检查的思路是模拟假设所有进程现在都停下来系统按某种顺序逐个把资源喂给它们看能不能全部喂完。能喂完就安全中途卡住就不安全。变量只有两组Work是“如果现在开始按这个顺序跑系统手里还有多少资源”初值等于 AvailableFinish标记每个进程是否已被假定完成。每一轮扫描所有未完成的进程找出一个 Need 不超过 Work 的把它的 Allocation 还回 Work标记完成记进安全序列一轮下来一个都没找到剩下的一律推不动判定不安全。/* 安全性检查安全返回 1 并把安全序列写入 seq不安全返回 0 */ int is_safe(int seq[]) { int Work[RES_NUM]; int Finish[PROC_NUM] {0}; int count 0; for (int j 0; j RES_NUM; j) Work[j] Available[j]; while (count PROC_NUM) { int found 0; /* 本轮是否找到可满足的进程 */ for (int i 0; i PROC_NUM; i) { if (Finish[i]) continue; int ok 1; for (int j 0; j RES_NUM; j) if (Need[i][j] Work[j]) { ok 0; break; } if (!ok) continue; for (int j 0; j RES_NUM; j) Work[j] Allocation[i][j]; Finish[i] 1; seq[count] i; found 1; /* 注意这里不 break本轮继续往后扫描让编号靠前的进程优先进入安全序列输出更稳定 */ } if (!found) break; /* 一整轮无人可满足提前退出 */ } return count PROC_NUM; }几个细节值得在报告里点出来。第一found这个标志不能省它是“一整轮无进展”的唯一证据靠count是否增长来判断也行但可读性差。第二内层找到可满足进程后不break而是继续扫完本轮这样输出的安全序列在同一份快照上永远一致方便写进报告做对照。第三Finish数组必须每调用一次就重新清零如果写成static或者全局变量第二次调用时上一轮的结果还在就会出现“明明不安全却判定安全”的诡异现象。复杂度是 O(n²m)外层最多 n 轮每轮扫 n 个进程每个进程比较 m 类资源。5 进程 3 资源的数据规模下完全无感但报告里把这个式子写出来说明你知道它在进程数上去之后会变慢。3.2 资源请求处理的四个返回分支请求处理是银行家算法的核心逻辑所在。一个请求进来要依次过四道关卡任何一道不过就返回对应状态码一道都过了才真正修改状态。第一道请求量是否超过该进程声明的剩余需求。超了就是非法请求程序员的错直接报错。第二道请求量是否超过系统当前可用。超了不是错误是正常现象——进程得排队等返回“阻塞”。第三道是试探性分配先把资源真给出去改 Available、Allocation、Need 三张表。第四道是安全性检查如果分配之后系统不安全必须把刚才三张表的修改原样退回去这就是回滚。/* 返回 1 成功0 资源不足需等待-1 超过最大需求-2 不安全已回滚 */ int request(int pid, const int req[]) { /* 关卡一不能超过该进程声明的剩余最大需求 */ for (int j 0; j RES_NUM; j) if (req[j] Need[pid][j]) return -1; /* 关卡二不能超过系统当前可用资源 */ for (int j 0; j RES_NUM; j) if (req[j] Available[j]) return 0; /* 关卡三试探性分配三张表一起改 */ for (int j 0; j RES_NUM; j) { Available[j] - req[j]; Allocation[pid][j] req[j]; Need[pid][j] - req[j]; } /* 关卡四分配后是否仍存在安全序列 */ int seq[PROC_NUM]; if (is_safe(seq)) return 1; /* 安全分配正式生效 */ /* 不安全把三张表原样退回去一条语句都不能少 */ for (int j 0; j RES_NUM; j) { Available[j] req[j]; Allocation[pid][j] - req[j]; Need[pid][j] req[j]; } return -2; }回滚这一段是整份代码最容易写错的地方因为它是“对称操作”看起来啰嗦很容易手滑只回滚两张表。漏回滚 Need 的后果是这次请求被拒绝了但进程的剩余需求凭空少了一块下一次它请求同样的量会被判成“超过最大需求”逻辑就彻底乱了。血泪经验是把这个函数写成“三张表永远同进同退”任何一张表的新增修改都必须在这一段里成对出现。把返回码整理成表放进报告测试结果一节会非常好写返回码含义程序动作1分配成功打印本次安全序列状态保留0当前可用资源不足进程阻塞等待状态不变-1请求超过声明的最大需求报错视为非法请求-2试探分配后系统进入不安全状态回滚三张表拒绝分配4. 交互层与实验报告让程序可演示让报告可复现算法写对只是及格线。课程设计真正拉开差距的是两件事程序能不能在别人手里跑出同样的结果报告能不能让评审在三分钟内看懂你做了什么。这一章解决这两个问题。4.1 菜单循环与输出格式交互层不需要做得多漂亮但必须做到“一个动作一个明确回显”。菜单给四个选项查看当前状态、发起资源请求、重新载入快照、退出。查看状态时把四张表按固定列宽对齐打印方便直接截图贴进报告。void menu_loop(void) { int choice; while (1) { printf(\n1.查看状态 2.发起请求 3.重载快照 0.退出\n请选择: ); if (scanf(%d, choice) ! 1) { /* 非数字输入清空缓冲区防死循环 */ while (getchar() ! \n); continue; } if (choice 0) break; if (choice 1) { print_state(); continue; } if (choice 2) { int pid, req[RES_NUM]; printf(进程号(0-%d) 与 %d 个请求量: , PROC_NUM - 1, RES_NUM); if (scanf(%d, pid) ! 1 || pid 0 || pid PROC_NUM) { printf(进程号非法\n); continue; } int bad 0; for (int j 0; j RES_NUM; j) if (scanf(%d, req[j]) ! 1 || req[j] 0) bad 1; if (bad) { printf(请求量非法\n); continue; } int r request(pid, req); print_result(pid, req, r); /* 按返回码打印不同结论 */ continue; } if (choice 3) { read_snapshot(snapshot.txt); printf(已重载\n); } } }scanf的返回值必须判断这是 C 语言交互程序的老坑用户手滑敲一个字母scanf读失败但不消费输入缓冲区里那个字符还在下一轮循环立刻又读失败屏幕上刷出一片菜单却不接受任何输入。加一句while (getchar() ! \n);清空到行尾问题就没了。这个细节写进报告的“问题与改进”一节比写十句“程序健壮性良好”有说服力。print_result按返回码分支输出重点是 -2 那一条要把“已回滚”三个字打出来并且紧跟着打印回滚后的状态让演示者一眼看出系统回到了分配前的样子。4.2 五组测试快照覆盖四个分支测试用例不是随便敲几个数字而要保证每个返回码至少被触发一次。下面这五组是我常用的组合全部基于经典的五进程三资源初始快照编号操作预期结论覆盖分支T1载入初始快照后查看状态安全序列为 P1→P3→P4→P0→P2安全性检查为真T2P1 请求 (1,0,2)准予返回 1正常分配T3P2 请求 (6,0,0)阻塞等待返回 0可用资源不足T4P4 请求 (3,3,0)拒绝并回滚返回 -2试探后不安全T5P0 请求 (8,0,0)报错返回 -1超过最大需求T1 的推演过程值得在报告里完整写一遍初始 Available 为 (3,3,2)先满足 P1 的 Need (1,2,2)回收后 Work 变成 (5,3,2)再满足 P3 的 (0,1,1)Work 变成 (7,4,3)接着 P4 的 (4,3,1) 通过Work 变成 (7,4,5)P0 的 (7,4,3) 通过Work 变成 (7,5,5)最后 P2 的 (6,0,0) 通过Work 变成 (10,5,7)五个进程全部完成。这五行推演就是报告“结果分析”一节的正文。T4 是最有价值的一组因为它能证明回滚是真的生效了。执行完 T4 之后立刻打印状态四张表必须和 T1 结束时逐字节一致如果 Allocation 或 Need 有任何一格对不上说明回滚写漏了。注意每组用例之间要重新载入快照否则 T3 留下的阻塞状态会污染 T4 的判定测试结果就没法复现了。4.3 实验报告的章节骨架程序跑通之后报告按这八节组织每一节对应代码里的一个模块写起来不费劲读起来也顺第一节实验目的两段话说明为什么做死锁避免而不是死锁检测第二节实验环境编译器版本和操作系统如实写第三节问题描述与算法原理把 2.1 的三条前提假设和四个矩阵的定义放这里第四节总体设计用文字描述四层结构——数据层负责快照文件与四个矩阵算法层是recompute_need、is_safe、request三个函数交互层是菜单循环与打印测试层是五组用例脚本第五节详细实现每个核心函数贴代码加注释说明重点解释 Work/Finish 的含义和回滚的对称性第六节测试与结果分析把 4.2 那张表连同每组的输入输出截图贴全第七节问题与改进写清银行家算法的局限——需要预声明最大需求、实际系统难以做到、安全序列不唯一、只适用于资源类数不多且相对固定的场景第八节参考文献。第四节到第六节是评分主体篇幅占比不要低于六成。第七节反而最容易被忽略但它是唯一能体现你“知道这个方法边界在哪”的地方务必写满。5. 避坑与排查银行家算法实验里最容易翻车的五个点这一节的每一条都是我在看别人代码时反复遇到的现象、原因、解决三件套写清楚对着排查就行。5.1 算法逻辑类的三处翻车现象一程序对任何快照都判定“安全”包括那些明显会卡死的。原因基本是Finish数组没清零。它如果被写成全局变量或者static第一次调用把所有位置置 1 之后第二次调用时所有进程在扫描一开始就是“已完成”状态while循环连一次都没进count直接从 0 开始累计——等等count是局部变量会从 0 重新数但因为所有进程都被continue跳过循环空转到count永远到不了PROC_NUM最后返回 0。所以更常见的表现是“永远判定不安全”。两种表现都对取决于count放在哪。解决很简单Finish必须定义在函数内部用 {0}初始化每次调用重新分配。现象二安全序列里出现重复进程号或者长度超过进程数。原因是seq[count] i的执行位置放在了Finish[i] 1之前或者外层while的条件写成了while (1)靠break退出但count没有边界保护。解决是把seq的写入紧跟在Finish置位之后并在循环条件里保留count PROC_NUM让它自己停下来。现象三请求被拒绝之后下一次同样的请求反而成功了。这是回滚只回了两张表的典型症状。减少一张表比如漏回滚 Need下一次进来时 Need 偏小req[j] Need[pid][j]这道关卡更容易通过于是就“通过”了。排查方法很原始但很有效在request函数的出口和入口各打印一次完整状态比对这两次打印是否完全一致对不上就说明回滚不完整。5.2 工程实现类的两处翻车现象四用scanf读进程号时只要输错一次程序就再也不接受输入了屏幕上疯狂刷菜单。原因在 4.1 已经解释过scanf读失败不消费缓冲区。解决办法是每次scanf返回非预期值时调用while (getchar() ! \n);把当前行剩余字符清掉然后再continue。这个坑不踩过一次很难自己想明白属于典型的黑匣子式 bug——程序没崩但行为完全不符合直觉。现象五换一份快照就段错误。最常见的原因是进程数或资源类数在文件里被改了但代码里还是按宏的旧值分配数组。比如文件写 6 个进程read_snapshot照单全收往Max[5][3]里塞越界写得悄无声息。解决就是 2.3 里那段规模校验文件声明的 n、m 跟PROC_NUM、RES_NUM不一致就直接返回错误码宁可启动失败也不要带病运行。提示这五个问题里前三个属于算法理解问题后两个属于工程习惯问题。报告里把它们写进“问题与改进”说明你是调试出来的而不是抄出来的。6. 验收与答辩三个动作证明你的程序真的不会死锁答辩现场时间有限评审不会看你从头读代码通常就三个动作。把这三个动作练熟比多写两百行注释管用。第一个动作让他指定一份快照你当场手推 T1 的安全序列然后在程序里跑一遍两边对上。这一步考的是算法理解不是代码。手推的时候不要慌按“Work 初值 Available找 Need ≤ Work 的进程回收它的 Allocation”三步走每一步把 Work 念出来评审就知道你确实会。第二个动作跑 T4让他看着你输入一个会导致不安全的请求然后你立刻打印状态证明系统原样退回去了。这是最能体现实现质量的一步因为太多人的回滚是残缺的。提前把回滚前后的状态截图准备好现场跑不出来的时候能顶上。第三个动作改文件里的一个数字重跑 T1让他看到结论跟着变。这一步证明程序不是把答案硬编码进去的——银行家算法实验里硬编码安全序列是常见操作评审心里都有数主动演示一次数据驱动比解释十句有效。验收标准可以按下面这张表自查五项全过基本就是满分往上的水平检查项通过标准安全性检查五组用例结论与手推一致安全序列无重复、长度正确请求四分支返回码 1、0、-1、-2 各被触发至少一次回滚完整性拒绝分配前后四张表逐格一致数据驱动修改快照文件后结论随之变化无需重新编译报告对应每一节都能在代码里找到对应函数反之亦然最后一项最容易被忽视报告里的每一段描述都应该能在代码里落到具体函数上代码里的每个函数也应该在报告里被提到。有次我把print_state写得很完整但报告里只字未提被问了一句“这个函数实现了什么设计意图”就哑了。从那以后我每次交实验报告前都强制走一遍“报告翻到哪一节、代码就翻到哪个函数”的对照对不上的当场补。希望帮到你。本文还有配套的精品资源点击获取

银行家算法实验报告与源码：死锁避免、安全序列及回滚实现

相关推荐

C++工业级switch实战：性能优化、枚举状态机与编译器跳转表

N9000A信号分析仪实操指南：频谱测量与ACPR相噪调试要点

Markdown 配套文件全指南：渲染、模板与 PDF 导出实践

更多资讯

Kornia 修复解析：warp_affine、warp_perspective 与 remap 空目标在 MPS 上的崩溃（4032、4354）

艾尔登法环存档怎么改SteamID？ER-Save-Editor实战避坑指南

Minke自定义快捷键教程：如何设置8个高频操作，快速驾驭AI桌面智能体

Hydra Launcher 快速上手：3 步配齐游戏库、下载与云存档

Hydra Launcher 游戏启动器：游戏库管理、下载调优与云存档完整上手指南

轻量级平台监控雷达系统搭建实战：指标采集到告警通知全链路

今日更新

PLFM_RADAR：从被动告警到主动感知的微服务健康监控系统

SPI隔离设计实战：MAX14431BAEE+与STM32F407工业级应用

数字隔离器如何根治SPI通信地环路干扰：MAX14431与TM4C129实战

本周精选

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

本月热门

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

读完文章，想聊聊您的网站？