1. 先想清楚你手里的习题答案到底该怎么定位每到学期中后段计算机操作系统这门课的复习资料就会在班级群里疯传最抢手的那份往往就是《计算机操作系统》汤小丹第四版的课后习题答案。我见过太多人把它当成通关秘籍——把 PDF 打印出来对着题目一行行抄抄完感觉整本书都懂了结果考试时换了个条件脑子直接空白。这不是记忆力的问题是把答案的定位搞错了。习题答案真正的价值是一面镜子用来照出你的推导过程和参考思路之间的差距在哪里而不是一个可以直接复制的成品。操作系统这门课有个很鲜明的特点它的题目普遍带有变量同一道题把进程数从 3 改成 5、把信号量初值从 1 改成 0答案的结构就完全不一样了。你抄下来的那几行 PV 操作脱离原始条件之后基本没有迁移能力。所以这份材料怎么用顺序很重要。我个人的建议是先自己完整写一遍哪怕写得很难看、写得不对也要写。写完再翻答案重点看两件事——第一它的解题起点是从哪里切入的是先从资源分配表入手还是先找临界资源第二它在哪些地方做了简化表述答案常常会写其余类似、略这些地方恰恰是考点。这两件事想明白了一份答案能顶十道题。还有一个心态问题值得说。计算机操作系统这个领域概念密度特别高进程、线程、管程、协程、死锁、虚拟内存、文件系统每一个名词背后都是一整套机制。习题答案能帮你验证这个机制我理解得对不对但它帮不了你建立机制之间的联系。真正拉开分差的是你能不能把页面置换和虚拟内存的地址变换串成一条线能不能解释清楚为什么有了信号量还需要管程。这些联系答案里通常不会写。提示拿到任何一份课后习题答案第一件事是核对版本。汤小丹这本书出到第四版之后章节顺序和部分习题编号有过调整网上流传的很多答案是按第三版整理的题号对不上容易越看越乱。1.1 答案不是标准解而是思路的对照物操作系统里很多题目并没有唯一正确的写法。最典型的是同步互斥问题生产者-消费者模型你可以用两个信号量加一个互斥信号量实现也可以把缓冲区的计数逻辑揉进一个信号量里读者-写者问题读者优先和写者优先的写法差异很大。答案给出的只是其中一种而且往往是教科书式的、为了排版简洁而做过精简的那一种。我在帮同学看作业时发现一个现象那些习惯对着答案逐字比对的人一旦遇到答案里没有的问题类型就彻底不会动笔了。因为他们脑子里存的是一道道具体的题而不是一类问题的处理套路。反过来那些先自己想、再看答案的人会主动去问它为什么不这样做这种追问才是理解的开始。1.2 操作系统习题的三类错误纠正方式完全不同把错题做分类是提高效率最快的一步。我一般把它分成三类错误类型典型表现纠正方式概念性错误把管程和协程的作用搞混把死锁和饥饿混为一谈回到教材原文重新读定义找出两者的判定条件差异计算性错误页面置换命中率算错磁盘调度移动距离累加漏了一端手推表格每一步都写下来不跳步表述性错误思路对了但写出来的步骤缺前提条件或者结论没有说明适用场景对照答案的组织结构补齐前提、过程、结论三段这三类的处理成本差别很大。概念性错误最贵因为它会连着后面好几章一起塌表述性错误最便宜改两三次就能形成习惯。很多人复习时把精力平摊其实应该优先砸在概念性错误上。1.3 一个我踩过的坑答案抄得越熟读题能力越差大二那年我就是典型的答案收集癖。攒了三个版本的答案 PDF还有一份学长手写的笔记觉得自己资源齐全。结果期末考第一道大题题面条件比我抄过的任何一道都多两个约束我盯着题目看了五分钟脑子里找不到对应的模板。那次考试的计算题我几乎全军覆没。后来我反思问题出在读题这一步被我省略了。抄答案的时候我默认题目条件都是标准配置从来没训练过从题面里提取约束条件的能力。操作系统的大题题面往往就是一份浓缩的系统描述谁先能把这些描述翻译成进程、资源、信号量、页表谁就先赢一半。从那以后我改了做法拿到题目先不看答案用铅笔在题面上圈出所有数量、初值、约束然后自己画一张简单的状态图或者资源表再动手写。这个习惯养成之后读题速度快了很多也再没出现过看懂了但不知道从哪下手的情况。2. 汤小丹第四版的知识骨架哪几章是计算重灾区哪几章是概念重灾区复习之前得先有一张权重地图。这门课的课时分配和考点分布并不均匀有些章节几乎全是概念有些章节则是一道接一道的计算。把这门课的骨架拎清楚复习的优先级自然就出来了。2.1 全书章节的权重地图按我的经验这本书的内容大致可以分成四大块进程与处理机管理、内存管理、文件管理、设备管理再加上开头的一章概述和结尾的接口、安全相关的补充内容。这四块的考试分量差别很大我自己总结的权重大概是这样的模块核心内容考题形态相对权重概述操作系统定义、发展、基本特征、主要功能选择、名词解释低但概念题必考进程与处理机管理进程状态、同步互斥、调度、死锁大题集中区PV 操作、调度计算、银行家算法最高内存管理连续分配、分页分段、虚拟内存、页面置换地址变换计算、置换算法推演很高文件管理逻辑结构、物理结构、目录、索引节点索引结构计算、目录检索中设备管理IO 控制方式、缓冲、磁盘调度磁盘调度计算中计算部分很明确这张表的意义在于分配时间。进程管理和内存管理这两块几乎占据了大题总分的一半以上而且这两块的计算非常依赖熟练度光看懂不行必须手推。相对而言概述那一章的内容适合用碎片时间反复过不需要大块时间。2.2 计算题集中在哪几个具体位置如果你时间紧张只看计算题下面这几个点是绕不过去的信号量机制与 PV 操作生产者-消费者、读者-写者、哲学家进餐以及各种变形题。进程调度算法先来先服务、短作业优先、高响应比优先、时间片轮转通常要求计算平均周转时间和平均带权周转时间。银行家算法给出资源分配表求安全序列或者判断某个请求能否满足。页面置换算法先进先出、最近最久未使用、最佳置换以及时钟算法通常要求填表并算缺页率。地址变换分页、分段、段页式系统中逻辑地址到物理地址的转换涉及页表、页表寄存器、快表。磁盘调度算法先来先服务、最短寻道时间优先、扫描算法、循环扫描算法计算磁头移动总距离。文件物理结构连续、链接、索引结构下的记录访问次数以及多级索引能表示的最大文件长度。这七类题目基本上覆盖了操作系统计算题的绝大部分。我的做法是把每一类单独建一个文件夹每类至少手推十道不同条件的题直到看到题面就能条件反射地知道用哪张表。2.3 概念题里最容易丢分的表述细节概念题看起来好拿分实际上失分点非常隐蔽。举几个我印象深刻的例子第一并发和并行这两个词很多人写答案时混着用。并发指的是多个程序在同一时间段内交替执行宏观上像是同时进行并行指的是在同一时刻真正同时执行需要多处理机或者多核支持。这一字之差判断题里直接判错。第二谈到进程和线程的区别只说线程更轻量是不够的得说到资源拥有和调度单位这两个维度进程是资源分配的基本单位线程是处理机调度的基本单位同一进程内的线程共享该进程的资源但各自有独立的栈和寄存器上下文。第三死锁的四个必要条件很多人能背出来但被问到破坏其中哪一个条件最常用时答不上来。实际系统里最常做的是破坏请求并保持和不可剥夺前者靠资源一次性分配后者靠资源抢占。第四分页和分段的区别重点不在页是物理划分、段是逻辑划分这一句而在于分页对用户透明、分段对用户可见以及两者的地址空间维度不同。答题时把这两点写出来才算答完整。3. PV操作与同步互斥习题答案里最容易被简写掉的部分同步互斥是这门课公认的难点也是习题答案省略最多的地方。很多答案为了让页面整洁会把一些设置信号量初值、判断条件顺序的细节一笔带过而这些细节恰恰是判卷时看的东西。3.1 信号量题的通用解题框架我处理这类题有一个固定的四步框架写熟了之后速度很快找临界资源题面里被多个进程共同访问的对象是什么缓冲区、表格、打印机还是某个变量。拆解约束进程之间是互斥关系抢同一资源还是同步关系有先后依赖还是两种都有。给信号量起名字并定初值互斥信号量初值一般是 1同步信号量初值取决于资源的初始数量。写代码时保证 PV 配对同一个临界区内P 在进入前、V 在退出后一个不落。这个框架的好处是即使题目变形你也只是把第三步的名字和初值换掉骨架不用重写。我在考场上遇到没见过的题也是靠这个框架硬拆出来的。3.2 三种经典模型的变形套路生产者-消费者模型的变形方向通常是缓冲区容量变化、增加一类进程、增加一个额外条件比如必须先取出才能放入。不管怎么变核心永远是两个同步信号量管空位和满位一个互斥信号量管缓冲区的访问。读者-写者模型的关键分歧点在优先级。读者优先的写法里写者可能长期得不到执行写者优先则需要在信号量之外再加一个计数器和一个信号量来控制新读者的进入。考试里如果只写了读者优先的版本被问到这样会不会导致写者饥饿时要能答出来。哲学家进餐模型考的是死锁避免。最直白的写法是五个人同时拿起左边的筷子然后等右边的这个写法必然死锁。常见的三种改法一是限制最多四个人同时拿筷子二是要求奇数号先拿左、偶数号先拿右三是用一次性的互斥信号量把拿两只筷子变成原子操作。这三种改法在答案里经常只出现一种但你都应该掌握。3.3 答案里那几行省略到底省了什么我专门统计过几个流传较广的答案版本发现省略主要出现在三个地方初始化的写法答案经常只写semaphore mutex 1;这一行但不解释这个 1 是怎么来的。实际上初值是该资源在同一时刻允许被访问的进程数互斥场景下就是 1。循环结构的边界while(1)还是for(;;)无关紧要但P(empty)和P(mutex)的先后顺序是有讲究的——先申请资源信号量再申请互斥信号量顺序反了在某些场景下会引入死锁风险。计数器的更新位置读者-写者模型里读者计数器的加减必须在互斥区内答案有时会写在外面这是错的。注意如果你看到某份答案里P(mutex)出现在了P(empty)之前先别急着照抄。这个顺序在缓冲区满的情况下可能导致持有互斥锁的进程被阻塞其他进程也无法进入灵活性明显下降。4. 银行家算法、页面置换、磁盘调度手推一遍比看十遍答案有用这三类题目有个共同点看起来机械实际极容易出错而且错误往往不是理解问题纯粹是流程不完整导致的。我的经验是这几类题必须手推而且要推够数量形成肌肉记忆。4.1 银行家算法的安全序列判定银行家算法的标准流程是先算出每个进程的 Need 矩阵Max 减去 Allocation再算系统的 Available 向量然后从第一个进程开始逐个检查 Need 是否小于等于 Available能满足就假定它执行完并释放资源更新 Available继续往下找。这里容易出问题的地方有两个。一是顺序很多人从第一个进程开始找找到一个就往下走但正确的做法是每一轮都要从头扫一遍因为 Available 在更新之后原本不满足的进程可能变得满足。二是多个安全序列题目往往只要求给出一条但答案如果有多个要能判断出自己找到的那条是否合法。举个简单的核对方法。假设系统有 A、B、C 三类资源初始 Available 是 (3, 3, 2)进程 P0 的 Need 是 (7, 4, 3)这一看就不满足直接跳过P1 的 Need 是 (1, 2, 2)满足进入序列。这个先排除明显不满足的策略能帮你快速缩小范围。4.2 页面置换的表格填写与命中率计算页面置换题的标准格式是一张表列是页面访问序列行是物理块最后一列标注是否缺页。这类题我建议用铅笔在草稿纸上画表格每个格子都填满不要跳步。三类算法的区别必须说清楚。先进先出算法淘汰最早进入内存的页面实现简单但可能出现 Belady 异常也就是物理块增加反而缺页率上升最近最久未使用算法淘汰最长时间未被访问的页面性能接近最佳置换算法但需要硬件支持最佳置换算法淘汰未来最长时间不会被访问的页面理论最优但无法实现通常只作为性能比较的基准。时钟算法是最近最久未使用算法的一种近似实现用一个循环指针扫描访问位访问位为 1 就清零并继续为 0 就淘汰。答题时要把指针停留的位置写清楚很多人漏掉这一步导致后续步骤全错。4.3 磁盘调度的移动距离累加磁盘调度题的答案通常是一串数字和最后的累加值中间的推导过程被压缩了。我建议自己把每一步的磁头位置都写出来这样既能检查错误也方便回看。算法核心规则常见坑先来先服务按请求到达顺序服务移动距离大但不会漏最短寻道时间优先每次选最近的请求边界处的请求可能长期得不到响应扫描算法沿一个方向扫到底再折返折返点的位置容易算错循环扫描算法只沿一个方向服务回程不服务回程距离是否需要计入要看清题意累加的时候最大的坑是起点的处理。磁头初始位置到第一个被服务请求的距离必须计入很多人从第一个请求到第二个请求才开始算结果整体偏小。另外扫描算法里如果题目限定了当前移动方向折返点的选择会不一样读数时要特别小心。5. 管程和协程教材里最容易被混为一谈的一对概念这两个词经常一起出现在搜索热词里也经常被初学者搞混。它们名字里都有个程字但解决的问题、所在的层次、调度权归属完全是两回事。我把它们放在一起讲是因为很多习题答案在涉及这两个概念时表述都偏简略。5.1 管程到底解决了什么管程是一种高级同步机制它把共享变量和对这些变量的操作封装在一起同一时刻只允许一个进程进入管程内部执行。你可以把它理解成一个自带门禁的房间房间里放着共享数据和操作这些数据的方法门禁保证一次只进一个人。管程的价值在于把信号量的使用藏了起来。用信号量的时候P 和 V 要程序员自己写在正确的位置写错了就死锁管程把同步逻辑封装在内部使用者只需要调用方法不用关心底层信号量怎么用。管程内部通常配合条件变量使用当某个条件不满足时进程在条件变量上等待条件满足时由另一个进程唤醒。这里有个细节值得强调管程的互斥是编译器和运行时自动保证的不需要程序员手动加锁。这正是它相对于信号量的最大优势也是它被引入高级语言比如 Java 的 synchronized 块、各种语言里的监视器的原因。5.2 协程的调度权在谁手里协程是用户态的轻量级执行单元它的切换不经过操作系统内核由程序自己在合适的时机主动让出。这一点是它和线程最本质的区别线程的调度权在内核手里切换需要陷入内核态开销较大协程的调度权在程序手里切换就是一次普通的函数调用级别的操作开销小得多。正因为调度权在程序手里协程特别适合IO 密集型的任务。比如一个程序要发起大量网络请求用线程的话每个线程的大部分时间都在等待白白占用内核资源用协程的话在等待的时候主动让出让同一个线程去处理其他任务整体吞吐量能高很多。需要说清楚的是协程并不能提供并行能力。在单线程里跑协程任何时刻仍然只有一个协程在执行只是它们之间切换的代价比线程小得多。这一点和管程、和并发概念都不一样别混在一起。5.3 一张对照表把它们彻底分开对比维度管程协程所属层次语言/机制层的同步工具用户态的执行单元解决的核心问题共享资源的互斥访问与条件同步高并发下的执行单元切换开销调度权归属不涉及调度管的是进入许可程序自身主动让出切换开销不涉及上下文切换极低不陷入内核是否需要操作系统支持依赖编译器/运行时通常由语言库或运行时实现典型用法封装共享数据结构条件变量等待唤醒IO 密集任务并发、生成器、异步流程把这张表记牢遇到概念题基本不会错。这里我特别想提醒一句管程和协程不是竞争关系也不是替代关系。你完全可以在一个用协程实现的并发程序里用管程或者说监视器来保护共享状态。它们在不同的层次上解决不同的问题。5.4 为什么这两个词会同时成为热词从学习路径上看管程出现在同步互斥那一章是信号量之后的高阶内容协程则更多出现在操作系统教材的补充阅读、或者并发编程相关的课程里属于教材讲了概念但没展开的那一类。学生在复习时同时搜索这两个词多半是因为期末考试里出现了对比题或者课程设计要用到。我的建议是把这两个词分别归到各自的体系里去记。管程归到同步机制这条线忙等待、信号量、管程是一个逐步抽象、逐步封装的过程协程归到执行单元这条线进程、线程、协程是一个逐步轻量化、逐步把调度权从内核转移到用户态的过程。两条线的起点和终点都不一样硬放在一起背只会越背越乱。6. 慕课版、第四版和网络答案的差异怎么搭配才不打架汤小丹这本教材的版本情况稍微有点复杂。除了经典的第四版还有配套慕课课程使用的版本两者的章节编排和习题编号存在差异。这一点在复习时会带来实实在在的困扰。6.1 版本差异带来的具体麻烦最直接的问题是题号对不上。同一道同步互斥的大题在第四版里可能是第 3 章第 12 题在慕课版的习题集里可能挪到了别的位置。如果你手上拿的是按第四版编的答案而课程用的是慕课版对着题号找会非常痛苦。第二个问题是侧重点不同。慕课版因为要配合线上学习和讨论往往会把一些概念性的内容拆得更细习题里概念解释题的比重会高一些第四版作为长期使用的教材经典的计算题型保留得更完整。第三个问题是表述方式的差异。同一道题不同版本的题面描述可能略有出入比如资源的初始数量、约束条件的顺序这些细节会影响解题过程。6.2 网络答案的三种典型质量层次我接触过的答案大致能分成三档第一档带完整推导过程的。这类答案会把每一步的计算写清楚包括中间变量的更新。遇到这种重点看它的推导顺序。第二档只给最终结果的。这类答案的价值在于校对你得自己先做一遍再用它对答案。第三档结果本身有争议或者错误的。这类答案最难处理因为你要先判断它错在哪。判断方法很简单——用教材里的定义和公式重新推一遍看能不能得到同样的结果。第三档的存在也是我一直强调别直接背答案的原因之一。你背下来的可能本身就是错的。6.3 我的交叉核对方法我现在处理版本问题的方式是以任课教师指定的教材版本为准其他版本只作为题型补充。具体做法是建一个表格把每一章的题目按题型而不是题号归类比如信号量实现类、调度计算类、地址变换类然后从各个版本的答案里挑对应的题目放进来。这样整理一遍的好处是你关注的就不再是第几题而是哪种类型。题型是跨版本稳定的题号不是。提示整理题型的时候顺手把每类题的变体条件记在旁边比如缓冲区容量 3 改成 5 时答案怎么变。这些东西在考场上比原题的答案有用得多。7. 把习题变成能跑的小实验几段代码验证你的答案纸上推演再多也不如跑一遍代码来得实在。操作系统这门课虽然理论性强但很多算法完全可以用几十行代码模拟出来跑出来的结果和你的手推结果一比对对错立刻分明。7.1 用 Python 模拟页面置换下面这段代码实现了三种页面置换算法输入物理块数和访问序列输出缺页次数和缺页率。跑一遍再和你的手推表格对照很容易发现自己在哪一步记错了。def fifo(pages, frames): memory, faults, queue [], 0, [] for p in pages: if p not in memory: faults 1 if len(memory) frames: memory.append(p) else: victim queue.pop(0) memory[memory.index(victim)] p queue.append(p) return faults, round(faults / len(pages), 4) def lru(pages, frames): memory, faults [], 0 for p in pages: if p in memory: memory.remove(p) else: faults 1 if len(memory) frames: memory.pop(0) memory.append(p) return faults, round(faults / len(pages), 4) def opt(pages, frames): memory, faults [], 0 for i, p in enumerate(pages): if p in memory: continue faults 1 if len(memory) frames: memory.append(p) else: farthest, victim -1, None for m in memory: nxt pages[i 1:] idx nxt.index(m) if m in nxt else float(inf) if idx farthest: farthest, victim idx, m memory[memory.index(victim)] p return faults, round(faults / len(pages), 4) seq [7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1] for name, fn in [(FIFO, fifo), (LRU, lru), (OPT, opt)]: print(name, fn(seq, 3))把这段代码跑一遍你会看到一个很直观的现象物理块数从 3 增加到 4 的时候先进先出算法在某些序列上缺页次数不降反升。这就是教材里提到的 Belady 异常用代码验证一次比背十遍定义记得牢。7.2 用多线程验证信号量题同步互斥的题目可以用线程加锁的方式验证逻辑。Python 里没有原生的信号量 PV 操作但可以用threading.Semaphore模拟。写一个生产者-消费者的小程序把缓冲区大小设成 1观察输出顺序就能理解为什么互斥信号量和同步信号量的顺序不能反。需要提醒的是Python 因为有全局解释器锁多线程的并发效果不明显验证逻辑可以验证性能不行。如果想看真正的并发效果可以用多进程或者换个语言写。不过对于验证 PV 操作的逻辑正确性多线程已经完全够用了。7.3 验证之后的收获我自己跑完这些代码之后有两个明显的收获。第一对边界条件的理解深了很多。手推的时候我经常会忽略第一个请求或者最后一个请求的特殊处理代码会强制你把每一个元素都走一遍。第二对算法的代价有了直观感受。最近最久未使用算法手推的时候感觉很自然写代码时才发现需要维护访问顺序这就是为什么实际系统里更常用时钟算法这种近似实现。这种理论-代码-再回理论的循环是这门课效率最高的一种学习方式。习题答案只给你结果代码给你过程。8. 复盘阶段错题本和手推清单怎么建复习到后期比的不是谁资料多而是谁的错误清单短。我建议在考前两周左右把之前做的题全部过一遍重点整理错题。8.1 错题本上该记什么只记题目和正确答案价值不大。我记的是三样东西这道题的陷阱在哪、我当时是怎么想错的、下次遇到同类题该从哪切入。举个例子银行家算法里 Available 的更新时机我记的是我在第二轮扫描时忘了重新从头扫导致漏掉了 P3。这种记录方式下次复习的时候一眼就能想起来。错题本不用记得多漂亮用最粗糙的方式记就行。我那时候就是一张纸对折左边抄题目关键条件右边写自己的错误点和纠正思路两周下来攒了三十多条考前翻一遍只要二十分钟。8.2 考前必须能手推的清单下面这七件事如果不能在白纸上完整推出来考场上大概率会卡壳生产者-消费者模型的两个同步信号量加一个互斥信号量的完整代码。三种页面置换算法在一组访问序列上的完整表格和缺页率。银行家算法求安全序列的完整扫描过程。两级页表下逻辑地址到物理地址的转换步骤。四种磁盘调度算法的磁头移动距离累加。索引结构下给定索引节点和块大小计算最大文件长度。进程三态转换图中每一种转换的触发条件。这七件事覆盖了绝大多数计算题的骨架。能推出来考试时的计算题基本就稳了。8.3 我个人的一点体会最后说点实在的。这门课我前后学过两遍第一遍是应付考试靠着答案和笔记混过去了考完就忘第二遍是因为做课程设计被迫重新啃了一遍。奇怪的是第二遍看的时候我发现很多当时觉得抽象的概念突然都能对上现实里的东西了——进程调度像食堂打饭的排队规则缓冲机制像快递驿站的临时堆放虚拟内存像图书馆的书架和借阅台的关系。我现在回头看当年那份习题答案给我带来的最大价值不是那些被我抄下来的解法而是在我抄不下去、被逼着回到教材重新推导的那些时刻。真正留在脑子里的东西都是在那些时刻建立起来的。如果你现在正拿着这份答案发愁我的建议是把它合上先自己写一遍哪怕写得很烂。写完了再打开看你会发现它的价值翻了好几倍。