磁盘结构和调度算法

2018-03-09 操作系统

• 磁盘结构
• 磁盘调度算法
  • 1. 先来先服务 (FCFS, First Come First Served)
  • 2. 最短寻道时间优先 (SSTF, Shortest Seek Time First)
  • 3. 电梯算法
    • 循环电梯算法
    • LOOK 与 C-LOOK算法

磁盘结构

上面的图片展示了一个常见的机械磁盘。

• 盘面（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 算法，磁头在每个方向上仅仅移动到最远的请求位置，然后立即反向移动，而不需要移动到磁盘的最始端或最末端，反向移动的途中不会响应请求。