三级调度对比

提示：高级调度决定“谁调入内存”，中级调度决定“谁在内/外存间对换”，低级调度决定“谁上 CPU 运行”。

调度的两种基本方式

• 非抢占式（非剥夺式）：一旦进程获得 CPU 就一直运行到结束或主动放弃，不允许被抢占。实现简单，适合批处理。
• 抢占式（剥夺式）：可根据时间片或优先级强制剥夺当前进程的 CPU。有利于提高响应速度，适合分时/实时系统，但开销大。

① FCFS 先来先服务

原理：按作业/进程到达的先后顺序进行调度，先到先服务。属于非抢占式算法。

优点：实现简单、公平；对长作业有利。

缺点：平均等待时间往往较长；存在护航效应（convoy effect）——一个长作业会使其后到达的短作业长时间等待；对 I/O 繁忙型作业不利。

适用：批处理系统；也常用于打印机等设备分配。

② SJF 短作业（进程）优先

原理：选择要求服务时间（运行时间）最短的作业/进程投入运行。可分非抢占式 SJF 与抢占式 SJF（SRTF，最短剩余时间优先）：抢占式下，每当新进程到达时比较剩余时间，若新进程剩余时间更短则抢占。

优点：可获得最短的平均等待/周转时间（理论最优）。

缺点：必须预知运行时间（实际难以做到）；对长作业不利，可能产生饥饿；未考虑紧迫程度。

示例（非抢占式 SJF）：5 个作业 A~E，到达时间与运行时间如下，求周转时间。

说明：时刻 0 只有 A 到达，先执行 A；A 完成(时刻4)时，就绪队列有 B(3)、C(5)、D(2)、E(4)，选最短的 D(2)，以此类推。

对比：同一组数据用 FCFS 调度顺序为 A→B→C→D→E，平均周转时间 = 9、平均带权周转时间 = 2.8，可见 SJF 更优。

③ HRRN 高响应比优先

原理：每次调度时计算各就绪作业的响应比，选择响应比最高者投入运行。属于非抢占式算法。

特点：等待越久响应比越高（照顾长作业，避免饥饿），服务时间越短响应比也越高（照顾短作业），兼顾长短作业、无饥饿，是 FCFS 与 SJF 的折中。但每次调度都要重新计算响应比，开销较大。

示例：4 个作业，到达时间与 CPU 时间如下。

④ 优先级调度

原理：为每个进程设置优先级，调度时选择优先级最高（数值通常最小）的进程。可分为抢占式与非抢占式。

• 静态优先级：进程创建时确定，运行期间不变。优点是简单、开销小；缺点是可能产生饥饿，低优先级进程长期得不到调度。
• 动态优先级：运行期间优先级可变（如随等待时间增加而提高，随占用 CPU 时间增加而降低）。更灵活、可防止饥饿，但开销大。

⑤ 时间片轮转 RR

原理：将 CPU 处理时间划分为一个个时间片（q），就绪进程按 FCFS 排成队列。进程获得 CPU 后运行一个时间片，若未完成则被抢占并插入就绪队列末尾，循环执行。

特点：公平、响应快，适合分时/交互式系统。

时间片大小选择：

• q 过大 → 退化为 FCFS；
• q 过小 → 上下文切换频繁，系统开销过大；
• 通常 q 略大于一次典型交互所需时间，使大多数交互进程在一个时间片内完成。

⑥ 多级反馈队列调度 MFQ

原理：设置多个就绪队列，优先级从高到低排列，而各队列时间片从短到长（如第 1 级 q=1，第 2 级 q=2，第 3 级 q=4……）。

• 新作业进入最高优先级队列队尾；
• 进程用完当前队列的时间片仍未完成，则降级到下一级队列末尾；
• 进程主动放弃 CPU（如等 I/O），则留在原队列或升级；
• 仅当高优先级队列为空时，才调度低优先级队列；高优先级队列有进程到达时可抢占低优先级队列中正在运行的进程。

优点：短作业/交互型作业优先完成，长作业自动降级，兼顾响应时间与吞吐量，自适应性好，是目前公认较好的调度算法。

缺点：实现复杂；存在饥饿可能（若高优先级队列总有新进程到来）。

调度算法对比总结

• 内存分配与回收：为程序分配内存空间，使用完毕后回收。
• 地址转换（重定位）：将逻辑地址转换为物理地址。
• 存储保护：保证各作业在自己的内存空间运行，互不干扰。
• 存储扩充：借助虚拟存储技术，从逻辑上扩充内存容量。

地址重定位（地址映射）是把程序的逻辑地址（相对地址）转换为物理地址（绝对地址）的过程。

固定分区分配

将内存预先划分为若干个固定大小的分区，每个分区装入一道作业。

优点：实现简单；支持多道程序。

缺点：分区大小固定，会产生内部碎片（作业小于分区时浪费）；大作业可能放不下；限制了并发作业数。

动态分区分配

根据作业的实际需要，动态地划分内存分区。分区大小与作业大小一致，无内部碎片，有外部碎片。常用分配算法：

碎片问题

基本概念

• 页（页面）：将进程的逻辑地址空间划分为大小相等的离散单元，页大小由硬件决定，等长。
• 帧（物理块）：将内存物理空间划分为与页大小相同的块。
• 页表：记录逻辑页号 → 物理块号映射关系的表，实现从页号到块号的地址映像。
• 页表寄存器 PTR：存放页表始址和页表长度，用于地址转换和越界检查。

分页管理中作业地址空间是一维的，页的长度等长。每存取一个数据需访问两次内存（一次查页表，一次取数据）。

地址转换公式

转换步骤：① 用逻辑地址求出页号 P 和页内偏移 d；② 用 P 与页表长度比较，若 P ≥ 页表长度则越界中断；③ 查页表得块号；④ 块号 × 页大小 + 偏移 = 物理地址。

地址转换示例

