磁盘调度算法

复习定位

磁盘的物理结构——磁头读取磁盘上的数据——磁头的移动速度远慢于磁盘的旋转速度。当多个I/O请求排队时——调度算法决定先服务哪个请求——目标是减少磁头移动的总距离(平均寻道时间)。FCFS简单但低效——SSTF改进了但可能饿死了远处的请求——SCAN和C-SCAN在公平性、饥饿防止方面表现更好。

磁头寻道与旋转延迟

磁盘的一次I/O时间由三部分组成：寻道时间(磁头移动到目标磁道) + 旋转延迟(盘片旋转到目标扇区) + 数据传输时间。寻道时间约4-10ms——旋转延迟约2-6ms——数据传输相对较小。所以减少寻道时间成为磁盘调度最重要的目标。

FCFS(先来先服务)

按请求到达的顺序处理。实现简单——但没有优化寻道——磁头往往来回大幅度摆动——平均寻道时间长。

磁头初始位置: 50
请求队列: 95, 180, 34, 119, 11, 123, 62, 64
磁头移动顺序: 50→95→180→34→119→11→123→62→64
总寻道: |50-95|+|95-180|+|180-34|+|34-119|+|119-11|+|11-123|+|123-62|+|62-64|=
      45+85+146+85+108+112+61+2=644(磁道)

SSTF(最短寻道时间优先)

选择离当前磁头最近的请求先服务——有效减少寻道时间——但可能导致远处的请求无限等待(饥饿)——特别是如果不断有近处的请求集中到达。

50→62(12)→64(2)→34(30)→11(23)→95(84)→119(24)→123(4)→180(57)
总寻道: 12+2+30+23+84+24+4+57=236(磁道)——明显优于FCFS。

SCAN(电梯算法)

磁头从一端向另一端移动——沿途服务经过的所有磁道的请求——到达末端后折返。像一个电梯——从一楼到顶楼——途中停靠各层——到达顶楼后向下。

假设磁头向增大方向移动,初始50,队列同上
向增大方向服务: 62,64,95,119,123,180→到达末端→折返→34,11
总寻道: 从50到180=130 + 从180折返到11=169 = 299(磁道)

SCAN解决了饥饿问题——因为所有请求总会在某个时间内被服务(磁头在扫描路径上一定会经过它们)。

C-SCAN(循环扫描)

SCAN的一个变种——磁头始终只向一个方向移动(从外到内)——服务完最后一个请求后立即返回最外道——再从外到内扫描。优点是各磁道上的请求等待时间更均匀。

复习检查

1. 为什么SSTF可能导致某些请求饿死——如果磁头当前位置附近不断有新的请求到达——远处的请求可能一直无法被选中而无限等待——因为当前最近的请求永远是新的近处请求不是远处的请求。

2. SCAN和C-SCAN在公平性上的差别——SCAN在到达末端折返时——刚服务过的磁道可能立即又有新请求——而折返后磁头马上又经过它们——这些新请求被快速服务——但末端磁道的请求等待时间可能更长——C-SCAN始终只向一个方向服务——没有"折返"的不公平。

3. 现代SSD为什么不再需要磁盘调度算法——SSD没有机械部件(没有磁头也没有旋转盘片)——随机寻址时间与顺序寻址时间没有差别——所以调度算法(减少寻道)对它无意义——SSD使用的NVMe队列可以深度多队列并行处理多个请求。

4. FCFS在磁盘调度中的应用——优点——极其简单、公平、没有饥饿；缺点——平均寻道时间很大——磁盘性能低下。

5. 如果请求队列分布非常分散——SCAN的平均寻道时间几乎与SSTF相近——但有了公平性的保证——因此SCAN是公平性和性能的综合折中——被许多实际磁盘调度实现参考。