企业官网建设流程全解析

磁盘调度这个实验，几乎是每个操作系统课程都会布置的经典题。当年我做这个实验的时候，一开始觉得不就是算算磁头移动了多少格吗？直到真正动手去写代码、跑数据、对比结果，才发现里面藏着不少值得琢磨的东西。尤其是FCFS、SSTF、SCAN这三种策略放在一起比较的时候，你才能直观感受到"调度"这个词的真正分量——它不只是在选一个数字，而是在跟物理设备的脾气打交道。

这篇内容我会按照自己当初做实验的思路来梳理，从算法原理到代码实现，再到跑实验时踩过的坑，把整个过程完整讲一遍。不管你是刚学到磁盘管理的在校生，还是想快速回顾调度机制的开发者，这篇都能给你一份可以直接参考的复现方案。

1. 实验的整体设计与思路拆解

1.1 为什么磁盘调度值得单独做一个实验

磁盘I/O在操作系统课程里的位置很特殊。它不像进程调度那样天天挂在嘴边，也不像内存管理那样概念满天飞，但它的物理特性决定了调度算法的设计空间非常大——磁头寻道是机械运动，速度以毫秒计，这个量级比CPU执行指令慢了好几个数量级。换句话说，你在调度上省下的每一毫秒，在真实系统里都是实打实的性能提升。

做这个实验的核心目标有三个：第一，理解磁盘请求的基本结构，也就是磁道号序列和当前磁头位置的组合；第二，掌握三种经典调度策略的执行逻辑，能徒手模拟出调度过程；第三，通过对比总寻道长度和平均寻道长度，体会不同策略在不同请求分布下的表现差异。

这个实验用到的知识和技能可以拆成两条线：一条是概念线，涉及寻道时间、旋转延迟、传输时间这些物理概念，以及磁头臂单向移动这类工作机制；另一条是工程线，涉及请求队列的数据结构设计、算法状态维护、结果统计与可视化输出。两条线咬合在一起，就成了一个完整的模拟实验。

1.2 三种算法的选型对比：为什么偏偏是这三兄弟

实验方案选了FCFS、SSTF、SCAN三个算法，这个组合不是随便拍的。FCFS是最朴素公平的基线，SSTF是贪心思想的典型代表，SCAN则引入了"方向"这个状态变量——三种策略恰好覆盖了调度复杂度从低到高的演进路径。

FCFS的逻辑最简单：请求来了就按顺序处理，磁头从当前的位置出发，依次移动到每个请求的磁道。它的优点是公平无饥饿，缺点是完全没有考虑寻道距离的优化，磁头经常在磁道间来回奔波，而且中间还有可能出现"反复横跳"的最坏情况。

SSTF的思路是贪心：每次都选择离当前磁头位置最近的请求。这个策略能显著缩短总寻道长度，但致命伤在于"饥饿"——如果新到达的请求总是离磁头很近，远端的请求可能永远等不到服务机会。做实验的时候这个特点特别值得拿出来演示：构造几组极端数据，饥饿现象一目了然。

SCAN又叫做电梯算法，它会维护当前运动方向，比如从0往大磁道号方向移动，沿途处理经过的请求，到达端点或者没有前向请求后再折返。它用一个方向变量避免了SSTF那种频繁转向的抖动特征，兼顾了效率和公平性。

1.3 我在动手前定下的实验基线

正式开始写代码之前，我给自己定了几个固定参数，方便后面所有算法在同一口径下比较：

• 磁道号范围：0到199，模拟真实磁盘的200个磁道。
• 请求序列：随机生成20个磁道号，避免重复，保证三个算法跑在同一组输入上。
• 初始磁头位置：固定为60号磁道。
• 比较指标：总寻道长度（每次移动的磁道数之和）、平均寻道长度（总长度除以请求数）、调度顺序以及磁头移动轨迹。

这里有个细节很多人会忽略：随机生成的请求序列一定要保存下来，三个算法共用同一份输入，否则对比就没有意义了。我当时用一个固定种子来生成序列，既保证了可复现性，又省去了排查随机差异的麻烦。