设页面大小为 1024B，页表为 {0→2, 1→3, 2→1, 3→6}（即页表长度 4，有效页号 0~3）。将逻辑地址 1011、2148、5012 转换为物理地址。

快表 TLB

快表（TLB，Translation Lookaside Buffer）是一个具有并行查找能力的高速缓存（小容量联想寄存器），用于存放当前访问过的页表项，以加速地址转换过程。

作用：避免每次访存都先查内存中的页表，把“两次访存”降为可能一次访存，大幅提高有效访问速度。

工作过程：先查快表，若命中（页表项在快表中）则直接得到块号、计算物理地址；若未命中则查内存页表，并将该页表项写入快表。

基本概念

按程序的逻辑结构（如主程序、子程序、数据段等）划分为若干段，每段是一组有意义的信息，段长不等。段表记录每段的段号、段长（段限）和内存始址（基址）。分段地址空间是二维的，地址由 (段号, 段内偏移) 给出。

地址转换公式

转换步骤：① 用段号 S 与段表长度比较，若 S ≥ 段表长度则越界中断；② 查段表得该段基址和段长 L；③ 若段内偏移 d ≥ 段长 L，则越界中断；④ 否则物理地址 = 基址 + d。

地址转换示例

设段表如下（段号 → 基址/段长）：

转换逻辑地址 (2, 88) 与 (4, 100)：

虚拟存储器是指具有请求调入和置换功能，能从逻辑上对内存容量进行扩充的存储器系统。它通过把内存和外存统一管理，为用户提供了比实际物理内存大得多的地址空间。

三大特征：

• 多次性：一个作业被分为多段，分多次调入内存运行（而非一次全部装入）。
• 对换性：运行过程中内存中的数据可与外存上的数据换入/换出。
• 虚拟性：从逻辑上扩充内存，可用空间远大于物理内存。

页表项与缺页中断

请求分页的页表项在基本分页基础上增加了若干字段：

• 状态位（存在位）：标识该页是否在内存中。
• 访问位（引用位）：记录该页最近是否被访问，供置换算法使用。
• 修改位：记录该页是否被修改过，决定换出时是否写回外存。
• 外存地址：该页在外存上的位置。

缺页中断：当访问的页不在内存时（状态位为 0），产生缺页中断，由操作系统将该页从外存调入内存；若内存已满则需用置换算法淘汰一页。

请求分页需要的三项基础：① 页表机制；② 缺页中断机构；③ 地址变换机构。

① OPT 最佳置换

定义：选择未来最长时间内不再被访问的页面进行淘汰。这是理论上的最优算法，缺页率最低。

特点：缺页率最低，作为其他算法的衡量标准；但需要预知未来的页面访问情况，无法实现，仅用于理论分析。

示例（3 个物理块）：

关键置换决策：访问 2 时淘汰 7（7 在第 18 步才再用）；访问 3 时淘汰 1（1 在第 14 步才再用）；访问 4 时淘汰 0；访问 0 时淘汰 4（4 不再使用）；访问 1 时淘汰 3（不再使用）；访问 7 时淘汰 2（不再使用）。

② FIFO 先进先出

定义：选择最早进入内存的页面淘汰（按进入内存的先后顺序，先进先出）。实现简单，可用队列（移位寄存器）实现。

特点：最简单；但性能差，且会产生 Belady 异常。

示例（同一引用串，3 个物理块）：

③ LRU 最近最久未使用

定义：选择最近最长时间未被访问的页面淘汰。性能接近 OPT，但实现开销大（需硬件支持记录访问时间，可用栈或计数器实现）。

特点：性能好，是常用的优秀算法；LRU 属于栈式算法，不会产生 Belady 异常。

示例（同一引用串，3 个物理块）：

④ Clock / NRU 简单时钟置换

定义：LRU 的近似算法。为每页设置一个访问位（使用位），把内存中的页面链接成循环队列，配一个循环指针。

机制：

• 页面装入或被访问时，访问位置 1；
• 需淘汰页面时，指针顺时针扫描循环队列：若访问位 = 1，则清 0 并跳过；若访问位 = 0，则淘汰该页；
• 最坏情况下指针需扫描一圈（把所有访问位清 0），再淘汰遇到的第一个页面。

示例：引用串 2 3 2 1 5 2 4 5 3 2 5 2，3 个物理块。

定义：在采用某种置换算法时，分配的物理块数增加，缺页次数反而增加的现象。

（上表中 OPT/LRU/FIFO 的缺页、置换次数为同一引用串、3 个物理块下的计算结果。）

设 λ 为查快表时间，t 为访问一次内存的时间，ε 为缺页中断处理时间。则有效访问时间 EAT 分三种情况：

文件：指具有标识符（文件名）的一组相关信息的集合，是文件系统中最大的数据单位。

数据组织层次：数据项 → 记录 → 文件 → 文件系统。其中数据项是最小逻辑单位，记录是一组相关数据项的集合。

文件分类：

有结构文件按记录的组织方式分为以下逻辑结构：

FCB（File Control Block，文件控制块）是用于描述和控制文件的数据结构，是文件存在的标志（类似 PCB 之于进程）。FCB 的有序集合构成文件目录（目录项即 FCB）。

FCB 包含三类信息：

• 基本信息：文件名、物理位置、逻辑结构、物理结构等。
• 存取控制信息：文件主、权限（读/写/执行）、访问属性等。
• 使用信息：建立时间、修改时间、访问时间、当前使用状态等。

① 单级目录

整个系统只设置一张目录表，每个文件占一个目录项。

优点：简单，能实现按名存取。

缺点：查找速度慢；不允许文件重名；不便于文件共享。

② 两级目录

分为主文件目录 MFD（记录各用户名及对应用户文件目录位置）和用户文件目录 UFD（记录该用户的文件）。

优点：查找较快；允许不同用户文件重名；提高了安全性（用户间隔离）。

缺点：灵活性低；用户之间共享文件不便。

③ 树形目录

