操作系统4.2.2 磁盘调度算法_典型的磁盘调度算法基本原理及调度过程

一、一次磁盘读/写操作需要的时间

①寻找时间（寻道时间）Ts：在读/写数据前，需要将磁头移动到指定磁道所花费的时间。

寻道时间分两步：

1. 启动磁头臂消耗的时间：s。
2. 移动磁头消耗的时间：m * n。假设磁头匀速移动，每跨越一个磁道消耗时间为m，共跨越n条磁道。
3. 则寻道时间 Ts = s + m * n。

磁头移动到指定的磁道，但是不一定正好在所需要读/写的扇区，所以需要通过磁盘旋转使磁头定位到目标扇区。

②延迟时间TR（转动磁盘的时间）：通过旋转磁盘，使磁头定位到目标扇区所需要的时间。设磁盘转速为r（单位：转/秒，或转/分），则平均所需延迟时间TR = (1/2)*(1/r) = 1/2r。

1/r 就是转一圈所需的时间。找到目标扇区平均需要转半圈，因此再乘以1/2。

 

③传输时间Tt：从磁盘读出或向磁盘中写入数据所经历的时间，假设磁盘转速为r，此次读/写的字节数为b，每个磁道上的字节数为N，则传输时间Tt = (b/N) * (1/r) = b/(rN)。

求需要几个磁道：每个磁道可存N字节数据，因此b字节数据需要b/N个磁道才能存储。

转一圈所花费的时间：而读/写一个磁道所需的时间刚好是转一圈的时间1/r。

 

④总的平均时间Ta = 寻道时间 + 延迟时间 + 传输时间 = Ts + 1/2r + b/(rN)

由于延迟时间和传输时间都是与磁盘转速有关的，且是线性相关。

而转速又是磁盘的固有属性，因此无法通过操作系统优化延迟时间和传输时间。所以只能优化寻找时间。

 

 

二、磁盘调度算法

1、先来先服务算法（FCFS）

算法思想：根据进程请求访问磁盘的先后顺序进行调度。

假设磁头的初始位置是100号磁道，有多个进程先后陆续地请求访问55、58、39、18、90、160、150、38、184号磁道。

按照先来先服务算法规则，按照请求到达的顺序，磁头需要依次移动到55、58、39、18、90、160、150、38、184号磁道。

磁头共移动了 45 + 3 + 19 + 21 + 72 + 70 + 10 + 112 + 146 = 498个磁道。响应一个请求平均需要移动498 / 9 = 55.3个磁道（平均寻找长度）。

优点：公平；如果请求访问的磁道比较集中的话，算法性能还算可以。

缺点：如果大量进程竞争使用磁盘，请求访问的磁道很分散，FCFS在性能上很差，寻道时间长。

 

 

2、最短寻找时间优先（SSTF）

算法思想：优先处理的磁道是与当前磁头最近的磁道。可以保证每次寻道时间最短，但是不能保证总的寻道时间最短。（其实是贪心算法的思想，只是选择眼前最优，但是总体未必最优）。

假设磁头的初始位置是100号磁道，有多个进程先后陆续地请求访问55、58、39、18、90、160、150、38、184号磁道。

磁头总共移动了（100 -18）+ （184 -18） = 248个磁道。响应一个请求平均需要移动248 / 9 = 27.5个磁道（平均寻找长度）。

缺点：可能产生饥饿现象。

本例中，如果在处理18号磁道的访问请求时又来了一个38号磁道的访问请求，处理38号磁道的访问请求又来了一个18号磁道访问请求。如果有源源不断的18号、38号磁道访问请求，那么150、160、184号磁道请求的访问就永远得不到满足，从而产生饥饿现象。这里产生饥饿的原因是磁头在一小块区域来回移动。

 

 

3、扫描算法（SCAN）

SSTF算法会产生饥饿的原因在于：磁头有可能再一个小区域内来回得移动。

