简介这份资源是《计算机操作系统第三版》课后习题的参考答案文档面向高校计算机专业学生、考研复习者以及准备操作系统课程考核的学习者用于对照教材章节核对习题解答、梳理知识脉络。内容覆盖操作系统引论、进程管理、并发编程等核心章节对分时系统与实时系统的比较、进程三态转换、PCB 的作用与唯一标志性、记录型信号量 wait/signal 的物理含义、前趋图与临界区互斥等典型题目均给出完整作答可当作章节复习的对照清单与答题思路参考。资源包共 1 个 doc 文件约 170KB体量轻便便于打印或离线查阅。目前已有 512 人学习适合在期末复习与考研初试阶段配合教材逐章核对使用。1. 操作系统复习地图从引论到设备管理的五条主线翻开任何一本操作系统教材目录几乎都长一个样引论、进程、调度与死锁、内存、设备。真正拉开差距的不是背没背过这些名词而是能不能在脑子里把它们串成一条因果链——为什么要有进程因为多道程序要并发并发为什么出问题因为资源竞争和推进顺序不确定于是需要同步机制、调度策略、死锁处理进程多了内存不够于是有虚拟存储和页面置换I/O 慢于是有通道、缓冲和 SPOOLing。这条链子理顺了第三版课后习题里那些看似零散的问答就会自动归位。这份笔记面向正在系统学操作系统、或者拿课后习题答案做复习底稿的人把五章内容压成一张可查漏补缺的地图重点标出概念对比和血泪易错点而不是把答案再抄一遍。2. 引论与进程管理OS 特征、PCB 与状态转换的复习重点2.1 操作系统的目标、作用与四大特征引论部分的考点高度集中梳理下来无非三组目标、作用、特征。设计现代 OS 的主要目标是方便性、有效性、可扩充性和开放性这四个词经常被拆开考单选或填空。OS 的作用表现为三个方面作为用户与计算机硬件系统之间的接口、作为计算机系统资源的管理者、实现了对计算机资源的抽象。这三条要能顺着说下来而不是死记顺序。四大特征是并发性、共享性、虚拟性、异步性。这里有个高频陷阱最基本特征是并发和共享而最重要的特征是并发性。题目问法不同答案就不同很多翻车就翻在没看清问的是最基本还是最重要。异步性的成因也要能讲清楚多道程序环境下多个进程并发执行受资源限制走走停停何时执行、何时暂停、推进速度都不可预知所以完成次序与进入内存次序不一致但在进程控制和同步机制支持下相同运行环境多次运行结果相同说明异步执行是系统允许的。分时系统与实时系统的比较是另一道必考题按交互性、及时性、可靠性三条线对比最稳比较维度分时系统实时系统交互性较强主要用于终端用户程序有交互能力但不及分时系统及时性以人所能接受的等待时间衡量实时控制以开始/完成截止时间衡量要求更高可靠性一般要求要求显著更高分时系统的关键问题是让用户能与自己的作业交互键入命令时系统要及时接收、及时处理、及时返回。及时接收靠多路卡同时接收各终端输入并为每个终端配缓冲区暂存命令及时处理则让所有用户作业直接进入内存为每个作业分配时间片只在自己的时间片内运行从而在不长时间内让每个作业都轮转一次。2.2 进程概念、PCB 与三态转换为什么要引入进程为了让程序在多道程序环境下能并发执行并能对并发执行的程序加以控制和描述。进程与程序的比较从三个角度切入动态性上进程由创建而产生、由调度而执行、因缺资源而暂停、由撤销而消亡有生命周期程序只是有序指令的静态集合并发性上进程是能与其他进程并发执行的基本单位程序本身不能并发独立性上进程实体是独立运行、独立获得资源和独立调度的基本单位未建立进程的程序不能作为独立单位运行。PCB 是进程实体的一部分是操作系统中最重要的记录型数据结构记录了描述进程情况和控制进程运行所需的全部信息。它使一个在多道环境下不能独立运行的程序成为一个能独立运行、能与其他进程并发执行的基本单位。说 PCB 是进程存在的唯一标志是因为整个生命周期中系统总是通过 PCB 控制进程是根据 PCB 而不是别的什么感知进程存在。三态转换的典型原因要能双向说清就绪到执行是进程调度程序分配了处理机执行到阻塞是当前进程因某事件无法执行比如访问已被占用的临界资源执行到就绪是时间片用完被暂停。挂起状态的引入有四种需要终端用户请求、父进程请求、负荷调节需要、操作系统需要被挂起的进程处于静止状态不能直接被处理机调度。2.3 同步机制信号量、前趋图与经典问题同步机构遵循四条准则空闲让进、忙则等待、有限等待、让权等待目的是实现进程互斥进入临界区。进入临界区前执行进入区代码是为了检查临界资源是否正被访问未被访问才可进入退出前执行退出区代码是为了恢复访问标志让其他进程能再访问该资源。记录型信号量的物理含义是这章的核心。wait(S) 在 S.value0 时表示还有可用资源执行后资源数减一S.value0 时资源已分配完进程调用 block 原语自我阻塞、放弃处理机并插入信号量链表。signal(S) 释放一个单位资源S.value 加一若加一后 S.value≤0说明链表中仍有被阻塞进程调用 wakeup 唤醒第一个等待进程。这段描述要能默写因为它是后面所有经典问题的地基。前趋图用信号量描述时每条有向边对应一个初值为 0 的信号量前驱语句执行完 signal后继语句执行前 wait。以四条语句 S1: a:xy; S2: b:z1; S3: c:a-b; S4: w:c1 为例S1 是 S3 的前驱S2 也是 S3 的前驱S3 是 S4 的前驱// 每条边一个信号量初值 0 表示事件尚未发生 semaphore a 0, b 0, c 0; // S1 完成后通知 S3 的两个前驱条件之一 S1; signal(a); // S2 完成后通知 S3 的另一个前驱条件 S2; signal(b); // S3 必须等 a、b 都 signal 过才能执行 wait(a); wait(b); S3; signal(c); // S4 只依赖 S3 wait(c); S4;参数说明信号量初值一律为 0因为前趋关系表达的是事件先后不是资源计数wait 的个数等于该语句入边的条数signal 的个数等于出边条数。写前趋图程序时最容易漏的是汇合点要 wait 全部入边只 wait 一条就会让 S3 提前跑。生产者—消费者问题的两个经典改错必须吃透。缺少 signal(full) 时full 始终为 0消费者执行 wait(full) 会认为缓冲池为空而永远等待缺少 signal(empty) 时缓冲池取空后 empty 仍为 0生产者申请不到空缓冲区而被阻塞。把 wait(full) 和 wait(mutex) 互换位置可能引起死锁缓冲区全满时生产者先拿到 mutex再 wait(empty) 失败阻塞它不释放 mutex消费者和其他生产者全部堵死而 signal(mutex) 与 signal(full) 互换只影响释放次序不会死锁。这条wait 顺序不能换、signal 顺序可换的结论是考场上最值钱的一句话。单缓冲区数据采集与计算的同步算法用 mutex、empty、full 三个信号量初值 1、1、0 即可若缓冲区只有一个且采集与计算天然互斥可省掉 mutex只用 empty1、full0 两个信号量这是答案里给出的简化版本考试时写哪个取决于题目是否要求显式互斥。2.4 线程与进程的四方比较引入线程是为了减少程序并发执行付出的时空开销使 OS 具有更好的并发性。进程与线程从四方面比较调度性上传统 OS 中进程既是资源拥有单位又是调度分派单位引入线程后线程成为调度分派单位、进程成为资源拥有单位并发性上线程让同一进程内多个线程也能并发并发粒度更细拥有资源上进程始终是资源拥有基本单位线程只拥有一点运行必不可少的资源但可访问所属进程的资源开销上创建撤销进程要分配回收资源切换要保存的现场信息也多于线程所以进程的创建、撤销、切换开销显著大于线程。低级通信工具效率低、对用户不透明、操作全靠程序员实现高级通信工具用一组通信命令高效传送大量数据这个对比常以简答出现。3. 调度与死锁三级调度、算法对比与银行家算法3.1 三级调度的分工高级调度决定把外存后备队列中哪些作业调入内存、创建进程、分配必要资源并插入就绪队列低级调度决定就绪队列中哪个进程获得处理机再由分派程序执行具体分配引入中级调度是为了提高系统资源利用率和系统吞吐量本质是在内存紧张时把暂时不能运行的进程换出等条件具备再换入。三级调度常被问各自任务是什么、为什么引入中级答的时候要把作业和进程两个词用准高级调度面对的是作业低级调度面对的是进程。3.2 FCFS 与 SPF 的异同两者相同点是都既可用于作业调度也可用于进程调度。不同点在选择依据FCFS 每次从后备队列选最先进入的作业调入内存有利于长作业/进程不利于短作业/进程SPF 选估计运行时间最短的作业有利于短作业/进程不利于长作业/进程。实时调度按调度方式分为非抢占调度算法和抢占调度算法两类这个二分法要记牢后面实时调度大题基本从这里展开。3.3 死锁四条件与处理策略死锁是多个进程因竞争资源造成的僵局无外力作用则永远无法推进。产生原因有二竞争资源和进程推进顺序非法。必要条件是互斥、请求和保持、不剥夺、环路等待四个条件缺一不可这是判断是否可能死锁的标尺。处理策略的取舍是高频简答预防死锁最容易实现但限制条件过严会降低资源利用率和系统吞吐量检测和解除死锁能让系统获得较好的资源利用率和吞吐量。预防的三条途径对应摒弃三个条件摒弃请求和保持要求进程运行前一次性申请全部资源只要有一种不能满足就整体等待摒弃不剥夺已持有资源的进程再申请新资源失败时必须释放已持有的全部资源以后重新申请摒弃环路等待把所有资源按类型线性排序并赋序号进程必须严格按序号递增次序请求资源分配图就不可能成环。3.4 银行家算法安全序列怎么推银行家算法是这章唯一需要动手算的题。给一张 Allocation、Need、Available 表第一步算 WorkAllocation第二步找 Need≤Work 的进程第三步回收其 Allocation 继续找直到所有进程都能 finish。以题目数据为例存在安全序列 P0→P3→P4→P1→P2所以初始状态安全。当 P2 请求 Request(1,2,2,2) 时先做合法性检查Request 不超过 Need、不超过 Available试分配后 Available 变为 (0,4,0,0)此时没有任何进程的 Need 能被满足系统进入不安全状态因此不能分配。检查步骤判断内容本例结果请求≤Need(1,2,2,2)≤(2,3,5,6)通过请求≤Available(1,2,2,2)≤(1,6,2,2)通过试分配后找安全序列Available(0,4,0,0)找不到拒绝提示安全序列不唯一考试写出任意一条即可但每一步的 Work、Need、Allocation、WorkAllocation 四列要写全否则过程分拿不到。4. 存储器管理装入链接、分页分段与页面置换4.1 装入方式与链接方式配置层次式存储器的理由有三多个存储器使两端硬件能并行工作多级存储特别是 Cache 是减轻存储器带宽对系统性能影响的最佳结构方案微处理机内部设缓冲存储器、增加寄存器数量可缓解对存储器的压力。程序装入内存有三种方式绝对装入适用于单道程序环境重定位装入和动态运行时装入适用于多道程序环境。链接分三种静态链接在运行前把目标模块和库函数链接成完整装配模块且不再拆开装入时动态链接边装入边链接遇到外部模块调用就去找并修改相对地址运行时动态链接把链接推迟到执行时发现被调用模块未装入才由 OS 装入并链接。链接时要完成两件事修改相对地址、变换外部调用符号。动态重定位的引入是因为程序运行中经常要在内存中移动移动后必须修改地址才能正常执行实现靠硬件地址变换机构增设重定位寄存器存放程序在内存的起始地址真正访问的地址是相对地址与寄存器值相加。4.2 分区分配策略与对换四种分区分配策略的优缺点要成对记首次适应保留高址大空闲区、利于大作业但低址不断被划分留下大量小空闲区且每次从低址查找增加开销循环首次适应让空闲区分布更均匀、减少查找开销但缺乏大空闲区装不下大作业最佳适应每次给最合适的分区但留下大量难以利用的小空闲区最坏适应剩下的空闲区不至于太小、碎片几率最小但缺乏大空闲区不利于大文件。引入对换能把暂不运行的进程或暂不用的程序数据换到外存腾出内存给具备运行条件的进程提高内存利用率。以进程为单位对换时并非整个进程换出PCB 总有部分或全部常驻内存程序段和数据段可能正被若干进程共享这两部分不能换出。4.3 分页与分段三维度区别分页需要页表机制和地址变换机构的硬件支持。分页与分段的共同点是都采用离散分配、都要通过地址映射机构实现地址变换区别有三功能上页是物理单位分页是为消减内存外零头、提高利用率满足系统管理需要段是逻辑单位含一组意义相对完整的信息满足用户需要大小上页固定由系统确定段长度不固定由用户程序决定地址空间上分页是一维的分段是二维的。分段更易实现共享和保护因为每段从 0 开始编址、地址连续共享保护只需设一个段表项把基址与内存地址对应而分页每页分散存储需要建立大量页表项一一对应。连续分配与离散分配的比较要落到各自适合什么连续分配包括单一连续和分区式单一连续最简单但只适合单用户单任务固定分区会造成空间浪费动态分区按需分配但四种算法各有碎片问题离散分配包括分页、分段、段页式分页提高内存利用率分段满足用户需要且共享保护更优段页式取长补短既有分段便于共享保护动态链接的优点又能像分页那样解决外部碎片和离散分配问题。4.4 虚拟存储器与页面置换计算虚拟存储器的特征是离散性、多次性、对换性、虚拟性最本质的特征是离散性最重要的特征是虚拟性——这两个最又是易混点。实现虚拟存储器需要页表机制、缺页中断机构、地址变换机构分段系统对应段表、缺段中断、地址变换机构。请求分页的物理块分配策略有三种固定分配局部置换、可变分配全局置换、可变分配局部置换。FIFO 缺页计算是必练题型。页面走向 4、3、2、1、4、3、5、4、3、2、1、5物理块 M3 时缺页 9 次、缺页率 75%M4 时缺页 10 次、缺页率 83%。块数增加反而缺页增加这就是 Belady 现象只有 FIFO 这类算法会出现LRU 和 OPT 不会。改进型 Clock 算法在考虑页面使用情况之外再引入置换代价换出时若页面被修改过要写回磁盘未修改则不必所以优先选未使用且未修改的页面换出。抖动是指内存无空闲又发生缺页时调出一页刚换出的页很快又被访问需重新调入频繁换页使系统大部分时间耗在换进换出上几乎不能完成有效工作。成因是 CPU 利用率与多道程序度的矛盾提高多道程序度本为提高利用率却造成缺页率急剧上升、利用率下降调度程序又继续提高多道程序度形成恶性循环。5. 设备管理I/O 控制方式、缓冲与 SPOOLing5.1 三种通道与瓶颈破解字节多路通道含许多非分配型子通道连接低中速设备子通道按时间片轮转共享主通道按字节传送一个子通道交换完一个字节立即让出主通道给下一个数组选择通道只含一个分配型子通道一段时间只能执行一道通道程序、控制一台设备按数组传送被占用后一直独占直到传完利用率低主要用于多台高速设备数组多路通道结合两者优点含多个非分配型子通道连接高中速设备按时间片轮转共享主通道、按数组传送既有高速率又有满意的通道利用率。通道不足造成的瓶颈最有效的解法是增加设备到主机间的通路而不是增加通道即一个设备连多个控制器、一个控制器连多个通道。多通路不仅解决瓶颈还提高可靠性个别通道或控制器故障不会让设备与存储器之间无法建立通路。5.2 I/O 控制方式的演进与适用场合推动 I/O 控制发展的因素有三尽量减少 CPU 对 I/O 控制的干预把 CPU 从繁杂控制中解脱出来做数据处理缓和 CPU 高速性与设备低速性的矛盾提高利用率和吞吐量提高 CPU 与 I/O 设备的并行程度。四种控制方式及适用场合程序 I/O 方式适用于早期无中断的计算机系统中断驱动方式普遍用于现代计算机系统DMA 方式适用于块设备与主机交换数据I/O 通道方式适用于一组数据块的交换但要求系统配置相应通道及通道控制器。5.3 单缓冲与双缓冲的时间公式单缓冲下磁盘把一块数据输入缓冲区时间为 TOS 把缓冲区数据传到用户区为 MCPU 计算为 C。设备输入与 CPU 处理可并行所以每块数据处理时间为 max(C,T)M。双缓冲下设备输入与 CPU 处理并行、设备输入与数据传送也并行耗时约为 max(CM,T)因 M 是内存内搬移、非常短暂可省略近似为 max(C,T)。这两个公式要能解释为什么而不是只背结果。5.4 设备独立性与 SPOOLing 虚拟设备引入设备独立性使应用程序独立于具体物理设备设备分配更灵活也容易实现 I/O 重定向。实现的关键是在设备驱动程序之上设一层设备独立性软件执行所有 I/O 设备的公用操作并向用户层提供统一接口系统中设置逻辑设备表 LUT 完成逻辑设备到物理设备的映射表目含逻辑设备名、物理设备名、驱动程序入口地址三项。分配独占设备的步骤是一条链进程以逻辑设备名请求查 LUT 得物理设备类型指针检索系统设备表找空闲且安全可用的设备控制表再依次检查控制器控制表、通道控制表是否忙碌忙则挂等待队列三者都分配成功才算成功然后启动设备传送。虚拟设备是通过虚拟技术把一台独占设备变换成若干台逻辑设备供多个进程同时使用实现依赖的关键技术是 SPOOLing。后台打印时输出进程在输出井中申请空闲盘块区存放待打印数据这是 SPOOLing 系统为请求 I/O 进程提供服务的起点后续再由输出进程按队列实际打印。6. 查漏补缺一份可执行的复习清单复习到这一步最怕的不是不会而是以为会了。我的做法是把五章压成一张自测表每行一个必答点能不看书画出关键词才算过。下面这张表按章排列右列是我自己踩过的坑你可以直接拿去对照。章节必答点常见翻车处引论OS 四大特征、最基本与最重要之分把最基本答成最重要引论分时与实时三线对比及时性衡量标准混用进程PCB 为何是唯一标志只答记录信息不答系统据此感知进程进程三态转换双向原因阻塞到就绪写成被调度进程wait/signal 物理含义忘记 value≤0 时唤醒进程生产者消费者改错wait 互换与 signal 互换混为一谈调度三级调度任务高级调度对象写成进程死锁四条件与三种预防途径预防与避免策略张冠李戴死锁银行家算法安全序列试分配后忘检查 Available内存分页分段三维区别地址空间维数答反内存FIFO 缺页与 Belady块数增加就认定缺页必减内存虚拟存储最本质/最重要特征离散性与虚拟性互换设备单双缓冲时间公式只背公式不解释并行关系设备独占设备分配六步漏掉通道检查具体怎么用这张表第一遍合上书对每行口述 30 秒卡壳的做记号第二遍只攻记号行回到对应章节把那段答案的因果链重新推一遍而不是重读第三遍挑计算题——前趋图信号量、银行家算法、FIFO 缺页——各手写一遍写的时候强制标出每一步的参数含义。计算题是操作系统的黑匣子光看答案觉得顺自己动笔就露馅这是血泪经验。还有一个容易被忽略的动作把每道简答题的答案压缩成结论 一句理由。比如最基本特征是并发和共享因为多道程序环境下两者互为存在条件考场上先写结论再补理由比整段背诵更抗紧张。前趋图和信号量题则相反必须完整写出 wait/signal 序列少一个就扣分没有后悔药。从那以后我每次复习操作系统都强制走一遍合书口述—标记卡壳—手写计算—压缩结论这四步哪怕时间只够走一遍也比通读三遍答案踏实。希望帮到你。本文还有配套的精品资源点击获取
简介这份资源是《计算机操作系统第三版》课后习题的参考答案文档面向高校计算机专业学生、考研复习者以及准备操作系统课程考核的学习者用于对照教材章节核对习题解答、梳理知识脉络。内容覆盖操作系统引论、进程管理、并发编程等核心章节对分时系统与实时系统的比较、进程三态转换、PCB 的作用与唯一标志性、记录型信号量 wait/signal 的物理含义、前趋图与临界区互斥等典型题目均给出完整作答可当作章节复习的对照清单与答题思路参考。资源包共 1 个 doc 文件约 170KB体量轻便便于打印或离线查阅。目前已有 512 人学习适合在期末复习与考研初试阶段配合教材逐章核对使用。1. 操作系统复习地图从引论到设备管理的五条主线翻开任何一本操作系统教材目录几乎都长一个样引论、进程、调度与死锁、内存、设备。真正拉开差距的不是背没背过这些名词而是能不能在脑子里把它们串成一条因果链——为什么要有进程因为多道程序要并发并发为什么出问题因为资源竞争和推进顺序不确定于是需要同步机制、调度策略、死锁处理进程多了内存不够于是有虚拟存储和页面置换I/O 慢于是有通道、缓冲和 SPOOLing。这条链子理顺了第三版课后习题里那些看似零散的问答就会自动归位。这份笔记面向正在系统学操作系统、或者拿课后习题答案做复习底稿的人把五章内容压成一张可查漏补缺的地图重点标出概念对比和血泪易错点而不是把答案再抄一遍。2. 引论与进程管理OS 特征、PCB 与状态转换的复习重点2.1 操作系统的目标、作用与四大特征引论部分的考点高度集中梳理下来无非三组目标、作用、特征。设计现代 OS 的主要目标是方便性、有效性、可扩充性和开放性这四个词经常被拆开考单选或填空。OS 的作用表现为三个方面作为用户与计算机硬件系统之间的接口、作为计算机系统资源的管理者、实现了对计算机资源的抽象。这三条要能顺着说下来而不是死记顺序。四大特征是并发性、共享性、虚拟性、异步性。这里有个高频陷阱最基本特征是并发和共享而最重要的特征是并发性。题目问法不同答案就不同很多翻车就翻在没看清问的是最基本还是最重要。异步性的成因也要能讲清楚多道程序环境下多个进程并发执行受资源限制走走停停何时执行、何时暂停、推进速度都不可预知所以完成次序与进入内存次序不一致但在进程控制和同步机制支持下相同运行环境多次运行结果相同说明异步执行是系统允许的。分时系统与实时系统的比较是另一道必考题按交互性、及时性、可靠性三条线对比最稳比较维度分时系统实时系统交互性较强主要用于终端用户程序有交互能力但不及分时系统及时性以人所能接受的等待时间衡量实时控制以开始/完成截止时间衡量要求更高可靠性一般要求要求显著更高分时系统的关键问题是让用户能与自己的作业交互键入命令时系统要及时接收、及时处理、及时返回。及时接收靠多路卡同时接收各终端输入并为每个终端配缓冲区暂存命令及时处理则让所有用户作业直接进入内存为每个作业分配时间片只在自己的时间片内运行从而在不长时间内让每个作业都轮转一次。2.2 进程概念、PCB 与三态转换为什么要引入进程为了让程序在多道程序环境下能并发执行并能对并发执行的程序加以控制和描述。进程与程序的比较从三个角度切入动态性上进程由创建而产生、由调度而执行、因缺资源而暂停、由撤销而消亡有生命周期程序只是有序指令的静态集合并发性上进程是能与其他进程并发执行的基本单位程序本身不能并发独立性上进程实体是独立运行、独立获得资源和独立调度的基本单位未建立进程的程序不能作为独立单位运行。PCB 是进程实体的一部分是操作系统中最重要的记录型数据结构记录了描述进程情况和控制进程运行所需的全部信息。它使一个在多道环境下不能独立运行的程序成为一个能独立运行、能与其他进程并发执行的基本单位。说 PCB 是进程存在的唯一标志是因为整个生命周期中系统总是通过 PCB 控制进程是根据 PCB 而不是别的什么感知进程存在。三态转换的典型原因要能双向说清就绪到执行是进程调度程序分配了处理机执行到阻塞是当前进程因某事件无法执行比如访问已被占用的临界资源执行到就绪是时间片用完被暂停。挂起状态的引入有四种需要终端用户请求、父进程请求、负荷调节需要、操作系统需要被挂起的进程处于静止状态不能直接被处理机调度。2.3 同步机制信号量、前趋图与经典问题同步机构遵循四条准则空闲让进、忙则等待、有限等待、让权等待目的是实现进程互斥进入临界区。进入临界区前执行进入区代码是为了检查临界资源是否正被访问未被访问才可进入退出前执行退出区代码是为了恢复访问标志让其他进程能再访问该资源。记录型信号量的物理含义是这章的核心。wait(S) 在 S.value0 时表示还有可用资源执行后资源数减一S.value0 时资源已分配完进程调用 block 原语自我阻塞、放弃处理机并插入信号量链表。signal(S) 释放一个单位资源S.value 加一若加一后 S.value≤0说明链表中仍有被阻塞进程调用 wakeup 唤醒第一个等待进程。这段描述要能默写因为它是后面所有经典问题的地基。前趋图用信号量描述时每条有向边对应一个初值为 0 的信号量前驱语句执行完 signal后继语句执行前 wait。以四条语句 S1: a:xy; S2: b:z1; S3: c:a-b; S4: w:c1 为例S1 是 S3 的前驱S2 也是 S3 的前驱S3 是 S4 的前驱// 每条边一个信号量初值 0 表示事件尚未发生 semaphore a 0, b 0, c 0; // S1 完成后通知 S3 的两个前驱条件之一 S1; signal(a); // S2 完成后通知 S3 的另一个前驱条件 S2; signal(b); // S3 必须等 a、b 都 signal 过才能执行 wait(a); wait(b); S3; signal(c); // S4 只依赖 S3 wait(c); S4;参数说明信号量初值一律为 0因为前趋关系表达的是事件先后不是资源计数wait 的个数等于该语句入边的条数signal 的个数等于出边条数。写前趋图程序时最容易漏的是汇合点要 wait 全部入边只 wait 一条就会让 S3 提前跑。生产者—消费者问题的两个经典改错必须吃透。缺少 signal(full) 时full 始终为 0消费者执行 wait(full) 会认为缓冲池为空而永远等待缺少 signal(empty) 时缓冲池取空后 empty 仍为 0生产者申请不到空缓冲区而被阻塞。把 wait(full) 和 wait(mutex) 互换位置可能引起死锁缓冲区全满时生产者先拿到 mutex再 wait(empty) 失败阻塞它不释放 mutex消费者和其他生产者全部堵死而 signal(mutex) 与 signal(full) 互换只影响释放次序不会死锁。这条wait 顺序不能换、signal 顺序可换的结论是考场上最值钱的一句话。单缓冲区数据采集与计算的同步算法用 mutex、empty、full 三个信号量初值 1、1、0 即可若缓冲区只有一个且采集与计算天然互斥可省掉 mutex只用 empty1、full0 两个信号量这是答案里给出的简化版本考试时写哪个取决于题目是否要求显式互斥。2.4 线程与进程的四方比较引入线程是为了减少程序并发执行付出的时空开销使 OS 具有更好的并发性。进程与线程从四方面比较调度性上传统 OS 中进程既是资源拥有单位又是调度分派单位引入线程后线程成为调度分派单位、进程成为资源拥有单位并发性上线程让同一进程内多个线程也能并发并发粒度更细拥有资源上进程始终是资源拥有基本单位线程只拥有一点运行必不可少的资源但可访问所属进程的资源开销上创建撤销进程要分配回收资源切换要保存的现场信息也多于线程所以进程的创建、撤销、切换开销显著大于线程。低级通信工具效率低、对用户不透明、操作全靠程序员实现高级通信工具用一组通信命令高效传送大量数据这个对比常以简答出现。3. 调度与死锁三级调度、算法对比与银行家算法3.1 三级调度的分工高级调度决定把外存后备队列中哪些作业调入内存、创建进程、分配必要资源并插入就绪队列低级调度决定就绪队列中哪个进程获得处理机再由分派程序执行具体分配引入中级调度是为了提高系统资源利用率和系统吞吐量本质是在内存紧张时把暂时不能运行的进程换出等条件具备再换入。三级调度常被问各自任务是什么、为什么引入中级答的时候要把作业和进程两个词用准高级调度面对的是作业低级调度面对的是进程。3.2 FCFS 与 SPF 的异同两者相同点是都既可用于作业调度也可用于进程调度。不同点在选择依据FCFS 每次从后备队列选最先进入的作业调入内存有利于长作业/进程不利于短作业/进程SPF 选估计运行时间最短的作业有利于短作业/进程不利于长作业/进程。实时调度按调度方式分为非抢占调度算法和抢占调度算法两类这个二分法要记牢后面实时调度大题基本从这里展开。3.3 死锁四条件与处理策略死锁是多个进程因竞争资源造成的僵局无外力作用则永远无法推进。产生原因有二竞争资源和进程推进顺序非法。必要条件是互斥、请求和保持、不剥夺、环路等待四个条件缺一不可这是判断是否可能死锁的标尺。处理策略的取舍是高频简答预防死锁最容易实现但限制条件过严会降低资源利用率和系统吞吐量检测和解除死锁能让系统获得较好的资源利用率和吞吐量。预防的三条途径对应摒弃三个条件摒弃请求和保持要求进程运行前一次性申请全部资源只要有一种不能满足就整体等待摒弃不剥夺已持有资源的进程再申请新资源失败时必须释放已持有的全部资源以后重新申请摒弃环路等待把所有资源按类型线性排序并赋序号进程必须严格按序号递增次序请求资源分配图就不可能成环。3.4 银行家算法安全序列怎么推银行家算法是这章唯一需要动手算的题。给一张 Allocation、Need、Available 表第一步算 WorkAllocation第二步找 Need≤Work 的进程第三步回收其 Allocation 继续找直到所有进程都能 finish。以题目数据为例存在安全序列 P0→P3→P4→P1→P2所以初始状态安全。当 P2 请求 Request(1,2,2,2) 时先做合法性检查Request 不超过 Need、不超过 Available试分配后 Available 变为 (0,4,0,0)此时没有任何进程的 Need 能被满足系统进入不安全状态因此不能分配。检查步骤判断内容本例结果请求≤Need(1,2,2,2)≤(2,3,5,6)通过请求≤Available(1,2,2,2)≤(1,6,2,2)通过试分配后找安全序列Available(0,4,0,0)找不到拒绝提示安全序列不唯一考试写出任意一条即可但每一步的 Work、Need、Allocation、WorkAllocation 四列要写全否则过程分拿不到。4. 存储器管理装入链接、分页分段与页面置换4.1 装入方式与链接方式配置层次式存储器的理由有三多个存储器使两端硬件能并行工作多级存储特别是 Cache 是减轻存储器带宽对系统性能影响的最佳结构方案微处理机内部设缓冲存储器、增加寄存器数量可缓解对存储器的压力。程序装入内存有三种方式绝对装入适用于单道程序环境重定位装入和动态运行时装入适用于多道程序环境。链接分三种静态链接在运行前把目标模块和库函数链接成完整装配模块且不再拆开装入时动态链接边装入边链接遇到外部模块调用就去找并修改相对地址运行时动态链接把链接推迟到执行时发现被调用模块未装入才由 OS 装入并链接。链接时要完成两件事修改相对地址、变换外部调用符号。动态重定位的引入是因为程序运行中经常要在内存中移动移动后必须修改地址才能正常执行实现靠硬件地址变换机构增设重定位寄存器存放程序在内存的起始地址真正访问的地址是相对地址与寄存器值相加。4.2 分区分配策略与对换四种分区分配策略的优缺点要成对记首次适应保留高址大空闲区、利于大作业但低址不断被划分留下大量小空闲区且每次从低址查找增加开销循环首次适应让空闲区分布更均匀、减少查找开销但缺乏大空闲区装不下大作业最佳适应每次给最合适的分区但留下大量难以利用的小空闲区最坏适应剩下的空闲区不至于太小、碎片几率最小但缺乏大空闲区不利于大文件。引入对换能把暂不运行的进程或暂不用的程序数据换到外存腾出内存给具备运行条件的进程提高内存利用率。以进程为单位对换时并非整个进程换出PCB 总有部分或全部常驻内存程序段和数据段可能正被若干进程共享这两部分不能换出。4.3 分页与分段三维度区别分页需要页表机制和地址变换机构的硬件支持。分页与分段的共同点是都采用离散分配、都要通过地址映射机构实现地址变换区别有三功能上页是物理单位分页是为消减内存外零头、提高利用率满足系统管理需要段是逻辑单位含一组意义相对完整的信息满足用户需要大小上页固定由系统确定段长度不固定由用户程序决定地址空间上分页是一维的分段是二维的。分段更易实现共享和保护因为每段从 0 开始编址、地址连续共享保护只需设一个段表项把基址与内存地址对应而分页每页分散存储需要建立大量页表项一一对应。连续分配与离散分配的比较要落到各自适合什么连续分配包括单一连续和分区式单一连续最简单但只适合单用户单任务固定分区会造成空间浪费动态分区按需分配但四种算法各有碎片问题离散分配包括分页、分段、段页式分页提高内存利用率分段满足用户需要且共享保护更优段页式取长补短既有分段便于共享保护动态链接的优点又能像分页那样解决外部碎片和离散分配问题。4.4 虚拟存储器与页面置换计算虚拟存储器的特征是离散性、多次性、对换性、虚拟性最本质的特征是离散性最重要的特征是虚拟性——这两个最又是易混点。实现虚拟存储器需要页表机制、缺页中断机构、地址变换机构分段系统对应段表、缺段中断、地址变换机构。请求分页的物理块分配策略有三种固定分配局部置换、可变分配全局置换、可变分配局部置换。FIFO 缺页计算是必练题型。页面走向 4、3、2、1、4、3、5、4、3、2、1、5物理块 M3 时缺页 9 次、缺页率 75%M4 时缺页 10 次、缺页率 83%。块数增加反而缺页增加这就是 Belady 现象只有 FIFO 这类算法会出现LRU 和 OPT 不会。改进型 Clock 算法在考虑页面使用情况之外再引入置换代价换出时若页面被修改过要写回磁盘未修改则不必所以优先选未使用且未修改的页面换出。抖动是指内存无空闲又发生缺页时调出一页刚换出的页很快又被访问需重新调入频繁换页使系统大部分时间耗在换进换出上几乎不能完成有效工作。成因是 CPU 利用率与多道程序度的矛盾提高多道程序度本为提高利用率却造成缺页率急剧上升、利用率下降调度程序又继续提高多道程序度形成恶性循环。5. 设备管理I/O 控制方式、缓冲与 SPOOLing5.1 三种通道与瓶颈破解字节多路通道含许多非分配型子通道连接低中速设备子通道按时间片轮转共享主通道按字节传送一个子通道交换完一个字节立即让出主通道给下一个数组选择通道只含一个分配型子通道一段时间只能执行一道通道程序、控制一台设备按数组传送被占用后一直独占直到传完利用率低主要用于多台高速设备数组多路通道结合两者优点含多个非分配型子通道连接高中速设备按时间片轮转共享主通道、按数组传送既有高速率又有满意的通道利用率。通道不足造成的瓶颈最有效的解法是增加设备到主机间的通路而不是增加通道即一个设备连多个控制器、一个控制器连多个通道。多通路不仅解决瓶颈还提高可靠性个别通道或控制器故障不会让设备与存储器之间无法建立通路。5.2 I/O 控制方式的演进与适用场合推动 I/O 控制发展的因素有三尽量减少 CPU 对 I/O 控制的干预把 CPU 从繁杂控制中解脱出来做数据处理缓和 CPU 高速性与设备低速性的矛盾提高利用率和吞吐量提高 CPU 与 I/O 设备的并行程度。四种控制方式及适用场合程序 I/O 方式适用于早期无中断的计算机系统中断驱动方式普遍用于现代计算机系统DMA 方式适用于块设备与主机交换数据I/O 通道方式适用于一组数据块的交换但要求系统配置相应通道及通道控制器。5.3 单缓冲与双缓冲的时间公式单缓冲下磁盘把一块数据输入缓冲区时间为 TOS 把缓冲区数据传到用户区为 MCPU 计算为 C。设备输入与 CPU 处理可并行所以每块数据处理时间为 max(C,T)M。双缓冲下设备输入与 CPU 处理并行、设备输入与数据传送也并行耗时约为 max(CM,T)因 M 是内存内搬移、非常短暂可省略近似为 max(C,T)。这两个公式要能解释为什么而不是只背结果。5.4 设备独立性与 SPOOLing 虚拟设备引入设备独立性使应用程序独立于具体物理设备设备分配更灵活也容易实现 I/O 重定向。实现的关键是在设备驱动程序之上设一层设备独立性软件执行所有 I/O 设备的公用操作并向用户层提供统一接口系统中设置逻辑设备表 LUT 完成逻辑设备到物理设备的映射表目含逻辑设备名、物理设备名、驱动程序入口地址三项。分配独占设备的步骤是一条链进程以逻辑设备名请求查 LUT 得物理设备类型指针检索系统设备表找空闲且安全可用的设备控制表再依次检查控制器控制表、通道控制表是否忙碌忙则挂等待队列三者都分配成功才算成功然后启动设备传送。虚拟设备是通过虚拟技术把一台独占设备变换成若干台逻辑设备供多个进程同时使用实现依赖的关键技术是 SPOOLing。后台打印时输出进程在输出井中申请空闲盘块区存放待打印数据这是 SPOOLing 系统为请求 I/O 进程提供服务的起点后续再由输出进程按队列实际打印。6. 查漏补缺一份可执行的复习清单复习到这一步最怕的不是不会而是以为会了。我的做法是把五章压成一张自测表每行一个必答点能不看书画出关键词才算过。下面这张表按章排列右列是我自己踩过的坑你可以直接拿去对照。章节必答点常见翻车处引论OS 四大特征、最基本与最重要之分把最基本答成最重要引论分时与实时三线对比及时性衡量标准混用进程PCB 为何是唯一标志只答记录信息不答系统据此感知进程进程三态转换双向原因阻塞到就绪写成被调度进程wait/signal 物理含义忘记 value≤0 时唤醒进程生产者消费者改错wait 互换与 signal 互换混为一谈调度三级调度任务高级调度对象写成进程死锁四条件与三种预防途径预防与避免策略张冠李戴死锁银行家算法安全序列试分配后忘检查 Available内存分页分段三维区别地址空间维数答反内存FIFO 缺页与 Belady块数增加就认定缺页必减内存虚拟存储最本质/最重要特征离散性与虚拟性互换设备单双缓冲时间公式只背公式不解释并行关系设备独占设备分配六步漏掉通道检查具体怎么用这张表第一遍合上书对每行口述 30 秒卡壳的做记号第二遍只攻记号行回到对应章节把那段答案的因果链重新推一遍而不是重读第三遍挑计算题——前趋图信号量、银行家算法、FIFO 缺页——各手写一遍写的时候强制标出每一步的参数含义。计算题是操作系统的黑匣子光看答案觉得顺自己动笔就露馅这是血泪经验。还有一个容易被忽略的动作把每道简答题的答案压缩成结论 一句理由。比如最基本特征是并发和共享因为多道程序环境下两者互为存在条件考场上先写结论再补理由比整段背诵更抗紧张。前趋图和信号量题则相反必须完整写出 wait/signal 序列少一个就扣分没有后悔药。从那以后我每次复习操作系统都强制走一遍合书口述—标记卡壳—手写计算—压缩结论这四步哪怕时间只够走一遍也比通读三遍答案踏实。希望帮到你。本文还有配套的精品资源点击获取
