1. 项目概述从磁盘寻道到代码实现最近在整理一些经典的操作系统算法实现SCAN算法也叫电梯算法是绕不开的一个。它最初是为磁盘臂调度设计的核心思想是模仿电梯的运行方式磁头或电梯在一个方向上移动服务沿途的所有请求直到到达该方向的尽头然后掉头继续服务反方向的请求。这个算法在平衡效率和公平性上做得相当不错避免了像先来先服务FCFS那样的低效也比最短寻道时间优先SSTF更公平不会让边缘的请求“饿死”。我这次实现的是一个非常朴素的C版本。说它“朴素”是因为它剥离了所有复杂的工程外壳比如多线程、实时请求队列、图形化界面等只聚焦于算法最核心的逻辑本身。这就像学做菜先搞清楚怎么把西红柿炒鸡蛋炒好再去研究满汉全席。这个版本非常适合初学者理解SCAN算法的骨架也适合老手快速回顾其核心思想。代码结构清晰每一步都有注释你完全可以把它当作一个“算法模板”来使用和修改。2. 算法核心思想与设计思路拆解2.1 为什么是“电梯算法”SCAN算法的得名非常形象。想象一下你在一栋高楼里等电梯。电梯的运作模式通常是假设它当前在10楼向上运行那么它会依次响应11楼、12楼...直到最高层比如20楼的所有上行请求。到达20楼后它不会立刻掉头而是会继续“扫描”完这个方向上的所有请求后再改变方向向下运行依次响应19楼、18楼...的请求。映射到磁盘调度上电梯轿厢-磁盘读写磁头楼层-磁道号Cylinder乘客的上下楼请求-进程的磁盘I/O请求需要访问的磁道号电梯的运行方向-磁头的移动方向向内/向外或向磁道号增大/减小方向这种设计带来了两个核心优势较好的平均寻道时间由于磁头持续朝一个方向移动避免了像FCFS那样可能出现的“磁头反复横跳”的极端低效情况。避免了“饥饿”现象在SSTF算法中如果不断有新的请求出现在磁头当前位置附近那么远处磁道的请求可能永远得不到服务。而SCAN算法保证了无论请求在哪个磁道只要磁头扫描过那个方向就一定会被服务到公平性更好。2.2 算法流程的朴素拆解要实现这个算法我们需要明确几个关键状态和步骤初始化我们需要知道磁头从哪里开始current_track初始向哪个方向移动direction通常用true表示向磁道号增大方向false表示减小方向以及当前所有待处理的请求队列request_queue。请求排序与分组这是算法的核心预处理步骤。根据当前磁头位置和方向将请求队列分为两部分在当前移动方向“前方”的请求和“后方”的请求。例如磁头在50方向向上增大那么所有大于50的请求是“前方”请求所有小于等于50的请求是“后方”请求。服务当前方向请求对“前方”的请求按照距离当前磁头位置的远近进行排序如果是向上就按升序排列。然后磁头依次移动到这些请求所在的磁道完成服务并从队列中移除该请求。这个过程会一直持续到“前方”没有更多请求即到达了该方向上的最大请求磁道或者我们预设的磁盘边界。调转方向当一个方向的服务完成后改变磁头移动方向。服务反方向请求对“后方”的请求此时它们已经变成了新方向的“前方”请求按照新方向的顺序排序如果现在方向向下就按降序排列然后重复步骤3的服务过程。循环与终止持续进行方向判断、请求分组、排序和服务的过程直到所有请求都被处理完毕。这个流程听起来简单但在代码实现时对数据结构的选取和边界条件的处理是决定代码是否清晰、健壮的关键。2.3 数据结构选型为什么用向量Vector在这个朴素实现中我选择了C标准模板库STL中的std::vector来存储磁盘请求队列。这是经过权衡的std::vector的优势动态数组支持随机访问内存连续缓存友好。对于我们这个需要频繁排序和按索引访问的场景来说性能很好。sort()算法对vector的排序效率很高。为什么不直接用std::listlist是双向链表插入删除效率高但不支持随机访问排序效率低于vector。在我们的算法中每次服务一个请求后是“逻辑移除”不再考虑而非必须从容器中物理删除所以vector的删除劣势不明显。相反我们需要频繁排序vector更合适。为什么不使用std::priority_queue优先队列堆能高效获取下一个最近请求这更像是SSTF算法的思路。SCAN算法需要的是按方向分组后对组内请求进行排序这是一个批处理排序的过程而非动态的实时获取下一个最近点。使用vector配合sort()更直观地体现了“扫描”这一批处理特性。注意在更复杂的、请求动态到达的实时系统中可能需要结合队列和有序数据结构。但在这个用于理解算法本质的朴素版中vector的简单和清晰是首要目标。3. 代码实现详解与核心环节剖析下面我将结合代码片段一步步拆解这个朴素SCAN算法的C实现。我会先给出关键函数的框架然后深入每个部分的细节。3.1 头文件与全局定义#include iostream #include vector #include algorithm // 用于sort函数 #include cmath // 用于abs绝对值函数 using namespace std; // 定义磁盘请求的结构体 struct Request { int track; // 请求访问的磁道号 // 可以扩展其他属性如请求ID、进程ID等 Request(int t) : track(t) {} }; // 全局变量定义为了示例清晰使用了全局变量。实际项目中建议封装成类 vectorRequest requests; // 磁盘请求队列 int current_track; // 磁头当前位置 int total_tracks; // 磁盘总磁道数例如0-199 bool direction; // 磁头移动方向 true: 向磁道号增大方向, false: 减小方向代码解析Request结构体是请求的抽象目前只包含最核心的磁道号track。在实际的磁盘调度器中它可能还会包含请求时间、进程ID、操作类型读/写等信息。使用全局变量是为了让示例代码最简洁聚焦于算法逻辑。在严谨的项目中强烈建议将这些封装在一个类里例如class DiskScheduler这样状态更清晰也更安全。total_tracks定义了磁盘的边界对于SCAN算法是必要的因为磁头需要知道何时“掉头”。通常假设磁道号从0开始。3.2 核心函数SCAN调度算法这是整个程序的心脏。我们将按照之前拆解的流程来实现它。void scanAlgorithm() { // 1. 创建两个临时向量分别存放当前方向前方和后方的请求 vectorint ahead; // 当前方向前方的请求磁道号 vectorint behind; // 当前方向后方的请求磁道号 // 2. 遍历所有请求根据当前位置和方向进行分类 for (const auto req : requests) { if (direction) { // 方向为增大 if (req.track current_track) { ahead.push_back(req.track); } else { behind.push_back(req.track); } } else { // 方向为减小 if (req.track current_track) { ahead.push_back(req.track); } else { behind.push_back(req.track); } } } // 3. 对 ahead 队列进行排序 // 如果方向是增大就升序排序从小到大这样磁头从当前位置向大号移动时依次访问最近的。 // 如果方向是减小就降序排序从大到小。 if (direction) { sort(ahead.begin(), ahead.end()); // 升序 } else { sort(ahead.begin(), ahead.end(), greaterint()); // 降序 } // 4. 对 behind 队列进行排序排序顺序与当前方向相反 // 因为当磁头掉头后behind会变成新的ahead需要按新方向排序。 // 例如当前方向增大behind是较小的磁道。掉头后方向减小访问它们需要从大到小访问。 if (direction) { sort(behind.begin(), behind.end(), greaterint()); // 降序 } else { sort(behind.begin(), behind.end()); // 升序 } // 5. 服务当前方向ahead队列的请求 cout 磁头从 current_track 开始向 (direction ? 增大 : 减小) 方向移动。 endl; for (int track : ahead) { // 计算寻道距离移动的磁道数 int seek_distance abs(track - current_track); cout 移动到磁道 track 寻道距离: seek_distance endl; // 更新磁头当前位置 current_track track; // 在实际系统中这里会触发磁盘I/O操作 } // 6. 调转方向 direction !direction; cout 到达当前方向末端调转方向。现在方向为: (direction ? 增大 : 减小) endl; // 7. 服务另一方向原behind队列现在按新方向已排好序的请求 for (int track : behind) { int seek_distance abs(track - current_track); cout 移动到磁道 track 寻道距离: seek_distance endl; current_track track; } cout 所有请求服务完毕。最终磁头位置: current_track endl; }关键点与避坑指南分类逻辑分类是SCAN算法的第一步也是最容易出错的一步。注意条件中的等号或。一个常见的争议是如果请求恰好就在当前磁头位置怎么办按照定义这个请求可以立即被服务无需移动。在我们的分类中将它归入了ahead队列并且在下一步移动中第一个移动距离就是0这符合逻辑。你也可以选择在分类前单独处理所有与当前位置相等的请求。排序顺序这是体现“扫描”行为的关键。一定要根据移动方向来决定排序顺序。方向增大就访问越来越大的号所以ahead升序方向减小就访问越来越小的号所以ahead降序。behind的排序是为掉头后准备的所以顺序与当前方向相反。边界处理朴素版的局限我们这个版本有一个隐含假设ahead队列中包含了从当前位置到该方向最远请求的所有待处理请求。在真实的SCAN算法中如果该方向上没有请求了磁头会一直移动到磁盘的物理边界如0号磁道或最大磁道号然后才掉头。我们这个版本简化了这一点假设ahead队列的最后一个请求就是本次扫描的“终点”。这是一个“朴素”之处。要模拟完整行为可以在ahead服务完后让current_track走到磁盘边界再掉头服务behind。3.3 辅助函数计算总寻道长度与平均寻道长度一个调度算法的优劣寻道长度是核心衡量指标。我们来实现一个计算函数。int calculateTotalSeek(const vectorint sequence, int start_track) { if (sequence.empty()) return 0; int total_seek 0; int previous_track start_track; cout \n寻道序列分析: endl; cout 起始磁道: start_track endl; for (int track : sequence) { int distance abs(track - previous_track); total_seek distance; cout 从 previous_track 到 track , 距离: distance endl; previous_track track; } cout 总寻道长度: total_seek endl; return total_seek; } double calculateAverageSeek(int total_seek, int num_requests) { if (num_requests 0) return 0.0; // 注意平均寻道长度 总寻道距离 / 请求次数 // 但第一次从初始位置到第一个请求的距离也算一次寻道。 // 所以除数就是请求数量如果初始位置不算请求则寻道次数等于请求数 return static_castdouble(total_seek) / num_requests; }注意calculateTotalSeek函数接收一个磁道访问序列和起始位置。在我们上面的scanAlgorithm函数中我们可以记录下磁头访问的磁道顺序形成一个vectorint然后传给这个函数计算。这样将算法执行和性能评估分离结构更清晰。3.4 主函数与测试用例让我们写一个main函数来测试这个算法。int main() { // 初始化测试数据 // 假设磁盘有200个磁道 (0-199) total_tracks 200; // 设置初始磁头位置和方向 current_track 53; direction true; // 初始方向设为增大向外 // 设置一组磁盘请求序列这是一个经典测试序列 // 通常包括98, 183, 37, 122, 14, 124, 65, 67 requests.clear(); requests.push_back(Request(98)); requests.push_back(Request(183)); requests.push_back(Request(37)); requests.push_back(Request(122)); requests.push_back(Request(14)); requests.push_back(Request(124)); requests.push_back(Request(65)); requests.push_back(Request(67)); cout SCAN电梯磁盘调度算法模拟 endl; cout 磁盘总磁道数: 0 - total_tracks-1 endl; cout 磁头起始位置: current_track endl; cout 初始移动方向: (direction ? 向磁道号增大方向 : 向磁道号减小方向) endl; cout 待处理请求序列: ; for (const auto req : requests) { cout req.track ; } cout endl endl; // 为了记录访问序列我们需要修改一下scanAlgorithm函数。 // 更清晰的做法是让scanAlgorithm返回访问序列。 // 这里为了保持上面讲解的简洁性我们采用一个折中方案在函数内部记录。 // 下面我们实现一个带返回序列的版本 scanAlgorithmWithSequence。 vectorint visit_sequence; int start_pos current_track; bool start_dir direction; // 重新分类和排序逻辑与scanAlgorithm相同但记录顺序 vectorint ahead, behind; for (const auto req : requests) { if (start_dir) { if (req.track start_pos) ahead.push_back(req.track); else behind.push_back(req.track); } else { if (req.track start_pos) ahead.push_back(req.track); else behind.push_back(req.track); } } if (start_dir) { sort(ahead.begin(), ahead.end()); sort(behind.begin(), behind.end(), greaterint()); } else { sort(ahead.begin(), ahead.end(), greaterint()); sort(behind.begin(), behind.end()); } // 记录访问序列 int current start_pos; for (int track : ahead) { // 只有当目标磁道与当前位置不同时才记录移动避免记录距离为0的“移动” // 但为了序列完整我们通常记录所有被访问的磁道包括起点如果起点有请求 visit_sequence.push_back(track); current track; } // 注意这里没有走到磁盘边界是朴素版的简化 for (int track : behind) { visit_sequence.push_back(track); current track; } cout \n生成的磁道访问序列: ; for (int t : visit_sequence) cout t ; cout endl; // 计算性能指标 int total_seek calculateTotalSeek(visit_sequence, start_pos); double avg_seek calculateAverageSeek(total_seek, visit_sequence.size()); cout \n 性能总结 endl; cout 总寻道长度: total_seek endl; cout 平均寻道长度: avg_seek (磁道数/请求) endl; return 0; }运行这个程序你会得到类似下面的输出基于初始位置53方向增大 SCAN电梯磁盘调度算法模拟 磁盘总磁道数: 0 - 199 磁头起始位置: 53 初始移动方向: 向磁道号增大方向 待处理请求序列: 98 183 37 122 14 124 65 67 生成的磁道访问序列: 65 67 98 122 124 183 37 14 寻道序列分析: 起始磁道: 53 从 53 到 65, 距离: 12 从 65 到 67, 距离: 2 从 67 到 98, 距离: 31 从 98 到 122, 距离: 24 从 122 到 124, 距离: 2 从 124 到 183, 距离: 59 从 183 到 37, 距离: 146 从 37 到 14, 距离: 23 总寻道长度: 299 性能总结 总寻道长度: 299 平均寻道长度: 37.375 (磁道数/请求)你可以尝试改变current_track和direction的初始值观察访问序列和寻道长度的变化。例如将方向设为false减小序列会变成37 14 65 67 98 122 124 183总寻道长度也会不同。4. 从朴素版到实用化的思考与扩展我们这个“very朴素版”实现了SCAN算法的核心骨架但它距离一个实用的磁盘调度模块还有很大距离。下面我们来探讨一下如果要投入实际使用需要考虑哪些扩展和优化。4.1 动态请求到达的处理现实中的磁盘请求是随时可能到来的而不是在调度开始前就全部已知。我们的静态队列模型需要升级。解决方案思路维护两个队列一个用于保存当前扫描周期内已到达的、尚未服务的请求pending_requests另一个用于保存磁头移动过程中新到达的请求new_requests。同步与互斥在多线程或中断环境下对这两个队列的访问需要加锁例如使用std::mutex防止数据竞争。调度时机磁头每完成一个请求或者每隔一个很短的时间片就检查new_requests队列将其中的请求按照SCAN规则插入到pending_requests队列的正确位置。这个“插入”操作需要保持pending_requests在磁头移动方向上的有序性。算法调整这时的算法不再是批处理而是一个循环选择下一个请求 - 移动磁头服务 - 合并新请求 - 重新选择。这被称为LOOK 算法它是SCAN的改进磁头移动到该方向最后一个请求就掉头不必走到磁盘边界。实操心得实现动态SCAN/LOOK时对数据结构的操作频率很高。如果使用vector每次插入新请求都可能需要移动大量元素。可以考虑使用std::set或std::multiset来维护pending_requests它们本身就是有序的插入效率是O(log n)。需要定义好排序比较函数使其符合当前扫描方向。4.2 面向对象设计与代码重构将全局变量和函数封装成类是迈向工程化的第一步。class ScanDiskScheduler { private: int current_track_; int total_tracks_; bool direction_; // true for increasing, false for decreasing vectorRequest requests_; // 或者使用 set 来维护有序请求 // setint, custom_compare pending_requests_; public: ScanDiskScheduler(int start_track, int total_tracks, bool init_direction) : current_track_(start_track), total_tracks_(total_tracks), direction_(init_direction) {} void addRequest(const Request req) { // 需要考虑线程安全这里可以加锁 requests_.push_back(req); } void schedule() { // 实现调度逻辑可能是一个循环直到请求队列为空 // 内部可以调用类似 processNextRequest 的方法 } pairvectorint, int getScheduleSequenceAndTotalSeek() { // 计算并返回调度序列和总寻道长度 // 这是对之前静态算法函数的一个封装 } // ... 其他方法如重置状态、改变方向等 };4.3 性能评估与算法对比单独实现SCAN意义有限通常需要与其他算法对比。你可以很容易地基于现在的框架实现FCFS、SSTF算法。FCFS最简单直接按请求到达顺序服务。总寻道长度往往最大。SSTF总是服务离当前磁头最近的请求。平均寻道时间通常优于FCFS和SCAN但可能导致“饥饿”。C-SCANSCAN的变种提供更均匀的等待时间。磁头只在一个方向上服务请求到达尽头后直接返回磁盘的另一端开始而不服务回程中的请求。实现一个统一的测试框架用同一组请求序列测试不同算法并输出总寻道长度、平均寻道长度、最大等待时间等指标会非常有价值。4.4 可视化与调试对于学习而言将磁头的移动过程可视化能极大加深理解。你可以控制台图形用字符在控制台打印出一条磁道轴用*或H标记磁头位置用数字标记请求动态刷新。使用简单图形库如C的SFML或Raylib画一条线段代表磁道用移动的圆点代表磁头用竖线代表请求实时显示移动过程。生成日志文件将每一步的磁头位置、请求队列状态、移动方向写入文件然后用Python的matplotlib等工具绘制成动画或静态时序图。5. 常见问题与调试技巧实录在编写和调试这类算法时我踩过不少坑。这里总结几个典型问题和解决方法。5.1 问题一访问序列与预期不符特别是掉头后的顺序症状磁头掉头后访问的磁道顺序看起来是乱的或者没有按照预想的方向排序。排查步骤检查分类条件这是最可能出错的地方。确认你的if (direction)分支里的和是否正确。打印出分类后的ahead和behind队列看请求是否被正确划分。检查排序逻辑确认ahead和behind的排序顺序是否与当前及未来的移动方向匹配。记住一个原则ahead队列按当前方向排序behind队列按相反方向排序为掉头后做准备。验证边界情况测试磁头初始位置恰好等于某个请求磁道的情况。测试所有请求都在磁头一侧的情况。测试只有一两个请求的情况。调试技巧在算法关键步骤后插入详细的打印语句。例如cout “分类后 - ahead: “; for (int t : ahead) cout t ” “; cout endl “behind: “; for (int t : behind) cout t ” “; cout endl “排序后 - ahead: “; // ... 打印排序后的队列5.2 问题二总寻道长度计算错误症状计算出的总寻道长度与手动模拟的结果对不上。排查步骤检查序列记录确保你记录的visit_sequence包含了所有被访问的磁道并且顺序完全正确。第一个被访问的磁道不一定是初始位置current_track而是ahead队列的第一个元素如果ahead不为空。检查计算函数calculateTotalSeek函数是否正确地从起始位置开始累加序列中每两个相邻磁道的距离。确保previous_track在循环开始时被正确初始化为start_track而不是序列的第一个元素。理解“寻道”定义寻道长度是磁头移动经过的磁道数。如果磁头从53移动到65距离是12即使65号磁道没有请求在我们的朴素版中不会发生这个移动距离也算。我们的计算是基于访问序列的所以是正确的。5.3 问题三如何处理与当前位置相同的请求症状请求磁道等于当前磁头位置算法是应该立即服务它还是把它当作普通请求放入队列解决方案两种处理方式都可以但需要在设计上明确。方式A立即服务在分类和排序之前先遍历一遍请求队列将所有track current_track的请求直接标记为“已服务”并记录到访问序列中距离为0同时将它们从待处理队列中移除。这样更高效也符合逻辑。方式B放入队列就像我们朴素版代码所做将其放入ahead队列。由于排序后它很可能在ahead的最前面第一次移动距离为0效果和方式A类似。这种方式代码统一更简洁。在我们的实现中方式B是可行的。但如果你发现计算结果有细微差别检查一下这里。5.4 从SCAN到LOOK和C-SCAN的调整当你理解了朴素SCAN后实现它的变种就很容易了。实现LOOK在服务完ahead队列后不要立即掉头。检查behind队列是否为空。如果为空算法结束如果不为空再掉头服务behind。这避免了无意义的移动到磁盘边界。只需要修改掉头的条件即可。实现C-SCAN在服务完ahead队列后将磁头直接移动到磁盘的起始端或末端取决于方向这个移动过程不服务任何请求然后将方向重置为初始方向再开始新一轮扫描。这需要修改代码在服务完ahead后将current_track设置为边界值0或total_tracks-1并不改变方向或者改变方向但逻辑上视为新的一圈然后将behind队列中的请求当作新的ahead队列按同一方向排序来处理。最后这个朴素的C实现项目就像一把钥匙帮你打开了磁盘调度算法这扇门。代码本身不长但背后关于效率与公平的权衡、数据结构的选择、边界条件的处理都是编程和系统设计中反复出现的主题。我建议你不仅停留在看懂最好能自己默写一遍然后尝试实现FCFS和SSTF进行对比再挑战一下LOOK和C-SCAN。这个过程里遇到的编译错误、逻辑bug才是让你真正掌握它的阶梯。