一、磁盘移臂调度算法
1、磁盘移臂调度算法简介
磁盘 数据块读取 的 性能 主要由
- 寻道时间
- 旋转延时
决定 ;
旋转延时 是 硬盘的 盘面 持续保持匀速旋转 实现的 , 这是 硬盘 本身的硬件特性 , 该延时没有规律 ;
磁头的寻道时间 , 是可以使用算法进行优化的 , 该算法称为 " 移臂调度算法 " ,
" 磁盘移臂调度算法 " 在 磁盘调度器 Disk Scheduler 中实现 , 用于 用于优化磁盘访问时间 , 以最小化 磁头移动时间 和 优化磁盘 访问顺序 ;
" 磁盘移臂调度算法 " 有如下几种 :
- 先来先服务 , FCFS , First Come First Served
- 最短寻道时间优先 , SSTF , Shortest Seek Time First
- 电梯算法 Elevator Algorithm / 扫描算法 SCAN
- 循环扫描算法 , C-SCAN , Circular SCAN
2、先来先服务算法
先来先服务 , FCFS , First Come First Served , 谁先申请 , 就先让谁访问磁盘数据 , 这是最简单的磁盘调度算法 , 按照请求到达的顺序依次处理 ;
先来先服务 FCFS 算法 的 缺点是 磁头在磁盘上无规律地移动 , 造成平均等待时间较长 , 效率很低 ;
下面是 先来先服务 FCFS 算法 示例 ,
左侧的 ① ② ③ ~ ⑨ 是 申请的 顺序序号 ,
初始状态下 , 磁头位于 100 号磁道 ;
第 ① 个数据请求 , 申请访问 55 号磁道 , 根据 先来先服务 的 算法原则 , 先为 申请 ① 服务 , 需要从 100 号磁道 移动到 55 号磁道 , 移动了 45 个磁道 ;
第 ② 个数据请求 , 申请访问 58 号磁道 , 当前处于 55 号磁道 , 移动 3 个磁道 , 去访问 58 号磁道 ;
最终访问完 ① ~ ⑨ 这 9 个数据请求 , 平均每个数据请求 寻道长度为 55.3 个 ;
3、最短寻道时间优先
最短寻道时间优先 , SSTF , Shortest Seek Time First , 每次选择 最靠近当前磁头位置的请求 进行处理 , 以最小化寻道时间 ;
最短寻道时间优先 SSTF 算法 相比于 先来先服务算法 在效率上是有提升的 ;
最短寻道时间优先 SSTF 算法的 缺点是 可能会因为 频繁访问某些区域 而 导致其他区域的请求 长时间等待 , 可能产生饥饿现象 ;
下面的案例是 最短寻道时间优先 算法示例 :
初始位置时 100 号磁道 ,
先后出现了 ① ~ ⑨ 九个数据访问请求 , 磁头寻道 并不会按照 请求顺序 进行寻道 ,
而是按照 磁道 距离进行 寻道 ;
离 初始位置 100 号磁道 , 最近的 被访问磁道号 是 90 , 那么优先访问 90 号磁道 , 跨越 10 个磁道 , 访问完毕后 , 处于 90 号磁道位置 ;
距离 90 号磁道 最近的是 58 号磁道 , 跨越 32 个磁道 , 访问完毕后 , 处于 58 号磁道位置 ;
距离 58 号磁道 最近的请求是 55 号磁道 , 跨越 3 个磁道 , 访问完毕后 , 处于 55 号磁道 ;
以此类推 …
访问完 最后一个数据后 , 9 个寻道平均寻道个数是 27.5 个磁道 ;
4、扫描算法
扫描算法 SCAN 又叫做 电梯算法 Elevator Algorithm ;
扫描算法 SCAN 的运行机制是 模拟电梯的运行方式 , 沿着一个方向移动磁头 , 直到遇到 最边缘的请求 , 然后改变方向移动 ;
扫描算法 SCAN 适合处理相对均匀分布的请求 , 能有效减少平均等待时间 ;
5、循环扫描算法
循环扫描算法 , C-SCAN , Circular SCAN , 沿着一个方向移动磁头 , 直到 磁头 移动到 最边缘 , 当到达最边缘时直接跳到另一边的最边缘 , 形成一个循环 ;
循环扫描算法 适合处理特定模式的请求分布 , 可以减少平均等待时间 ;
二、最短寻道时间优先算法示例
初始状态下 , 磁头位于 15 号 磁道 / 柱面 , 下面是 6 个数据访问请求 , 以及数据所在的磁道 , 采用 最短寻道时间优先算法 , 计算其 数据访问 序列 ;
磁道 就是 柱面 , 二者含义相同 ;
磁头号 是 磁头在不同 盘面 的编号 , 一个硬盘 有 6 个盘面 , 则每个盘面上都有一个磁头 ;
扇区 是 同一个磁道 的 不同角度区域 , 磁头在磁道上以后 , 靠 磁盘旋转 切换扇区 ;
一般在软考中 , 只需要关注 磁道 即可 , 不需要关注 磁头号 和 扇区号 这两个迷惑选项 ;
计算过程 :
初始状态 , 磁头位于 15 号磁道 ;
- 当前离 15 号 最近的 磁道 是 ① 和 ⑤ 请求 , 都在 12 磁道中 ;
- 先 响应 ① 和 ⑤ 请求 , 具体先响应那个 , 无从判断 , 可能是 ①⑤ , 也可能是 ⑤① ;
响应完 ①⑤ 请求后 , 当前处于 12 号磁道 , 离 12 号磁道最近的是 ② 和 ④ 请求的 19 号 磁道 ;
然后访问 ③ 号请求的 23 号磁道 ,
最后访问 ⑥ 号请求的 28 号磁道 ;
