磁盘调度算法

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

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

(1) 启动磁头臂消耗的时间：s。
(2) 移动磁头消耗的时间：假设磁头匀速移动，每跨越一个磁道消耗时间为m，共跨越n条磁道。

则寻道时间 Ts = s + m * n。

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

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

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

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

每个磁道可存N字节数据，因此b字节数据需要b/N个磁道才能存储。而读/写一个磁道所需的时间刚好是转一圈的时间1/r。

总的平均时间Ta = Ts + 1/2r + b/(rN)，由于延迟时间和传输时间都是与磁盘转速有关的，且是线性相关。而转速又是磁盘的固有属性，因此无法通过操作系统优化延迟时间和传输时间。所以只能优化寻找时间。

2 磁盘调度算法

2.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.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号磁道请求的访问就永远得不到满足，从而产生饥饿现象。这里产生饥饿的原因是磁头在一小块区域来回移动。