银行家算法(用C语言实现)课程设计报告

课程设计报告课程设计报告 题题 目目 银行家算法程序设计银行家算法程序设计 课课 程程 名名 称称 操作系统课程设计操作系统课程设计 院院 部部 名名 称称 信息技术学院信息技术学院 专专 业业 计算机科学与技术计算机科学与技术 班班 级级 学学 生生 姓姓 名名 学学 号号 课程设计地点课程设计地点 课程设计学时课程设计学时 20 指指 导导 教教 师师 教务处制教务处制 成绩 1 操作系统课程设计报告操作系统课程设计报告 摘摘 要要 Dijkstra 提出的银行家算法 是最具代表性的避免死锁的算法 本文对如何用银行家算法来处理操作系统给进程分配资源做了详细的说明 包括需求分析 概要设计 详细设计 测试与分析 总结 源程序清单 首先做了需求分析 解释了什么是银行家算法 并指出它在资源分配中的 重要作用 然后给出了银行家算法的概要设计 包括算法思路 步骤 以及要用到的 主要数据结构 函数模块及其之间的调用关系等 在概要设计的基础上 又给出了详细的算法设计 实现概要设计中定义的 所有函数 对每个函数写出核心算法 并画出了流程图 接着对编码进行了测试与分析 并在最后附上 Java 编写的程序代码 最后对整个设计过程进行了总结 关键词关键词 安全状态 安全序列 银行家算法 安全性算法 安全序列 流 程图 2 目录目录 摘要摘要 1 目录目录 2 1 绪论绪论 3 1 1 前言前言 3 1 2 研究意义研究意义 4 1 3 结构安排结构安排 4 2 需求分析需求分析 5 2 1 题目描述题目描述 5 2 2 银行家算法银行家算法 5 2 3 基本要求基本要求 5 2 4 目的目的 6 3 概要设计概要设计 7 3 1 设备环境设备环境 7 3 2 算法思路算法思路 7 3 3 银行家算法步骤银行家算法步骤 7 3 4 安全性算法步骤安全性算法步骤 8 3 5 数据结构数据结构 9 3 6 系统结构图系统结构图 12 4 详细设计详细设计 13 4 1 主要函数的核心代码主要函数的核心代码 13 4 2 程序流程图程序流程图 13 5 测试测试 16 5 1 测试用例测试用例 16 5 2 测试结果截图测试结果截图 17 6 总结总结 22 参考文献参考文献 24 致谢致谢 25 附录附录 26 3 1 绪论绪论 1 1 前言前言 Dijkstra 1965 提出了一种能够避免死锁的调度算法 称为银行家算法 它的模型基于一个小城镇的银行家 他向一群客户分别承诺了一定的贷款 额度 每个客户都有一个贷款额度 银行家知道不可能所有客户同时都需要最 大贷款额 所以他只保留一定单位的资金来为客户服务 而不是满足所有客户 贷款需求的最大单位 这里将客户比作进程 贷款比作设备 银行家比作系统 客户们各自做自己的生意 在某些时刻需要贷款 在某一时刻 客户已获 得的贷款和可用的最大数额贷款称为与资源分配相关的系统状态 一个状态被 称为是安全的 其条件是存在一个状态序列能够使所有的客户均得到其所需的 贷款 如果忽然所有的客户都申请 希望得到最大贷款额 而银行家无法满足 其中任何一个的要求 则发生死锁 不安全状态并不一定导致死锁 因为客户 未必需要其最大贷款额度 但银行家不敢抱这种侥幸心理 银行家算法就是对每一个请求进行检查 检查如果满足它是否会导致不安 全状态 若是 则不满足该请求 否则便满足 检查状态是否安全的方法是看他是否有足够的资源满足一个距最大需求最 近的客户 如果可以 则这笔投资认为是能够收回的 然后接着检查下一个距 最大需求最近的客户 如此反复下去 如果所有投资最终都被收回 则该状态是安全的 最初的请求可以批准 4 1 2 研究意义研究意义 在多道程序系统中 多个进程的并发执行来改善系统的资源利用率 提高 系统的吞吐量 但可能发生一种危险 死锁 所谓死锁 Deadlock 是指多个 进程在运行过程中因争夺资源而造成的一种僵局 DeadlyEmbrace 当进程处 于这种状态时 若无外力作用 他们都无法在向前推进 要预防死锁 有摒弃 请求和保持 条件 摒弃 不剥夺 条件 摒弃 环路等待 条件等方法 但是 在预防死锁的几种方法之中 都施加了较强的限制条件 而在避免 死锁的方法中 所施加的限制条件较弱 有可能获得令人满意的系统性能 在 该方法中把系统状态分为安全状态和不安全状态 便可避免死锁的发生 而最具代表性的避免死锁的算法 便是 Dijkstra 的银行家算法 利用银行家算法 我们可以来检测 CPU 为进程分配资源的情况 决定 CPU 是否响应某进程的的请求并为其分配资源 从而很好避免了死锁的产生 1 3 结构安排结构安排 一 绪论 介绍了题目背景以及研究意义 二 需求分析 介绍了题目描述 银行家算法 以及基本要求和所需达到 的目的 三 概要设计 介绍了基本的算法思路 步骤 以及数据结构和主要的函 数模块及其调用关系 四 详细设计 介绍了主要函数及其核心代码 以及程序流程图 五 测试 六 总结 参考文献 附录 原程序清单 5 2 需求分析需求分析 2 1 题目描述题目描述 银行家算法是一种最具有代表性的避免死锁的算法 所谓安全状态 是指系统能按照某种进程顺序 P1 P2 Pn 称 P1 P2 Pn 序列为安全序列 来为每个进程 Pi 分配其所需资源 直至满 足每个进程对资源的最大需求 使每个进程都可以顺利完成 安全状态一定没 有死锁发生 如果系统无法找到这样一个安全序列 则称系统处于不安全状态 那么 什么是安全序列呢 如果对每一个进程 Pi 1 i n 它以后尚需要的 资源量不超过系统当前可利用的资源量与所有的进程 Pj j n 所占有的资源量之 和 则称此进程序列 P1 P2 Pn 是安全的 称作安全序列 2 2 银行家算法银行家算法 我们可以把操作系统看做是银行家 操作系统管理的资源相当于银行家管 理的资金 进程向操作系统请求资源相当于客户向银行家贷款 操作系统按银行家制定的规则为进程分配资源 当进程首次申请资源时 要测试该进程尚需求的资源量 若是系统现存的资源可以满足它尚需求的资源 量 则按当前的申请量来分配资源 否则就推迟分配 当进程在执行中继续申请资源时 先测试该进程申请的资源量是否超过了 它尚需的资源量 若超过则拒绝分配 若没超过则再测试系统尚存的资源是否 满足该进程尚需的资源量 若满足即可按当前的申请量来分配 若不满足亦推 迟分配 2 3 基本要求基本要求 6 设计一 n 个并发进程共享 m 个系统资源的程序实现银行家算法 要求包括 1 简单的初始化界面 2 系统资源的占用和剩余情况 3 为进程分配资源 用银行家算法对其进行检测 分为以下三种情况 A 所申请的资源大于其所需资源 提示分配不合理不予分配并返回 B 所申请的资源未大于其所需资源 但大于系统此时的可利用资源 提示分配不合理不予分配并返回 C 所申请的资源未大于其所需资源 亦未大于系统此时的可利用资源 预分配并进行安全性检查 a 预分配后系统是安全的 将该进程所申请的资源予以实际分配 并打印后返回 b 与分配后系统进入不安全状态 提示系统不安全并返回 4 对输入进行检查 即若输入不符合条件 应当报错并返回重新输入 5 撤销作业 释放资源 2 4 目的 目的 银行家算法是避免死锁的一种重要方法 本设计要求用 C 语言编写和调试 一个简单的银行家算法程序 加深有关资源申请 避免死锁等概念 并体会和 了解死锁和避免死锁的具体实施方法 通过设计这个算法 让学生能够对书本 知识有更深的理解 在操作和其它方面有更高的提升 对程序设计的水平也有 所提高 根据设计题目的要求 充分地分析和理解题目 叙述系统的要求 明确程 序要求实现的功能以及限制条件 明白自己需要用代码实现的功能 清楚编写每部分代码的目的 做到有的 放矢 有条理不遗漏的用代码实现银行家算法 7 3 概要设计概要设计 3 1 设备环境 设备环境 软件 windows XP Microsoft Officc Word 2003 Microsoft Officc Visio 2003 Turbo C 2 0 硬件 CPU 2 00GHZ 内存 0 99GB 主频 2 00HZ 3 2 算法思路算法思路 先对用户提出的请求进行合法性检查 即检查请求是否大于需要的 是否 大于可利用的 若请求合法 则进行预分配 对分配后的状态调用安全性算法 进行检查 若安全 则分配 若不安全 则拒绝申请 恢复到原来的状态 拒 绝申请 3 3 银行家算法步骤银行家算法步骤 1 如果 Requesti or Need 则转向步骤 2 否则 认为出错 因为它所需要 的资源数已超过它所宣布的最大值 8 2 如果 Request or Available 则转向步骤 3 否则 表示系统中尚无足 够的资源 进程必须等待 3 系统试探把要求的资源分配给进程 Pi 并修改下面数据结构中的数值 Available Available Request i Allocation Allocation Request Need Need Request 4 系统执行安全性算法 检查此次资源分配后 系统是否处于安全状态 3 4 安全性算法步骤安全性算法步骤 1 设置两个向量 工作向量 Work 它表示系统可提供进程继续运行所需要的各类资源数目 执行安全算法开始时 Work Allocation 标志向量 Finish 它表示系统是否有足够的资源分配给进程 使之运行 完成 开始时先做 Finish i 0 当有足够资源分配给进程时 令 Finish i 1 2 从进程集合中找到一个能满足下述条件的进程 Finish i 0 Need or Work 如找到 执行步骤 3 否则 执行步骤 4 3 当进程 P 获得资源后 可顺利执行 直至完成 并释放出分配给它的资源 故应执行 9 Work Work Allocation Finish i 1 转向步骤 2 4 如果所有进程的 Finish i 1 则表示系统处于安全状态 否则 系统处于不 安全状态 3 5 数据结构数据结构 3 5 1 主要用到的数据结构 主要用到的数据结构 1 工作向量 已分配矩阵 rdy 2 仍需求矩阵 nd max rdy 3 可利用资源向量 sys 4 申请各类资源向量 req 5 等待向量 wait 6 标志向量 zhuang 3 5 2 程序模块 程序模块 main 系统的主函数 int pstart 初始化 10 void inputpcb 输入资源及进程 void csh 数据备份 void outputpcb 打印输出 void inputreq 提出资源请求 int canloc 判断请求 int change int a 10 int b 假设满足请求后 修改资源个数 int exchange int a 10 int b 请求不能满足 恢复资源个数 int ss int ri 判断是否有安全序列 int locate 利用安全性算法进行安全性检测 void agree 资源分配后修改资源个数 void output 输出安全序列 void back 撤销作业 归还资源 3 5 3 各模块间的调用关系 各模块间的调用关系 主函数 main 要调用 pstart inputpcb csh outputpcb inputreq canloc ss ri change req qq output agree exchange req qq 11 初始化函数pstart 要调用 exit back 银行家算法函数ss 要调用 locate 3 6 系统结构图系统结构图 main 初 始 化 模 块 输 入 模 块 进 程 提 出 请 求 模 块 备 份 模 块 资 源 信 息 输 出 模 块 判 断 请 求 模 块 安 全 性 检 查 模 块 资 源 分 配 输 出 模 块 进 程 撤 销 模 块 判断请求模块 请求与最大 需求相比 请求与还需 资源相比 请求与系统 资源相比 查找安全序 列 安全性检查模块 保存安全序 列 实际分配资 源 12 4 详细设计详细设计 4 1 主要函数的核心代码主要函数的核心代码 1 进行初始化输入的函数 2 打印输出的函数 3 利用安全性算法进行检测的函数 4 进行资源分配的函数 5 利用行家算法进行判定的函数 4 2 程序流程图程序流程图 1 系统主要过程流程图 撤销进程撤销相应等 待进程 进程撤销模块 回收资源 13 2 银行家算法流程图 14 15 3 安全性算法流程图 调用 Safty 函数 Work Available Finish False Need Available b 4 2 1 1 Request Need c 1 1 0 1 可以分配 d 2 1 2 1 系统不安全 5 2 测试结果截图 测试结果截图 17 1 开始界面 2 初始化并打印输出 18 3 用例测试 a 进程 1 发出请求 Request 7 2 2 Request Available 不予分配 保存请求 当资源足够时再行分配 4 用例测试 b 进程 4 发出请求 Request 2 1 1 Request Need 不予分配 19 5 用例测试 c 进程 1 发出请求 Request 1 0 1 可以分配 6 用例测试 d 进程 2 发出请求 Request 1 2 1 系统不安全 20 7 输入测试 a 如果进行作业 的撤消 且进行资源的回收 8 输入测试 b 如果进行作业 1 的撤消 且进行资源的回收 若等 待队列中也有相应的作业 则一起删除 21 9 输入测试 c 所作业全部撤销后 显示系统可用资源 10 输入测试 a 输入 a 则退出运行 22 6 总结总结 在银行家算法这个系统之中 所采用的数据结构应是最基本的部分 银行 家算法的数据结构我们采用了一维数组与二维数组来存储 比如已分配资源数 rdy 仍需求资源数 nd 以及系统可利用的资源数 sys 申请各类资源 req 进程个数 jc 等数组 其中每一个进程还使用了结构体 数据结构虽然重要但却只是基础 而最主要的用以实现系统功能的应该有 两个部分 一是用银行家算法来判断 二是用安全性算法来检测系统的安全性 在本程序代码中 银行家算法用 canloc 函数来实现 首先 输入欲申请资源的进程以及其所申请的资源数 存放在 qq 变量和 req 数组中 然后 判断进程请求的资源数是否大于其所需的资源数 若大于则报错并 返回 若不大于则继续判断它是否大于系统在此时刻可利用的资源数 同样 如果大于则报错并反回 如果不大于则调用 change 函数来进行预分配 之后 再调用安全型算法 ss 检查 若检查结果为不安全 则调用 exchange 函数来改 回原值 最后 无论此次分配是否成功 我们都可以选择继续分配或者退出系统或 者撤销进程 安全性检测我们是用 locate 函数来实现的 首先 zhuang 为布尔型 默认是 0 即该进程未完成 而 sys 即该系 统中可以用来工作的资源数 最开始为系统最初可以用的资源数 然后 我们从第一个进程开始判断该进程未完成且其所需求的资源量不大 于该系统中可以用来工作的资源量这个条件是否成立 即 zhuang 0 且 jc nd sys 是否成立 成立的话则将当前在工作的资源量与该进程已分配的资 源量相加 存放于当前可用来工作的资源量当中 即 Work Work 23 Allocation 并将 zhuang 1 否则便将此进程的优先级减一 排在队位 然 后开始往后循环 待所有的进程循环完毕 我们再次判断是否还存在进程的 zhuang 0 如 果仍存在 则说明系统没有安全序列 处于不安全状态 不可以进行分配 否 则 系统处于安全状态 将预分配变为实际分配 求出安全序列并且将实际分 配后的资源分配情况打印输出 除此之外 在程序当中 我们也得强调一下对输入的合法性的判断 比如 我们输入的欲申请资源的进程号没有在系统已存在的进程当中 或者进程号定 义为整型 但是却错输成字母等情况 我们需要对这些情况进行判断 让程序 报错返回而并非因错误而中断 这样的情况处理起来比较麻烦 相当于对每次输入针对各种不同的情况都 得做判断 我也没有涵盖全部的输入 仅仅只是对输入的进程号不在已存在进 程当中 以及输入的操作选择不存在两种情况分别作了判断 并且针对第二种 情况设定了五次输入错误的话系统关闭的功能 而因为对于某些 比如进程 号 本来设定就是整型 因此对输入的是字母的判别因比较复杂而未能加上 总之 银行家算法是避免死锁的主要方法 其思路在很多方面都非常值得 我们来学习借鉴 24 参考文献参考文献 1 汤小丹 梁红兵 哲凤屏 汤子瀛 计算机操作系统 西安 西安电子科技大 学出版社 2007 2 严蔚敏 吴伟民 数据结构 北京 清华大学出版社 2006 3 田祥宏 沈奇 王旭辉 吕艳琳 C 语言程序设计 西安 西安电子科技 大学出版社 2007 4 百度文库 银行 家算法报告 5 志文工作室 银行家算法模 拟实现 25 致谢致谢 历时将近两个星期的时间终于将这篇课程设计报告写完 在报告的写作过 程中遇到了无数的困难和障碍 都在同学和老师的帮助下度过了 尤其要强烈 感谢我的课设指导老师何健老师 他对我进行了无私的指导和帮助 不厌其烦 的帮助进行论文的修改和改进 另外 在校图书馆查找资料的时候 图书馆的 老师也给我提供了很多方面的支持与帮助 在此向帮助和指导过我的各位老师 表示最中心的感谢 感谢这篇论文所涉及到的各位学者 本文引用了数位学者的研究文献 如 果没有各位学者的研究成果的帮助和启发 我将很难完成本篇论文的写作 感谢我的同学和朋友 在我写论文的过程中给予我了很多你问素材 还在 论文的撰写和排版灯过程中提供热情的帮助 由于我的学术水平有限 所写论文难免有不足之处 恳请各位老师和学友 批评和指正 26 附录 源程序主模块清单附录 源程序主模块清单 include 头文件头文件 struct pcb 结构体定义结构体定义 int rdy 10 int nd 10 jc 10 tjc 10 int sys 10 tsys 10 int nn n g qq ri 0 a 0 ww 10 wait 10 10 req 10 as 10 t zhuang 10 char tcs 定义全局变量定义全局变量 void inputreq 某一进程得出资源请求某一进程得出资源请求 int i j 0 printf please input the PCB requested n n If you have no request you can check the wait n n scanf d oo if qq 1000 qq 0 printf please input the PCB requested n n scanf d for i 1 i n i if qq i j if j 1 printf meiyou xiangtong de jincheng please input the PCB requested n n scanf d goto oo printf please input the source requested n n for i 1 i1000 req i 0 printf please input the source requested n n 27 scanf d goto ooo int locate 查找安全序列查找安全序列 int i j k for g 1 g n g j 0 if zhuang g 0 for i 1 isys i j 1 i nn if j 0 for k 1 k nn k sys k jc g rdy k zhuang g 1 return g return 0 int canloc 判断请求是否合理判断请求是否合理 int i j 0 for i 1 i jc qq nd i j 1 if j 1 return 2 for i 1 isys i j 1 if j 0 return 1 else return 0 void back 撤销进程 回收资源撤销进程 回收资源 int i