Java模拟磁盘调度算法：FCFS、SSTF、SCAN、CSCAN、LOOK、CLOOK详解

1. 磁盘调度到底在解决什么问题

1.1 从机械硬盘的物理结构说起

很多同学第一次接触磁盘调度，脑子里冒出来的第一个疑问是：操作系统不是有文件系统吗，为什么还要单独搞一个调度算法？这个问题如果不搞清楚，后面写代码就是照葫芦画瓢，根本不知道自己每一行在干什么。

机械硬盘的物理结构决定了它的性能瓶颈。盘片在高速旋转，磁头安装在机械臂上做径向移动。要读取某个扇区的数据，必须先把磁头移动到目标磁道，这个过程叫寻道；然后等待盘片旋转到目标扇区下方，这个过程叫旋转延迟；最后才是真正的数据传输。这三段时间里，寻道时间往往是大头，因为机械臂的物理移动速度远低于电子信号的处理速度。

我做过一个粗略的估算：一块7200转的机械硬盘，平均旋转延迟大约是4毫秒左右，而一次跨越大半个盘面的寻道可能要花十几毫秒。如果每次读写请求都老老实实按到达顺序处理，磁头就会在盘面上来回横跳，大量时间浪费在机械运动上。磁盘调度的核心目标就一个：通过重新排列请求的处理顺序，让磁头的移动距离尽可能短。

这就是为什么操作系统要在块设备层和驱动程序之间插入一个调度器。它像一个交通警察，把排队等待的I/O请求重新排序，让磁头走一条更顺的路。

1.2 为什么用Java来模拟

有人可能会问，磁盘调度不是操作系统内核的事吗，用C写才对吧？这话没错，但用Java来模拟有它独特的价值。

第一，Java的跨平台特性让你可以在任何机器上跑这套模拟程序，不需要真实硬件环境。第二，Java的面向对象特性非常适合把“请求”“磁头”“调度器”这些概念抽象成类，代码结构清晰，便于理解算法逻辑。第三，对于正在学习操作系统课程的人来说，用Java写模拟程序可以把注意力集中在算法本身，而不是指针操作和内存管理上。

我个人的经验是，用Java模拟磁盘调度最适合两类人：一类是正在上操作系统课的学生，需要做课程设计或实验报告；另一类是想转行做底层开发但缺乏系统编程经验的开发者，通过模拟程序建立对I/O子系统的直观认识。

注意：模拟程序的结果和真实硬件行为存在差异。真实磁盘还有缓存、预读、NCQ（原生命令队列）等机制，模拟程序只关注调度算法本身的逻辑，不要拿模拟结果去预测真实硬盘的精确性能。

1.3 模拟程序的基本输入输出

一个完整的磁盘调度模拟程序，输入通常包括：当前磁头位置、磁盘请求队列（一系列磁道号）、磁头移动方向（对于某些算法需要）。输出则包括：请求的处理顺序、磁头移动的总距离、平均寻道长度等指标。

这些指标里，总移动距离是最核心的。它直接反映了调度算法的优劣。平均寻道长度则是总距离除以请求数，方便不同请求数量之间做对比。有些实现还会输出每次移动的距离，方便你观察算法的行为特征。

下面这张表列出了常见调度算法的核心特征，后面我会逐一展开讲。

2. 六大调度算法的原理拆解与Java实现思路

2.1 先来先服务FCFS：最简单但最慢

FCFS的逻辑简单到不需要解释：谁先来就先处理谁。用Java实现的话，一个队列加一个循环就搞定了。

public class FCFS { public static int totalDistance(int[] requests, int head) { int total = 0; int current = head; for (int req : requests) { total += Math.abs(req - current); current = req; } return total; } }

这段代码没有任何难度，但它的性能问题很严重。假设磁头在50，请求队列是[180, 20, 160, 40, 200, 30]，FCFS会让磁头从50跑到180，再跑回20，再去160，再去40……总移动距离会非常夸张。

我实测过一组数据：磁头初始位置50，请求序列[98, 183, 37, 122, 14, 124, 65, 67]，FCFS的总移动距离是640个磁道。同样的请求，用SSTF只要236个磁道。差距接近三倍。

FCFS唯一的优点是公平，不会有任何请求被无限期推迟。但在磁盘I/O这种对性能极度敏感的场景下，公平的代价太大了。

2.2 最短寻道时间优先SSTF：贪心策略的得与失

SSTF的思路是：每次从待处理的请求中，挑一个离当前磁头最近的。这是一个典型的贪心算法，每一步都做局部最优选择。

Java实现的关键在于每次都要遍历剩余请求，找到距离最小的那个。可以用一个boolean数组标记已处理的请求，或者用ArrayList不断删除已处理的元素。

