简介这份面向高校计算机相关专业学生的操作系统课程设计资料聚焦磁盘调度算法的模拟实现与对比适合正在完成实验报告、课程设计或准备操作系统笔试面试的学习者。压缩包内仅含1个PDF文件约172KB将实验报告与源代码合并在同一文档中便于对照阅读。内容围绕先来先服务FCFS、最短寻道时间优先SSTF、扫描SCAN和循环扫描C-SCAN四种算法展开包含需求分析、概要设计、详细设计与调试分析并给出输入磁道序列、输出服务序列、计算平均寻道时间和比较磁头移动道数的实现思路。其中对SSTF可能引发饥饿、SCAN与C-SCAN在公平性和单向移动上的差异以及FCFS为O(n)、SSTF为O(n²)的时间复杂度讨论较具体还记录了调试问题、运行结果与总结反思。目前已有1104人学习下载适合需要参考算法逻辑、报告结构和代码实现细节的读者。1. 磁头只有一根请求却排着队这份实验要交付什么排队等磁头的场景每天都在发生八个读写请求挤在队列里磁头停在 53 号磁道先服务谁结果能差出三倍。磁盘调度算法实验说穿了就是把这件事量化——给定磁道范围 0 到 199、一个初始磁头位置和一组请求序列按 FCFS、SSTF、SCAN、C-SCAN 四种规则各走一遍算出累计寻道长度和平均寻道长度再从公平性和饥饿风险上比出高下。要交付的东西有两份能编译能跑的代码和一份数据对得上、结论站得住的实验报告。做操作系统课程设计的同学、准备操作系统期末复习的同学以及要给实验课准备参考实现的助教往往卡在同一个地方——算法原理半小时就背下来了代码里的方向参数和边界处理却能耗掉一整个下午。下面按模型、Python 实现、C 实现与报告写法、结果校验的顺序推下去参数怎么设、边界怎么处理、报告里哪些结论必须有数据撑着一并说清楚。2. 磁盘调度算法的寻道模型与选型依据2.1 一次磁盘访问的成本拆成哪几段一次随机读的耗时由三段构成磁头移动到目标磁道的寻道时间、盘片旋转到目标扇区的旋转延迟、以及数据本身的传输时间。7200 转的机械盘旋转半圈大约 4 毫秒而跨 100 个磁道的寻道往往要 8 到 12 毫秒传输几 KB 数据却只要几十微秒。三段里寻道是唯一能靠调度顺序改变的所以课程实验把模型简化成只统计寻道长度这个简化假设必须写进报告的实验目的里否则一定被问为什么不算旋转延迟。还要提前说清两个约定寻道长度用磁道号之差的绝对值表示不考虑磁头加速减速的非线性服务完一个请求后磁头停在目标磁道下一个请求从该位置起算。这两条约定决定了后面所有数字能不能对得上。2.2 实验输入怎么定磁道范围、初始磁头与请求序列磁道数取 200编号 0 到 199初始磁头取 53这是教材里用了很多年的经典配置好处是请求分布同时覆盖磁头两侧还留了 14 和 183 两个接近端点但不贴边的值方便观察 SCAN 走满边界与 LOOK 提前折返的差别。请求序列我一般直接用98, 183, 37, 122, 14, 124, 65, 67八个数刚好够画出一次完整的折返。先把累计寻道长度算出来后面所有对比都以它为基准# seek_calc.py —— 手算校验用确认自己理解的是磁道号之差的绝对值累加 head, seq 53, [98, 183, 37, 122, 14, 124, 65, 67] def total_seek(order, start): order 是服务顺序start 是初始磁头位置返回累计寻道长度 cur, total start, 0 for t in order: total abs(t - cur) # 单步寻道长度 cur t return total print(total_seek(seq, head)) # FCFS按到达顺序服务 print(total_seek(sorted(seq), head)) # 从小到大一趟扫过去接近单向扫描的效果逻辑很直白每一步的距离是目标磁道减当前磁头位置的绝对值累加就是总寻道长度除以请求个数就是平均寻道长度。参数上唯一要留心的是start——它必须是磁头的初始位置不是第一个请求的位置很多人把start写成seq[0]结果 FCFS 的第一段距离被吃掉八个数少算一大截报告里的表格全错。2.3 四种算法的行为差异与选型依据FCFS 按请求到达顺序服务谁先来谁先做绝对公平但磁头会在盘面上来回横跳。SSTF 每一步都挑离当前位置最近的请求属于贪心策略平均表现通常很好代价是远处的请求可能一直等不到服务。SCAN 是电梯算法磁头沿一个方向一路扫到端点再反向扫回来方向参数决定先往哪边。C-SCAN 只朝一个方向服务扫到端点后直接跳回另一端重新开始把返程的等待时间拉平代价是多走一段空程。用 2.2 的数据实际跑一遍差异非常直观单位磁道数算法服务顺序规则方向依赖累计寻道长度最大单步寻道FCFS按到达顺序无640146SSTF每步选最近无23684SCAN扫到端点再折返强331向上/ 236向下162 / 65C-SCAN单向扫回程空跳强382向上/ 386向下199 / 199选型上要抓住三点请求局部性强、延迟要求宽松的场景SSTF 的贪心性价比最高请求量大且要求等待时间可预期选 SCAN 或 C-SCANFCFS 更多是作为对照组出现在实验里。特别提醒一句SCAN 和 C-SCAN 的结果对方向参数极其敏感同一组数据向上和向下能差出 95 个磁道报告里只给一个数不写方向等于没做。2.4 只比平均寻道长度会漏掉什么平均寻道长度是最容易算的指标也是最容易骗人的指标。看上面的表SSTF 平均最好但它的最大单步是 84而 SCAN 向下只有 65FCFS 平均最差可它不会让任何一个请求无限等待。评价调度算法至少要看四个维度——平均寻道长度、最大单次寻道长度、请求等待时间的波动、以及是否存在饥饿。真实系统里的取舍更能说明问题。Linux 的块层早就不止一个调度器mq-deadline在读优先的前提下给每个请求设了截止时间防止写请求被无限推迟BFQ 按 cgroup 权重分配带宽目标是多租户下的公平而不是最短寻道。也就是说从课堂实验的最短平均寻道走到生产环境的延迟可控加公平中间跨的正是饥饿和尾部延迟这两道坎报告的分析部分写到这一层深度就够看了。3. 用 Python 把四种磁盘调度算法跑通3.1 环境准备与文本文档怎么运行代码用 Python 3.8 以上即可不需要第三方库。代码用一个文本文档写完另存为disk_sched.py注意两点编码选 UTF-8否则打印中文表头时会抛UnicodeEncodeError引号必须是半角从文档里复制示例代码时中文引号是最常见的隐形错误。运行方式在终端里直接给解释器喂文件名python disk_sched.py --head 53 --seq 98,183,37,122,14,124,65,67 --dir up # Windows 上如果 python 不在 PATH用 py -3 disk_sched.py --head 53 ...命令行参数比在代码里写死更能体现实验可复现换一组数据不用改一行代码报告里也能附上完整的调用命令。3.2 FCFS 与 SSTF 的示例代码# disk_sched.py片段一FCFS 与 SSTF from typing import List, Tuple def fcfs(head: int, req: List[int]) - Tuple[List[int], int]: 先来先服务服务顺序就是请求到达顺序 order, cur, total [], head, 0 for r in req: total abs(r - cur) cur r order.append(r) return order, total def sstf(head: int, req: List[int]) - Tuple[List[int], int]: 最短寻道时间优先每步挑距离当前位置最近的请求 pending list(req) order, cur, total [], head, 0 while pending: # key 用元组距离相同时取磁道号小的保证多次运行结果完全一致 nxt min(pending, keylambda r: (abs(r - cur), r)) total abs(nxt - cur) cur nxt order.append(nxt) pending.remove(nxt) return order, totalSSTF 的key写成(abs(r - cur), r)而不是单个距离是为了消除并列时的随机性。报告要求的可复现性不是形式主义——两个距离相同的请求随便挑一个服务顺序就变了后面 SCAN 的折返点也跟着变最后表格里的数字和你截图里的对不上答辩时很难解释。另一个细节是pending.remove(nxt)按值删除请求序列里如果有重复磁道号第一次删除后剩下的重复项仍然会被服务这符合每个请求都是一次独立的 IO的语义。3.3 SCAN 与 C-SCAN 的方向参数和边界处理3.3.1 direction 参数与 0/199 两个端点SCAN 必须走满到端点这是它和 LOOK 的分水岭。代码里把端点显式放进路径再靠一个集合判断哪些点是真的请求避免端点恰好也是请求时被算两次。# disk_sched.py片段二SCAN 与 C-SCAN MAX_TRACK 199 def scan(head: int, req: List[int], direction: str up) - Tuple[List[int], int]: 电梯算法一路扫到端点再反向扫回 req_set set(req) left sorted(r for r in req if r head) right sorted(r for r in req if r head) # up先服务大号磁道扫到 199 折返down先服务小号磁道扫到 0 折返 path (right [MAX_TRACK] left[::-1]) if direction up \ else (left[::-1] [0] right) order, cur, total [], head, 0 for t in path: total abs(t - cur) cur t if t in req_set: # 端点不是请求时不进服务序列 req_set.discard(t) order.append(t) return order, total def cscan(head: int, req: List[int], direction: str up) - Tuple[List[int], int]: 循环扫描只朝一个方向服务到端点后空跳回另一端 req_set set(req) left sorted(r for r in req if r head) right sorted(r for r in req if r head) path (right [MAX_TRACK, 0] left) if direction up \ else (left[::-1] [0, MAX_TRACK] right[::-1]) order, cur, total [], head, 0 for t in path: total abs(t - cur) # 199→0 的空跳同样计入寻道长度 cur t if t in req_set: req_set.discard(t) order.append(t) return order, totalMAX_TRACK和0是硬编码的端点常量如果实验要求磁道数改成 100只需要把常量改成 99路径拼接逻辑不用动。direction的取值限定为up/down别用 0/1报告里的表格标题可以直接写SCAN初始向大号磁道方向比写方向1清楚得多。C-SCAN 里那个 199→0 的空跳必须计入距离这是它平均表现常常不如 SCAN 的原因漏算它就会得出C-SCAN 更优的错误结论。3.3.2 把 SCAN 写成 LOOK 的典型 bug最常见的错误是分组条件写错。用r head和r head分组磁头位置上的请求会被直接丢掉服务序列比请求序列短一个用分到右组则没问题因为它的第一步距离是 0属于磁头正好停在该磁道上立即完成。两个条件必须覆盖全部请求且不重叠这一点可以用一行断言守住assert len(order) len(req)。第二个坑是把path写成right left[::-1]省掉了端点。这样写出来的其实是 LOOK平均寻道长度会比 SCAN 小一截两种算法的结果混在一起后面的对比表就失去意义了。3.4 主程序一次跑出四种算法的对比结果# disk_sched.py片段三命令行入口与对比输出 if __name__ __main__: import argparse p argparse.ArgumentParser(description磁盘调度算法寻道长度对比) p.add_argument(--head, typeint, default53, help初始磁头位置) p.add_argument(--seq, default98,183,37,122,14,124,65,67, help逗号分隔的请求序列) p.add_argument(--dir, defaultup, choices[up, down], help初始扫描方向) args p.parse_args() req [int(x) for x in args.seq.split(,)] jobs [ (FCFS, lambda: fcfs(args.head, req)), (SSTF, lambda: sstf(args.head, req)), (SCAN, lambda: scan(args.head, req, args.dir)), (CSCAN, lambda: cscan(args.head, req, args.dir)), ] print(f{算法:8}{累计寻道:10}{平均寻道:10} 服务顺序) for name, fn in jobs: order, total fn() assert len(order) len(req), f{name} 服务序列长度不匹配 avg total / len(req) print(f{name:8}{total:10}{avg:10.2f} { - .join(map(str, order))})--seq接收逗号分隔字符串而不是位置参数是为了和报告里的数据行一一对应复制粘贴不会错位。--dir用choices约束取值传错值直接在参数解析阶段报错不会带着非法方向跑出莫名其妙的结果。循环里的断言是成本最低的自检手段服务序列长度必须等于请求个数任何一个算法少服务或多服务一个请求程序立刻停下而不是安静地输出错数据。4. C 语言实现与实验报告的数据表怎么填4.1 编译运行与核心结构多数课程要求用 C 或 C 交代码C 版本的核心就是距离累加和排序。编译时把警告打开-Wall能拦住格式化输出参数不匹配这类低级错误gcc -stdc99 -Wall -O2 disk_sched.c -o disk_sched ./disk_sched requests.txt 53 up4.2 请求序列从文件读入C 语言文件读写操作代码把请求序列放进requests.txt既方便替换数据也让报告里的测试用例有据可查。下面这段读入函数同时兼容逗号分隔和每行一个数字两种写法/* 从文本文件读取请求序列返回请求个数 */ int read_requests(const char *path, int *req, int max_n) { FILE *fp fopen(path, r); if (!fp) { perror(fopen); exit(1); } /* 文件不存在直接退出别让后面算出空结果 */ int n 0; char line[256]; while (fgets(line, sizeof(line), fp) n max_n) { char *tok strtok(line, , \t\r\n); /* 逗号、空格、制表符、换行都当分隔符 */ while (tok n max_n) { int v atoi(tok); if (v 0 v MAX_TRACK) req[n] v; /* 越界磁道号直接丢弃 */ tok strtok(NULL, , \t\r\n); } } fclose(fp); return n; }用fgets逐行读再strtok切分比fscanf(%d,)稳因为后者遇到行尾没有逗号或者多一个空格就会把格式串卡死。max_n是缓冲区上限防止请求文件被误写成几千行导致数组越界。范围校验放在读入侧磁道号超过 199 的数据在源头就被过滤不会污染后面的统计结果。4.3 实验报告的骨架每一节该放什么报告章节必写内容常见扣分点实验目的说明研究寻道优化并写明忽略旋转延迟与传输时间的简化假设只抄教材原话不写假设实验环境系统、编译器版本、源文件与编译命令缺编译命令代码无法复现算法原理四种规则的服务顺序配伪代码或文字流程用截图代替原理描述程序结构函数划分、关键变量含义、方向参数取值全篇贴代码无说明测试数据磁道范围、初始磁头、请求序列、方向设置不写方向SCAN 数据无法解释结果与分析对比表加折线图指出平均与最大值的差异只报数字没有任何解释问题与改进饥饿现象、LOOK 的优化方向、真实系统的调度器差异空泛写加深了理解4.4 数据表、折线图与结论的写法表格至少给出累计寻道长度、平均寻道长度、最大单步寻道三列折线图用请求序号为横轴、累计寻道长度为纵轴一张图里四条曲线能直观看出 SSTF 前期涨得最慢、FCFS 一路陡着上去。结论必须挂在数据上比如这一组SSTF 累计 236、SCAN 向下也是 236平均值打平但 SSTF 的最大单步 84SCAN 向下只有 65说明在这个序列上 SCAN 的等待时间更平稳而 FCFS 的最大单步高达 146是 SCAN 向下的两倍多用它做基线才显得出差距。这类平均值相同、尾部不同的观察比SCAN 优于 FCFS这种口号式的结论有价值得多。5. 进阶校验LOOK、C-LOOK 与结果正确性验证5.1 LOOK 与 C-LOOK省掉没有请求的那一段SCAN 走到 199 往往是在空扫LOOK 改成只走到最远的那个请求就折返。在同一组数据上SCAN 向上是 331LOOK 向上只有 299省下的正是 183 到 199 再折返的那一段C-LOOK 向上则是 322。改动很小把路径拼接里的MAX_TRACK换成right[-1]、0换成left[0]即可但顺序服务逻辑和 SCAN 完全一致报告里可以单独列一行做对比。5.2 三条不变量校验结果写完代码别急着截图先跑这三条断言每条服务的距离逐步累加必须等于返回的总量服务序列的长度必须等于请求个数且每个请求恰好出现一次LOOK 和 C-LOOK 服务完最后一个请求后磁头必须停在最后一个请求的位置上而 SCAN 和 C-SCAN 允许停在端点。第三条最容易发现问题——只要方向参数的判断写反最终位置就会落在错误的一端。5.3 小规模暴力枚举SSTF 并不是最优想给自己的实现找点有分量的分析素材可以用itertools.permutations枚举全部服务顺序找出真正的最短路径。八个数有 40320 种排列一秒内能跑完。结果会让人意外SSTF 贪心得到的 236 并不是最小最优值只有 208走法是先向下到 14再一路向上扫到 183。原因在一维空间里很清楚——任何一条访问全部请求的路径本质只有先到近端再扫到远端和反过来两种走法最优值就是min(head - min, max - head) (max - min)。把这段枚举脚本和公式一起写进报告的分析部分等于用实验数据证明了一个理论结论比多贴十张截图都管用。本文还有配套的精品资源点击获取
