操作系统课程设计报告-磁盘调度算法的模拟实现.doc

淮阴工学院 操作系统课程设计报告操作系统课程设计报告 选题名称选题名称 磁盘调度算法的模拟实现 系 院 系 院 经济管理学院 专专 业业 信息管理与信息系统 班班 级级 姓名姓名 学学 号号 指导教师指导教师 学年学期学年学期 2014 2015 学年 第 1 学期 2014年 12 月 21 日 操作系统课程设计报告 磁盘调度算法的模拟实现 设计任务书设计任务书 课题课题 名称名称 磁盘调度算法的模拟实现 设计设计 目的目的 1 调研并熟悉磁盘调度的基本概念 排序算法与工作规程 2 学习 Visual C 中的图形化界面设计技术 3 通过实际编程加深对基础知识的理解 提高实践能力 4 学习开发资料的收集与整理 学会撰写课程设计报告 实验实验 环境环境 1 微型电子计算机 PC 2 安装 Windows 2000 以上操作系统 Visual C 6 0 开发工具 任务任务 要求要求 1 利用课余时间去图书馆或上网查阅课题相关资料 深入理解课题含义及设计要求 注意材料收集与整理 2 在第 15 周末之前完成预设计 并请指导教师审查 通过后方可进行下一步工作 3 本课题主要实现能用各种排序算法实现对数据的排序 排序后显示排序结果 4 结束后 及时提交设计报告 含纸质稿 电子稿 要求格式规范 内容完整 结 论正确 正文字数不少于 3000 字 不含代码 工作进度计划工作进度计划 序号序号起止日期起止日期工工 作作 内内 容容 12014 12 15 2014 12 16 在预设计的基础上 进一步查阅资料 完善设计方案 形 成书面材料 22014 12 17 2014 12 18 设计总体方案 构建 绘制流程框图 编写代码 上机调 试 32014 12 18 2014 12 19测试程序 优化代码 增强功能 撰写设计报告 42014 12 20 2014 12 21 提交软件代码 设计报告 参加答辩 根据教师反馈意见 修改 完善设计报告 指导教师 签章 指导教师 签章 年月日年月日 操作系统课程设计报告 磁盘调度算法的模拟实现 摘要 磁盘是外设中一个很常用的部分 所以 对磁盘数据的寻道时间的长短可以直 接影响机器的整体运行速度的快慢 本设计为一个模拟磁盘调度算法的磁盘调 度模拟系统 能够模拟先来先服务 FCFS 算法 最短寻道时间 SSTF 算法 电梯 SCAN 算法 环形扫描 C SCAN 算法及 N SCAN 算法五个磁盘调度算法 输入为一组作业的磁道请求 输出为按选择的算法执行时的磁头移动轨迹 其 中 先来先服务 FCFS 算法 最短寻道时间 SSTF 算法 电梯 SCAN 算 法为基本算法 环形扫描 C SCAN 算法及 N SCAN 算法为扩展算法 关键字 磁盘调度 模拟 算法 选择 执行 操作系统课程设计报告 磁盘调度算法的模拟实现 目录目录 1 磁盘调度算法的基本概念磁盘调度算法的基本概念 1 2 主要算法分析主要算法分析 2 2 1 先来先服务算法 FCFS 2 2 2 最短寻道时间优先算法 SSTF 2 2 3 扫描算法 SCAN 2 3 各算法的流程图各算法的流程图 3 4调试分析及测试结果调试分析及测试结果 5 4 1 运行结果 5 4 2 程序代码 7 总结总结 12 致谢致谢 13 参考文献参考文献 14 操作系统课程设计报告 磁盘调度算法的模拟实现 1 1 1 磁盘调度算法的基本概念磁盘调度算法的基本概念 设备的动态分配算法与进程调度相似 也是基于一定的分配策略的 常用 的分配策略有先请求先分配 优先级高者先分配等策略 在多道程序系统中 低效率通常是由于磁盘类旋转设备使用不当造成的 操作系统中 对磁盘的访 问要求来自多方面 常常需要排队 这时 对众多的访问要求按一定的次序响 应 会直接影响磁盘的工作效率 进而影响系统的性能 访问磁盘的时间因子 由 3 部分构成 它们是查找 查找磁道 时间 等待 旋转等待扇区 时间和 数据传输时间 其中查找时间是决定因素 因此 磁盘调度算法先考虑优化查 找策略 需要时再优化旋转等待策略 平均寻道长度 L 为所有磁道所需移动距离之和除以总的所需访问的磁道 数 N 即 L M1 M2 Mi MN N 其中 Mi 为所需访问的磁道号所需移动的磁道数 启动磁盘执行输入输出操作时 要把移动臂移动到指定的柱面 再等待指 定扇区的旋转到磁头位置下 然后让指定的磁头进行读写 完成信息传送 因 此 执行一次输入输出所花的时间有 寻找时间 磁头在移动臂带动下移动到指定柱面所花的时间 延迟时间 指定扇区旋转到磁头下所需的时间 传送时间 由磁头进程读写完成信息传送的时间 其中传送信息所花的时间 是在硬件设计就固定的 而寻找时间和延迟时 间是与信息在磁盘上的位置有关 为了减少移动臂进行移动花费的时间 每个 文件的信息不是按盘面上的磁道顺序存放满一个盘面后 再放到下一个盘面上 而是按柱面存放 同一柱面上的各磁道被放满信息后 再放到下一个柱面上 所以各磁盘的编号按柱面顺序 每个柱面按磁道顺序 每个磁道又按扇区顺序 进行排序 磁盘是可供多个进程共享的设备 当有多个进程都要求访问磁盘是 应采 用一种最佳调度算法 以使各种进程对磁盘的平均访问时间最小 由于在访问 磁盘的时间中 主要是寻道时间 因此 磁盘调度的目标 是使磁盘的平均寻 道时间最少 目前常用的磁盘帝调度算法有 先来先服务 最短寻道时间优先 操作系统课程设计报告 磁盘调度算法的模拟实现 2 及扫描等算法 操作系统课程设计报告 磁盘调度算法的模拟实现 3 2 2 主要算法分析主要算法分析 2 1 先来先服务算法 先来先服务算法 FCFS 先来先服务 FCFS 调度 按先来后到次序服务 未作优化 最简单的移臂调度算法是 先来先服务 调度算法 这个算法实际上不考 虑访问者要求访问的物理位置 而只是考虑访问者提出访问请求的先后次序 例如 如果现在读写磁头正在 50 号柱面上执行输出操作 而等待访问者依次要 访问的柱面为 130 199 32 159 15 148 61 99 那么 当 50 号柱面上 的操作结束后 移动臂将按请求的先后次序先移到 130 号柱面 最后到达 99 号 柱面 采用先来先服务算法决定等待访问者执行输入输出操作的次序时 移动臂 来回地移动 先来先服务算法花费的寻找时间较长 所以执行输入输出操作的 总时间也很长 2 2 最短寻道时间优先算法 最短寻道时间优先算法 SSTF 最短寻找时间优先调度算法总是从等待访问者中挑选寻找时间最短的那个 请求先执行的 而不管访问者到来的先后次序 现在仍利用同一个例子来讨论 现在当 50 号柱面的操作结束后 应该先处理 61 号柱面的请求 然后到达 32 号 柱面执行操作 随后处理 15 号柱面请求 后继操作的次序应该是 99 130 148 159 199 采用最短寻找时间优先算法决定等待访问者执行操作的次序时 读写磁头 总共移动了 200 多个柱面的距离 与先来先服务 算法比较 大幅度地减少了 寻找时间 因而缩短了为各访问者请求服务的平均时间 也就提高了系统效率 但最短查找时间优先 SSTF 调度 FCFS 会引起读写头在盘面上的大范围 移动 SSTF 查找距离磁头最短 也就是查找时间最短 的请求作为下一次服务 的对象 SSTF 查找模式有高度局部化的倾向 会推迟一些请求的服务 甚至引 起无限拖延 又称饥饿 2 3 扫描算法 扫描算法 SCAN 操作系统课程设计报告 磁盘调度算法的模拟实现 4 SCAN 算法又称电梯调度算法 SCAN 算法是磁头前进方向上的最短查找时 间优先算法 它排除了磁头在盘面局部位置上的往复移动 SCAN 算法在很大程 度上消除了 SSTF 算法的不公平性 但仍有利于对中间磁道的请求 电梯调度 算法是从移动臂当前位置开始沿着臂的移动方向去选择离当 前移动臂最近的那个柱访问者 如果沿臂的移动方向无请求访问时 就改变臂 的移动方向再选择 这好比乘电梯 如果电梯已向上运动到 4 层时 依次有 3 位乘客陈生 伍生 张生在等候乘电梯 他们的要求是 陈生在 2 层等待去 10 层 伍生在 5 层等待去底层 张生在 8 层等待 15 层 由于电梯目前运动方向是 向上 所以电梯的形成是先把乘客张生从 8 层带到 15 层 然后电梯换成下行方 向 把乘客伍生从 5 层带到底层 电梯最后再调换方向 把乘客陈生从 2 层送 到 10 层 但是 电梯调度 算法在实现时 不仅要记住读写磁头的当前位置 还必 须记住移动臂的当前前进方向 3 3 各算法的流程图各算法的流程图 1 先来先服务算法模块 操作系统课程设计报告 磁盘调度算法的模拟实现 5 图 3 1 先来先服务算法流程图 2 最短寻道时间优先算法模块 开始 操作系统课程设计报告 磁盘调度算法的模拟实现 6 图 3 2 最短寻道时间优先算法流程图 3 扫描算法模块 结束 开始 操作系统课程设计报告 磁盘调度算法的模拟实现 7 图 3 3 扫描算法流程图 4 4 调试分析及测试结果调试分析及测试结果 4 1 运行结果运行结果 1 开始界面 结束 输出磁盘 调度序列 操作系统课程设计报告 磁盘调度算法的模拟实现 8 图 4 1 开始界面 2 运行先来先服务 FCFS 算法调度后程序结果如下 图 4 2 FCFS 运行结果 3 运行最短寻道时间优先 SSTF 算法调度程序结果如下 图 4 3 SSTF 运行结果 操作系统课程设计报告 磁盘调度算法的模拟实现 9 4 运行扫描 SCAN 算法调度程序结果如下 图 4 4 SCAN 向磁道号增加方向移动 图 4 5 SCAN 向磁道号减小放向移动 4 2 程序代码程序代码 1 先来先服务算法 void FCFS int array int m 先来先服务算法 int j i now float sum 0 avg cout now sum abs now array 0 cout 先来先服务算法 FCFS 调度后的序列为 array 0 输出磁盘调度序列 for i 0 j 1 j m i j sum sum abs array j array i cout array j 输出磁盘调度序列 操作系统课程设计报告 磁盘调度算法的模拟实现 10 avg sum m cout endl 平均寻道长度 avg endl 输出平均寻道长度 2 最短寻道时间优先算法 void SSTF int array int m 最短寻道时间优先算法 int temp int k 1 int now l r int i j float sum 0 avg 0 for i 0 i m i for j i 1 jarray j 将磁道号从小到大排序 temp array i array i array j array j temp cout now cout 最短寻道时间优先算法 SSTF 调度后的序列为 输出磁盘调度序列 if array m 1 0 i cout array i now 若被访问的下一最小的磁道号不小于当前的磁道号 for i 0 i m i cout array i 输出磁盘调度序列 sum array i now now array i else 当前的磁道号的值在若所有被访问的下的磁道号之间 操作系统课程设计报告 磁盘调度算法的模拟实现 11 while array k now 确定当前磁道在已排的序列中的位置 k l k 1 r k if now array l 0 先向磁道号减小方向访问 cout array l 输出磁盘调度序列 sum sum now array l now array l l l 1 now array 0 for j r j m j 再向磁道号增加方向访问 cout array j 输出磁盘调度序列 sum array j now now array j else 先向磁道号增加方向访问 while r m cout array r 0 j 再向磁道号减小方向访问 cout array j 输出磁盘调度序列 sum now array j now array j avg sum m cout endl 平均寻道长度 avg endl 输出平均寻道长度 3 扫描算法 void SCAN int array int m 扫描算法 操作系统课程设计报告 磁盘调度算法的模拟实现 12 int temp int k 1 int now d l r int i j float sum 0 avg 0 for i 0 i m i for j i 1 jarray j 将磁道号从小到大排序 temp array i array i array j array j temp cout now cout d 先要给出当前磁道号和移动臂的移动方向 cout 扫描算法 SCAN 调度后的序列为 if array m 1 0 i cout array i now 若被访问的下一最小的磁道号不小于当前的磁道号 for i 0 i m i cout array i 输出磁盘调度序列 sum array i now now array i else 当前的磁道号的值在若所有被访问的下的磁道号之间 while array k 0 cout array l 输出磁盘调度序列 sum sum now array l now array l l l 1 now array 0 for j r j m j cout array j 输出磁盘调度序列 sum array j now now array j break case 1 先向磁道号增加方向访问 while r m cout array r 0 j cout array j 输出磁盘调度序列 sum now array j now array j break default cout 输入有误 endl avg sum m cout endl 平均寻道长度 avg endl 输出平均寻道长度 操作系统课程设计报告 磁盘调度算法的模拟实现 14 总总 结结 通过这次的课程设计使我认识到要将操作系统这门计算机专业的课学好不 仅仅是要把书上的基本知识学好而且还要不断进行实践 将所学的跟实践操作 结合起来才能更好地巩固所学 才能提高自己实践能力 通过这次的设计使我 认识到只停留在表面理解问题是很难使问题得到很好的解决的 实践能力与理 论知识同样重要 可以说此课程设计的理论难度并不大 各种流图设计特别是 算法过程图的设计很容易忽略操作性细节 在实际调试中带来很大麻烦 需要 特别注意 但是若要深入发掘其中的东西 并且实际去编程实现 就遇到了相 当大的难度 因为与之涉及的很多方面并没有学过 需要自己去自学和实践检 验 通过模拟磁盘调度及进程排队算法来加深对操作系统中各个磁臂调度算法 概念的理解模拟磁盘调度算法 实现各种不同调度算法的过程 并计算各算法 的平均寻道长度 以便于我们判断各种算法的优劣以及各种算法使用的场合 操作系统课程设计报告 磁盘调度算法的模拟实现 15 致致 谢谢 这次课程设计让我受益匪浅 我不仅加深了对操作系统的了解 进一步熟 悉了 C 语言编程和 Microsoft Visual C 6 0 的使用 更加了解了很多之前在课 本中和课程学习中并不了解和知道的知识 扩展了视野 丰富了体验 非常感谢在课程设计中殷路和高尚兵两位老师不厌其烦的讲解指导 同时 我还要感谢同学们的热心帮助 操作系统课程设计报告 磁盘调度算法的模拟实现 16 参考文献参考文献 1 汤子瀛 哲凤屏 汤小丹 计算机操作系统 西安电子科技大学出版社 2005 2 周敏 杨武 杨承玉 计算机操作系统原理实验指导基于 LINUX Ver 3 0 重庆工学院 2006 3 谭浩强编著 C 语言程序设计 第 3 版 清华大学出版社 2005 4 周湘贞 曾宪权 操作系统原理与实践教程 清华出版社 5 陈家骏 程序设计基础教程 机械工业出版社 操作系统课程设计报告 磁盘调度算法的模拟实现 17 附录 include include include void FCFS int array int m 先来先服务算法 int j i now float sum 0 avg cout now sum abs now array 0 cout 先来先服务算法 FCFS 调度后的序列为 array 0 输出磁盘调度序列 for i 0 j 1 j m i j sum sum abs array j array i cout array j 输出磁盘调度序列 avg sum m cout endl 平均寻道长度 avg endl 输出平均寻道长度 void SSTF int array int m 最短寻道时间优先算法 int temp int k 1 int now l r int i j float sum 0 avg 0 for i 0 i m i for j i 1 jarray j 将磁道号从小到大排序 temp array i array i array j array j temp cout now cout 最短寻道时间优先算法 SSTF 调度后的序列为 输出磁盘调度序列 if array m 1 0 i cout array i now 若被访问的下一最小的磁道号不小于当前的磁道号 for i 0 i m i cout array i 输出磁盘调度序列 sum array i now now array i else 当前的磁道号的值在若所有被访问的下的磁道号之间 操作系统课程设计报告 磁盘调度算法的模拟实现 19 while array k now 确定当前磁道在已排的序列中的位置 k l k 1 r k if now array l 0 先向磁道号减小方向访问 cout array l 输出磁盘调度序列 sum sum now array l now array l l l 1 now array 0 for j r j m j 再向磁道号增加方向访问 cout array j 输出磁盘调度序列 sum array j now now array j else 先向磁道号增加方向访问 while r m cout array r 0 j 再向磁道号减小方向访问 cout array j 输出磁盘调度序列 sum now array j now array j avg sum m cout endl 平均寻道长度 avg endl 输出平均寻道长度 void SCAN int array int m 扫描算法 int temp int k 1 int now d l r int i j float sum 0 avg 0 for i 0 i m i for j i 1 jarray j 将磁道号从小到大排序 temp array i array i array j array j temp cout now cout d 先要给出当前磁道号和移动臂的移动方向 cout 扫描算法 SCAN 调度后的序列为 if array m 1 0 i cout array i now 若被访问的下一最小的磁道号不小于当前的磁