6.磁盘调度实验报告.doc

1 1操作系统课程设计 磁盘调度算法 操作系统实验报告操作系统实验报告 磁磁 盘盘 调调 度度 实验六 磁盘调度算法实验六 磁盘调度算法 一 实验目的一 实验目的 复习模拟实现一种磁盘调度算法 进一步加深对磁盘调度效率的理解 二 实验属性二 实验属性 该实验为设计性实验 三 实验仪器设备及器材三 实验仪器设备及器材 普通 PC386 以上微机 2 2操作系统课程设计 磁盘调度算法 四 实验要求四 实验要求 本实验要求 2 学时完成 本实验要求完成如下任务 1 建立相关的数据结构 作业控制块 已分配分区及未分配分区 2 实现一个分区分配算法 如最先适应分配算法 最优或最坏适应分配算法 3 实现一个分区回收算法 4 给定一批作业 进程 选择一个分配或回收算法 实现分区存储的模拟管理 实验前应复习实验中所涉及的理论知识和算法 针对实验要求完成基本代码编写并完 成预习报告 实验中认真调试所编代码并进行必要的测试 记录并分析实验结果 实验后 认真书写符合规范格式的实验报告 参见附录 A 并要求用正规的实验报告纸和封面装订 整齐 按时上交 五五 主要算法分析主要算法分析 各个算法分析各个算法分析 1 先来先服务算法 先来先服务算法 FCFS 先来先服务 FCFS 调度 按先来后到次序服务 未作优化 最简单的移臂调度算法是 先来先服务 调度算法 这个算法实际上不考虑访问者要求 访问的物理位置 而只是考虑访问者提出访问请求的先后次序 例如 如果现在读写磁头 正在 50 号柱面上执行输出操作 而等待访问者依次要访问的柱面为 130 199 32 159 15 148 61 99 那么 当 50 号柱面上的操作结束后 移动臂 将按请求的先后次序先移到 130 号柱面 最后到达 99 号柱面 采用先来先服务算法决定等待访问者执行输入输出操作的次序时 移动臂来回地移动 先来先服务算法花费的寻找时间较长 所以执行输入输出操作的总时间也很长 2 最短寻道时间优先算法 最短寻道时间优先算法 SSTF 最短寻找时间优先调度算法总是从等待访问者中挑选寻找时间最短的那个请求先执行 的 而不管访问者到来的先后次序 现在仍利用同一个例子来讨论 现在当 50 号柱面的 操作结束后 应该先处理 61 号柱面的请求 然后到达 32 号柱面执行操作 随后处理 15 号柱面请求 后继操作的次序应该是 99 130 148 159 199 采用最短寻找时间优先算法决定等待访问者执行操作的次序时 读写磁头总共移动了 200 多个柱面的距离 与先来先服务 算法比较 大幅度地减少了寻找时间 因而缩短了 为各访问者请求服务的平均时间 也就提高了系统效率 但最短查找时间优先 SSTF 调度 FCFS 会引起读写头在盘面上的大范围移动 SSTF 查找距离磁头最短 也就是查找时间最短 的请求作为下一次服务的对象 SSTF 查找模 式有高度局部化的倾向 会推迟一些请求的服务 甚至引起无限拖延 又称饥饿 3 扫描算法 扫描算法 SCAN SCAN 算法又称电梯调度算法 SCAN 算法是磁头前进方向上的最短查找时间优先算 法 它排除了磁头在盘面局部位置上的往复移动 SCAN 算法在很大程度上消除了 SSTF 算法的不公平性 但仍有利于对中间磁道的请求 电梯调度 算法是从移动臂当前位置开始沿着臂的移动方向去选择离当前移动臂最近 的那个柱访问者 如果沿臂的移动方向无请求访问时 就改变臂的移动方向再选择 这好 比乘电梯 如果电梯已向上运动到 4 层时 依次有 3 位乘客陈生 伍生 张生在等候乘电 梯 他们的要求是 陈生在 2 层等待去 10 层 伍生在 5 层等待去底层 张生在 8 层等待 15 层 由于电梯目前运动方向是向上 所以电梯的形成是先把乘客张生从 8 层带到 15 层 3 3操作系统课程设计 磁盘调度算法 然后电梯换成下行方向 把乘客伍生从 5 层带到底层 电梯最后再调换方向 把乘客陈生 从 2 层送到 10 层 但是 电梯调度 算法在实现时 不仅要记住读写磁头的当前位置 还必须记住移动臂 的当前前进方向 六 程序代码六 程序代码 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 当前的磁道号的值在若所有被访问的下的磁道号之间 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 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 5 5操作系统课程设计 磁盘调度算法 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 6 6操作系统课程设计 磁盘调度算法 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 输出平均寻道长度 void main int i m n flag 1 array 100 cout m cout 分别输入磁盘调度序列 for i 0 i array i do cout 0 终止 endl cout 1 先来先服务算法 FCFS endl cout 2 最短寻道时间优先算法 SSTF endl cout 3 最短寻道时间优先算法 SCAN endl cout n switch n case 0 flag 0 break 终止程序 7 7操作系统课程设计 磁盘调度算法 case 1 FCFS array m break 先来先服务算法 FCFS case 2 SSTF array m break 最短寻道时间优先算法 SSTF case 3 SCAN array m break 最短寻道时间优先算法 SCAN default cout 输入有误 请重新输入 endl while flag 0 七 各算法的流程图七 各算法的流程图 1 先来先服务算法流程图先来先服务算法流程图 输入当前磁道号 now 磁头移动距离 sum abs now array 0 磁头移动总距离 Sum abs array j array i 输出磁盘调度序列 array j 目前的位置变为当前 的位置 j j m 输出平均寻道长度 avg sum m 2 最短寻道时间优先算法流程图最短寻道时间优先算法流程图 8 8操作系统课程设计 磁盘调度算法 3 扫描算法流程图扫描算法流程图 将磁道号从小到大排序 输入当前磁道号 now array m 1 0 输出磁盘调度 序列 array j array 0 now 磁头移动总距离 sum now array i 目前的位置变为 当前的位置 now array i now array i i m 确定当前磁道在已 排的序列中的位置 now array l arra y r now 先向磁道号 减小方向访 问 再向磁 道号增加方 向访问 输出磁盘 调度序列 先向磁道号 增加方向访 问 再向磁 道号减小方 向访问 输出磁盘 调度序列 输出平均寻道长度 avg sum m 9 9操作系统课程设计 磁盘调度算法 将磁道号从小到大排序 输入当前磁道号 now 移动臂的移动的方向 array m 1 0 array 0 now 输出磁盘调度 序列 array j i m 磁头移动总距离 sum array i now 确定当前磁道在已 排的序列中的位置 switch d case 0 移动臂 向磁道号减小 方向访问 case 1 移动臂 向磁道号增加 方向访问 访问 输出磁盘 调度序列 输出磁盘 调度序列 输出平均寻道长度 avg sum m 八 课程设计运行结果八 课程设计运行结果 一一 运行后的开始界面如下 运行后的开始界面如下 二 运行各个算法结果如下二 运行各个算法结果如下 1 运行先来先服务 FCFS 算法调度后程序结果如下 2 运行最短寻道时间优先 SSTF 算法调度程序结果如下 11 11操作系统课程设计 磁盘调度算法 3 运行扫描 SCAN 算法调度程序结果如下 5 选择退出后程序界面如下 九 心得体会九 心得体会 整个设计中最麻烦的就是整个程序模块的划分和各模块之间接口设计 编程中经常犯 想当然的错误 编程中出现了不少奇怪的错误 再调试中尝试使用了分割法 对错误模块进 行定位 再进行排查 通过这次的课程设计使我认识到要将操作系统这门计算机专业的课学 好不仅仅是要把书上的基本知识学好而且还要不断进行实践 将所学的跟实践操作结合起 来才能更好地巩固所学 才能提高自己实践