常见的磁盘调度算法

更新 2019-8-10：增加了 LOOK 调度算法和添加了一些小的知识点

早期的磁盘调度算法

先来先服务

顾名思义，先来先服务就是按照请求访问磁道的顺序来访问磁道。

我们来看一个实例

从 100 开始，按照请求的顺序，依次访问 55，58 … 等磁道。
移动距离是上一个磁道到下一个磁道的距离。

1. 优点：公平，避免饥饿现象发生，不会产生磁臂黏着现象
2. 缺点：寻道时间长

最短寻道时间优先（SSTF）

SSTF 的原理是访问的下一个磁道是距离现在这个磁道最近的那一个磁道。

假如此时磁盘请求队列如下，55，58，39，18，90，160，150，38，184，初始磁道是 100。

此时在整个队列中距离 100 最近的磁道是 90，于是磁头移动到 90 处。在队列剩余磁道中，距离 90 最近的是 58，于是磁头又移动到 58。以此类推。

注意，每次比较的两个数值一个是当前磁道数，另一个是队列中剩余的磁道数，拉通比较（实际上看一眼就知道了）后选择最近的。

可以看到 90 这个磁道是距离 100 这个磁道距离最近的磁道，所以先访问。
而 58 这个磁道是距离 90 这个磁道距离最近的，所以是接下来访问。

1. 优点：比先来先算法性能更好
2. 缺点：容易造成饥饿现象

为什么会造成饥饿现象

因为磁道的请求时动态的，随时都会有新的磁道请求加入，如果，一段时间内，所请求的磁道数都是在当前磁道数附近，那么早期请求但是距离当前磁道远的磁道将长时间得不到满足，造成饥饿现象。

基于扫描的磁盘调度算法

扫描算法（电梯调度算法，SCAN）

我们看到 SSTF 算法虽然性能好，但是容易造成饥饿现象，本质上就是磁头一直处在当前
磁道的小范围内。所以扫描算法就是用来解决这个问题的。

1. 基本原理：就像它的名字一样，“电梯”算法先按照一个方向进行扫描，比如从内向外（如，从 0 号磁道向 100 好磁道移动就叫从内向外），再从外回到内（简单来说就是，从小到大，再从大到小）
2. 注意点：在移动的过程中，不必到头才转向，如此时从外向内，当磁头移动到 5 号时，已经到达了本轮的最小磁道，就不会继续向 0 号移动了
3. 示例：扫描算法的解决方式是，就是在 SSTF 的基础上增加了对磁头移动方向的规定。比如，此时磁盘请求队列中的请求顺序是 55，58，39，18，90，160，150，38，184。磁头初始位置在 100，且磁头沿着磁道号增大的方向移动。那么整个过程如下图所示
   

循环扫描算法（Circular SCAN）

扫描算法也同样存在问题，那就是，如果我按照向外的方向，刚走过假设是 100 的磁道，此时新请求是 99 磁道，但是因为需要继续向外，所以不能访问 99 磁道，这就造成了一定的开销。

1. 基本原理：循环扫描规定了磁头单向移动，在返回时是直接快速移动到起始端。比如现在假定该算法按照从内向外移动，当磁道扫描完本轮的最外（大）磁道 184 号时，磁头会直接移动到当前的最内磁道 18 号，如下图所示
   

LOOK 调度算法

look 调度算法是对 SCAN 算法和 C-SCAN 算法的优化
1

在 SCAN 算法和 C-SCAN 算法中，磁头移动（如向外移动）时，必须要达到远端（最远的那个磁道）才回返。比如最远的磁道数是 200，而此时请求调度的磁道数是 180，但我们依然要移动到 200 才回返。

优化的点就在这里，LOOK 算法不需要达到磁盘的端点（如果这个端点没有处于请求队列中），只需要达到最远的那个请求的磁道就可以返回了。其实现的方法是每次移动前查看是否有更远的请求。

比如我们看到的下面两幅图片，分别是对 SCAN 和 C-SCAN 进行优化后的 LOOK 算法，它们都没有到达端点在回返。

（下面两幅图片的来源）

参考

1. 《计算机操作系统》
2. 磁盘调度算法剖析