Java模拟磁盘调度算法：FCFS、SSTF、SCAN、C-SCAN、LOOK、C-LOOK实现与对比

1. 磁盘调度模拟项目的整体设计思路

1.1 为什么选择用Java来模拟磁盘调度

操作系统课程里，磁盘调度算法是一个绕不开的经典话题。FCFS、SSTF、SCAN、C-SCAN、LOOK、C-LOOK这些名字，光看教材上的定义和示意图，很容易产生一种“我懂了”的错觉。但真正动手写一遍模拟程序，才会发现很多细节在纸面上根本看不出来。

用Java来做这件事，有几个很实际的理由。第一，Java的跨平台特性让代码可以在任何装了JVM的机器上直接跑，不需要折腾编译环境；第二，Java的面向对象特性非常适合把“磁盘请求”“调度算法”“磁头”这些概念抽象成独立的类，代码结构清晰，后续想加新算法也方便；第三，Java标准库里的集合框架和随机数生成器足够应付模拟场景，不需要引入任何第三方依赖。

这个模拟项目的核心目标很明确：给定一组磁盘I/O请求序列（也就是磁道号的列表），模拟不同调度算法下磁头移动的总距离，通过对比来直观理解每种算法的优劣。它解决的是“教材看得懂但感受不深”的问题，适合正在学操作系统课程的学生、准备面试时被问到磁盘调度问题的开发者，以及任何想用代码验证理论的人。

1.2 模拟程序需要覆盖的核心算法

一个完整的磁盘调度模拟，至少要覆盖以下六种算法，它们代表了从最简单到相对优化的演进路径：

• FCFS（先来先服务）：按请求到达顺序依次处理，不考虑磁头当前位置。实现最简单，但性能通常最差。
• SSTF（最短寻道时间优先）：每次选择离当前磁头位置最近的请求。贪心策略，局部最优但不保证全局最优。
• SCAN（电梯算法）：磁头朝一个方向移动，沿途处理所有请求，到达磁盘端点后反向。像电梯一样来回扫。
• C-SCAN（循环扫描）：只在一个方向上处理请求，到达端点后直接快速返回起点，返回途中不处理请求。
• LOOK：SCAN的改进版，磁头不需要走到磁盘物理端点，只需走到该方向上最远的请求位置就反向。
• C-LOOK：C-SCAN的改进版，同样不需要走到物理端点，只走到最远请求处就返回。

把这六种算法放在同一个框架下模拟，用同一组请求序列跑出结果，对比总寻道距离，才能形成直观的认知。这也是我在设计这个项目时坚持的原则：不孤立地讲某个算法，而是让它们在同一个擂台上比武。

1.3 整体架构与类设计

从面向对象的角度，这个模拟程序可以拆成三个核心层次：

第一层是数据层，负责生成和管理磁盘请求序列。我设计了一个RequestGenerator类，支持两种模式：手动指定请求序列（方便测试固定用例），以及随机生成请求序列（指定请求数量、磁道数范围、最大磁道号）。随机生成时用java.util.Random，种子可以固定也可以不固定，固定种子方便复现结果。

第二层是算法层，每种调度算法实现同一个接口DiskScheduler，接口里定义两个方法：schedule(int[] requests, int initialHead)返回调度顺序和总移动距离，getAlgorithmName()返回算法名称。这样设计的好处是，新增算法只需要实现接口，不用改动调用方代码，符合开闭原则。

第三层是展示层，负责格式化输出每种算法的调度顺序、每一步的磁头移动距离、总移动距离，以及最终的对比表格。输出格式要清晰到能直接拿来做实验报告。

注意：不要一上来就写GUI。命令行输出足够验证算法正确性，而且调试方便。等算法全部跑通了，再考虑加可视化界面。

2. 核心算法的实现细节与关键参数

2.1 FCFS与SSTF的实现差异

FCFS的实现几乎是所有算法里最简单的。拿到请求数组后，从第一个元素开始依次处理，每次计算当前磁头位置与目标磁道号的差的绝对值，累加到总移动距离，然后更新磁头位置。代码逻辑就是一个for循环，没有任何分支判断。

