C++实现磁盘调度算法：从FCFS到LOOK的工程实践

1. 项目概述从理论到实践的磁盘调度算法在操作系统的学习与实践中磁盘调度算法是一个绕不开的核心话题。它不仅仅是教科书上的几个公式和流程图更是直接影响系统I/O性能、关乎用户体验的关键技术。很多初学者包括当年的我在学完FCFS、SSTF、SCAN这些算法后总觉得隔着一层纱——原理懂了但它是如何在一个“活”的系统里运作的参数怎么调不同场景下到底选哪个这些问题光靠看书和做题很难有深刻的体会。这个项目的初衷就是亲手“造”一个磁盘调度算法的模拟器。我们不依赖任何图形界面库或复杂的框架就用最纯粹的C和标准库中的vector容器把教科书上的算法从静态的图示变成动态的、可观察、可测量的代码。通过这个过程你会真正理解每个算法背后的“权衡”为什么SSTF可能导致饥饿SCAN和C-SCAN的“电梯”比喻到底体现在代码的哪一行LOOK算法又是如何优化了SCAN的机械臂移动当你亲手实现它们并看到不同的请求序列下磁头移动总距离的显著差异时那种对原理的领悟是无可替代的。更重要的是我们选择vector作为核心数据结构。它动态、灵活完美契合磁盘请求队列随时可能到来的新请求这一特性。通过这个项目你不仅能巩固操作系统知识还能深入掌握C中vector的增删查改、排序、迭代器使用等实战技巧理解如何用合适的数据结构优雅地实现特定算法。这绝对是一举两得的练习。2. 核心概念与设计思路拆解在动手写代码之前我们必须把几个关键概念和设计思路理清楚。这就像盖房子前先画好图纸能避免后续很多返工。2.1 磁盘调度到底在解决什么问题想象一下磁盘的读写磁头就像唱机的唱针磁盘表面被划分为一个个同心圆的磁道。当多个进程同时发出读写磁盘的请求时这些请求的目标磁道号我们称之为“请求序列”可能是杂乱无章的。如果磁头完全按照请求到达的先后顺序FCFS去服务它可能会在磁盘表面“长途奔袭”从最外道跳到最内道再跳回中间道导致大量的寻道时间磁头移动到目标磁道所需的时间。寻道时间是磁盘I/O中最耗时的部分因此磁盘调度算法的核心目标就是重新排列服务这些请求的顺序以最小化磁头的平均寻道时间从而提高系统的整体吞吐量和响应速度。2.2 算法家族巡礼特点与适用场景我们主要实现四种经典算法它们各有千秋先来先服务FCFS最简单最公平。按请求到达顺序服务。但性能往往最差因为完全没有优化寻道路径。它的价值在于作为一个性能基准Baseline其他算法的优化效果可以与之对比。最短寻道时间优先SSTF贪心算法。总是选择当前磁头所在位置最近的那个请求进行服务。性能通常比FCFS好很多。但它的致命缺点是可能导致饥饿Starvation。如果一个请求的磁道号离当前磁头始终很远而不断有离得更近的新请求到来那么这个“远方”的请求可能永远得不到服务。扫描算法SCAN电梯算法磁头在一个方向上移动服务沿途的所有请求直到到达该方向的最后一个磁道或边界然后掉头反向移动并服务请求。就像电梯上行时只响应上行请求到了顶层再下行。它解决了SSTF的饥饿问题但对两端请求的响应时间不平均。循环扫描算法C-SCANSCAN的变种。磁头单向移动比如只从内向外服务沿途请求。到达终点后立即快速返回起点此过程不服务任何请求然后重新开始单向扫描。这样对所有请求的响应时间更公平。LOOK与C-LOOK算法这是SCAN和C-SCAN的优化版。它们并不傻傻地走到物理边界而是走到该方向上的最后一个请求的磁道就掉头或返回。这避免了无意义的空跑是实际系统中更常用的策略。我们的实现将以LOOK和C-LOOK为重点。2.3 为什么选择C和vectorC足够底层能让我们关注算法和数据结构本身而不是被高级语言或框架的抽象所干扰。性能可控适合做这种偏底层的模拟。std::vector它是实现这个项目的“神器”。动态数组请求序列的长度是不固定的vector可以动态增长完美匹配。高效的随机访问算法中需要频繁比较磁道号、计算距离vector通过下标[]或迭代器的随机访问是O(1)复杂度效率极高。强大的STL算法支持我们可以方便地使用std::sort,std::find,std::lower_bound等算法来对请求队列进行排序和查找极大简化代码。模拟请求队列我们可以用一个vectorint来代表待处理的请求队列另一个vectorint来记录服务完成的顺序清晰直观。设计思路我们将构建一个DiskScheduler类。它至少需要包含当前磁头位置、请求序列、磁道总数等属性。成员函数则包括各个调度算法的实现如schedule_FCFS(),schedule_SSTF()等每个函数都返回服务顺序和总寻道距离。通过vector的灵活操作插入、删除、排序、遍历来模拟磁头的移动和请求的服务过程。3. 核心数据结构与算法实现细节接下来我们深入到代码层面看看如何用vector这把“瑞士军刀”来实现这些算法。我会先给出核心的数据结构设计然后逐一剖析每个算法的实现要点和易错点。3.1 数据结构定义与初始化我们首先定义一个DiskScheduler类。这里做出一个关键设计决策不直接在原始请求序列上操作而是使用副本。因为每个调度算法都会改变请求的服务顺序如果直接修改原始序列那么运行完一个算法后原始序列就被破坏了无法再给下一个算法使用。#include iostream #include vector #include algorithm // 用于sort, min_element等 #include cmath // 用于abs #include climits // 用于INT_MAX class DiskScheduler { private: int currentHead; // 当前磁头位置 int totalTracks; // 磁盘总磁道数用于SCAN/C-SCAN判断边界 std::vectorint requestSequence; // 原始请求序列 public: // 构造函数 DiskScheduler(int startPos, int tracks, const std::vectorint requests) : currentHead(startPos), totalTracks(tracks), requestSequence(requests) { // 可以添加一些基本验证例如请求磁道号是否在有效范围内[0, totalTracks-1] for (int req : requests) { if (req 0 || req tracks) { std::cerr 警告请求磁道 req 超出有效范围 [0, tracks-1 ]。 std::endl; } } } // 各调度算法函数将在这里声明 std::pairstd::vectorint, int schedule_FCFS(); std::pairstd::vectorint, int schedule_SSTF(); std::pairstd::vectorint, int schedule_SCAN(char direction); // direction: inward or outward std::pairstd::vectorint, int schedule_CSCAN(char direction); std::pairstd::vectorint, int schedule_LOOK(char direction); std::pairstd::vectorint, int schedule_CLOOK(char direction); };注意totalTracks参数对于SCAN/C-SCAN是必要的因为它们需要知道物理边界0和totalTracks-1。对于LOOK/C-LOOK理论上可以不需要但保留它有助于程序的完整性也可以用于请求的合法性校验。3.2 FCFS算法实现简单但重要FCFS的实现是最直接的它几乎不涉及vector的复杂操作但它是我们测试和比较的基准。std::pairstd::vectorint, int DiskScheduler::schedule_FCFS() { std::vectorint scheduleOrder; // 记录服务顺序 int totalSeek 0; int head currentHead; // 使用局部变量不改变成员变量 for (int req : requestSequence) { scheduleOrder.push_back(req); totalSeek std::abs(head - req); // 计算寻道距离 head req; // 移动磁头 } return {scheduleOrder, totalSeek}; }要点直接遍历原始请求序列requestSequence。std::abs()用于计算绝对距离。返回一个pair包含服务顺序和总寻道距离。这样主函数可以方便地获取结果并打印。3.3 SSTF算法实现贪心的陷阱SSTF的实现开始有趣起来。我们需要在剩余的请求中反复寻找离当前磁头最近的那个。std::pairstd::vectorint, int DiskScheduler::schedule_SSTF() { std::vectorint requests requestSequence; // 关键使用副本 std::vectorint scheduleOrder; int totalSeek 0; int head currentHead; while (!requests.empty()) { // 使用迭代器和min_element算法找到最小距离的请求 auto closestIt std::min_element(requests.begin(), requests.end(), [head](int a, int b) { return std::abs(a - head) std::abs(b - head); }); // 处理找到的请求 int closestTrack *closestIt; scheduleOrder.push_back(closestTrack); totalSeek std::abs(head - closestTrack); head closestTrack; // 关键步骤从待处理列表中删除已服务的请求 requests.erase(closestIt); } return {scheduleOrder, totalSeek}; }核心技巧与避坑指南一定要用副本std::vectorint requests requestSequence;这行代码至关重要。否则运行一次SSTF后原始请求序列就空了。使用std::min_element与Lambda表达式这是C STL的优雅之处。min_element返回指向最小元素的迭代器。我们传入一个Lambda表达式作为自定义比较器比较的标准是到当前head的距离。这比手动写循环遍历找最小值更简洁、更不易出错。删除元素requests.erase(closestIt)用于删除已服务的请求。注意erase会使指向被删除元素及其后元素的迭代器失效但因为我们每次循环都重新调用min_element从头查找所以没有问题。如果要在循环中复用迭代器则需要更谨慎的处理如it requests.erase(it)的模式。3.4 LOOK算法实现高效的“电梯”LOOK是SCAN的优化也是实际中最常用的算法之一。它的实现比SSTF稍复杂需要处理方向和对请求序列的排序。std::pairstd::vectorint, int DiskScheduler::schedule_LOOK(char direction) { std::vectorint requests requestSequence; // 使用副本 std::vectorint scheduleOrder; int totalSeek 0; int head currentHead; // 对请求排序这是LOOK/SCAN类算法的前提 std::sort(requests.begin(), requests.end()); // 确定初始扫描方向上的请求子集 // 使用lower_bound找到第一个大于等于head的位置 auto it std::lower_bound(requests.begin(), requests.end(), head); std::vectorint left(requests.begin(), it); // 小于head的请求逆序 std::vectorint right(it, requests.end()); // 大于等于head的请求 if (direction o || direction O) { // 向外磁道号增大 // 先服务右侧向外的方向 for (int track : right) { scheduleOrder.push_back(track); totalSeek std::abs(head - track); head track; } // 掉头服务左侧需要逆序因为磁头向内移动 std::reverse(left.begin(), left.end()); for (int track : left) { scheduleOrder.push_back(track); totalSeek std::abs(head - track); head track; } } else { // 向内磁道号减小默认或i // 先服务左侧需要逆序因为当前head在右侧向左移动 std::reverse(left.begin(), left.end()); for (int track : left) { scheduleOrder.push_back(track); totalSeek std::abs(head - track); head track; } // 掉头服务右侧 for (int track : right) { scheduleOrder.push_back(track); totalSeek std::abs(head - track); head track; } } return {scheduleOrder, totalSeek}; }实现解析与难点排序std::sort(requests.begin(), requests.end())。LOOK算法需要知道请求的全局分布排序是第一步。分割请求队列使用std::lower_bound找到第一个不小于head的请求位置。它将排序后的队列分割成left小于head和right大于等于head两部分。lower_bound使用二分查找效率是O(log n)。方向处理这是最容易混淆的地方。代码中通过direction参数控制初始移动方向。向外‘o’先遍历right从小到大然后反转left从大到小再遍历。因为掉头后磁头是向内移动需要服务比当前head此时已在最右更小的磁道所以left需要逆序。向内‘i’先反转left从大到小并遍历然后遍历right从小到大。原理类似。SCAN算法的实现如果你需要实现标准的SCAN走到物理边界只需在LOOK的基础上在服务完一个方向后先让磁头移动到边界0或totalTracks-1并把这部分移动距离加到totalSeek中然后再掉头。代码结构类似但增加了边界移动的逻辑。3.5 C-LOOK算法实现更公平的循环C-LOOK是C-SCAN的优化版实现上与LOOK类似但“掉头”的逻辑不同。std::pairstd::vectorint, int DiskScheduler::schedule_CLOOK(char direction) { std::vectorint requests requestSequence; std::vectorint scheduleOrder; int totalSeek 0; int head currentHead; std::sort(requests.begin(), requests.end()); auto it std::lower_bound(requests.begin(), requests.end(), head); std::vectorint left(requests.begin(), it); std::vectorint right(it, requests.end()); if (direction o || direction O) { // 向外扫描 for (int track : right) { scheduleOrder.push_back(track); totalSeek std::abs(head - track); head track; } // C-LOOK关键点从最左端重新开始而不是掉头 // 如果左侧有请求磁头需要“快速返回”到左侧第一个请求 if (!left.empty()) { totalSeek std::abs(head - left.front()); // 快速返回的距离 head left.front(); for (int track : left) { // 左侧请求已经是升序直接遍历 scheduleOrder.push_back(track); totalSeek std::abs(head - track); head track; } } } else { // 向内扫描逻辑对称 // 注意向内扫描时left需要逆序从大到小服务 std::reverse(left.begin(), left.end()); for (int track : left) { scheduleOrder.push_back(track); totalSeek std::abs(head - track); head track; } // 快速返回到右侧第一个请求 if (!right.empty()) { totalSeek std::abs(head - right.front()); head right.front(); for (int track : right) { scheduleOrder.push_back(track); totalSeek std::abs(head - track); head track; } } } return {scheduleOrder, totalSeek}; }C-LOOK与LOOK的核心区别LOOK服务完一个方向后掉头反向服务。C-LOOK服务完一个方向后直接跳到另一个方向的起始端快速返回然后继续同方向扫描。在代码中体现为服务完right后不是反转left而是直接跳到left.front()然后顺序服务left。这保证了所有请求的等待时间相对更公平。4. 完整模拟程序与测试案例分析有了核心算法函数我们需要一个主程序来驱动测试并直观地展示不同算法的效果。我们将设计一个交互性较强的控制台程序。4.1 主程序框架与交互设计#include iomanip // 用于格式化输出 void printSchedule(const std::string algoName, const std::pairstd::vectorint, int result) { std::cout \n algoName 调度结果 std::endl; std::cout 服务顺序: ; for (size_t i 0; i result.first.size(); i) { std::cout result.first[i]; if (i ! result.first.size() - 1) std::cout - ; } std::cout \n总寻道距离: result.second std::endl; std::cout 平均寻道长度: std::fixed std::setprecision(2) static_castdouble(result.second) / result.first.size() std::endl; } int main() { // 模拟参数设置 int startHead 100; int totalTracks 200; // 假设磁道号0-199 std::vectorint requests {55, 58, 39, 18, 90, 160, 150, 38, 184}; DiskScheduler scheduler(startHead, totalTracks, requests); std::cout 初始磁头位置: startHead std::endl; std::cout 请求序列: ; for (int r : requests) std::cout r ; std::cout std::endl; // 测试不同算法 auto fcfsResult scheduler.schedule_FCFS(); printSchedule(FCFS, fcfsResult); auto sstfResult scheduler.schedule_SSTF(); printSchedule(SSTF, sstfResult); // LOOK算法可以测试不同方向 auto lookOutResult scheduler.schedule_LOOK(o); printSchedule(LOOK (向外), lookOutResult); auto lookInResult scheduler.schedule_LOOK(i); printSchedule(LOOK (向内), lookInResult); auto clookResult scheduler.schedule_CLOOK(o); printSchedule(C-LOOK (向外), clookResult); return 0; }4.2 测试案例深度解析让我们用上面的请求序列{55, 58, 39, 18, 90, 160, 150, 38, 184}磁头起始于100号磁道来分析一下。FCFS结果 服务顺序55 - 58 - 39 - 18 - 90 - 160 - 150 - 38 - 184 总寻道距离 |100-55||55-58||58-39||39-18||18-90||90-160||160-150||150-38||38-184| 4531921727010112146 498可以看到磁头来回剧烈摆动从100跳到55向内又跳到58向外再跳回39向内……效率很低。SSTF结果从100开始最近的是90距离10服务90。从90开始最近的是58距离32但58和55都距离32这里就涉及min_element在距离相等时的选择它会选择第一个遇到的取决于vector的顺序。假设先找到58服务58。从58开始最近的是55距离3服务55。从55开始最近的是39距离16但39和38呢同样问题。假设先服务39。以此类推……最终顺序可能是90, 58, 55, 39, 38, 18, 150, 160, 184。 总寻道距离会远小于FCFS可能约在200-250之间。但注意如果请求18一直离得很远而90、58、55附近不断有新请求18可能被“饿死”。LOOK (向外) 结果排序后请求: [18, 38, 39, 55, 58, 90, 150, 160, 184]当前head100lower_bound找到right[150, 160, 184]100left[18,38,39,55,58,90]100。向外扫描服务150, 160, 184。掉头此时head184反转left得到[90, 58, 55, 39, 38, 18]服务它们。 服务顺序150 - 160 - 184 - 90 - 58 - 55 - 39 - 38 - 18 总寻道距离 (100-150)(150-160)(160-184)(184-90)(90-58)(58-55)(55-39)(39-38)(38-18) 5010249432316120 250这个距离比FCFS好很多并且没有饥饿问题。C-LOOK (向外) 结果同LOOK先服务right: 150, 160, 184。快速返回从184直接跳到left的第一个元素90。距离184-9094。然后顺序服务left: 90, 58, 55, 39, 38, 18。 服务顺序150 - 160 - 184 - 90 - 58 - 55 - 39 - 38 - 18 顺序看起来和LOOK一样注意虽然顺序一样但寻道距离的计算不同。在服务完184后LOOK是掉头移动到90距离94而C-LOOK是“快速返回”到90距离也是94。在这个特定序列下两者总距离巧合相同。但如果left的第一个请求不是90而是18那么LOOK掉头需要从184走到18距离很大而C-LOOK快速返回的距离是184到18和LOOK一样。但C-LOOK的设计哲学是单向循环对所有请求的响应时间方差更小。通过这个对比你可以清晰地看到不同算法在同一组数据下的表现差异。动手修改请求序列和起始位置观察结果的变化是理解这些算法行为的最佳方式。5. 性能考量、扩展性与常见问题在实现基础功能后我们可以从工程和优化的角度思考更多。5.1 时间复杂度分析FCFS: O(n)只需一次遍历。SSTF: O(n²)。因为每次服务一个请求都需要在剩余列表中线性搜索min_element是O(k)k为剩余请求数最近的那个。对于n个请求总复杂度是n(n-1)...1 O(n²)。这是SSTF的一个缺点当请求队列很长时调度器本身的计算开销会变大。可以使用优先队列如std::priority_queue进行优化将查找最近请求的复杂度降到O(log n)总体复杂度降至O(n log n)。LOOK/C-LOOK/SCAN/C-SCAN: O(n log n)。主要开销在于初始的排序std::sort其平均复杂度为O(n log n)。之后的扫描过程是线性的O(n)。因此对于请求数较多的情况这些算法的预处理开销是值得的因为它们能提供更稳定、更优的整体性能。5.2 如何模拟动态请求到达我们的实现是静态的即所有请求一开始就已知。但在真实操作系统中请求是动态到达的。如何模拟一个简单的思路是引入“时间”概念。我们可以维护一个“当前时间”每个请求有一个“到达时间”。调度器在每个时刻只从“已到达”的请求中进行调度。这需要更复杂的事件驱动模拟但核心的调度算法逻辑不变只是每次调度的候选集是“已到达且未服务”的请求子集。5.3 常见问题与调试技巧请求磁道号越界在构造函数或添加请求时务必检查磁道号是否在[0, totalTracks-1]范围内。否则在计算距离或判断方向时可能出现逻辑错误。空请求序列处理如果requestSequence为空你的算法函数应该能优雅处理返回空的服务顺序和0寻道距离。在SSTF的while循环和LOOK的lower_bound前添加空判断是个好习惯。方向参数校验schedule_LOOK和schedule_CSCAN中的direction参数应该只接受有效的字符如‘i’, ‘I’, ‘o’, ‘O’并为无效输入提供默认值或错误提示。迭代器失效在SSTF中我们在循环内调用了requests.erase(closestIt)。正如之前提到的这会使closestIt失效。因为我们每次循环都重新计算closestIt所以安全。但如果想优化在删除后使用erase返回的新的迭代器作为下一轮查找的起点需要小心处理边界条件。浮点数比较计算平均寻道长度时注意整数除法会截断小数。务必先转换为double再相除并使用std::setprecision控制输出精度。可视化调试对于复杂的序列在纸上画出磁道轴手动模拟一遍算法的步骤再与程序输出对比是排查逻辑错误最有效的方法。也可以在每个算法内部添加一些调试输出打印出每一步磁头的位置和选择的请求。5.4 项目扩展方向这个基础模拟器可以作为一个起点进行很多有意义的扩展实现更多算法如N-Step-SCAN将请求队列分成长度为N的子队列每个子队列内用SCAN、F-SCAN在扫描期间冻结新到的请求等本次扫描完再处理等。图形化界面使用如Qt、SFML或简单的Web前端Emscripten编译到WebAssembly将调度过程动画展示出来磁头移动、请求服务过程一目了然。性能对比与统计分析自动生成大量随机请求序列批量运行所有算法统计平均寻道距离、平均响应时间、标准差等指标用图表如控制台打印表格或生成CSV文件直观对比。集成到简单OS模拟器中将这个磁盘调度模块作为你编写的简易操作系统课程设计项目的一部分模拟进程发出I/O请求并被调度的完整过程。通过这个从零实现磁盘调度算法的项目你收获的远不止是几个C函数。你深入理解了操作系统核心组件的工作原理掌握了用恰当的数据结构vector实现复杂算法的方法并锻炼了将理论转化为实践的能力。下次当你听到“电梯算法”或“磁盘调度”时你脑海中浮现的将不再是枯燥的定义而是一行行自己写过的、让磁头高效移动的代码。这才是真正意义上的“学会”。