采用层次结构，目录可以包含文件和子目录，是目前广泛使用的目录结构。

• 当前目录（工作目录）：进程当前所在的目录，便于相对路径访问。
• 绝对路径：从根目录开始的完整路径（如 /home/user/file.txt）。
• 相对路径：从当前目录开始的路径（如 ../doc/file.txt）。

优点：层次清晰，便于分类管理；允许重名（不同目录下）；便于共享与保护。

目录查询技术

• 线性检索法：顺序扫描目录项进行比较，实现简单但效率低。
• Hash 方法：对文件名进行 Hash 得到目录项位置，平均 O(1) 查找，效率高；需处理冲突。

① 连续分配

为每个文件分配一组连续的磁盘盘块。

优点：顺序存取速度快；实现简单；支持随机访问（直接定位）。

缺点：产生外部碎片；需预先知道文件大小；文件不能动态增长；删除后产生碎片。

② 链接分配

每个文件对应一个盘块链表，盘块可以离散分配。

• 隐式链接：每个盘块中存放指向下一盘块的指针。
  优点：无外部碎片，空间利用率高。
  缺点：只能顺序存取，随机访问效率低；可靠性差（指针丢失导致链断裂）；指针占空间。
• 显式链接（FAT，文件分配表）：将所有盘块的链接指针集中存放在一张 FAT 表中（常驻内存）。
  优点：支持随机访问（在内存中查 FAT）；空间利用率高。
  缺点：FAT 表占用内存空间。

③ 索引分配

为每个文件建立一张索引表，索引表记录文件各逻辑块对应的物理盘块号。

• 单级索引：每个文件一张索引表。优点：支持随机访问。缺点：索引表占空间，大文件需要多块索引。
• 多级索引：为索引表再建索引，适合大文件，空间利用高效，但查找层次多。
• 增量式（混合）索引：结合直接索引 + 一级索引 + 二级索引 + 三级索引（如 UNIX inode），小文件直接索引即可，大文件动态扩展，兼顾效率与空间。

优点：支持随机访问，文件可动态增长，空间利用率高。缺点：索引表本身占额外空间，开销较大。

用于管理磁盘上的空闲盘块，主要有四种方法：

本章概览

设备管理是操作系统的重要功能之一，负责管理和控制各类 I/O 设备，完成用户提出的 I/O 请求、加快 I/O 速度、方便设备使用。核心内容包括：I/O 设备分类、I/O 控制方式、缓冲技术、SPOOLing 技术、设备分配与中断处理。

引入缓冲的目的

• 缓和 CPU 与 I/O 设备之间速度不匹配的矛盾
• 减少对 CPU 的中断频率，放宽对中断响应时间的限制
• 提高 CPU 与 I/O 设备之间的并行程度

什么是 SPOOLing

SPOOLing（Simultaneous Peripheral Operations On-Line，外部设备联机并行操作）又称假脱机技术。它利用高速磁盘模拟脱机 I/O，把独占设备改造为共享设备，从而实现虚拟设备。

核心思想：用一道程序模拟脱机输入/输出，使慢速 I/O 设备与 CPU 并行工作。

打印机是典型的独占设备，通过 SPOOLing 可改造为共享设备：

1. 用户进程请求打印时，不立即把打印机分配给该进程，而是由 SPOOLing 的输出进程 申请空闲磁盘块（输出井），将打印数据送入其中。
2. 为该用户进程申请一张空白的用户请求打印表，填入打印要求，将其挂到请求打印队列末尾。
3. 用户进程的打印请求完成，可继续执行其他任务（对用户而言"打印已完成"）。
4. 当打印机空闲时，输出进程 SO 从请求打印队列队首取一张表，按其中要求从输出井取出数据送到打印机进行真正的物理打印。

概念

设备独立性（Device Independence）指应用程序独立于具体使用的物理设备，即用户程序中使用逻辑设备名，由系统将其映射为物理设备名。

• 逻辑设备名：用户程序中使用的、与具体设备无关的名称（如 /dev/printer）。
• 物理设备名：系统中实际设备的唯一标识。
• 优点：提高程序可适应性，便于 I/O 重定向；设备故障时可用其他设备替代。

1. 唤醒被阻塞的驱动（I/O）程序进程：把等待该 I/O 完成的进程从阻塞队列移出，置为就绪态。
2. 保护被中断进程的现场：保存 CPU 寄存器、程序状态字（PSW）等到被中断进程的 PCB 中，以便将来恢复。
3. 分析中断原因，转入相应的设备中断处理程序：根据中断向量找到对应的中断处理程序入口。
4. 进行中断处理：执行具体的中断处理程序，完成数据传送或错误处理。
5. 恢复被中断进程的现场：从 PCB 中恢复现场，返回被中断的程序继续执行。

本章概览

磁盘是现代计算机中最重要的共享 I/O 设备，磁盘管理的核心是磁盘调度算法（决定服务请求的顺序以减少寻道时间）。本章重点掌握 5 种调度算法的计算。

• 盘片（Platter）：磁盘的物理载体，两面涂有磁性材料。
• 磁道（Track）：盘片上一个面上的同心圆环，是磁头读写的基本轨迹。
• 柱面（Cylinder）：所有盘面上同一半径的磁道组成的圆柱面。柱面号即磁道号。
• 扇区（Sector）：磁道被划分为若干弧段，每个扇区是磁盘读写的最小物理单位（通常 512B）。

例题（旋转延迟计算）

若磁盘转速为 5400 转/分，平均寻道时间为 8ms，每个磁道包含 1000 个扇区，求访问一个扇区的平均存取时间。

解：转速 5400 转/分 = 90 转/秒，旋转一周 = 1000/90 ≈ 11.11ms

平均旋转延迟 = 11.11 / 2 ≈ 5.56ms

传输一个扇区时间 = 11.11 / 1000 ≈ 0.011ms

平均存取时间 = 8 + 5.56 + 0.011 ≈ 13.57ms