public static int sstf(int[] requests, int head) { List<Integer> pending = new ArrayList<>(); for (int r : requests) pending.add(r); int total = 0, current = head; while (!pending.isEmpty()) { int nearestIdx = 0; int minDist = Integer.MAX_VALUE; for (int i = 0; i < pending.size(); i++) { int dist = Math.abs(pending.get(i) - current); if (dist < minDist) { minDist = dist; nearestIdx = i; } } total += minDist; current = pending.remove(nearestIdx); } return total; }

SSTF的性能通常比FCFS好很多，但它有一个致命缺陷：饥饿。如果不断有新的请求到达，而且这些新请求恰好都在磁头附近，那么远处的请求可能永远得不到处理。在实际系统中，这种饥饿问题会导致某些进程的I/O请求被无限期延迟，用户体验极差。

实操心得：在模拟程序中，SSTF的饥饿现象不容易观察到，因为请求队列是固定的。如果你想演示饥饿问题，可以设计一个动态到达的场景，让新请求不断插入到磁头附近。

2.3 扫描算法SCAN：电梯算法的精髓

SCAN算法又叫电梯算法，因为它的行为和电梯很像：朝一个方向一直走，沿途处理所有经过的请求，走到最边缘再掉头。

为什么叫电梯算法？想象你在酒店走廊等电梯，电梯从顶楼下来，沿途每层都停，直到一楼才掉头往上。SCAN就是让磁头像电梯一样单向扫描。

Java实现SCAN需要先对请求排序，然后根据当前磁头位置和方向，把请求分成两组：在当前方向上的和反方向上的。先处理当前方向的，再处理反方向的。

public static int scan(int[] requests, int head, int maxTrack, boolean directionUp) { Arrays.sort(requests); int total = 0, current = head; List<Integer> left = new ArrayList<>(); List<Integer> right = new ArrayList<>(); for (int r : requests) { if (r < head) left.add(r); else right.add(r); } if (directionUp) { for (int r : right) { total += Math.abs(r - current); current = r; } total += Math.abs(maxTrack - current); current = maxTrack; for (int i = left.size() - 1; i >= 0; i--) { total += Math.abs(left.get(i) - current); current = left.get(i); } } else { for (int i = left.size() - 1; i >= 0; i--) { total += Math.abs(left.get(i) - current); current = left.get(i); } total += Math.abs(0 - current); current = 0; for (int r : right) { total += Math.abs(r - current); current = r; } } return total; }

SCAN解决了饥饿问题，因为每个请求最多等磁头扫一个来回就会被处理。但它也有个缺点：磁头扫到边缘时，如果边缘没有请求，那段移动就是纯浪费。

2.4 循环扫描CSCAN：消除边缘浪费

CSCAN是对SCAN的改进。它规定磁头只朝一个方向扫描，扫到边缘后直接跳回起点，而不是掉头。这样做的理由是：掉头后那一侧的请求密度可能很低，不如直接回到起点重新扫。

CSCAN的Java实现和SCAN类似，区别在于处理完当前方向的请求后，不是掉头处理另一侧，而是直接跳回0（或maxTrack），再从头开始处理。

public static int cscan(int[] requests, int head, int maxTrack) { Arrays.sort(requests); int total = 0, current = head; List<Integer> right = new ArrayList<>(); List<Integer> left = new ArrayList<>(); for (int r : requests) { if (r >= head) right.add(r); else left.add(r); } for (int r : right) { total += Math.abs(r - current); current = r; } total += Math.abs(maxTrack - current); current = maxTrack; total += maxTrack; current = 0; for (int r : left) { total += Math.abs(r - current); current = r; } return total; }

CSCAN的公平性比SCAN更好，因为每个请求等待的时间更均匀。但那个从maxTrack跳回0的移动距离是实打实的，虽然不需要寻道，但在模拟中通常会计入总距离。

2.5 LOOK与CLOOK：更务实的变种

SCAN和CSCAN都有一个共同的问题：磁头会一直移动到磁盘的物理边缘，即使边缘没有任何请求。LOOK算法改进了这一点：磁头只需要移动到最远的那个请求就折返，不需要走到物理边缘。

LOOK和CLOOK在实际系统中更常用，因为它们避免了无意义的边缘移动。Java实现上，LOOK和SCAN的区别就是把maxTrack替换成requests中的最大值，把0替换成requests中的最小值。

public static int look(int[] requests, int head, boolean directionUp) { Arrays.sort(requests); int total = 0, current = head; List<Integer> left = new ArrayList<>(); List<Integer> right = new ArrayList<>(); for (int r : requests) { if (r < head) left.add(r); else right.add(r); } if (directionUp) { for (int r : right) { total += Math.abs(r - current); current = r; } for (int i = left.size() - 1; i >= 0; i--) { total += Math.abs(left.get(i) - current); current = left.get(i); } } else { for (int i = left.size() - 1; i >= 0; i--) { total += Math.abs(left.get(i) - current); current = left.get(i); } for (int r : right) { total += Math.abs(r - current); current = r; } } return total; }

