磁盘调度

## 1 磁盘结构

### 1.1 盘片

1. **一个磁盘由多个盘片叠加而成**。
2. 盘片的表面涂有**磁性物质**，这些磁性物质用来**记录二进制数据**，因为**正反两面都可涂上磁性物质**，所以**一个盘片可能会有两个盘面**。
3. **每个盘面对应一个磁头**，**所有的磁头都是连在同一个磁臂上的**，因此**所有磁头只能共进退**。

![](/media/202105/2021-05-25_093944.png)

### 1.2 磁道、扇区

1. 每个盘片被划分为一个个磁道，**每个磁道又划分为一个个扇区**，**每个扇区就是一个磁盘块**，各个扇区存放的**数据量相同**。
2. 最内侧**磁道**上的**扇区**面积最小，因此其数据密度最大。

![在这里插入图片描述](/media/202105/2021-05-25_094438.png)

### 1.3 柱面

1. 所有盘面**相对位置相同的磁道组成柱面**。

![](/media/202105/2021-05-25_094803.png)

## 2 相关时间

1. **寻道时间**：将磁头**移动到指定磁道**所花费的时间，主要包括两部分：
   1. **启动磁头臂消耗的时间**。
   2. **移动磁头消耗的时间**。
2. **旋转时间**：通过**旋转磁盘**，**使磁头定位到目标扇区**所需要的时间。
3. **传输时间**：从磁盘**读出或向磁盘写入数据**所经历的时间。
4. 由于**旋转时间**和**传输时间**都是**与磁盘转速有关**，而**转速又是磁盘的固有属性**，因此**无法通过操作系统优化旋转时间和传输时间**，**只能优化寻道时间**。

## 3 磁盘调度算法

> 磁盘调度算法都是用来减少**寻道时间**的。

现在常用的磁盘调度算法主要包括**先来先服务算法**（FCFS）、**最短寻找时间优先算法**（SSTF）、**扫描算法**（SCAN）、**循环扫描算法**（C_SCAN）。

### 3.1 先来先服务算法

#### 3.1.1 原理

1. 先来先服务算法的基本思想是**根据进程请求访问磁盘的先后顺序进行调度**。

#### 3.1.2 优缺点

##### 3.1.2.1 优点

1. **公平**。
2. **如果请求访问的磁道比较集中的话，算法性能还算可以**。

##### 3.1.2.2 缺点

1. 如果大量进程竞争使用磁盘，**请求访问的磁盘很分散**，则FCFS在**性能上很差**，**寻道时间长**。

#### 3.1.2 示例

1. 假设磁头的初始位置是100号磁道，有多个进程陆续地请求访问55、58、39、18、90、160、150、38、184号磁道。
2. 按照先来先服务算法规则，按照请求到达的顺序，磁头需要一次移动到55、58、39、18、90、160、150、38、184号磁道。
3. 磁头共移动了45 + 3 + 19 + 21 + 72 + 70 + 10 + 112 + 146 = 498个磁道，响应一个请求平均需要移动498 / 9 = 55.3个磁道（平均寻找长度）。

![](/media/202105/2021-05-25_103820.png)

### 3.2 最短寻找时间优先

#### 3.2.1 原理

1. 最短寻找时间优先算法的基本思想是**优先处理的磁道是与当前磁头最近的磁道**，可以保证**每次寻道时间最短**，但是**不能保证总的寻道时间最短**（其实是**贪心算法**的思想，只是选择眼前最优，但是总体未必最优）。

#### 3.2.2 优缺点

##### 3.2.2.1 缺点

1. **可能产生饥饿现象**，即磁头**在一小块区域移动**，导致**其他区域的访问请求无法得到响应**。

#### 3.2.3 示例

1. 假设磁头的初始位置是100号磁道，有多个进程先后陆续地请求访问55、58、39、18、90、160、150、38、184号磁道。
2. 磁头总共访问了（100 -18）+ （184 -18） = 248个磁道，响应一个请求平均需要移动248 / 9 = 27.5个磁道（平均寻找长度）。
3. 如果在处理18号磁道的访问请求时又来了一个38号磁道的访问请求，处理38号磁道的访问请求又来了一个18号磁道的访问请求，如果有源源不断的18号、38号磁道访问请求，那么150、160、184号磁道的访问请求就永远得不到满足，从而产生饥饿现象。

![](/media/202105/2021-05-25_105028.png)

### 3.3 扫描算法

#### 3.3.1 原理

1. SSTF算法会产生饥饿的原因在于**磁头有可能在一个小区域内来回移动**。
2. 为了防止这个问题，可以规定**磁头只有移动到请求最外侧磁道或最内侧磁道才可以反向移动，如果在磁头移动的方向上已经没有请求，就可以立即改变磁头移动，不必移动到最内/外侧的磁道**。
3. 由于**磁头移动的方式很像电梯**，因此也叫**电梯算法**。

#### 3.3.2 优缺点

##### 3.3.2.1 优点

1. **性能较好，寻到时间较短，不会产生饥饿现象**。

##### 3.3.2.2 缺点

1. **对各个位置磁道的响应频率不平均**。

#### 3.3.3 示例

1. 假设某磁盘的磁道为0~200号，磁头的初始位置是100号磁道，且此时磁头正在往磁道号增大的方向移动，有多个进程先后陆续地访问55、58、39、18、90、160、150、38、184号磁道。
2. 磁头共移动了（184 - 100）+ （184 -18） = 250个磁道，响应一个请求平均需要移动250 / 9 = 27.5个磁道（平均寻找长度）。
3. 但是该算法对各个位置磁道的响应频率不平均，假设此时磁头正在往右移动，且刚处理过90号磁道，那么下次处理90号磁道的请求就需要等待磁头移动很长一段距离，而响应了184号磁道的请求之后，很快又可以再次响应184号磁道的请求了。

![](/media/202105/2021-05-25_110528.png)

### 3.4 循环扫描算法

#### 3.4.1 原理

1. SCAN算法对各个位置磁道的响应频率不平均，而C-SCAN算法就是为了解决这个问题的。
2. 规定**只有磁头朝某个特定方向上移动时才处理磁道访问请求**，而**返回时直接快速移动至最靠边缘的并且需要访问的磁道上而不处理任何请求**。

#### 3.4.2 优缺点

##### 3.4.2.1 优点

1. 相比于SCAN算法，**对于各个位置磁道响应频率很平均**。

##### 3.4.2.2 缺点

1. 相比于SCAN算法，**平均寻道时间更长**。

#### 3.4.3 示例

1. 假设某磁盘的磁道为0~200号，磁头的初始位置是100号磁道，且此时磁头正在往磁道号增大的方向移动，有多个进程先后陆续地访问55、58、39、18、90、160、150、38、184号磁道。
2. 磁头共移动了（184 -100）+ （184 - 18）+（90 - 18）=322个磁道，响应一个请求平均需要移动322 / 9 = 35.8个磁道（平均寻找长度）。

## 4 参考文献

1. [5 分钟图解 磁盘的结构（盘片、磁道、扇区、柱面）](https://blog.csdn.net/weixin_37641832/article/details/103217311)。
2. [磁盘调度算法](https://www.jianshu.com/p/3c2b79af130b)。