磁盘管理：磁盘调度算法

文件系统层次结构
设备（含磁盘）管理位于最后一层
下图来自王道考研操作系统

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

平均存取时间 = 寻道时间 + 延迟时间 + 传输时间
$$T_a=T_s+\frac{1}{2r}+\frac{B}{rN}$$

延迟时间与传输时间均与磁盘转速有关，而磁盘转速是硬件属性，无法通过软件实现优化
操作系统唯一能优化的是寻道时间

1.1.1 寻道时间

寻道时间$T_s$：在读写数据前，启动磁头臂并将磁头移动到指定磁道所花的时间
1.启动磁头臂耗时$s$
2.假设磁头每跨越一个磁道耗时$m$，若共需要跨越$n$条磁道
$$T_s=s+m\ast n$$
寻道时间 = 磁头臂启动时间 + 移动磁头时间

1.启动磁头臂耗时$s$

2.磁头每跨越一个磁道耗时$m$，若共需要跨越$n$条磁道

下图来自王道考研操作系统

1.1.2 延迟时间

磁头移动到某个磁道上后定住不动，需要磁盘旋转才能使得磁头读取对应磁道上的某个扇区，这个磁盘旋转的时间就是延时时间

延迟时间$T_R$：通过旋转磁盘，使得磁头定位到目标扇区所需要的时间。
设磁盘转速为 $r$（单位：转/秒 或者 转/分），则平均所需的延迟时间
$$T_R=\frac{1}{2}\ast \frac{1}{r}=\frac{1}{2r}$$
$\frac{1}{r}$就是转一圈需要的时间。找到目标扇区平均需要转半圈，因此再乘$\frac{1}{2}$
延迟时间 = 磁盘转一圈的时间的平均值

下图来自王道考研操作系统

1.1.3 传输时间

传输时间$T_t$：从磁盘读出或向磁盘写入数据所经历的时间
设磁盘转速为$r$，此次读写字节数为$B$，每个磁道上能存储字节数为$N$，故需要占用$B/N$个磁道，读写一个磁道所需时间就是磁盘转一圈需要的时间 $1/r$
$$T_t=\frac{1}{r}\ast \frac{B}{N}=\frac{B}{rN}$$
传输时间 = 读写一个磁道时间 * 要读写的磁道个数

下图来自王道考研操作系统

2.1 磁盘调度算法

磁盘调度在多道程序设计的计算机系统中，各个进程可能会不断提出不同的对磁盘进行读/写操作的请求。由于有时候这些进程的发送请求的速度比磁盘响应的还要快，因此我们有必要为每个磁盘设备建立一个等待队列

寻道时间是影响磁盘调度算法的指标

2.1.1 先来先服务（FCFS）

思想：磁头从当前磁道移动到第一个请求访问的磁道，之后按照提出请求的顺序依次进行

下图来自王道考研操作系统

2.1.2 最短寻找时间优先（SSTF）

思想：磁头每次都从当前磁道移动到离最近发出请求访问的那个磁道。只能保证每次寻找的时间最短，但无法保证总的寻找时间最短，也就是无法达到所有请求访问时的寻找时间最短（局部最优，非总体最优）

下图来自王道考研操作系统
为了防止SSTF中陷入局部不断的请求而导致其他磁道的饥饿现象，引出扫描算法

2.1.3 扫描算法 / 电梯算法（SCAN）

思想：磁头每次都从当前磁道移动往请求访问序列中磁道号较大的方向移动，直到遇到磁盘的最外层磁道才开始回头寻找请求访问中的较小号磁道

下图来自王道考研操作系统

扫描算法中其实没必要非得移动到磁盘最外层磁道，应该在请求访问序列中最大磁道处回头，针对扫描算法的第一个缺点做出改进，引出LOOK调度算法

扫描算法各个磁道的响应不均，可能某个磁道频繁访问，而其他被访问的次数少，针对扫描算法的第二个缺点做出改进，引出循环扫描算法

2.1.4 LOOK调度算法（LOOK）

思想：对扫描算法第一个缺点的改进，无需像扫描算法一样移动到磁盘最外侧磁道才回头，可以边移动边观察，如果移动到请求访问序列中最后一个磁道就立马回头

下图来自王道考研操作系统

2.1.5 循环扫描算法（C-SCAN）

思想：解决了扫描算法即各个磁道响应频率不均（第二个缺点）的问题。只有当磁头往某特定方向移动时（比如往右）才进行处理请求，往左移动时不处理任何请求，即便是路过某个访问请求也不处理

下图来自王道考研操作系统

2.1.6 C-LOOK调度算法（C-LOOK）

思想：解决C-SCAN中遇到磁盘最外侧磁道才回头的问题。若磁头移动方向上没有磁道访问请求了，就可让磁头回头，只需返回到有磁道访问请求的位置即可

下图来自王道考研操作系统