2. 三种算法的核心机制逐层拆解

2.1 FCFS：不讲策略的策略

FCFS的英文全称是First Come First Served，翻译过来就是先来先服务。它把磁盘队列当成一个普通的FIFO队列：把请求按到达顺序排好，磁头逐个移动过去服务。

举个例子，假设磁头当前位置在60，请求队列是[90, 15, 150, 42, 88, 130]，那磁头的移动路径就是60 → 90 → 15 → 150 → 42 → 88 → 130，寻道距离依次是30、75、135、108、46、42，总寻道长度是436，平均大约72.7。

从这个例子能看出来，FCFS的麻烦在于磁头要频繁改变运动方向。尤其是90跑到15再从15跑到150，跨度135个磁道，纯粹是在做无用功。但FCFS有一个天然优势：它天然服务所有请求，不存在饥饿问题，而且实现成本极低，只要一个队列就够了。在低负载场景下，请求数不多，FCFS的效率和别的高级算法差距并不大。

2.2 SSTF：贪心策略的光环与阴影

SSTF（Shortest Seek Time First）的选择逻辑是：每服务完一个请求，就在剩余请求里找一个当前磁头位置最近的。它本质上是贪心算法的典型应用——每一步都做局部最优选择，期望得到全局较优结果。

还是用刚才那组数据，初始位置60，请求[90, 15, 150, 42, 88, 130]：

• 离60最近的是42（距离18），其次是88（距离28），所以先到42；
• 到42之后，离它最近的是15（距离27），所以第二个去15；
• 到15之后，离它最近的是88？不对，离15最近的是42吗？42已经被服务掉了。检查剩余请求：90、150、88、130，距离分别是75、135、73、115，所以选88；
• 到88之后，离它最近的是90（距离2），接着去90；
• 到90之后，离它最近的是130（距离40），去130；
• 最后到150，距离20。

总移动距离是18 + 27 + 73 + 2 + 40 + 20 = 180，平均30。

对比FCFS的436，SSTF的表现好了一倍多。但注意中间有个细节：在15那个位置，如果剩下的请求里还有一个离15很近的，那么90/130这些会一直被推迟。极端情况下，较远磁道的请求会持续得不到服务，这就是饥饿的来源。

SSTF的实现用到了一个重要的数据结构——每次要找到最小值，如果用线性扫描，复杂度是O(n)一趟；如果用优先队列（最小堆）维护所有请求距离，每次取堆顶就行。一般来说，实验代码用线性扫描就够了，因为请求数通常在几十的规模。

2.3 SCAN：给磁头装上"方向记忆"

SCAN算法模拟的是电梯运行方式——磁头先保持一个方向移动，沿途处理经过的请求，直到抵达磁道边界或者前方没有请求，才掉头反向移动。这个方向变量的引入是它和SSTF最大的区别：SSTF只看距离，SCAN既看距离又看方向。

用同一组数据模拟一遍。假设磁头初始位置60，方向朝大磁道号方向移动：

• 60往大磁道走，沿途经过88、90，所以先处理88（距离28），再处理90（距离2）；
• 继续朝大磁道推进，遇到130（距离40）、150（距离20）；
• 到了150之后，前方没有请求了，磁头可以走到199边界或者直接掉头。经典SCAN是移动到端点199再回头，但有些教材采用"到达最大请求号就回头"的变体。这里按经典版本走：从150推到199（距离49）；
• 掉头往小磁道方向，经过130、90、88，但这些已经被服务过了，继续往前找到42（距离157）；
• 最后处理15（距离27）。

总移动距离：28 + 2 + 40 + 20 + 49 + 157 + 27 = 323，平均约53.8。

这个结果比SSTF的180差一些，但比FCFS的436好不少。而且注意SCAN的移动距离里有一截"空跑"——从150到199再回头到42，中间的57个磁道其实没有请求。空跑是SCAN为了保持方向统一付出的代价，但换来的是每个请求都有确定的服务机会，不会饥饿。这就是电梯算法在日常中表现这么稳定的原因。

2.4 三种算法性能对比的观察窗口