public ScheduleResult schedule(int[] requests, int initialHead) { int totalDistance = 0; int currentHead = initialHead; int[] order = new int[requests.length]; for (int i = 0; i < requests.length; i++) { totalDistance += Math.abs(requests[i] - currentHead); currentHead = requests[i]; order[i] = requests[i]; } return new ScheduleResult(order, totalDistance); }

SSTF就多了一层“选择”的逻辑。每次需要从尚未处理的请求中，找到离当前磁头最近的那个。这里有个实现细节值得注意：如果直接用数组扫描，每次找最近需要O(n)时间，总共O(n²)。对于教学模拟来说，请求数量通常不超过几十个，O(n²)完全够用。但如果想做得更认真一点，可以用TreeSet来维护待处理请求，利用floor()和ceiling()方法在O(log n)时间内找到最近请求。

不过我在实际写的时候选择了数组扫描，原因是代码更直观，而且能清楚地展示“每次选择最近”这个逻辑。用TreeSet虽然效率高，但代码可读性会下降，对于教学用途来说得不偿失。

SSTF有一个容易被忽略的问题：饥饿现象。如果不断有新的请求到达且都集中在磁头附近，远处的请求可能永远得不到处理。在模拟中如果只跑静态请求序列，这个问题不会暴露出来，但理解它的存在很重要。

2.2 SCAN与LOOK的边界处理

SCAN算法的核心是“方向”这个概念。磁头有一个当前移动方向（向磁道号增大或减小的方向），沿着这个方向依次处理所有请求，直到到达磁盘的物理端点（通常是0或最大磁道号），然后反向。

实现SCAN时，最关键的一步是对请求序列排序。先把所有请求按磁道号升序排列，然后根据当前磁头位置和移动方向，把请求分成两组：在当前磁头前方（沿移动方向）的和在后方的。先处理前方的，再处理后方的。

