★ FEATURED ARTICLE 磁盘调度实验几乎是每个操作系统课程的必修课也是很多同学第一次接触“算法策略对系统性能影响”的直观案例。FCFS、SSTF、SCAN这三个算法听起来不难但真正动手实现时你会发现许多细节——方向怎么维护、边界怎么处理、平局怎么选、磁头初始位置算不算请求——都会直接影响计算结果。这篇博客就按我实际做这个实验的完整过程来写从原理到代码再到踩坑记录给正在做课程设计、准备面试或者单纯想搞懂调度策略的同学一个可以直接参考的版本。1. 这个实验到底在解决什么问题1.1 磁盘访问慢在哪里要理解磁盘调度先得搞清楚磁盘的“慢”到底慢在哪个环节。机械硬盘读写一个扇区本质上包含三部分时间寻道时间、旋转延迟、传输时间。其中寻道是磁头从当前柱面移动到目标柱面所花的时间机械结构决定了它是最慢、也是变化最大的部分——一次寻道动辄几毫秒到十几毫秒而真正传输一个扇区往往不到一毫秒。所以操作系统面对一批磁盘请求时如果能合理安排磁头的移动路径减少来回跑的“空走距离”就能显著提升IO效率。实验里计算的总寻道距离虽然没有把旋转延迟算进去但它已经是评价调度算法最直观的指标了。这也是为什么这个实验在所有操作系统课程中生命力这么强逻辑简单指标清晰又能体现策略差异带来的性能差距。1.2 调度算法的本质是“排队策略”磁盘请求到达的次序是随机的磁头只有一个无法同时响应所有请求。操作系统的任务就是决定“下一个先服务谁”。这跟超市收银台排队是一个道理先来先到最公平但如果前面的人都在买大量商品后面只买一瓶水的顾客会等到崩溃如果让买得少的插队整体平均等待时间会下降但“买到一半被插队”的顾客就会不满。磁盘调度就是在“公平”和“效率”之间找平衡。FCFS是彻底的公平但效率低SSTF是效率优先但可能出现饥饿SCAN则尝试兼顾两者。做这个实验时不能只把三个函数写完跑一遍就了事真正有价值的是你能否解释清楚“为什么不同策略在不同请求分布下表现差异那么大”。1.3 实验目标拆解这个实验的核心目标有三个层次。第一实现FCFS、SSTF、SCAN三种算法输入一批柱面号请求和磁头初始位置输出每个算法的访问顺序与总寻道距离。第二通过对照测试理解不同调度策略对性能的影响尤其是贪心思想SSTF和方向扫描思想SCAN的本质区别。第三能观察到饥饿现象——SSTF在极端请求分布下会让某些请求长时间得不到服务。课程设计里常有一个附加要求随机生成多组请求序列统计不同算法的平均寻道距离并分析结果。这个扩展部分才是整个实验的精华也是我在第4节会重点分析的内容。2. 三种核心算法的原理与取舍2.1 FCFS先来先服务最公平的“对照组”FCFSFirst Come First Serve有的教材写作FIFS实现起来最简单维护一个请求队列谁先到先处理谁磁头严格按队列顺序移动。算法过程就是依次遍历请求数组累加从当前位置移动到目标柱面的距离。比如磁头在100请求依次是98、183那么移动距离是|100-98| |98-183|没有任何跳过的余地。FCFS的优点是没有饥饿问题每个请求都能按到达顺序得到服务算法实现零复杂度。缺点是磁头会频繁来回移动产生大量无意义的“空驶”。请求越分散FCFS表现越差。这也是为什么它只能作为对照算法存在——你用它作为性能下限再去对比其他算法的优化效果。我在实验里习惯把FCFS当作“基线”如果某个新算法在绝大多数请求分布下连FCFS都打不过那说明这个算法本身设计就有问题。2.2 SSTF贪心选最近总距离低但会“饿”SSTFShortest Seek Time First的思想是每次从当前磁头位置出发选择离自己最近的那个请求作为下一个服务对象。这是一个典型的贪心策略每次只考虑局部最优试图让每一步的移动距离都最小。贪心算法线程跑得好时效果确实不错总寻道距离通常远低于FCFS。但它的致命弱点是饥饿如果磁头附近不断有新的请求到达那么离磁头很远的请求可能永远轮不到。比如当前在100附近98、102一直有请求而183的请求排在队列里很久SSTF会不停地先服务近处的请求导致183一直等待。实验里常用静态请求序列来模拟此时饥饿不会动态发生但你依然可以从访问顺序中看出端倪——某些靠近初始位置的请求被反复优先远处的请求总是最后一个才被访问。2.3 SCAN电梯算法兼顾公平与效率SCAN采用了一种完全不同的思路给磁头规定一个运动方向沿着这个方向一直前进途中遇到请求就服务直到到达最边界然后反向继续扫描。因为它的运动方式跟电梯上下楼很像所以也叫电梯算法。SCAN的优势在于磁头不会像SSTF那样频繁“折返”每次扫描都能线性覆盖一片连续区域效率高且公平性不错——同一方向上的请求不会出现极端饥饿。缺点也很明显如果某个请求刚好在磁头当前方向的“身后”那它必须等磁头走到边界再折返回来才能被服务等待时间可能比较长。实现SCAN时方向变量是整个代码的灵魂。我见过不少同学在改动方向时出错导致磁头在某一段区间来回震荡最终算出来的总距离甚至比FCFS还差。这个问题我在第3节会给出一个明确的实现方案在第5节也会单独讲排查方法。3. 完整实现过程与核心代码3.1 实验参数与请求序列约定先约定实验基本参数后面所有代码都基于这组参数。我做的版本假设磁盘有200个柱面编号0到199初始磁头位置在100请求序列采用经典的一组数据98, 183, 37, 122, 14, 124, 65, 67这组数据的好处是覆盖了当前磁头左右两侧、远处和近处的请求能明显看出三种算法的差异。用C语言实现不仅因为实验环境普遍支持而且C的数组操作和指针逻辑能让你更直观地理解“磁头位置”的状态变化。3.2 公共数据结构整个程序的主体数据结构很简单#define CYLINDER_NUM 200 // 柱面总数 #define MAX_REQ 20 // 最大请求数 int requests[MAX_REQ] {98, 183, 37, 122, 14, 124, 65, 67}; int requestCount 8; int startHead 100;为了让三种算法共用一套代码框架我封装了两个基础工具函数int absDistance(int a, int b) { return a b ? a - b : b - a; } void printStep(int step, int from, int to, int total) { printf(第%2d步: %d - %d, 移动距离 %2d, 累计距离 %d\n, step, from, to, absDistance(from, to), total); }printStep是调试神器。每走一步就把磁头位置、目标位置、单步距离和累计距离打印出来哪里有逻辑错误一眼就能看出来。这个习惯帮我省了大量排查时间。3.3 FCFS代码实现FCFS是整个实验里最简单的算法属于“五分钟写完但必须保证正确”的程度void fcfs() { int cur startHead; int total 0; printf(\n FCFS 调度算法 \n); for (int i 0; i requestCount; i) { total absDistance(cur, requests[i]); printStep(i 1, cur, requests[i], total); cur requests[i]; } printf(FCFS 总寻道距离: %d\n, total); }你需要理解的并不是这几行代码本身而是它所表达的“零策略”理念磁头完全没有自主选择权队列顺序决定一切。这也意味着只要请求序列固定FCFS的结果就是唯一的不可能出现平局或二义性。3.4 SSTF代码实现SSTF的实现要比FCFS多一个核心动作在未访问的请求里找距离最近的。我维护了一个visited访问标记数组每一轮遍历所有未访问请求计算与当前磁头的距离记录最小值和对应的数组下标void sstf() { int visited[MAX_REQ] {0}; int cur startHead; int total 0; printf(\n SSTF 调度算法 \n); for (int step 0; step requestCount; step) { int bestIndex -1; int bestDist 2147483647; for (int i 0; i requestCount; i) { if (visited[i]) continue; int dist absDistance(cur, requests[i]); if (dist bestDist) { bestDist dist; bestIndex i; } } visited[bestIndex] 1; total bestDist; printStep(step 1, cur, requests[bestIndex], total); cur requests[bestIndex]; } printf(SSTF 总寻道距离: %d\n, total); }注意一个容易忽略的细节当两个请求距离相同时程序会选数组中下标更靠前的那个。比如当前在124183和65距离都是59我的实现会固定选择65。这个“平局处理规则”看似无关紧要实际上会直接影响总寻道距离后面第5节我会单独讲。SSTF的复杂度是O(n²)每步都要遍历所有剩余请求。对于课程实验这种几十个请求的规模完全够用但如果要处理海量请求优化思路是先按柱面号排序再用双指针查找最近点。3.5 SCAN代码实现SCAN的实现最考验对“方向”的理解。我最初写过一个排序后分段遍历的版本但边界情况处理得很痛苦后来干脆模拟磁头一步步移动方向没有请求时就走到边界再转向void scan() { int served[MAX_REQ] {0}; int cur startHead; int total 0; int dir 1; // 1表示向柱面号增大方向0表示向减小的方向 printf(\n SCAN 调度算法 \n); for (int step 0; step requestCount; step) { int bestIndex -1; int bestDist 2147483647; // 在当前方向上寻找最近的未服务请求 for (int i 0; i requestCount; i) { if (served[i]) continue; if (dir 1 requests[i] cur) { int dist requests[i] - cur; if (dist bestDist) { bestDist dist; bestIndex i; } } else if (dir 0 requests[i] cur) { int dist cur - requests[i]; if (dist bestDist) { bestDist dist; bestIndex i; } } } // 当前方向上没有请求移动到边界并转向 if (bestIndex -1) { if (dir 1) { total (CYLINDER_NUM - 1 - cur); cur CYLINDER_NUM - 1; printf(到达右边界 %d折返\n, cur); dir 0; } else { total cur; cur 0; printf(到达左边界 %d折返\n, cur); dir 1; } step--; // 边界移动不消耗请求循环需要继续 continue; } served[bestIndex] 1; total bestDist; printStep(step 1, cur, requests[bestIndex], total); cur requests[bestIndex]; } printf(SCAN 总寻道距离: %d\n, total); }这段代码的核心逻辑是每一轮优先在当前方向上寻找最近的请求如果当前方向上已经没有未服务请求就让磁头移动到边界再转向转向过程本身也要计入寻道距离。我特别说明一下代码里step--的作用磁头移动到边界这个动作只是方向的转换不服务任何请求所以不能消耗“请求计数”否则循环会提前结束。3.6 结果输出与验证方式运行结束后程序会依次输出三种算法的访问顺序和总寻道距离。但光看总距离不够你需要人工验证一下访问顺序是否合理。我的验证方法是把每一步的from - to打印结果和手动算的路径对照尤其是SCAN要确认磁头确实先走到右边界199再折返而不是在中途就反向。这一步看起来朴素却是整个实验最可靠的保障。我在做SSTF平局处理调整时就是靠逐行对比打印结果才发现某个边界方向出了问题。4. 测试结果与数据对比4.1 经典序列手动验证先用上面那组固定请求序列手动算一遍。磁头初始位置100请求序列是98、183、37、122、14、124、65、67。FCFS的移动路径完全按请求顺序100到98298到18385183到3714637到12285122到1410814到124110124到655965到672。累加总距离为597。SSTF的路径是100到98298到12224122到1242124到655965到67267到373037到142314到183169总距离311。这个结果里注意平局规则——124时65和183距离都是59我的实现选了65导致最后才访问183如果先访问183再转回65总距离反而会更小。这是SSTF“局部最优不等于全局最优”的典型体现。SCAN初始方向取增大方向dir1路径是100到12222122到1242124到18359183到19916折返后199到9810198到673167到65265到372837到1423总距离284。把三个数字放在一起看算法访问顺序总寻道距离FCFS100→98→183→37→122→14→124→65→67597SSTF100→98→122→124→65→67→37→14→183311SCAN100→122→124→183→199→98→67→65→37→14284这组经典序列里SCAN反而比SSTF更好。这很反直觉但原因在上面已经揭示了SSTF每一步只看局部距离却被124处的一个平局选择“带偏”了方向导致磁头先跑到65后来又得返回头处理183。贪心算法并不保证全局最优这就是最好的教学案例。4.2 随机请求多次模拟的平均表现固定序列只能反映一种场景为了更客观地比较三种算法我写了个随机请求生成器每次随机生成20个柱面号范围0到199初始磁头位置随机重复跑10组分别记录三种算法的总寻道距离。我本地跑的一组示例数据如下组别FCFSSSTFSCAN17363453812812327366368735137247543383905705342358669832936577423313778719340369976434838310728336374平均734.5338.7373.5SSTF平均表现最好SCAN紧随其后FCFS基本是前两者的两倍以上。这个趋势与理论预期一致SSTF总是选择最近请求平均寻道距离自然低SCAN加上方向约束后虽然略差于SSTF但它能防止某些请求被无限期推迟。4.3 为什么SSTF不总是胜出如果你的实验结论只写到“SSTF性能最优”那就漏掉了整个实验最重要的思考深度。SSTF的“优”建立在局部贪心正确的前提下但它的每一步选择都会影响后续路径。某个看似最优的近距离选择可能会把磁头吸引到一个不利的位置导致后期要跨越大段距离去服务另一端的请求。更关键的是饥饿问题。我做了另一个测试把请求集中在柱面90到110之间的20个请求再加上一个位于柱面190的请求初始磁头在95。SSTF在访问完周围密集请求前永远不会去碰那个190的请求如果请求是动态到达的这个远端请求可能永远等不到服务。SCAN没有这个毛病——它遵守“朝一个方向扫到底”的纪律即使某个方向没有请求也要走到边界再回头这保证了磁头迟早会覆盖整片磁盘区域。4.4 如果想做得更深LOOK与C-SCAN做完三种基础算法后稍微扩展一下就能让实验报告更有含金量。LOOK算法与SCAN的区别在于SCAN强制走到磁盘边界才折返LOOK只走到该方向上最后一个请求就回头省去了边界上的空驶距离。C-SCAN循环扫描则是从0到199扫描后直接回到0重新开始只在单方向上服务请求让等待时间更均匀。在上面那组经典序列中LOOK的总距离是252比SCAN的284少了32省的就是183到199再折返回183这一段路程。C-SCAN的路径则是100→122→124→183→0→14→37→65→67→98总距离22259183142328231364虽然比SCAN大但它保证了所有请求在两次扫描内必然被服务不会出现方向折返导致的额外等待。这些变体实现起来只是对方向与边界逻辑的小改动但对理解调度策略的演化很有帮助。5. 我踩过的坑与实用排查技巧5.1 SSTF平局处理不一致结果对不上这是我和A同学对答案时发现的第一个坑。同一组请求序列我们俩SSTF算出来的总距离不一样排查了半天才发现是平局处理规则不同。124到65和183距离都是59我的代码选了65他写的遍历顺序选了183最终总距离差了51。后来我在代码里固定了规则扫描数组时只有严格小于当前最小值才更新这样平局时总是选数组中靠前的请求。实验报告里也明确写出这条规则结果就有可复现性了。5.2 SCAN方向变量被意外修改SCAN最隐蔽的bug是方向翻转条件写错。我第一版代码在“当前方向上找不到请求”时才转向但没考虑磁头正好停在某个请求上的情况导致如果初始磁头位置恰好等于待访问请求柱面号这个请求会被错误跳过方向判定也会乱。排查方法很笨但很有效把所有移动步骤完整打印出来逐行标出磁头位置看它是否出现“来回反复震荡”的轨迹。如果出现这种情况基本可以断定是方向维护出了问题。5.3 磁头初始位置算不算一个请求有的同学会把初始位置当作请求之一参与排序和计数导致总距离和访问顺序里多出一个不存在的柱面。我的约定是磁头初始位置是起点不是请求。计算距离时只从它开始累加计数只统计请求数组里的元素。这个约定在你打印“访问顺序”的时候尤其重要。输出结果里起点可以出现但它不计入请求数也不单独算一次“服务”。5.4 边界数字写错199还是200CYLINDER_NUM定义为200代表柱面总数是200个编号范围是0到199。SCAN里到达右边界时应该使用CYLINDER_NUM - 1也就是199。如果写成200移动距离会多算1。这类错误在单个例子里看不出来但在随机多组测试的统计数据里会造成稳定的偏差而且很难排查。我给自己的建议是把MAX_CYLINDER和MAX_CYLINDER_NUM两个名字区分清楚一个是数量一个是编号上限代码里用注释标明就不会混。5.5 随机请求生成时容易出现的“重复请求”随机生成请求时如果直接用rand() % 200生成20个柱面号很可能出现重复值。重复请求不是不能处理但会让人误以为算法bug——比如SSTF访问完重复值后另一个相同柱面号的请求距离为0移动距离为0看起来不太自然。解决方法有两种一是生成时去重保证请求柱面号互不相同二是保留重复值并在实验报告中说明重复请求会让寻道距离为0但总距离不受影响计数上会多算一次服务。我更推荐去重因为数据处理起来更干净。5.6 如何验证算法没有算错我最后用了一招“穷举验证”把请求序列固定为只有少数几个请求的小数组比如3个请求手动枚举所有可能的访问顺序和程序输出的结果进行比对。SSTF在3个小请求的情况下你可以暴力算出所有顺序的总距离再确认程序选的确实是贪心路径。这招听起来基础但它能确保你后面跑大规模随机测试时心里有底。千万不要一上来就随机生成100个请求然后直接拿三个总距离数字写报告——你根本不知道中间有没有算错。我个人做完这个实验最大的体会是三个算法的“策略思想”在纸上写出来不过几行字但真正写代码、跑数据、调bug的过程才会让你真正理解为什么操作系统在磁盘调度上没有选择让每个请求都绝对公平也没有选择完全极致地追求平均性能而是要设计出SCAN这种“方向优先、兼顾效率”的折中方案。如果你想把实验做得更完整还可以把磁头移动轨迹用折线图画出来直观展示三者的路径差异这在答辩时会非常加分。
阅读完成 · 觉得有帮助？
