<!-- GFM-TOC -->
* [磁盘结构](#磁盘结构)
* [磁盘调度算法](#磁盘调度算法)
    * [1. 先来先服务](#1-先来先服务)
    * [2. 最短寻道时间优先](#2-最短寻道时间优先)
    * [3. 扫描算法](#3-扫描算法)
    * [4. 循环扫描算法](#4-循环扫描算法)
<!-- GFM-TOC -->


# 磁盘结构

- 盘面（Platter）：一个磁盘有多个盘面；
- 磁道（Track）：盘面上的圆形带状区域，一个盘面可以有多个磁道；
- 扇区（Track Sector）：磁道上的一个弧段，一个磁道可以有多个扇区，它是最小的物理储存单位，目前主要有 512 bytes 与 4 K 两种大小；
- 磁头（Head）：与盘面非常接近，能够将盘面上的磁场转换为电信号（读），或者将电信号转换为盘面的磁场（写）；
- 制动手臂（Actuator arm）：用于在磁道之间移动磁头；
- 主轴（Spindle）：使整个盘面转动。

<div align="center"> <img src="https://s2.ax1x.com/2019/06/15/VoCepR.jpg"/> </div><br>

# 磁盘调度算法

读写一个磁盘块的时间的影响因素有：

- 旋转时间（主轴转动盘面，使得磁头移动到适当的扇区上）
- 寻道时间（制动手臂移动，使得磁头移动到适当的磁道上）
- 实际的数据传输时间

其中，寻道时间最长，因此磁盘调度的主要目标是使磁盘的平均寻道时间最短。

常见的磁盘调度算法有：

1.FCFS：先来先服务算法；

2.SSTF：最短寻道时间算法；

3.SCAN：扫描算法（也叫电梯调度算法）；

4.CSCAN：循环扫描算法



## 1. 先来先服务

> FCFS, First Come First Served

按照磁盘请求的顺序进行调度。算法思想非常简单，就是不论初始磁头在什么位置，都是按照服务队列的先后顺序依次处理进程，可以类比队列的先进先出。优点是进程处理起来非常简单，但缺点显而易见，因为未对寻道做任何优化，使平均寻道时间可能较长。

<div align="center"> <img src="https://i.loli.net/2019/06/15/5d04a489c547948743.gif"/> </div><br>

## 2. 最短寻道时间优先

> SSTF, Shortest Seek Time First

优先调度与当前磁头所在磁道距离最近的磁道。

虽然平均寻道时间比较低，但是不够公平。如果新到达的磁道请求总是比一个在等待的磁道请求近，那么在等待的磁道请求会一直等待下去，也就是出现饥饿现象。具体来说，两端的磁道请求更容易出现饥饿现象。

<div align="center"> <img src="https://i.loli.net/2019/06/15/5d04a527129a369200.gif
"/> </div><br>

## 3. 扫描算法

> SCAN

对于扫描算法，磁臂从磁盘的一端开始，向另一端移动；在移过每个柱面时，处理请求。当到达磁盘的另一端时，磁头移动方向反转，并继续处理。磁头连续来回扫描磁盘。SCAN 算法有时称为电梯算法，因为磁头的行为就像大楼里面的电梯，先处理所有向上的请求，然后再处理相反方向的请求。

因为考虑了移动方向，因此所有的磁盘请求都会被满足，解决了 SSTF 的饥饿问题。

<div align="center"> <img src="https://i.loli.net/2019/06/15/5d04a5f7897cc95866.gif
"/> </div><br>



## 4.循环扫描算法

> C-SCAN

循环扫描（C-SCAN）调度是 SCAN 的一个变种，以提供更均匀的等待时间。像 SCAN 一样，C-SCAN 移动磁头从磁盘一端到磁盘另一端，并且处理行程上的请求。然而，当磁头到达另一端时，它立即返回到磁盘的开头，而并不处理任何回程上的请求。

<div align="center"> <img src="https://i.loli.net/2019/06/15/5d04a66b764bd64678.gif
"/> </div><br>

  

参考资料：

<http://c.biancheng.net/view/1289.html>

<https://github.com/CyC2018/CS-Notes/>