简介南京航空航天大学操作系统复习笔记是一份面向计算机考研与期末备考的PDF资料围绕操作系统核心知识进行系统整理便于快速搭建课程框架。压缩包内为单个PDF文档大小约1.15MB内容浓缩已获得1331人浏览学习适合日常翻阅与考前冲刺。笔记从批处理、分时、实时、网络、分布式五类系统及系统目标功能切入深入覆盖并发、共享、虚拟、异步特征以及程序顺序执行与并发执行、Bernstein条件、进程实体与PCB、进程状态转换、内核态/用户态、原语与进程创建步骤等内容。同时结合南航操作系统课程重点对进程控制块组织方式、进程同步通信等考查点做了归纳能帮助备考者理解操作系统工作机制强化记忆并查漏补缺整体结构清晰、重点突出适合二轮复习对照使用。1. 操作系统复习笔记南航课程里最值得反复啃的那本操作系统是计算机考研的核心课也是最容易“看着都会、做题就废”的一门课。南航这份复习笔记的特别之处在于它不是教材的简单缩写而是把整门课压缩成了一份能直接对着背、对着刷题的知识骨架——从五种操作系统分类到进程同步、调度算法、死锁处理每一章都保留了教材里的关键定义、伪代码和经典例题。对正在备战计科考研的人或者本科阶段想系统性过一遍操作系统核心概念的人这份笔记能帮你省下大量翻书整理的时间。不过要提醒一句这份笔记是知识密度很高的提纲不是小说需要配合做题才能真正吸收下面我按自己的拆解顺序把重点和踩过的坑一次说清楚。2. 进程与同步把信号量、PV操作和经典模型一次性理清2.1 从顺序执行到并发执行特征对比是理解一切的起点程序在单道环境下的顺序执行有三大特征顺序性、封闭性、可再现性。笔记里对它们的定义很简练但考试时容易在这里设概念题。顺序性指程序按书写顺序执行封闭性指程序独占全部资源可再现性指同样的初始条件和环境多次执行结果一致。这三个特征反过来说就是并发执行的问题所在——间断性、失去封闭性、不可再现性也就是“走走停停”、资源被共享、结果可能因调度顺序不同而不同。理解这个对比的意义在于后续讲的进程同步、互斥、信号量本质上都是在解决并发带来的“不可再现”问题。笔记里提到的Bernstein条件是判断两个程序能否并发执行的理论依据读集和写集不冲突才能安全并发。考试一般不直接考Bernstein条件的计算但它是理解为什么需要同步机制的基础。从顺序到并发系统引入的新实体就是进程。进程实体由程序段、数据段和PCB进程控制块三部分组成其中PCB是进程存在的唯一标志创建进程本质上是创建PCB撤销进程本质上是撤销PCB。这个观点值得记住因为后面对进程状态切换、调度、通信的理解都建立在PCB之上。2.2 进程状态转换与挂起不只是三态五态和挂起才是考点教科书上讲进程三态——就绪、执行、阻塞但实际考试和真实系统中还会涉及新状态、终止状态、挂起状态。笔记里对挂起状态的说明很关键挂起可以是终端用户的需要、父进程请求、负荷调节需要或操作系统自身需要。挂起操作把活动就绪变为静止就绪、活动阻塞变为静止阻塞激活操作则反向转换。我在复习时踩过的一个坑是把“阻塞”和“挂起”混为一谈。阻塞是进程等待某事件如I/O此时进程仍在内存中属于资源请求未满足挂起则是进程被整体移到外存不参与CPU调度哪怕它的等待事件已经满足也不会被调度。两者在状态转换图中的位置和条件不同做题时如果题目描述是“进程被换出内存”就要想到挂起而非阻塞。另外一个高频考点是用户态与核心态的划分。笔记提到Unix/Linux中核心态也称管态用户态也称目态。划分二者的主要原因是为了把用户程序和系统程序区分开以利于程序的共享和保护——代价是增加了系统复杂度和开销。这里考试常问的是哪些操作必须在核心态完成比如进程调度、内存分配、I/O操作、中断处理等凡是涉及硬件资源管理和系统安全的操作基本都在核心态。2.3 信号量与PV操作不要背代码要背物理含义信号量机制是进程同步的核心笔记里给出了整型信号量和记录型信号量的伪代码这是考试必考题。整型信号量的wait操作是while(S0); S--;会让进程忙等浪费CPU记录型信号量引入阻塞队列用S-value--和block操作避免忙等这才是实用方案。信号量的物理含义建议背下来S0表示有S个资源可用S0表示无资源可用S0时S的绝对值表示等待队列中的进程个数。做题时如果拿到一个信号量初值和一组PV操作第一步永远是确认这个信号量的物理含义再分析进程的等待关系。// 记录型信号量的 wait 和 signal 操作 wait(S) { S-value--; if (S-value 0) block(S-list); // 资源不够进程阻塞 } signal(S) { S-value; if (S-value 0) wakeup(S-list); // 唤醒第一个等待进程 }代码逻辑说明wait操作先减1再判断结果是否小于0。举个例子信号量初值为1第一个进程执行wait后value变为0可以继续运行第二个进程执行wait后value变为-1小于0因此被阻塞。signal操作先加1再判断结果是否小于等于0如果是就说明还有进程在等待需要唤醒一个。注意这里是0而不是0因为value加1后如果仍为0或负数说明等待队列中仍有进程存在。参数与使用场景说明初值代表可用资源数量用于互斥时初值设为1用于同步时初值设为0或资源数量。用于互斥时PV操作出现在同一个进程中临界区夹在wait和signal之间用于同步时PV操作出现在不同进程中一个进程负责V释放资源另一个进程负责P申请资源。这个区分有助于在做综合题时快速判断题目考的是互斥还是同步。2.4 生产者-消费者、读者-写者、哲学家进餐三个模型的解题模板这三个经典问题几乎每年都考笔记里给出了核心伪代码但单纯背代码不够要理解每个模型背后的同步约束。生产者-消费者问题中最关键的是P操作的顺序同步P操作必须在互斥P操作之前。笔记里的代码wait(full); wait(mutex);就是这层意思——先检查缓冲区是否有数据再申请进入临界区。如果颠倒顺序先wait(mutex)再wait(full)当缓冲区为空而消费者已经拿到mutex时它会阻塞在wait(full)上同时占着mutex不放导致生产者也无法进入临界区放数据形成死锁。两个V操作顺序则无关紧要。读者-写者问题考察的是读写公平性。读者优先策略中读者不等待除非有写者正在写写者优先策略中只要有写者等待新来的读者就不能进入。笔记提到读者优先会导致写者饥饿写者优先会导致读者饥饿。考试时题目通常会要求写出两种策略的信号量设置和PV代码关键是维持一个readcount变量并用mutex保护它。哲学家进餐问题是死锁的经典案例笔记给出了三种解法使用信号量集机制或奇偶编号规定拿筷子顺序。前两种在实际代码中各有代价第三种改动最小——奇数号先拿左边偶数号先拿右边打破环路等待。// 哲学家进餐奇数号先拿左筷偶数号先拿右筷 // chopstick[i] 和 chopstick[(i1)%5] 分别表示哲学家左右两侧的筷子 repeat { if (i % 2 1) { wait(chopstick[i]); // 奇数号先拿左 wait(chopstick[(i1) % 5]); // 再拿右 eat(); signal(chopstick[i]); signal(chopstick[(i1) % 5]); } else { wait(chopstick[(i1) % 5]); // 偶数号先拿右 wait(chopstick[i]); // 再拿左 eat(); signal(chopstick[(i1) % 5]); signal(chopstick[i]); } think(); } until false;代码逻辑说明解法通过改变拿筷顺序破坏环路等待条件。原来每个哲学家都先拿左筷可能形成所有哲学家各持一只筷子等待另一只的环现在奇偶号拿筷顺序相反相邻哲学家不可能同时各自持有对方需要的筷子而不释放。这段代码在考卷上直接可用不需要额外引入管程或信号量集。2.5 管程与进程通信理解设计动机比背定义重要管程是比信号量更高级的同步机制。笔记里提到采用PV机制编写并发程序有个问题共享变量和信号量的操作分散在各个进程中易读性差、不利于修改维护、正确性难以保证。管程把这些操作集中封装起来保证任何时候只有一个进程在管程内执行。管程由四部分组成名称、数据结构说明、对该数据结构进行操作的一组过程或函数、初始化语句。理解管程的关键是与进程做对比——进程是主动的有自己的生命周期由PCB管理管程是被动的是操作系统的固有成分不存在创建和撤销等待队列管理方式也不同。考试如果出管程相关题目通常是判断题或概念题能答出这些区别就够了。进程通信的三大类——共享存储器系统、消息传递系统、管道通信也是常考点。共享存储器靠共享数据结构或共享存储区消息传递以消息为单位直接或间接通信管道通信借助pipe文件实现。这里容易混淆的是共享存储区和共享数据结构前者是物理共享内存区域效率更高后者是两个进程通过公共变量交换数据属于低级通信。考试时如果问“哪种方式适合大量数据传输”要选共享存储区。2.6 线程为什么说线程切换比进程切换便宜引入线程的目的是进一步减小并发粒度——一个进程内部的各个部分也能并发执行。笔记里对进程与线程的比较整理得很清楚同进程中线程切换不引起进程切换跨进程的线程切换才引起进程切换线程不拥有系统资源但能访问所属进程的资源创建、撤销、切换的线程开销远小于进程线程间同步和通信比进程间容易。需要留意的是线程的分类内核支持线程和用户级线程。用户级线程切换不需要内核干预速度更快但一个线程阻塞会让整个进程阻塞内核支持线程由内核调度每个线程可以独立被调度代价是每次切换要陷入内核。笔记里特别强调只设置用户级线程的系统调度以进程为单位设置内核支持线程的系统调度以线程为单位。这句话在选择题里经常被换一种说法来出。3. 处理机调度与死锁计算题全攻略3.1 三级调度体系与调度算法目标操作系统的调度分为高级调度作业调度、低级调度进程调度和中级调度内存调度。高级调度决定哪些作业调入内存运行频率最低低级调度决定哪个就绪进程获得CPU运行频率最高中级调度负责进程在外存和内存之间的对换。考试常考的是这个“频率”对应关系以及各层调度的对象。调度算法的目标分为几类资源利用率、公平性、平衡性以及批处理系统关注的平均周转时间短、系统吞吐量高、处理机利用率高。如果把周转时间、等待时间、响应时间的定义混淆后续计算题就容易出错。周转时间从作业提交开始算到作业完成结束等待时间是不包括执行时间的纯等待响应时间从敲键盘开始到屏幕显示结果。3.2 四种经典算法的手算对比FCFS、SJF、PSA、HRRN先来先服务FCFS与短作业优先SJF是最常考的一对。FCFS按到达顺序调度简单、公平但短作业等待时间可能很长SJF按执行时间长短调度能显著缩短平均周转时间但长作业可能饿死。抢占式SJF也称最短剩余时间优先SRTF每次有进程到达时重新选择剩余时间最短的进程运行非抢占式SJF则只在一个进程执行完后才重新调度。下面用笔记里的数据做一个完整的手算示范这组数据在计算题练习中很有代表性。假设系统在8:00开始处理作业四个作业的提交时刻和服务时间如下表作业号提交时刻服务时间分钟18:002528:201038:202048:302558:3515FCFS调度下作业1在8:00开始8:25结束作业2在8:25开始8:35结束作业3在8:35开始8:55结束作业4在8:55开始9:20结束作业5在9:20开始9:35结束。平均周转时间为2515355060再除以5等于37分钟。SJF非抢占式调度下8:00作业1先运行到8:25。此时作业2、3都在等待作业2服务时间10分钟更短先运行至8:35作业3运行至8:558:55时作业4、5都在等待作业5服务时间15分钟更短先运行至9:10作业4最后运行至9:35平均周转时间为2515354540除以5等于32分钟。高响应比优先HRRN在8:25计算作业2和3的响应比。作业2等待5分钟服务时间10分钟响应比1.5作业3等待5分钟服务时间20分钟响应比1.25作业2先运行。HRRN在每次调度时刻都重新计算各作业优先权优先权等于等待时间加服务时间再除以服务时间既照顾短作业又防止长作业饿死。这三种算法的对比结论建议整理成笔记平均周转时间排序一般是SJF优于HRRN优于FCFS但SJF可能饿死长作业HRRN是一种折中方案。3.3 轮转调度与多级反馈队列时间片选多大才合理轮转调度算法RR让就绪队列上的每个进程每次只运行一个时间片时间片用完就切换到下一个进程。时间片的大小直接影响系统性能时间片太大退化为FCFS交互响应变差时间片太小进程切换开销占比过高CPU大部分时间都在做上下文切换。常见取值在10到100毫秒之间切换开销应控制在时间片的1%以内。多级反馈队列调度是轮转的升级版。笔记里的要点是总是先调度第1级队列的进程仅当第1级队列为空时才调度第2级队列依此类推进程用完一个时间片还没结束就降级到下一级队列。新进程总是进入第1级队列因此短作业能在高档队列快速完成长作业逐渐降级但不会饿死。考试中多级反馈队列常与时间片组合出题要求写出进程的执行顺序甘特图。解题时记住优先级高的队列绝对优先同一队列内用轮转。3.4 实时调度与优先级倒置EDF和LLF怎么算实时调度的基本条件包括提供必要的信息、系统处理能力强、采用抢占式调度机制、具有快速切换机制。实时调度不追求高吞吐量追求的是在截止时间内完成处理。EDF算法按截止时间确定优先级截止时间越早优先级越高。做题时把每个任务的当前截止时间列出来按最早截止时间选择下一个运行任务。LLF算法按松弛度确定优先级松弛度 截止时刻 - 当前时刻 - 还需CPU时间松弛度越小越紧急。注意松弛度会随调度过程的推进而改变每次调度时都要重新计算。优先级倒置是高频考点。解决办法有两种一是规定低优先级进程进入临界区后处理机不允许被抢占对短临界区有效二是动态优先级继承低优先级进程在使用临界资源时继承高优先级进程的优先级防止中间优先级进程抢占这能保证高优先级进程尽快获得资源。3.5 死锁四种必要条件与银行家算法的完整流程死锁的四个必要条件是互斥条件、请求和保持条件、不可抢占条件、环路等待条件。处理死锁的基本方法分为预防、避免、检测和解除四类。预防通过破坏必要条件实现——实际能破坏的是后三个互斥条件是非共享设备必须具备的不能破坏。破坏请求和保持条件用资源静态分配或请求前释放已占资源破坏不可抢占条件允许强行收回资源破坏环路等待条件用资源顺序分配法。银行家算法是避免死锁的核心算法也是考试计算题的重灾区。核心数据结构四个Available可利用资源向量、Max最大需求矩阵、Allocation分配矩阵、Need需求矩阵其中Need Max - Allocation。// 银行家算法核心步骤伪代码 // 1. 检查请求是否合法 if (Request[i][j] Need[i][j]) error(进程请求的资源超过其最大需求); if (Request[i][j] Available[j]) wait(当前无足够资源进程需等待); // 2. 试探性分配 Available[j] - Request[i][j]; Allocation[i][j] Request[i][j]; Need[i][j] - Request[i][j]; // 3. 执行安全性算法检查 // 若能找到安全序列则正式分配否则回滚代码逻辑说明试探性分配之后必须调用安全性算法检查系统是否仍处于安全状态。安全性算法的本质是模拟执行每次找一个Need不超过当前Available的进程假定它执行完并释放所占资源重复这个过程直到所有进程都能执行完。如果存在这样的推进顺序系统就是安全的。这里考试最容易出错的是忘记回滚——当安全性检查发现不安全时必须把Available、Allocation、Need恢复为试探前的值。死锁检测与避免的区别也要注意检测算法只需要判断是否存在安全序列不需要输出安全序列本身而死锁的解除常用剥夺资源和撤销进程两种方法。资源分配图中每种资源只有一个实例时有环等价于死锁多实例资源类型时有环不一定死锁——这种区分在判断题中常考。4. 避坑指南操作系统复习中的五个高频翻车点4.1 “阻塞”和“挂起”混为一谈现象做题时遇到“进程被换出内存到外存”第一反应写“进程进入阻塞状态”。原因阻塞是指进程等待某个事件而暂停进程仍然在内存中等待的事件一旦发生就会转为就绪挂起则是进程实体被移出内存到外存即使其等待的事件已满足也不能参与调度。解决把二者当成两个不同的状态维度。判断标准是看进程是否还“在内存里”——在内存中等待是阻塞被移出内存是挂起。另外记住挂起的四类起因终端用户需要、父进程请求、负荷调节需要、操作系统需要选择题常考。4.2 互斥PV和同步PV搞混顺序现象写生产者-消费者问题代码时先写wait(mutex)再写wait(full)运行后发现死锁。原因同步信号量负责“资源是否可用”互斥信号量负责“临界区是否可进”。当消费者发现缓冲区为空时如果它已经持有mutex那么它在等待full的同时占着mutex不放生产者无法进入临界区放数据互相等待死锁。解决同步P操作必须放在互斥P操作之前即先wait(full/empty)再wait(mutex)两个V操作顺序无关紧要。这个规则在考场上可以直接用不用每次推演一遍。4.3 死锁和饥饿分不清楚现象判断题说“低优先级进程长时间得不到调度属于死锁”判断为正确。原因死锁是多个进程互相等待对方释放资源形成循环等待没有外力作用永远无法推进饥饿是单个进程因调度策略不公平长期得不到所需资源不涉及循环等待。死锁必然伴随阻塞但饥饿进程可能处于就绪态只是永远不被调度。解决判断题的关键词是“循环等待”和“相互”。死锁强调每一方都持有对方需要的资源饥饿强调的是调度策略导致的资源分配不均。4.4 时间片轮转和抢占式SJF分不清楚现象题目给出时间片和作业到达时间套用SJF规则计算结果与答案不一致。原因时间片轮转是固定的时间片轮流执行不考虑剩余时间长短抢占式SJF是每次新进程到达时比较剩余执行时间选择剩余最短的进程运行。二者的本质区别在于“谁决定切换”——RR是时间片到期强制切换SRTF是出现更短剩余时间的进程时立刻抢占。解决做题时先看题目是否给出了时间片长度。有时间片就是RR没有时间片但强调“剩余时间最短优先”才是抢占式SJF。4.5 银行家算法忘记回滚现象计算完之后得出“系统进入不安全状态”但直接写了“分配成功”。原因银行家算法的试探分配必须配合安全性检查检查失败时要恢复原状。很多同学在草稿纸上算出Available的预分配值后直接当作最终结果提交。解决每次做银行家算法题都在草稿末尾预留一块区域写“回滚后的值”。正式答案需要体现分配前的值是什么、试探后的值是什么、安全性检查失败后恢复的值是什么阅卷老师看到这三个数才能确认你理解了这个流程。5. 复习方法把笔记变成自己的知识骨架拿到这份笔记后建议用三轮复习法每轮的目标不同不要试图一遍全记住。第一轮通读建立框架。花一到两天把五个章节按顺序快速过一遍不追求记忆只在阅读中圈出高频关键词——进程、PCB、信号量、死锁、调度算法、存储管理。这一轮目的是在脑中建立“操作系统知识地图”知道每个主题的管辖范围。笔记的开头把操作系统的分类、目标、功能、特征浓缩在一页内这一页就是整张地图的根节点。第二轮做题反哺笔记。操作系统是一门必须配合做题才能内化的课程。每做完一类题回到笔记对应章节把笔记上没有的内容补充进去。比如做完生产者-消费者问题后可以发现在笔记的信号量代码旁边追加一个“同步P在前互斥P在后”的醒目标注。笔记这时候不是一个终点而是一个折页的笔记本——越补充越厚才是复习到位的标志。第三轮默写检查。拿出一张白纸不看笔记尝试默写以下内容五种操作系统分类及特征、进程三态与五态转换图、记录型信号量的wait/signal代码、生产者-消费者问题的完整代码、银行家算法的四个数据结构的计算公式、死锁的四个必要条件。每默写一项就与笔记对照一次把遗漏的地方做标记下次复习优先看标记处。这个方法看着笨但经过三次默写后几乎没有知识盲区。我备考时做完八套真题后仍然坚持每天默写一次信号量操作代码持续了一个月——看上去简单但真正在考场上做到PV操作代码不丢分就是靠这种重复。另外有几个可以节省时间的筛选原则笔记中标记“背”的章节优先记忆如同步机制遵循的四条规则、死锁的四个条件、进程的五大特征标记“理解”的章节不需要逐字背如管程的设计背景、引入线程的原因——这类内容能用自己的话说明白就够了。最后提醒一句操作系统考研复习最忌讳“只看不做”笔记再好也要落实到做题上。这份笔记适合作为复习主轴但请一定搭配历年真题同步练习祝顺利上岸希望帮到你。本文还有配套的精品资源点击获取
