1. 这份作业到底在练什么：先看清第十七章的知识骨架
操作系统导论第十七章，绝大多数版本讲的是空闲空间管理，核心话题就一个：磁盘上的空间被反复申请和释放之后，怎么把碎片收拾干净、怎么快速找到一块够用的空地。课后作业围绕这一章出题，本质上不是考你背概念，而是考你能不能把分配策略、碎片处理、元数据组织这三件事串起来算清楚、讲明白。
我带过几轮这门课的答疑，发现一个很普遍的现象：很多同学翻开作业题，第一反应是去翻PPT找原话，找到一句“首次适应算法从低地址开始扫描”就抄上去交差。结果题目稍微一变——比如给一串具体的申请释放序列让你画空闲链表——就完全卡住。原因很简单，这一章的题目几乎全是过程题，答案不在某一页PPT里，而在你能不能把每一步的状态变化推演出来。
所以这篇内容我打算换个讲法。不逐题报答案，而是把第十七章作业里反复出现的几类题型拆开，讲清楚每类题背后的机制、推导路径、容易算错的地方，再配上可以直接照着走的解题模板。你拿到自己那份作业时，对着题型往里套就行。适合正在做这份作业、被碎片和链表绕晕的同学，也适合想把这章真正吃透、应付考试同类题的人。
先给个全局地图。第十七章作业的题目，九成落在下面四个板块里：
- 空闲空间的组织方式：位图、空闲链表，各自的查找代价和更新代价。
- 分配策略的推演：首次适应、最佳适应、最差适应，给定序列画状态。
- 碎片问题：内部碎片和外部碎片的产生条件、量化计算。
- 元数据与一致性：超级块、inode、空闲计数的关系，崩溃后怎么恢复。
下面按这个顺序展开，每个板块都讲“为什么这么设计”和“题怎么算”。
2. 空闲空间组织：位图和链表为什么是两种活法
2.1 位图法：一位一个块，查找靠扫描
位图是最直观的空闲空间表示法。磁盘被切成固定大小的块，每个块对应位图里的一个二进制位，0 表示空闲，1 表示已分配（有些教材反过来，做题时先看清题目约定，这是第一个坑）。
位图的核心优势是空间开销极小且可预测。一块 4KB 的块，管理它只需要 1 个 bit，比例是 1:32768。一个 1TB 的磁盘，块大小 4KB，总共约 2.68 亿个块，位图大小约 32MB。这个数字作业里经常让你算，公式记牢：
位图大小 = 磁盘总容量 / 块大小 / 8（单位字节）
代入 1TB、4KB：1TB = 2^40 字节，除以 2^12 得 2^28 个块，再除以 8 得 2^25 字节 = 32MB。算的时候注意单位换算，很多同学错在把 1TB 当成 10^12 而不是 2^40，两种约定答案差 10% 左右，题目一般会说明，没说明就按 2 的幂算并在答案里注明假设。
位图的查找代价是它的软肋。要找连续 n 个空闲块，最坏情况要把整个位图扫一遍。作业里常出的题是“给定位图，找出第一个长度不小于 3 的连续空闲区”，这时候你要一位一位看，遇到 1 就重置计数器。我建议做题时把位图按 8 位一组画成表格，标出每组的连续 0 长度，比纯线性扫快得多，也不容易数错。
位图的更新代价倒是很便宜：分配或释放一个块，就是改一位，O(1)。这个不对称性——查找贵、更新便宜——是位图适合“块大小固定、分配频繁但连续分配需求少”场景的原因。
2.2 空闲链表：把空闲块串起来，查找灵活但更新麻烦
空闲链表把每个空闲块本身当作节点，块里存下一个空闲块的指针。它天然支持变长分配，因为链表节点可以按需合并。作业里最常考的是链表的合并操作：释放一个块时，要看它的前驱和后继是否也空闲，是就合并。
这里有个经典陷阱：单向链表合并后继容易，合并前驱难。因为单向链表只能顺着指针走，你释放块 B 时，知道 B 的下一个是谁，但不知道谁指向 B。所以教材里通常用双向链表或者分离的空闲链表来解决。做题时如果题目给的是单向链表，释放操作往往只要求合并后继，别自作主张去合并前驱，否则答案对不上。
链表的查找代价取决于策略。首次适应从头扫，最佳适应要扫全表，最差适应也要扫全表。作业里让你比较这几种策略时，标准答法是列一张表，从“查找代价、碎片倾向、实现复杂度”三个维度对比，而不是笼统说“最佳适应最好”。实际上最佳适应产生的碎片最小但最碎，反而可能让后续大块申请失败，这个反直觉的点是作业简答题的高频考点。
2.3 两种组织方式的选型逻辑
为什么真实系统里两种都用？因为场景不同。位图适合块大小固定、需要快速判断某块状态的场合，比如很多文件系统用它管理数据块。空闲链表适合需要按大小查找、支持合并的场合，比如内存分配器。
作业里如果问“某场景该选哪种”，判断依据就两条：分配请求是定长还是变长，查找频率和更新频率哪个更高。定长且更新频繁选位图，变长且需要合并选链表。把这个逻辑写清楚，比背结论得分高。
3. 分配策略推演：给定序列怎么一步步画状态
3.1 三种策略的本质区别
首次适应：从链表头开始，找到第一个够大的空闲块就用。最佳适应：扫全表，选够用且最小的那块。最差适应：扫全表，选最大的那块。
三者的差别不在“能不能分配”，而在把哪块空地切出去。首次适应切靠前的，最佳适应切最贴合的，最差适应切最大的。这个差别直接决定了碎片的形态。
作业里最常见的题型是：给一个初始空闲链表（比如 5 个空闲块，大小分别是 10、4、20、18、7），再给一串申请序列（比如 12、5、8），让你分别用三种策略画分配后的链表状态。
3.2 手把手推一遍首次适应
初始链表按地址顺序：[10] -> [4] -> [20] -> [18] -> [7]。
申请 12：从头扫，10 不够，4 不够，20 够，切出 12，剩 8。链表变成[10] -> [4] -> [8] -> [18] -> [7]。
申请 5：从头扫，10 够，切出 5，剩 5。链表变成[5] -> [4] -> [8] -> [18] -> [7]。
申请 8：从头扫，5 不够，4 不够，8 够，正好切完，剩 0，该节点删除。链表变成[5] -> [4] -> [18] -> [7]。
注意最后一步：切完剩 0 的节点要从链表里摘掉，很多同学忘了删，答案就多一个空节点。这是首次适应题最常见的失分点。
3.3 最佳适应为什么容易“切碎”
同样初始链表，申请 12：扫全表，够大的有 20 和 18，最小的是 18，切出 12 剩 6。链表变成[10] -> [4] -> [20] -> [6] -> [7]。
申请 5：够大的有 10、20、6、7，最小的是 6，切出 5 剩 1。链表变成[10] -> [4] -> [20] -> [1] -> [7]。
申请 8：够大的有 10、20，最小的是 10，切出 8 剩 2。链表变成[2] -> [4] -> [20] -> [1] -> [7]。
看到问题了吗？三次分配之后，链表里出现了 2、4、1 这种极小的碎片，它们单独都满足不了稍大的申请，这就是外部碎片。最佳适应“选最贴合”的直觉是对的，但它把大块切得七零八落，长期看反而降低了大块申请的命中率。作业简答题如果问“最佳适应是否总是最优”，答案是否定的，理由就是碎片化。
3.4 最差适应：切最大的，留均匀的
申请 12：最大是 20，切出 12 剩 8。链表[10] -> [4] -> [8] -> [18] -> [7]。
申请 5：最大是 18，切出 5 剩 13。链表[10] -> [4] -> [8] -> [13] -> [7]。
申请 8：最大是 13，切出 8 剩 5。链表[10] -> [4] -> [8] -> [5] -> [7]。
最差适应的思路是“把大块切小，让剩下的块尽量均匀”，避免出现极小碎片。但它的代价是每次都要扫全表，而且会把本来能应付大申请的大块提前消耗掉。三种策略没有绝对优劣，作业里让你比较时，一定要结合具体序列说结果，而不是空谈理论。
3.5 推演题的通用检查清单
做完任何一道分配推演题，按这四条自查：
- 每次分配后，被切块的剩余大小是否算对（原大小减申请大小）。
- 剩余为 0 的节点是否从链表删除。
- 链表顺序是否保持地址序（首次适应题尤其要求）。
- 所有申请结束后，空闲块大小之和是否等于初始总和减申请总和。这条是总量守恒校验，能抓出绝大多数计算错误。
提示：总量守恒校验是我强烈建议养成的习惯。做完题花十秒加一遍，比回头重算一遍快得多，考场上能救回不少分。
4. 碎片问题：内部碎片和外部碎片别搞混
4.1 两种碎片的产生条件
内部碎片：分配出去的块比实际请求的大，多出来的部分浪费在块内部，拿不回来。它产生于固定大小分配，比如块大小 4KB，你申请 1KB，剩下 3KB 就浪费了。
外部碎片：空闲空间总量够，但被切得太碎，凑不出一块连续的大空间。它产生于变长分配加反复申请释放，就是上一节最佳适应推演里出现的 2、4、1 那种情况。
作业里常出的判断题：“采用分页的系统不会产生外部碎片”——对，因为页是定长的，任何空闲页都能用。“采用分段的系统不会产生内部碎片”——对，因为段按需分配。这类题考的就是“定长对应内部碎片、变长对应外部碎片”这个对应关系，记牢就不会错。
4.2 碎片量化：作业里的计算题怎么下手
有一类题会给分配序列，让你算“最终外部碎片总量”或“最大可分配块”。做法就是完整推演一遍链表状态，然后把所有小于某个阈值的空闲块加起来。阈值题目一般会给，比如“小于 4 的视为碎片”。
计算时注意：碎片是相对概念，同样一个大小 3 的空闲块，如果后续申请都是 2，它就不是碎片；如果后续申请都是 5，它就是碎片。所以题目问碎片量时，一定结合后续申请序列判断，别脱离上下文硬算。
4.3 减少碎片的三种手段
作业简答题经常问“如何减少碎片”，标准答案有三个方向，但每个都要说清代价：
- 紧凑（compaction）：把已分配块挪到一起，空闲块合并。代价是移动数据开销大，且要求能安全移动（有些系统不允许）。
- 分页/分段：用定长或按需的虚拟化手段从根上规避某一类碎片。代价是地址转换开销和页表空间。
- 分配策略调优：比如分离空闲链表，按大小分桶，减少扫描和切碎。代价是实现复杂度上升。
答题时把“手段—消除哪类碎片—代价”三列写清楚，比罗列名词得分高得多。
5. 元数据与一致性：崩溃之后账怎么对
5.1 超级块、inode 与空闲计数
第十七章后半段通常会讲到文件系统的元数据组织。超级块记录整个文件系统的全局信息，包括空闲块总数、空闲 inode 总数。inode 记录单个文件的属性和数据块指针。空闲位图或链表记录哪些块可用。
这三者之间必须保持一致：位图里 0 的个数要等于超级块里的空闲块计数，inode 里引用的块要在位图里标记为 1。作业里常出的题是“给一个不一致的状态，问崩溃可能发生在哪一步”。
比如：位图显示某块空闲，但某个 inode 的数据块指针指向它。这说明分配块时先改了 inode 没改位图，或者释放时先改了位图没清 inode 指针。判断依据是操作顺序：安全的顺序是先占资源再改引用，释放时先清引用再放资源。这个顺序逻辑是崩溃一致性的核心，作业简答题几乎必考。
5.2 崩溃恢复的两种思路
一种是一致性检查：启动时扫全盘，比对位图、inode、超级块，发现不一致就修。代价是慢，大磁盘扫一遍要很久。
另一种是日志（journaling）：改元数据前先写日志，崩溃后重放或回滚日志。代价是每次写要多写一次日志，性能有损耗。
作业里如果让你比较，就从“恢复速度、正常运行开销、实现复杂度”三个维度列表。日志快但平时慢，检查平时无开销但恢复慢，没有银弹。
5.3 一道典型的一致性推演题
题目常这样出：给一个简化文件系统，超级块说空闲块 100 个，位图数出来 98 个 0，inode 表里有两个 inode 指向了位图标记为 0 的块。问哪里出了问题、怎么修。
推演路径：先确认位图是权威还是超级块是权威（题目一般说位图是权威），然后以位图为基准，把超级块计数改成 98，再把那两个 inode 指向的块在位图里标 1（因为 inode 引用说明它们实际被占用）。修完之后再校验一遍总数。这类题的关键是先定权威源，再单向修正，不要两边各改一半，否则越改越乱。
6. 常见失分点与排查速查表
我把答疑时见过的高频错误整理成表，做题前扫一眼，能避开大半坑。
| 失分点 | 典型表现 | 正确做法 |
|---|---|---|
| 位图 0/1 约定搞反 | 题目说 1 表示空闲，仍按 0 空闲算 | 动笔前先在草稿纸写清约定 |
| 切块剩余为 0 没删节点 | 链表里留着大小为 0 的块 | 剩余为 0 立即摘除节点 |
| 单向链表强行合并前驱 | 释放时去找前一个空闲块 | 单向链表只合并后继，或题目明确用双向 |
| 单位换算用十进制 | 1TB 当 10^12 算位图 | 看清题目约定，默认按 2 的幂并注明 |
| 碎片量脱离后续序列算 | 把所有小块都算成碎片 | 结合后续申请判断是否真碎片 |
| 一致性修复两边乱改 | 超级块和位图各改一半 | 先定权威源，单向修正后校验 |
再说两个表格装不下的经验。
第一个是画图习惯。推演题千万别只在脑子里想，一定要在纸上画链表或位图，每步标上序号。我见过太多同学心算到第三步就乱了，回头找不出错在哪。画图虽然慢一点，但可回溯，错了能定位。
第二个是简答题先写结论再展开。作业简答题阅卷是按点给分的，把“结论句”放段首，后面再解释为什么，比铺垫半天最后才亮观点得分稳。比如问“最佳适应是否最优”，第一句就写“不是，因为它倾向于产生大量小碎片”，然后再展开。
注意：不同教材对第十七章的编排略有差异，有的把空闲空间管理放在这一章，有的把文件系统实现放这一章。拿到作业先对照目录确认本章主题，再套用上面的框架。如果本章讲的是别的主题，把对应板块替换掉即可，推演和校验的方法论是通用的。
最后分享一个我自己做题时的笨办法：每道推演题做完，用反向操作验算一遍——从最终状态倒着把释放序列走回去，看能不能回到初始状态。能回去，说明正向推演没出错；回不去，就说明中间某步切块或合并算错了。这个办法比正向重算一遍更能抓出隐蔽错误，尤其是合并操作那种容易漏掉的情况。刚开始用会慢，练几道之后速度就上来了，考场上也来得及。
