银行家算法C语言实现：死锁避免、安全序列与实验报告

简介这是一份围绕操作系统银行家算法实验整理的资料包包含实验报告与可编译源代码面向计算机专业学习操作系统课程、需要完成死锁避免实验或课程设计的学生。压缩包共5个文件以2个cpp源文件、1个h头文件和1个docx实验报告为主另附1个txt初始化数据整体约452KB头文件与实现分离便于对照理解数据结构与算法流程。目前已有5251人学习下载。代码围绕最大需求、可用资源、已分配与需求矩阵展开覆盖进程管理、资源请求、安全性检查、资源分配与释放及模拟循环配合报告可梳理安全序列构造和死锁避免的判断依据。对调试中可能出现的资源分配不当、资源泄露或安全性检查错误也提供了可对照分析的实验场景适合用作课程实验参考、代码复盘与答辩准备。1. 从一次「明明有资源却不敢分」说起操作系统课设周银行家算法这道题最容易让人卡住Available 里明明还躺着空闲资源程序却判定这次请求不能批。很多同学交上去的实验报告加源代码基本是把课本伪代码抄了一遍安全序列跟标准答案对不上答辩时被问一句「为什么拒绝这个请求」就答不上来。这份资源把两件事放在一起交付一份结构完整、能直接交的实验报告和一份能编译、能换数据、能批量跑用例的源码。它适合两类人——赶 OS 课设、需要一份能讲清楚原理的报告的同学以及想把「死锁避免」从公式落到二维数组上的开发者。银行家算法本身不复杂真正的门道在状态怎么存、试分配怎么回滚、安全序列怎么证明这些才是后面几章要拆的东西。2. 项目组成与技术选型一份报告加一份能跑的实现这个项目的交付物是「文档 代码」的双份结构代码用标准 CC11写成不依赖任何第三方库gcc或clang直接编Windows 上 Dev-C、VS Code MinGW 也能跑。选 C 不是情怀是因为这门课的实验环境普遍是这种配置老师看代码时不会因为环境问题打回同时 C 的数组和指针正好能把四张资源矩阵的「原地试分配 回滚」表现得最直白换成带垃圾回收的语言反而看不出回滚这一步的价值。2.1 目录结构与两份交付物的分工源码和报告分开放是为了让「改代码」和「改文档」互不干扰。报告里贴的代码片段来自src/测试数据放在data/批量验证脚本放在tests/。这样老师在验收时改一个用例只需要动data/下的文本文件不用重新读代码。banker/ ├── README.md # 编译方式、用例说明、输出约定 ├── Makefile # make / make run / make clean ├── src/ │ ├── banker.h # 结构体定义、函数声明、返回码枚举 │ ├── banker.c # 主流程、文件读取、矩阵打印、交互循环 │ └── safe.c # 安全性检查 资源请求处理 ├── data/ │ ├── case1.txt # 经典 5 进程 3 资源用例安全 │ ├── case2.txt # 初始状态就不安全的用例 │ └── case3.txt # 单资源退化用例方便手算核对 ├── tests/ │ └── run_cases.sh # 逐个跑用例并对比期望输出 └── report/ ├── report.md # 实验报告正文 └── figs/ # 流程图、运行截图提示report/figs/里的截图建议用同一台机器、同一个终端字号截报告里图与图之间风格统一观感差别很大。把safe.c单独拆出来是有意为之。安全性检查和资源请求是两个可以独立测试的单元主流程只负责读数据和打印结果。二次开发时想加「撤销上一次分配」「记录每一步 Work 变化」这类功能改动点全在safe.c里不会牵连输入输出。2.2 四张表定天下Available / Max / Allocation / Need银行家算法的全部状态就是四个矩阵加两个向量写成结构体最省事。下面这份定义把「上限」和「实际规模」分开是为了后面加越界检查。/* src/banker.h */ #ifndef BANKER_H #define BANKER_H #include stdbool.h #define MAX_PROC 16 /* 进程数上限够课设用了 */ #define MAX_RES 8 /* 资源类型数上限 */ typedef struct { int n; /* 实际进程数 */ int m; /* 实际资源类型数 */ int available[MAX_RES]; /* 各类资源剩余量 */ int max[MAX_PROC][MAX_RES]; /* 每个进程声明的最大需求 */ int allocation[MAX_PROC][MAX_RES]; /* 当前已分配 */ int need[MAX_PROC][MAX_RES]; /* 还差多少 max - allocation */ } Banker; typedef enum { REQ_GRANTED 0, /* 分配成功状态已更新 */ REQ_WAIT 1, /* 当前资源不够进程应等待 */ REQ_INVALID -1, /* 请求超过自己声明的最大需求 */ REQ_UNSAFE -2 /* 试分配后不安全已回滚 */ } ReqResult; bool load_from_file(Banker *b, const char *path); void print_state(const Banker *b); bool is_safe(const Banker *b, int safe_seq[]); ReqResult request_resources(Banker *b, int pid, const int req[]); #endifneed不在每次计算时用max - allocation现减而是在读文件那一刻就算好存下来后面所有判断直接取。这个选择看着是小优化实际是防错如果某个分支里改了allocation却忘了同步need实时相减的写法会把错误藏起来而预存need会在下一轮安全检查里立刻暴露成「负数需求」或者「永远不安全」。四个矩阵的语义再捋一遍报告里也必须写清楚名称维度含义谁写入Available1 × m系统当前还能借出去的资源初始化 每次分配/回收后更新Maxn × m进程自己声明的最大需求量输入运行期不变Allocationn × m已经拿到手的资源分配时加回滚时减Needn × m还需要多少才能跑完Max − Allocation随分配变化Max在运行期是只读的这一点很关键。资源请求算法判断「这个请求合不合法」比的就是Request[i] Need[i]如果Max被改过这条判断就失去意义了。2.3 编译运行三条命令跑通第一个用例Makefile保持最朴素的写法不引入 cmake是因为课设环境上用 cmake 反而增加解释成本。CC ? gcc CFLAGS ? -stdc11 -Wall -Wextra -O2 -g SRC : $(wildcard src/*.c) BIN : banker $(BIN): $(SRC) $(CC) $(CFLAGS) -o $ $^ run: $(BIN) ./$(BIN) data/case1.txt clean: rm -f $(BIN)跑起来就三步make # 编译正常应该零警告 ./banker data/case1.txt # 用经典用例跑一次 # 交互输入形如1 1 0 2 进程 1 请求 R11 R20 R32 # 输入 -1 退出case1.txt的格式是「先规模再 Available 一行然后 Max 矩阵 n 行最后 Allocation 矩阵 n 行」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这是课本上那个 5 进程 3 资源的经典例子手算的安全序列是 P1 → P3 → P4 → P0 → P2也可能先 P4 再 P2不唯一。第一次跑出来能打印出这个结果说明读文件、算Need、安全性检查整条链路是通的。-Wall -Wextra一定要留着。这类代码最常见的错误是int i, j里把j b-m写成j b-n不加警告编译能过运行时只在进程数和资源数不同的时候才崩排查起来特别费劲。3. 核心模块拆解安全性算法与资源请求的完整链路整个项目真正需要动脑的只有两个函数is_safe和request_resources。前者回答「当前这个状态还能不能走通」后者回答「这次请求该不该批」。其余代码都是给这两个函数喂数据和打印结果。3.1 安全性检查Work 和 Finish 两个向量怎么滚动安全性检查的本质是一次「模拟执行」假设所有进程现在开始申请它剩余需要的资源看看能不能找到一个顺序让每个进程都跑完。Work是模拟过程中的可用资源Finish标记哪些进程已经模拟跑完。/* src/safe.c */ #include string.h #include banker.h bool is_safe(const Banker *b, int safe_seq[]) { int work[MAX_RES]; bool finish[MAX_PROC]; int count 0; /* 1. 初始化Work 拷贝 AvailableFinish 全部置 false */ for (int j 0; j b-m; j) work[j] b-available[j]; memset(finish, 0, sizeof(bool) * b-n); /* 2. 反复扫描直到所有进程都跑完或一轮下来毫无进展 */ while (count b-n) { bool progressed false; for (int i 0; i b-n; i) { if (finish[i]) continue; /* 判断 Need[i] 是否全部 Work */ bool ok true; for (int j 0; j b-m; j) { if (b-need[i][j] work[j]) { ok false; break; } } if (!ok) continue; /* 模拟 Pi 跑完把它手里的资源全部归还 */ for (int j 0; j b-m; j) work[j] b-allocation[i][j]; finish[i] true; safe_seq[count] i; progressed true; } /* 3. 一整轮没有任何进程能推进说明剩下的是死锁集合 */ if (!progressed) return false; } return true; }逐段看。第一步的两个初始化Work Available是必须的Finish全 false 也是必须的。曾见过有人复用上一轮调用的finish数组结果第二次安全检查直接返回「安全」因为所有进程都被标记成已完成——这种 bug 只在连续请求时出现单次测试完全测不出来。第二步的循环结构是这段代码的核心。外层while保证只要有进展就继续下一轮内层for每轮从头扫一遍所有未完成进程。progressed是防止死循环的保险丝如果一整轮扫下来没有任何进程能满足Need Work说明剩下的进程互相卡着直接返回不安全不用再转。第三步的work[j] b-allocation[i][j]容易被写成 b-need[i][j]。两者结果不同进程跑完归还的是它「已经拿到的」资源Allocation不是它「曾经想要」的资源Need。写错的话安全序列可能还是能算出来但每一步的 Work 值是错的报告里的过程表一对就露馅。safe_seq用count递增写入而不是用i或者work的下标保证每个进程在序列里只出现一次。这是第二个高频错误点下面避坑章会专门讲。复杂度上最坏情况每轮只推进一个进程共 n 轮每轮扫 n 个进程、每个比 m 个资源是 O(n²m)。课设规模下完全够用不用考虑优化。3.2 资源请求的四道闸门与回滚request_resources是真正会修改全局状态的地方也是最容易写错的地方。它要依次过四道闸门任何一道没过都必须保证状态没被污染。/* src/safe.c 续 */ ReqResult request_resources(Banker *b, int pid, const int req[]) { if (pid 0 || pid b-n) return REQ_INVALID; /* 闸门一请求量必须非负 */ for (int j 0; j b-m; j) if (req[j] 0) return REQ_INVALID; /* 闸门二不能超过自己声明的最大需求 */ for (int j 0; j b-m; j) if (req[j] b-need[pid][j]) return REQ_INVALID; /* 闸门三当前可用资源是否够不够就让进程等 */ for (int j 0; j b-m; j) if (req[j] b-available[j]) return REQ_WAIT; /* 闸门四试探性分配然后跑一遍安全性检查 */ for (int j 0; j b-m; j) { b-available[j] - req[j]; b-allocation[pid][j] req[j]; b-need[pid][j] - req[j]; } int seq[MAX_PROC]; if (is_safe(b, seq)) return REQ_GRANTED; /* 安全分配生效 */ /* 不安全必须原路回滚否则后面的判断全乱 */ for (int j 0; j b-m; j) { b-available[j] req[j]; b-allocation[pid][j] - req[j]; b-need[pid][j] req[j]; } return REQ_UNSAFE; }四道闸门的顺序不能调。闸门二超Need必须在闸门三资源不够之前因为「请求超过自己声明的最大需求」是逻辑错误属于进程违规应该直接报错而「资源暂时不够」只是时机不对进程应该等。这两种情况在输出里必须区分开报告的结果分析部分也要分开讨论。试分配那一段是三个操作同时做Available减、Allocation加、Need减。三者必须严格配对回滚时严格逆序还原。这里用「原地改 手工回滚」而不是「拷贝一份副本试算」是课设里更常见的写法——副本写法内存开销小但代码看着绕而且Banker结构体里有两个二维数组拷贝一份要写循环反而容易漏字段。原地改的风险是回滚必须一处不漏所以回滚代码最好紧跟在判断后面中间不要插别的逻辑。ReqResult用四个返回值而不是简单的true/false就是为了让主流程能打印不同的提示。如果只返回布尔值用户看到「分配失败」根本不知道是资源不够还是会被判不安全调试时只能靠猜。3.3 主流程先验证初始状态再进交互循环主函数只做三件事读文件、验证初始状态、循环处理请求。/* src/banker.c */ #include stdio.h #include banker.h int main(int argc, char *argv[]) { Banker b; const char *path (argc 1) ? argv[1] : data/case1.txt; if (!load_from_file(b, path)) { fprintf(stderr, 读取 %s 失败检查文件格式\n, path); return 1; } print_state(b); int seq[MAX_PROC]; if (!is_safe(b, seq)) { printf(初始状态不安全请检查 Max / Allocation 矩阵\n); return 1; } printf(初始状态安全一个可行安全序列); for (int i 0; i b.n; i) printf(P%d%s, seq[i], i 1 b.n ? - : \n); /* 交互每行输入 进程号 m 个资源请求量输入 -1 退出 */ int pid, req[MAX_RES]; while (1) { printf(请求 ); if (scanf(%d, pid) ! 1 || pid 0) break; for (int j 0; j b.m; j) if (scanf(%d, req[j]) ! 1) return 0; ReqResult r request_resources(b, pid, req); switch (r) { case REQ_GRANTED: printf(P%d 请求已批准\n, pid); break; case REQ_WAIT: printf(P%d 资源不足请等待\n, pid); break; case REQ_INVALID: printf(P%d 请求非法超过声明的最大需求\n, pid); break; case REQ_UNSAFE: printf(P%d 请求被拒试分配后系统将进入不安全状态\n, pid); break; } print_state(b); } return 0; }启动时先跑一次is_safe是有必要的。如果输入的矩阵本身就是死锁状态后面任何请求都必然返回不安全用户会以为是请求逻辑写错了实际上是初始数据有问题。先验一次能把这层歧义掐掉。每次请求处理完都print_state是为了让报告里的过程截图有内容可贴。截图里能看到Available在拒绝请求前后一模一样正好证明回滚生效了——这比在报告里写十句「本程序实现了回滚」有说服力。scanf的返回值都做了判断因为交互输入时用户很容易输个字母不检查的话pid会保持上一次的值程序进入诡异状态。4. 实验报告怎么写从原理图到结果分析代码跑通只是及格线报告才是拿分的地方。很多报告失分不是因为算法写错而是「原理部分抄书、测试部分只有一张截图、分析部分一句话带过」。这一章按报告的实际章节顺序讲怎么填。4.1 原理与数据结构把四张表画成一张状态图原理章节不要直接抄课本的定义。课本讲的是通用模型你的报告要讲的是「我这份代码里的数组分别对应什么」。最有效的写法是先摆一张表说明Available、Max、Allocation、Need各自的维度和更新时机就是 2.2 节那张再配一个具体的数值例子走一步。比如拿case1的初始状态写清楚Available [3, 3, 2]表示系统还剩 3 个 R1、3 个 R2、2 个 R3Need[0] Max[0] - Allocation[0] [7,5,3] - [0,1,0] [7,4,3]判断 P0 能不能跑就是看[7,4,3]是否逐分量不大于[3,3,2]答案是不能。再往下画安全性检查的流程初始化 → 找满足Need Work的未完成进程 → 假设它跑完并归还资源 → 重复 → 全部完成则安全。流程图用 Visio 或者 draw.io 画都行关键是每个判断框的分支条件要写具体比如判断框里写Need[i] Work ?而不是含糊的「是否满足条件」。数据结构章节要说明为什么用二维数组而不是链表。理由很实在进程数和资源类型数在运行期不变数组的随机访问和Max - Allocation这种逐元素运算写起来最直接链表反而要为每个进程维护 m 个节点。这条理由写进去比空谈「数组效率高」强。4.2 测试用例设计四类输入覆盖所有分支request_resources有四条返回路径报告里的测试用例就应该正好覆盖这四条一条不多一条不少。用例输入期望返回覆盖分支正常批准P1 请求 [1,0,2]REQ_GRANTED试分配后仍安全资源不足P0 请求 [3,3,3]超过 AvailableREQ_WAIT闸门三超过最大需求P1 请求 [3,0,0]Need[1][1,2,2]REQ_INVALID闸门二导致不安全P0 请求 [2,0,0] 后再构造冲突请求REQ_UNSAFE试分配后回滚第四类用例最容易被漏掉也最能体现工作量。构造方法先让系统进入一个「只剩少量资源」的状态然后让某个进程申请刚好够用但会导致其他进程永远等不到资源的数量。跑出来如果打印的是「试分配后系统将进入不安全状态」并且紧跟着的状态表里Available和请求前完全一致就证明回滚是对的。每个用例除了贴运行截图还要在旁边写出手算过程。比如 P1 请求 [1,0,2]Need[1][1,2,2]请求没超Available[3,3,2]够试分配后Available[2,3,0]、Allocation[1][3,0,2]、Need[1][0,2,0]此时 P1、P3 都能跑完……手算三五行比截图更有说服力因为这证明你理解了算法而不是只会按回车。case2.txt那个「初始就不安全」的用例也要留着它验证的是启动时那次预检查输出应该是「初始状态不安全」程序直接退出。4.3 结果分析安全序列不唯一这件事必须说清分析部分至少写三件事。第一安全序列不唯一。case1手算能得到 P1→P3→P4→P0→P2也能得到 P1→P3→P4→P2→P0。程序输出哪一个取决于内层for扫描的顺序。这句话必须写进报告否则老师看到你的结果和答案不一样第一反应是判错。顺便可以写一句算法的目标是找到任意一个安全序列而不是唯一解所以不同实现给出不同序列是正常的。第二为什么某个请求被拒。不要只写「不安全」要写清楚是哪一步卡住了。比如「试分配后Available[0,1,0]剩余进程的Need分别是 [7,4,3]、[6,0,0]、[0,1,1]没有任何一个能全部满足因此不存在安全序列」。把 Work 和剩余 Need 摆出来逻辑就闭环了。第三复杂度与局限。安全性检查是 O(n²m)每次请求都要跑一遍进程多了会慢。真正的通用系统不会用银行家算法做在线判断因为进程的最大需求很难事先声明。这句话写在「问题与改进」里既显示你想过算法的适用边界也给二次开发留了口子。5. 避坑与排查跑出来但答案是错的五种情况下面五条是这类实现里出现频率最高的故障。它们的共同特点是程序不崩、能输出所以特别难发现。5.1 安全性检查把同一个进程算了两遍现象安全序列里出现P1 - P1 - ...或者序列长度对但进程号重复总有一个进程没被列入。原因safe_seq的下标用错写成了safe_seq[i] i或者safe_seq[work[0]] i而不是用独立的计数器count。另一种情况是finish[i]更新了但i在外层也自增导致跳过。解决序列写入只认countcount和finish严格同步递增循环结束条件用while (count n)不要用for (i 0; i n; i)包住整个算法。写完打印一次count和n对比。5.2 拒绝请求之后状态被污染现象第一次请求被拒绝后后续所有请求都返回「不安全」Available越跑越小重启程序才恢复正常。原因试分配时直接改了b-available但走REQ_UNSAFE分支时忘了回滚或者只回滚了Available忘了Allocation和Need。三个数组只还原一部分下次判断当然全错。解决回滚代码紧跟在安全性检查之后三个数组available、allocation、need一次性全部逆操作还原中间不插入任何return或其他逻辑。还有一种更保险的做法先在栈上复制一份Banker试算安全了再把副本整体拷回去。课设规模下这点内存完全无所谓我现在更倾向副本写法因为它天然不会有「漏还原一个字段」的问题。5.3 Need 出现负数现象打印状态表时Need里有-1、-3这种值后续判断全部异常。原因读文件时矩阵顺序搞反了把Allocation当Max读或者行主序和列主序弄混。也可能是请求处理里Need减了两次。解决文件头写死顺序注释读的时候严格按「Available 一行 → Max n 行 → Allocation n 行」读完后立刻算Need并检查是否有负值有就报错退出。加一道if (b-need[i][j] 0) return false;的校验能把数据问题挡在算法之前。5.4 数组越界但程序不崩现象换成 12 个进程的用例后结果错乱或者在自己机器上正常、换台机器就段错误。原因MAX_PROC定成 10用例却给了 12 个进程或者嵌套循环里j b-m写成了j b-n当 n m 时就越界读。解决读文件后立刻校验n MAX_PROC m MAX_RES不满足直接退出开发阶段加上-fsanitizeaddress,undefined编译一次越界会立刻报出具体行号。这个开关我在交作业前一定会打开跑一遍比事后猜快得多。5.5 交互输入把进程号和资源量吞掉现象输入1 1 0 2后程序跳过了一次请求或者把上一轮的资源量当成了新的进程号。原因scanf(%d, pid)失败后没有清空输入缓冲区残留字符被下一次读取吃掉或者退出条件pid 0写在读完资源量之后导致-1后面还要求输入 m 个数字。解决先读pid并判断退出再读 m 个资源量scanf的返回值全部检查失败的字符用getchar()循环清掉。规范的交互程序应该在任何非法输入后给出提示并继续而不是静默错位。6. 二次开发给它加一个能自证的测试回路手写用例的覆盖度终究有限尤其当你把MAX_PROC调到 16 之后人脑已经算不出正确答案了。这时候我会加一个对拍脚本随机生成小规模矩阵用暴力穷举算出「是否存在安全序列」再跟 C 程序的输出比对。暴力法的思路很直接——既然是安全性那就枚举所有可能的推进顺序只要存在一条能全部跑完的路径就是安全的。规模压到 n ≤ 6、m ≤ 3穷举量完全可以接受。import itertools, random, subprocess def brute_safe(avail, alloc, need): 穷举所有排列判断是否存在安全序列仅供小规模对拍 n, m len(need), len(avail) for order in itertools.permutations(range(n)): work list(avail) ok True for i in order: if any(need[i][j] work[j] for j in range(m)): ok False break for j in range(m): work[j] alloc[i][j] # 进程跑完归还已分配资源 if ok: return True return False # 生成用例 - 写临时文件 - 调 ./banker - 解析第一行输出 - 与 brute_safe 比对把这段和./banker的输出接起来跑上几百组随机用例凡是「暴力说安全、程序说不安全」或者反过来的都是真 bug。我用这套办法抓到过一个藏得很深的问题某个分支里Need减了但Available没减单看输出完全正常只有在对拍时才会出现两个实现的结论不一致。除了对拍还有两个投入产出比很高的改造方向。一是把is_safe改造成「带回溯信息」的版本记录每一步的Work快照输出成一张过程表报告里的分析章节可以直接引用二是把交互层换成读脚本文件一次跑十几个请求并打印每个请求的判定结果这样报告里的测试部分就是一份完整的执行日志而不是零散截图。至于性能is_safe每次请求都从头跑一遍进程数上百时确实会慢但这个算法本来就不是给大规模系统用的优化它的意义不大。真想练手不如把「进程可以动态加入、Max可以事后上调」这套约束加进去那时候你才会真正体会到为什么真实系统不敢用银行家算法——Max一旦可以随便改所有的安全性证明都成了空话。我现在每次交这类课设前都会强制走一遍「随机对拍 sanitizer 编译 换个规模的用例」这三步不管代码看起来多简单。银行家算法的坑不在算法本身全在数组下标和回滚那句for循环里肉眼是看不出来的。希望帮到你。本文还有配套的精品资源点击获取