CS-Notes 计算机操作系统笔记：磁盘结构与磁盘调度算法（FCFS / SSTF / SCAN）详解

本文是 CS-Notes 仓库「计算机操作系统」系列中设备管理篇的深度展开。设备管理关注操作系统如何高效地协调 CPU 与 I/O 设备，而磁盘作为最典型的块设备，其访问效率直接决定整个存储子系统的性能。文章以磁盘物理结构为起点，逐一剖析先来先服务（FCFS）、最短寻道时间优先（SSTF）与电梯算法（SCAN）三类经典磁盘调度算法，并补充算法背后的适用场景与扩展变体，帮助读者在面试与系统设计中准确理解"为什么寻道时间决定一切"以及"每种调度策略的公平性与吞吐量取舍"。

磁盘结构

磁盘是一个机械与电磁结合的存储设备，其物理结构决定了读写数据的代价模型。理解磁盘结构，是理解磁盘调度算法为何存在的前提。一个磁盘通常由以下部分组成：

• 盘面（Platter）：一个磁盘由多个盘面叠加而成，数据就存储在每个盘面的磁性介质上。盘面越多，同一转速下可存储的数据总量越大；
• 磁道（Track）：盘面上的圆形带状区域，一个盘面可以被划分为多个同心圆形状的磁道；
• 扇区（Sector）：磁道上的一个弧段，一个磁道可以划分为多个扇区。扇区是磁盘上最小的物理存储单位，目前主要有 512 bytes 与 4 K（4096 bytes）两种大小，这与 Linux.md 中关于磁盘分区表（MBR/GPT）的论述互相印证——GPT 使用逻辑区块地址（Logical Block Address, LBA）来定义扇区，默认 LBA 大小即为 512 bytes；
• 磁头（Head）：与盘面非常接近的读写元件，能够将盘面上的磁场转换为电信号（读操作），或将电信号转换为盘面上的磁场（写操作）。磁头悬浮在盘面上方，并不与盘面直接接触；
• 制动手臂（Actuator Arm）：用于在磁道之间移动磁头。磁头的径向定位完全依赖制动手臂的机械摆动，这是整个寻道过程中最慢的环节；
• 主轴（Spindle）：使整个盘面转动，为磁头访问同一磁道上不同扇区提供旋转定位能力。

从机械结构可以看出，磁盘访问涉及"旋转"与"移动"两类物理运动，因此单次读写远慢于内存访问。这也解释了为什么 MySQL.md 的磁盘访问原理部分会强调"如果数据不在同一个磁盘块上，通常需要移动制动手臂进行寻道"，并据此论证 B+ 树比红黑树更适合磁盘存储：树高更低意味着寻道次数更少。

磁盘调度算法

一次磁盘读写的时间构成

读写一个磁盘块的时间主要受三个因素影响：

1. 旋转时间（Rotational Latency）：主轴转动盘面，使磁头移动到目标扇区上方所花费的时间；
2. 寻道时间（Seek Time）：制动手臂移动，使磁头从当前磁道移动到目标磁道所花费的时间；
3. 实际的数据传输时间（Transfer Time）：磁头与盘面介质之间真正交换数据的时间。

其中寻道时间最长，因此磁盘调度的主要目标就是使磁盘的平均寻道时间最短。当有多个磁盘 I/O 请求同时到达时，操作系统需要决定按什么顺序响应它们——这个决策策略就是磁盘调度算法。底层中断驱动机制可参考 计算机操作系统 - 概述 中对外中断（如 I/O 完成中断）的介绍：每次设备 I/O 完成都会产生一次中断，操作系统据此获知设备状态并派发下一个请求。

1. 先来先服务（FCFS）

FCFS，First Come First Served

按照磁盘请求到达的顺序进行调度，谁先发出请求，谁先被服务。

优点：

• 公平：所有请求按到达次序获得服务，不存在插队与优先级偏向；
• 简单：调度逻辑不需要任何额外状态，实现代价几乎为零。

缺点：未对寻道做任何优化。例如磁头当前位于磁道 53，若后续请求依次指向磁道 98、183、37、122、14、124、65、67，则磁头将频繁地在磁盘内外径之间往返，平均寻道距离可能相当长。在随机访问为主的负载下，FCFS 的吞吐量较低。

适用场景：请求数很少，或磁头移动距离本身不成为瓶颈时，FCFS 足够使用；也常作为衡量其他算法优化效果的基准。

2. 最短寻道时间优先（SSTF）

SSTF，Shortest Seek Time First

每次调度时，优先选择与当前磁头所在磁道距离最近的请求。

优点：平均寻道时间比较低。因为磁头每次都走向最近的请求，累计移动距离显著小于 FCFS。