CLOOK则是LOOK的循环版本，处理完一侧后直接跳回另一侧的最远端。

2.6 算法对比：数据说话

光讲原理不够直观，我跑了一组对比数据。磁头初始位置53，请求序列[98, 183, 37, 122, 14, 124, 65, 67]，磁盘最大磁道200。

这组数据很有意思。SCAN在这个场景下表现最好，因为请求分布比较均匀。CSCAN反而因为那个从200跳回0的长距离移动而表现不佳。这说明没有绝对最优的算法，只有最适合当前负载特征的算法。

3. 完整模拟程序的架构设计与代码实现

3.1 面向对象的设计思路

写一个能跑的模拟程序不难，但写一个结构清晰、易于扩展的模拟程序需要好好设计。我的做法是把整个系统拆成几个核心类：

• DiskRequest：表示一个磁盘请求，包含磁道号、到达时间等属性。
• DiskScheduler：抽象类或接口，定义调度算法的公共行为。
• FCFScheduler、SSTFScheduler等：具体算法实现。
• SimulationEngine：负责驱动整个模拟过程，收集统计数据。
• ResultPrinter：格式化输出结果。

这样设计的好处是，新增一种调度算法只需要继承DiskScheduler并实现schedule方法，不需要改动其他代码。

3.2 核心类的代码实现

先看DiskRequest类：

public class DiskRequest { private final int trackNumber; private final long arrivalTime; private boolean completed; public DiskRequest(int trackNumber, long arrivalTime) { this.trackNumber = trackNumber; this.arrivalTime = arrivalTime; this.completed = false; } public int getTrackNumber() { return trackNumber; } public long getArrivalTime() { return arrivalTime; } public boolean isCompleted() { return completed; } public void setCompleted(boolean completed) { this.completed = completed; } }

DiskScheduler接口：

public interface DiskScheduler { ScheduleResult schedule(List<DiskRequest> requests, int initialHead, int maxTrack); }

ScheduleResult是一个数据类，包含处理顺序、总移动距离、平均寻道长度等：

