银行家算法课程设计报告.doc

操作系统课程设计报告操作系统课程设计报告 题目 银行家算法设计与实现题目 银行家算法设计与实现 院院 系 系 计算机科学与工程学院计算机科学与工程学院 专专 业 业 对日软件对日软件 班班 级 级 080612 学学 生 生 闫建军闫建军 学学 号 号 080608115 指导教师 指导教师 姜虹姜虹 2010 年 12 月 操作系统课程设计报告 1 银行家算法设计与实现银行家算法设计与实现 摘摘 要要 银行家算法是一个用来预防系统进入死锁状态的算法 用它可以判断系统 的安全性 如果系统当前处于安全状态 则可以为申请资源的进程分配资源 如果不是安全状态 则不能为申请资源的进程分配资源 银行家算法执行过程中 首先判断申请资源的进程所申请的资源数目是否 合法 若是合法的 则可以为其进行试分配 再利用安全性算法求出安全序列 如果存在安全序列 则说明可以给申请资源的进程分配资源 分配成功 继 续为其它进程服务 如果找不到安全序列 则说明为该进程分配资源后系统会 进入不安全状态 所以不能为该进程分配资源 使该进程进入阻塞状态 若申 请资源的进程申请的资源数目不合法 则不需要进行试分配 直接使其进入阻 塞状态 处理其他申请资源的进程 论文首先对算法的设计从总体上进行了分析 然后分析各个细节 再对算 法分模块设计 并对各个模块的算法思想通过流程图表示 分块编写代码 并 进行调试和测试 最后进行组装测试及系统测试 使其成为一个可以用来判断 系统安全状态的程序 关键词 可用资源关键词 可用资源 最大需求矩阵最大需求矩阵 分配矩阵分配矩阵 需求矩阵需求矩阵 请求向量请求向量 试分配试分配 安全性算法安全性算法 安全序列安全序列 操作系统课程设计报告 2 目目 录录 银行家算法设计与实现 1 摘 要 1 目 录 2 1 绪论 5 1 1 课题背景 5 1 2 课题意义 5 1 3 运行环境 5 2 需求分析 1 2 1 问题描述 1 2 2 基本要求 1 2 3 概要分析 2 3 算法思想 3 3 1 安全性算法的算法思想 3 3 1 1 设置两个向量 3 3 1 2 安全性检测 3 3 2 银行家算法的算法思想 4 操作系统课程设计报告 3 3 2 1 银行家算法的思路 4 3 2 2 银行家算法 4 3 2 3 安全性检查算法 5 4 详细设计 6 4 1 银行家算法中用到的主要数据结构设计 6 4 2 算法整体设计与调用 6 4 3 模块设计与时间复杂度分析 8 4 3 1 int check distribution int p int k 函数 8 4 3 2 int check safe 银行家算法 8 4 3 2 void print 输出函数 8 4 4 程序流程图 8 4 5 1 主函数 void main 函数流程图 9 4 5 2 判断试分配函数 int check distribution int p int k 流程图 9 4 5 3 银行家算法 int check safe 流程图 10 4 5 4 输出函数 void print 流程图 11 5 程序调试 分析与修改 12 5 1 分模块调试与分析 12 5 1 1 进程信息的输入与输出调试 12 5 1 2 进程请求资源输入出错提示信息处理 13 5 1 3 判断试分配函数 int check distribution int p int k 13 5 1 4 求安全序列函数 int check safe 14 操作系统课程设计报告 4 6 结论 15 7 小结 16 参考文献 17 附录 源代码 18 绪论 5 1 绪论绪论 1 11 1 课题背景课题背景 在预防死锁的各种算法中 总的来说 都是施加了较强的限制条件 从而 使实现简单 但却严重地损害了系统的性能 在避免死锁的算法中 施加的条 件较较弱 有可能获得令人满意的系统性能 在该方法中把系统的状态分为安 全状态和不安全状态 只要能使系统处于安全状态 便可避免死锁的发生 最具有代表性的避免死锁的算法是 Dijkstra 的银行家算法 这是因为该算 法能用于银行系统现金贷款的发放而得名 在这一次的课程设计中就要对银行 家算法从分析到实现 整体做一个详细的描述 1 21 2 课题意义课题意义 1 从课程设计上讲 提高自己的分析问题 解决问题和动手能力 2 从银行家算法上本身讲 通过算法可以判断系统的安全性 对申请资 源的进程进行限制 从而避免系统进入死锁状态 1 31 3 运行环境运行环境 TurboTurbo C C VisualVisual C C 6 06 0 2 需求分析 1 2 需求分析需求分析 2 12 1 问题描述问题描述 当系统在进行资源管理时 如果对进城申请的资源分配不当 可能会使系 统进入死锁状态 因而后面到来的进程也无法顺利执行 银行家算法中 要对 当前申请资源的进程申请资源的数目进行判断 如果可以试分配 则试求出一 个安全序列 如果可以求出 则说明给这个进程分配资源后系统不会进入不安 全状态 将该进程申请的资源分配给他 若求不出安全序列 则说明将资源分 配给该进程后系统会进入不安全状态 所以就使该进程进入阻塞状态 等待以 后可以分配资源时再执行该进程 然后系统继续服务其它进程 通过这样一个 过程 可以有效避免系统进入死锁状态 2 22 2 基本要求基本要求 1 对各个进程的进程名 最大需求资源 已分配资源 系统可用资源等进 行有序的输入 2 对申请资源的进程要有合法性判断 如进程名 申请资源数等 3 若有进程申请资源 首先要对它申请的资源数进行判断 4 在上面判断合法的前提下进行试分配 利用银行家算法求出安全序列 如果可以求出安全序列 则为该进程分配资源 否则使它进入阻塞状态 2 需求分析 2 2 32 3 概要分析概要分析 在避免死锁的算法中 允许进程动态地申请资源 系统在进行资源分配之 前 先计算资源分配的安全性 若此次分配不会使系统进入不安全状态 便将 资源分配给该进程否则进程等待 所谓安全状态是指系统能按某种顺序如 称 为安全序列 就这样来为每个进程分配资源 直至最大 需求 使每个进程都可以顺序地执行完毕 若系统不存在这样一个安全序列 那么系统此时会进入不安全状态 虽然并非所有的不安全状态都会产生死锁状态 但当系统进入不安全状态 后 便可能进而进入死锁状态 反之 只要系统处于安全状态 系统便可避免 进入死锁状态 因此 避免死锁的实质在于 如何使系统不进入不安全状态 银行家算法就是用来判断某种情况会不会进入不安全状态 操作系统课程设计报告 3 3 算法思想算法思想 3 1 安全性算法的算法思想安全性算法的算法思想 思想 系统在进行资源分配之前 应先计算此次资源分配后状态的安全性 若此次分配后的状态是安全状态 则将资源分配给进程 否则 令进程等待 3 1 13 1 1 设置两个向量设置两个向量 1 工作向量Work m 它表示系统可提供给进程继续运行所需的各类资源 数目 Work初 Available 2 Finish n 它表示系统是否有足够的资源分配给进程 使之运行完 成 false表示未完成 true表示完成 3 1 2 安全性检测安全性检测 Work Available Finish 根据根据Need赋赋 值值 寻找进程寻找进程i 满足 满足 Finish i false 且且Need i work 返回安全状态返回安全状态 y Work work Allocation i Finish i true 找到找到 所有进程的所有进程的 Finish i true 没找到没找到 n 返回不安全状态返回不安全状态 操作系统课程设计报告 4 3 23 2 银行家算法的算法思想银行家算法的算法思想 3 2 13 2 1 银行家算法的思路银行家算法的思路 先对用户提出的请求进行合法性检查 即检查请求的是不大于需要的 是 否不大于可利用的 若请求合法 则进行试分配 最后对试分配后的状态调用 安全性检查算法进行安全性检查 若安全 则分配 否则 不分配 恢复原来 状态 拒绝申请 3 2 23 2 2 银行家算法银行家算法 进程 i 发出申请资源请求 1 调用 check distribution int p int k 检查申请量是否不大于需求量再 检查检查申请量是否小于系统中的可利用资源数量 若条件不符重新输入 不 允许申请大于需求量 2 若以上条件都满足 则系统试探着将资源分配给申请的进程 并修改下面 数据结构中的数值 Available i j Available i j Request i j Allocation i j Allocation i j Request i j need i j need i j Request i j 3 进行试分配 执行安全性检查 调用 check safe 函数检查此次资源试分 配后系统是否处于安全状态 若安全 才正式将资源分配给进程 否则本次试 探分配作废 恢复原来的资源分配状态 让该进程等待 4 用 while 循环语句实现输入字符 Y N 判断是否继续进行资源申请 3 2 33 2 3 安全性检查算法安全性检查算法 1 设置向量 工作向量 Work 它表示系统可提供给进程继续运行所需的各类资源数目 在执 操作系统课程设计报告 5 行安全性算法开始时 Work Available Finish 它表示系统是否有足够的资源分配给每个进程 使之运行完成 开 始时先做 Finish i 0 当有足够的资源分配给进程时 再令 Finish i 1 2 在进程中查找符合以下条件的进程 条件 1 Finish i 0 条件 2 need i j Work j 若找到 则执行步骤 3 否则 执行步骤 4 3 当进程获得资源后 可顺利执行 直至完成 并释放出分配给它的资源 故 应执行 Work j Work j Allocation i j Finish i 1 goto step 2 4 最后循环检查是否所有的 Finish i 1 都满足 如果是 则返回 1 表示系统 处于安全状态 否则 返回 0 表示系统处于不安全状态 操作系统课程设计报告 6 4 详细设计详细设计 4 14 1银行家算法中用到的主要数据结构设计银行家算法中用到的主要数据结构设计 1 进程名向量 char processnema N 进程名 2 可利用资源向量 int Available M 资源清单 系统中现有各资源 空闲个数 3 最大需求矩阵 int Max N M 最大需求矩阵 每个进程对各 资源的最大需求数分配矩阵 4 已分配矩阵 int Allocation N M 分配矩阵 系统给每个进程 已分配的各类资源数 5 需求矩阵 int Need N M 需求矩阵 每个进程还需要每 种资源的个数申请各类资源数量 6 申请向量 int Request M 进程申请资源的向量 7 工作向量 int Work N M 初始第一个向量为 Available 随寻找安全序列时为其余每个向量赋值 可 以防止安全序列未找到而丢了初始状态的值 8 安全序列向量 int sequence N 0 存放安全序列号 9 标志向量 int Finish N 求安全序列时记录每个进程是否可以 顺利执行 4 2 算法整体设计与调用算法整体设计与调用 主函数 void main 首先输入每个进程信息 然后判断是否有进程申请 资源 若有 则调用 int check distribution int p int k 函数判断是否可以进行试 操作系统课程设计报告 7 分配 如果满足试分配条件 调用 int check safe 函数求安全序列 如果可以 求出安全序列 则说明分配后系统不会进入不安全状态 正式将资源分配给申 请资源的进程 最后用 void print 函数输出分配资源后每个进程的信息 如果 求不出安全序列 说明分配后系统会处于不安全状态 则不能将资源分配给该 进程 让其等待 系统恢复原始状态 如果申请资源的数量不满足条件 则让 该进程等待 继续判断其他申请资源的进程 1 int check distribution int p int k 这个函数用来判断是否可以 进行试分配 如果函数结果返回 1 说明可以进行试分配 如果行数返回 0 说 明申请资源的进程申请的资源数目不满足 Request need 或 Request available 条件 不能为该进程进行试分配 2 int check safe 这个函数用来求安全序列 首先初始化 Work 0 i Available i 然后循环找满足条件 Finish i 0 i M i 判断是否满足约束条件 p i Need k i 时间复杂 度为 O M 4 3 24 3 2 intint check safe check safe 银行家算法银行家算法 1 用 for i 0 i M i 循环 Work k i Available i Request i 初始化 Work 矩阵 2 用 for m 0 m N m 循环找出满足 0 Finish i i N i 检查是否所有进程都执行完了 如果所有进程都可执 行则 finish 值等于 1 4 由上面执行可以得出 int check safe 函数时间复杂度为 O N 或 O M 4 3 24 3 2 voidvoid print print 输出函数输出函数 for i 0 i N i for j 0 j M j 循环输出每个进程的每一类资源信息 时间复杂度为 O N 或 O M 4 44 4 程序流程图程序流程图 操作系统课程设计报告 9 4 5 14 5 1 主函数主函数 voidvoid mainmain 函数流程图 函数流程图 4 4 1 1 4 1 4 5 2 判断试分配函数 int check distribution int p int k 流程图 4 2 4 2 操作系统课程设计报告 10 4 5 3 银行家算法银行家算法 int check safe 流程图流程图 4 3 4 3 操作系统课程设计报告 11 4 5 4 输出函数输出函数 void print 流程图 流程图 4 4 4 4 操作系统课程设计报告 12 5 程序调试 分析与修改程序调试 分析与修改 5 15 1 分模块调试与分析分模块调试与分析 函数的书写分模块进行 每完成一个模块进行调试 测试直到该函数运行 无误 5 1 1 进程信息的输入与输出调试进程信息的输入与输出调试 1 能正确无误的输入进程名向量 processnema N 输入系统现有各类资源数量 Available M 向量 输入每个进程对各类资源的最大需求数 Max N M 矩阵 输 入系统给每个进程已分配的各类资源数 Allocation N M 矩阵 输出程序过程如 下 操作系统课程设计报告 13 2 在进程信息输入中没有出现多大问题 在进程信息输出时 按设计要求输 出的话应该是一个表格形式 在输出函数设计最初 由于有些部分分割或空格 没有填充好 导致输出表格比较乱 没有达到设计要求 经过修改后输出形式 才符合了设计要求 进程信息输入完成后 初始状态各进程信息输出如下 5 1 25 1 2 进程请求资源输入出错提示信息处理进程请求资源输入出错提示信息处理 1 在系统询问是否有进程申请资源时 如果有输入信息出错 系统会给与出 错提示 如果输入信息正确则系统将继续执行下面操作 执行如下 5 1 35 1 3 判断是否可以试分配函数判断是否可以试分配函数 intint check distribution int check distribution int p intp int k k 1 在这个函数中主要是对申请资源的进程申请的资源数量是否满足约束条件 Request need 或 Request available 如果不满足将打出提示信息 如果满足 则返回 1 继续执行下面程序 执行结果如下 操作系统课程设计报告 14 5 1 45 1 4 求安全序列函数求安全序列函数 intint check safe check safe 1 如果申请资源的进程申请的资源数目满足试分配条件 则再用这个函数来 求试分配后的安全序列 如果可以求出安全序列 则说明这次分配不会使系统 进入不安全状态 正式将资源分配给该进程 修改系统资源信息 如果求不出 安全序列 说明这次分配后系统会进入不安全状态 不能给该进程分配资源 系统恢复初始状态 打印出提示信息 执行结果如下 操作系统课程设计报告 15 6 结论结论 银行家算法是通过检查试分配 求安全序列 从而判断是否可以为申请资源 的进程分配资源 从而有效地避免系统进入死锁状态 7 小结 16 7 小结小结 虽然并非所有的不安全状态都会产生死锁状态 但系统进入不安全状态时 便可能进而进入死锁状态后 当系统在进行资源管理时 如果对进城申请的资 源分配不当 可能会使系统进入死锁状态 因而后面到来的进程也无法顺利执 行 银行家算法中 要对当前申请资源的进程申请资源的数目进行判断 如果 可以试分配 则试求出一个安全序列 如果可以求出 则说明给这个进程分配 资源后系统不会进入不安全状态 将该进程申请的资源分配给他 若求不出安 全序列 则说明将资源分配给该进程后系统会进入不安全状态 所以就使该进 程进入阻塞状态 等待以后可以分配资源时再执行该进程 然后系统继续服务 其它进程 通过这样一个过程 可以有效避免系统进入死锁状态 反之 只要 系统处于安全状态 系统便可避免进入死锁状态 因此 避免死锁的实质在于 如何使系统不进入不安全状态 参考文献 17 参考文献参考文献 1 数据结构实验指导书 网上资料 2 计算机操作系统 汤子瀛 哲凤屏 汤小丹 西安电子科技大学出 版社 3 C 语言程序设计 谭浩强 清华大学出版社 附录 源代码 18 附录 源代码 附录 源代码 include define N 5 进程个数 define M 3 资源种类数 void print int check safe int check distribution int p int k char processnema N 进程名 int Request M 请求向量 int Finish N 标记某一个进程是否可以执行 int Work N M 初始为 Available 随寻找安全序列而变化 防 止安全序列未找到而丢了初始状态的值 int Available M 资源清单 系统中现有各资源空闲个数 int Work Allocation N M int Max N M 最大需求矩阵 每个进程对各类资源的最大需求数 int Allocation N M 分配矩阵 系统给每个进程已分配的各类资源数 int Need N M 需求矩阵 每个进程还需要每种资源的个数 int sequence N 0 存放安全序列号 void main int i 0 j 0 k 0 记录申请资源的进程的序列号 int flag 0 标记输入的进程名是否存在 int safe 0 标志系统是否出于安全状态 0 表示不安全 1 表示安全 int distribution 0 标志是否可以进行试分配 0 表示可以 1 表示不 可以 char flag1 标记是否有进程申请资源 Need N M Max N M Allocation N M char name 要请求资源的进程名 printf 银行家算法 n printf 请分别初始化各矩阵信息 n printf 请输入各进程的进程名 n 进程名连续输入 附录 源代码 19 for i 0 i N i scanf c printf 请输入现有各资源空闲个数 n for i 0 i M i scanf d printf 请分别输入每个进程对各类资源的最大需求数 n for i 0 i N i for j 0 j M j scanf d printf 请分别输入系统给每个进程已分配的各类资源数 n for i 0 i N i for j 0 j M j scanf d printf 请分别输入每个进程还需要每种资源的个数 n for i 0 i N i for j 0 j M j Need i j Max i j Allocation i j 附录 源代码 20 printf 信息输入完毕 n for i 0 i N i sequence i i print safe check safe 检查初始状态是否安全 if 0 safe printf 系统现处于不安状态 不能为进程分配资源 进入死锁状态 n exit 0 else if 1 safe printf 系统处于安全状态 可以为进程分配资源 n while 1 safe 0 getchar printf 是否有进程请求系统资源 Y N n flag1 getchar scanf c if Y flag1 y flag1 printf 请输入进程名 getchar while 1 附录 源代码 21 name scanf c for i 0 i N i 检查进程名输入是否正确 if name processnema i flag 1 输入的进程名存在 k i break 找到申请资源的进程序列号跳出 getchar 将在此之前的一个回车接收了 不然会影响输入 if flag 1 进程名输入不合法 printf 你输入的进程不存在 请重新输入 continue else break 进程名输入合法 则执行下面操作 else if N flag1 n flag1 printf 进程执行完毕 退出系统 n break else if N flag1 continue 附录 源代码 22 printf 请输入该进程请求各类资源的数量 n for i 0 i M i scanf d distribution check distribution Request k 检查是否 可以试分配 if 1 distribution 检查 safe check safe 可以试分配 则求安全序列 if 1 safe 试分配成功 printf 试分配成功 可以为该进程分配资源 n distribution 是否给申请资源的进程分配资源 for i 0 i M i Allocation k i Allocation k i Request i 为进程分配资源后修改该进程的有关资源数 Need k i Need k i Request i printf 分配后各资源数量如下 n print printf 分配成功 n printf 系统剩余资源数各为 for i 0 i M i printf d Available i printf n continue 附录 源代码 23 else 试分配失败 printf 试分配失败 有可能进入死锁状态 请等待 n 未求出安全序列 continue else 试分配失败 printf 该进程申请的资源太多 无法分配 请等待 n continue void print int i j printf 资源 Work Need tAllocation tWork Allocation t Finish n n printf 进程名 A B C A B C t A B C t A B C n printf n for i 0 i N i printf c processnema sequence i for j 0 j M j printf d Work sequence i j printf for