带操作系统这门课我前前后后带了快十年。办公室桌上常年放着一本翻得脱胶的《计算机操作系统》第四版主编汤小丹。这本书在很多高校是本科核心教材也是不少计算机考研专业课的指定参考书地位基本属于“操作系统方向人手一本”。它的课后习题覆盖很广概念题、计算题、设计题都有很多学生问我的第一个问题都是“老师课后习题答案去哪找”我一般会回一句“答案能找但思路得自己搭。”这篇博文就把我这些年带学生刷这本书前七章习题的经验整理一遍。内容覆盖操作系统引论、进程描述与控制、处理机调度与死锁、存储器管理、虚拟存储器、输入输出系统、文件管理适合正在期末复习、考研备考或者单纯想把这门课学扎实的同学参考。我不会把答案原封不动搬出来而是把每个章节“到底在考什么”“解题的切入点是什么”“哪些地方最容易翻车”讲透。你能把这篇看完再回去翻课后题会发现大部分题目其实不用背答案也能推出来。1. 先看清教材整体脉络再动笔做题1.1 七章内容是一条完整的逻辑链很多人学操作系统觉得散今天讲进程明天讲内存后天讲文件知识点相互之间好像没什么联系。其实这本书前七章的设计逻辑非常清晰它先把操作系统当成一个“管理者”来介绍接着按它管理的核心资源展开每种资源的管理方式单独成章最后再用接口和用户态收口。第一章操作系统引论是总纲回答的是“操作系统是什么、有什么特征、能干什么”。第二章到第七章本质上是“操作系统如何管理CPU、内存、外设、文件”这几类核心资源。第二章和第三章管CPU进程是CPU调度的基本单位信号量机制解决并发中的同步与互斥处理机调度算法决定哪个进程先上CPU死锁则是资源分配不当造成的极端情况。第四章和第五章管内存先看在物理内存里怎么放程序再看内存不够时怎么用虚拟存储技术给程序“画饼”。第六章管设备解决CPU和外设速度不匹配的问题。第七章管文件解决数据怎么组织、怎么存、怎么共享保护的问题。这个脉络理清之后你再去看每一章的课后题就会发现题目都围绕“某类资源用什么数据结构描述、用什么算法分配、遇到冲突怎么解决”这三件事展开答题的时候思路会清晰很多。为什么一定要先讲脉络因为操作系统这门课的课后习题有一个特点很多题目表面上在考某一章实际上在考你能否跨章节调用知识。比如第五章虚拟存储器里的“抖动”概念如果不回看第一章的“虚拟”特征就很难理解为什么抖动是虚拟存储技术的副作用再比如第七章文件的共享与保护如果不理解进程间的互斥与同步就很难明白文件锁为什么要分成共享锁和排他锁。先建立整体框架再逐章填细节是少走弯路的前提。1.2 每章的核心考点和题型分布课后习题大致分三类。第一类是概念简答题比如“操作系统有哪些基本特征”“死锁的必要条件是什么”这类题考记忆但记忆要建立在理解上不然换个问法就懵。第二类是计算题比如调度算法求平均周转时间、页面置换算法求缺页次数、磁盘调度求总寻道时间这类题考公式和流程步骤写清楚就能拿分。第三类是综合设计题比如用信号量描述一个生产者消费者问题、设计一个管理空闲空间的数据结构这类题考建模能力也是很多学生觉得最难的部分。我统计了一下前七章习题里第二、三、五章计算题和设计题占比最高第一、七章偏概念和综合第四、六章计算量也不小。你复习的时候如果时间紧优先把第二章的信号量题、第三章的调度算法与银行家算法、第四章的地址转换与页面置换算法、第六章的磁盘调度、第七章的位示图全套算熟基本就能覆盖大部分分值。还有一点要提醒第四版教材的课后题数量不算少但千万不要“平均用力”。同一道题如果已经练过三遍再刷也只是熟练度提升反而是那种第一遍完全没思路的题才是真正的提分点。我建议每章做完后给题目标个难度等级第一遍不会做的题做上记号第二遍复习时优先看记号题否则很容易陷入“会做的反复做、不会做的永远跳过”的陷阱。2. 基础篇第一到第三章习题怎么破2.1 第一章引论概念题要“会串”第一章的题大多不难但很多同学栽在“答不全”上。比如“操作系统有哪些基本特征”这道题标准答法是并发、共享、虚拟、异步四个特征并且每个特征都要展开一句并发是指多个程序在同一时间间隔内交替运行共享是指系统中的资源可供多个进程共同使用虚拟是指将一个物理实体映射为多个逻辑对应物异步是指进程以不可预知的速度向前推进。有的同学只写四个词不看题目里“解释”二字阅卷时很难给分。这里有个技巧凡是遇到“特征”“功能”“作用”这类题把概念还原到“它解决了什么问题”去答。并发对应单CPU上多道程序的推进问题共享对应资源有限而进程众多的问题虚拟对应物理资源不足的问题异步对应系统内事件发生的不确定性。这样答既不会漏点又能显示出你是真懂而不是在背词条。第一章里还有个高频题是“操作系统的主要功能”教材从处理机管理、存储器管理、设备管理、文件管理、用户接口五个角度展开。我建议你把这五个功能与后面章节做对应处理机管理就是第二、三章的内容存储器管理就是第四、五章的内容设备管理就是第六章文件管理就是第七章。到期末复习时你只需要记住“五件事”后面每一章都是这五件事的细化。要特别提醒的是第一章有些简答题喜欢“反着问”。比如题目问“操作系统为什么需要中断机制”有些同学只回答“中断是CPU与外设通信的方式”这就漏掉了一半。操作系统引入中断首先是为了让CPU从低速的I/O等待中解放出来提高系统效率其次是为了应对程序运行中的异常情况比如除零、越界、缺页等。回答这类题时最好从“提高效率”和“处理异常”两个维度各写两三句覆盖面就完整了。2.2 第二章进程信号量题的关键套路第二章是整本书的分水岭。进程概念、状态转换、PCB进程控制块这些内容靠理解加记忆就能搞定真正难的是信号量机制的PV操作题。这类题的通用做法可以归纳成四步一是找同步关系也就是哪些进程之间有先后顺序二是找互斥关系也就是哪些资源同一时刻只能被一个进程使用三是为每一类关系定义一个信号量并确定初始值四是在代码适当位置加上wait和signal操作。以经典的“生产者消费者问题”为例生产者和消费者共享一个有界缓冲区。缓冲区是临界资源需要一把互斥锁另外“缓冲区有空位”和“缓冲区有产品”这两个条件是同步关系分别用两个信号量表示。于是至少需要三个信号量mutex初始值1负责互斥empty初始值为缓冲区大小表示空位数量full初始值为0表示产品数量。很多同学会漏掉mutex或者把empty和full的初始值搞反结果程序跑起来就死锁。我给一个检查办法代码写完后把所有wait操作都读一遍凡是wait后紧接着wait另一个信号量就要警惕这两个信号量之间的耦合会不会造成互相等待再验证信号量的初始值是否等于资源的初始数量。能过这两步大部分同步题都能避免低级错误。第二章课后习题里还有一类“为什么引入进程”“PCB的作用是什么”的简答题看起来简单但阅卷时很看重关键词。答“进程引入是为了描述程序并发执行时的动态特征”要能点出“程序本身是静态的只有进程才能反映动态执行过程”答“PCB是进程存在的唯一标志”一定要提到“系统通过PCB感知进程的存在进程被创建时建立PCB进程消亡时回收PCB”。这些关键词就是得分点丢了就扣分。如果你做PV操作题总出错我建议先用“前驱图”练手。教材在绪论部分引入了前驱图很多同学觉得它只是画图游戏其实它是信号量题的图形化解法。把每个任务画成一个节点任务间的先后依赖画成有向边那么每条边就是一个信号量边的起点执行完后signal边的终点执行前wait。把前驱图吃透生产者消费者、读者写者、哲学家进餐这些经典问题都会变得直观很多。2.3 第三章调度与死锁计算题要规范写步骤第三章的调度算法题属于“方法知道就会做方法不知道就全错”的类型。FCFS先来先服务、SJF短作业优先、RR时间片轮转、优先级调度这四种算法要求能从给定的一组进程到达时间和服务时间计算出完成时间、周转时间、带权周转时间和平均周转时间。我批改作业时看到最多的问题是时间轴画错。SJF在做非抢占式调度时要特别注意“当前进程执行完后从已到达的进程里选出服务时间最短的那个”而不是单纯按顺序排。很多同学上来就把所有进程按服务时间排序完全忽略到达时间。进程2可能在第4分钟到达你还在等进程3完成结果整个调度序列从头错到尾。正确做法是像排班一样只在“当前可以选的候选池”里选最短的。RR调度则要画好时间片轮转表每个时间片结束时检查是否有新进程到达未完成的进程排到队尾。写答案时建议把每一步的时间点都列出来这样即使最后平均周转时间算错过程分也能保住。死锁部分的重点有两个。一个是死锁的四个必要条件分别是互斥、请求并保持、不可剥夺和循环等待考试常考“破坏哪个条件对应哪种方法”要能和死锁预防、避免、检测与解除对应起来。另一个是银行家算法这种题分值高、套路固定。做题时依次判断每个进程的需求量是否小于当前可用资源能分配就分配并假设进程执行完释放资源把这种“试探性分配”迭代下去。如果能找到一个让所有进程都完成的序列即安全序列系统就处于安全状态否则就存在死锁风险。千万别在中间步骤省略银行家算法最值钱的就是那张安全序列推导表。还要提醒一个细节计算平均周转时间时如果题目要求的是“带权周转时间”公式是周转时间除以服务时间。很多同学套公式时忘记除以服务时间直接把周转时间当带权周转时间用结果数值全对但概念全错。做题时把每个公式先写在草稿纸最上方再开始代数据能有效避免这类问题。3. 内存篇第四、五章习题怎么算才稳3.1 第四章存储器管理地址转换是核心第四章的课后计算题主要围绕连续分配、分页存储、分段存储和段页式存储展开。最基础也最常考的是“将逻辑地址转换为物理地址”的计算。以分页系统为例逻辑地址分为页号和页内偏移两部分。做题第一步是拿逻辑地址除以页大小商是页号余数是页内偏移第二步查页表得到该页对应的物理块号第三步用“物理块号乘页大小加页内偏移”算出物理地址。很多同学在这类题上丢分不是因为不会除而是没注意单位换算。题干给的程序长度可能是KB逻辑地址却以十进制或十六进制给出页大小是4KB有的同学直接拿十进制地址去除忘了先统一单位。我建议你拿到题先圈出所有数字的单位全部换算成字节尤其涉及十六进制地址时先把每个地址转换为二进制按页大小拆分成高位的页号和低位的页内偏移再查页表基本不会错。这里有个非常容易忽略的步骤越界检查。分页系统里逻辑地址的页号如果大于页表长度就会产生越界中断。很多同学在地址转换题里从不写这一步直接查表算物理地址结果题目特意给了一个超大页号目的就是考察你有没有“越界”意识。规范答题顺序应该是先求页号判断页号是否越界再查页表判断物理块号是否为空最后才能计算物理地址。分段系统的换算逻辑类似区别是段号对应的段长和段基址都在段表里偏移量不能大于段长否则触发越界中断这也是常考点。第四章还会考外部碎片和内部碎片的概念。连续分配方式会产生外部碎片分页方式会产生内部碎片也叫页内碎片分段方式又会产生外部碎片。判断题里经常挖坑“分页管理完全没有碎片”这显然是错的分页只是消除了外部碎片但最后一页不可能总是恰好装满内部碎片依然存在。这类概念题靠语句的严谨性给分你在复习时多留意教材里“完全”“一定”“所有”这些绝对化表述。3.2 第五章虚拟存储器页面置换算法要手推第五章是虚拟存储最重要的计算题是页面置换算法下的缺页次数统计。考试常用的算法有最佳置换算法OPT、先进先出FIFO、最近最久未使用LRU以及Clock置换算法。OPT是理想算法选择将来最长时间不被访问的页面换出它无法在实际系统中实现但常拿来做理论下限对比。FIFO实现最简单但可能出现Belady异常也就是分配物理块数增多缺页次数反而增加。LRU利用“最近的过去”近似“最近的将来”性能接近OPT但需要硬件支持计时或栈。做这类题时我强烈建议画一个“内存页面状态表”一行是一个物理块一列是一次页面访问。每访问一个页面把内存中当前的页面集合标出来如果发生缺页就单独打标记。表格画完后缺页次数一目了然也不容易漏算。FIFO很简单换出最早进入的页即可LRU要盯住“最近最久未被使用”比如访问序列是1、2、3、4、1、2、5当访问5时发生缺页哪个页面被换出要倒着往前看最近访问过1和2再往前是4、3所以3比4更久没被访问换出3。不少同学在这里习惯性按顺序换结果LRU算成了FIFO整道题崩盘。Clock算法则是给每个页面一个访问位发生缺页时沿着环形链表找访问位为0的页遇到访问位为1就置0并继续向下找。这类题画好几个环的滚动状态比背公式有效。记住Clock算法只是LRU的一种近似实现它不保证换出的一定是“最久未使用”的页只是找到一个“最近未被访问过的页”这两个概念在简答题里经常被对比着考。第五章还有一个高频简答题是“什么是抖动thrashing”怎么解决。答案核心是进程频繁缺页系统大部分时间都花在换页上CPU利用率反而下降这种现象叫抖动。解决思路包括采用局部置换策略、引入工作集模型、把物理块分配控制在合理范围内。答题时如果能顺手写出“工作集是进程在一段时间内实际访问页面的集合”得分会更高。另外磁盘交换区的大小、程序局部性的好坏、页面置换算法的优劣都会影响抖动的严重程度这类题容易出成“多选式”的简答复习时要把相关因素一并记住。4. 设备与文件第六、七章习题怎么答4.1 第六章输入输出系统磁盘调度计算题第六章的内容多而杂但习题计算题主要集中在磁盘调度上包括FCFS、SSTF最短寻道时间优先、SCAN电梯算法和C-SCAN循环扫描几种算法的寻道长度计算。这类题给定当前磁头位置和请求序列要求依次列出磁头移动顺序再计算总寻道长度或平均寻道长度。做磁盘调度题我只有一个建议先把数轴画出来把所有请求位置按从小到大标好再把磁头当前位置标出来最后按算法规则一步步移动。SSTF是每次都找离当前磁头最近的请求SCAN是让磁头先按某个方向一直走走到最边端或直到没有更远的请求再反向。很多同学会把SCAN和SSTF混淆在SCAN过程中看到旁边有个更近的请求就想拐弯这是错的电梯算法在换向之前必须沿原方向走到底。如果题目限定“移臂方向由外向内”或“由内向外”务必按限定方向走不要自己随意改方向。计算总寻道长度时只累计磁头移动的距离不统计请求之间的绝对距离这个细节也容易让结果差出一个数量级。举个例子磁头在100道请求序列是23、68、189SSTF第一步移动32道来到68第二步再移动45道到23第三步移动166道到189总寻道243道。这三个数字每一步都要在草稿上写出来别心算心算最容易错。第六章还常考SPOOLing技术问“SPOOLing系统由哪些部分组成”“它如何实现虚拟设备”。答法要抓住关键SPOOLing由输入井、输出井、输入进程、输出进程组成利用磁盘上的缓冲区模拟独占设备把一个独占设备改造成可共享的设备。考试时还要说明它提高了I/O速度把独占设备变成了共享设备实现了虚拟设备功能。这里的“虚拟”要和第一章讲的虚拟特征呼应起来答题时能点出“多个进程通过SPOOLing共享一台打印机从用户角度看就像每人都有一台打印机”这就是虚拟设备最通俗的注脚。4.2 第七章文件管理位示图和目录结构是重头第七章文件管理课后习题题型比较固定高频考点有三个文件逻辑结构与物理结构的对应、目录结构的组织方式、存储空间管理算法。存储空间管理里最常考的是位示图法。一个磁盘被划分为若干物理块位示图中每一位对应一个物理块1表示已分配0表示空闲。做题时给定位示图的行列数要求计算某个盘块号对应的字号、位号或者反过来由字号位号求盘块号。这类题纯粹是换算但特别容易在公式上翻车。我总结了一个通用办法先搞清楚位示图是按行还是按列编号。如果题目说“位示图有m行n列行列号从1开始盘块号从1开始按行排列”那么盘块号b对应的行号i (b-1) / n 1列号j (b-1) % n 1这里的整除和取余都要基于b-1而不是b因为盘块号从1开始。反过来由行号i、列号j求盘块号b (i-1) * n j。不少同学问“为什么是b-1不是b”你拿b1代入试试第1块应该对应第1行第1列用b-1才成立。理解了这一点位示图题就能举一反三。如果题目把行列号或盘块号从0开始编号公式又不一样这时不论序号从几开始都有一个通用的笨办法先明确“第几行第几列”对应的是物理块的计数顺序再去套公式比死记一个版本更可靠。文件目录习题里最常问的是“引入索引节点inode有什么好处”。标准答法是将文件名和文件属性分开目录项里只保留文件名和指向索引节点的指针这样在查找文件时只需要把文件名部分读入内存减少磁盘I/O加快检索速度。另一个高频题是“多级目录结构有什么优点”要提到它解决了文件重名问题提高了目录检索速度也便于实现文件的共享和保护。答题时如果能用具体例子说明比如两个用户都可以在自己的子目录里建立名为test的文件互不干扰就能让答案更有说服力。第七章还有一个容易出计算题的位置文件物理结构的盘块计算。比如一个文件系统盘块大小为4KB每个盘块号占4字节索引节点中共有多少直接块、一级间接块、二级间接块求一个文件最大能有多大。这类题本质是乘法估算关键是把“一个盘块能装多少个盘块号”算对盘块大小除以盘块号占用字节数得到每个间接块能容纳的指针数量再逐级相乘并乘以盘块大小。很多同学会把多级间接块的最大文件容量算成一个单级结果题目里“一级”“二级”这些字眼一定要先圈出来。5. 刷题避坑与备考节奏心得5.1 我批改作业时最常看到的几个错误刷完上面这些题我再把学生作业和考试里反复出现的问题集中列出来你可以当个自查清单。第一信号量初始值乱设。mutex类信号量初始值一定是1资源计数类信号量初始值是资源数量同步类信号量的初始值要能体现“当前有多少个可用条件”。第二银行家算法只判断不推导。题目问“系统是否安全”很多同学直接写安全或不安全不给安全序列这种答案在考试里通常只能拿一半分。第三分页地址转换忽略越界检查。分页系统里逻辑地址的页号如果大于页表长度就会产生越界中断这一步一定要写在答题过程中。第四LRU和FIFO混淆。FIFO看进入内存的时间LRU看被访问的时间这两个“时间”不是一回事。第五磁盘调度SCAN和SSTF混淆。SCAN按固定方向移动SSTF按最近距离移动判断依据是“算法规则”而不是“看起来更优”。还有一个很隐晦的坑很多题目里“平均周转时间”和“带权周转时间”会混着问。平均周转时间是所有进程周转时间的算术平均带权周转时间是周转时间除以服务时间再取平均两者的分母完全不同。做题时先看清题目要哪个量再决定用哪套公式。另外概念题里“动态重定位”“静态重定位”也是一对易混点。静态重定位是在程序装入内存时一次性完成地址变换程序运行过程中不能再移动动态重定位是在程序执行过程中每次访问内存前通过重定位寄存器计算物理地址。很多同学把两者记反这里可以简单记成静态是“装完就定死”动态是“边跑边算”。5.2 我的刷题节奏建议两遍法最后说说我给学生推荐的刷题节奏。我个人比较推荐“两遍法”。第一遍在学完每一章后立刻做不查书硬做做不完也要把卡住的地方标记出来这一遍的目标是暴露问题。第二遍在全部七章学完后做题型汇总把所有计算题按类归拢在一起比如调度算法放一起、页面置换放一起、位示图放一起集中刷。你会发现很多题虽然题目变了但计算套路完全一样第二遍刷起来速度会快很多。遇到实在不会的题我建议先看答案的结论再看思路然后把答案合上自己重推一遍。只看答案不动手等于没做能独立推出正确答案这道题才算真正拿下。很多同学问我为什么看懂了答案还是不会做题原因就在这里看懂是别人替你走了一遍逻辑独立推出来逻辑链才是你自己的。网上流传的答案版本很多偶尔会有印刷错误或表述不一致。做完题后如果要核对尽量结合教材正文和课件去验证关键步骤尤其是计算题自己推导的结果如果和答案不一致不要急着怀疑自己先检查单位、初始值、边界条件这几个最容易出错的点。毕竟做课后题的核心目标不是把答案背下来而是通过一次次推导把操作系统的机制内化成自己的知识结构。教材例题和习题里反复出现的PV操作、地址转换、页面置换、银行家算法都是后面复试、面试里高概率被追问的内容现在花时间把每一步想清楚后面会省很多事。
