处理机调度模拟设计——短作业先调度、先来先服务调度、最高响应比调度算法.doc

此文档收集于网络 如有侵权 请联系网站删除 此文档仅供学习与交流 衡阳师范学院衡阳师范学院 操作系统操作系统 课程设计课程设计 题题 目目 处理机调度模拟设计处理机调度模拟设计 短作业先调短作业先调 度 先来先服务调度 最高响应比调度 先来先服务调度 最高响应比调 度算法度算法 专专 业业 计算机科学与技术计算机科学与技术 班班 级级 1001 班班 学学 号号 10190134 10190136 姓姓 名名 张德旺张德旺 屈金屈金 指导教师指导教师 王玉奇王玉奇 2012 年12 月日 目目 录录 1 1 概述 概述 1 1 1 1 设计目的 1 1 2 设计内容 1 1 3 开发环境 1 1 4 任务分配 1 2 2 需求分析 需求分析 2 2 2 1 死锁概念 2 2 2 关于死锁的一些结论 2 2 3 资源分类 2 2 4 产生死锁的四个必要条件 3 2 5 死锁的解决方案 3 2 5 1 产生死锁的例子 3 2 5 2 死锁预防 4 2 6 安全状态与不安全状态 5 此文档收集于网络 如有侵权 请联系网站删除 此文档仅供学习与交流 3 3 数据结构设计 数据结构设计 5 5 3 1 定义全局变量 5 3 2 函数声明 5 3 3 主函数结构 6 4 4 算法的实现 算法的实现 7 7 4 1 初始化 7 4 2 银行家算法 7 4 3 安全性检查算法 7 4 4 程序模块划分 8 4 5 程序运行结果显示 9 4 6 各算法流程图 11 4 7 源程序清单 12 5 5 心得与体会 心得与体会 2222 6 6 参考文献 参考文献 2222 此文档收集于网络 如有侵权 请联系网站删除 此文档仅供学习与交流 1 1 概述 概述 1 11 1 设计目的 设计目的 1 了解多道程序系统中 多个进程并发执行的资源分配 2 掌握死锁的产生的原因 产生死锁的必要条件和处理死锁的基本方法 3 掌握预防死锁的方法 系统安全状态的基本概念 4 掌握银行家算法 了解资源在进程并发执行中的资源分配策略 5 理解死锁避免在当前计算机系统不常使用的原因 1 21 2 设计内容 设计内容 利用银行家算法来实现资源的分配 先对用户提出的请求进行合法性检查 再进行预 分配 利用安全性检查算法进行安全性检查 1 31 3 开发环境 开发环境 操作系统编译环境生成文件 Windows7Visual C 6 0Bank exe Windows7Code blocks 10 05Bank exe 源文件 Bank cpp 1 1 4 4 任务分配 任务分配 设计人员设计任务 刘新宇负责主要代码编写 丁正宁负责程序意见提取和进度安排 谭琼斐课程设计报告主要的书写 王正香心得与体会的书写 此文档收集于网络 如有侵权 请联系网站删除 此文档仅供学习与交流 2 2 需求分析 需求分析 2 12 1 死锁概念 死锁概念 在多道程序系统中 虽可借助于多个进程的并发执行 来改善系统的资源利用率 提高系统的吞吐量 但可能发生一种危险 死锁 所谓死锁 Deadlock 是指多个进 程在运行中因争夺资源而造成的一种僵局 Deadly Embrace 当进程处于这种僵持状态 时 若无外力作用 它们都将无法再向前推进 一组进程中 每个进程都无限等待被 该组进程中另一进程所占有的资源 因而永远无法得到的资源 这种现象称为进程死 锁 这一组进程就称为死锁进程 2 22 2 关于死锁的一些结论 关于死锁的一些结论 a 参与死锁的进程最少是两个 两个以上进程才会出现死锁 b 参与死锁的进程至少有两个已经占有资源 c 参与死锁的所有进程都在等待资源 d 参与死锁的进程是当前系统中所有进程的子集 注 如果死锁发生 会浪费大量系统资源 甚至导致系统崩溃 2 32 3 资源分类 资源分类 永久性资源 可以被多个进程多次使用 可再用资源 a 可抢占资源 b 不可抢占资源 临时性资源 只可使用一次的资源 如信号量 中断信号 同步信号等 可消耗性资源 申请 分配 使用 释放 模式 此文档收集于网络 如有侵权 请联系网站删除 此文档仅供学习与交流 2 42 4 产生死锁的四个必要条件 产生死锁的四个必要条件 1 互斥使用 资源独占 一个资源每次只能给一个进程使用 2 不可强占 不可剥夺 资源申请者不能强行的从资源占有者手中夺取资源 资源只能由占有者自愿释放 3 请求和保持 部分分配 占有申请 一个进程在申请新的资源的同时保持对原有资源的占有 只有这样才是动态申请 动 态分配 4 循环等待 存在一个进程等待队列 P1 P2 Pn 其中 P1 等待 P2 占有的资源 P2 等待 P3 占有的资源 Pn 等待 P1 占有的资源 形 成一个进程等待环路 2 52 5 死锁的解决方案死锁的解决方案 2 5 1 产生死锁的例子 申请不同类型资源产生死锁 P1 申请打印机 申请扫描仪 使用 释放打印机 释放扫描仪 P2 此文档收集于网络 如有侵权 请联系网站删除 此文档仅供学习与交流 申请扫描仪 申请打印机 使用 释放打印机 释放扫描仪 申请同类资源产生死锁 如内存 设有资源 R R 有 m 个分配单位 由 n 个进程 P1 P2 Pn n m 共享 假设每个 进程对 R 的申请和释放符合下列原则 一次只能申请一个单位 满足总申请后才能使用 使用完后一次性释放 m 2 n 3 资源分配不当导致死锁产生 2 5 2 死锁预防 定义 在系统设计时确定资源分配算法 保证不发生死锁 具体的做法是破坏产生死锁的 四个必要条件之一 破坏 不可剥夺 条件 在允许进程动态申请资源前提下规定 一个进程在申请新的资源不能立即得到满足而 变为等待状态之前 必须释放已占有的全部资源 若需要再重新申请 破坏 请求和保持 条件 要求每个进程在运行前必须一次性申请它所要求的所有资源 且仅当该进程所要资源 均可满足时才给予一次性分配 破坏 循环等待 条件 采用资源有序分配法 把系统中所有资源编号 进程在申请资源时必须严格按资源编号的递增次序进行 否 此文档收集于网络 如有侵权 请联系网站删除 此文档仅供学习与交流 则操作系统不予分配 2 62 6 安全状态与不安全状态 安全状态与不安全状态 安全状态 如果存在一个由系统中所有进程构成的安全序列 P1 Pn 则系统处于 安全状态 一个进程序列 P1 Pn 是安全的 如果对于每一个进程 Pi 1 i n 它 以后尚需要的资源量不超过系统当前剩余资源量与所有进程 Pj j i 当前占有资源量 之和 系统处于安全状态 安全状态一定是没有死锁发生的 不安全状态 不存在一个安全序列 不安全状态一定导致死锁 3 数据结构设计 数据结构设计 3 13 1 定义全局变量 定义全局变量 const int x 50 y 100 定义常量 便于修改 int Available x 各种资源可利用的数量 int Allocation y y 各进程当前已分配的资源数量 int Max y y 各进程对各类资源的最大需求数 int Need y y 还需求矩阵 int Request x 申请各类资源的数量 int Work x 工作向量 表示系统可提供给进程运行所需各类资源数量 int Finish y 表示系统是否有足够的资源分配给进程 0 为否 1 为是 int p y 存储安全序列 int i j 全局变量 主要用于循环语句中 int n m n 为进程的数量 m 为资源种类数 int l 0 counter 0 3 23 2 函数声明 函数声明 int shuzi int sz 数字判断函数 void chushihua 系统初始化函数 void safe 安全性算法函数 void bank 银行家算法函数 void showdata 函数 showdata 输出当前资源分配情况 void sign 签名函数 此文档收集于网络 如有侵权 请联系网站删除 此文档仅供学习与交流 3 33 3 主函数结构 主函数结构 int main system color 06f 设置当前窗口的背景色和前景色 0 黑色 8 灰色 cout endl endl cout t t endl cout t t endl cout t t 模拟银行家算法 endl cout t t endl cout t t 作者 lxy endl cout t t endl cout t t endl endl endl endl chushihua 初始化函数调用 cout endl endl showdata 输出初始化后的状态 判断当前状态的安全性 safe 安全性算法函数调用 if l n cout n 当前状态不安全 无法申请 程序退出 endl cout endl system pause sign 调用签名函数 return 0 break else int i l 0 cout n 安全的状态 endl cout 安全序列为 cout endl 进程 p 0 输出安全序列 考虑显示格式 先输 出第一个 for i 1 i n i cout 进程 p i for i 0 i n i Finish i 0 所有进程置为未分配状态 cout endl endl bank 银行家算法函数调用 此文档收集于网络 如有侵权 请联系网站删除 此文档仅供学习与交流 return 0 4 算法的实现 算法的实现 4 14 1 初始化 初始化 调用函数 chushihua 输入进程数量 资源种类 各资源可用数量 各进程已分配 最大需求各资源数量等 4 24 2 银行家算法 银行家算法 调用 bank 函数 输入用户的请求三元组 I J K 为进程 I 申请 K 个 J 类资源 4 34 3 安全性检查算法 安全性检查算法 调用函数 safe 检查当前资源分配状态 1 设置两个临时变量 FINISH N 记录进程模拟执行的结束状态 初值为 0 如果可以模拟执行结束 则可 设为 1 也可设为其它非零值以表示执行的先后次序 WORK M 记录模拟执行中资源 的回收情况 初值为 AVAILABLE M 的值 2 在进程中查找符合以下条件的进程 条件 1 FINISH I 0 条件 2 NEED I J WORK J 3 如果查找成功则进行资源的模拟回收 语句如下 WORK J WORK J ALLOCATION I J FINISH I 1 或查找到的顺序号 4 如果查找不成功 则检查所有进程的 FINISH 如果有一个为 0 则系统不为 0 返 回不成功标志 否则返回成功标志 此文档收集于网络 如有侵权 请联系网站删除 此文档仅供学习与交流 4 44 4 程序模块划分 程序模块划分 本程序共有以下六个模块 4 4 1 字符判断模块 判断输入的字符是否为数字 如果不是则提示出错并重新输入 主要处理输入为非数字时程序出现运行错误现象 此模块功能由数字判断函数 int shuzi int sz 实现 4 4 2 程序初始化模块 用于程序开始进行初始化输入数据 进程数量 资源种 类 各种资源可利用数量 各进程的各种资源已分配数量 各进程对各类资源最大需求数 等 此模块功能在系统初始化函数 void chushihua 中实现 4 4 3 当前安全性检查模块 用于判断当前状态安全性 根据不同地方的调用提 示处理不同 在安全性算函数 void safe 中实现 4 4 4 银行家算法模块 进行银行家算法模拟实现的模块 调用其他各个模块进 行银行家算法模拟过程 在银行家算法函数 void bank 中实现 4 4 5 显示分配模块 显示当前资源分配详细情况 包括 各种资源的总数量 all 系统目前各种资源可用的数量 各进程已经得到的资源数量 各进程还需要的资源 量 在显示分配情况函数 void showdata 中实现 4 4 6 签名模块 用于程序结束时显示程序版权声明签名等 在签名函数 void sign 中实现 此文档收集于网络 如有侵权 请联系网站删除 此文档仅供学习与交流 4 54 5 程序运行结果显示程序运行结果显示 4 64 6 各算法流程图 各算法流程图 此文档收集于网络 如有侵权 请联系网站删除 此文档仅供学习与交流 开始开始 清除所有进程清除所有进程 能运行完成能运行完成 的标志的标志 系统剩余资源数与系统剩余资源数与 能运行完能运行完 标志为标志为 0 的进程尚需资源数的进程尚需资源数 比较 找出一个系统能满足要求的进程 比较 找出一个系统能满足要求的进程 对申请者预分配对申请者预分配 找到找到 设置该进程设置该进程 能运行完能运行完 标志标志 并假设它归还全部资源 并假设它归还全部资源 检查是否有检查是否有 能运行能运行 完完 标志尚未设置的进标志尚未设置的进 程 程 有有 分配不安全分配不安全 不能分配不能分配 Y 分配安全分配安全 进行实际分配进行实际分配 N 结束结束 此文档收集于网络 如有侵权 请联系网站删除 此文档仅供学习与交流 4 74 7 源程序清单 源程序清单 include include include include include using namespace std 定义全局变量 const int x 50 y 100 定义常量 便于修改 int Available x 各种资源可利用的数量 int Allocation y y 各进程当前已分配的资源数量 int Max y y 各进程对各类资源的最大需求数 int Need y y 还需求矩阵 int Request x 申请各类资源的数量 int Work x 工作向量 表示系统可提供给进程继续运行所需的各类资源数量 int Finish y 表示系统是否有足够的资源分配给进程 0 为否 非 0 为是 int p y 存储安全序列 int i j int n m n 为进程的数量 m 为资源种类数 int l 0 counter 0 数字判断函数 int shuzi int sz 输入数据并判断是否为数字 char temp temp new char 临时指针 存放输入字符 int len 存储取字符的长度 sz 0 清零 char s do 输入赌注 只能输入数字 cin temp len strlen temp 取字符长度 for int i 0 i len i s temp i if s 9 cout 笨蛋 输错了 你输入的是数字吗 n n cout 请重新输入 break while s 9 此文档收集于网络 如有侵权 请联系网站删除 此文档仅供学习与交流 for int i 0 i len i 输入字符串转化为整形数字 int t 1 for int j 1 j len i j t 10 sz temp i 48 t return sz 系统初始化函数 void chushihua 系统初始化输入 cout 程序开始 系统初始化输入 endl endl cout endl endl cout 请输入进程的数量 从此开始输入有关数据 n shuzi n cout 请输入资源种类数 m shuzi m cout endl endl 请输入各种资源可利用的数量 m 种 endl cout endl for j 0 j m j cout 输入资源 j 可利用的数量 Available j Available j shuzi Available j Work j Available j 初始化 Work j cout endl cout 请输入各进程当前已分配的资源数量 Allocation n m endl endl for i 0 i n i for j 0 j m j cout 请输入进程 i 当前已分配的资源 j 数量 Allocation i j shuzi Allocation i j cout endl Finish i 0 初始化 Finish i cout endl endl cout 请输入各进程对各类资源的最大需求数 Max n m endl endl 此文档收集于网络 如有侵权 请联系网站删除 此文档仅供学习与交流 for i 0 i n i for j 0 j m j cout 请输入进程 i 对资源 j Allocation i j Need i j Max i j Allocation i j 计算还需求量 else Need i j 0 最大需求量小于已分配量时还需求量为 0 即此类资源已足 够不需再申请 cout endl cout endl 初始化完成 endl 安全性算法函数 void safe l 0 for i 0 i n i if Finish i 0 寻找 Finish i 0 的进程 条件一 counter 0 记数器 算法一 for j 0 j Need i j 可用大于等于需求 counter counter 1 记数 if counter m 算法二 for j 0 j Need i j 可用大于等于需求 else counter 1 break if counter 1 进程的每类资源量都符合条件 Work j Need i j 条件二 p l i 存储安全序列 Finish i 1 标志为可分配 for j 0 j Need i j i 1 从第一个进程开始继续寻找满足条件一二的进程 i for 循环继续寻找 显示分配情况函数 void showdata 函数 showdata 输出当前资源分配情况 int i j 局部变量 int All y 各种资源的总数量 int l2 局部变量 l1 cout endl endl cout 系统当前状态如下 endl endl cout 各种资源的总数量 all endl for j 0 j m j cout 资源 j All j Available j 初始化 先赋值加上可利用量 for i 0 i n i All j Allocation i j 再加上每个进程已分配量计算 J 类资源总量 cout All j if j 1 5 0 cout endl 每行显示五个 cout 系统目前各种资源可用的数为 available endl for j 0 j m j cout 资源 j Available j if j 1 5 0 cout endl 每行最多显示五个 cout 各进程已经得到的资源量 allocation endl l1 0 归零 for i 0 i m 5 i 设计每行最多显示五种资源 此文档收集于网络 如有侵权 请联系网站删除 此文档仅供学习与交流 for j i 5 j i 5 5 j cout 资源 j cout endl for l2 0 l2 n l2 cout 进程 l2 for j i 5 j i 5 5 j cout Allocation l2 j cout endl cout endl cout 各进程还需要的资源量 need endl l1 0 for i 0 i m 5 i 设计每行显示五种资源 for j i 5 j i 5 5 j cout 资源 j cout endl for l2 0 l2 n l2 cout 进程 l2 for j i 5 j i 5 5 j cout Need l2 j cout endl cout endl cout endl cout endl system pause 暂停 签名函数 void sign system cls 清屏 cout endl endl endl endl endl endl cout t t endl cout t t endl cout t t 本程序由刘新宇制作 endl cout t t 谢谢你的使用 endl cout t t 版权没有 随便复制 endl cout t t endl cout t t 衡阳师院 12 5 endl cout t t endl 此文档收集于网络 如有侵权 请联系网站删除 此文档仅供学习与交流 cout t t endl cout endl endl endl endl endl endl endl endl endl getch 等待键盘输入 不返回任何值 用于设置程序运行界面 system pause 暂停 比较两种方式 经过在不同的编辑器中调试发现 不同的调试器对函数执行的顺序有差别 如在此处使用 getch 和 system pause 函数时 在 visual c 6 0 中先执行此函数再 显示 而在 dev c 中则按顺序执行 对此问题我在很多地方搜索查找均未找到满意的答案 本次换用调试器才发现理解 4 29 本次调试格式时 将换行命令 n 改为 endl 时 发现 system pause 函数执行变 为顺序 执行 由此领悟到 n 命令和 system pause 调用了一样系统函数 在调用的顺序上 system pause 优先所以它就先执行了 查找了一下相关帮助 在 OSTREAM H 中有这样的一个 inline 函数 inline CRTIMP ostream 也就是说 endl return outs n flush endl 除了写 n 进外 还调用 flush 函数 刷新缓冲区 把缓冲区里的数据写入文件或 屏幕 如果考虑效率就用 n cout t t t 银行家算法函数 void bank cout endl endl cout 以下开始为进程进行资源分配申请 endl endl 申请资源 int k 0 用于输入进程编号 bool r false 初值为假 输入 Y 继续申请则置为真 do 输入请求 cout 请输入申请资源的进程编号 输入 0 n 1 之间 k shuzi k cout n 1 输入异常处理 cout endl 您输入了错误的进程号 请重新输入 endl 此文档收集于网络 如有侵权 请联系网站删除 此文档仅供学习与交流 cout endl 请输入申请资源的进程编号 输入 0 n 1 之间 k shuzi k cout endl cout endl 请输入该进程申请各类资源的数量 endl for j 0 j m j do do while 循环判断申请输入的情况 cout 进程 k 申请资源 j 的数量 Request j shuzi Request j cout Need k j 申请大于需求量时出错 提示重新输入 贷 款数目不允许超过需求数目 cout 申请大于需要量 endl cout 您申请资源 j 的数量为 Request j 大于进程 k 对该资源需求量 Need k j endl cout 请重新输入 Available j 申请大于可利用量 应该阻塞等待 cout n 没有那么多资源 目前可利用资源 j 数量为 Available j 本次申请不成功 进程等待 Need k j Request j Available j 改变 Avilable Allocation Need 的值 for j 0 j m j Available j Available j Request j Allocation k j Allocation k j Request j Need k j Need k j Request j Work j Available j 判断当前状态的安全性 safe 调用安全性算法函数 if l n l 0 此文档收集于网络 如有侵权 请联系网站删除 此文档仅供学习与交流 cout n 当前状态不安全 不予分配 endl 恢复数据 for j 0 j m j Available j Available j Request j Allocation k j Allocation k j Request j Need k j Need k j Request j Work j Available j for i 0 i n i Finish i 0 进程置为未分配状态 else l 0 cout n 申请资源成功 endl 如果该进程所有需要的资源都已申请到 即 NEED k j 均为零 则进程可 以执行 执行完后需释放其所有拥有的资源 算法一 for j 0 j m j if Need k j 0 l l 1 if l m 此处借用 l 做下计数器 for j 0 j m j 释放该进程的所有资源 Available j Available j Max k j Allocation k j 0 l 0 归零 算法二 相对第一种算法节省时间 for j 0 j m j if Need k j 0 else 有一种资源还没全部申请到 则该进程不可执行 不能释放拥 有的资源 l 1 置 l 为 1 作为判断标志 break if l 1 进程可以执行 则释放该进程的所有资源 for j 0 j m j 此文档收集于网络 如有侵权 请联系网站删除 此文档仅供学习与交流 Available j Available j Allocation k j Allocation k j 0 cout 该进程已得到所有需求资源 执行后将释放其所有拥有资源 endl l 0 归零 cout n 安全的状态 endl cout 安全序列为 cout endl 进程 p 0 输出安全序列 考虑显示格式 先输 出第一个 Finish 0 0 for i 1 i n i cout 进程 p i Finish i 0 所有进程置为未分配状态 cout endl endl showdata 显示当前状态 ppp 申请大于可利用量 应该阻塞等待 结束本次资源申请 GOTO 语句跳转 至此 cout endl 是否继续申请资源 y n char b new char 输入 y n 判断是否继续申请 b cout endl cout endl endl cout endl if b y b Y r true else r false 输入非 Y 则令 R false sign 调用签名函数 while r true int main 此文档收集于网络 如有侵权 请联系网站删除 此文档仅供学习与交流 system color 06f 设置当前窗口的背景色和前景色 0 黑色 8 灰色 cout endl endl cout t t endl cout t t endl cout t t 模拟银行家算法 endl cout t t endl cout t t 作者 lxy endl cout t t endl cout t t endl endl e ndl endl chushi