操作系统习题解析：PV操作、银行家算法与页面置换的解题逻辑

1. 为什么这门课的习题值得花时间死磕如果你正在学操作系统大概率绕不开汤小丹老师这本《计算机操作系统慕课版》。这本书在高校里的覆盖率极高考研408的复习也经常拿它当参考教材。但很多人学到第三章就开始卡壳——进程同步的PV操作、银行家算法、页面置换算法课本上的例题看懂了一到课后习题就懵。这不是你笨而是操作系统这门课本身的特点决定的它的知识点不是孤立的每一道习题背后都牵扯着好几个概念的联动。我见过太多人拿着习题答案直接抄抄完觉得自己会了考试换个数字就做不出来。问题的根源在于操作系统的习题不是让你背答案的它是让你验证自己有没有真正理解机制。比如信号量机制那道经典的生产者-消费者题答案里写的是wait(mutex)在前还是wait(empty)在前顺序换一下就是死锁。你光看答案知道哦要先wait(empty)再wait(mutex)但为什么如果不去想清楚信号量之间的依赖关系下次遇到读者-写者问题照样写错。所以这篇内容不是简单地把答案罗列出来给你抄。我会按章节拆解每类题型的解题逻辑告诉你答案背后的推导过程以及我在做题和讲题过程中总结出来的那些课本上不会写但考试一定会考的细节。适合正在学这门课的学生、准备考研的复习者以及需要给这门课做辅导的助教。如果你只想找一份能直接抄的答案那这篇可能不太适合你但如果你想真正搞懂操作系统习题的套路往下看。2. 进程管理章节的习题类型与破题思路2.1 PV操作题从背答案到推答案的转变进程同步这一块的习题核心就一个东西信号量。但信号量的题目千变万化光靠背几道经典题的答案根本不够用。我的建议是拿到一道PV操作题先别急着写代码按下面这个顺序理一遍第一步找出所有进程和它们各自要做的动作。比如生产者-消费者问题里生产者往缓冲区放东西消费者从缓冲区取东西这就是两个进程、两个核心动作。第二步确定共享资源有哪些各自的容量是多少。缓冲区是共享资源容量为N互斥访问缓冲区的权限也是共享资源容量为1。这一步决定了你要定义几个信号量。第三步判断哪些是同步关系哪些是互斥关系。生产者必须等缓冲区有空位才能放这是同步消费者必须等缓冲区有数据才能取这也是同步生产者和消费者不能同时操作缓冲区这是互斥。第四步根据关系定义信号量并赋初值。同步信号量初值通常是资源初始可用数量互斥信号量初值固定为1。第五步在每个进程的动作前后加上对应的P操作和V操作。P操作申请资源V操作释放资源。这套流程走下来大部分PV操作题都能推出来不需要死记。我拿一道课本上的典型题演示一下。题目有一个仓库可以存放A和B两种产品每次只能存入或取出一件产品。要求A产品数量与B产品数量之差在[-N, M]之间。请用PV操作描述入库和出库过程。这道题的难点在于那个差值范围的约束。很多人看到这个条件就不知道信号量该怎么定义了。其实换个角度想A比B最多多M个意味着A最多领先B M个位置B比A最多多N个意味着B最多领先A N个位置。所以需要两个信号量来分别控制这两个方向的领先额度。semaphore mutex 1; // 互斥访问仓库 semaphore sa M; // A领先B的剩余额度 semaphore sb N; // B领先A的剩余额度 int countA 0, countB 0; // 存入A产品 void putA() { P(sa); // 申请A的领先额度 P(mutex); // 互斥进入 // 存入A countA; V(mutex); V(sb); // 释放一个B的领先额度因为A多了B相对落后了 } // 存入B产品 void putB() { P(sb); P(mutex); // 存入B countB; V(mutex); V(sa); }这里的关键理解是sa和sb不是直接控制产品数量而是控制两个方向上的差值空间。存入A会让A领先更多所以消耗sa、释放sb存入B则相反。这个思路一旦想通类似的差值约束题目都能套。注意PV操作题里P操作的顺序绝对不能随便换。如果两个P操作都涉及互斥信号量互斥的P一定要放在资源P的后面。否则可能出现一个进程占着互斥锁等资源另一个进程占着资源等互斥锁直接死锁。2.2 银行家算法手算表格的规范流程银行家算法是死锁避免里的重点也是考试高频考点。课本上的例题通常给一个5进程3资源的表格然后问某个请求能不能分配。很多人觉得这题简单不就是试算一下嘛。但实际操作中最容易出错的地方是安全性检查的顺序和Work向量的更新。我总结了一套手算流程按这个走基本不会错列出Available、Max、Allocation、Need四个矩阵。Need Max - Allocation这个先算好。把请求向量Request和Need比较。如果Request Need说明请求量超过了进程声明的最大需求直接拒绝。把Request和Available比较。如果Request Available说明当前资源不够让进程等待。试探性分配。Available - RequestAllocation RequestNeed - Request。执行安全性检查。这一步是核心找一个安全序列。如果找到安全序列正式分配否则回滚恢复原来的状态。安全性检查的具体做法是维护一个Work向量初始等于Available和一个Finish数组初始全false。每次找一个Need ≤ Work且Finish为false的进程假设它执行完Work AllocationFinish设为true。重复这个过程如果所有进程都能Finish说明存在安全序列。这里有个细节很多人会忽略安全序列可能不止一个你只需要找到任意一个就行。但找的时候要按顺序从头扫不要跳着找否则容易漏掉。另外Work向量在每一步都要更新不能一直用初始值。我见过一个常见的错误有人在第5步检查时把Work的初始值写成了原始的Available而不是减去Request之后的Available。这个错误会导致安全性检查结果完全错误。记住安全性检查是在假设已经分配的基础上做的所以Work的起点必须是分配后的Available。2.3 进程调度算法计算题的时间轴画法进程调度这块的习题主要是计算周转时间、带权周转时间、等待时间。算法本身不难FCFS、SJF、RR、优先级调度规则都很清晰。但手算的时候容易乱尤其是RR时间片轮转算法进程来回切换时间轴一长就容易算错。我的方法是画一条时间轴每个进程一行用不同颜色的块表示运行、就绪、等待状态。虽然这里不能用图但你可以自己在纸上画。具体步骤先按到达时间把所有进程排好。从时刻0开始看当前有哪些进程到达了。根据算法规则选择下一个运行的进程。记录它的开始时间、运行时长、完成时间。更新就绪队列继续下一步。对于RR算法关键是维护好就绪队列的顺序。新到达的进程排在队尾被时间片打断的进程也排在队尾。这个顺序不能乱否则整个时间轴就错了。周转时间 完成时间 - 到达时间。带权周转时间 周转时间 / 服务时间。等待时间 周转时间 - 服务时间。这三个公式要记牢但更重要的是理解它们的含义周转时间衡量的是从提交到完成的总耗时带权周转时间衡量的是相对于服务时间的效率。提示RR算法中如果时间片足够大大于所有进程的服务时间它就退化成FCFS。如果时间片非常小进程切换开销会变大但响应时间会变短。考试里经常考时间片取多大合适这种概念题答案通常是要大于一次上下文切换的开销同时要保证大多数进程能在一个时间片内完成。3. 内存管理习题的核心计算与易错点3.1 页面置换算法缺页率的精确计算页面置换算法的习题通常给一个页面引用串和一个物理块数量让你算缺页次数和缺页率。OPT、FIFO、LRU三种算法都要会手算。这里面的坑特别多我逐个说。OPT最佳置换算法每次淘汰未来最长时间不会被访问的页面。这个算法理论上最优但实际不可实现只用于理论比较。手算的时候你需要往后看引用串找到每个已装入页面下一次出现的位置淘汰最远的那个。如果某个页面后面再也不出现了那它就是最佳淘汰对象。FIFO先进先出算法淘汰最早进入内存的页面。这个规则简单但有个反直觉的现象叫Belady异常——增加物理块数反而可能导致缺页率上升。考试里经常考这个现象让你举一个例子。经典的例子是引用串1 2 3 4 1 2 5 1 2 3 4 5用3个物理块和4个物理块分别算会发现4个块的缺页次数反而更多。LRU最近最久未使用算法淘汰最长时间没有被访问的页面。这个算法性能接近OPT但实现开销大。手算的时候你需要维护每个页面的最近访问时间每次淘汰时间最早的那个。计算缺页率的时候注意缺页率 缺页次数 / 总访问次数。总访问次数就是引用串的长度。有些题目会问命中率那就是1减去缺页率。我总结了一个手算表格的模板你可以直接套访问顺序页面号物理块1物理块2物理块3是否缺页111--是2212-是33123是44423是..................每访问一个页面就更新一次表格。缺页的时候标记是不缺页标记否。最后数一下是的个数就是缺页次数。注意FIFO算法中如果物理块里还有空位新页面直接放入空位不算置换。只有物理块满了才需要淘汰。这个细节很多人会搞错导致缺页次数算多。3.2 分页与分段地址转换的计算套路分页存储管理里逻辑地址到物理地址的转换是必考题。题目通常给页面大小、页表内容然后给一个逻辑地址让你算物理地址。这类题的套路很固定确定页面大小算出页内偏移量的位数。比如页面大小为4KB那页内偏移就是12位因为2^12 4096。把逻辑地址拆成页号和页内偏移。页号 逻辑地址 / 页面大小偏移 逻辑地址 % 页面大小。查页表找到页号对应的物理块号。物理地址 物理块号 × 页面大小 页内偏移。看起来简单但有几个易错点。第一页面大小可能是1KB、2KB、4KB对应的偏移位数是10、11、12别搞混。第二页表里存的可能是物理块号也可能是物理地址的起始地址要看清楚题目怎么说的。第三如果题目给的是十六进制地址计算的时候要小心进制转换。分段存储管理的地址转换类似但段表里存的是段长和基址。逻辑地址 段号 段内偏移。转换时先检查段内偏移是否超过段长如果超过就是越界错误。这个检查步骤不能漏考试里经常考。段页式管理是两者的结合逻辑地址 段号 页号 页内偏移。转换过程要查两次表先查段表找到页表地址再查页表找到物理块号。计算量更大但套路是一样的。3.3 虚拟内存页面分配与抖动问题虚拟内存部分的习题经常考页面分配策略和抖动Thrashing的判断。页面分配有固定分配和可变分配两种置换有全局置换和局部置换两种组合起来有四种策略。考试里常问的是工作集模型和缺页率与物理块数的关系。工作集模型的核心思想是进程在一段时间内活跃的页面集合是相对稳定的。如果分配给进程的物理块数小于工作集大小就会频繁缺页导致抖动。题目通常会给一个引用串和一个窗口大小让你算工作集。算法是从当前时刻往前看窗口大小的引用所有出现过的页面就是工作集。抖动的原因是物理块数不够解决办法是增加物理块数或者减少多道程序度。考试里经常出概念题让你判断某个场景是不是抖动或者问怎么解决。记住一个核心原则抖动的本质是缺页率过高导致CPU利用率下降而缺页率高的原因是物理块数不足。4. 文件系统与I/O管理的习题处理4.1 文件存储空间管理位示图与索引结点的计算文件系统这块的计算题主要集中在位示图和索引结点上。位示图用二进制位表示磁盘块的使用情况0表示空闲1表示占用。题目通常给一个字的大小比如32位和块号让你算它在位示图中的位置。计算公式字号 块号 / 字长位号 块号 % 字长。注意块号通常从0开始字号和位号也从0开始。如果题目给的块号从1开始记得先减1。索引结点的计算更复杂一些。题目会给索引结点的结构比如直接地址项有10个一级间接、二级间接、三级间接各一个每个地址项占4字节磁盘块大小4KB。然后问你某个文件最大能有多大或者给一个逻辑块号问你怎么找到它。这类题的解题关键是算清楚每个间接级别能覆盖多少块。一级间接一个索引块能存4KB/4B 1024个地址项所以能覆盖1024个数据块。二级间接1024 × 1024 1M个数据块。三级间接1024^3个数据块。直接地址项覆盖10个块。所以最大文件大小 (10 1024 1024^2 1024^3) × 4KB。给逻辑块号找物理地址的时候先判断它在哪个范围。如果逻辑块号小于10直接查直接地址项。如果在10到1033之间查一级间接。以此类推。这个判断过程要熟练考试里时间紧没空慢慢推。4.2 磁盘调度算法寻道时间的计算与比较磁盘调度算法有FCFS、SSTF、SCAN、C-SCAN、LOOK、C-LOOK几种。题目通常给一个磁道请求序列和当前磁头位置让你算总寻道长度或平均寻道长度。FCFS就是按请求顺序来总寻道长度 相邻两个请求之间距离的累加。SSTF每次选最近的请求需要排序。SCAN是电梯算法先往一个方向走到底再反向。C-SCAN是循环扫描到了端点直接回到另一端。计算的时候先确定磁头的移动方向。SCAN和C-SCAN都需要知道当前方向题目一般会说明。如果没说通常默认往磁道号增大的方向。然后按方向排序请求依次计算距离。我见过一个常见的错误在SCAN算法里磁头走到端点后反向但反向后的第一个请求不是最近的而是按顺序来的。这个顺序不能乱否则总寻道长度就错了。提示考试里经常比较不同算法的总寻道长度。一般来说SSTF比FCFS好SCAN比SSTF更稳定不会饿死远端请求C-SCAN比SCAN更公平响应时间更均匀。这些结论要记住概念题会考。4.3 I/O缓冲与设备管理计算题的边界条件I/O管理部分的习题相对少一些但缓冲区的计算是个考点。单缓冲、双缓冲、缓冲池的处理时间计算关键是要理解缓冲区的作用是缓解CPU和I/O设备之间的速度差异。单缓冲的情况下处理一块数据的时间 max(CPU处理时间, I/O传输时间) 缓冲区传递时间。双缓冲的情况下如果CPU处理和I/O传输可以并行处理时间接近max(CPU, I/O)。缓冲池更复杂但核心思想是一样的。设备管理里的计算题主要是SPOOLing系统的相关计算。SPOOLing用磁盘上的缓冲区模拟脱机输入输出题目可能问输入井和输出井的容量、作业的周转时间等。这类题的关键是理清数据流向输入设备 → 输入井 → 内存 → CPU → 输出井 → 输出设备。5. 从习题答案到考试实战的转化技巧5.1 答案看懂了但不会做题问题出在哪这是最普遍的问题。很多人看答案的时候觉得哦原来是这样但合上答案自己写就卡住。根本原因是你看的是答案的结果没有看答案的推导过程。答案里写P(empty); P(mutex);你记住了这个顺序但不知道为什么是这个顺序。下次题目换成读者-写者问题信号量变了顺序也变了你就不会了。解决办法是每看一道题的答案强迫自己回答三个问题。第一这道题用了哪些信号量每个信号量的含义是什么第二每个P操作和V操作分别对应什么物理意义第三如果我把某个P操作的顺序换一下会发生什么把这三个问题想清楚这道题才算真正吃透。我建议的做法是先自己做一遍做不出来再看答案。看答案的时候不要只看代码要看文字解释。如果答案没有文字解释就自己给自己讲一遍。讲不顺的地方就是你没理解的地方。5.2 考前复习的优先级排序操作系统这门课内容多考前时间有限不可能每个知识点都平均用力。根据我的经验习题的优先级可以这样排第一优先级PV操作、银行家算法、页面置换算法。这三类是必考的计算题分值高套路固定练熟了就能拿分。第二优先级进程调度计算、地址转换、磁盘调度。这些也是计算题但相对简单一些套路更固定。第三优先级文件系统计算、I/O缓冲计算。这些出现的频率稍低但一旦考到就是大题。第四优先级概念题和简答题。这些靠平时积累考前突击效果有限但可以把课本上的关键概念过一遍。复习的时候每类题找3-5道典型题练手练到能独立写出完整过程为止。不要贪多关键是练透。5.3 那些答案里不会写但考试会扣分的细节最后分享几个我在做题和讲题过程中总结的细节这些在标准答案里通常不会特别强调但考试里不注意就会扣分。第一PV操作的代码格式要规范。信号量定义要写清楚初值P操作和V操作要写对名字有些教材用wait/signal有些用P/V要跟课本一致。代码块要标注清楚哪个是哪个进程。第二计算题要写中间步骤。比如算周转时间不要只写最终结果要把完成时间、到达时间、服务时间都列出来。阅卷老师看的是过程结果错了但过程对还能拿步骤分。第三单位要写清楚。地址转换题里物理地址是多少KB、多少字节要写明白。磁盘调度题里寻道长度是多少个磁道要标注。第四安全性检查要写出安全序列。银行家算法里找到安全序列后要把序列写出来比如P1 → P3 → P0 → P2 → P4这样阅卷老师一眼就能看出你做对了。第五页面置换要画出完整的表格。不要只写缺页次数要把每次访问后的物理块状态都列出来。这样即使最后数字算错了过程分也能拿到。这些细节看起来琐碎但考试里往往就是这些地方拉开差距。我见过太多人思路对了但格式不规范最后扣了冤枉分。操作系统这门课的习题说到底考的不是记忆力而是你对机制的理解程度。每道题都是一个具体的场景你要做的是把课本上的原理应用到场景里。这个过程一开始会慢但练多了就会形成条件反射。看到PV操作题就知道找同步互斥关系看到页面置换就知道画表格看到银行家算法就知道走安全性检查流程。到了这个程度考试就是体力活了。