简介这份山东大学操作系统期末复习笔记面向备考操作系统课程的高校学生尤其适合需要系统梳理考点、快速回顾核心概念的期末冲刺场景。内容围绕操作系统导论、系统结构、进程管理、存储管理、文件管理、设备管理、作业管理与文件系统管理展开重点整理了进程与程序的区别、三态转换时机、PCB组成、调度队列、进程间通信的消息传递与共享内存对比以及Simple structure、Layered、Microkernel三种结构设计的优劣并附有系统调用接口与用户态内核态切换等易考细节。资源包为1个PDF文件大小约2.91MB结构紧凑便于打印或平板批注。目前已有974人学习下载说明其考点覆盖与笔记组织方式受到同校及同类课程学习者的认可适合作为期末查漏补缺与简答题背诵的参考材料。1. 操作系统期末复习从知识地图到查漏补缺的完整梳理操作系统这门课期末复习最怕的不是背不下来而是知识点散落在十几个章节里进程、调度、同步、死锁、内存、文件系统各成一块复习时东一榔头西一棒子考场上遇到综合题就拼不起来。梳理下来会发现这门课其实有一条清晰的主线操作系统是管理软硬件资源的系统软件所有章节都在回答同一个问题——怎么把有限的 CPU、内存、设备公平高效地分给多个进程。进程是基本单位调度决定谁先用 CPU同步和死锁解决协作中的冲突内存管理和虚拟内存解决空间分配文件系统解决持久化存储。适合正在系统学这门课的人拿它当复习地图也适合考前突击的人按模块查漏补缺。下面按这条主线把每个模块的要点、重点和容易翻车的地方逐一理清。2. 操作系统基础与结构概念、启动流程与三种结构的取舍2.1 操作系统的定义与五大功能操作系统是计算机系统中的一种系统软件负责组织和管理计算机的软硬件资源组织工作流程控制程序执行并向用户提供各种服务功能。它的功能可以拆成五块来记进程管理合理分配 CPU 时间提高 CPU 使用效率存储管理负责主存的分配回收和保护文件管理负责信息的存储、检索、共享和保护设备管理负责各种输入/输出设备作业管理负责作业调度及执行控制。这里有个容易混的点——作业JOB是用户要求计算机系统处理的一个计算问题它和进程不是一回事作业是用户提交的任务单位进程是系统执行的基本单位。计算机系统的层次结构是 hardware → operating system → application program → users操作系统在硬件之上、其他软件之下直接与硬件打交道。这个层次关系决定了操作系统的两个核心角色对上是服务提供者对下是硬件管理者。2.2 启动过程与中断驱动机制操作系统的启动过程是常考的描述题。接通电源或重启时计算机自动执行引导程序bootstrap loader引导程序进行系统初始化然后把操作系统核心程序装入主存等待事件发生。当有事件出现操作系统的服务程序处理它处理结束后继续等待下一个事件。这里的关键词是中断驱动interrupt driven——计算机系统中会有许多不同类型的事件发生对所发生的事件均有硬件识别且触发一个中断把控制转移给操作系统的某个服务程序。固件firmware用于存放初始引导代码。注意启动过程要按顺序写清楚——引导程序 → 系统初始化 → 核心程序装入主存 → 等待事件 → 中断触发 → 服务程序处理。漏掉任何一步都会丢分。2.3 三种操作系统结构的对比操作系统结构有三种经典设计考试常以对比题出现结构类型优点缺点Simple structure实现直接难以实现和保持未分模块Layered构造和调试简单层之间很难定义效率低Microkernel扩展简单可靠安全易于移植性能开销较大微内核的核心思路是把尽可能多的功能从内核移到用户空间内核只保留最基本的机制比如进程间通信和基本调度。这样扩展性和可靠性都好但每次服务请求都要经过用户态和内核态的切换开销自然就大了。2.4 API、系统调用接口与操作系统的关系这是概念题的高频考点。API 是应用程序调用操作系统功能的入口系统调用接口是应用程序和操作系统系统调用之间的链接。以open()为例应用程序调用open()时API 调用被系统调用接口截取由用户模式转为内核模式然后调用操作系统中相应的系统调用。整个链路是应用程序 → API → 系统调用接口 → 内核模式 → 系统调用。用户模式和内核模式的切换是理解这条链路的关键后面讲进程切换和中断处理时还会反复用到。3. 进程与线程状态转换、PCB、通信方式与多线程模型3.1 进程的概念与组成进程是某一特定功能的程序的一次执行过程是操作系统中最基本的单位。进程之间相互独立、相互作用竞争使用资源。进程的组成部分包括代码段、数据段全局变量、寄存器、栈临时变量、堆malloc 分配的内存。进程的三要素是程序 数据 PCB。进程和程序的区别是必考简答题四个要点要记牢进程由程序和数据组成离开程序没有意义程序是静态的进程是动态的进程有生命周期有诞生有消亡进程是短暂的而程序相对长久一个程序可以对应多个进程。另外系统进程执行操作系统的进程优先于用户进程完成用户功能的进程。PCB进程控制块是系统为了管理进程设置的专门数据结构用于记录进程的外部特征描述进程的运动变化过程。PCB 里包含许多特定进程信息是进程存在的唯一标志。3.2 进程状态转换图与转换时机进程有三个基本状态运行、等待、就绪。状态转换的时机是考试重点运行 → 等待等待某事件发生如发出 I/O 请求等待 → 就绪等待的事件发生了运行 → 就绪时间片到或有更高优先级进程出现就绪 → 运行被调度程序选中实际操作系统里状态转换更复杂但考试按这四个基本转换来答就够了。进程被选中执行后可能发生三种情况发出 I/O 请求被放入 I/O 队列创建一个新的子进程并等待其结束写时复制父子进程各自变量互不影响由于中断而强制释放 CPU被放回就绪队列。3.3 进程终止与父子进程关系进程终止涉及几个关键概念容易在选择题里设坑子进程通过系统调用exit()终止父进程通过wait()返回终止子进程的进程标识符由此得知哪个子进程终止了级联终止cascading termination父进程终止后子进程自动终止某些系统子进程终止但父进程未调用wait()→ 子进程变成僵尸进程父进程未调用wait()就终止 → 子进程变成孤儿进程Linux 和 Unix 会将 init 作为该子进程的父子进程的 pid0父进程的 pid0这个细节在代码题里经常用到。3.4 进程调度队列与三类调度程序进程进入系统后加入作业队列包含系统中所有进程就绪的、等待运行的进程保存在就绪队列由链表实现等待 I/O 设备的进程放在设备队列。三类调度程序的分工要分清长期调度程序从缓冲池中选择进程装入内存准备执行。它控制多道程序的 degree区分 I/O bound 和 CPU-bound 进程短期调度程序从准备执行的进程里选择进程并为之分配 CPU中期调度程序能将进程从内存中换出挂起suspend暂存在磁盘上后来再激活换入3.5 进程间通信共享内存与消息传递进程间通信有两种基本方式对比记忆对比项共享内存消息传递通信机制建立共享内存区域使用共享变量交换信息操作系统提供机制通过消息传递工具通信优点不需要系统调用速度快建立后不需要内核帮助交换少量数据很有用更容易实现缺点需要应用程序员自己编写访问和操作共享内存的代码需要内核介入开销相对大实例POSIXMach客户机服务器系统的通信方式有四种套接字、远程过程调用、管道、远程方法调用。Windows 使用本地过程调用local procedure call是同一机器两进程间的通信通过创建连接端口和通信端口实现。3.6 线程的引入原因与多线程模型线程是 CPU 使用的基本单元。引入线程有四个原因响应度高部分线程阻塞其他线程仍可继续执行资源共享同一进程的各个线程共享该进程的内存和资源经济线程比进程轻量创建及切换代价小多处理器体系结构的利用一个进程中的多个线程可运行在不同处理器上。用户线程由用户空间管理不需要内核支持不支持抢占式调度内核线程由操作系统直接支持和管理线程阻塞不相互影响切换代价接近于进程。多线程模型有三种多对一、一对一、多对多。线程取消分两种异步撤销立即终止目标线程和延迟撤销允许目标线程定期检查是否需要被取消。线程池预先创建一定数量的线程放入池中等待工作需要时唤醒。线程库创建方法有两种在用户空间中提供没有内核支持的库或使用操作系统直接支持的内核级库。4. CPU 调度从 FCFS 到多级反馈队列的算法对比与计算4.1 调度基础概念分派程序dispatcher是一个模块用来将 CPU 的控制交给由短期调度程序选择的进程功能包括切换上下文、切换到用户模式、跳转到用户程序的合适位置以重启程序。分派程序停止一个进程而启动另一个所花费的时间叫分派延迟dispatch latency。调度方式分两种非抢占某一进程被调度运行后除自身原因外会一直运行下去和抢占允许优先级更高的进程剥夺正在运行进程的 CPU。这个区分贯穿所有调度算法判断一个算法是抢占还是非抢占是选择题的常见考法。4.2 经典调度算法逐一拆解FCFS先到先服务非抢占实现简单但存在护航效果——若干个短进程被迫跟在长进程后面使进程推进缓慢。SJF最短作业优先具有最小等待时间常用于长期调度。非抢占版本就是 SJF抢占版本叫 SRTF最短剩余时间优先。HRRN最高响应比优先响应比 等待时间 服务时间/ 服务时间兼顾了等待时间和服务时间。优先级调度抢占或非抢占都可高优先级进程先执行。有的系统数字小优先级高有的系统数字大优先级高做题时要看清题目约定。低优先级进程可能永远不被执行这叫饥饿starvation解决办法是老化aging——逐渐增加在系统中等待很长时间的进程的优先级。RR轮转法每个进程执行一个时间片time quantum q后进入就绪队列末尾是抢占式专门为分时系统设计。q 太大退化成 FCFSq 太小导致上下文切换开销过大。理想情况下时间片应比上下文切换时间长。4.3 多级队列与多级反馈队列的区别这是简答题的高频考点两种算法的设计思想有本质不同多级队列调度将就绪队列分为多个独立队列根据进程属性分配队列每个队列有自己的调度方法。常见划分是前台进程交互和后台进程批处理前台优先级更高。队列间也有调度一般采用固定优先级抢占调度。进程一旦被分配到某个队列就不能在队列间移动。多级反馈队列允许进程在队列间移动根据不同 CPU 区间的特点来区分进程。若进程占用 CPU 时间过多会被挪到更低优先级的队列等待时间过长的进程会被挪到更高优先级的队列将 I/O 约束和交互进程留在更高优先级队列。它是最常用且最复杂的调度程序。对比要点多级队列是静态分配、队列间不移动多级反馈队列是动态调整、允许移动能自适应地区分进程类型。4.4 调度算法性能指标与计算衡量调度算法性能的指标有CPU 使用率、吞吐量、周转时间从进程提交到进程完成的时间段、等待时间在就绪队列中等待花费的时间和、响应时间从提交请求到产生第一响应的时间。需要使 CPU 使用率和吞吐量最大化使周转时间、等待时间、响应时间最小化尽量优化平均值。对于交互系统最小化响应时间的方差比最小化平均响应时间更重要。CPU-I/O 区间循环CPU-I/O burst cycle进程执行从 CPU 区间开始之后是 I/O 区间接着是另一个 CPU 区间然后是另一个 I/O 区间如此进行下去最终最后的 CPU 区间通过系统请求终止执行。注意计算等待时间时要区分单个进程的等待时间和平均等待时间。RR 调度中等待时间的计算要按时间片轮转的顺序逐段累加不能简单用总时间减去服务时间。5. 进程同步与死锁信号量、经典问题与银行家算法5.1 临界区问题与三个必要条件每个进程有一个代码段称为临界区在该区中的进程可能改变共同变量、更新一个表、写一个文件等。没有两个进程可以同时在临界区内执行。临界区问题需要满足三个条件互斥若进程 Pi 在临界区内执行则其他进程都不能在临界区内执行有空让进如果没有进程在临界区内执行且有进程需进入临界区那么只有那些不在剩余区内执行的进程可参加选择且这种选择不能无限推迟有限等待从一个进程做出进入临界区的请求直到该请求允许为止其他进程允许进入其临界区的次数有上限Peterson 算法是软件方法用于两个进程在临界区和剩余区交替执行。硬件同步用锁来防护临界区TestAndSet 原子指令用于检查和修改字的内容或交换两个字的内容是自动执行、不可中断的指令。5.2 信号量与自旋锁信号量 S 是一个整数变量除了初始化外只能通过 P 和 V 操作访问。计数信号量值域不受限制二进制信号量互斥锁只能为 0 或 1。自旋锁是在代码中连续循环进行忙等待的信号量由于进程在等待锁时还在运行浪费 CPU 时钟。解决自旋锁浪费的办法让每个信号量有一个整型值和一个进程链表当 P 操作中信号量不为正时让该进程阻塞自己当某进程必须等待信号量时就加入到进程链表上V 操作会从等待进程链表里取一个唤醒。信号量和互斥锁的区别是常考简答题信号量用于线程的同步互斥锁用于线程的互斥互斥锁只能为 0 或 1信号量可以为其他整数互斥锁加锁和解锁都由同一线程使用信号量可以有一个进程释放、另一个线程得到。自旋锁在单处理器系统中不能存在因为只有一个处理器为多个进程共享忙等待浪费 CPU 时钟。而在多处理器系统中一个线程在一个处理器自旋时另一线程可在另一处理器上在其临界区内执行所以自旋锁常用于多处理器系统。5.3 经典同步问题生产者-消费者问题一群生产者进程生产产品消费者进程消费产品。两者之间设置一个具有 n 个缓冲区的缓冲池生产者将产品放入缓冲区消费者从缓冲区取走产品。需要用三个信号量mutex 用于互斥访问缓冲池empty 表示空缓冲区数量full 表示满缓冲区数量。读者-写者问题一个数据库由多个并发进程共享读者只读数据库写者要更新数据库。要求写者对数据库有排他访问。读者之间可以同时读但写者写时不能有读者或其他写者。5.4 死锁的四个必要条件与处理策略死锁是一组进程每个进程都持有一定的资源并向系统申请其他进程当前拥有的资源进入死循环每个进程都无法推进。四个必要条件缺一不可互斥至少有一个资源处于非共享模式占有并等待一个进程持有一个资源并申请另外一个进程当前持有的资源非抢占资源不能被强制抢占循环等待存在一个进程等待环死锁处理有三种策略死锁预防静态策略限制申请资源确保至少一个必要条件不成立、死锁避免动态策略跟踪并评估资源分配过程、死锁检测和恢复。死锁预防的具体做法在进程执行前申请并获得所有需要的资源或申请其他资源前释放已分配资源资源利用率低可能产生饥饿把非抢占变为抢占对所有资源类型进行完全排序要求每个进程按递增顺序申请资源。5.5 银行家算法与安全状态安全状态是指存在进程序列对每个进程进程仍可以申请的资源数小于当前可用资源加上所有它前面的进程所占用的资源则这一序列是安全序列。安全状态不会死锁不安全状态可能死锁要确保系统永远不会进入不安全状态。银行家算法适用于每个资源有多个实例的情况。新进程进入系统时必须说明其每种资源可能的最大需求数量申请资源时系统计算资源分配后是否仍处于安全状态是则分配。算法分两步安全性算法找安全序列和资源请求算法通过安全性算法判断是否分配。应用条件在固定数量进程中共享固定数量资源进程申请资源小于可用资源总数进程等待资源时间有限进程间无顺序关系无需协作同步。5.6 死锁检测与恢复单个实例用等待图有环存在死锁Pi→Pj 表示 Pi 等待 Pj。多个实例用死锁检测算法类似银行家算法的结构allocation、request、available找 request available 前一个 allocation 的进程序列排不进序列的产生死锁。死锁恢复算法选择一个牺牲品进程回滚终止进程并重启或回滚到某安全状态。饥饿是某进程总被选为牺牲品导致的。死锁和饥饿的异同是简答题相同点是二者都由于竞争资源引起。不同点在于死锁进程都处于等待状态饥饿可能出现在忙等待的进程死锁进程等待永远不会被释放的资源饿死进程等待会被释放但却不会分配给自己的资源死锁一定发生了循环等待饥饿则不然死锁一定涉及多个进程饥饿可能只有一个饥饿情形下至少有一个进程能正常运行死锁则可能使整个系统崩溃。6. 内存管理与虚拟内存分页分段、页面置换与颠簸处理6.1 连续分配与非连续分配内存管理机制分连续分配和非连续分配两大类。连续分配包括固定分区用户空间划分为固定大小的分区每个分区装入一个进程和可变分区不预先划分根据进程大小动态建立分区。可变分区有三种放置策略首次适应分配第一个够大的、最佳适应分配足够大的孔里最小的、最差适应分配所用孔里最大的。外碎片是可用内存总和满足请求但并不连续形成的外部碎片用紧缩解决。内碎片是分配进程后在分区内被浪费的不能使用的内存碎片。6.2 分页与分段分页将用户进程空间分为相同大小的页物理内存空间分成相对应的帧帧与页大小相同。页表硬件包括 PTBR页表基寄存器存放页表的最小物理地址和 PTLR页表长度寄存器存放页表大小。TLB 是快表只存放页表的一部分查找时和 TLB 中每一项同时比较是并行搜索提高访问效率。二级页表要访问三次内存两次页表加一次主存。分段按程序自身逻辑划分若干程序段每段有段号内存空间被动态划分为长度不相同的区域称为物理段以段为单位分配每段在内存中占连续空间但各段之间可不相邻。地址映射过程CPU 取到逻辑地址后用段号查段表得到该段在内存的起始地址与段内偏移量计算出物理地址。分段和分页的比较分页对用户透明页大小固定是物理划分分段对用户可见段大小可变是逻辑划分。6.3 地址绑定与逻辑地址地址绑定有三种时机编译时编译时就知道进程将在内存中的驻留地址生成绝对代码、加载时编译器生成重定位代码地址变化时重新加载用户代码、执行时绑定延迟到执行中进行需要特定硬件支持。逻辑地址是 CPU 生成的地址物理地址是内存单元能看到的地址。编译和加载时生成相同的逻辑地址和物理地址运行时地址绑定方案会导致逻辑地址和物理地址不同。6.4 虚拟内存与按需调页虚拟内存将用户逻辑内存和物理内存分开好处包括弥补物理内存大小的不足为用户提供巨大的虚拟内存使编程更加容易一定程度提高反应速度减少对物理内存的读取从而保护内存允许文件和内存通过共享页为两个或多个进程所共享。按需调页是只有程序执行需要时才载入页那些从未访问的页不会调入物理内存。页错误陷阱缺页是访问尚未调入内存的页。缺页率 缺页次数 / 访问页面总数。处理缺页的步骤处理页错误中断 → 读入页 → 重新启动进程。写时复制是父子进程开始时共享同一页面若任何一个进程要对该页进行写操作就创建一个共享页的副本。Vfork() 不使用写时复制将父进程挂起子进程使用父进程的地址空间。6.5 页面置换算法对比算法置换目标特点FIFO最先调入的页实现简单可能出现 Belady 异常最优置换未来访问页中最远的只能用于和其他方法作比较LRU最近最少使用的计数器实现需遍历整个表格栈实现把引用页移到栈顶二次机会访问位为 0 的页用 FIFO 选择访问位为 1 则挪到链表尾并清零增强二次机会最近没使用没修改过的页使用位权重高于修改位LFU计数最小的页最不经常使用MFU计数最大的页最常使用LRU 的栈实现引用某页时把它移到栈顶栈底为牺牲页。二次机会算法用指针指向置换页面的下一个页面若访问位为 1 则改成 0 然后指针指向下一个页这就是时钟算法的思路。6.6 帧分配与系统颠簸帧分配有平均分配每个进程分得一样多的帧和比例分配根据进程大小按比例分配空闲帧。全局置换从所有帧中选择一个置换系统吞吐量更好常用局部置换每个进程仅从自己分配到的帧里选择置换有的帧会一直空闲。系统颠簸是频繁的调页行为若一个进程换页时间大于运行时间则这个进程就是颠簸的。解决方法包括页错误率策略页错误率低则减少分配帧数页错误率高则增加分配帧数和内存映射文件将一个磁盘块映射成内存的一页。7. 文件系统与期末查漏补缺从 FCB 到复习清单7.1 文件系统实现要点文件系统实现涉及几个关键数据结构引导控制块包括系统从该卷引导 OS 所需要的信息、卷控制块包括卷的详细信息、文件控制块FCB包含各项有关文件信息、访问许可、文件大小等。系统范围内打开的文件表包含每个打开文件的 FCB 副本及其他信息单个进程的打开文件表包含一个指向系统范围内已打开文件表中相关条目的指针。文件系统依据文件名找到 FCB 的过程系统先调用open()将文件名传给文件系统在打开文件时根据给定文件名搜索目录结构找到文件后其 FCB 复制到系统范围内的打开文件表接着在单个进程文件表中增加一个条目通过指针将系统文件表的条目和其他域相连open()返回一个指向单个进程的文件打开表中合适条目的指针。文件空间分配有三种方式连续分配每个文件占一系列连续的磁盘块访问性能最好但存在外部碎片、链接分配每个文件的数据块是一个单向链表无外部碎片但不能有效支持直接访问、FAT文件分配表下标是块号值指向下一个块号便于快速访问和高速缓存。FAT32 每项在表内占 32 位4B。虚拟文件系统VFS在文件系统接口和某个具体的本地文件系统实现或远程文件系统实现之间增加虚拟文件系统层可以把不同实现的文件系统统一起来。7.2 期末复习清单按模块自查考前对照下面这张清单逐项打勾能快速定位薄弱环节模块必会内容自查基础与结构操作系统定义与五大功能、启动过程、三种结构对比、API 与系统调用关系□进程与线程进程与程序区别、状态转换图、PCB 组成、父子进程终止、线程引入原因、多线程模型□CPU 调度FCFS/SJF/HRRN/优先级/RR 特点、多级队列与多级反馈队列区别、等待时间计算□进程同步临界区三条件、Peterson 算法、信号量 P/V 操作、生产者-消费者、读者-写者□死锁四个必要条件、预防与避免的区别、银行家算法、安全序列判断、死锁与饥饿异同□内存管理分页与分段对比、地址映射过程、TLB 作用、逻辑地址与物理地址□虚拟内存按需调页、缺页处理、页面置换算法对比、帧分配、系统颠簸□文件系统FCB 查找过程、三种分配方式对比、FAT 原理、VFS 作用□7.3 最容易翻车的几个点梳理下来会发现有几个地方几乎每年都有人栽跟头。第一银行家算法的安全序列判断——很多人在计算 Work Allocation 时忘记更新 Work 的值导致后面判断全错。正确做法是每分配一个进程Work 要加上该进程的 Allocation。第二RR 调度等待时间的计算——不能简单用总时间减去服务时间要按时间片逐段累加特别是进程多次进入就绪队列的情况。第三信号量 P/V 操作的顺序——在生产者-消费者问题中P(empty) 和 P(mutex) 的顺序不能颠倒否则可能死锁。第四页面置换算法的缺页次数统计——FIFO 可能出现 Belady 异常即增加帧数反而缺页次数增加这个反直觉的现象要记住。第五死锁检测中等待图的环判断——单个实例有环即死锁多个实例有环不一定死锁要结合可用资源数判断。提示计算题做完后用安全状态的定义反向验证一遍——检查是否存在一个进程序列使得每个进程都能在有限等待后获得所需资源并完成。这个习惯能帮你抓出大部分计算错误。7.4 考前一周的复习节奏如果只剩一周建议按这个节奏走前两天把进程管理、CPU 调度、同步与死锁的计算题各做一遍重点是银行家算法和 RR 调度第三天集中攻内存管理和虚拟内存的地址映射与页面置换计算第四天过文件系统的 FCB 查找和分配方式对比第五天把简答题的高频考点进程与程序区别、死锁与饥饿异同、多级队列与多级反馈队列区别、信号量与互斥锁区别默写一遍最后两天做综合题和查漏补缺。从那以后我每次复习操作系统都会先把这张知识地图默画一遍——进程是核心调度、同步、死锁、内存、文件系统是围绕它的五个模块每个模块的计算题和简答题分别过一遍再对照清单打勾。希望帮到你。本文还有配套的精品资源点击获取