为了防止这个问题，可以规定：磁头只有移动到请求最外侧磁道或最内侧磁道才可以反向移动，如果在磁头移动的方向上已经没有请求，就可以立即改变磁头移动，不必移动到最内/外侧的磁道。这就是扫描算法的思想。由于磁头移动的方式很像电梯，因此也叫电梯算法。

假设某磁盘的磁道为0~200号，磁头的初始位置是100号磁道，且此时磁头正在往磁道号增大的方向移动，有多个进程先后陆续的访问55、58、39、18、90、160、150、38、184号磁道。

磁头共移动了（200 - 100）+ （200 -18） = 282个磁道。响应一个请求平均需要移动 282 / 9 = 31.3个磁道（平均寻找长度）。

优点：性能较好，寻道时间较短，不会产生饥饿现象。

缺点：①只有到达最边上的磁道（200）时才能改变磁头移动方向，实际上处理完184号磁道的访问请求之后不必再右移（LOOK调度算法解决）。

②SCAN算法对于各个位置磁道的响应频率不平均。（假设此时磁头正在往右移动，且刚处理过90号磁道，那么下次处理90号磁道的请求就需要等待低头移动很长一段距离；而响应了184号磁道的请求之后，很快又可以再次响应184号磁道请求了。）（C-SCAN循环扫描算法解决）

 

 

4、LOOK调度算法

算法思想：扫描算法（SCAN）中，只有到达最边上的磁道时才能改变磁头移动方向，事实上，处理了184号磁道的访问请求之后就不需要再往右移动磁头了。

LOOK调度算法就是为了解决这个问题，如果在磁头移动方向上已经没有别的请求，就可以立即改变磁头移动方向。（边移动边观察，因此叫LOOK）

假设某磁盘的磁道为0~200号，磁头的初始位置是100号磁道，且此时磁头正在往磁道号增大的方向移动，有多个进程先后陆续地请求访问55、58、39、18、90、160、150、38、184号磁道

磁头总共移动了（184-100）+（184-18）=250个磁道

响应一个请求平均需要移动250/9 = 27.5个磁道（平均寻找长度）

 

 

5、循环扫描算法（C-SCAN）

SCAN算法对各个位置磁道的响应频率不平均，而C-SCAN算法就是为了解决这个问题。

规定：只有磁头朝某个特定方向移动时才处理磁道访问请求，而返回时直接快速移动至最靠边缘的并且需要访问的磁道上而不处理任何请求。

通俗理解就是SCAN算在改变磁头方向时不处理磁盘访问请求而是直接移动到另一端最靠边的磁盘访问请求的磁道上。

假设某磁盘的磁道为0~200号，磁头的初始位置是100号磁道，且此时磁头正在往磁道号增大的方向移动，有多个进程先后陆续的访问55、58、39、18、90、160、150、38、184号磁道。

磁头共移动了（184 -100）+ （184 - 18）+（90 - 18）=322个磁道。响应一个请求平均需要移动322 / 9 = 35.8个磁道（平均寻找长度）。

优点：相比于SCAN算法，对于各个位置磁道响应频率很平均。

缺点：相比于SCAN算法，平均寻道时间更长。

 

 

6、C-LOOK调度算法

算法思想：C-SCAN算法的主要缺点是只有到达最边上的磁道时才能改变磁头移动方向，并且磁头返回时不一定需要返回到最边缘的磁道上。C-LOOK算法就是为了解决这个问题。

如果磁头移动的方向上已经没有磁道访问请求了，就可以立即让磁头返回，并且磁头只需要返回到有磁道访问请求的位置即可。

假设某磁盘的磁道为0~200号，磁头的初始位置是100号磁道，且此时磁头正在往磁道号增大的方向移动，有多个进程先后陆续地请求访问55、58、39、18、90、160、150、38、184号磁道

磁头总共移动了（184-100）+（184-18）+（90-18）=322个磁道

响应一个请求平均需要移动322/9=35.8个磁道（平均寻找长度）
 

 

 

三、小结

如果题目无特别说明，SCAN就是LOOK，C-SCAN就是C-LOOK。