银行家算法设计实验报告

1 银行家算法设计实验报告银行家算法设计实验报告 一 题目分析一 题目分析 1 1 银行家算法银行家算法 我们可以把操作系统看做是银行家 操作系统管理的资源相当于银行家管理的资金 进程向操作系统请求资源相当于客户向银行家贷款 操作系统按银行家制定的规则为进程分配资源 当进程首次申请资源时 要测试该进 程尚需求的资源量 若是系统现存的资源可以满足它尚需求的资源量 则按当前的申 请量来分配资源 否则就推迟分配 当进程在执行中继续申请资源时 先测试该进程申请的资源量是否超过了它尚需的资 源量 若超过则拒绝分配 若没有超过则再测试系统尚存的资源是否满足该进程尚需 的资源量 若满足即可按当前的申请量来分配 若不满足亦推迟分配 2 2 基本要求基本要求 1 可以输入某系统的资源以及 T0 时刻进程对资源的占用及需求情况的表项 以及 T0 时刻系统的可利用资源数 2 对 T0 时刻的进行安全性检测 即检测在 T0 时刻该状态是否安全 3 进程申请资源 用银行家算法对其进行检测 分为以下三种情况 A 所申请的资源大于其所需资源 提示分配不合理不予分配并返回 B 所申请的资源未大于其所需资源 但大于系统此时的可利用资源 提示分配 不合理不予分配并返回 C 所申请的资源未大于其所需资源 亦未大于系统此时的可利用资源 预分配并 进行安全性检查 a 预分配后系统是安全的 将该进程所申请的资源予以实际分配并打印后返 回 b 与分配后系统进入不安全状态 提示系统不安全并返回 4 对输入进行检查 即若输入不符合条件 应当报错并返回重新输入 3 3 目的 目的 根据设计题目的要求 充分地分析和理解题目 叙述系统的要求 明确程序要求实现 的功能以及限制条件 明白自己需要用代码实现的功能 清楚编写每部分代码的目的 做到有的放矢 有条 理不遗漏的用代码实现银行家算法 二二 概要设计概要设计 1 1 算法思路 算法思路 先对用户提出的请求进行合法性检查 即检查请求是否大于需要的 是否大于可利用 的 若请求合法 则进行预分配 对分配后的状态调用安全性算法进行检查 若安全 则 分配 若不安全 则拒绝申请 恢复到原来的状态 拒绝申请 2 2 安全性算法步骤安全性算法步骤 1 设置两个变量 剩余资源变量盘 p 它表示系统可提供进程继续运行所需要的各类资源数目 执 行安全算法开始时 p N S N 2 标记数组 C 它表示系统是否有足够的资源分配给进程 使之运行完成 开始时先做 C i F 当有足够资源分配给进程时 令 C i T 2 从进程集合中找到一个能满足下述条件的进程 C i F Q p 如找到 执行步骤 3 否则 执行步骤 4 3 当进程 T 获得资源后 可顺利执行 直至完成 并释放出分配给它的资源 故应执行 p p R C i T 转向步骤 2 4 如果所有进程的 C i T 则表示系统处于安全状态 否则 系统处于不安全 状态 3 3 进程请求算法步骤进程请求算法步骤 1 如果 Request Q 则转向步骤 2 否则 认为出错 因为它所需要的资源数 已超过它所宣布的最大值 2 如果 Request p 则转向步骤 3 否则 表示系统中尚无足够的资源 进程必须等待 3 系统试探把要求的资源分配给进程 Tt t 从 1 开始 并修改下面数据结构中的数值 p j p j Request t 1 j R t 1 j R t 1 j Request t 1 j Q t 1 j Q t 1 j Request t 1 j 4 系统执行安全性算法 检查此次资源分配后 系统是否处于安全状态 4 4 主要用到的数据结构 主要用到的数据结构 1 最大需求矩阵 Max N N 2 已分配矩阵 R N N 3 仍需求矩阵 Q N N Max N N R N N 4 可利用资源向量 p N 5 申请各类资源向量 Request N 6 工作向量 work C N 7 各类资源总数 S N 5 5 程序模块 程序模块 voidvoid main 系统的主函数 用来显示资源的分配情况和提示信息 同时用 Main 函数来调用其它子程序 int check 安全性检查函数 用来检查是否有安全序列 如果存在则返回一个 1 给主函数 否则返回 0 int judge 进程请求函数 用来进行资源请求 分为手动的和随机申请 同时对 申请的资源进行判断 检查申请是否有效 如果有效则返回一个 1 给主函数 否则 返回 0 三 流程图三 流程图 3 1 1 银行家算法银行家算法 Main Main 函数流程图函数流程图 开开始始 输输入入进进程程个个数数 输输入入资资源源类类数数 输输入入每每类类资资源源数数 输输入入进进程程最最大大需需求求矩矩阵阵Max 已已分分配配矩矩阵阵R R 尚尚需需矩矩阵阵Q Q M MA AX X R R 打打印印输输出出此此时时资资 源源分分配配情情况况表表 调调用用c ch he ec ck k 函函数数进进行行 安安全全性性检检查查 调调用用j ju ud dg ge e 函函数数进进 行行请请求求分分配配 4 2 安全性检查算法安全性检查算法 check 函数流程图函数流程图 调用调用 check check 函函 数数 p S C F Q i j p j C i F p j p j R i j C i T Y N 所有进程的所有进程的 C i T l m Y N 输出安全序列 并输出安全序列 并 打印出当前资源分打印出当前资源分 配情况配情况 输出提示 系统不安输出提示 系统不安 全全 调用结束调用结束 j n Y N 5 3 进程请求算法进程请求算法 judge 函数流程图函数流程图 四 运行结果及说明四 运行结果及说明 输入进程总数 资源总类 每类资源总数 然后输入已分配矩阵 最大需求矩阵 系统会求出尚需矩阵并且在屏幕上输出 然后系统调用 check 安全检查函数 进行安全检查 会在屏幕上输出系统是否安全 若安全 则会输出安全序列 接着系统调用 judge 请求分配函数 屏幕上提醒输入要申请资源的序列号和 要申请的各类资源数 输入以后 系统会进行判断要申请的资源数是否小于剩 余资源数 是否小于或等于最大需求数 若都小于 系统会进行安全检查 若 安全 系统就会进行资源分配 运行结果如下 运行结果如下 6 五 总结五 总结 通过这次的课程设计 我了解掌握了银行家算法 学会模拟实现资源分配 同时通过编写和调试一个系统分配资源的简单模拟程序 观察到了死锁产生的 条件 并使用适当的算法 有效的防止和避免死锁的发生 虽然操作系统是以前学的 再接触时遗忘了许多 但是通过老师的讲解 同学的帮助 自己也仔细地看了这次课程设计的实验指导 捡回了许多东西 对于银行家算法的设计 编写的思路变得清晰 通过几天反复的阅读实验指导 仔细的思考出现的问题 反复推敲 测试与修改 终于能完满的完成课程设计 任务 课程设计的时间虽然不长 但带了给我知识 也带给了我战胜困难 完 成任务的欢乐 希望以后有更多的机会接触这类的课程设计 7 附 程序清单 define N 100 include int T N int S N 各类资源总数 int p N 剩余资源数 char C N int R N N 已分配矩阵 int Q N N 尚需分配矩阵 int MAX N N 最大需求矩阵 int check int judge main int sum i j n m printf 请输入进程总数 scanf d printf 请输入资源总类数 scanf d printf 请输入每类资源总数 for j 0 j n j scanf d printf 请输入已分配资源矩阵 n for i 0 i m i for j 0 j n j scanf d 已分配矩阵 printf 请输入最大需求资源矩阵 n for i 0 i m i for j 0 j n j scanf d 最大需求矩阵 printf 尚需分配资源矩阵为 n printf 进程名 for j 0 j n j printf R d t j 1 printf n for i 0 i m i printf T d t i 1 for j 0 j n j Q i j MAX i j R i j 8 printf d t Q i j 尚需分配矩阵 printf n check m n judge m n int check int m int n 安全检查函数 int i j k l 0 for j 0 j n j p j S j for i 0 i m i p j p j R i j for i 0 i m i C i F for i 0 i m i if C i T continue else for j 0 j n j if p j Q i j break if j n C i T for k 0 k n k p k R i k T l i i 1 else continue if l m printf 系统是安全的 n printf 安全序列是 n for i 0 i printf n 9 return 1 int judge int m int n 进程请求函数 int i j t int Request N N char ch while 1 printf 输入要申请的资源的进程号 1 d m scanf d printf 输入进程所请求的各资源的数量 for j 0 j n j scanf d for j 0 jQ t 1 j printf 你输入的请求数超过进程的需求量 n return 0 if Request t 1 j p j printf 你输入的请求数超过系统有的资源数 n return 0 for j 0 j n j p j Request t 1 j R t 1 j Request t 1 j Q t 1 j Request t 1 j if check printf 同意分配请求 n else printf 你的请求被拒绝 n 10 for j 0 j n j p j Requ