磁盘结构和调度算法
2018-03-09 操作系统
磁盘结构
上面的图片展示了一个常见的机械磁盘。
- 盘面（Platter）：一个磁盘有多个盘面；
- 磁道（Track）：盘面上的圆形带状区域，一个盘面可以有多个磁道；
- 扇区（Track Sector）：磁道上的一个弧段，一个磁道可以有多个扇区，它是最小的物理储存单位；
- 磁头（Head）：与盘面非常接近，能够将盘面上的磁场转换为电信号（读），或者将电信号转换为盘面的磁场（写）；
- 柱面（Cylinder）：多个具有相同编号的磁道形成一个圆柱，称为磁盘的柱面；
- 制动手臂（Actuator arm）：用于在磁道之间移动磁头；
- 主轴（Spindle）：使整个盘面转动；
下面在来一张三维图片，可以更直观地展示出不同的盘面。
读写一个磁盘块的时间的影响因素有：
- 旋转时间（主轴转动盘面，使得磁头移动到目标扇区上）
- 寻道时间（制动手臂移动，使得磁头移动到目标磁道上）
- 实际的数据传输时间
其中寻道时间最长，因此 磁盘调度算法的主要目标是使磁盘的平均寻道时间最短，也就是优化磁盘的访问请求顺序。
磁盘调度算法
1. 先来先服务 (FCFS, First Come First Served)
按照磁盘请求的顺序进行调度，也就是朴素的排队算法。
优点: 实现简单、相对公平 缺点: 未对寻道做任何优化，使平均寻道时间可能较长
- 假设现在有一个磁道请求队列: 98，183，37，122，14，124，65，67
- 假设当前磁头位于 53 号磁道
采用 FCFS 算法，磁道移动距离等于:
(98-53) + (183-98) + (183-37) + (122-37) + (122-14) + (124-14) + (124-65) + (67-65) = 640
如果系统中存在大量进程竞争使用磁盘，请求访问的磁道可能非常分散，FCFS 算法因为寻道时间过长，在性能上会表现很差。
2. 最短寻道时间优先 (SSTF, Shortest Seek Time First)
优先调度与当前磁头所在磁道距离最近的磁道，虽然平均寻道时间比较低，但是不够公平。
如果新到达的磁道请求总是比一个在等待的磁道请求近，那么在等待的磁道请求会一直等待下去，也就是出现饥饿现象。如果请求磁道正好位于对立的两端，更容易出现饥饿现象。
- 假设现在有一个磁道请求队列: 98，183，37，122，14，124，65，67
- 假设当前磁头位于 53 号磁道
采用 SSTF 算法，磁道移动距离等于:
(65-53) + (67-65) + (67-37) + (37-14) + (98-14) + (122-98) + (124-122) + (183-124) = 236
SSTF 算法相比 FCFS 算法，性能提高了很多，但可能存在某些磁道请求的饥饿现象。
- 假设现在有一个磁道请求队列: 53，183 … 后面所有请求磁道号均小于 53
- 假设当前磁头位于 53 号磁道
那么 183 号磁道可能永远不会被响应，于是产生了饥饿现象，磁头只在 0 - 53 号这个区域内来回移动。
3. 电梯算法
SSTF 算法会产生饥饿的原因在于：磁头有可能在一个小区域内来回移动。
电梯算法可以防止这个问题，电梯算法规定：磁头只能在一个方向上移动，访问所有未完成的请求，直到磁头到达该方向上的最后的磁道，然后改变方向。
就像现实中的电梯一样，总是按一个方向来进行磁盘调度，直到该方向上没有未完成的磁盘请求，然后改变方向。
- 假设现在有一个磁道请求队列: 98，183，37，122，14，124，65，67
- 假设当前磁头位于 53 号磁道
磁头先响应左边的请求，直到到达最左端（ 0 磁道）后，才开始反向移动，响应右边的请求。
采用电梯算法，磁道移动顺序:
37，14，0，65，67，98，122，124，183
磁道移动距离等于:
(53-37) + (37-14) + (14-0) + (65-0) + (67-65) + (98-67) + (122-98) + (124-122) + (183-124) = 236
电梯算法性能较好，而且不会产生饥饿问题，但是位于中间部分的磁道比较 “占便宜”，因为中间部分相比其他部分的响应频率会较多，结果就是每个磁道的响应频率是不一样的。就像现实中坐电梯一样，不论电梯是上还是下，中间楼层的乘客可以直接乘坐电梯的概率更大。
循环电梯算法
电梯算法使得每个磁道的响应频率存在差异，要优化这个问题，可以总是保持相同的方向进行扫描，使得每个磁道的响应频率基本一致。
循环电梯扫描 规定：只有磁头朝某个特定方向移动时，才处理磁道访问请求，而返回时直接移动到对端边缘的磁道，也就是复位磁头，这个过程是很快的，并且返回中途不处理任何请求，该算法的特点就是 磁道只响应当前同一个方向上的请求。
- 假设现在有一个磁道请求队列: 98，183，37，122，14，124，65，67
- 假设当前磁头位于 53 号磁道
假设循环电梯调度算先朝磁道增加的方向移动，磁道移动顺序：
65，67，98，122，124，183，199，0，14，37
磁道移动距离等于 (忽略磁头复位):
(65-53) + (67-65) + (98-67) + (122-98) + (124-122) + (183-124) + (199-183) + (14-0) + (37-14) = 183
磁头先响应了右边的请求，直到碰到了最右端的磁道 199，就立即回到磁盘的开始处（磁道 0），但这个返回的途中是不响应任何请求的，直到到达最开始的磁道后，才继续顺序响应右边的请求。
循环电梯算法相比于电梯算法，对于各个位置磁道响应频率相对比较平均。
LOOK 与 C-LOOK算法
刚才提到的电梯算法和循环电梯算法，都是磁头移动到磁盘「最始端或最末端」之后，然后再开始调换方向。这部分其实是可以优化的，优化的思路就是 磁头在移动到「最远的请求」位置，然后立即反向移动即可。
针对电梯算法的优化则叫 LOOK 算法，磁头在每个方向上仅仅移动到最远的请求位置，然后立即反向移动，而不需要移动到磁盘的最始端或最末端，反向移动的途中会响应请求。
针对循环电梯算法的优化叫 C-LOOK 算法，磁头在每个方向上仅仅移动到最远的请求位置，然后立即反向移动，而不需要移动到磁盘的最始端或最末端，反向移动的途中不会响应请求。
