死锁避免与银行家算法：操作系统课程设计实现指南

简介面向高校操作系统课程设计的死锁检测算法资源包适合正在学习并发控制、进程管理的学生或需要完成类似课题的开发者。压缩包共18个文件仅154KB采用典型Visual C工程结构包含C源码cpp、工程配置文件dsp/dsw/plg/opt/ncb、课程设计报告doc、数据库文件db及多张示意图片另有txt说明文档可查看题目要求与运行指引整体结构清晰便于直接编译运行、修改和复用。资源以死锁检测为课题围绕互斥、不可抢占、持有并等待、循环等待四个必要条件展开通过可执行的程序模拟资源分配与进程等待状态同时涉及银行家算法、资源分配图等经典内容帮助学习者从理论到代码层面理解系统如何提前避免或事后检测死锁。已有218人学习下载对正在完成操作系统课程设计或复习死锁知识的学生而言是一份兼具参考价值与操作性的实践资料。1. 操作系统课程设计里的死锁算法为什么银行家是首选学期末拿到操作系统课程设计清单死锁相关题目几乎每年都有。常见的有银行家算法模拟、死锁检测与恢复、资源分配图判定几类。如果只挑一个算法做演示系统我建议优先做银行家算法。它的输入输出非常直观给出当前资源分配状态再输入一个资源请求程序判断“分配后系统是否仍然安全”。这个判断过程正好覆盖死锁避免的核心思想也天然适合做成课程设计答辩时那种“运行一次、讲一分钟”的交互式演示。相比资源分配图化简银行家算法不需要画图不需要处理环的数学判定只要维护好三个矩阵和一个向量就能完整展示从安全性检测到回滚的整套逻辑。标题里“死锁_操作系统_算法_课程设计”四个词落到一个可运行的程序上最省力且最不容易被问到答不上来的就是银行家算法。接下来的写法按“建模 → 实现 → 扩展 → 验证”推进代码以 C 语言为主直接对应课程设计里常见的提交形式。2. 死锁的四个必要条件与资源分配模型的建模2.1 死锁的四个必要条件与预防策略的对应关系先明确死锁的四个必要条件互斥、持有并等待、不可剥夺、循环等待。这四个条件缺一个死锁就不会发生所以“死锁的四个必要条件 → 预防策略”的思路就是在资源分配算法中主动打破其中一个条件。必要条件含义常见预防策略代码层体现互斥资源同一时刻只能被一个进程占用一般无法避免资源本身特性决定用数组保存每个资源的归属者即可持有并等待进程持有部分资源又申请新资源一次性申请全部所需资源request请求数组必须一次性完整填写不可剥夺资源不能被强制拿走可剥夺式分配比如优先级抢占请求失败时回滚已分配的资源循环等待多个进程形成等待环资源编号按递增顺序申请对输入资源类型编号并规定申请顺序在写课程设计代码之前要把这四行对应关系放在报告引言里因为答辩老师基本都会从“你怎么避免死锁”问起。银行家算法实际走的是另一条路它不去强行打破条件而是通过安全性检测在分配前预测是否存在安全序列。它属于死锁避免而不是死锁预防这个区别要在代码注释里写明避免答辩时概念混淆。另外注意“饥饿”和死锁是两回事。死锁是进程互相等待永不释放饥饿是某个进程长期得不到资源但其他进程还能推进。在银行家算法里如果一个进程的 max 需求设置得特别大它可能一直通过不了安全性检测出现实际上的饥饿。这部分可以在扩展章节实现但基础版本不必写入代码。2.2 资源分配模型的数据结构设计银行家算法需要维护四种数据可用资源向量、进程最大需求矩阵、已分配矩阵、还需资源矩阵。常见做法是直接用全局二维数组课程设计规模下 N 个进程、M 类资源一般 N 不超过 10M 不超过 5数组大小完全够用。#define N 5 // 进程数 #define M 3 // 资源类型数 int available[M]; // 各类资源的可用数量 int max_need[N][M]; // 每个进程的最大需求 int allocation[N][M]; // 每个进程已分配的资源 int need[N][M]; // 每个进程还需要多少资源 void calc_need(void) { for (int i 0; i N; i) { for (int j 0; j M; j) { need[i][j] max_need[i][j] - allocation[i][j]; } } }need矩阵不需要从外部读入它由max_need减allocation得到这是为了保持输入数据的一致性和可验证性。如果允许直接输入need可能出现need allocation ! max_need的矛盾状态答辩时被问到就很被动了。available数组也可以在初始化时通过总资源减已分配资源计算出来但课程设计里通常直接给全方便用教材上的经典数据做演示。需要注意max_need的语义是进程在整个生命周期里对每类资源的最大需求量不是单次请求量。因此每次收到request程序都要先对比request和need请求量只能小于等于剩余需求这是银行家算法的第一个边界检查。2.3 用一张状态表描述进程资源占用课程设计报告里建议直接给出下面这样一张表作为测试数据它来自操作系统教材里最经典的 5 进程 3 资源示例。这张表的价值在于所有后续安全性检测步骤都可以对照它手工演算答辩时就算老师质疑代码逻辑也可以现场用笔验证结果。进程最大需求 max已分配 allocation还需 need可用 availableP07 5 30 1 07 4 33 3 2P13 2 22 0 01 2 2P29 0 23 0 26 0 0P32 2 22 1 10 1 1P44 3 30 0 24 3 1这张表对应的状态经过安全性检测可以得到安全序列 P1 → P3 → P4 → P0 → P2。建议把这一组数据硬编码到程序里作为默认启动状态同时提供文件读取或手动输入接口。这样做的好处是演示时先跑默认数据老师觉得太顺利再现场输入一组你自己构造的数据展示结果变化比单纯跑一遍要有说服力。3. 银行家算法的死锁避免实现数据结构、检测函数与参数3.1 安全性检测的逐步推导逻辑安全性检测做的事情很简单假设分配已经完成判断系统是否存在一个进程执行顺序使得每个进程都能在有限时间内获得全部所需资源并运行结束。实现上维护两个数组work表示当前可用的资源副本finish标记进程是否已执行完毕。每一轮扫描所有未完成的进程找第一个满足need[i][j] work[j]对所有资源类型 j 成立的进程。找到后模拟该进程执行完毕释放它占用的资源即work[j] allocation[i][j]然后标记完成。如果一整轮扫描找不到任何可执行的进程说明不存在安全序列返回失败。这个循环对新手来说有个容易写错的地方work数组是随着扫描不断增长的每一轮都要从头开始重新扫描所有未完成进程而不是只扫描一次。如果写成单遍扫描遇到初始不满足、但被前面进程释放资源后可以满足的情况就会漏判得出错误的安全序列。int safety_check(int work[M], int safe_seq[N]) { bool finish[N]; memset(finish, 0, sizeof(finish)); int done 0; while (done N) { bool found false; for (int i 0; i N; i) { if (finish[i]) continue; int j 0; for (; j M; j) { if (need[i][j] work[j]) break; } if (j M) { for (j 0; j M; j) { work[j] allocation[i][j]; } safe_seq[done] i; finish[i] true; found true; } } if (!found) { return -1; // 这一轮没有任何进程能被满足 } } return 0; }这里work是调用方传入的副本函数内不会修改全局的available。safe_seq参数用于记录产生的安全序列方便外层调用直接打印“P1 → P3 → P4 → P0 → P2”这样的结果。返回 0 表示存在安全序列返回 -1 表示不存在错误码的语义要保持在整份代码里一致。3.2 可运行的最小银行家算法代码C 语言把初始化、安全性检测和请求处理合并在一起就可以得到一个能直接编译运行的完整版本。下面的实现去掉了界面交互只保留核心逻辑方便移植到自己的课程设计框架里。#include stdio.h #include stdbool.h #include string.h #define N 5 #define M 3 int available[M] {3, 3, 2}; int max_need[N][M] {{7,5,3},{3,2,2},{9,0,2},{2,2,2},{4,3,3}}; int allocation[N][M] {{0,1,0},{2,0,0},{3,0,2},{2,1,1},{0,0,2}}; int need[N][M]; int request_res(int pid, int req[M]) { for (int j 0; j M; j) { if (req[j] need[pid][j]) return -1; // 请求量超过声明需求 if (req[j] available[j]) return -2; // 当前可用资源不足 } // 试探性分配修改三个矩阵 for (int j 0; j M; j) { available[j] - req[j]; allocation[pid][j] req[j]; need[pid][j] - req[j]; } int work[M], safe_seq[N]; memcpy(work, available, sizeof(work)); if (safety_check(work, safe_seq) 0) { printf(分配后仍安全安全序列: ); for (int i 0; i N; i) printf(P%d , safe_seq[i]); printf(\n); return 1; } else { // 分配后进入不安全状态回滚 for (int j 0; j M; j) { available[j] req[j]; allocation[pid][j] - req[j]; need[pid][j] req[j]; } return 0; // 拒绝分配 } }request_res的返回值含义要在界面代码里区分清楚-1是请求不合理-2是资源暂时不足但请求合理0是分配会导致不安全状态所以被拒绝1是分配成功且系统保持安全。前两种属于输入层面的拒绝第三种属于算法层面的拒绝报告里要把这三类输出分别截图作为测试用例的证据。safety_check函数在这个版本里是前置声明或定义在本文件上方实际提交时建议把所有函数放在一个.c文件里不用拆头文件课程设计规模下这样做最简单。打印安全序列时注意每个进程输出一个空格不要在序列最后一个进程后面多打“→”否则窗口输出不太整齐。3.3 请求处理时 3 个边界参数的判断顺序请求处理是银行家算法里最容易出细节问题的地方三个检查必须按固定顺序执行。第一先判断req[j] need[pid][j]。这属于非法请求说明进程申请量超过了自己声明过的最大需求直接返回错误。某些实现会把这步忽略结果进程可以不断申请超过 max 的资源系统状态变得不可信安全性检测也就失去了意义。第二判断req[j] available[j]。如果请求量本身在声明范围内但当前资源不足进程应该阻塞等待。课程设计里一般不会实现真正的阻塞队列所以只需要返回一个“资源不足”的错误码即可。第三前两项通过后执行试探分配调用安全性检测。检测失败就必须回滚要注意回滚必须同时恢复available、allocation、need三个矩阵。许多错误实现只恢复available导致allocation和need已经被修改但系统状态不一致后续所有判断全部出错。// 回滚时三个矩阵必须全部恢复顺序不能乱 for (int j 0; j M; j) { available[j] req[j]; allocation[pid][j] - req[j]; need[pid][j] req[j]; }另外需要注意work数组必须在试探分配完成后用新的available初始化不能沿用分配前的值。因为安全性检测模拟的是“当前状态下能否完成所有进程”available已经变了work也要跟着变。3.4 测试用例设计从死锁课程设计演示脚本角度基础功能写完后准备一组交互式测试数据。建议让程序支持从命令行读取请求格式为“进程编号 资源1数量 资源2数量 资源3数量”。以默认的 5 进程 3 资源状态为例设计下面两组请求请求序号请求内容预期输出对应场景1P1 请求 1 0 2分配成功输出安全序列正常分配2P4 请求 3 3 0拒绝资源不足触发 available 检查3P0 请求 0 2 0拒绝分配后不安全触发安全性检测展示回滚请求 1 执行后available变为 2 3 0。此时再请求 3P0 需要 7 4 3如果先分配给 P0 0 2 0available变为 2 1 0这个状态下所有进程的 need 都无法被满足安全性检测返回 -1程序回滚。这组用例能把算法三种典型行为全部覆盖答辩演示时按顺序执行一次即可。4. 从银行家到死锁检测课程设计的“饥饿和死锁”扩展方向4.1 死锁避免与死锁检测的分工差异银行家算法属于死锁避免它在每次分配前判断“之后是否存在安全执行序列”。而死锁检测算法恰恰相反它不阻止死锁发生而是允许系统自由分配然后周期性运行检测模块判断当前是否已经出现死锁。这个区别在课程设计扩展题里经常出现一个题目要求实现银行家另一个题目要求实现检测与恢复。从工程角度想银行家算法很难在真实操作系统中用因为进程的最大需求通常无法预先知道资源类型也在动态变化。死锁检测则更接近真实系统状态检测出死锁后用撤消进程或回滚的方式恢复。在课程设计报告里可以把这两种算法做成对照实验同一组初始状态分别跑避免和检测输出各自的判定结果。矩阵化简是死锁检测的常用实现它和银行家的安全性检测很像但有本质差异。检测算法不需要max_need矩阵只需要allocation和request其中request是进程当前真实发出的资源请求而不是进程生命周期内的最大需求。检测目标也不是“未来是否安全”而是“当前是否存在无法推进的进程”。4.2 用矩阵化简实现死锁检测算法检测算法的核心是一个化简过程先把已分配资源为 0 的进程标记为完成因为这类进程没有持有任何资源必然可以终止然后将可用资源复制到work循环查找“剩余请求能被当前 work 满足”的进程找到就假设它运行结束并释放资源反复化简直到没有进程可以被满足。int deadlock_detect(int avail[M], int alloc[N][M], int req[N][M]) { bool finish[N]; for (int i 0; i N; i) { finish[i] true; for (int j 0; j M; j) { if (alloc[i][j] ! 0) { finish[i] false; break; } } } int work[M]; memcpy(work, avail, sizeof(int) * M); int progress; do { progress 0; for (int i 0; i N; i) { if (finish[i]) continue; int j 0; for (; j M; j) { if (req[i][j] work[j]) break; } if (j M) { for (j 0; j M; j) { work[j] alloc[i][j]; } finish[i] true; progress; } } } while (progress 0); int deadlocked 0; for (int i 0; i N; i) { if (!finish[i]) { printf(进程 P%d 处于死锁状态\n, i); deadlocked; } } return deadlocked 0 ? 1 : 0; }这段代码与银行家安全性检测的相似之处在于都反复扫描未完成进程区别在于初始条件检测算法把未持有任何资源的进程视为已完成且请求矩阵是当前即时请求安全性检测则先假定所有进程都可以推进唯一阻塞原因就是资源不满足。课程设计报告里如果能画一张“银行家安全性检测与死锁检测矩阵化简对比表”这个扩展题就写得很扎实了。4.3 线程死锁场景与 JVM、数据库的排查对照真实工程里没有银行家算法但排查线程死锁的思路与矩阵化简完全一致找出每个线程持有哪些锁、等待哪些锁然后判断锁的持有与等待关系是否成环。JDK 的jstack命令就能直接打印线程死锁检测结果它识别的是典型的两线程互相持锁等待场景。Found one Java-level deadlock: Thread-0: waiting to lock monitor 0x000000001c0e9c78 (object 0x00000000d44ddbf0, a java.lang.Object) Thread-1: waiting to lock monitor 0x000000001c0e9cb8 (object 0x00000000d44ddbd8, a java.lang.Object)jstack输出里的waiting to lock就是进程在等待一个尚未获得的资源blocked on lock表示当前被阻塞打印出的两行互相等待的锁就是等待环的物化表现。数据库死锁日志也是同理MySQL 在死锁发生后会输出LATEST DETECTED DEADLOCK信息显示事务 A 持有索引记录锁等待事务 B 持有的锁事务 B 反过来等事务 A这就是典型的循环等待。这里值得多说一句给有经验的人Java 层面检测到死锁不代表操作系统层面发生了死锁很可能只是应用自研锁的等待关系成环操作系统里的线程依然在正常调度。所以课程设计里讲死锁检测时要区分“资源级死锁”和“应用级死锁”前者用矩阵化简判断后者用等待图判断两者模型相通但对象不同。5. 答辩前必做的 3 个验证技巧5.1 用固定脚本跑对照实验手动敲命令演示容易在关键时刻敲错数据可以用脚本方式把测试请求序列固化下来。程序支持从文件读取状态与请求时准备一个input.txt内容格式为初始状态后跟着若干行请求程序启动后顺次执行并打印结果。./banker input.txt # 输入文件内容示例 # 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 # REQUEST 1 1 0 2 # REQUEST 4 3 3 0把程序的标准输出重定向到文本文件连同input.txt一起放进实验资料目录。答辩现场如果时间紧张直接运行脚本并把输出文件展示出来即可不需要现场一步步输入。5.2 构造一个“不安全但不死锁”的输入银行家算法最容易讲不清的边界是“不安全状态不一定死锁”。构造一个具体反例让 P0 请求 0 2 0 后安全性检测返回非安全但系统里实际没有任何进程被永久阻塞只是存在一个资源分配序列会让未来无法完成全部进程。这个反例可以作为答辩加分项在演示完正常流程后主动提出“下面展示一个系统未死锁但被判定为不安全的输入说明银行家算法的安全性检测是保守策略”。这个验证不需要额外代码只是预先准备一组请求序列让算法拒绝即可。同时把它和死锁检测算法对比检测算法面对同一状态可能返回未死锁两个算法的差异就在这一步体现出来。5.3 把终态快照写进报告课程设计报告里建议加入一个“运行状态转移表”每一列是完成一轮请求后的资源状态精确展示 available 从初始值到最终值的变化。下面是一个简化的三行示例实际报告中可以根据测试请求数扩展行数。步骤请求availableallocation P0..P4是否安全初始-3 3 20 1 0 2 0 0 3 0 2 2 1 1 0 0 2安全1P1 → 1 0 22 3 00 1 0 3 0 0 3 0 2 2 1 1 0 0 2安全2P4 → 3 3 0拒绝同左-表格放在程序测试结果之后不要放在开头。老师在翻报告时看到代码、输出截图、状态表三者顺序一致基本不会再追问细节问题。答辩演示时照着状态表一行一行点讲完表中最后一行时直接收束这个验证工作就算做完整了。本文还有配套的精品资源点击获取