蛮荆

磁盘结构和调度算法

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

LOOK 算法

针对循环电梯算法的优化叫 C-LOOK 算法,磁头在每个方向上仅仅移动到最远的请求位置,然后立即反向移动,而不需要移动到磁盘的最始端或最末端,反向移动的途中不会响应请求

C-LOOK 算法

转载申请

本作品采用 知识共享署名 4.0 国际许可协议 进行许可,转载时请注明原文链接,图片在使用时请保留全部内容,商业转载请联系作者获得授权。