统一示例条件

假设磁盘有 200 个磁道（编号 0~199），磁头当前位置 149，请求队列（按到达顺序）为：

88, 147, 95, 177, 94, 150, 102, 175, 138

（无特殊说明时，SCAN/C-SCAN 默认磁头当前向磁道号增大方向移动。）

原理：按请求到达的先后顺序服务，最简单最公平。

服务顺序：149 → 88 → 147 → 95 → 177 → 94 → 150 → 102 → 175 → 138

计算：|149-88|+|88-147|+|147-95|+|95-177|+|177-94|+|94-150|+|150-102|+|102-175|+|175-138|

= 61+59+52+82+83+56+48+73+37 = 551

平均寻道长度：551 / 9 ≈ 61.2

原理：每次选择与当前磁头位置距离最近的请求服务。是贪心算法。

服务顺序：149 → 150 → 147 → 138 → 102 → 95 → 94 → 88 → 175 → 177

计算：1+3+9+36+7+1+6+87+2 = 152

平均寻道长度：152 / 9 ≈ 16.9

原理：磁头沿当前方向移动，服务沿途所有请求，到达该方向最远请求（或磁盘边界）后反向移动，继续服务。

服务顺序：149 → 150 → 175 → 177 →（转向）→ 147 → 138 → 102 → 95 → 94 → 88

计算：1+25+2+30+9+36+7+1+6 = 117

平均寻道长度：117 / 9 ≈ 13.0

方向判断例题（来自样卷）

磁盘有 200 个柱面（0~199），当前存储臂在 134 号柱面，刚刚完成 152 号柱面的服务请求。请求队列为：68, 174, 91, 137, 94, 152, 102, 157, 120。求 SCAN 算法的磁道移动总和。

方向判断：134 < 152，磁头从 152 移到 134，向小方向扫描。

服务顺序：134 → 120 → 102 → 94 → 91 → 68 →（到底端 0 后转向）→ 137 → 152 → 157 → 174

计算：14+18+8+3+23+68+137+15+5+17 = 308

原理：磁头沿一个方向移动服务沿途请求，到达磁盘边界（端点 0 或 199）后，直接跳回另一端，沿同方向继续服务。提供更均匀的等待时间。

服务顺序：149 → 150 → 175 → 177 →（走到 199 后跳回 0）→ 88 → 94 → 95 → 102 → 138 → 147

计算：1+25+2+(177→199→0：22+199)+(0→88：88)+6+1+7+36+9 = 352

平均寻道长度：352 / 9 ≈ 39.1

原理：与 C-SCAN 类似，但到达方向上最后一个请求后立即返回另一端的第一个请求（不走到磁盘端点）。

服务顺序：149 → 150 → 175 → 177 →（返回到 88）→ 94 → 95 → 102 → 138 → 147

计算：1+25+2+89+6+1+7+36+9 = 176

平均寻道长度：176 / 9 ≈ 19.6

本章概览

实时系统要求在规定时限内对外部事件作出响应。实时调度的核心是保证任务在截止时间（Deadline）前完成，主要算法有 EDF（最早截止时间优先）和 LLF（最低松弛度优先）。

原理

EDF（Earliest Deadline First）根据任务的截止时间确定优先级：截止时间越早，优先级越高。

• 可用于抢占式和非抢占式调度。
• 主要用于非周期性实时任务，也可用于周期任务。
• 当任务可调度时，EDF 能使 CPU 利用率达到理论最大（100%）。

原理

LLF（Least Laxity First）根据任务的松弛度（Laxity）确定优先级：松弛度越低，优先级越高（越紧急）。主要用于可抢占调度。

例题条件

有两个周期性实时任务：

• 任务 A：周期 20ms，执行时间 10ms（到达时刻 0，截止时刻 20）
• 任务 B：周期 50ms，执行时间 25ms（到达时刻 0，截止时刻 50）

两任务在 t=0 同时到达，采用 LLF（可抢占）调度，求 0~50ms 的调度过程。

松弛度计算与调度决策表

松弛度 = 本周期截止时间 − 本周期还需运行时间 − 当前时间

调度时序（甘特图）

|  A(0-10)  | B(10-20) | A(20-30) | B(30-35) |空闲(35-40)| A(40-50) | B(50-...) |
0           10         20         30         35          40         50

定义

优先级倒置是指高优先级进程被低优先级进程延迟或阻塞的现象。当低优先级进程持有高优先级进程所需资源时，若又有中等优先级进程抢占低优先级进程，会导致高优先级进程被中等优先级进程间接地长时间阻塞。

示例过程

设有三个进程，优先级 P1（高）> P2（中）> P3（低）：

1. P3 先运行，获得资源 R（如临界资源）。
2. P1 就绪，因优先级高抢占 P3 运行。
3. P1 运行中需要资源 R，但 R 被 P3 占用，P1 阻塞，等待 P3 释放 R。
4. 此时 P2 就绪，P2 优先级高于 P3，P2 抢占 P3 运行。
5. 结果：高优先级的 P1 反而被中优先级的 P2 长时间阻塞——P3 无法运行、无法释放 R，P1 持续等待。

解决方法：优先级继承（Priority Inheritance）

动态优先级继承：当高优先级进程阻塞等待低优先级进程所占资源时，低优先级进程临时继承高优先级进程的优先级，使中等优先级进程无法抢占它，从而尽快运行完毕释放资源，再恢复原优先级。

上述示例中，P1 阻塞后，P3 继承 P1 的高优先级，P2 无法抢占 P3，P3 迅速释放 R，P1 得以继续，避免了倒置。

本章概览

本章汇总 8 个必考大题类型，每个题型给出解题步骤、核心公式和关键注意事项，是备考重点。

解题步骤

1. 根据调度算法确定作业执行顺序。
2. 逐个作业计算：开始时间、完成时间。
3. 套公式计算周转时间、带权周转时间。
4. 求平均值。

