说实话最开始看到实验五的题目“磁盘管理”我是有点懵的。前面进程管理实验、内存管理实验好歹能通过打印日志直观看到效果磁盘管理总不能让我把硬盘拆开吧。后来做完整轮实验才发现这个实验恰恰是整门操作系统课里最能“摸到硬件”的一次你写的每一行调度代码都对应着磁头在盘片上真实的一次移动你在终端敲下的每一条分区命令都在改动一个真实块设备的布局。广州大学2020操作系统实验五的磁盘管理实验核心任务就是用C语言模拟实现FCFS、SSTF、SCAN、C-SCAN等磁盘调度算法并在Linux环境下对照真实磁盘管理工具理解它们的意义。这篇文章会从实验设计思路、调度原理、代码实现到Linux真实工具验证完整还原一遍操作过程。无论你是在做课程作业还是想自己把磁盘调度这块彻底弄懂都可以直接拿这套路线去试。1. 实验背景与选题思路拆解1.1 这次实验到底要解决哪三个问题我拿到的实验要求分了两大部分一是用C语言模拟实现至少三种磁盘调度算法对比它们的平均寻道长度二是使用Linux下的磁盘管理命令观察真实磁盘的分区、格式化和挂载过程。读完题目就能感觉到这个实验不是单纯让你背概念而是逼着你去回答三个问题。第一个问题是磁盘一次I/O的时间到底花在哪里。教材里写的是寻道时间、旋转延迟、传输时间三部分但很多人没意识到这三者的量级差距有多大。机械硬盘的磁头寻道一次大约是几毫秒到十几毫秒盘片旋转半圈大约要4到5毫秒而真正传输一个扇区的数据只需要几十微秒。也就是说一次读操作里真正“干活”的时间可能只占几百分之一。磁盘调度要做的事情本质上是把“找位置”的时间尽量压缩。第二个问题是当多个I/O请求同时到达的时候操作系统按什么顺序处理它们。先来先服务当然公平但可能让磁头满盘乱跑每次都选最近的请求平均表现很好却可能让远处的请求一直等不到服务。这个问题没有标准答案只有取舍。实验要求用程序把这些算法跑出来用平均寻道长度这个数字说话。第三个问题是磁盘上的空间如何分配和管理。一个磁盘从物理扇区到逻辑分区再到文件系统最后挂载成一个目录中间跨越了好几层抽象。实验第二部分就是让你在Linux里亲手敲命令把这块内容从抽象变成具象。提示不同学校对磁盘管理实验的侧重点不太一样有的偏算法模拟有的偏文件系统空间管理。我这次按算法模拟加Linux命令对照的完整版本来做你完全可以只取其中一条线参考。1.2 为什么选择C语言模拟而不是直接操作磁盘一开始我也想过既然是磁盘管理实验能不能直接在虚拟机里加一块虚拟磁盘然后写代码去读写块设备后来跟同学交流才发现直接在真实磁盘上做实验风险很高一个分区命令敲错可能就是数据丢失而且调度算法的优劣在物理盘上并不容易测量。所以实验的常见做法是先用C语言把FCFS、SSTF、SCAN、C-SCAN这些调度算法抽象成数学模型用固定的请求序列模拟磁头移动再用Linux命令观察真实的磁盘分区和文件系统确认模拟里的概念确实存在于实际的磁盘管理中。环境方面我用的是一台Ubuntu 20.04的虚拟机加一个gcc编译器没有任何特殊依赖。之所以用C语言而不是Python一个是课程本身的导向另一个是C语言在处理数组、指针、内存的时候能让你更清楚地感受到请求队列这个数据结构是怎么被操作系统操纵的。用Python的话列表、排序、索引都太方便了反而不容易体会到底层细节。当然如果你自己练习用Python验证算法结论也行但实验报告和代码建议还是按课程要求的C语言来做。2. 磁盘调度核心原理与实验参数设定2.1 磁盘读一次数据物理层面到底发生了什么要写调度算法得先搞清楚磁盘读数据的物理过程。想象一下老式唱片机唱针要在唱片上找到某一段音轨的位置然后读出那一段内容。磁盘的原理类似只不过唱片换成了盘片唱针换成了磁头音轨换成了磁道。一次完整的读操作有三个步骤。第一步是寻道磁头所在的机械臂要移动到目标磁道上方。这一步是纯机械运动最慢也是调度算法重点优化的对象。第二步是旋转延迟即使磁头到了正确的磁道目标扇区也不一定正好转到磁头下方需要等盘片转到位。第三步是传输扇区经过磁头下方时把数据读出来。用一个不太严谨的类比磁盘调度就像图书馆里一个管理员取书。书在哪个架子上取决于索书号管理员每次移动推车都要时间。如果同时有很多取书请求管理员可以先排序把同一片区域的书籍一次性取完而不是取完一本跑回服务台再去取下一本。这个排序策略就是磁盘调度算法。实验模拟的时候通常忽略旋转延迟和传输时间只统计寻道长度也就是磁头移动的磁道数。这样做有两个原因一是寻道时间占总时间比例最大优化空间也最大二是旋转延迟和磁盘转速强相关在同一个盘片上参数固定不参与算法比较。所以我在代码里衡量指标就是“总寻道长度每次移动的磁道数绝对值之和”再除以请求数量得到平均寻道长度。2.2 四种经典调度算法逐个拆解先来服务FCFS是最朴素的策略请求按照到达顺序依次处理。它的优点是实现简单、公平每个请求都能等得到缺点是磁头会沿着请求的到达路径来回跑在请求分布比较散的情况下寻道路线会很曲折。这个算法用来做基准线衡量其他算法比它好多少。最短寻道时间优先SSTF每次从所有未处理的请求里选择一个离当前磁头最近的磁道处理完后再做下一次选择。它的平均寻道长度通常很短但存在一个问题如果新请求总是出现在磁头附近离磁头很远的请求可能被无限期推迟这就是“饥饿”。实验里请求序列是固定的所以看不到饥饿的累积效果但在真实系统里这是一个需要警惕的问题。扫描算法SCAN也叫电梯算法因为它的运行方式和电梯很像。磁头先朝一个方向移动沿途处理所有经过的请求移动到最内或者最外的磁道后调头反向处理请求。这样做的好处是任何请求的等待时间都有上界基本不会饿死。实验里常见的有两个版本一个是严格移动到磁道边界再回头另一个是移动到当前方向上最远的请求就折返后者也叫做LOOK算法。循环扫描算法C-SCAN是SCAN的变体。磁头只朝一个方向服务请求移动到边界后不是原路返回而是直接跳回另一端回程不处理任何请求。这样做的效果是两端磁道的请求等待时间更均匀适合负载很重的场景。C-SCAN在回程上虽然花了一整段寻道时间但从统计角度看它把磁头带回起点的方式更可预测。2.3 实验参数怎么定才公平实验里比较算法不能只用一组数据拍脑袋参数设计很关键。我参考教材经典案例把磁盘磁道范围设为0到199共200个磁道初始磁头位置设为100。请求序列用两种方式生成一组是手工指定的数据保证覆盖磁道两端和中间区域另一组是随机生成让程序自动产生20个请求多测几组看统计趋势。这里有个细节容易被忽略SCAN和C-SCAN需要指定磁头初始移动方向。我的实现里统一让磁头先向磁道号增大的方向移动也就是从100往199方向走。如果你把方向改成先向0方向走同一组数据的结果会有差异这不代表算法错了而是初始条件不同。写报告的时候必须把这个条件写清楚否则结果不可复现。请求数量也别太少。三五个请求可能随便一个算法都很接近根本看不出SSTF和SCAN的区别。20个请求以上随机性才能被平均掉一部分四种算法的差异才稳定。还有一个在报告里很容易被忽略的点SCAN到边界再折返还是到最远请求折返这两个版本的结果不同。我实验里采用的是严格扫到199再回头和一个只到184请求序列里的最远磁道就折返的LOOK版本做了对照后面会看到差别。3. 代码实现与运行结果全过程3.1 请求队列的数据结构数组和链表各有利弊写代码前要先选数据结构。请求队列的规模在实验里是固定的所以最简单的方式是用一个定长数组存请求序列再配一个整型变量记录当前磁头位置。FCFS和SSTF这样写都没问题。不过如果你像我一样把SSTF实现成“每轮从未访问请求中选最近的一个”就需要额外一个visited数组标记每个请求是否已经被处理过。这个方案有个缺陷每次选最近请求都得把所有未访问请求扫一遍时间复杂度是O(n²)。但实验请求数量最多20个这个开销可以忽略。如果想把代码写得更优雅可以用链表组织请求节点每次选完就把节点从链表里移除省掉visited数组。缺点是SCAN算法需要按磁道号排序链表排序比数组排序麻烦。我最后用的是结构体数组加visited标记关键定义如下#define MAX_REQ 64 typedef struct { int req[MAX_REQ]; // 请求涉及的磁道号 int n; // 请求个数 int head; // 当前磁头位置 } DiskQueue;使用数组还有一个实打实的好处打印调度顺序和计算平均寻道长度时下标可以直接复用方便对比多种算法在同一个请求序列上的表现。3.2 核心调度函数怎么写FCFS的实现最简单按数组顺序走一遍就行。核心逻辑就是从头到尾累加当前磁头位置与下一个请求磁道号的差的绝对值然后更新磁头位置int fcfs(int req[], int n, int head, int order[]) { int total 0; for (int i 0; i n; i) { order[i] req[i]; total abs(req[i] - head); head req[i]; } return total; }SSTF稍微复杂一点每轮要找最近的未访问请求。我额外传了一个order数组用于记录处理顺序方便后面画轨迹int sstf(int req[], int n, int head, int order[]) { int total 0; int visited[MAX_REQ] {0}; for (int i 0; i n; i) { int min_idx -1; int min_dist 1 30; for (int j 0; j n; j) { if (!visited[j]) { int dist abs(req[j] - head); if (dist min_dist) { min_dist dist; min_idx j; } } } visited[min_idx] 1; order[i] req[min_idx]; total min_dist; head req[min_idx]; } return total; }SCAN和C-SCAN的核心是排序。我先把请求序列复制一份用qsort按磁道号从小到大排序然后根据磁头当前位置把请求分为左右两段。以磁头从100往199方向移动为例先输出所有大于等于100的请求按升序再输出所有小于100的请求按降序。代码如下int cmp_int(const void *a, const void *b) { return *(int *)a - *(int *)b; } int scan(int req[], int n, int head, int direction, int order[]) { int tmp[MAX_REQ]; memcpy(tmp, req, n * sizeof(int)); qsort(tmp, n, sizeof(int), cmp_int); int total 0, cnt 0, i; // 先按移动方向处理 if (direction 1) { // 磁道号增大方向 for (i 0; i n tmp[i] head; i); for (int j i; j n; j) { order[cnt] tmp[j]; total abs(tmp[j] - head); head tmp[j]; } // 到边界 199 后折返 total abs(199 - head); head 199; for (int j i - 1; j 0; j--) { order[cnt] tmp[j]; total abs(tmp[j] - head); head tmp[j]; } } // 减小方向的代码对称略 return total; }这里有个容易搞错的点我在折返时手动加了一次从184这类最远请求到199的移动距离。如果采用LOOK版本这个到边界的移动就不加。两种口径的差异会在结果里体现出来。C-SCAN的代码在SCAN基础上改一处就行到达199后直接回到0这段距离也要计入总寻道长度因为它真实消耗了时间但途中不处理请求。然后从0继续往大磁道号方向处理刚才那些小于初始磁头位置的请求。这里注意C-SCAN的“回程”虽然不服务请求但在计算总寻道长度时不能漏掉否则平均结果会虚低。3.3 测试数据设计与运行结果为了能手动验算我用一组比较有代表性的请求序列55, 58, 39, 18, 90, 160, 150, 38, 184。初始磁头位置100。这个序列里有小磁道号18、38、39也有大磁道号150、160、184还有离100不太远的90、55、58覆盖了各种分布情况。用程序跑一遍再手工核对一遍得到的结果如下算法处理顺序总寻道长度平均寻道长度FCFS55,58,39,18,90,160,150,38,18449855.33SSTF90,58,55,39,38,18,150,160,18424827.56SCAN到199折返150,160,184,199,90,58,55,39,38,1828031.11SCANLOOK到184折返150,160,184,90,58,55,39,38,1825027.78C-SCAN到199后回0再服务150,160,184,199,0,18,38,39,55,58,9038843.11FCFS的总寻道长度最高因为磁头在198从184到199不算真正的跨度是从18到184这个范围内来回跳了好几次。SSTF在这个样本上表现最好平均27.56个磁道甚至比SCAN更优。C-SCAN因为多了一段从199回到0的199个磁道回程平均寻道长度被拉高了。我第一眼看到这个结果有点意外直觉里总觉得电梯算法应该比SSTF好才对。后来仔细想明白了原因在于数据集太小、请求分布不够均匀SSTF这种“局部贪心”策略在小规模随机数据里经常能占到便宜。想知道SCAN的优势什么时候能体现需要做更多实验。4. 实验结果分析与避坑指南4.1 为什么SCAN不一定比SSTF快很多初学者会把“先进”的算法等同于“更快”但调度算法的比较要放在具体负载特征里看。SSTF每次选最近请求本质上是在做局部最优它的平均寻道长度在绝大多数中小规模随机请求下确实不错。问题在于它缺乏“全局方向感”当请求分布比较极端比如连续出现大量磁道号在200附近的请求时磁头会长时间待在那一侧而另一侧的请求等待时间变得不可控。SCAN和C-SCAN的优势是服务质量的可预测性。磁头按固定方向扫过去每个磁道范围的请求都能在一个扫描周期内得到服务不会出现极端饥饿。在持续高负载、请求源源不断进来的生产环境里这种可预测性比平均寻道时间更重要。实验里的固定请求序列只能反映某个瞬间的快照想验证这一点需要连续生成多批随机请求并统计最坏等待时间而不是只盯着平均寻道长度。所以我做实验时没有只跑一组数据。除了上面手动验算用的请求序列我还写了个随机数生成函数分别生成了20个、50个、100个请求各跑50轮取平均值。规律很稳定SSTF的平均寻道长度最优SCAN次之FCFS最差但SSTF在某些特殊序列里会出现单个请求等待时间特别长的情况。这个观察放到报告里比单纯抄教材结论有说服力得多。4.2 会影响结果的几个参数细节处理顺序、边界策略、初始方向这三个细节之间会互相影响。我单独把影响最大的几个参数列出来供你在验证自己实现时对比。第一个是初始磁头位置。同样的请求序列初始磁头在100和初始磁头在10SSTF的结果会差很多。初始磁头正好落在请求密集区SSTF前几步的寻道距离会非常小平均数据好看初始磁头落在请求稀疏区前几步就要跨很大距离。实验中统一把初始位置设为100就是为了给所有算法一个相同的起点。第二个是SCAN的边界策略。到物理边界199折返还是到当前方向上最远请求184折返平均寻道长度差了大约3.33个磁道。很多教材例题为了手算方便都采用“到最远请求折返”的口径但代码实现时如果没注意可能会在循环里多算或少算一段边界距离。我建议在报告里同时给出两种结果并说明你用的是哪一种。第三个是C-SCAN的回程计算。回程从199回到0这199个磁道是真实存在的机械移动必须计入总寻道长度。有的同学图省事回程不计数算出来的平均寻道长度会凭空少一大截和理论值对不上。这是我在查同学代码时发现的高频问题写报告时尤其要注意。4.3 写代码时容易踩的坑第一个坑是SSTF死循环。如果visited数组忘记标记某个请求已经处理过第二轮扫描又会选同一个请求导致后续所有选择都混乱甚至永远跳不出去。调试方法很简单在循环开头打印当前选中的请求下标和磁头位置一看就明白。第二个坑是SCAN排序后没有正确处理方向。排序只是把请求变成有序列表不等于磁头就能按序访问。要做到这一点必须找到第一个大于等于当前磁头位置的元素下标然后按方向分别遍历左右两段。我刚开始写的时候直接用排序后的数组从头扫到尾结果磁头从100出发先处理了18和38这种比100小的请求方向就反了。第三个坑是平均寻道长度的分母。如果你统计的是从初始磁头位置到第一个请求的第一次移动那么总移动次数等于请求个数n平均总距离/n。但如果是C-SCAN这种带回程的算法回程这段不计入“服务请求”的移动却计入总距离分子分母的含义容易混淆。我做了一个辅助函数专门统计实际服务请求的次数宁可多写几行也不要口头约定不清。5. Linux环境下的真实磁盘管理对照实验5.1 把命令和磁盘管理概念一一对应模拟算法跑完之后实验要求还包含使用Linux磁盘管理命令理解真实磁盘布局。我是在Ubuntu 20.04虚拟机上操作的以下命令只要不执行危险的分区或格式化操作在物理机上也可以安全查看。先用lsblk查看块设备拓扑这个命令列出的是磁盘和分区的树状关系。比如我的虚拟机里有一块sda磁盘下面分出了sda1和sda2两个分区一个挂载到/一个作为swap。lsblk输出的SIZE、TYPE、MOUNTPOINT列直接对应着物理扇区之外的分区和文件系统抽象层。再看df -hT这个命令查的是文件系统状态。它的输出里会有Filesystem、Type、Size、Used、Mounted on解释的是逻辑卷标之上、用户能直接感知的那一层。我一般把lsblk和df搭配看前者回答“磁盘怎么分块”后者回答“每块上文件系统用了多少”。fdisk -l可以查看更底层的分区表细节。在虚拟机里执行fdisk -l /dev/sda能看到分区起始扇区、结束扇区、大小和类型。START和END标记了分区占用的扇区范围这就是操作系统管理磁盘空间时的物理边界。需要注意的是fdisk写入模式下危险很高纯查看没问题但别在生产环境随便执行w。格式化与挂载是另一组对照概念。我在虚拟机里用dd创建了一个1GB的纯镜像文件然后通过losetup挂为loop设备在上面执行mkfs.ext4创建文件系统再用mount挂载到目录。这相当于在一个完全可控的“假磁盘”上完整演示了从分区、格式化到挂载的流程既能观察真实命令行为又不会破坏任何现有数据。如果你也想在实验里复现建议照这个安全路线做。命令作用对应概念lsblk查看块设备与分区拓扑物理磁盘 / 分区df -hT查看文件系统挂载与使用文件系统逻辑层fdisk -l查看分区表起始结束扇区分区表mkfs.ext4在分区上创建文件系统格式化mount / umount挂载 / 卸载文件系统挂载点5.2 操作系统的IO调度器和实验里的算法有什么关系做完模拟实验后我一直有个疑问现实中Linux真的在用我们写的SCAN或SSTF吗查了一圈发现Linux内核的IO调度器在历史上确实实现过类似电梯算法的逻辑比如早期的anticipatory和cfq调度器核心思想就是合并相邻请求、按扇区顺序批量处理。后来SSD普及寻道时间不再是主要矛盾内核默认调度器改成了对SSD更友好的none或mq-deadline但合并相邻请求的思路依然保留。这恰好在实验里能形成一个对照观察。我跑了一个压力测试用dd从磁盘多个位置随机读小块数据同时用iostat -x 1观察磁盘利用率。你能看到await和util数值的变化机械磁盘上的util会很高说明磁头一直在忙而这个“忙”很大程度是在寻道。如果把读请求改成顺序读util立刻下降吞吐显著上升。这个过程比任何文字都直观地说明了磁盘调度为什么重要。注意iostat不是所有系统都自带如果提示命令找不到先执行sudo apt install sysstat安装。观察时重点关注await平均I/O响应时间和%util设备繁忙程度这两个指标和实验里仿真的平均寻道长度直接对应。模拟实验和真实命令验证是互补的。模拟算法让你在可控条件下理解每种策略的数学性质真实命令让你看到这些数学性质在物理设备上如何表现。做完这一套对照再回头看实验要求里的“磁盘管理”四个字含义就完全不一样了。6. 一点个人套路之外的体会最后说点我做完这个实验后一直想分享的事情。磁盘调度算法在教材里就那么几页读起来很快但只有自己把请求序列一个个手算、再让程序跑一遍才会真正理解为什么SSTF在课本的例子里总是最优而生产环境里却需要担心饥饿问题。我做实验的时候额外做了一件事把生成的请求序列画在一张坐标纸上把每种算法的磁头移动轨迹画成折线。FCFS的折线像心电图一样乱跳SCAN的折线像梳子一样整整齐齐直观得让人一下子记住它们的区别。如果你也在做这个实验强烈建议试试这个方法比盯着终端里的数字强得多。后续如果想继续深挖可以把算法改成多线程版本用pthread模拟多个进程同时发起I/O请求再引入一个共享请求队列这就是真实操作系统的样子了。实验能做得很深但核心还是先把这四种算法吃透。