拿到这份2016年操作系统真题还原版的时候我正帮几个考研的学生做考前梳理。第一遍过完整套卷子我的判断是这是一份被严重低估的复习材料。它的知识点覆盖非常典型进程管理、内存管理、文件系统、I/O与死锁这几大板块全部命中大题出题风格跟后面几年的408统考也高度吻合。无论你是在准备操作系统期末复习还是瞄准考研408这份题都值得从头到尾刷两遍。这篇文章我会按考卷的实际布局把每类题背后的操作系统知识点、手算过程和踩坑点拆开讲清楚目标只有一个让你看完能直接上手做题而不是看了一堆概念回头还是不会算。1. 先看整体这张还原版卷子到底考了什么1.1 题型分布和分值占比操作系统这门课有个特点章节之间相对独立考来考去就那几个固定模块。2016年这份还原版卷子也不例外整体结构大致是单选题、填空题、简答题和综合应用题四类。从分值上看进程管理占比最高大概三成内存管理紧随其后占两成五左右文件管理和设备管理各占一两成死锁和操作系统概述相关的小题穿插在选择题和填空题里。我习惯把分值画成一张表来定位复习重点考查模块常见题型大致分值占比复习优先级进程管理含处理机调度、同步互斥选择、填空、PV大题30%左右极高内存管理分页、分段、页面置换选择、填空、综合计算25%左右极高文件系统目录、分配方式、磁盘调度选择、简答、计算20%左右高设备管理I/O控制、缓冲、SPOOLing选择、填空、简答15%左右中死锁必要条件、银行家算法选择、综合计算10%左右高这张表不是让大家去猜题而是提醒你精力分配进程和内存这两块一旦出大题就是十五到二十分的大题性价比最高文件系统里的磁盘调度和混合索引也是稳定的大题来源死锁部分基本围绕银行家算法出综合题。把这些位置盯住了及格不是问题冲刺高分也才有基础。1.2 命题风格为什么说它是408方向的风向标很多同学一上来就刷各种难题偏题反而把基础计算忽略掉这是大忌。2016年这套还原卷的风格跟408统考非常接近不考背诵型论述考的是给一组数据你能不能算对。比如处理机调度给你进程到达时间和服务时间让你算先来先服务和短作业优先的平均周转时间比如内存管理给你逻辑地址和页表让你算物理地址比如磁盘调度给你磁道请求队列让你算四种调度算法的寻道长度。这些题没有任何弯弯绕绕拼的就是对概念的理解和手算的细心程度。所以这套卷子真正的价值在于练手。它把操作系统的核心计算题几乎覆盖全了你每做一道就等于把这一类题的通用解法过了一遍。后面我在文章中会把这些大题的完整推导过程写出来你可以对照自己的草稿纸找差距。2. 进程管理与处理机调度送分和送命往往只差一步2.1 状态转换和PCB别在这种题上丢分进程管理的选择题里进程三态转换几乎是必考的就绪态、运行态、阻塞态外加新建态和终止态。这里有个高频陷阱一个进程从运行态变成阻塞态是它主动等待某个事件比如等待I/O完成而一个进程从运行态变成就绪态通常是被迫的时间片用完或被更高优先级进程抢占。2016年这套卷子里就有一道辨析题选项故意混了主动和被动的关系一不留神就选错。关于PCB进程控制块我建议大家记四个字系统感知。操作系统并不是直接管理进程而是通过PCB来管理进程PCB是进程存在的唯一标志。凡是问进程从系统角度看是什么答案都是PCB不是程序代码也不是数据集合。程序是静态的进程是动态的这个区别在简答题里也经常出现能用自己的话把进程是程序的一次执行过程是资源分配和调度的基本单位讲清楚这几分就到手了。2.2 处理机调度计算把公式和过程写规范调度算法的计算题是整套卷子里最机械也最容易拿满分的题。常见的考核方式是给出进程到达时间和服务时间分别用先来先服务FCFS、短作业优先SJF、时间片轮转RR计算周转时间和带权周转时间。我先说两个必须背下来的公式这两个公式基本每套卷子都用得上周转时间 完成时间 - 到达时间带权周转时间 周转时间 / 服务时间以一道典型还原题为例系统中有4个进程到达时间和服务时间如下表。进程到达时间服务时间P107P224P341P454先看FCFS调度顺序就是到达顺序P1、P2、P3、P4。P1在0时刻开始7时刻完成P2虽然2时刻就到了但要等P1做完所以7时刻开始11时刻完成P3在11开始12完成P4在12开始16完成。平均周转时间 (7 9 8 11) / 4 8.75。再看SJF这里有个小陷阱短作业优先调度的是就绪队列里服务时间最短的进程不是全局按服务时间排序。0时刻只有P1先做P1P1在7时刻做完时P2、P3、P4都已经到达此时服务时间最短的是P31所以先做P3P3在8时刻完成接着做P24P2在12时刻完成最后做P416时刻完成。平均周转时间 (7 10 4 11) / 4 8。比FCFS略好这个过程必须写清楚为什么先做P3再做P2否则阅卷老师不知道你是真懂还是蒙的。这里我要特别强调一个失分点很多同学算出来了FCFS和SJF的结果却不写调度时刻表只写最终答案。综合应用题是按步骤给分的把每个进程的开始时间和完成时间列出来就算后面算错了也能拿到大部分过程分。这个习惯一定要养成。2.3 PV操作大题橘子苹果问题的完整解法PV操作大题是进程管理里最让学生头疼的部分但2016年这套还原卷出得很规矩考的是经典的橘子苹果问题我用它来演示完整解题思路。题目描述大概是爸爸、妈妈、儿子、女儿四个人共享一个盘子盘子一次只能放一个水果。爸爸只放苹果妈妈只放橘子儿子只吃苹果女儿只吃橘子。用P、V操作实现这个同步互斥关系。这类题的解题套路就三步。第一步找资源盘子的空位是资源苹果是资源橘子也是资源。第二步给每个资源配一个信号量empty初值为容量这里设为1表示盘子里最多放一个水果apple初值为0orange初值为0因为盘子本身是临界资源还要一个mutex初值为1保护它。第三步把每个角色的动作翻译成PV操作。爸爸放入苹果的代码是这样的爸爸 repeat 准备苹果; P(empty); // 占一个盘子空位 P(mutex); // 互斥访问盘子 放入苹果; V(mutex); // 释放盘子 V(apple); // 苹果数量加1通知儿子 until false妈妈逻辑完全类似只是最后V(orange)。儿子进程取苹果儿子 repeat P(apple); // 等待苹果 P(mutex); // 互斥访问盘子 取走苹果; V(mutex); V(empty); // 释放一个盘子空位 吃苹果; until false女儿进程同理只是把apple换成orange。这里有一个特别容易踩的坑儿子在等苹果时到底先P(apple)还是先P(mutex)正确顺序一定是先P(apple)再P(mutex)。如果反过来儿子先拿到了盘子的互斥锁然后发现没有苹果就会一直阻塞在P(apple)上盘子被锁死了爸爸和妈妈也放不进水果系统直接死锁。这类同步信号量在前、互斥信号量在后的规则我建议大家在做题时先写同步再写互斥可以避开绝大多数死锁。3. 内存管理最值得死磕的得分板块3.1 分页地址变换先算页号再查页表内存管理这块2016年还原卷重点考了分页存储管理的地址变换。这类题给分非常慷慨因为步骤固定逻辑地址拆成页号和页内偏移查页表得到页框号再把页框号拼上页内偏移得到物理地址。拆分的规则要记牢系统按字节寻址页大小为2的k次方字节那么逻辑地址的低k位就是页内偏移高位就是页号。我用一道还原题变形来演示。假设页面大小为4KB逻辑地址为0x2A5C。4KB是2的12次方所以低12位0xA5C是页内偏移高位的0x2是页号。如果页表第2项对应页框号为8那么物理地址就是页框号8拼接偏移0xA5C得到0x8A5C。我见过太多人在这里犯一个低级错误直接拿0x2A5C和0x8A5C去比对发现页框号变了就怀疑自己算错了。其实地址变换的本质是换页号不换偏移偏移始终是低12位只是高位从逻辑页号替换成物理页框号。把这个本质想明白十进制题和十六进制题就都不怕了。如果题目给的是十进制数操作完全一样。比如逻辑地址10572页面大小1KB2的10次方那么页内偏移就是10572除以1024的余数页号就是商。手动算除法容易出错我建议先心算1024的倍数再取余速度会快很多。3.2 页面置换算法手算要讲究方法页面置换算法计算是内存管理里必考的计算题常见的有OPT最佳置换、FIFO先进先出、LRU最近最久未使用、Clock时钟置换。2016年这套卷子用的是经典引用串我拿一个典型例子演示怎么手算最不容易出错。假设页框数为3访问串为7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1。先看FIFO把三个页框想象成一个队列新页面进来时淘汰最早进入的页面。从头模拟缺页情况会交替出现我一步步过关键节点。初始7、0、1都缺页三个页框变成[7,0,1]访问2时7最老被淘汰页框变成[2,0,1]访问0命中访问3时0最老被淘汰页框变成[2,3,1]访问0时1最老被淘汰变成[2,3,0]访问4时2被淘汰变成[4,3,0]……整个序列模拟下来FIFO的缺页次数是15次。再看LRU淘汰的是最久没有访问的页面。同样从7、0、1开始访问2时7最久未用被淘汰访问0命中并刷新0的访问时间访问3时1最久未用被淘汰访问0命中刷新访问4时3最久未用被淘汰……完整模拟下来LRU的缺页次数是12次。手算LRU时我推荐一个自己的笨办法在草稿纸上画三行格子每访问一个页面就把被访问的页号划掉并写在最右端淘汰时永远看最左端那一个。这样不用靠脑子记访问时间只要眼睛盯着行首就行准确率高很多。很多人算LRU出错不是概念不懂是过程太乱这个画格子的小技巧能直接解决问题。这里还要留意一个知识点OPT是理论上最优的算法因为要预知未来访问序列现实无法实现它的作用只是作为衡量其他算法优劣的上限。而FIFO有个著名的Belady异常——增加页框数反而缺页次数增多如果考到简答题能举出一个实例说明分数会非常好看。3.3 虚拟内存背后的局部性原理除了计算题内存管理还会出简答题其中最经典的就是为什么虚拟内存能跑得起来。答案核心是局部性原理程序在一段时间内的访问往往集中在某个区域。时间局部性说的是刚刚访问过的数据很快会被再次访问比如循环体空间局部性说的是访问了一个地址后附近的地址很快也会被访问比如数组的连续遍历。理解了局部性原理就能解释很多操作系统的设计为什么页面置换要用LRU而不是随机淘汰因为LRU正好利用了时间局部性。为什么预取页prefetching能提速因为用了空间局部性。一旦简答题出到页面置换算法为什么有效或者虚拟内存为什么可行围绕局部性原理展开作答基本不会跑偏。4. 文件系统与I/O容易被忽视的大题来源4.1 混合索引算文件最大长度文件管理部分2016年还原卷考了一道非常典型的混合索引大题。混合索引就是把直接索引、一级间接索引、二级间接索引组合在一起既照顾小文件访问速度又让大文件能撑到足够大。计算的关键是一个盘块能放多少个地址项。假设盘块大小4KB一个地址项4字节那么一个盘块能放4KB/4B 1024个地址项即1024个盘块号。再来算文件最大长度直接索引块假设有10个每个能直接指向一个4KB的数据盘块合计40KB一级间接索引1个指向一个索引盘块这个索引盘块里能存1024个地址每个地址指向4KB数据块合计4MB二级间接索引1个指向一个二级索引盘块其中1024个地址各指向一个一级索引盘块每个一级索引盘块又管1024个数据块合计1024 × 1024 × 4KB 4GB所以文件最大长度 40KB 4MB 4GB。这道题几乎每年都会以不同数字出现数字会变但先算每个盘块存多少地址项再分直接、一级、二级逐层相乘的思路完全不变。4.2 磁盘调度四种算法一次算明白磁盘调度计算题是文件系统里的硬菜因为数据一多就很容易算乱。2016年这套卷子用的请求队列也很经典98, 183, 37, 122, 14, 124, 65, 67磁头初始位置在53。磁盘有200个柱面0到199。先看FCFS完全按请求到达顺序服务53到98走4598到183走85183到37走14637到122走85122到14走10814到124走110124到65走5965到67走2总寻道长度 640。再看SSTF最短寻道时间优先每次找离当前磁头最近的请求。53最近的请求是65距离1265后面最近的是67距离2然后是37距离30、14距离23、98距离84、122距离24、124距离2、183距离59总寻道 236。SSTF效果好但缺点是可能让远处的请求饿死这个缺点常考简答。SCAN电梯算法要复杂一些。磁头先朝一个方向移动比如从53向柱面号增大的方向走依次服务65、67、98、122、124、183。至于到183之后是继续走到199再回头还是在183直接回头不同教材约定不同。按走到最远柱面199再回头的约定总寻道 (199 - 53) (199 - 14) 146 185 331如果按到最大请求183就回头的简化约定结果就是299。考试时一定要看清题目有没有说明扫描到端部才回头没说明的话两种做法都可能被接受但你必须在答题区写清楚自己的约定。C-SCAN是单向服务磁头从53往大柱面方向走到199然后直接回到0再往大方向服务14、37。总寻道 (199 - 53) 199 14 23 382。C-SCAN比SCAN均匀等待时间更稳定。4.3 I/O控制方式对比设备管理简答题里I/O控制方式的对比是高频考点。四种方式级别从低到高程序查询方式、中断驱动方式、DMA方式、通道方式。程序查询方式最大的问题是CPU忙等一个字节一个字节地轮询设备状态CPU利用率被拖到很低中断驱动方式解决了忙等但每次传输一个字节都要中断一次CPU中断开销太大DMA方式让外设和内存之间直接传输数据只在传输开始和结束时打断CPU适合块设备通道方式更进一步通道是专门处理I/O的处理器能执行通道程序CPU只需要发一条I/O指令通道自己管理一批数据传输。用排队打比方程序查询像你站在取餐口一直盯着后厨问好了没中断驱动像后厨做好一份就喊你一次但一份一份喊还是累DMA像后厨一次性把十份做好再喊你一次通道方式则是你把整张菜单交给一个专门的助手让他盯着后厨你自己去干别的。这个类比我在复习时经常给学生讲理解以后再做题选项里的关键词一抓一个准。5. 死锁与银行家算法考频最高的一道老题5.1 死锁四必要条件和处理策略死锁这块的选择题喜欢考四个必要条件互斥、占有且等待、不可剥夺、循环等待。死锁发生时四个条件必须同时成立所以破坏任何一个条件都能预防死锁。比如通过一次性申请所有资源来破坏占有且等待通过允许抢占来破坏不可剥夺通过资源有序分配来破坏循环等待。这里要区分三个容易混的概念预防是破坏四个必要条件之一是静态的、限制严格的避免是在资源分配过程中用算法判断是否安全典型代表就是银行家算法检测和解除是允许死锁发生然后通过资源剥夺或撤销进程来恢复。2016年这套题在简答题里考了这个区别只要把这个层次理清楚拿分很稳。5.2 银行家算法安全序列演算银行家算法是死锁里的大题担当。我用一个典型数据完整演算一遍这个过程建议你们在草稿纸上自己写一次。假设系统有3类资源A、B、C总数为(10, 5, 7)5个进程P0到P4。已知某一时刻的分配情况如下进程已分配(A,B,C)最大需求(A,B,C)还需(A,B,C)P0(0,1,0)(7,5,3)(7,4,3)P1(2,0,0)(3,2,2)(1,2,2)P2(3,0,2)(9,0,2)(6,0,0)P3(2,1,1)(2,2,2)(0,1,1)P4(0,0,2)(4,3,3)(4,3,1)先算剩余资源Available 总数 - 各进程已分配之和 (10,5,7) - (7,2,5) (3,3,2)。安全检测从P0开始P0还需(7,4,3)Available(3,3,2)不够跳过P1还需(1,2,2)(3,3,2)满足分配后P1运行并释放资源Available变为(3,3,2)(2,0,0)(5,3,2)。接着P3还需(0,1,1)(5,3,2)满足运行后Available变为(5,3,2)(2,1,1)(7,4,3)。此时P4还需(4,3,1)满足运行后Available变为(7,4,3)(0,0,2)(7,4,5)。然后P2还需(6,0,0)满足运行后Available变为(10,5,7)最后P0也能满足。安全序列{P1, P3, P4, P2, P0}存在所以系统处于安全状态。考场上的高效写法是画一张进程、还需、Available、可否满足的推进表每分配一个进程就更新一次Available这样既清晰又不容易漏算。银行家算法主要考是否安全、找安全序列如果题目再让你判断某个新请求能否分配核心思路就是试探分配再做一次安全性检查。5.3 一道新请求也能算把方法变成套路常见变形是P1请求资源(1,0,2)问系统能否分配。这时候先把Available从(3,3,2)减到(2,3,0)把P1的已分配改为(3,0,2)还需改为(0,2,0)然后重新做安全性检查。如果能找到安全序列就分配找不到就拒绝。这个过程在卷面上要写清楚试探性分配四个字让阅卷老师知道你不是随便改的数据。这里有个很容易犯的错题目问的是能否分配很多同学直接回答能或不能就结束了。至少要写一行判断依据分配后系统仍然处于安全状态所以可以分配或者分配后找不到安全序列所以拒绝。这样才叫完整作答。6. 复盘总结这份真题的复习打开方式6.1 常见失分点清单这几年带学生刷题我把他们在类似真题上的失分点总结成了一张表对照自查比盲目刷题有用得多失分点原因解决办法PV操作顺序写反导致死锁先P互斥后P同步统一先同步信号量后互斥信号量调度题不写完成时间只写答案跳步严重每题列出进程开始、完成时间表地址变换混淆页号和偏移进制位权不清楚先确定页大小是2的几次方再拆地址LRU手算算错靠脑子记访问顺序画格子最左端就是淘汰对象磁盘调度约定不清忽略是否到端部回头答题区写明采用的约定银行家算法算完Available不更新流程不熟练每分配一个进程立即更新Available这些坑几乎每个都是历年考生反复踩的。你不用一次全记住但每次做完题对一下这张表就知道自己该补哪块。6.2 三轮复习建议和资料搭配操作系统的复习我建议至少过三轮。第一轮以教材和课堂笔记为主把概念和原理弄懂配套做一遍教材课后题这一轮的目的是建立知识框架。第二轮以真题为主先做这份2016年还原卷的每一个计算题做完之后把同类题集中在一起横向比较比如把所有调度算法题放一起做、所有页面置换题放一起做你会很快发现套路高度相似。第三轮就是查漏补缺重点看简答题的表述规范和上次做错的题。资料方面如果你用的是计算机操作系统教材课后题一定不要跳过很多真题就是课后题换个数字如果准备考研408王道系列的章节题目可以作为第二轮补充。但我不建议贪多一份高质量的真题卷反复做三遍胜过十份卷子各做一遍尤其是计算题第二遍做的时候你会有完全不一样的理解。我个人在复习后期还有一个习惯每做完一套卷子把错题涉及的公式和算法步骤单独抄在一张A4纸上考前只看这张纸。像带权周转时间的公式、页内偏移位数、SCAN算法两种约定、银行家算法安全序列的推进表格式全部浓缩成半页纸考试进考场前扫一眼基本就能避免低级失误。这个方法我推荐给每一届学生反馈都很好。这份2016年还原版真题的价值不在于题目有多难而在于它把操作系统最核心的算法和计算全部串了一遍你认真做完、认真复盘一遍收获会比盲目刷十套模拟题大得多。