三种算法选择规则

• FCFS：按到达顺序，先到先服务。
• SJF：从就绪作业中选服务时间最短的先执行（非抢占式）。
• HRRN（最高响应比优先）：每次调度时计算所有就绪作业响应比，选响应比最高的执行。

解题步骤

1. 确定临界资源，设互斥信号量 mutex（初值 1）。
2. 确定同步关系，设同步信号量（初值通常为可用资源数，如空缓冲区、满缓冲区）。
3. 在临界区前后配对使用 P/V：P(申请资源)在前，V(释放资源)在后。
4. 多个 P 操作时，先做同步 P，再做互斥 P，避免死锁。

生产者—消费者问题（经典代码）

semaphore mutex = 1;   // 互斥访问缓冲区
semaphore empty  = n;   // 空缓冲区数
semaphore full   = 0;   // 满缓冲区数

生产者:
  while(1) {
    生产一个产品;
    P(empty);     // 申请空位(同步P)
    P(mutex);     // 互斥进入临界区
    把产品放入缓冲区;
    V(mutex);     // 释放临界区
    V(full);      // 增加满位(通知消费者)
  }

消费者:
  while(1) {
    P(full);      // 申请产品(同步P)
    P(mutex);     // 互斥进入临界区
    从缓冲区取出产品;
    V(mutex);     // 释放临界区
    V(empty);     // 增加空位(通知生产者)
    消费产品;
  }

两个流程

流程一：安全性检查（判断当前状态是否安全）

1. 初始化 Work = Available；Finish[i] = false（对所有 i）。
2. 找一个 Finish[i]=false 且 Need[i] ≤ Work 的进程 i（逐分量比较）。
3. 若找到，则 Work = Work + Allocation[i]，Finish[i]=true，回到步骤 2。
4. 若所有 Finish[i]=true，则安全（存在安全序列）；否则不安全。

流程二：资源请求分配（进程 Pi 请求 Request[i]）

1. 若 Request[i] ≤ Need[i]，继续；否则出错（请求超过最大需求）。
2. 若 Request[i] ≤ Available，继续；否则 Pi 必须等待（资源不足）。
3. 试分配：Available = Available − Request[i]；Allocation[i] += Request[i]；Need[i] −= Request[i]。
4. 执行安全性检查：若安全，则正式分配；否则回滚（恢复原值），Pi 等待。

示例（5 进程 4 资源类型）

系统有 4 种资源 A、B、C、D，总量 Total=(6,9,8,8)。各进程当前 Allocation、Max 如下：

计算 Available = Total − ΣAllocation = (6,9,8,8) − (3,4,3,3) = (3,5,5,5)

安全性检查过程

Work = Available = (3,5,5,5)

存在安全序列 P0 → P1 → P2 → P3 → P4，系统处于安全状态。

资源请求示例

若 P1 提出请求 Request1 = (1,1,1,0)：

1. Request1 ≤ Need1？(1,1,1,0) ≤ (1,1,1,2) ✓
2. Request1 ≤ Available？(1,1,1,0) ≤ (3,5,5,5) ✓
3. 试分配：Available=(2,4,4,5)，Allocation1=(2,2,2,0)，Need1=(0,0,0,2)
4. 安全性检查：Work=(2,4,4,5) → P0✓→P1✓→P2✓→P3✓→P4✓，安全序列存在。

结论：可以满足 P1 的请求，正式分配。

解题步骤

1. 由逻辑地址求页号和页内偏移。
2. 判断是否越界：页号 ≥ 页表长度则越界（缺页中断/地址错误）。
3. 查页表，由页号得到物理块号。
4. 计算物理地址。

示例

分页系统，页面大小 4KB，页表：第 0、1、2 页依次存放在物理块 5H、AH、BH 中。逻辑地址为 1E6BH，求物理地址。

解：页面大小 4KB = 1000H。逻辑地址 1E6BH。

页号 = INT(1E6BH / 1000H) = 1H（高位部分）

页内偏移 = 1E6BH mod 1000H = E6BH（低位部分）

页号 1 → 物理块号 AH。物理地址 = AH × 1000H + E6BH = A000H + E6BH = AE6BH

解题步骤

1. 由逻辑地址拆分出段号和段内偏移。
2. 段号越界检查：若段号 ≥ 段表长度，则越界（地址错误）。
3. 查段表，得到该段的基地址和段长。
4. 段内偏移越界检查：若段内偏移 ≥ 段长，则越界（地址错误）。
5. 计算物理地址。

示例

段表如下：

逻辑地址 <0, 430>：段号 0 < 5 ✓；偏移 430 < 500 ✓；物理地址 = 210 + 430 = 640

逻辑地址 <3, 1400>：段号 3 < 5 ✓；偏移 1400 < 590？否，越界，地址错误

解题步骤

1. 按访问串依次处理，维护当前驻留页帧集合。
2. 每访问一页：若在内存中则命中；不在则缺页，按算法选淘汰页。
3. 记录每次缺页，最后统计缺页次数和缺页率。

四种算法淘汰规则

• OPT（最佳置换）：淘汰未来最长时间不被使用的页（理论最优，不可实现，用于评价基准）。
• FIFO（先进先出）：淘汰最先进入内存的页（按进入时间排队）。
• LRU（最近最久未用）：淘汰最长时间未被访问的页（按上次访问时间）。
• Clock（时钟/NRU）：循环扫描各页的访问位，访问位为 0 则淘汰，为 1 则置 0 并跳过。

示例

页面访问串：7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1（共 20 次访问），分配 3 个页帧。

Clock 算法是 LRU 的近似实现，缺页次数介于 LRU 与 FIFO 之间。

解题步骤

1. 确定磁头当前位置和移动方向（由"刚完成对 X 的服务"判断）。
2. 按算法确定服务顺序。
3. 计算每步移动距离（相邻磁道号差的绝对值），求总移动距离。
4. 总移动距离 / 请求数 = 平均寻道长度。