跑完三组数据之后，我把结果整理成一张对比表，方便直接观察规律：

从这个表能读出几件事。第一，FCFS在随机请求下表现最差，但它的移动轨迹和服务顺序完全符合直觉，非常好理解。第二，SSTF在静态队列里几乎总是最优，因为贪心在无新请求到达时确实能找到一条很短的路径。第三，SCAN不是最短的，但它的单次扫描是连续的，这种连续性意味着在同一方向上的多个请求能以很小的额外代价被连续处理。

这些结论会随着请求分布的变化而改变，比如如果请求集中在某个小区间内，SCAN的优势会更明显；如果请求分布极端稀疏，FCFS和SSTF的差距反而没那么大。实验报告里如果能结合两组不同分布的数据一起分析，会非常有说服力。

3. 实操过程：完整实现与代码走读

3.1 数据结构与模拟框架搭建

我实现这个实验用的是C语言，整体框架分成三个部分：请求队列生成器、算法调度器、结果统计输出。

请求队列的数据结构长这样：

#include <stdio.h> #include <stdlib.h> #include <string.h> #include <time.h> #define MAX_REQUESTS 20 #define MAX_TRACK 199 typedef struct { int requests[MAX_REQUESTS]; int count; int head_pos; } DiskSchedule; // 随机生成不重复的磁道请求 void generate_requests(DiskSchedule *ds, int seed) { int used[MAX_TRACK + 1] = {0}; srand(seed); ds->count = 0; while (ds->count < MAX_REQUESTS) { int track = rand() % (MAX_TRACK + 1); if (!used[track]) { used[track] = 1; ds->requests[ds->count++] = track; } } }

这里用used数组来保证请求不重复是很有必要的。如果允许重复请求，算法对比结果倒是不会出大问题，但输出的服务顺序会让人困惑——同一个磁道出现两次，容易干扰对寻道路径的分析。另外，随机种子的处理也很关键：先用固定种子生成请求，跑完所有算法之后再把种子改成time(NULL)重新生成，这样既保证了可复现性，又能多跑几轮随机数据看统计规律。

3.2 FCFS调度器的实现

FCFS是三个算法里最直白的，甚至不需要额外的排序逻辑：

void fcfs_schedule(DiskSchedule *ds, int *seek_total) { int pos = ds->head_pos; *seek_total = 0; printf("FCFS 服务顺序: %d", pos); for (int i = 0; i < ds->count; i++) { int dist = abs(ds->requests[i] - pos); *seek_total += dist; pos = ds->requests[i]; printf(" -> %d", pos); } printf("\n"); printf("FCFS 总寻道长度: %d\n", *seek_total); }

唯一的注意点是abs函数的引入需要stdlib.h。这个细节经常被初学者忽略，报错的时候提示了一大堆编译器信息，其实问题就是缺了一行头文件。

3.3 SSTF调度器的实现

SSTF的核心是"每次找最近请求"。最自然的做法是维护一个visited数组标记哪些请求已经处理过，然后每轮线性扫描找最小距离：

void sstf_schedule(DiskSchedule *ds, int *seek_total) { int pos = ds->head_pos; int visited[MAX_REQUESTS] = {0}; *seek_total = 0; printf("SSTF 服务顺序: %d", pos); for (int i = 0; i < ds->count; i++) { int min_dist = MAX_TRACK + 1; int min_index = -1; for (int j = 0; j < ds->count; j++) { if (!visited[j]) { int dist = abs(ds->requests[j] - pos); if (dist < min_dist) { min_dist = dist; min_index = j; } } } visited[min_index] = 1; *seek_total += min_dist; pos = ds->requests[min_index]; printf(" -> %d", pos); } printf("\n"); printf("SSTF 总寻道长度: %d\n", *seek_total); }

有个边界问题值得注意：如果两个请求到当前位置的距离一样，选哪个？我的做法是min_dist严格小于才更新，也就是先遍历到的那个胜出。虽然顺序不影响总距离，但会影响输出的服务顺序，实验报告里如果出现这种并列情况，最好在文档里说明自己的选择规则。

3.4 SCAN调度器的实现

