操作系统期末复习攻略：进程、死锁与内存管理考点全解析

操作系统原理这门课相信不少同学和当年的我一样上课听得云里雾里进程、线程、信号量、PV操作、页面置换、银行家算法……这些术语一个接一个砸过来书翻了几页就头大。但等我真正把指定的《操作系统原理第二版》这本教材从头到尾捋过一遍再对照历届真题摸了一遍规律之后才发现期末卷面其实非常“诚实”考点高度集中题型套路固定计算大题掰着手指头数也就四五个方向。期末复习拼的从来不是谁熬夜熬得久而是谁先把“考点地图”画出来。这篇文章不打算把整本教材照本宣科抄一遍而是按照卷面上分值权重较高的模块把进程管理、死锁、内存管理、文件与设备管理这几大块的核心概念、计算模板、常见陷阱和复习顺序一次讲清楚。不管你是平时听课少、期末全靠突击的“冲刺型选手”还是想稳住成绩再冲高分的建议先花半小时顺着这篇文章把框架搭起来再回到教材对应章节做定点突破。下面直接上干货。1. 先把“考点地图”画出来再动手复习1.1 教材章节不等于考点分布《操作系统原理第二版》的内容编排走的是经典路线前面介绍操作系统的定义、功能和发展历史中间花大篇幅讲进程与线程、调度算法、同步互斥、死锁后半部分讲内存管理、文件系统、设备和I/O最后补一点安全和虚拟化相关的概论。如果逐章逐节背既没效率卷面也未必按这个比例出题。我看过几所学校的期末卷子也问过不同学校的同学大家出题尽管风格有差异但分值分布大致是这样一个规律模块常见题型大致占比进程管理进程、调度、同步选择、填空、PV大题30%40%死锁与银行家算法计算大题、简答10%20%存储管理分页、分段、虚拟内存计算大题、选择填空20%30%文件与设备管理含磁盘调度选择、填空、磁盘计算10%20%除了四大模块还会混入少量冷门概念题比如操作系统的发展阶段、实时系统的特点、微内核与宏内核的差异等。这类题分值不高但往往是选择题里拉开差距的地方。复习策略上我强烈建议按“分值权重”安排精力先啃进程管理再攻内存和死锁文件与设备管理可以放在后面别平均用力。1.2 期末卷面的常见题型拆解操作系统这门课的大题高度模板化我在复习时把它归成六个方向调度算法计算给出一组进程的到达时间和服务时间算平均周转时间、平均等待时间。PV操作设计给一个并发场景生产者消费者、读者写者、哲学家进餐用信号量写出同步互斥代码。银行家算法给资源总量和进程的最大需求、已分配资源找一个安全序列或判断是否会进入不安全状态。分页地址转换已知页表、页面大小、逻辑地址求物理地址。页面置换给一个页面引用串和物理块数用FIFO、LRU、OPT算缺页次数。磁盘调度给一组磁道访问序列和初始磁头位置算总寻道距离或平均寻道长度。把这六类题目练熟计算题基本不会失分。后面的章节我就按这个顺序逐个展开每个部分都会带上可直接照做的计算过程。2. 进程管理分值最重也最容易出大题的模块2.1 基础概念程序与进程的区别状态转换图进程管理在期末卷上的地位就像高数里的导数属于“承重墙”。选择题、填空题、简答题、大题都会从这里面出。第一个必背的知识点是“程序与进程的区别”这几乎是简答题的常客。程序是静态的指令集合保存在磁盘上自己不会动进程是程序的一次执行过程是动态的包含代码、数据和堆栈还挂着一个数据结构叫PCB进程控制块。程序可以长期存在进程则随着运行创建、随着结束消亡。另一个高频考点是进程的状态转换。三态模型必须能画出来就绪态、运行态、阻塞态。就绪到运行靠调度程序分配CPU运行到就绪通常是时间片用完或被更高优先级的进程抢占运行到阻塞是因为进程主动请求I/O或等待某事件阻塞到就绪是等待的事件完成。要注意阻塞态不能直接变成运行态必须先回到就绪态重新排队。有的教材讲五态模型多出来的两个是创建态和终止态原理是一样的考试不会太为难人。提示画状态转换图时最容易写错的是“阻塞→运行”这个箭头。一定记得这条边是不存在的阻塞进程被唤醒后只能进入就绪队列。2.2 PCB和线程为什么它们也是考点很多同学忽略PCB觉得它只是个概念。其实PCB是理解整个进程管理的一把钥匙。它记录进程标识符、进程状态、程序计数器、寄存器保存区、调度信息、内存管理信息等。一个进程被中断后现场恢复靠的就是PCB里保存的寄存器内容。考试如果出简答题问你“进程为什么要引入PCB”标准答法就是PCB是进程存在的唯一标志系统通过PCB感知和管理进程进程切换的本质就是切换PCB并保存恢复现场。线程是进程概念的自然延伸。线程是CPU调度的基本单位进程是资源分配的基本单位。同一进程内的多个线程共享进程的地址空间、打开的文件等资源但每个线程有自己的栈和寄存器上下文。考题经常问线程比进程开销小在哪答案就是线程切换不需要切换地址空间和资源不像进程切换那样要涉及大量页表和资源表的更新。2.3 调度算法横向对比加一套计算模板调度算法的选择填空并不难难的是计算题。常见算法有几个先来先服务FCFS、短作业优先SJF、高响应比优先HRRN、时间片轮转RR、优先级调度、多级反馈队列。考试最爱考的是FCFS、SJF和RR这三种。先说怎么算。题目会给你一张表列出若干个进程的到达时间和服务时间。计算平均周转时间周转时间完成时间-到达时间等待时间周转时间-服务时间从这里能看出等待时间本质上是除CPU执行之外的所有时间。FCFS最无脑按照到达顺序依次执行即可。SJF要分抢占和非抢占非抢占是先到先执行完一个再挑最短的抢占式SRTN则是在每个新进程到达时重新比较剩余服务时间谁短谁上。我拿一个典型例子说明。假设有A、B、C、D、E五个进程到达时间分别是0、1、2、3、4服务时间分别是4、3、5、2、4。FCFS的调度顺序是A→B→C→D→E完成时间依次是4、7、12、14、18周转时间分别为4、6、10、11、14平均周转时间(46101114)/59平均等待时间(035910)/55.4。非抢占SJF的调度顺序是A→D→B→E→C。原因是0时刻只有A所以A先执行到4时刻此时B、C、D、E全部到达服务时间最短的是D2所以D接着执行到6再看剩余进程B最短3B执行到9之后是E4到13最后C5到18。完成时间依次是4、9、18、6、13平均周转时间(481639)/58平均等待时间(051315)/54.8。你发现没有平均等待时间从5.4降到了4.8这就是短作业优先的优势。RR算法如果时间片取1调度顺序会变成A、B、C、D、E、A、B、C、D、E……轮着来它的平均周转时间通常比SJF高但优点是响应快适合分时系统。注意SJF在考试中有个潜规则除非题目明确说“可抢占”一般默认按非抢占处理。如果题目说“最短剩余时间优先”那才用抢占式思路。多级反馈队列也是选择填空常客。它把就绪队列分成多个优先级队列新进程先进最高优先级队列用尽时间片还没执行完就降到下一级。特点是能让短作业快速完成同时兼顾长作业。2.4 信号量与PV操作大题的“门面担当”信号量是好多人的噩梦但一旦掌握了模板反而是送分题。信号量本质是一个整数变量配合P操作和V操作使用。P操作相当于申请资源会让信号量减1如果减完小于0进程阻塞V操作相当于释放资源会让信号量加1如果加完仍然小于等于0说明有进程在等待就唤醒一个。考试里最常见的就是用两个信号量解决互斥和同步问题。标准套路是用一个互斥信号量保护临界区初始值为1用若干资源信号量控制资源数量或同步关系初始值根据资源数量或初始可用的条件来定。2.5 生产者-消费者问题一套代码通吃同类型题目生产者-消费者问题是PV操作的题眼。背熟下面这套代码思路自然就通了。设一个缓冲区能放n件产品定义三个信号量mutex1互斥访问缓冲区、emptyn缓冲区空位数量、full0缓冲区中产品数量。生产者进程while(1) { 生产一件产品; P(empty); // 申请一个空位 P(mutex); // 加锁进入临界区 把产品放入缓冲区; V(mutex); // 解锁 V(full); // 产品数量加1同时可能唤醒消费者 }消费者进程while(1) { P(full); // 申请一个产品 P(mutex); // 加锁 从缓冲区取出一件产品; V(mutex); // 解锁 V(empty); // 空位数量加1 消费产品; }我看到不少同学在写这道题时会犯一个顺序错误生产者先P(mutex)再P(empty)。如果缓冲区已经满了生产者拿着锁等空位而消费者又进不了临界区取产品就死锁了。所以务必记住一句话资源信号量在前互斥信号量在后释放顺序无所谓但申请顺序不能反。读者-写者问题也常考核心是允许多个读者同时读但写者必须独占。解法用读者计数加信号量控制代码比生产者消费者稍长但思路一样。哲学家进餐问题考得频率低一些主要考死锁防止思路比如要求哲学家必须同时拿到左右两支筷子才能开吃或者限制最多四只哲学家同时入座。3. 死锁与银行家算法把计算步骤练成肌肉记忆3.1 死锁的四个必要条件死锁这块知识框架很清晰背住四个必要条件就算拿下一半互斥条件、占有且等待条件、不可剥夺条件、循环等待条件。选择题常拿其中一个条件做干扰项比如“没有互斥就不会死锁”这类说法判断题。简答题如果问死锁的处理方式分四层预防、避免、检测、解除。预防是从四个必要条件下手破坏其中一个。比如要求进程运行前一次性申请所有资源就是破坏“占有且等待”允许系统强行剥夺资源就是破坏“不可剥夺”。避免策略靠算法在资源分配前判断安全性典型的代表就是银行家算法。检测与解除属于事后处理先让死锁发生再通过资源剥夺或进程撤销来恢复。3.2 银行家算法手算模板银行家算法必须要会手算因为它是计算大题中出现频率极高的题型。核心步骤分四步计算每个进程还缺多少资源需求最大需求-已分配。计算当前可用资源向量可用系统总量-所有进程已分配资源之和。找进程它的剩余需求必须小于等于当前可用资源优先满足它。假设把资源给它它执行完会归还全部已分配资源更新可用资源继续找下一个能完成的进程。我直接上一个例子。系统中有5个进程P0到P4资源A、B、C总量分别为10、5、7。已分配矩阵如下进程已分配(A B C)最大需求(A B C)还需求(A B C)P00 1 07 5 37 4 3P12 0 03 2 21 2 2P23 0 29 0 26 0 0P32 1 12 2 20 1 1P40 0 24 3 34 3 1所有进程已分配之和为(7, 2, 5)因此当前可用资源为(10-7, 5-2, 7-5)(3, 3, 2)。然后开始找安全序列。当前可用(3,3,2)检查谁能完成P1需要(1,2,2)小于等于(3,3,2)可行。让P1运行完归还它的已分配资源(2,0,0)可用变成(5,3,2)。再找下一个P3需要(0,1,1)小于(5,3,2)可行P3归还后可用变(7,4,3)。接着P4需要(4,3,1)可行归还后可用变(7,4,5)。然后是P0需要(7,4,3)可行归还后变(7,5,5)。最后P2需要(6,0,0)可行。所以安全序列可以是P1→P3→P4→P0→P2。注意写银行家算法时先把“还需求”这一列算对这步错了后面全错。另外安全序列可能不唯一只要你能按上述规则找出一条完整的就说明系统处于安全状态。考试还可能升级一下某个进程发出新的资源请求要判断能否立即分配。处理方法是先假装把资源分配给该进程更新它的已分配和还需求同时减少当前可用资源再重新执行安全性检查。如果检查通过才能真的分配。4. 内存管理与页面置换理解抽象概念掌握计算模板4.1 分页、分段与段页式三者对比不混淆内存管理这块概念多容易记混。核心是把三种管理方式的关系搞清楚。分页是把物理内存切成固定大小的页框把进程的逻辑地址空间也切成同样大小的页然后通过页表映射。特点是内存利用率高碎片小但一个进程的页面在物理内存中可以不连续。分段是按程序的逻辑结构代码段、数据段、栈段划分段的大小可以不同便于共享和保护但会产生外部碎片。段页式则结合两者先按逻辑分段再在每段内部分页地址转换要查两次表。选择题常见考法问“分页系统的逻辑地址由什么组成”答案就是页号和页内偏移问“分段系统的逻辑地址由什么组成”答案是段号和段内偏移。还有个易错点分页由系统自动完成对程序员透明分段对程序员可见因为它对应程序结构。4.2 逻辑地址到物理地址的换算流程分页地址转换是必考计算题套路特别固定。题目一般给你页面大小、逻辑地址、页表内容让你求物理地址。举个例子。页面大小为4KB4KB2的12次方所以页内偏移占12位。有一个逻辑地址十六进制为0x1A2B。先把逻辑地址拆开0x1A2B的偏移部分取低12位即0xA2B剩余高位是页号这里是1。查页表假设页号1对应的页框号是5。物理地址页框号×页面大小页内偏移5×4KB0xA2B0x5A2B。考试时如果用十进制给地址优先转成二进制或十六进制再拆分不容易错。页内偏移就是逻辑地址对页面大小取余数页号就是整除的结果。例如页面大小1024逻辑地址4500页号4偏移404查页表找页号4对应的页框号再算物理地址就好。易错点如果题目给的是页表项从0号页开始查表时别把页号当索引从1开始一定要从0开始数。4.3 页面置换算法FIFO、LRU、OPT缺页次数怎么算页面置换大题通常给一个页面引用串和物理块数让你分别用FIFO、LRU、OPT算出缺页次数。FIFO先进先出淘汰最早进入内存的页面。LRU最近最久未使用淘汰最长时间没有被访问的页面。OPT最佳置换淘汰未来最长时间不会被访问的页面这是理论算法实际不可实现但考试用来比较性能上限。我拿引用串“7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1”配合3个物理块这是教材里最经典的对比题。直接列表会很长但考试的解题思路是先画一张表每一列是一次访问每个物理块占一行访问缺页就填上新页号缺页次数记一次。FIFO在这个引用串下会表现出所谓Belady异常物理块增加到4块缺页次数反而比3块时候更多。这个是选择填空的常客知道“FIFO可能出现Belady异常LRU和OPT不会”就够了。手算时容易出错的点在于LRU要在内存里按访问时间排序记下每页最近一次被访问的位置OPT要往后看引用串找到每个页下一次出现的位置选最远的那个淘汰。画表时建议每行标明“缺页”或“命中”最后数缺页数量。我在练习时发现最稳的办法是先抄几遍教材例题再拿其他题自练练到看到引用串就能下意识反映谁被淘汰。4.4 虚拟存储、页面分配和“抖动”虚拟存储这块简答题和概念题偏多。核心思想是程序只需部分装入内存就能运行其余部分驻留在磁盘运行时按需调入请求调页。好处是逻辑地址空间可以大于物理内存多道程序并发度提高。必背的两个名词缺页率指访问页面不在内存中的概率缺页率太高会导致系统频繁换页抖动颠簸指系统忙于调页、真正执行程序的时间极少CPU利用率骤降。产生抖动的原因是物理块分配不足系统给进程分配的页面数太少进程频繁缺页。解决办法是增加工作集、改善局部性、适当增加分配块数。选择题常让你识别哪种情况属于抖动记住关键词“频繁缺页”“系统效率急剧下降”就不会选错。5. 文件系统、I/O与磁盘调度小题常客但也有固定计算题5.1 文件物理结构与目录结构文件系统这一章通常以选择题和填空题为主但其中磁盘调度可能是计算题。物理结构三种连续分配、链接分配、索引分配。连续分配实现简单、读写快但会产生外部碎片文件扩展困难链接分配用指针串联不连续块解决碎片问题但只能顺序访问且链接指针会占额外空间索引分配把每个文件的盘块号集中放在索引块中既支持随机访问又便于扩展但索引块本身要开销。当前主流文件系统普遍采用索引或类似多级索引的结构考概念时说出优缺点就能得分。目录结构偶尔考树形目录和多级目录的优点便于分类管理、路径解析快、支持文件重名。常配合绝对路径和相对路径出个小计算题只要分清“从根目录出发”和“从当前目录出发”的区别即可。5.2 盘块分配与位示图磁盘空间管理最常见的考题是位示图。位示图用一串二进制位表示每个盘块是否空闲1表示已分配0表示空闲。题目常给出盘块总数、字长如16位或32位让你算某盘块号在第几个字、第几位。公式很简单盘块号从1开始计数则它在这个字中的位置(盘块号-1)取模字长1所在的字(盘块号-1)整除字长1。这种题就是套公式考前花十分钟记公式考试两分钟拿分。5.3 磁盘调度算法计算SSTF、SCAN、C-SCAN磁盘调度算法是容易被轻视的计算题。先记住算法思路FCFS按请求顺序服务SSTF优先服务离当前磁头最近的那个请求SCAN电梯算法朝一个方向移动沿途服务所有请求到端点或最后一个请求再反向C-SCAN循环扫描单向服务到端点后快速回起点继续扫描。考试给一组磁道请求序列和初始磁头位置让你算总寻道距离。举个例子磁头初始在53请求队列为98、183、37、122、14、124、65、67。FCFS寻道顺序就是请求的顺序53→98(45)98→183(85)183→37(146)37→122(85)122→14(108)14→124(110)124→65(59)65→67(2)总寻道距离458514685108110592640。SSTF需要每次选择最近的一个从53出发最近的是65(12)接着67(2)接着37(30)接着14(23)接着98(84)接着122(24)接着124(2)接着183(59)。总距离12230238424259236。看SSTF明显比FCFS高效很多。SCAN会规定一个初始方向比如向磁道号增大的方向。那么服务顺序是65、67、98、122、124、183然后反向处理37、14。第一次从53到183的距离是130反弹到14距离是169总距离130169299。计算时一定要先明确方向不然顺序全错。提醒SCAN和C-SCAN的边界条件不同教材对“到端点还是到最远请求后反向”有细微差别。考试时按教材的写法来如果题目只给了“SCAN”没给方向默认沿磁道号增大的方向。5.4 I/O控制方式与设备分配I/O这章的概念题偶尔出现在选择题里程序直接控制方式、中断驱动方式、DMA方式、通道方式。要记住程序直接控制是CPU忙等效率最低中断驱动让CPU在I/O期间可以做其他事但每次传输一个数据都要中断一次DMA按块传输只在开始和结束时中断CPU能直接在外设和内存之间搬运数据通道是一个专门执行I/O指令的处理器能独立管理多台设备。设备分配相关的名词有设备独立性用户程序使用逻辑设备名而不直接面对物理设备、逻辑设备表LUT映射等。考简答题的话“什么是设备独立性为什么引入”就是标准答案让用户程序与物理设备解耦提高可扩展性和易用性系统通过设备映射表完成逻辑到物理的转换。6. 考前一周的实操安排6.1 复习节奏怎么定先框架后刷题再查漏如果距离期末考试只剩一周建议按“3-2-1-1”的节奏安排前3天过教材重点章节按我上面整理的框架每天完成一个模块的阅读和笔记接下来2天集中刷计算大题重点练PV操作、银行家算法、页面置换和地址转换每天至少各做两类做完对照答案看自己的步骤是否规范第6天做一套完整的往年卷子严格限时模拟考场状态第7天只看错题和背诵型知识点比如进程状态图、死锁四个条件、各种调度算法优缺点。刷大题特别要强调“过程”两个字。操作系统计算题给分按步骤来就算结果错了只要中间的画表、公式、判断过程在也能拿大半分。所以平时练习就要养成把每一步写清楚的习惯尤其是银行家算法安全序列找错了没关系但要让老师看得到你的判断过程。6.2 根据个人经验最后提醒三个容易翻车的点第一个PV操作不要死记生产者和消费者的代码要理解信号量里“P申请、V释放”的本质考试很可能换个场景比如吸烟者问题、理发师问题。只要先把信号量的初始值定对再用“资源信号量在前、互斥信号量在后”的口诀就能稳住。第二个页面置换算法画表时不要把物理块编号和页面号搞混。表的第一行是页面访问序列下面若干行是内存里的物理块标“缺页”那一列才是计时器。我见过不少同学表画得很大却数错了缺页次数就因为在表格头部忘了区分“访问的页面”和“换入的页面”。第三个银行家算法里“剩余需求”必须用最大需求减去已分配很多人直接用题干给的Max判断忘了先算Need矩阵导致整个安全序列崩掉。这个步骤一分钱一分货先把表补完整再往后走。操作系统复习从来拼的不是天赋而是你有没有把它当成一门“有规律可循”的课。概念题靠理解加反复记忆计算题靠模板加刻意练习。把这些模块按分值排好优先级每天推进一小块期末卷子发下来的时候你会发现那些曾经吓人的大题不过都是换汤不换药的套路题。我最后再说一个亲测有效的小技巧把所有算法都亲手在草稿纸上完整走三遍以上尽量不要只看答案。写得多了考场上真的会形成肌肉记忆看一眼条件手就知道下一步该干嘛。