解题步骤

1. 列出各任务的截止时间、还需运行时间、当前时间。
2. EDF：选截止时间最早的任务运行。
3. LLF：计算各任务松弛度，选松弛度最低的任务运行。
4. 若可抢占，每个时刻重新比较优先级（松弛度/截止时间）。

本章概览

本章以紧凑列表/表格形式汇总最高频考点，适合考前快速回顾。

• PCB 是进程存在的唯一标志，每个进程有且仅有唯一的 PCB，由 OS 创建管理，用户不能创建/删除。
• 进程是资源分配的基本单位；线程是 CPU 调度的基本单位。
• 进程撤销时不止释放 PCB，还需释放占用的所有资源（内存、打开文件等）。

• 四个条件必须同时满足才会死锁；破坏任一即可预防。
• 互斥条件无法破坏（如打印机本质互斥）。
• 死锁与推进顺序、资源分配策略有关，与进程数量无必然关系。
• 饥饿可以只有 1 个进程，而死锁至少 2 个进程。
• 安全状态一定无死锁；不安全状态可能死锁（不一定）。

同一访问串（7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1，3 页帧）：

OPT(9) < LRU(12) < Clock < FIFO(15)

• OPT 最优不可实现，LRU 接近 OPT（常用），FIFO 最差。
• Belady 异常只有 FIFO 有（增加页帧缺页反增）。
• 缺页率 = 缺页次数 / 总访问次数。

• 总移动距离：FCFS=551 > C-SCAN=352 > C-LOOK=176 > SSTF=152 > SCAN=117。
• SSTF 可能饥饿；SCAN/C-SCAN/C-LOOK 不会。
• SCAN 到最远请求转向；C-SCAN 到磁盘端点返回；C-LOOK 到最远请求返回。
• 方向判断：看"当前位置 vs 刚完成位置"。

1. 提高 I/O 速度（低速设备 I/O → 高速磁盘存取）。
2. 将独占设备改造为共享设备。
3. 实现虚拟设备功能。

组成：输入井/输出井（磁盘）+ 输入/输出缓冲区（内存）+ 输入进程 SI/输出进程 SO。

切换由以下事件引起（会导致从用户态进入核心态）：

• 系统调用（程序接口，用户主动请求 OS 服务）
• 中断（I/O 中断、时钟中断等硬件中断）
• 异常（缺页中断、除零、地址越界等）

本章概览

汇总操作系统全课程核心公式，便于考前快速查阅。

本章概览

从练习 HTML、样卷 2/3 中精选高频选择题、判断题与计算题，每题附答案与解析，覆盖操作系统各章节。

第 1 题【操作系统概念】

计算机的操作系统是一种 ____。

A、系统软件　B、应用软件　C、工具软件　D、字表处理软件

答案：A

解析：操作系统是管理计算机硬件与软件资源的系统软件，不是应用软件。应用软件在操作系统之上运行。

第 2 题【多道程序】

在现代操作系统中引入了 ____，从而使并发和共享成为可能。

A、单道程序　B、磁盘　C、对象　D、多道程序

答案：D

解析：多道程序设计使多个程序同时驻留内存交替执行，从而实现并发和共享。单道程序无法实现并发。

第 3 题【进程与 PCB】

进程控制块是描述进程状态和特性的数据结构，一个进程 ____。

A、可以有多个 PCB　B、可与其他进程共用一个 PCB　C、可以没有 PCB　D、只能有唯一的 PCB

答案：D

解析：每个进程有且仅有唯一的 PCB，PCB 是进程存在的唯一标志，由 OS 创建管理。

第 4 题【进程状态转换】

一个正在 CPU 上运行的进程，其进程状态 ____。

A、只能转变为阻塞状态　B、可以转变为就绪状态也可以转变为阻塞状态　C、只能转变为就绪状态　D、可以转变为就绪状态也可以转变为执行状态

答案：B

解析：运行态进程可因时间片用完转为就绪态，也可因等待事件转为阻塞态。

第 5 题【进程自身决定】

进程自身决定 ____。

A、从运行态到阻塞态　B、从就绪态到运行态　C、从运行态到就绪态　D、从阻塞态到就绪态

答案：A

解析：只有"运行→阻塞"是进程自身决定的（主动请求 I/O）；其余转换由调度程序或外部事件决定。

第 6 题【PV 操作】

关于 PV 操作，以下说法不正确的是 ____。

A、P(S) 操作意味着申请一份关于信号量 S 的资源
B、V(S) 操作意味着释放一份关于信号量 S 的资源
C、进程调用一个 V(S) 操作，将信号量的值加 1 后，信号量的值小于 0，则应从信号量的等待队列中唤醒一个进程
D、进程调用一个 P(S) 操作，将信号量的值减 1 后，信号量的值小于 0，则进程应阻塞，进入等待队列

答案：C

解析：V 操作是先加 1 再判断，加 1 后若值≤ 0（不是 < 0）才唤醒一个进程。C 中"小于 0"表述错误。

第 7 题【信号量】

当某一信号量的值为 2 时，说明 ____。

A、有 2 个该信号量的资源实例可分配　B、在该信号量的队列中有两个进程　C、有两个进程由于申请相应资源而被阻塞　D、系统中有两个并发执行的进程

答案：A

解析：信号量值 > 0 时表示可用资源数；< 0 时其绝对值表示等待进程数。

第 8 题【死锁】

在多进程的并发系统中，肯定不会因竞争 ____ 而产生死锁。

A、打印机　B、磁带机　C、磁盘　D、CPU

答案：D（磁盘/磁盘等共享设备也可，此处 CPU 为经典答案）

解析：CPU 和磁盘等可剥夺/共享资源不会因竞争而死锁。打印机、磁带机等独占设备可能死锁。

第 9 题【死锁原因】

操作系统讨论的死锁是与 ____ 有关。

