操作系统磁盘调度算法实验报告

目录目录 一 课程设计目的一 课程设计目的 3 二 课程设计要求二 课程设计要求 3 三 课程设计原理三 课程设计原理 3 四 程序代码四 程序代码 5 五五 流程图设计 流程图设计 11 六 六 运行运行结果结果 14 七 调试分析七 调试分析 16 八 八 心得体会心得体会 16 一 课程设计目的一 课程设计目的 操作系统是最重要的计算机系统软件 同时也是最活跃的学科之一 发展 极为迅速 我们在本课程的实验过程中 要了解实际操作系统的工作过程 加 深对操作系统基础理论和重要算法的理解 在实践过程中加深对操作系统原理 的理解 通过设计一个磁盘调度模拟系统 以加深对先来先服务 最短寻道时间 电梯算法以及循环扫描算法等磁盘调度算法的理解 让我们更好地掌握操作系 统中磁盘调度的原理及实现方法 增强动手能力 本实验通过对磁盘调度算法的实现 加深对算法的理解 同时通过用 C 语言编写程序实现这些算法 并在 windows 平台上实现 也再一次提高了自己 编程的能力 提高了综合运用专业课知识的能力 二 课程设计要求二 课程设计要求 本设计的具体要求如下 1 模拟一个磁盘调度算法 2 要求能够模拟 FCFS 最短寻道时间 电梯算法等磁盘调度算法 3 输入为一组作业的磁道请求 4 输出为按选择的算法执行时的磁头移动轨迹 三 课程设计原理三 课程设计原理 1 1 各个算法分析各个算法分析 1 先来先服务算法 FCFS 这是一种最简单的磁盘调度算法 它根据请求访问磁盘的先后次序进行调 度 此算法的优点是公平 简单 且每个进程的请求都能依次地得到处理 不 会出现某一进程的请求长期得不到满足的情况 但是此算法由于未对寻道进行 优化 致使平均寻道时间可能较长 当有进程先后提出磁盘 I O 请求时 先按 他们发出请求的先后次序排队 然后依次给予服务 其平均寻道距离较大 故 先来先服务算法仅适用于请求磁盘 I O 进程数目较少的场合 2 最短寻道时间优先算法 SSTF 该算法选择这样的进程 其要求访问的磁道与当前磁头所在的磁道距离最 近 以使每次寻道时间最短 但这种算法不能保证平均寻道时间最短 有可能 导致某个进程出现 饥饿 现象 因为只要不断有新进程请求到达 且其所要 访问的磁道与磁头当前所在的磁道的距离较近 这种新进程的 I O 请求必然优 先满足 3 扫描算法 SCAN 该算法不仅考虑到正欲访问的磁道与当前磁道间的距离 更优先考虑的是 磁头当前的移动方向 例如 当磁头正在自里向外移动时 SCAN 算法所考虑 的下一个访问对象应该是其欲访问的磁道之外 又是距离最近的 这样自里向 外地访问 直至再无更外的磁道需要访问时 才将磁臂换向为自外向里移动 这时 同样也是每次选择这样的进程来调度 既要访问的磁道在当前位置内距 离最近者 这样 磁头又逐步地从外向里移动 直至再无更里面的磁道要访问 从而避免了出现 饥饿 现象 由于在这种算法中磁头移动的规律颇似电梯的 运行 因而又常称之为电梯调度算法 4 循环扫描算法 CSCAN SCAN 算法规定磁头单向移动 例如 只是自里向外移动 当磁头移动到 最外的磁道并访问后 磁头立即返回到最里的欲访问的磁道 亦即将最小磁道 号紧接着最大的磁道号构成循环 进行循环扫描 2 2 磁盘调度思想磁盘调度思想 磁盘设备在工作时以恒定的速率旋转 为了读或写 磁头必须能移动到所 要求的磁道上 并等待所要求的扇区开始位置旋转到磁头下 然后或开始读或 写数据 故可把磁盘访问时间分成以下三部分 1 寻道时间 Ts 这是把磁头移动到指定磁道上所经历的时间 该时间是启动磁臂的时间 s 与磁头移动 n 条磁道所花费的时间之和 即 Ts m n s 其中 m 是一常数 与磁盘驱动器的速度有关 对于一般磁盘 m 0 2 对于高速磁盘 m 0 1 磁臂的启动时间 约为 2ms 这样 对于一般的温盘 对于一般的温盘 其寻道时间将随着寻道距离的增加而增大 大体上是 5 30ms 2 旋转延迟时间 Tr 这是指定扇区移动到磁头下面所经历的时间 不同的磁盘类型中 旋转速 度至少相差一个数量级 如软盘为 300r min 硬盘一般为 7200 15000r min 甚 至更高 对于磁盘旋转延迟时间而言 如硬盘 旋转速度为 15000r min 每转 需时 4ms 平均旋转延迟时间 Tr 为 2ms 而软盘 其旋转速度为 300r min 或 600r min 这样 平均 Tr 为 50 100ms 3 传输时间 Tt 这时指把数据从磁盘读出或向磁盘写入数据所经历的时间 Tt 的大小与每 次所读 写的字节数 b 和旋转速度有关 Tt b r N 其中 r 为磁盘每秒钟的转数 N 为一条磁道上的字节数 当一次读 写的字节 数相当于半条磁道上的字节数时 T3 与 T2 相同 因此 可将访问时间 Ta 表示 为 Ta Ts 1 2 r b r N 由上式可以看出 在访问时间中 寻道时间和旋转延迟时间基本上都与所读 写 数据的多少无关 而且它通常占据了访问时间中的大头 磁盘是可供多个进程共享的设备 当有多个进程都要求访问磁盘时 应采 用一种最佳调度算法 以使各进程对磁盘的平均访问时间最小 由于在访问磁 盘的时间中 主要是寻道时间 因此 磁盘调度的目标是使磁盘的平均寻道时 间最少 现在我们考虑平均寻道长度 所有磁道所需移动距离之和除以总的所 需访问的磁道数 所以寻道长度决定了寻道时间 我们需要从上面的算法中选 择最优者 四 程序代码四 程序代码 下面给出部分重要的程序 先来先服务调度算法 void FCFS int cidao int m 磁道号数组 磁道数为 m int now 当前所在磁道号 int sum 0 总寻道长度 int i int j int a char str max float ave 平均寻道长度 cout 磁盘请求序列为 for i 0 i m i 按先来先服务策略输出磁盘请求序列 cout cidao i cout endl cout str 判断输入的数据是不是正确 a panduan str if a 0 cout 数据类型错误 请重新输入 endl goto BB else now zhuanhuan str a 当前磁道号 sum abs cidao 0 now cout 磁盘扫描序列为 for i 0 i m i 输出磁盘扫描序列 cout cidao i for i 0 j 1 j m i j 求总寻道长度和平均寻道长度 sum abs cidao j cidao i ave float sum float m cout endl cout 平均寻道长度 ave endl 最短寻道时间优先调度算法 void SSTF int cidao int m int k 1 int now l r int i j sum 0 int a char str max float ave cidao paixu cidao m 调用排序算法排序 cout str 判断输入的数据是不是正确 a panduan str if a 0 cout 数据类型错误 请重新输入 endl goto CC else now zhuanhuan str a 输入当前磁道号 if cidao m 1 now 若当前磁道号大于请求序列中最大者 则直接由外向 内依次给予各请求服务 cout 0 i cout cidao i now 若当前磁道号小于请求序列中最小者 则直接由内向外 依次给予各请求服务 cout 磁盘扫描序列为 for i 0 i m i cout cidao i cidao 0 while cidao k 0 sum now cidao l now cidao l l l 1 else cout cidao r sum cidao r now now cidao r r r 1 if l 1 说明磁头已移动到序列的最小号 现返回外侧扫描仍未扫描的 磁道 for j r j m j cout cidao j 0 j cout cidao j sum cidao m 1 cidao 0 ave float sum float m cout endl cout 平均寻道长度 ave endl 电梯算法 void SCAN int cidao int m 先要给出当前磁道号和移动臂的移动方向 int k 1 int now l r d int i j sum 0 int a char str max float ave cidao paixu cidao m 调用排序算法排序 cout str 判断输入的数据是否正确 a panduan str if a 0 cout 数据类型错误 请重新输入 endl goto DD else now zhuanhuan str a 输入当前磁道号 if cidao m 1 now 若当前磁道号大于请求序列中最大者 则直接由外向 内依次给予各请求服务 cout 0 i cout cidao i now 若当前磁道号小于请求序列中最小者 则直接由内向外 依次给予各请求服务 cout 磁盘扫描序列为 for i 0 i m i cout cidao i cidao 0 l k 1 r k cout d if d 0 选择移动臂方向向内 则先向内扫描 cout 0 j cout cidao j 输出向内扫描的序列 for j r j m j 磁头移动到最小号 则改变方向向外扫描未扫描的磁 道 cout cidao j 输出向外扫描的序列 sum now 2 cidao 0 cidao m 1 else 选择移动臂方向向外 则先向外扫描 cout 磁盘扫描序列为 for j r j m j cout cidao j 0 j 磁头移动到最大号 则改变方向向内扫描未扫描的磁 道 cout cidao j sum now cidao 0 2 cidao m 1 ave float sum float m cout endl cout 平均寻道长度 ave endl 循环扫描调度算法 void CSCAN int cidao int m int k 1 int now l r int i j sum 0 int a char str max float ave cidao paixu cidao m 调用排序算法排序 cout str 判断输入的数据是否正确 a panduan str if a 0 cout 数据类型错误 请重新输入 endl goto EE else now zhuanhuan str a 输入当前磁道号 if cidao m 1 now 若当前磁道号大于请求序列中最大者 则直接将移动 臂移动到最小号磁道依次向外给予各请求服务 cout 磁盘扫描序列为 for i 0 i m i cout cidao i now 若当前磁道号小于请求序列中最小者 则直接由内向外 依次给予各请求服务 cout 磁盘扫描序列为 for i 0 i m i cout cidao i cidao 0 while cidao k now 反复地从内向外扫描 k l k 1 r k for j r j m j cout cidao j 输出从当前磁道向外扫描的序列 for j 0 j r j 当扫描完最大号磁道 磁头直接移动到最小号磁道 再 向外扫描未扫描的磁道 cout cidao j sum 2 cidao m 1 cidao l now 2 cidao 0 ave float sum float m cout endl cout 平均寻道长度 ave endl 五五 流程图设计 流程图设计 1 先来先服务算法流程图先来先服务算法流程图 输入当前磁道号 now 磁头移动距离 sum abs now cidao 0 磁头移动总距离 sum abs cidao j cidao i 输出磁盘调度序列 cidao j 目前的位置变为当前 的位置 j j m 输出平均寻道长度 ave sum m 2 最短寻道时间优先算法流程图最短寻道时间优先算法流程图 将磁道号从小到大排序 输入当前磁道号 now cidao m 1 0 输出磁盘调度 序列 cidao j cidao 0 now 磁头移动总距离 sum now cidao i 目前的位置变为 当前的位置 now cidao i now array i i m 确定当前磁道在已 排的序列中的位置 now cidao l cid ao r now 先向磁道号 减小方向访 问 再向磁 道号增加方 向访问 输出磁盘 调度序列 先向磁道号 增加方向访 问 再向磁 道号减小方 向访问 输出磁盘 调度序列 输出平均寻道长度 ave sum m 3 扫描算法流程图扫描算法流程图 将磁道号从小到大排序 输入当前磁道号 now 移动臂的移动的方向 cidao m 1 0 cidao 0 now 输出磁盘调度 序列 cidao j i m 磁头移动总距离 sum cidao i now 确定当前磁道在已 排的序列中的位置 switch d case 0 移动臂 向磁道号减小 方向访问 case 1 移动臂 向磁道号增加 方向访问 访问 输出磁盘 调度序列 输出磁盘 调度序列 输出平均寻道长度 ave sum m 六 六 运行运行结果结果 1 程序运行后的开始界面如下 程序运行后的开始界面如下 图图 1 2 先来先服务算法程序运行界面如下 先来先服务算法程序运行界面如下 图图 2 3 最短寻道时间优先算法程序运行界面如下 最短寻道时间优先算法程序运行界面如下 图图 3 4 电梯算法程序运行界面如下 电梯算法程序运行界面如下 图图 4 图图 5 5 循环扫描算法程序运行界面如下 循环扫描算法程序运行界面如下 图图 6 七 调试分析七 调试分析 此程序结果显示的界面非常清楚 友好 首先 需要用户输入所有的磁道号 此时若输入的不是数字 则提示有错误 重新输入 若正确 则可继续输入 若输入的是数字 0 则结束输入 用户输入的磁道号会按照输入