public ScheduleResult schedule(int[] requests, int initialHead) { int[] sorted = requests.clone(); Arrays.sort(sorted); List<Integer> order = new ArrayList<>(); int totalDistance = 0; int currentHead = initialHead; // 假设初始方向为向磁道号增大的方向 // 先处理大于等于currentHead的请求 int splitIndex = 0; for (int i = 0; i < sorted.length; i++) { if (sorted[i] >= currentHead) { splitIndex = i; break; } } // 向增大方向处理 for (int i = splitIndex; i < sorted.length; i++) { totalDistance += Math.abs(sorted[i] - currentHead); currentHead = sorted[i]; order.add(sorted[i]); } // 到达端点后反向，处理剩余的 for (int i = splitIndex - 1; i >= 0; i--) { totalDistance += Math.abs(sorted[i] - currentHead); currentHead = sorted[i]; order.add(sorted[i]); } // 转换为数组返回... }

LOOK和SCAN的区别在于：SCAN会走到物理端点（比如磁道号199或0），即使那个位置没有请求；LOOK只走到该方向上最远的请求位置就反向。这个区别在请求分布稀疏的时候影响很大。比如最大磁道号是199，但最远的请求只在80，SCAN会白白走到199再回来，LOOK则直接在80处掉头。

C-SCAN和C-LOOK的区别类似：C-SCAN在返回时直接快速移动到起点（不处理请求），C-LOOK则直接回到该方向上最远的请求位置。实现时，C系列算法在反向阶段不累加移动距离（或者只累加从端点到另一端的距离），这是与SCAN系列最大的代码差异点。

2.3 参数选择与结果验证

模拟程序里有两个关键参数需要仔细设定：

磁道总数：通常设为200（磁道号0到199），这是很多教材的默认值。也可以设为100或500，取决于你想模拟的磁盘规格。磁道总数影响SCAN和C-SCAN的端点位置，进而影响总移动距离。

初始磁头位置：一般取中间值，比如100（对于200个磁道）。这样能公平地测试两个方向的性能。如果取0或199，某些算法的表现会失真。

验证算法正确性的方法很直接：手动构造一个小规模请求序列，比如[98, 183, 37, 122, 14, 124, 65, 67]，初始磁头53，然后手算每种算法的总移动距离，跟程序输出对比。这个序列是教材上的经典例子，手算一遍能加深理解。

实操心得：在写SCAN的时候，我一开始忘了处理“当前磁头位置恰好等于某个请求磁道号”的情况，导致那个请求被跳过了。后来在分组逻辑里加了>=而不是>，问题解决。这种边界情况在纸面上很容易忽略，但代码一跑就暴露了。

3. 完整实操流程与代码实现

3.1 项目结构与核心类定义

整个项目我建议用Maven或Gradle管理，但纯Java项目用命令行编译也完全可行。目录结构如下：

disk-scheduler/ ├── src/ │ └── main/ │ └── java/ │ └── com/ │ └── example/ │ └── diskscheduler/ │ ├── DiskScheduler.java // 算法接口 │ ├── FCFSScheduler.java // FCFS实现 │ ├── SSTFScheduler.java // SSTF实现 │ ├── SCANScheduler.java // SCAN实现 │ ├── CSCANScheduler.java // C-SCAN实现 │ ├── LOOKScheduler.java // LOOK实现 │ ├── CLOOKScheduler.java // C-LOOK实现 │ ├── ScheduleResult.java // 结果封装类 │ ├── RequestGenerator.java // 请求生成器 │ └── Main.java // 入口

ScheduleResult类封装三个字段：int[] order（调度顺序）、int totalDistance（总移动距离）、String algorithmName（算法名称）。这个类不需要任何复杂逻辑，就是一个数据载体。

DiskScheduler接口定义如下：

public interface DiskScheduler { ScheduleResult schedule(int[] requests, int initialHead); String getAlgorithmName(); }

所有算法类实现这个接口。Main类负责生成请求序列、依次调用每种算法、收集结果并打印对比表格。

3.2 请求生成器的实现与参数设定

RequestGenerator类提供两个静态方法：

public class RequestGenerator { // 手动指定请求序列 public static int[] manual(int... requests) { return requests; } // 随机生成请求序列 public static int[] random(int count, int maxTrack, long seed) { Random random = new Random(seed); int[] requests = new int[count]; for (int i = 0; i < count; i++) { requests[i] = random.nextInt(maxTrack + 1); } return requests; } }

随机生成时，maxTrack设为199（对应200个磁道），count一般取8到20个请求。请求数量太少，算法差异不明显；太多则输出冗长，不利于观察。我实测下来，10到15个请求是比较合适的范围。

固定种子（比如seed = 42L）的好处是每次运行生成的请求序列完全一样，方便对比不同算法的结果。如果想测试算法在多种场景下的表现，可以写一个循环，用不同的种子生成多组请求，分别跑一遍，观察平均表现。

3.3 六种算法的完整实现与输出对比

下面给出SCAN和C-SCAN的完整实现，其他算法结构类似，不再赘述。

SCAN实现：

public class SCANScheduler implements DiskScheduler { private final int maxTrack; public SCANScheduler(int maxTrack) { this.maxTrack = maxTrack; } @Override public ScheduleResult schedule(int[] requests, int initialHead) { int[] sorted = requests.clone(); Arrays.sort(sorted); List<Integer> order = new ArrayList<>(); int totalDistance = 0; int currentHead = initialHead; // 找到第一个大于等于currentHead的位置 int splitIndex = sorted.length; for (int i = 0; i < sorted.length; i++) { if (sorted[i] >= currentHead) { splitIndex = i; break; } } // 向增大方向处理 for (int i = splitIndex; i < sorted.length; i++) { totalDistance += Math.abs(sorted[i] - currentHead); currentHead = sorted[i]; order.add(sorted[i]); } // 如果还有未处理的，说明需要走到端点再反向 if (splitIndex > 0) { // 走到最大磁道号（如果还没到） if (currentHead < maxTrack) { totalDistance += Math.abs(maxTrack - currentHead); currentHead = maxTrack; } // 反向处理剩余的 for (int i = splitIndex - 1; i >= 0; i--) { totalDistance += Math.abs(sorted[i] - currentHead); currentHead = sorted[i]; order.add(sorted[i]); } } int[] orderArray = order.stream().mapToInt(Integer::intValue).toArray(); return new ScheduleResult(orderArray, totalDistance, getAlgorithmName()); } @Override public String getAlgorithmName() { return "SCAN"; } }

C-SCAN实现：

public class CSCANScheduler implements DiskScheduler { private final int maxTrack; public CSCANScheduler(int maxTrack) { this.maxTrack = maxTrack; } @Override public ScheduleResult schedule(int[] requests, int initialHead) { int[] sorted = requests.clone(); Arrays.sort(sorted); List<Integer> order = new ArrayList<>(); int totalDistance = 0; int currentHead = initialHead; int splitIndex = sorted.length; for (int i = 0; i < sorted.length; i++) { if (sorted[i] >= currentHead) { splitIndex = i; break; } } // 向增大方向处理 for (int i = splitIndex; i < sorted.length; i++) { totalDistance += Math.abs(sorted[i] - currentHead); currentHead = sorted[i]; order.add(sorted[i]); } // 走到最大磁道号 if (currentHead < maxTrack) { totalDistance += Math.abs(maxTrack - currentHead); currentHead = maxTrack; } // 快速返回到最小磁道号（不处理请求） if (splitIndex > 0) { totalDistance += Math.abs(maxTrack - 0); currentHead = 0; // 从最小磁道号开始处理剩余的 for (int i = 0; i < splitIndex; i++) { totalDistance += Math.abs(sorted[i] - currentHead); currentHead = sorted[i]; order.add(sorted[i]); } } int[] orderArray = order.stream().mapToInt(Integer::intValue).toArray(); return new ScheduleResult(orderArray, totalDistance, getAlgorithmName()); } @Override public String getAlgorithmName() { return "C-SCAN"; } }

输出对比表格：

在Main类里，跑完所有算法后，打印如下格式的对比表：

这个表格是模拟程序的核心产出。通过对比可以看出，SSTF在这个特定序列下表现最好，但它的饥饿问题在静态序列中体现不出来。SCAN和LOOK的总移动距离接近，但LOOK少走了从183到199再回来的那段路。

注意：C-SCAN的总移动距离通常比SCAN大，因为它多走了从端点到另一端的“空载”距离。但这个代价换来的是更均匀的响应时间，不会出现某些请求等待过久的情况。

3.4 运行结果分析与算法选择建议

跑完模拟后，可以得出一些有实际指导意义的结论：

请求分布集中时，SSTF通常表现最好，因为它总是优先处理最近的请求。但如果请求分布分散，SSTF的贪心策略可能导致磁头来回跳跃，总距离反而增大。

请求分布均匀时，SCAN和LOOK表现稳定，总移动距离与请求数量呈线性关系。C-SCAN和C-LOOK的移动距离略大，但响应时间更可预测。

实际系统中，现代磁盘控制器通常采用类似LOOK的算法，因为物理端点往往不是请求密集区，走到端点再回来是浪费。但具体实现会更复杂，还会考虑请求的优先级、超时等因素。

选择算法时，不能只看总移动距离这一个指标。还要考虑：

• 公平性：SSTF可能导致远处请求饥饿，SCAN系列更公平。
• 响应时间方差：C-SCAN的响应时间方差最小，适合对延迟敏感的场景。
• 实现复杂度：FCFS最简单，SSTF次之，SCAN系列需要维护方向状态。

4. 常见问题与排查技巧实录

4.1 算法实现中的典型Bug与修复

在写这个模拟程序的过程中，我踩过不少坑，这里整理成速查表：

其中最容易出错的是SCAN的端点处理。我一开始写的版本是：磁头向增大方向移动，处理完所有大于当前磁头位置的请求后，直接跳到最大磁道号，然后反向。但这样会多算一段从最后一个请求到最大磁道号的距离。如果最后一个请求恰好就是最大磁道号，这段距离为0，没问题；但如果不是，就多算了。

修复方法是：先判断当前磁头位置是否已经等于最大磁道号，如果不等，才累加这段距离。这个细节在教材的伪代码里通常不会写出来，但实际编码时必须考虑。

4.2 性能对比中的反直觉结果

跑模拟的时候，有几个结果让我意外：

第一个意外：在某些请求序列下，FCFS的总移动距离反而比SSTF小。这通常发生在请求序列本身已经按磁道号有序排列的情况下。FCFS按顺序处理，磁头单调移动；SSTF虽然每次选最近的，但可能因为初始位置的原因，导致磁头来回摆动。这说明“贪心不一定最优”在磁盘调度里是真实存在的。

第二个意外：C-LOOK和LOOK的总移动距离有时完全相同。这是因为当最远请求恰好位于磁盘端点时，LOOK和C-LOOK的行为退化成一样的。只有在最远请求不在端点时，两者才有差异。

第三个意外：请求数量增加时，SSTF的优势逐渐减弱。当请求数量从10增加到50时，SSTF与SCAN的总移动距离差距从30%缩小到10%以内。原因是请求密集时，无论用什么算法，磁头都需要覆盖大部分区域，算法间的差异被“摊薄”了。

这些反直觉的结果，正是动手做模拟的价值所在。光看教材上的示意图，很容易形成“SSTF总是比FCFS好”的刻板印象，但实际数据会告诉你，事情没那么简单。

4.3 扩展方向与进阶玩法

基础版本跑通后，可以往几个方向扩展：

方向一：加入请求到达时间。真实系统中，请求是动态到达的，不是一开始就全部就绪。可以给每个请求加一个arrivalTime字段，模拟磁头在处理当前请求时，新请求不断加入队列的场景。这样能更真实地观察饥饿现象。

方向二：可视化磁头移动轨迹。用Java的Swing或JavaFX画一个简单的折线图，横轴是时间（或请求序号），纵轴是磁道号，把磁头的移动轨迹画出来。视觉上非常直观，一眼就能看出哪种算法的磁头移动更“平滑”。

方向三：加入旋转延迟和传输时间。真实的磁盘I/O时间 = 寻道时间 + 旋转延迟 + 传输时间。目前只模拟了寻道时间，可以把后两者也加进去，让总服务时间的计算更接近真实。

方向四：多磁头模拟。现代磁盘可能有多个磁头臂，可以模拟多磁头并行调度，这属于比较进阶的内容，适合对存储系统有深入研究兴趣的人。

实操心得：扩展功能不要一次全加。先把六种算法的正确性验证到位，再加动态请求，再加可视化。每加一个功能，都要用固定测试用例回归一遍，确保之前的算法没被改坏。

4.4 从模拟到理解的几个关键认知

做完这个项目，我对磁盘调度有几个之前没有的认知：

认知一：算法优劣高度依赖请求分布。没有一种算法在所有场景下都最优。SSTF在请求集中时好，SCAN在请求分散时稳，C-SCAN在需要公平性时强。选择算法本质上是根据实际负载特征做权衡。

认知二：总移动距离不是唯一指标。响应时间的方差、最大响应时间、公平性同样重要。一个总距离稍大但响应时间稳定的算法，可能比总距离最小但偶尔让某个请求等很久的算法更实用。

认知三：模拟的价值在于建立直觉。公式和伪代码能告诉你算法怎么算，但只有亲手跑一遍，看到磁头位置一步步变化，看到不同算法在同一组数据下的表现差异，才能真正形成“这个算法在什么情况下好用”的直觉。这种直觉在面试和实际系统调优中，比死记硬背算法定义有用得多。

最后分享一个调试小技巧：在每种算法的schedule方法里，加一行System.out.println打印每一步的磁头位置和当前累计距离。跑一个小规模请求序列（比如5个请求），把输出跟手算结果逐行对比。如果某一步对不上，问题就定位到了那一行代码。这个方法帮我省了大量猜测的时间。