A、进程申请的资源不存在　B、进程并发执行的进度和资源分配的策略　C、并发执行的进度　D、某个进程申请的资源数多于系统资源数

答案：B

解析：死锁与进程推进顺序（进度）和资源分配策略都有关，是时间相关错误。

第 10 题【缓冲技术】

在现代操作系统中采用缓冲技术的主要目的是 ____。

A、改善用户编程环境　B、提高 CPU 的处理速度　C、提高 CPU 和设备之间的并行程度　D、实现与设备无关性

答案：C

解析：缓冲主要缓和 CPU 与 I/O 设备速度不匹配矛盾，提高二者并行程度。

第 11 题【实时系统】

要求在规定的时间内对外界的请求必须给予及时响应的 OS 是 ____。

A、多道系统　B、实时系统　C、分时系统　D、网络操作系统

答案：B

解析：实时系统强调在规定时限内响应，关键指标是可靠性和及时性。

第 12 题【核心态】

当计算机提供了用户态和内核态时，____ 必须在内核态下执行。

A、PC 自增　B、I/O 操作　C、算术运算　D、访存操作

答案：B

解析：I/O 操作是特权指令，必须在核心态执行；PC 自增、算术运算、访存是非特权指令，用户态可执行。

第 13 题【内存分配】

操作系统为 ____ 分配内存空间。

A、线程　B、高速缓冲存储器（Cache）　C、进程　D、块表

答案：C

解析：进程是资源分配的基本单位，内存空间分配给进程；线程是调度基本单位，共享进程的地址空间。

第 14 题【安全状态】

非安全状态意味着 ____。

A、最终将必然产生死锁　B、存在一个不安全序列，将导致系统产生死锁　C、系统已进入死锁状态　D、以上说法均错误

答案：D

解析：非安全状态可能产生死锁（不是必然，B 错；A 也错），也不一定已死锁（C 错）。故选 D。

第 15 题【分段动态链接】

Which of following memory management schemes is fit for program's dynamic linking?

A、Segmentation　B、Paging　C、Dynamic-sized partitions　D、Fixed-sized partitions

答案：A

解析：分段存储管理（Segmentation）便于实现段的动态链接和共享，因为段是有意义的逻辑信息单位，长度可变；分页是固定大小，不利于动态链接。

第 1 题【操作系统性质】

(F) 操作系统属于最重要的、最不可缺少的应用软件。

答案：错误（F）

解析：操作系统属于系统软件，不是应用软件。

第 2 题【进程状态透明】

(T) 进程状态的转换是由操作系统完成的，对用户是透明的。

答案：正确（T）

解析：进程状态转换由 OS 调度完成，用户不能直接控制，对用户透明。

第 3 题【进程撤销】

(F) 进程被撤消时，只需释放该进程的 PCB 就可以了，因为 PCB 是进程存在的唯一标志。

答案：错误（F）

解析：撤销进程时除释放 PCB，还须释放进程占用的所有资源（内存、打开的文件等）。

第 4 题【用户级线程】

(T) 用户级线程不依赖于内核。

答案：正确（T）

解析：用户级线程由用户空间线程库管理，切换不需模式切换，不依赖内核。

第 5 题【共享条件】

(F) 资源的共享是以程序的并行执行为条件的，没有程序的并行执行，就没有资源的共享。

答案：错误（F）

解析：资源共享以并发执行为条件（不是并行）。单处理机下只能并发不能并行，但仍可实现共享。

第 6 题【PV 操作次序】

(T) 在生产者消费者进程中，V 操作的次序无关紧要，而 P 操作次序不能颠倒。

答案：正确（T）

解析：P 操作次序颠倒会导致死锁（如先 P(mutex) 再 P(empty)）；V 操作次序不影响正确性。

第 7 题【饥饿与死锁】

(T) 系统中进入饥饿状态的进程可以只有 1 个，而进入死锁状态的进程至少有 2 个。

答案：正确（T）

解析：饥饿可只有一个进程（长期得不到资源），死锁需至少两个进程循环等待。

第 8 题【临界区操作】

(F) 互斥进程在临界区里，对共享变量的操作是相同的。

答案：错误（F）

解析：互斥进程在临界区对共享变量的操作不必相同，只是不能同时进入临界区。

第 9 题【文件管理】

(T) 操作系统是通过文件控制块对文件进行管理的。

答案：正确（T）

解析：文件控制块（FCB）是文件存在的标志，OS 通过 FCB 管理文件。文件系统主要目的是按名存取。

第 10 题【SJF】

(F) 在各种作业调度算法中，短作业优先调度算法会使每个作业的等待时间变短。

答案：错误（F）

解析：SJF 使短作业等待时间短，但长作业等待时间可能很长，甚至饥饿。不是"每个作业"都变短。

第 11 题【时间片轮转】

(F) 采用简单的时间片轮转调度算法的系统中，也可能出现饥饿现象。

答案：错误（F）

解析：时间片轮转中每个进程轮流执行，等待时间有界，不会饥饿。

第 12 题【多级页表】

(T) 采用多级页表存储管理不会产生外部碎片。

答案：正确（T）

解析：分页/多级页表按固定页大小分配，没有外部碎片（但有内部碎片，页内碎片）。

第 1 题【信号量取值范围】

有 3 个进程共享一程序段，而每次最多允许两个进程进入该程序段，则信号量的取值范围是 ____。

答案：(2, 1, 0, −1)

解析：信号量初值为 2（允许 2 个进入）。3 个进程中最多 2 个进入，剩 1 个等待时信号量为 2−3=−1。所以取值范围是 2、1、0、−1。

第 2 题【死锁最少资源数】

某系统中有 5 个并发进程，都需要 3 个同类资源。试问该系统不会产生死锁的最少资源总数应该是 ____。

答案：11

解析：公式 n×(m−1)+1，n=5 进程，m=3 每进程所需。5×2+1=11。当资源数为 10 时，每个进程持有 2 个（共 10），都差 1 个而互相等待，死锁；资源数 11 时至少有一个进程能拿到 3 个完成并释放，不死锁。