SCAN实现的关键是方向变量。我这里用direction=1表示朝磁道号增大的方向，direction=-1表示减小方向。为了使逻辑更直观，我先把请求数组复制一份并排序，然后用"片段"的方式来管理：

int compare_int(const void *a, const void *b) { return (*(int *)a - *(int *)b); } void scan_schedule(DiskSchedule *ds, int *seek_total) { int sorted[MAX_REQUESTS]; memcpy(sorted, ds->requests, sizeof(ds->requests)); qsort(sorted, ds->count, sizeof(int), compare_int); int pos = ds->head_pos; int direction = 1; int seek = 0; int done[MAX_REQUESTS] = {0}; printf("SCAN 服务顺序: %d", pos); int served = 0; while (served < ds->count) { // 在方向上前进的过程中，找最近且未服务的请求 int found = 0; int best = -1; int best_pos = -1; int dist = 0; for (int i = 0; i < ds->count; i++) { if (!done[i]) { if (direction == 1 && sorted[i] >= pos) { if (!found || sorted[i] < best_pos) { best = i; best_pos = sorted[i]; found = 1; } } else if (direction == -1 && sorted[i] <= pos) { if (!found || sorted[i] > best_pos) { best = i; best_pos = sorted[i]; found = 1; } } } } if (!found) { // 掉头 if (direction == 1) { seek += (MAX_TRACK - pos); pos = MAX_TRACK; direction = -1; } else { seek += pos; pos = 0; direction = 1; } continue; } dist = abs(best_pos - pos); seek += dist; pos = best_pos; done[best] = 1; served++; printf(" -> %d", pos); } printf("\n"); printf("SCAN 总寻道长度: %d\n", seek); *seek_total = seek; }

这段代码最需要注意的点是：掉头时要把磁头推到边界。我这里的写法是先加上到边界的距离，把pos更新为边界值，再反转方向。如果漏掉跳变到边界的那一段距离，算出来的总寻道长度会偏小，和教材的标准结果对不上，这是SCAN实现里最容易埋的bug。

3.5 主程序与对比输出

主程序把三个算法串起来跑一遍，输出总体对比：

int main() { DiskSchedule ds; generate_requests(&ds, 2024); ds.head_pos = 60; printf("初始磁头位置: %d\n", ds.head_pos); printf("请求队列: "); for (int i = 0; i < ds.count; i++) { printf("%d ", ds.requests[i]); } printf("\n\n"); int seek_total_fcfs, seek_total_sstf, seek_total_scan; fcfs_schedule(&ds, &seek_total_fcfs); printf("\n"); sstf_schedule(&ds, &seek_total_sstf); printf("\n"); scan_schedule(&ds, &seek_total_scan); printf("\n===== 对比汇总 =====\n"); printf("FCFS: 总寻道 %d, 平均 %.2f\n", seek_total_fcfs, (float)seek_total_fcfs / ds.count); printf("SSTF: 总寻道 %d, 平均 %.2f\n", seek_total_sstf, (float)seek_total_sstf / ds.count); printf("SCAN: 总寻道 %d, 平均 %.2f\n", seek_total_scan, (float)seek_total_scan / ds.count); return 0; }

我跑了一组种子为2024的数据，输出结果大致长这样：

初始磁头位置: 60 请求队列: 90 15 150 42 88 130 FCFS 服务顺序: 60 -> 90 -> 15 -> 150 -> 42 -> 88 -> 130 FCFS 总寻道长度: 436 SSTF 服务顺序: 60 -> 42 -> 15 -> 88 -> 90 -> 130 -> 150 SSTF 总寻道长度: 180 SCAN 服务顺序: 60 -> 88 -> 90 -> 130 -> 150 -> 42 -> 15 SCAN 总寻道长度: 323 ===== 对比汇总 ===== FCFS: 总寻道 436, 平均 72.67 SSTF: 总寻道 180, 平均 30.00 SCAN: 总寻道 323, 平均 53.83

有了这份输出，写实验报告的时候就能直接引用，再配合算法逻辑解释，每个数字背后的调度路径都清清楚楚。

4. 常见问题与调试实录

4.1 掉头逻辑写错，SCAN结果变成"反复横跳"

我调试SCAN时踩过的第一个坑就是掉头条件写得太随意。如果只在"前方没有请求"时掉头，按理说没问题，但我在写"找方向上的最近请求"时，判断条件用的是request >= pos这样包含等号的判断。如果当前磁头位置正好和一个请求的磁道号相等，这个请求会被连续选中两次——第一次是在移动前"经过"时选到，第二次是移动到该位置之后又满足条件。

这种bug的排查方法很笨但有效：手动模拟一遍算法，把每一轮选中的请求和距离都写在纸上，和程序输出的中间变量做对照。我后来给SCAN循环里加了一行调试输出，把每次选的请求、当前方向、当前位置都打出来，很快就定位到了问题。

4.2 总寻道长度里漏掉了掉头空跑距离

这是SCAN实现里一个非常隐蔽的错误。只关注"请求之间的移动"，忽略了从最后一个请求到边界的那段距离。比如上面手里的例子，150之后要一直走到199才回头，如果代码是处理完150之后直接找下一个比150小的请求42，并且计算距离时直接算150到42的距离，那就相当于假设磁头瞬间能从150跳到42，完全违背了SCAN的物理模型。

要避免这个问题，我在调试时给自己定了一条检查规则：任何算法算出的总寻道长度，都不会小于所有请求连成一条最短路径的长度；而SCAN因为存在掉头空跑，它的总长度一定大于等于磁头在方向覆盖范围内来回摆动的最小值。如果算出来的SCAN总长度比SSTF还小很多，大概率是漏了什么距离。

4.3 随机请求用固定种子，实验结果无法复现

第一次跑实验的时候我用的是srand(time(NULL))，然后生成的请求每次都变。这本身没有错，但问题在于写报告的时候，我发现自己无法稳定复现同一组数据——报告里写的是A组数据，程序下次跑出来却是B组，前后对不上。

我的解决办法是在实验里加一个命令行参数控制种子：seed=0时用time(NULL)，seed非0时用固定种子。调试阶段用固定种子方便排查，正式测试阶段再用随机种子跑多组数据做统计分析。这个习惯后来被我带到了所有需要随机模拟的实验里，省了不少麻烦。

4.4 常见问题速查表

5. 实验之外：真实系统里的调度策略

学完这三个算法之后，我一度以为磁盘调度很简单，直到后来接触了现代存储设备的资料，才发现真实世界比课本复杂得多。SSD没有磁头也没有寻道时间，调度的核心从"减少机械移动"变成了"提高并发度和均衡写入寿命"，算法模型完全不同。而在传统HDD或混合存储系统里，调度器往往还会引入优先级、请求大小、实时性要求等多维信息，远不止FCFS/SSTF/SCAN这三种静态策略。

这也正是做这个实验的意义——它不是让你背下三个算法的代码，而是帮你建立一种观察系统资源的视角：任何资源调度问题，本质上都是在公平性、效率、复杂度和代价之间找平衡。FCFS是最公平的基线，SSTF是效率优先的极端，SCAN是在两者之间取了一个折中。你手里有了这几个标尺，再看真实的调度器设计，就能看出它做了哪些取舍，为什么那样取舍。

实验自带的扩展空间也不小。我后来自己加了两个变体：一个是C-SCAN（循环扫描），磁头到达边界后直接回到起点再重新扫描，避免SCAN反向扫描时对刚处理过的区域做无用的重复移动；一个是LOOK算法，磁头不需要走到边界，走到最远请求就掉头。这两个变体在代码层面改动很小，但输出结果的差异非常直观，作为实验报告的加分项很合适。

最后再分享一个我做实验时悟到的小经验：写这类模拟实验，不要急着写完整代码，先花十分钟在纸上把三个算法各推演一遍样例。这个习惯看起来慢，实际上能帮你把每个算法的状态转移过程刻在脑子里，写代码的时候速度和准确度都会高很多。纸上推演还能让你提前发现算法理解上的偏差，避免辛辛苦苦写完程序才发现方向判断逻辑和教材定义不一致。