磁盘调度算法_scan调度算法

  来自不同进程的磁盘I/O请求构成一个随机分布的请求队列。磁盘I/O调度的主要目标就是减少请求队列对应的平均柱面定位时间。
目前常用的磁盘调度算法有：

1. 先来先服务FCFS
2. 最短寻道时间优先SSTF
3. 扫描（SCAN）算法
4. 循环扫描（CSCAN）算法

例
  假设磁盘访问序列：98，183，37，122，14，124，65，67。移动臂的运动方向：沿磁道号递减的方向移动。
读写头起始位置：53
（1）安排磁头服务序列
（2）计算磁头移动总距离（道数）

1.先来先服务

• 按访问请求到达的先后次序服务
• 优点：简单，公平；
• 缺点：效率不高，相邻两次请求可能会造成最内到最外的柱面寻道，使磁头反复移动，增加了服务时间，对机械也不利
  图解
  
  安排磁头服务序列为：98，183 ，37，122，14，124，65，67
  磁头走过的总道数：（98-53）+（183-98）+（183-37）+（122-37）+（122-14）+（124-14）+(124-65)+(67-65)=640

2. 最短寻道时间优先(SSF)

• 优先选择距当前磁头最近的访问请求进行服务，主要考虑寻道优先
• 优点：改善了磁盘平均服务时间；
• 缺点：造成某些访问请求长期等待得不到服务
  图解
  
  安排磁头服务序列为：65，67 ，37，14，98，122，124，183
  磁头走过的总道数：（65-53）+（67-65）+（67-37）+（37-14）+（98-14）+（122-98）+（124-122）+（183-124）=236

3. 扫描算法（电梯算法）

• 克服了最短寻道优先的缺点，既考虑了距离，同时又考虑了方向
• 具体做法：当设备无访问请求时，磁头不动；当有访问请求时，磁头按一个方向移动，在移动过程中对遇到的访问请求进行服务，然后判断该方向上是否还有访问请求，如果有则继续扫描；否则改变移动方向，并为经过的访问请求服务，如此反复
  图解
  
  安排磁头服务序列为：37，14， 65，67 ， 98， 122， 124， 183
  磁头走过的总道数：（53-37）+（37-14）+(65-14)+(67-65)+(98-67)+(122-98)+(124-122)+(183-124)=208

4 .循环扫描调度算法

• 也称单向扫描算法。
• 电梯算法杜绝了饥饿，但当请求对磁道的分布是均匀时，磁头回头，近磁头端的请求很少（因为磁头刚经过），而远端请求较多，这些请求等待时间要长一些。
• 总是从0号柱面开始向里扫描。移动臂到达最后个一个柱面后，立即带动读写磁头快速返回到0号柱面。返回时不为任何的等待访问者服务。返回后可再次进行扫描
  图解