第 3 题【死锁资源范围】

某系统有 4 个并发进程，都需要同类资源 3 个，试问系统资源数在 3 到 ____ 这个范围内，可能因为进程推进顺序不当而引起死锁产生。

答案：8

解析：每个进程最多持有 m−1=2 个，4 个进程各持有 2 个共 8 个时，都差 1 个而互相等待，死锁。资源数 ≥ 9 时必有进程能完成。故范围是 3~8。

第 4 题【磁盘存取时间计算】

若磁盘转速为 5400 转/分，平均寻道时间为 8ms，每个磁道包含 1000 个扇区，则访问一个扇区平均存取时间大约是 ____ ms。

答案：13.57

解析：转速 5400/60=90 转/秒，旋转一周 1000/90≈11.11ms。平均旋转延迟 11.11/2≈5.56ms；传输一扇区 11.11/1000≈0.011ms。总时间 = 8+5.56+0.011 ≈ 13.57ms。

第 5 题【SCAN 磁盘调度计算】

假定磁盘有 200 个柱面（编号 0~199），当前存储臂的位置在 134 号柱面上，并刚刚完成 152 号柱面的服务请求。若请求队列先后顺序为 68, 174, 91, 137, 94, 152, 102, 157, 120，则使用 SCAN 算法时，磁道移动总和为 ____。

答案：308

解析：134<152，磁头从 152 移到 134，向小方向扫描。顺序：134→120→102→94→91→68→（到底端 0 转向）→137→152→157→174。移动 = 14+18+8+3+23+68+137+15+5+17 = 308。

第 6 题【分页地址转换】

在一分页存储管理系统中，逻辑地址长度为 16 位，页面大小为 4KB，有一逻辑地址为 1E6BH，且第 0、1、2 页依次存放在物理块 5H、AH、BH 中，问相应的物理地址为 ____ H。

答案：AE6BH

解析：页大小 4KB=1000H。页号 = INT(1E6BH/1000H)=1H，页内偏移 = 1E6BH mod 1000H=E6BH。页号 1→块号 AH。物理地址 = AH×1000H+E6BH = A000H+E6BH = AE6BH。

第 7 题【信号量资源计数】

设与某资源关联的信号量初值为 3，当前值为 1。若 M 表示该资源的可用个数，N 表示等待该资源的进程数，则 M、N 分别是 ____。

答案：M=1，N=0（即 B、1 0）

解析：当前值 1>0，表示可用资源数 M=1；值>0 说明没有进程在等待，N=0。

第 8 题【响应比调度】

哪个进程调度算法既考虑进程等待时间又考虑进程执行时间？请简述。

答案：最高响应比优先（HRRN）

解析：响应比 = (等待时间+要求服务时间)/要求服务时间 = 1+等待时间/服务时间。①等待时间相同，短作业响应比高（类 SJF）；②服务时间相同，等待久者响应比高（类 FCFS）；③随等待增加长作业响应比上升，最终能获 CPU，不饥饿。是 FCFS 与 SJF 的折中。

第 9 题【死锁与环路】

系统资源分配图中出现了环路，则系统是否必然发生死锁？请解释。

答案：不一定。

解析：资源分配图出现环路是死锁的必要条件而非充分条件。当每类资源只有一个实例时，环路必死锁；若某类资源有多个实例，即使有环路也可能不死锁（进程推进使资源释放后环路可解除）。

第 10 题【动态分区放置算法】

请列举动态分区的三种放置算法，并简单解释。

答案：

1. 首次适应（First Fit）：从空闲分区链首开始找第一个能满足的分区。实现简单、分配快，但低址端产生大量小碎片。
2. 最佳适应（Best Fit）：找能满足且最小的分区。减少浪费，但产生大量难以利用的小碎片，查找效率低。
3. 最坏适应（Worst Fit）：选能满足且最大的分区。剩余空间大仍可利用，但大进程可能无法分配。

第 11 题【虚拟存储物质基础】

请列举实现虚拟存储系统的三个物质基础。

答案：

1. 一定容量的内存：作为工作集，存放当前活跃页面/段。
2. 足够大的外存（磁盘）：作为后备存储，存放不在内存的页面/段。
3. 地址变换机构（MMU）：实现逻辑地址到物理地址转换，含页表/段表、快表（TLB）等硬件支持。

第 12 题【缺页中断原因】

请解释为什么在虚拟页式存储系统中需要引入缺页中断？

答案：当 CPU 访问的页面不在内存（在磁盘上）时，硬件无法完成地址转换，需缺页中断通知 OS。它是请求调页的核心机制，使程序可在部分页面在内存时正确运行。处理程序负责：①找到所需页在磁盘的位置；②在内存找空闲页框（或置换页面）；③把页面从磁盘读入内存；④更新页表；⑤重新执行被中断的指令。

第 13 题【模式切换与进程切换】

试问模式切换是否一定会引起进程切换？解释原因。

答案：不一定。

解析：①模式切换只是 CPU 执行状态（用户态↔核心态）的转变，OS 内核处理完中断或系统调用后可返回原进程继续，此时只有模式切换，无进程切换。②只有当 OS 决定调度另一个进程执行时（如时间片用完、更高优先级进程就绪），才发生进程切换。

第 14 题【FSCAN 避免饥饿】

除 FCFS 外的所有磁盘调度算法都不是真正公平的（可能出现"饥饿"）。请解释基于 SCAN 的改进算法 FSCAN 是如何避免饥饿的。

答案：①每个请求最多等待一轮扫描就能得到服务，等待时间有上界；②不像 SCAN 那样新请求可能立即被服务而老请求被推迟，FSCAN 保证先到的请求先被服务（在当前轮次内）；③避免了 SCAN 中某些请求（位于磁头刚经过位置）长时间等待的问题。