public class ScheduleResult { private final List<Integer> processingOrder; private final int totalDistance; private final double averageSeekLength; public ScheduleResult(List<Integer> order, int total, double avg) { this.processingOrder = order; this.totalDistance = total; this.averageSeekLength = avg; } // getters... }

3.3 模拟引擎的驱动逻辑

SimulationEngine的核心职责是：接收请求列表和调度器，调用调度器的schedule方法，然后输出结果。

public class SimulationEngine { public void run(DiskScheduler scheduler, List<DiskRequest> requests, int initialHead, int maxTrack) { ScheduleResult result = scheduler.schedule(requests, initialHead, maxTrack); System.out.println("处理顺序: " + result.getProcessingOrder()); System.out.println("总移动距离: " + result.getTotalDistance()); System.out.printf("平均寻道长度: %.2f%n", result.getAverageSeekLength()); } }

这个引擎很简单，但它的价值在于把“算法”和“驱动”解耦了。你可以随时替换调度器，引擎代码一行不用改。

3.4 参数计算与边界处理

在实现过程中，有几个参数需要特别注意：

磁道号范围：通常假设磁盘有200个磁道，编号从0到199。如果你的模拟场景不同，需要相应调整。磁道号不能为负数，也不能超过最大值，否则应该抛出异常或做截断处理。

初始磁头位置：这个值影响很大。同一个算法，初始位置不同，总移动距离可能差很多。建议在测试时多试几个初始位置，观察算法的稳定性。

方向参数：SCAN、LOOK等算法需要指定初始方向。如果方向参数和请求分布不匹配，性能会明显下降。比如所有请求都在磁头下方，但你指定向上扫描，磁头就会先跑到顶部再折返，白白浪费距离。

总距离的计算：对于CSCAN和CLOOK，从一端跳回另一端的距离是否计入总距离，不同教材有不同的处理方式。我的做法是计入，因为虽然不需要寻道，但磁头确实需要重新定位。你可以在代码中加一个开关来控制这个行为。

注意事项：在计算平均寻道长度时，分母是请求数量，不是移动次数。有些实现会把跳回动作也算作一次移动，导致平均值偏低，这是不准确的。

4. 实操中容易踩的坑与排查技巧

4.1 排序顺序导致的隐蔽Bug

SCAN和LOOK算法都需要先对请求排序。如果你用的是Arrays.sort，对于基本类型数组没问题，但如果请求存储在List<DiskRequest>中，就需要用Collections.sort并传入比较器。

我踩过的一个坑是：对请求排序后，原始的顺序信息丢失了。如果你需要同时输出“处理顺序”和“原始到达顺序”，就必须在排序前做好备份，或者在DiskRequest中保留一个序号字段。

另一个坑是重复磁道号的处理。如果两个请求的磁道号相同，排序后它们的相对顺序可能改变。对于FCFS这无所谓，但对于需要稳定排序的场景，应该使用Collections.sort的稳定版本，或者自己实现归并排序。

4.2 方向判断的逻辑陷阱

SCAN和LOOK算法中，判断一个请求在磁头的“上方”还是“下方”，用的是request.getTrackNumber() >= head还是> head？这个细节会影响磁道号恰好等于磁头位置的请求被分到哪一组。

我的建议是：把等于磁头位置的请求归入当前方向组，因为磁头不需要移动就能处理它，放在哪一组都不影响总距离，但放在当前方向组更符合直觉。

还有一个容易出错的地方是方向切换的时机。在SCAN中，磁头走到物理边缘后才切换方向；在LOOK中，磁头走到最远请求后就切换方向。如果你把LOOK实现成了SCAN，总距离会偏大；反过来，把SCAN实现成了LOOK，总距离会偏小。

4.3 常见问题速查表

4.4 性能优化的几个实用技巧

虽然模拟程序的性能不是关键，但如果你要处理大量请求（比如几万个），还是有一些优化空间的。

第一，SSTF的每次查找最近请求可以用优先队列优化，把时间复杂度从O(n²)降到O(n log n)。不过对于教学用途，O(n²)的版本更直观，没必要过度优化。

第二，排序操作可以复用。如果你要对比多个算法，可以只排序一次，然后把排序后的数组传给各个算法。但要注意，有些算法会修改数组，所以最好传副本。

第三，输出结果时，如果请求数量很大，不要逐个打印处理顺序，只打印统计指标即可。否则控制台输出会成为瓶颈。

实操心得：我在做课程设计时，喜欢把模拟结果导出成CSV格式，然后用表格软件画柱状图对比不同算法的总移动距离。这样在实验报告里展示效果非常好，比单纯列数字直观得多。

5. 从模拟到实战：这些算法在真实系统中的应用

5.1 Linux的I/O调度器演变

Linux内核的I/O调度器经历了多次演变。早期的noop调度器基本就是FCFS，后来出现了deadline和cfq。deadline调度器借鉴了SCAN的思想，但增加了超时机制，防止请求被无限期推迟。cfq则为每个进程维护独立的请求队列，试图在公平性和吞吐量之间取得平衡。

现在主流的mq-deadline和bfq调度器，核心思想仍然能看到SCAN和LOOK的影子。这说明这些经典算法虽然诞生于几十年前，但它们的核心思想至今仍然有效。

5.2 SSD时代的调度策略变化

SSD没有机械磁头，寻道时间几乎为零，所以传统的磁盘调度算法在SSD上意义不大。但SSD有擦除块、垃圾回收等特性，调度策略需要考虑的是如何减少写放大、均衡磨损，而不是减少寻道距离。

不过，这并不意味着学习磁盘调度没有价值。理解这些算法的核心思想——如何通过重新排序来减少不必要的移动——在很多其他领域都有应用。比如网络数据包调度、数据库查询优化、甚至快递配送路线规划，都能看到类似的思路。

5.3 模拟程序的扩展方向

如果你已经完成了基本的模拟程序，可以考虑以下几个扩展方向：

动态请求到达：让请求在模拟过程中动态到达，而不是一开始就给定全部请求。这样可以观察算法在动态负载下的表现，也能更真实地模拟饥饿现象。

多磁头模拟：现代磁盘可能有多个磁头，可以并行处理请求。这会把问题从一维排序变成多维调度，复杂度大幅提升。

可视化界面：用JavaFX或Swing做一个简单的可视化界面，把磁头的移动过程用动画展示出来。这对理解算法行为非常有帮助，也适合做课堂演示。

性能对比框架：写一个自动化测试框架，随机生成大量请求序列，自动运行所有算法并统计平均性能。这样可以得出更有统计意义的结论。

我个人在实际操作中的体会是，模拟程序最大的价值不在于代码本身，而在于它强迫你去思考每一个参数、每一个边界条件背后的原因。当你把FCFS、SSTF、SCAN、CSCAN、LOOK、CLOOK都亲手实现一遍，并且用各种不同的请求序列测试过之后，你对磁盘调度的理解就不再停留在课本上了。这种理解，是看多少遍书都换不来的。

最后分享一个小技巧：如果你在调试SCAN算法时发现结果总是差那么一点，不妨把磁头的移动轨迹打印出来，画成一条折线图。很多时候，看图比看代码更容易发现问题。磁头是不是多跑了一段冤枉路，折线图上一目了然。