磁盘调度

磁盘调度
- 与进程调度不同，对于磁盘调度，磁盘是清楚每个磁盘请求需要多长时间的
- 通过估计请求的查找和可能的旋转延迟，磁盘调度程序可以知道每个请求需要花费多少时间
- 因此，磁盘在调度多个请求时，可以按照贪心策略，先服务花费时间最少的请求，也就是遵循最短任务优先原则(principle of SJF, shortest job first)
最短寻道时间优先(SSTF)
- 最短寻道时间优先(SSTF, Shortest-Seek Time First)，也称最短寻道优先(STF, Shortest Time First)
- SSTF按照目标磁道距离当前磁道的远近来给请求排序，距离当前磁道越近的请求越先完成
- 虽然操作系统无法看到磁盘的物理结构，只能看到一些块。但是操作系统可以直接使用最近块优先(NBF, Nearest Block First) 而不是SSTF，按照逻辑块地址之间的差值来估计磁道距离远近，最后效果与SSTF相似
- SSTF可能会导致饥饿(starvation)。如果在当前磁道附近的磁道中总有请求，那么更远的磁道上的请求就会饥饿
电梯(SCAN/C-SCAN)
- 为了避免SSTF中的饥饿问题，我们可以使用电梯(elevator)算法，电梯算法是指SCAN与其衍生的一类算法
- 最早的电梯算法是SCAN算法：它会以跨越磁道的顺序执行请求，一次跨越磁盘被称为扫一遍。如果某个请求所属的磁道在这一次扫描中已经被扫过了，那么它就不会立刻被处理，而是排队等待下一次扫描
- 后来出现了F-SCAN算法：它会在扫描时冻结队列以进行维护，并将扫描期间加入的请求放入队列等待，这样可以避免远距离请求饥饿，但是会延迟迟到但更近的请求
- 循环SCAN(C-SCAN, Circular-Scan) 则对循环顺序有改变：不是单一的扫描方向，而是先从内扫到外，再从外扫到内，以此循环
- 电梯算法并不是最好的调度策略，SCAN和SSTF甚至并没有完全遵循SJF的原则：它们都忽视了旋转，而最接近SJF的策略要既考虑寻道，也考虑旋转
最短定位时间优先(SPTF)
- 最短定位时间优先(SPTF, Shortest Positioning Time First)，也被称为最短接入时间优先(SATF, Shortest Access TIme First)
- 如果寻道时间远远大于旋转时间，那么SSTF显然足够，但是实际情况不总是这样，因此我们需要综合考虑寻道时间和旋转时间的SPTF策略，但是它在操作系统中的实现非常困难，毕竟操作系统通常不清楚磁道边界在哪，也不知道磁头当前的位置

最短寻道时间优先(SSTF)

电梯(SCAN/C-SCAN)

最短定位时间优先(SPTF)