缺点：不够公平，可能产生饥饿（Starvation）。核心问题在于"SSTF 只考虑距离、不考虑方向与等待时间"：如果新到达的磁道请求总是比一个早已在等待的磁道请求离当前磁头更近，那么后者的服务会被不断推迟，一直等待下去。具体来说，位于磁盘两端的磁道请求更容易出现饥饿现象——因为磁头通常被"牵引"在中部的密集请求之间来回移动，很少走到磁盘边界。

SSTF 虽然名为"最短寻道"，本质上仍是一种贪心策略（每次局部最优），并不能保证全局最优的寻道总距离。它是 FCFS 与真正全局优化之间的折中。

3. 电梯算法（SCAN，扫描算法）

SCAN

电梯算法与电梯的运行过程高度类似：电梯总是保持一个方向运行，直到该方向没有请求为止，然后改变运行方向。类比到磁盘上，磁头总是沿一个方向移动并依次服务沿途的请求，到达该方向的请求边界（或没有更远的请求）后再反向扫描。

与 SSTF 的本质区别在于：SCAN 在决策时明确考虑了移动方向，而不只是比较距离远近。这使得：

• 所有的磁盘请求都会被满足：磁头在内外径之间来回"扫"过整个磁盘，任何请求只要在其扫描路径上就迟早会被服务；
• 解决了 SSTF 的饥饿问题：不再存在"永远比不过新请求"而被无限推迟的请求——对两端的请求而言，磁头每完成一次完整扫描都会经过磁盘边缘。

潜在代价：在磁盘两端（磁道 0 和最大磁道处）附近，若长时间没有请求，磁头仍可能一直移动到端后才折返，产生一定的无效行程；同时，若请求恰好在磁头刚经过之后到达，则必须等磁头从另一端折返回来才能被服务，等待时间存在波动。

电梯算法的常见改进：C-SCAN 与 LOOK

在原文档所述 SCAN 基础上，工业界与教科书中普遍存在两类改进变体，理解它们有助于应对面试追问：

• C-SCAN（循环扫描）：磁头只沿一个方向服务请求，到达一端后直接快速返回起点（返回途中不服务请求），再重新开始扫描。它提供了比 SCAN 更均匀的等待时间——请求被服务的顺序与到达顺序近似一致，不会出现 SCAN 中"磁头刚折返、边界处请求等待最长"的不对称性；
• LOOK（电梯算法的提前折返）：SCAN 的改进版，磁头不需要移动到磁盘物理边界，而只需移动到当前方向上最远的那个请求所在磁道即可折返。由于避免了"空跑"到边界，LOOK 的平均寻道时间更短，实际操作系统与磁盘控制器中实现的往往是 LOOK / C-LOOK 这类变体。

若磁盘请求均匀分布在全部磁道上，SCAN 系列算法的平均寻道距离通常约为磁盘总磁道数的三分之一量级，远优于随机到达场景下的 FCFS。

与本仓库其他笔记的关联阅读

磁盘调度并非孤立知识点，在 CS-Notes 仓库中可以与以下文档交叉印证：

• 计算机操作系统 - 概述：从整体视角了解操作系统的 I/O 管理职能（缓冲管理、设备分配、设备处理、虚拟设备）以及 I/O 完成中断在设备交互中的作用；
• Linux.md 磁盘与文件系统部分：介绍了 IDE / SATA / SCSI / SAS 磁盘接口差异、Linux 中磁盘设备文件名规则（如 /dev/sd[a-p]）、MBR 与 GPT 分区表的扇区与 LBA 概念，以及"磁盘碎片指文件内容所在 block 过于分散导致磁头移动距离过大"的论述——碎片恰恰会放大寻道开销，与本文"寻道时间最长"的结论互为印证；
• MySQL.md 磁盘访问原理部分：从数据库索引设计的角度说明"寻道次数与树高成正比"，解释了 B+ 树这类磁盘友好数据结构的设计动机，是磁盘调度知识在存储引擎层面的实际延伸。

小结

磁盘调度的本质，是在公平性与平均寻道时间两个目标之间做权衡：

算法	核心思想	优点	缺点
FCFS	按请求到达顺序调度	公平、简单	不做寻道优化，平均寻道时间可能很长
SSTF	优先服务离磁头最近的磁道	平均寻道时间较低	不公平，两端磁道请求易饥饿
SCAN（电梯算法）	保持方向移动，直到该方向无请求再折返	考虑方向，所有请求都会被满足，消除饥饿	边界处可能空跑，等待时间存在波动

面试中若能进一步答出"SCAN 因考虑方向而避免饥饿，SSTF 因只比较距离而可能饿死远端请求"，并顺带说明 LOOK / C-SCAN 的改进思路，即可构成对磁盘调度这一考点的完整回答。