📖 操作系统（Operating System）—— 408考研完全笔记

编写说明：本笔记严格依据全国硕士研究生招生考试计算机学科专业基础（科目代码：408/11408）考试大纲编写，融合汤子瀛《计算机操作系统》、Operating System Concepts（恐龙书）、CSAPP 与王道课程体系，力求概念严谨、表达通俗、解题实战。

考试概况：408统考满分150分，考试时间180分钟（3小时）。其中数据结构约45分，计算机组成原理约45分，操作系统约35分（约23%），计算机网络约25分。操作系统常见题型为：选择题约10道（20分）+综合应用题1~2道（约15分）。

高频核心章：第2章进程与线程、第3章调度与死锁、第4章同步互斥、第5-6章存储管理与虚拟内存、第7章I/O系统、第8章文件管理。

第一章操作系统引论

1.1 操作系统的目标和作用

操作系统的四个目标

目标	说明
方便性	提供良好用户接口，使计算机更易使用
有效性	提高系统资源利用率和系统吞吐量
可扩充性	能方便地增加新功能模块，适应硬件和应用发展
开放性	遵循国际标准，通过兼容层实现软件互操作

操作系统的作用

OS是用户与计算机硬件之间的接口
OS是计算机系统资源的管理者（处理机、存储器、I/O设备、文件）
OS实现了对计算机资源的抽象（隐藏硬件细节，提供虚拟机）

推动OS发展的主要动力

不断提高计算机资源利用率
方便用户使用
器件的不断更新换代
计算机体系结构的不断发展和更新
不断提出新的应用需求

1.2 操作系统的发展过程

阶段	特点	优缺点
人工操作	用户独占全机	CPU利用率极低，人机矛盾
脱机I/O	引入磁带，外围机处理I/O	减少CPU空闲时间
单道批处理	监督程序控制作业自动处理	自动性，顺序性，内存始终一道作业
多道批处理	内存中同时驻留多道程序	多道性、无序性、调度性；缺乏交互能力
分时系统	多用户同时联机交互	多路性、独立性、及时性、交互性；不能满足实时需求
实时系统	在规定时间内完成处理并给出响应	及时性、可靠性
微机操作系统	单用户单任务(MS-DOS)→单用户多任务(Windows)→多用户多任务(UNIX/Linux)	广泛普及
嵌入式操作系统	微型化、可定制、实时性、可靠性	资源受限环境
网络操作系统	提供网络服务（文件/打印/通信）	C/S模式
分布式操作系统	多台计算机协同工作，统一管理	透明性、模块化

⚠️ 关键辨析：

多道批处理 vs 分时系统：多道批处理追求吞吐量，分时系统追求响应时间

硬实时 vs 软实时：硬实时必须在截止时间内完成（如武器控制），否则灾难性后果；软实时偶尔超时可接受（如视频播放）

1.3 操作系统的基本特性（重点⭐）

四大基本特性

特性	定义	关键点
并发	宏观上多个事件在同一时间段发生	≠并行（并行是同一时刻，需多CPU）；并发是OS最基本特征
共享	系统资源可供多个并发进程共同使用	互斥共享（临界资源一个时刻只一个进程用）/ 同时共享（宏观同时微观交替）
虚拟	通过某种技术变一个物理设备为多个逻辑设备	时分复用（虚拟处理机/虚拟设备）/ 空分复用（虚拟存储器）
异步	进程以不可预知的速度走走停停地推进	并发执行导致；OS须保证运行结果可再现

⚠️ 关系：并发和共享是OS两个最基本特征，互为存在条件。虚拟以并发为前提，异步以并发为前提。没有并发和共享就谈不上虚拟和异步。

1.4 操作系统的运行环境

处理器的双重工作模式

用户态（目态）：普通用户程序运行的状态，不能执行特权指令
核心态（管态/内核态）：OS内核运行的状态，可执行全部指令

特权指令与非特权指令

特权指令：仅在核心态可执行（如I/O指令、置中断指令、存取特殊寄存器指令等）
非特权指令：在用户态和核心态均可执行

中断与异常

中断（外中断）：由CPU外部I/O设备引起（如I/O完成中断、时钟中断）
异常（内中断/陷入/陷阱）：由CPU内部事件引起（如除零、缺页、系统调用trap指令）

⚠️ 用户态→核心态：唯一途径是中断或异常（也包括系统调用，实质是通过trap指令触发中断） 核心态→用户态：通过设置程序状态字PSW即可

1.5 操作系统的主要功能

功能	子功能	说明
处理机管理	进程控制、进程同步、进程通信、调度	最核心的管理功能
存储器管理	内存分配与回收、地址映射、内存保护、内存扩充	逻辑→物理地址变换
设备管理	缓冲管理、设备分配、设备处理	隐藏设备细节
文件管理	文件存储空间管理、目录管理、读写管理、保护	方便用户使用
接口管理	命令接口(CLI)、程序接口(系统调用)、图形接口(GUI)	面向用户和程序

现代OS的新功能

安全保障：认证技术、密码技术、访问控制技术、反病毒技术
联网和服务功能
多媒体支持

1.6 操作系统的结构（重点⭐）

结构	优点	缺点	典型代表
简单结构	简单,执行效率高	无模块划分,难维护	MS-DOS
模块化结构	模块-接口法,模块间以接口通信	模块划分标准不统一,接口不清晰	—
分层式结构	自底向上逐层构建,正确性易保证,维护性好	效率较低(每层都有额外开销)	THE系统
微内核结构	足够小的内核+客户-服务器模式,可扩展/可靠/可移植/支持分布式/面向对象	上下文切换开销大(原需4次切换,微内核需8次)	Mach, Windows NT
外核结构	物理资源直接隔离与复用,减少映射层,库OS实现抽象	兼容性差	Exokernel(MIT)

微内核结构

微内核功能仅包含：①进程（线程）管理 ②低级存储器管理 ③中断和陷入处理
基本概念：足够小的内核 + 客户-服务器模式 + 策略与机制分离 + 面向对象
应用机制与策略分离：内核中只有机制（如进程调度机制），策略在用户进程中

1.7 系统调用

系统调用：OS提供给应用程序使用OS服务的接口（唯一接口）。

系统调用与一般过程调用的4个主要区别

方面	系统调用	一般过程调用
运行状态	用户态→核心态→用户态	保持在用户态
状态转换	通过中断机构进入核心态(INT 80H或trap)	无状态转换
返回问题	可能不返回调用进程（如被更高优先级抢占）	总是返回调用者
嵌套	嵌套深度有限	可任意嵌套/递归

系统调用的类型

进程控制类：创建/终止进程、加载/执行程序
文件操纵类：创建/删除/打开/关闭/读/写文件
进程通信类：发送/接收消息
设备管理类：请求/释放设备
信息维护类：获取/设置时间日期、系统数据

Linux系统调用补充：早期x86可通过 INT 0x80，现代x86-64主要使用 syscall 指令进入内核。

🎯 本章真题锚点与最短模板

高频题号（2009-2025）：2012Q23、2015Q24、2019Q25、2023Q23/Q24/Q26、2024Q23、2025Q23/Q24
优质例题：给定事件“除零、DMA完成、系统调用、缺页”，判断其属于中断/异常及是否会导致用户态→核心态。
最短解题模板：
1. 先判来源：外设=外中断；CPU内部=异常。
2. 再判态切换：发生中断/异常→必入核心态处理。
3. 最后排除干扰：普通算术/逻辑指令通常不触发态切换。

⚡ 秒杀版口令卡（10秒回忆）

口令：外设中断、内部异常、trap入核。
口令：用户态禁特权，系统调用走内核。
口令：判题三步：来源→态切换→干扰项。

第二章进程的描述与控制

2.1 前趋图和程序执行

前趋图（DAG）

有向无循环图（DAG），用于描述进程间的前后关系
节点表示语句/程序段/进程，有向边表示前趋关系

程序顺序执行的特征

顺序性：严格按顺序执行
封闭性：程序独占全部资源，结果不受外界影响
可再现性：输入相同→结果相同

程序并发执行的特征

间断性：执行—暂停—执行
失去封闭性：共享资源，执行环境被外界影响
不可再现性：结果可能因调度顺序不同而不同

2.2 进程的描述

进程的定义

进程是程序的一次执行过程
进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位（引入线程后，线程成为调度的基本单位）

进程的特征

特征	说明
动态性（最基本）	进程有创建、运行、消亡的生命周期
并发性	多个进程可同时存在于内存中并发执行
独立性	进程是独立运行和获得资源的基本单位
异步性	各进程按各自独立、不可预知的速度推进

进程的状态

三态模型：

        就绪 ——调度——→ 运行
         ↑               ↓
         ← —事件完成—— 阻塞
         ↑               ↓
         ←←←←←←←←←←←←←
                时间片完/被抢占

五态模型：就绪、运行、阻塞 + 创建、终止

进程五态转换图

七态模型（含挂起）：

活动就绪 ↔ 静止就绪（挂起）
活动阻塞 ↔ 静止阻塞（挂起）

七态模型状态转换图

挂起(Suspend)：进程从内存调至外存；激活(Active)：进程从外存调回内存

进程控制块 PCB

PCB是进程存在的唯一标志，包含4类信息：

类别	内容
进程标识符	内部标识符（PID数字标识）、外部标识符（用户使用的名称）
处理机状态	通用寄存器、PC、PSW、用户栈指针
进程调度信息	进程状态、优先级、事件（阻塞原因）、调度其他信息
进程控制信息	程序和数据地址、同步和通信机制、资源清单、链接指针

PCB的组织方式：

线性方式：所有PCB放在一个线性表中
链接方式：按状态链成多个队列（就绪队列、阻塞队列等）
索引方式：建立索引表，表项指向PCB

2.3 进程控制

进程控制通过原语实现（原语在内核态执行，不可中断）。

原语	功能
创建原语	分配PID→分配资源→初始化PCB→插入就绪队列
终止原语	查找PCB→若进程正在运行则终止→终止其子孙进程→归还资源→删除PCB
阻塞原语	将进程从运行态→阻塞态，保存现场，插入等待队列
唤醒原语	从等待队列移出→将进程从阻塞态→就绪态，插入就绪队列
挂起原语	活动就绪→静止就绪，或活动阻塞→静止阻塞
激活原语	静止就绪→活动就绪，或静止阻塞→活动阻塞

⚠️ 阻塞和唤醒必须成对出现！阻塞由进程自己调用（主动），唤醒由其他相关进程调用（被动）。

2.4 进程通信

方式	说明
共享存储器	多个进程通过读/写共享内存区域通信；需同步互斥机制保护
管道(pipe)	半双工，固定大小缓冲区(通常4KB)，FIFO字节流；写满时写进程阻塞,读空时读进程阻塞；连接读写进程的共享文件
消息传递	直接通信：点对点,send(P,msg)/receive(Q,msg)；间接通信：通过邮箱,send(A,msg)/receive(A,msg)
客户机-服务器	socket（套接字,可跨网络）/ RPC（远程过程调用）

2.5 线程

线程的概念

线程是CPU调度的基本单位
进程是资源分配的基本单位
一个进程可包含多个线程，共享进程资源
线程比进程更轻量，切换开销更小

进程 vs 线程

比较项	进程	线程
资源分配	资源分配的基本单位	不拥有系统资源(共享进程资源)
调度	(无线程时)调度的基本单位	调度的基本单位
并发性	进程间可并发	进程内的多线程也可并发
系统开销	进程创建/撤销/切换开销大(需切换页表导致TLB失效/Cache冷)	线程切换开销小(不切换地址空间,TLB/Cache仍有效)
独立性	进程间独立	同一进程内的线程共享地址空间

线程控制块 TCB

包含：线程标识符、寄存器状态（PC、PSW、通用寄存器）、线程运行状态、优先级、栈指针等。

线程的实现方式

方式	优点	缺点
用户级线程ULT	不需内核支持,切换快,进程可专用调度算法,平台无关	一个线程阻塞→整个进程阻塞；不能利用多处理机
内核级线程KST	多处理机上可并行,一线程阻塞不影响其他,内核本身也可多线程	模式切换开销大(用户态→内核态)
组合方式	结合两者优点	实现复杂

多线程模型

模型	说明	缺点
多对一	多个ULT映射到一个KST	一阻塞全阻塞，不能多处理机并行
一对一	每个ULT对应一个KST	创建开销大（如Windows NT）
多对多	多个ULT映射到≤ULT数的KST	结合优点,最灵活

轻量级进程(LWP)

作为ULT与KST之间的中间层
每个LWP连接一个KST
ULT通过LWP间接使用内核服务

2.6 程序运行环境与进程内存映像（2026趋势）

进程内存映像（Memory Image）

典型用户进程地址空间自低地址到高地址可概括为：

text(代码段) → data(已初始化全局/静态区) → bss(未初始化全局/静态区) → heap(堆,向高地址增长) ... stack(栈,向低地址增长)

text段：机器指令与只读常量，通常只读且可共享
data段：已初始化的全局变量和静态变量
bss段：未初始化全局变量和静态变量（装入时清零）
heap堆：由 malloc/new 等动态扩展和回收
stack栈：函数调用现场、局部变量、返回地址

⚠️ 易考辨析：进程共享“代码和只读数据”通常发生在同一程序多进程场景；线程共享进程地址空间，但各线程栈独立。

fork 与 COW（写时复制）

fork() 后父子进程最初共享物理页框（只读映射）
任一方尝试写入时触发保护异常，OS复制该页（Copy-On-Write）
COW的目标：减少无效复制开销，提高创建子进程效率

2.7 信号（Signal）机制（2025新增）

信号的本质

信号是软件层面的异步事件通知机制，用于告知进程“发生了某事件”
信号不是数据传输通道，主要表达“发生了什么”而非“传了什么”

信号处理方式

默认处理（终止/忽略/停止/继续/核心转储）
显式忽略（部分信号可忽略）
自定义处理函数（signal handler）

常见高频信号

SIGKILL(9)：立即终止，不可捕获、不可忽略
SIGTERM(15)：请求终止，可被捕获处理
SIGCHLD：子进程状态变化通知父进程
SIGSEGV：非法内存访问

生命周期与检查时机

流程：产生（generate）→ 未决（pending）→ 递送（deliver）→ 处理（handle）
内核通常在从核心态返回用户态前检查并递送可处理信号

信号 vs 信号量（常考）

对比项	信号（Signal）	信号量（Semaphore）
作用	异步事件通知	同步与互斥
是否计数资源	否	是（value体现资源数/等待数）
典型场景	进程终止、异常通知、子进程回收	生产者-消费者、互斥临界区

⚠️ 一句话区分：Signal解决“事件到了吗”，Semaphore解决“资源够不够/次序对不对”。

🎯 本章真题锚点与最短模板

高频题号（2009-2025）：2011Q25、2014Q26、2017Q27、2019Q23/Q24、2024Q24/Q25/Q28、2025Q22/Q46
优质例题：判断“创建子进程、I/O完成、时间片用完、请求I/O”引起的进程状态转换。
最短解题模板：
1. 建立五态图：就绪、执行、阻塞及方向箭头。
2. 逐事件映射：时间片到期→执行→就绪；I/O请求→执行→阻塞；I/O完成→阻塞→就绪。
3. 涉及线程时先判“共享什么”：地址空间共享，栈/寄存器私有。

⚡ 秒杀版口令卡（10秒回忆）

口令：时间片到=就绪；等I/O=阻塞；I/O完=就绪。
口令：进程管资源，线程管调度。
口令：共享地址空间，私有栈与寄存器。

第三章处理机调度与死锁

3.1 处理机调度的层次

层次	又称	频率	功能
高级调度（作业调度）	长程调度	最低	从外存后备队列中选择作业调入内存,创建进程
中级调度（内存调度）	中程调度/对换调度	中等	决定哪些进程可参与竞争CPU（挂起/激活）
低级调度（进程调度）	短程调度	最高（最频繁）	从就绪队列中选一个进程分配CPU

⚠️ 低级调度（进程调度）是最基本的调度，任何OS都必须有。多道批处理系统需要高级调度+低级调度，分时系统通常不需要高级调度。

3.2 调度的目标和准则

调度的共同目标

资源利用率高：CPU利用率 = CPU有效工作时间 / 总时间
公平性
平衡性
策略强制执行

不同系统的目标

系统类型	主要目标
批处理	平均周转时间短、吞吐量高、处理机利用率高
分时	响应时间快、均衡性
实时	满足截止时间、可预测性

重要公式⭐

$\bar{T} = \frac{1}{n}\sum_{i=1}^{n}T_i$

其中 $T_i =$ 作业完成时间 $-$ 作业提交时间 = 周转时间

$W_i = \frac{T_i}{T_{si}} \quad \text{（带权周转时间，}T_{si}\text{为实际服务时间）}$

$\bar{W} = \frac{1}{n}\sum_{i=1}^{n}W_i \quad \text{（平均带权周转时间）}$

3.3 调度算法（核心考点⭐⭐⭐）

3.3.1 先来先服务 FCFS

按到达先后顺序调度
非抢占式
对长作业有利，短作业不利
常与其他算法结合使用
既可作业调度,也可进程调度

3.3.2 短作业/进程优先 SJF/SPF

选择估计运行时间最短的作业优先
非抢占式SJF / 抢占式SRTN（最短剩余时间优先）
平均周转时间和平均带权周转时间最小
缺点：①须预知运行时间 ②长作业可能饥饿 ③无法用于交互式系统 ④忽视紧迫性

3.3.3 优先级调度

非抢占式：一旦某进程获得CPU，就一直运行到完成或阻塞
抢占式：有更高优先级进程到达时立即抢占

优先级的类型：

静态优先级：创建时确定，不再改变（依据：进程类型、资源需求、用户要求）
动态优先级：随运行情况动态调整（如等待时间越长优先级越高）

3.3.4 高响应比优先 HRRN

$R_P = \frac{\text{等待时间} + \text{要求服务时间}}{\text{要求服务时间}} = 1 + \frac{\text{等待时间}}{\text{要求服务时间}}$

$R_P$ 最高的优先调度
兼顾短作业和长作业（短作业天然响应比高,长作业等久了响应比也升高）
非抢占式
缺点：每次调度前都要重新计算所有作业的响应比，增加开销

3.3.5 时间片轮转 RR

专门为分时系统设计
所有就绪进程排成FIFO队列，每次分配一个时间片q
q太小 → 上下文切换频繁，开销大
q太大 → 退化为FCFS
q的经验值：略大于一次典型交互的时间

3.3.6 多级队列调度

设置多个就绪队列，不同队列可有不同调度算法和不同优先级
适合多处理机系统

3.3.7 多级反馈队列调度 MLFQ（⭐⭐⭐）

公认的较好的调度算法，兼顾多种类型作业。

算法规则：

设置多个就绪队列，优先级递减，时间片递增
新进程进入第1级队列末尾，按FCFS等待调度
若在当前时间片内未完成，降至下一级队列末尾
仅当第k级队列为空时，才调度第k+1级队列
若有新进程进入较高优先级队列，可抢占当前运行进程

优点：终端型用户（短作业快速响应）、短批处理作业用户（周转时间短）、长批处理作业用户（不会饥饿）都能满足。

3.3.8 公平调度

保证调度：N个进程，每个保证获得1/N的处理机时间。实际/应得比率最小的优先
公平分享调度（FSS）：按用户分配CPU时间，保证用户层面公平

3.4 实时调度

可调度条件

$\sum_{i=1}^{m}\frac{C_i}{P_i} \leq 1 \quad \text{（单处理机）}$

$\sum_{i=1}^{m}\frac{C_i}{P_i} \leq N \quad \text{（N个处理机）}$

其中 $C_i$ = 处理时间， $P_i$ = 周期

实时调度分类

类别	方式	响应时间
非抢占轮转	轮转调度	数秒~数十秒
非抢占优先级	优先级+非抢占	数百ms~数秒
抢占-时钟中断	在时钟中断时抢占	几ms~几十ms
抢占-立即抢占	事件发生立即抢占	几百μs~几ms

最早截止时间优先 EDF

截止时间越早，优先级越高
可用于抢占式/非抢占式
对隐式截止期任务集（ $D_i=P_i$ ），单处理机下 $\sum C_i/P_i \le 1$ 是充要条件
若任务模型不满足 $D_i=P_i$ ，则需结合具体约束（如 $D_i$ 与 $P_i$ 关系、是否可抢占）进一步判定

Rate Monotonic（RM）补充

RM为固定优先级实时调度（周期越短优先级越高）
RM充分条件（不是必要条件）：

$U = \sum_{i=1}^{n}\frac{C_i}{P_i} \le n\left(2^{1/n}-1\right)$

当 $n \to \infty$ 时，上界趋近于 $\ln 2 \approx 0.693$

最低松弛度优先 LLF

$\text{松弛度} = \text{必须完成时间} - \text{剩余运行时间} - \text{当前时间}$

松弛度越小，越紧迫，优先级越高
松弛度=0时必须立即执行
主要用于抢占式调度

优先级倒置问题⭐

问题：高优先级进程被低优先级进程间接阻塞。

典型场景：P1(高)→P2(中)→P3(低)。P3进入临界区持有共享资源；P1需要该资源被阻塞；P2就绪抢占P3运行→P3无法释放资源→P1一直被阻塞。

解决方案：

简单方法：进程进入临界区后，不允许被抢占（缺点：临界区长则影响系统）
动态优先级继承：P3继承P1的高优先级→P2无法抢占P3→P3尽快完成释放资源→P1得以运行

3.5 Linux CFS调度器

调度器类优先级：Stop > Real_Time > Fair > Idle
友好值nice：-20~+19，默认0
虚拟运行时间vruntime：nice值越大，vruntime增长越快；调度时选vruntime最小的
实时调度：SCHED_FIFO / SCHED_RR，静态优先级0-99
普通调度：优先级100-139（对应nice -20~+19）

3.6 死锁（核心考点⭐⭐⭐）

死锁的定义

多个进程因竞争资源而造成的一种互相等待的僵局。

死锁的四个必要条件

条件	说明
互斥条件	资源一次只供一个进程使用
请求和保持条件	进程持有至少一个资源,又请求新资源,但新资源被占用而阻塞,此时不释放已持有的
不可抢占条件	已获得的资源未使用完之前不能被强行夺走
循环等待条件	存在进程-资源的环形等待链

⚠️ 四个条件缺一不可。循环等待是死锁的必要不充分条件（有循环等待不一定死锁,但死锁必有循环等待）

死锁的处理策略

策略	方法
预防	破坏四个必要条件之一(除互斥外)
避免	银行家算法（动态检测安全性）
检测和解除	资源分配图,死锁定理
忽略（鸵鸟策略）	不处理,如UNIX/Linux一般采用

死锁预防

破坏条件	方法	缺点
请求和保持	一次性申请全部资源	资源浪费严重,可能饥饿
不可抢占	请求新资源不满足时释放已有的	实现复杂,可能导致已有工作丢失
循环等待	资源编号,按序申请	资源编号不灵活,可能浪费

银行家算法（⭐⭐⭐核心）

数据结构：

$Available[m]$ ：当前各类资源的可用数量
$Max[n][m]$ ：每个进程对各类资源的最大需求
$Allocation[n][m]$ ：已分配给每个进程的各类资源数量
$Need[n][m]$ ：每个进程还需要的各类资源数量

$Need[i][j] = Max[i][j] - Allocation[i][j]$

银行家算法流程图

调度算法对比图

安全性算法：

初始化： $Work = Available$ ， $Finish[i] = false$
找满足条件的进程 $P_i$ ： $Finish[i]=false$ 且 $Need[i] \leq Work$
若找到： $Work = Work + Allocation[i]$ ， $Finish[i] = true$ ，转第2步
若不能找到：检查所有 $Finish[i]$ ，若全为true→安全（输出安全序列）；否则→不安全

银行家算法完整数值示例（⭐⭐⭐ 高频大题）

题目：系统有 A、B、C 三类资源，初始可用量为 $(3,3,2)$ 。5个进程当前状态如下：

进程 Max (A,B,C) Allocation (A,B,C) Need (A,B,C)
$P_0$ (7,5,3) (0,1,0) (7,4,3)
$P_1$ (3,2,2) (2,0,0) (1,2,2)
$P_2$ (9,0,2) (3,0,2) (6,0,0)
$P_3$ (2,2,2) (2,1,1) (0,1,1)
$P_4$ (4,3,3) (0,0,2) (4,3,1)

$Available = (10,5,7) - (7,2,5) = (3,3,2)$

求安全序列：

步骤选进程 Work (A,B,C) Need≤Work? 执行后 Work+=Alloc
1 $P_1$ (3,3,2) (1,2,2)≤(3,3,2) ✓ (3,3,2)+(2,0,0)=(5,3,2)
2 $P_3$ (5,3,2) (0,1,1)≤(5,3,2) ✓ (5,3,2)+(2,1,1)=(7,4,3)
3 $P_4$ (7,4,3) (4,3,1)≤(7,4,3) ✓ (7,4,3)+(0,0,2)=(7,4,5)
4 $P_2$ (7,4,5) (6,0,0)≤(7,4,5) ✓ (7,4,5)+(3,0,2)=(10,4,7)
5 $P_0$ (10,4,7) (7,4,3)≤(10,4,7) ✓ (10,4,7)+(0,1,0)=(10,5,7)

✅ 所有进程均可完成 → 安全序列 $\langle P_1, P_3, P_4, P_2, P_0\rangle$

追问：若 $P_1$ 此时请求 $(1,0,2)$ ，能否分配？

试分配： $Available=(3,3,2)-(1,0,2)=(2,3,0)$ ， $Alloc_1=(3,0,2)$ ， $Need_1=(0,2,0)$

再跑安全性算法： $P_1→P_3→P_4→P_2→P_0$ ，仍安全 → 可以分配

进程	Max (A,B,C)	Allocation (A,B,C)	Need (A,B,C)
$P_0$	(7,5,3)	(0,1,0)	(7,4,3)
$P_1$	(3,2,2)	(2,0,0)	(1,2,2)
$P_2$	(9,0,2)	(3,0,2)	(6,0,0)
$P_3$	(2,2,2)	(2,1,1)	(0,1,1)
$P_4$	(4,3,3)	(0,0,2)	(4,3,1)

步骤	选进程	Work (A,B,C)	Need≤Work?	执行后 Work+=Alloc
1	$P_1$	(3,3,2)	(1,2,2)≤(3,3,2) ✓	(3,3,2)+(2,0,0)=(5,3,2)
2	$P_3$	(5,3,2)	(0,1,1)≤(5,3,2) ✓	(5,3,2)+(2,1,1)=(7,4,3)
3	$P_4$	(7,4,3)	(4,3,1)≤(7,4,3) ✓	(7,4,3)+(0,0,2)=(7,4,5)
4	$P_2$	(7,4,5)	(6,0,0)≤(7,4,5) ✓	(7,4,5)+(3,0,2)=(10,4,7)
5	$P_0$	(10,4,7)	(7,4,3)≤(10,4,7) ✓	(10,4,7)+(0,1,0)=(10,5,7)

⚠️ 银行家算法是死锁避免策略，不是死锁预防。它不破坏任何必要条件，而是在每次资源分配前检测安全性。

死锁检测

资源分配图的简化：

找到既不阻塞又不孤立的进程节点 $P_i$ （其请求可被满足）
消去 $P_i$ 的所有边（相当于 $P_i$ 执行完归还资源）
重复直到无法再简化

死锁定理：当且仅当资源分配图不可完全简化时，系统处于死锁状态。

死锁资源分配图

死锁解除

终止进程：终止所有死锁进程 / 逐个终止直到解除死锁
资源剥夺：从死锁进程中抢占资源分配给其他进程
选择终止/剥夺的依据：优先级、已执行时间、已使用资源量、进程性质（交互/批处理）

🎯 本章真题锚点与最短模板

高频题号（2009-2025）：2009Q24/Q25、2010Q26、2011Q23、2014Q23/Q24、2016Q24/Q25、2018Q24/Q26、2019Q27/Q30、2021Q23、2025Q26
优质例题：给出进程到达时间+服务时间，分别按FCFS/SJF/RR计算平均周转时间，并判断是否存在饥饿。
最短解题模板：
1. 先画甘特图（含抢占时刻）。
2. 算每进程完成时刻→周转时间→带权周转时间。
3. 死锁题先写“四必要条件”，再用安全序列/资源分配图做判定。

⚡ 秒杀版口令卡（10秒回忆）

口令：调度先画图，不画必错时刻。
口令：周转=完成-到达，带权=周转/服务。
口令：死锁先四条件，再判安全序列。

第四章进程同步（核心考点⭐⭐⭐）

4.1 基本概念

两种制约关系

间接制约（互斥）：多个进程因共享临界资源而互斥使用
直接制约（同步）：多个进程因合作而需要协调推进顺序

临界资源

一次仅允许一个进程使用的资源。硬件如打印机、软件如共享变量。

临界区

进程中访问临界资源的那段代码。

同步机制应遵循的四个准则

准则	说明
空闲让进	临界区空闲时，允许请求进入
忙则等待	临界区被占用时，其他请求必须等待
有限等待	保证进程在有限时间内能进入临界区（不饥饿）
让权等待	不能进入临界区的进程应释放CPU（原则上应遵循但非必须）

4.2 软件同步方法

Peterson算法（两进程互斥⭐）

// 进程Pi
flag[i] = true;     // 表示Pi想进入
turn = j;           // 谦让：设置对方优先
while(flag[j] && turn == j);  // 等待
    // 临界区
flag[i] = false;

满足空闲让进、忙则等待、有限等待（前3条准则）
不满足让权等待（忙等）
仅适用于两个进程

4.3 硬件同步机制

方法	原理	缺点
关中断	进入临界区前关中断，退出后开中断	滥用风险、影响效率、不适用多CPU
TS指令(Test-and-Set)	原子操作：读取lock旧值并置lock=true	忙等,不满足让权等待
Swap/XCHG指令	原子交换两个变量	忙等,不满足让权等待

// TS指令
boolean TestAndSet(boolean *lock) {
    boolean old = *lock;
    *lock = true;
    return old;
}
// 使用：while(TestAndSet(&lock)); 临界区; lock=false;

4.4 信号量机制（⭐⭐⭐最核心）

整型信号量

wait(S) { while(S <= 0); S--; }   // 忙等
signal(S) { S++; }

缺点：忙等（不满足让权等待）

记录型信号量（⭐⭐⭐）

typedef struct {
    int value;
    struct process_control_block *list;  // 等待队列
} semaphore;

void wait(semaphore *S) {     // P操作
    S->value--;
    if (S->value < 0)
        block(S->list);       // 阻塞自己,插入等待队列
}

void signal(semaphore *S) {   // V操作
    S->value++;
    if (S->value <= 0)
        wakeup(S->list);      // 唤醒等待队列中的一个进程
}

⭐ 关键理解：

$value > 0$ ：有 $value$ 个资源可用

$value = 0$ ：无资源可用，无进程等待

$value < 0$ ： $|value|$ = 等待队列中的进程数

满足让权等待（阻塞自己而非忙等）

AND型信号量

Swait(S1, S2, ..., Sn)：同时申请所有资源，全部≥1才分配
Ssignal(S1, S2, ..., Sn)：同时释放所有资源
避免死锁（一次获取所有需要的资源）

信号量集

Swait(S1,t1,d1; S2,t2,d2; ...; Sn,tn,dn)
- $t_i$ ：测试值（ $S_i \geq t_i$ 才分配）
- $d_i$ ：需求值（每次分配 $d_i$ 个）
特殊情况：
- $(S,d,d)$ ：每次申请 $d$ 个
- $(S,1,1)$ ：等价于记录型信号量
- $(S,1,0)$ ：开关型（ $S \geq 1$ 时允许， $S=0$ 时阻塞，但不消耗资源）

4.5 信号量的应用（⭐⭐⭐）

实现互斥

semaphore mutex = 1;  // 互斥信号量,初值为1

// 进程Pi
wait(mutex);          // P(mutex)
    // 临界区
signal(mutex);        // V(mutex)

$mutex$ 取值范围： $-1, 0, 1$

$1$ ：资源空闲

$0$ ：一个进程在临界区，无等待

$-1$ ：一个在临界区，一个在等待

实现同步

semaphore S = 0;  // 同步信号量,初值为0

// 进程P1                          // 进程P2
C1;  // 语句C1                     wait(S);  // P(S) 等在前面
signal(S); // V(S) 执行完C1后通知   C2;       // C2必须在C1之后执行

口诀：前V后P（在"前面的"操作后面做V，在"后面的"操作前面做P）

4.6 管程（⭐⭐）

管程的定义

管程由以下四部分组成：

管程名称
共享数据结构
对该数据结构操作的一组过程（函数）
对共享数据设置初始值的语句

管程的特性

封装：数据结构只能被管程内部的过程访问
互斥：每次只允许一个进程进入管程执行
信息隐蔽：外部不可见内部数据

条件变量

x.wait()   // 阻塞调用进程,释放管程,将进程加入x的等待队列
x.signal() // 唤醒x等待队列中的一个进程;若无等待进程,则无操作

⚠️ 条件变量的signal与信号量的signal不同：

信号量的signal： $S$ 值加1，即使无等待进程也有效果

条件变量的signal：若无等待进程则无动作（不会"记忆"）

管程 vs 进程

方面	管程	进程
目的	管理共享资源	实现系统并发
数据结构	共享数据结构	PCB
操作	同步操作	程序执行
工作方式	被动调用	主动运行
并发	不可并发(互斥进入)	可并发
动态性	管程是OS的一个资源管理模块（静态）	进程有生命周期（动态）

4.7 经典同步问题（⭐⭐⭐必考）

PV前驱图与生产者消费者模型

PV操作信号量机制

生产者-消费者问题

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

// 生产者                              // 消费者
while(1) {                             while(1) {
    生产一个产品;                          wait(full);     // 有产品才取
    wait(empty);    // 有空槽才放          wait(mutex);
    wait(mutex);                           从缓冲区取产品;
    放入缓冲区;                            signal(mutex);
    signal(mutex);                         signal(empty);  // 增加一个空槽
    signal(full);   // 增加一个产品         消费产品;
}                                      }

⚠️ 必须先P资源信号量,再P互斥信号量！反过来必死锁！

错误示例：wait(mutex); wait(empty); → 若缓冲区满,生产者持有mutex等empty,消费者想进入要等mutex → 死锁

哲学家进餐问题

5个哲学家围坐，5根筷子。每人需左右两根筷子才能吃饭。

semaphore chopstick[5] = {1, 1, 1, 1, 1};

// 哲学家i
while(1) {
    思考;
    wait(chopstick[i]);         // 拿左
    wait(chopstick[(i+1)%5]);   // 拿右
    进餐;
    signal(chopstick[i]);       // 放左
    signal(chopstick[(i+1)%5]); // 放右
}

可能死锁！（5人同时拿左筷子）

死锁解决方案（任选一）：

最多4人同时进餐（限制同时拿筷子的人数）
同时拿起两根筷子（AND信号量）
奇偶号策略：奇号哲学家先拿左再拿右，偶号先拿右再拿左

读者-写者问题

// 读者优先解法
semaphore rmutex = 1;    // 保护readcount
semaphore wmutex = 1;    // 互斥写
int readcount = 0;

// 读者                                // 写者
wait(rmutex);                          wait(wmutex);
    readcount++;                           写操作;
    if(readcount == 1)                 signal(wmutex);
        wait(wmutex);  // 第一个读者锁住写
signal(rmutex);
    读操作;
wait(rmutex);
    readcount--;
    if(readcount == 0)
        signal(wmutex); // 最后一个读者解锁写
signal(rmutex);

第一问题（读者优先）：读者可能导致写者饥饿 第二问题（写者优先）：需增加额外信号量，写者到达后新读者不能读

写者优先思路（补充）

// 写者优先常见信号量
semaphore rmutex = 1;    // 保护readcount
semaphore wmutex = 1;    // 写互斥
semaphore readTry = 1;   // 是否允许新读者进入
semaphore wcMutex = 1;   // 保护writecount
int readcount = 0, writecount = 0;

// 写者
wait(wcMutex); writecount++;
if (writecount == 1) wait(readTry);  // 第一位写者到达，阻止新读者
signal(wcMutex);

wait(wmutex); 写操作; signal(wmutex);

wait(wcMutex); writecount--;
if (writecount == 0) signal(readTry); // 最后一位写者离开，放行读者
signal(wcMutex);

要点：readTry 是“闸门”，只要有写者等待，就不再放新读者进入，从而避免写者饥饿。

4.8 Linux同步机制

并发来源：中断、内核态抢占、多处理机
原子操作：lock前缀指令、atomic_t
自旋锁：多处理机忙等,适用短临界区; spin_lock/spin_unlock; 变种rwlock/seqlock
信号量：适用长临界区,可睡眠

🎯 本章真题锚点与最短模板

高频题号（2009-2025）：2009Q45、2010Q27、2011Q45、2014Q47、2015Q45、2017Q46、2018Q32、2019Q43、2020Q45、2021Q45/Q46、2022Q45、2024Q46、2025Q45
优质例题：三线程A/B/C有前驱约束 A→C、B→C、C→D，写出最少信号量与P/V序列。
最短解题模板：
1. 先画前驱图，给每条“前驱边”分配一个同步信号量。
2. 每个活动：前驱边对应 P 在前，后继边对应 V 在后。
3. 共享缓冲区再补 mutex（互斥）+ empty/full（同步）。

⚡ 秒杀版口令卡（10秒回忆）

口令：先前驱后PV，不画图不下笔。
口令：互斥用mutex，同步用前驱信号量。
口令：缓冲区三件套：mutex、empty、full。

第五章存储器管理

5.1 程序的装入和链接

装入方式

方式	特点	适用
绝对装入	编译时产生绝对地址	单道程序
可重定位装入（静态重定位）	装入时一次性修改全部地址	装入后不能移动
动态运行时装入（动态重定位）	运行时借助重定位寄存器转换地址	地址可延迟到执行时变换，支持紧凑

链接方式

方式	说明
静态链接	装入前将所有模块链接成完整可执行文件
装入时动态链接	装入内存时边装入边链接
运行时动态链接	运行到某模块时才链接（最灵活,节省内存）

5.2 连续分配方式

方式	说明	碎片
单一连续分配	内存分为系统区+用户区,一次只一个程序	有内碎片
固定分区分配	预先分为若干固定大小分区	内碎片（分区内浪费）
动态分区分配	按需分配大小	外碎片（分区间浪费），可通过紧凑解决

动态分区分配算法⭐

算法	策略	空闲分区排列	优缺点
首次适应FF	从头找第一个够大的	地址递增	保留大分区,但低址碎片多
循环首次适应NF	从上次找到的位置继续	循环	分布均匀,但大分区缺乏
最佳适应BF	找最小的够用分区	容量递增	碎片最小但太小无法用
最坏适应WF	找最大的分区	容量递减	碎片概率小,但大分区缺乏

动态分区分配的改进算法

快速适应：按常用空间大小分类，设索引表管理
伙伴系统：分区大小为 $2^k$ ，分割/合并都是二分
哈希算法：以空闲分区大小为关键字建哈希表

5.3 分页存储管理方式（⭐⭐⭐）

基本概念

页面（页）：进程地址空间分成的固定大小区域（如4KB）
物理块（页框/帧）：内存空间分成的同大小区域
页内碎片（内碎片）：最后一页装不满一块

地址计算公式⭐

$P = INT\left[\frac{A}{L}\right] \quad d = A \mod L$

其中 $A$ = 逻辑地址， $L$ = 页面大小， $P$ = 页号， $d$ = 页内偏移

页表

每个进程一张页表
作用：页号 → 物理块号 的映射
页表寄存器PTR：存放页表起始地址和页表长度

地址变换过程（基本分页）

存储管理方式对比

分页地址变换图

从逻辑地址取出页号P和页内偏移d
页号P与页表长度比较 → 若P ≥ 页表长度则越界中断
页表起始地址 + P × 页表项长度 → 找到页表项 → 取物理块号b
物理地址 = b × L + d（即块号拼接页内偏移）

基本分页：访问一个数据需要2次访存（1次查页表+1次读数据）

快表TLB⭐

TLB命中路径图

虚拟地址翻译流程

引入TLB后：先查TLB(命中则1次访存)，未命中则查页表(2次访存)并更新TLB。

$EAT = h\,(t_{TLB}+t_m) + (1-h)\,(t_{TLB}+2t_m)$

其中 $h$ = TLB命中率， $t_{TLB}$ = TLB访问时间， $t_m$ = 内存访问时间。

等价写法： $EAT = 2t_m + t_{TLB} - h\,t_m$ 。

两级页表

32位地址空间，4KB页面 → 页表项1M个 → 页表占4MB → 不现实
解决：对页表也分页！
逻辑地址：|外层页号P1(10位)|外层页内地址P2(10位)|页内偏移d(12位)|
需要3次访存（访问外层页表→访问页表→访问数据）

多级页表

64位系统需要更多级（如x86-64用4级页表）
每增加一级多一次访存

反置页表

按物理块号而非页号组织：每个物理块对应一个表项
表项内容：页号 + 进程标识符PID
减少页表内存占用
可用哈希加速检索

5.4 分段存储管理方式

分段的引入目的

方便编程（逻辑分段）
信息共享（以段为单位共享）
信息保护
动态链接
动态增长

分段的基本原理

作业地址空间分为若干段，每段有段名和段长
逻辑地址：|段号S|段内地址d|（二维地址）
段表项：段号 + 段长 + 基址（起始地址）

段的地址变换

段号S与段表长度比较 → 若S ≥ TL则越界中断
由段表找到段表项 → 取段长和起始地址
段内地址d与段长比较 → 若d ≥ SL则越界中断（⭐两次越界检查！）
物理地址 = 起始地址 + d

分页 vs 分段（⭐⭐⭐必考）

分段与段页式对比图

比较项	分页	分段
目的	系统管理的需要,提高内存利用率	用户的需要,满足编程和使用
单位性质	页是信息的物理单位	段是信息的逻辑单位
大小	固定,由系统/硬件决定	不固定,由用户程序决定
地址维度	一维（页号+偏移自动划分,用户不可见）	二维（需给出段名和段内地址）
碎片	内碎片	外碎片

可重入代码（纯代码）

允许多个进程同时访问的代码
不允许任何修改
可修改的部分放在各进程的局部数据区

5.5 段页式存储管理方式

先分段,每段再分页
逻辑地址：|段号S|段内页号P|页内偏移d|
段表项：页表起始地址 + 页表长度
需要3次访存（段表→页表→数据）
实际中加TLB减少访存次数

5.6 IA-32/x86-64内存管理

IA-32

分段+分页：CPU生成逻辑地址→分段单元→线性地址→分页单元→物理地址
Linux在IA-32上仅最低限度使用段
4KB页使用二级页表（10+10+12）
PAE扩展为三级页表,支持36位物理地址(64GB)

x86-64

四级页表,48位虚地址,支持52位物理地址
页面大小可为4KB/2MB/1GB

🎯 本章真题锚点与最短模板

高频题号（2009-2025）：2009Q26/Q27、2010Q28/Q29、2016Q28、2019Q31、2024Q25/Q27、2025Q22
优质例题：已知逻辑地址长度、页大小、页表项大小，求页号位数/页内偏移位数/页表占用空间。
最短解题模板：
1. 先拆位：偏移位数 = $\log_2(页大小)$ 。
2. 页号位数 = 逻辑地址位数 - 偏移位数。
3. 页表空间 = 页数 × 页表项大小，注意单位统一（B/KB）。

⚡ 秒杀版口令卡（10秒回忆）

口令：先偏移后页号，最后算页表。
口令：页号=高位，页内偏移=低位。
口令：所有计算先统一单位。

第六章虚拟存储器

6.1 虚拟存储器概述

局部性原理⭐

时间局部性：刚访问的单元不久会被再访问（循环）
空间局部性：刚访问的单元附近的单元不久会被访问（顺序执行）

传统存储管理特征 vs 虚拟存储器

特征	传统	虚拟
一次性	必须一次性全部装入	多次性：允许分多次调入
驻留性	一直驻留到结束	对换性：允许换入换出
—	—	虚拟性：逻辑扩大内存

虚拟存储器三大特征：多次性（最重要）、对换性、虚拟性 虚拟性以多次性和对换性为基础，多次性和对换性建立在离散分配方式上

虚拟存储器的实现方式

请求分页存储管理（最常用）：以页为单位换入/换出
请求分段存储管理：以段为单位换入/换出

6.2 请求分页存储管理方式

请求页表项

页号	物理块号	状态位P	访问字段A	修改位M	外存地址

P（存在位）：该页是否在内存中（1在/0不在）
A（访问字段）：记录访问次数或多久未访问,供置换算法参考
M（修改位/脏位）：该页是否被修改过,供换出时决定是否写回
外存地址：该页在外存的位置

缺页中断⭐

发生在指令执行期间（不同于一般中断在指令执行后检查）
一条指令可能产生多次缺页中断（极端情况下可达6次：指令本身跨页最多2次 + 源操作数跨页最多2次 + 目的操作数跨页最多2次）

内存分配策略

策略	分配	置换	适用/特点
固定分配局部置换	固定物理块数	从本进程页面中选换出	物理块数难确定
可变分配全局置换	可变	从所有进程中选换出	最易实现,但可能影响其他进程
可变分配局部置换	可变	从本进程中选换出,可动态增减	兼顾灵活和隔离

页框分配与回收（新增强化）

常见页框分配算法

等额分配：每个进程平均分配相同数量页框
比例分配：按进程大小（页数）比例分配页框
优先级分配：高优先级进程获得更多页框（缺页时可从低优先级进程回收）

回收策略要点

局部回收：仅在本进程驻留集中置换，隔离性好
全局回收：可跨进程选牺牲页，系统吞吐量高但会互相干扰
后台回收：系统在空闲或阈值触发时批量回收脏页并维护空闲页框池

考试常用结论：页框过少会触发抖动；页框分配和页面置换需配合工作集思想联合判断。

缺页率

$f = \frac{F}{A} = \frac{F}{S+F}$

影响因素：页面大小、分配的物理块数、页面置换算法、程序局部性

6.3 页面置换算法（⭐⭐⭐必考）

页面置换算法对比

OPT（最佳页面置换算法）

淘汰未来最长时间不会被访问的页
最低缺页率，但不可实现（需预知未来）
用作评价其他算法的标准

FIFO（先进先出）

淘汰最早进入内存的页
实现简单（FIFO队列）
Belady异常：增加物理块数反而缺页率上升！⭐
实际应用极少

LRU（最近最久未使用）⭐

淘汰最近最久未使用的页
向前看（基于历史）对比OPT向后看（基于未来）
性能接近OPT
需要硬件支持：移位寄存器或栈

⚠️ LRU不会出现Belady异常（属于"栈算法"类）

LFU（最少使用）

淘汰一段时间内使用次数最少的页
用移位寄存器记录访问频率

Clock（时钟/NRU）⭐

简单Clock：循环队列,每页一个访问位A
- 若A=0 → 换出
- 若A=1 → 置A=0,给第二次机会,检查下一页
又称二次机会算法/NRU（最近未用）

改进型Clock⭐

同时考虑访问位A和修改位M
四类页面优先级：

类别	A	M	含义	淘汰优先级
第1类	0	0	未访问,未修改	最优先淘汰
第2类	0	1	未访问,已修改	次优先
第3类	1	0	已访问,未修改	可能再被访问
第4类	1	1	已访问,已修改	最不应淘汰

扫描过程：

第1轮找(0,0)不改A
找不到则第2轮找(0,1)同时把扫过的A置0
还找不到则重复1-2（此时A都已为0,必能找到）

页面缓冲算法 PBA

设空闲页面链表+修改页面链表

页面置换手工模拟示例（⭐⭐⭐ 必练）

题目：3个物理块，访问串 $7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1$ ，分别用 FIFO 和 LRU 计算缺页次数。

FIFO（淘汰最早进入的页）：

访问 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
块1 7 7 7 2 2 2 2 4 4 4 0 0 0 0 0 0 0 7 7 7
块2 0 0 0 0 3 3 3 2 2 2 2 2 1 1 1 1 1 0 0
块3 1 1 1 1 0 0 0 3 3 3 3 3 2 2 2 2 2 1
缺页 ✗ ✗ ✗ ✗ ✗ ✗ ✗ ✗ ✗ ✗ ✗ ✗ ✗ ✗ ✗

FIFO 缺页 15 次，缺页率 = 15/20 = 75%

LRU（淘汰最近最久未使用的页）：

访问 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
块1 7 7 7 2 2 2 2 4 4 4 0 0 0 1 1 1 1 1 1 1
块2 0 0 0 0 3 3 3 3 3 3 3 3 3 2 2 2 7 7 7
块3 1 1 1 1 0 0 2 2 2 2 2 2 2 0 0 0 0 0
缺页 ✗ ✗ ✗ ✗ ✗ ✗ ✗ ✗ ✗ ✗ ✗ ✗ ✗

LRU 缺页 12 次，缺页率 = 12/20 = 60%

结论：LRU(12次) < FIFO(15次)，LRU性能更优且无Belady异常。

📝 答题提醒：画表时每一步标清"淘汰了谁"和"新换入谁"，缺页打 ✗ ，命中留空。

换出时不立即写盘,而是挂在链表上
后续需要该页时可直接从链表取回（避免磁盘I/O）
修改页面积累到一定数量后批量写盘

6.4 "抖动"与工作集

抖动（颠簸）

定义：进程大部分时间用于页面置换而非有效计算
原因：分配给进程的物理块太少
多道程序度过高→物理块不足→频繁缺页→I/O繁忙→CPU利用率下降

工作集 w(t, Δ)

定义：进程在时间间隔 $(t-\Delta, t)$ 中实际访问的页面集合
$\Delta$ 为窗口尺寸
工作集大小是 $\Delta$ 的非降函数

抖动预防方法

局部置换策略：限制影响范围
工作集算法融入调度：确保驻留集足够才调入新作业
L=S准则：L(缺页间平均时间)≈S(平均缺页服务时间)时最优
挂起进程：减少多道程序度

6.5 请求分段存储管理

请求段表项

在普通段表项基础上增加：存取方式、访问字段A、修改位M、存在位P、增补位、外存地址

增补位

请求分段特有字段
表示该段在运行过程中是否做过动态增长

共享段表

count（共享计数）：记录共享该段的进程数，count为0时才回收
存取控制：不同进程可有不同的读写权限
段号：不同进程中可有不同的段号

分段保护

越界检查：段号 vs 段表长度；段内地址 vs 段长
存取控制检查：只读/只执行/读写
环保护机构：低编号环=高特权，程序可调用内环服务，可访问外环数据

🎯 本章真题锚点与最短模板

高频题号（2009-2025）：2009Q46、2010Q46、2011Q28/Q29、2014Q30、2015Q27/Q30、2016Q26/Q29、2018Q45、2019Q29、2024Q45、2025Q25/Q28/Q29
优质例题：4页框下访问串 1,2,3,4,1,2,5,1,2,3,4,5，比较FIFO与LRU缺页次数并判断Belady异常。
最短解题模板：
1. 画页框时间表（每一步记录页框内容）。
2. 命中不替换，缺页按算法选牺牲页。
3. 汇总缺页次数并比较：FIFO可能Belady，LRU通常不出现。

⚡ 秒杀版口令卡（10秒回忆）

口令：置换必画表，口算易翻车。
口令：命中不动，缺页才换。
口令：FIFO有Belady，LRU更稳。

第七章输入/输出系统

7.1 I/O设备分类

分类方式	类型	示例
按使用特性	存储设备 / 输入设备 / 输出设备 / 交互式设备	磁盘 / 键盘 / 打印机 / 显示器
按传输速率	低速 / 中速 / 高速	键盘 / 打印机 / 磁盘
按共享属性	独占设备 / 共享设备 / 虚拟设备	打印机 / 磁盘 / SPOOLing
按传输单位	块设备 / 字符设备	磁盘 / 键盘

7.2 设备控制器

设备控制器的组成

设备控制器与CPU的接口：数据线+地址线+控制线，含数据寄存器、控制/状态寄存器
设备控制器与设备的接口：数据/控制/状态信号
I/O逻辑：对命令译码，选择设备

CPU与控制器通信方式

特定I/O指令形式：专门的I/O指令（如io-store）
内存映像I/O：把设备寄存器地址映射到内存地址空间，用普通存取指令访问

7.3 I/O通道

通道类型	工作方式	适用设备	特点
字节多路通道	按字节交叉	低速设备	含多个非分配型子通道,轮流使用
数组选择通道	按数据块,独占	高速设备	一次只服务一个设备,利用率低
数组多路通道	按数据块,多路	高/中速设备	既高速又高利用率

瓶颈问题解决：增加通路（一个设备连多个控制器，一个控制器连多个通道）

7.4 I/O控制方式（⭐⭐⭐）

方式	数据传送单位	CPU干预程度	特点
程序直接控制（轮询）	字节	极高(忙等)	CPU与设备串行,CPU利用率极低
中断驱动	字节	每字节中断一次	CPU与设备可并行,但高速设备中断太频繁
DMA	数据块	每块中断一次	4个寄存器:CR/MAR/DR/DC；数据直接内存↔设备
通道	一组数据块	仅启动和完成时干预	执行通道程序,CPU/通道/设备三者并行

DMA控制器4个寄存器

CR（命令寄存器）：存放CPU命令
MAR（内存地址寄存器）：数据在内存的起始地址
DR（数据寄存器）：暂存传送数据
DC（数据计数器）：本次传送的字节数

I/O软件层次图

7.5 I/O软件层次

从低到高：

中断处理程序：最底层，直接与硬件交互
设备驱动程序：抽象I/O请求→具体设备命令
与设备无关的I/O软件：设备命名、保护、分配、缓冲
用户层I/O软件：库函数、SPOOLing

7.6 设备分配

设备分配相关数据结构

DCT（设备控制表）：每个设备一张
COCT（控制器控制表）：每个控制器一张
CHCT（通道控制表）：每个通道一张
SDT（系统设备表）：全系统一张，记录所有设备

SPOOLing（假脱机技术）⭐

将物理上的独占设备改造为逻辑上的共享设备
组成：输入井+输出井（在磁盘上）+ 输入缓冲区+输出缓冲区（在内存中）+ 输入/输出进程
典型应用：共享打印机（多个进程的打印请求放入磁盘输出井排队，由守护进程依次打印）

7.7 缓冲区管理⭐

缓冲引入原因

缓和CPU与I/O设备间的速度不匹配
减少I/O中断次数
解决基本数据单元大小不匹配

传输时间计算⭐

设 $T$ = 设备传送一块数据时间， $M$ = 将缓冲区数据传入用户区时间， $C$ = CPU处理一块数据时间

缓冲类型	每块平均处理时间
单缓冲	$\max(C, T) + M$
双缓冲	$\max(C+M, T)$

缓冲池

4种缓冲区：收容输入(hin)、提取输入(sin)、收容输出(hout)、提取输出(sout)

7.8 磁盘

磁盘访问时间⭐

$T_a = T_s + T_r + T_t$

$T_s$ （寻道时间）：磁头移到目标磁道
$T_r$ （旋转延迟）：等转到目标扇区。平均 $T_r = \frac{1}{2r}$ （ $r$ 为转速）
$T_t$ （传输时间）： $T_t = \frac{b}{rN}$ （ $b$ 为字节数， $N$ 为每磁道字节数）

磁盘调度算法⭐⭐⭐

磁盘结构示意图

磁盘调度轨迹对比

算法	策略	优缺点
FCFS	先来先服务	公平但效率低
SSTF	最短寻道时间优先	性能好但可能饥饿
SCAN（电梯）	单方向扫到头再折返	消除饥饿,对中间磁道有利
LOOK	单方向扫描到该方向最远请求即折返	避免无效扫到端点,平均寻道更优
C-SCAN（循环扫描）	单方向扫到头,快速返回起点重新扫	更均匀的等待时间
C-LOOK	单方向扫描到最远请求后,快速回到最小请求再扫	比C-SCAN更少无效移动
N-Step-SCAN	将请求队列分段,段内SCAN	避免磁臂粘着
FSCAN	两个子队列,一个当前服务,新请求入另一个	避免磁臂粘着

磁盘调度手工计算示例（⭐⭐ 高频选择/大题）

题目：磁盘请求队列为 $\{98, 183, 37, 122, 14, 124, 65, 67\}$ ，当前磁头在 53 号磁道，磁头正向磁道号增大方向移动。分别用 FCFS、SSTF、SCAN 计算总移动磁道数。

FCFS（按请求到达顺序）： $53→98→183→37→122→14→124→65→67$ 移动量 = $|53-98|+|98-183|+|183-37|+|37-122|+|122-14|+|14-124|+|124-65|+|65-67|$ $= 45+85+146+85+108+110+59+2 = \mathbf{640}$

SSTF（每次选最近磁道）： $53→65→67→37→14→98→122→124→183$ 移动量 = $12+2+30+23+84+24+2+59 = \mathbf{236}$

SCAN（电梯算法，先向大方向扫到最远请求再折返）： $53→65→67→98→122→124→183→37→14$ 移动量 = $12+2+31+24+2+59+146+23 = \mathbf{299}$

⚠️ LOOK vs SCAN：LOOK 扫到该方向最远请求（183）即折返；SCAN 扫到磁盘端点（如199）才折返。题目需看清"SCAN"还是"LOOK"。

🎯 本章真题锚点与最短模板

高频题号（2009-2025）：2009Q32、2010Q32、2011Q26/Q32、2012Q24/Q26、2017Q32、2022Q30、2025Q23
优质例题：比较程序直接控制/中断/DMA三种方式下CPU参与程度，并计算DMA每秒CPU占用比。
最短解题模板：
1. 先判传输粒度：程序/中断=字节，DMA=块。
2. CPU开销 = 次数 × 每次处理时间。
3. CPU占比 = CPU开销 / 总时间。

⚡ 秒杀版口令卡（10秒回忆）

口令：轮询最忙，中断次之，DMA最省CPU。
口令：DMA传块，CPU只管前后处理。
口令：占比=总CPU开销/总时长。

第八章文件管理

8.1 文件的逻辑结构

类型	说明
有结构文件（记录式）	顺序文件、索引文件、索引顺序文件、直接/哈希文件
无结构文件（流式）	字节序列,无明确结构

索引顺序文件（ISAM）补充

按关键字顺序组织主文件，并建立分层索引加速检索
插入新记录常先进入溢出区，再定期重组主文件
兼顾顺序访问与按键检索，适合“读多改少”的场景

🎯 本章真题锚点与最短模板

高频题号（2009-2025）：2009Q30/Q31、2014Q29/Q46、2015Q29、2017Q26/Q30/Q31、2018Q46、2020Q23/Q24/Q31、2022Q46、2024Q26/Q29、2025Q27/Q30/Q31
优质例题：i-node含“12直接+1一级+1二级+1三级间接”，给块大小与指针大小，求最大文件长度。
最短解题模板：
1. 每级可索引块数 = 块大小 / 指针大小。
2. 总容量 = 直接块 + 一级 + 二级 + 三级，对应逐级乘方。
3. 最终统一换算为KB/MB/GB并标明单位。

⚡ 秒杀版口令卡（10秒回忆）

口令：先算每级扇出，再逐级乘方。
口令：直接+一级+二级+三级，缺一项都丢分。
口令：硬链接同iNode，软链接存路径。

8.2 文件目录

FCB（文件控制块）

包含：文件名、类型、大小、物理地址（起始块号）、创建/修改时间、存取控制信息等

索引节点（i-node）⭐

将FCB中除文件名外的信息提取出来形成索引节点
目录项仅含文件名+索引节点号
显著减小目录项大小→提高目录检索效率
磁盘索引节点：存放在磁盘上
内存索引节点：打开文件时调入内存，增加引用计数等字段

目录结构

结构	说明
单级目录	唯一目录,不允许重名
两级目录	MFD（主文件目录）+ UFD（用户文件目录）
树形目录	多级层次,用绝对路径/相对路径定位
无环图目录（DAG）	支持共享子目录/文件

目录检索

线性检索法：顺序查找
Hash方法：用文件名哈希直接定位（需解决冲突）

8.3 文件共享

方式	原理	优缺点
硬链接	不同目录项指向同一索引节点，count引用计数	删除只count-1,count=0才真正删除；目录通常禁建硬链接防环
软链接（符号链接）	创建一个LINK类型文件,存放被链接文件的路径名	额外I/O开销（需解析路径）,被删除后变悬空链接

8.4 文件保护

访问矩阵

行=域(用户),列=对象(文件),元素=权限集合
太大难以存储→实际实现：

方式	原理	特点
ACL（访问控制列表）	按列存储,每个文件记录哪些用户有何权限	精简为owner/group/other三类
能力表	按行存储,每个用户记录可访问哪些文件	用户持有能力列表

特殊权限

复制权R'：能将权限复制给同一列其他域
所有权O：能授予/取消同一列其他域的权限
控制权：能修改同一行其他对象的权限

8.5 Linux文件系统

VFS四个对象

superblock（超级块）：整个文件系统的信息
dentry（目录项）：路径中的一个分量
iNode（索引节点）：文件的元信息
file（文件对象）：进程已打开的文件

ext2文件系统

块组结构：超级块 + 组描述符 + 块位图 + iNode位图 + iNode表 + 数据块
iNode 128B,含15个块指针i_block：
- i_block[0-11]：12个直接块
- i_block[12]：一次间接块
- i_block[13]：二次间接块
- i_block[14]：三次间接块

文件系统层次结构

iNode索引结构

⚠️ 口径提示：此处是 ext2 的“12直接 + 1一级 + 1二级 + 1三级”；而经典UNIX教材常写“10直接 + 3级间接”，两者来源不同，不矛盾。

8.6 文件操作与打开文件表（高频补强）

两级打开文件表

系统打开文件表（全局）
- 记录：文件元信息引用（如iNode指针）、打开方式、当前偏移量、引用计数等
进程打开文件表（每进程）
- 记录：该进程持有的文件描述符 fd 与系统打开文件表项的对应关系

关键关系：fd 本质是“进程打开文件表的索引”，再间接指向系统打开文件表。

`open()` 典型路径

按路径检索目录项，定位目标文件iNode
做权限检查与打开方式检查
在系统打开文件表建立/复用表项（引用计数+1）
在进程打开文件表分配一个空闲 fd 并返回

`close()` 典型路径

根据 fd 找到进程打开文件表项并清除
对应系统打开文件表项引用计数减1
若引用计数为0，按需回写并释放相关内核对象

常考辨析

多个 fd 可指向同一系统打开文件表项（如 dup、fork 后继承）
若共享同一系统表项，文件偏移量通常联动变化；若分别 open，偏移量通常独立

第九章磁盘存储器管理

9.1 外存组织方式

连续分配

目录项：文件名 + 起始盘块号 + 长度
优点：顺序访问快/支持随机访问
缺点：外碎片/需预知文件大小

链接分配

隐式链接：每个盘块含指向下一盘块的指针
- 仅支持顺序访问
显式链接（FAT）：文件分配表放在内存中
- FAT12（簇）/ FAT16（≤2048MB）/ FAT32（簇4KB,≤1TB,单文件≤4GB）/ NTFS
- 支持随机访问

索引分配

单级索引：一个索引块记录所有盘块号
多级索引：索引块不够时,索引块指向索引块
增量式混合索引（UNIX）⭐：

地址项	类型	4KB块时可寻址容量
i.addr(0)~i.addr(9)（经典UNIX）	直接地址	10×4KB = 40KB
i.addr(10)	一次间接	1K×4KB = 4MB
i.addr(11)	二次间接	1K×1K×4KB = 4GB
i.addr(12)	三次间接	1K×1K×1K×4KB = 4TB

⚠️ 口径提示：本表采用经典UNIX教材口径；与上章ext2的12个直接块写法属于不同文件系统实现。

9.2 空闲空间管理

方法	原理	特点
空闲区表法	表项（起始块号+空闲块数），FF/BF分配	连续分配适用
空闲链表法	盘块链（效率低）/ 盘区链（FF,效率高）	链接分配适用
位示图法⭐	每个盘块1bit，0空闲/1占用	简单高效
成组链接法（UNIX）	空闲盘块号栈（100个），栈底指向下一组	大型文件系统

位示图计算公式⭐

盘块号 $b$ → 位示图位置 $(i, j)$ ：

$i = (b-1) \div n + 1, \quad j = (b-1) \mod n + 1$

位示图 $(i, j)$ → 盘块号 $b$ ：

$b = n \times (i-1) + j$

其中 $n$ 为位示图每行的位数。

⚠️ 编号约定：上述公式按“盘块号与位示图行列均从1开始编号”给出；若题目采用0起编号，需整体平移后再代入。

成组链接法（UNIX）

空闲盘块号栈：存放100个空闲盘块号
栈底（第一个单元）存放下一组100个空闲盘块号所在的盘块号
分配：从栈顶取一块；栈空则将栈底指示的下一组读入
回收：盘块号压入栈顶；栈满则将当前100个写入回收块,该块号成为新栈底

9.3 磁盘容错与RAID

RAID级别

RAID 0：条带化,无冗余
RAID 1：镜像,100%冗余
RAID 5：分布式奇偶校验
RAID 6：双校验

软件容错技术（SFT）

SFT-I：双份目录、双份FAT、热修复重定向、写后读校验
SFT-II：磁盘镜像/磁盘双工
基于集群的容错：服务器镜像

9.4 存储新技术

技术	连接方式	访问级别	特点
DAS	直连主机	块级	简单/成本低/容量有限
NAS	网络附加(NFS/SMB)	文件级	共享方便
SAN	存储区域网(光纤)	块级	高性能/高可靠

9.5 数据一致性

事务

原子性：要么全做要么全不做
日志记录：(事务名, 数据项名, 旧值, 新值)
undo（事务未完成时恢复旧值）/ redo（事务已完成时重做新值）

检查点

定期在日志中记录检查点
恢复时只处理检查点之后的事务

并发控制

互斥锁 / 共享锁（类似读者-写者问题）

🎯 本章真题锚点与最短模板

高频题号（2009-2025）：2009Q29、2010Q45、2012Q32、2015Q31/Q32、2019Q44、2021Q28、2024Q32、2025Q32
优质例题：给定初始磁头位置与请求序列，分别按FCFS、SSTF、SCAN计算总移动磁道数。
最短解题模板：
1. 先按算法确定访问顺序。
2. 总移动量 = 相邻访问磁道差绝对值求和。
3. 需要时间时再乘“每磁道移动时间”并加旋转/传输延迟。

⚡ 秒杀版口令卡（10秒回忆）

口令：先排顺序，再算移动量。
口令：时间=寻道+旋转+传输。
口令：SSTF快但可能饿死远端请求。

第十章多处理机操作系统

10.1 多处理机系统类型

类型	耦合度	通信延迟	特点
紧密耦合	共享存储器	10~50ns	SMP/ASMP
松散耦合	各自OS，通过通信链路连接	10~50ms	分布式

UMA结构（4种）

结构	CPU数	特点
单总线	4~20	可加高速缓存
多总线	16~32	私有存储器
单级交叉开关	8~16	N²交叉点
多级交换网络	<100	分散流量

NUMA

多节点,3层存储：本地→群内共享→全局共享
CC-NUMA：高速缓存+目录表保证一致性
主要问题：远程访问时延

10.2 多处理机OS类型

类型	特点	优缺点
主从式	一个主处理机负责管理	简单但资源利用率低/主机瓶颈
独立监督式	每个处理机有自己的OS	自主可靠但复杂/负载不均
浮动监督式	管理功能可在处理机间浮动	最灵活/最可靠/负载均衡,实现复杂

10.3 多处理机调度（2025新增重点⭐）

多处理机调度策略（2025新增）⭐

策略	描述	优点	缺点
全局队列调度	OS维护一个公共就绪队列	负载均衡最好	随着CPU增多,临界区锁竞争加剧
私有队列调度	每个CPU维护私有就绪队列	亲和性(Affinity) 好,Cache命中率高	可能导致负载不均,需迁移机制

调度对应关系

单处理机调度：解决“何时执行”
多处理机调度：解决“何时执行” + “在哪执行”

调度策略算法

负载分配（Load Sharing）：通过推/拉机制在私有队列间平衡负载。
群组调度（Gang Scheduling）：将一个进程的所有相关线程同时调度到一组CPU上并行运行。
- 目的：减少同步阻塞（避免“互相等的线程没在运行”）。
专用处理器分配：某个应用长期独占一组CPU（适用于科学计算）。

10.4 多处理机上的进程同步

自旋锁⭐

适用于多处理机的互斥机制
循环测试锁变量（忙等），不阻塞不切换
vs 信号量：自旋锁避免了阻塞和进程切换开销,适用于短临界区
实现：总线设锁变量，循环Test-and-Set

🎯 本章真题锚点与最短模板

高频题号（2009-2025）：近年独立命题少；与新增考纲“多处理机调度”强相关（2025起新增）
优质例题：对比SMP中“公共就绪队列”与“私有就绪队列”的优缺点，判断何时需要负载均衡迁移。
最短解题模板：
1. 先判系统模型：ASMP 还是 SMP。
2. 再判调度策略：亲和性优先还是吞吐优先。
3. 结论用三词：可扩展性、均衡性、迁移开销。

⚡ 秒杀版口令卡（10秒回忆）

口令：SMP看均衡，ASMP看主控。
口令：自旋锁短临界区，信号量长临界区。
口令：亲和性提局部性，迁移有代价。

第十一章虚拟化和云计算

11.1 虚拟化

VMM类型

类型	位置	示例
Type1（裸金属型）	直接运行在硬件上	Xen, ESXi, KVM
Type2（寄居型）	运行在宿主OS之上	VMware Workstation, VirtualBox

虚拟化前提

敏感指令 ⊆ 特权指令（Popek-Goldberg准则）
80x86不满足此条件 → Intel VT / AMD-V硬件辅助

虚拟化实现方式

方式	是否需修改Guest OS	技术
全虚拟化	否	二进制翻译
半虚拟化	是（使用hypercalls）	Xen的para-virtualization
硬件辅助虚拟化	否	VT-x,根模式/非根模式

CPU虚拟化

vCPU：虚拟CPU
指令执行：解释/扫描修补/二进制翻译/硬件辅助
上下文切换：VMCS（虚拟机控制结构）

内存虚拟化

两级映射：GVA→GPA→HPA
实现：影子页表（软件维护,开销大）或 EPT/NPT（硬件辅助二维页表,效率高）

I/O虚拟化

全设备模拟 / 半虚拟化（前后端驱动）/ 直接I/O（VT-d）

11.2 云计算

NIST定义的5个特征

按需自助服务
广泛的网络接入
资源池化
快速弹性伸缩
可计量服务

服务模型

SaaS（软件即服务）：如Gmail
PaaS（平台即服务）：如Google App Engine
IaaS（基础设施即服务）：如AWS EC2

VM迁移

静态迁移：关机→复制→启动
动态（在线）迁移4阶段：①开始 ②迭代传输（脏页） ③挂起+复制剩余脏页 ④提交+激活

🎯 本章真题锚点与最短模板

高频题号（2009-2025）：2025Q24（虚拟化），其余年份多与系统结构综合考查
优质例题：判断Type1/Type2 VMM部署位置，并比较全虚拟化与半虚拟化是否需要修改Guest OS。
最短解题模板：
1. 先看VMM位置：在硬件上=Type1；在宿主OS上=Type2。
2. 再看Guest改动：要改Guest多为半虚拟化。
3. 最后补一句：硬件辅助虚拟化依赖VT-x/AMD-V。

⚡ 秒杀版口令卡（10秒回忆）

口令：Type1贴硬件，Type2压宿主。
口令：改Guest多半虚拟，不改多全虚拟。
口令：硬件辅助记VT-x/AMD-V。

第十二章保护和安全

12.1 安全目标 CIA

目标	含义
机密性(Confidentiality)	防止未授权访问
完整性(Integrity)	防止未授权修改
可用性(Availability)	合法用户能及时获得服务

12.2 安全等级（TCSEC）

D → C1 → C2 → B1 → B2 → B3 → A（安全性递增）

等级	名称	特点
D	最小保护	无安全特性,如MS-DOS
C1	自主安全保护	用户登录,访问控制
C2	受控制的访问保护	审计功能,如Windows NT
B1	标记安全保护	强制访问控制
B2	结构保护	形式化安全模型
B3	安全域	可信恢复
A	验证设计	形式化验证

12.3 加密

方法	说明
易位法	改变明文字符排列顺序
置换法（替换密码）	用其他字符替换明文字符
对称加密（DES等）	加密和解密用同一密钥(64位)
非对称加密（公钥密码）	公钥 $K_e$ 加密,私钥 $K_d$ 解密

数字签名

简单签名：用发方私钥 $K_{dA}$ 加密
保密签名：先用发方私钥加密(签名),再用收方公钥加密(保密)

数字证书

CA（证书授权机构）签发
包含：公钥+持有者信息+CA签名

12.4 用户验证

方式	示例
口令	密码
一次性口令	动态验证码
物理标志	IC卡/U盾
生物识别	指纹/虹膜/面部

12.5 安全威胁

内部攻击

特洛伊木马：隐藏在正常程序中的恶意代码
登录欺骗：伪造登录界面窃取密码
逻辑炸弹：在特定条件下触发的恶意代码
陷阱门（后门）：绕过安全检查的秘密入口
缓冲区溢出：最常见的攻击手段之一

外部攻击

病毒：寄生于宿主程序，可自我复制
蠕虫：独立运行，通过网络自我传播
移动代码：通过网络传播的代码（如Java Applet）

🎯 本章真题锚点与最短模板

高频题号（2009-2025）：近年在408中独立命题较少，常以内核态/特权指令/系统调用安全边界形式融合出题（如2012Q23、2015Q24）
优质例题：给定攻击场景（木马/蠕虫/缓冲区溢出），判断攻击类别并匹配防护手段（认证/访问控制/加密）。
最短解题模板：
1. 先判攻击载体：宿主依赖=病毒；独立传播=蠕虫。
2. 再判防线层次：身份认证→授权控制→数据加密。
3. 最后对照CIA三目标：机密性、完整性、可用性。

⚡ 秒杀版口令卡（10秒回忆）

口令：CIA三目标：机密、完整、可用。
口令：病毒要宿主，蠕虫可独立。
口令：安全三层：认证→授权→加密。

附录：408操作系统冲刺总览

一、408考纲变化与命题趋势（2021-2026）

年份	变化内容	命题影响
2021-2024	操作系统核心框架稳定（进程/内存/文件/I/O）	题型相对稳定：选择+PV大题
2025	明确新增：信号（Signal）、多处理机调度；“页框分配”表述扩展为“页框分配与回收”	2026起高概率考查新增概念辨析题
2026备考	继续强调“程序运行环境、内存映像、虚拟化、VFS”	跨章节综合题概率上升

二、应试技巧（高分版）

选择题策略（20分）

先做“概念判断题”（状态转换/中断异常/文件链接），再做“计算题”（调度/分页/置换/磁盘调度）。
对计算题统一采用“先列公式→再代数值→最后写单位”的三步法，避免低级算错。
新增考点优先锁定：Signal与Semaphore辨析、页框分配与回收策略、COW触发条件。

大题策略（15分）

PV题：先画前驱关系，再定义信号量含义，最后写P/V序列。
内存题：先拆地址位段（页号/页内偏移），再判TLB/页表命中路径，最后给物理地址。
虚存题：先判“页框分配策略（固定/可变）+置换范围（局部/全局）”，再分析是否抖动。
文件题：先确认分配方式（连续/链接/索引），再算访盘次数和最大文件长度。

零基础30天冲刺法（OS专用）

第1阶段（1-10天）：进程状态、调度算法、PV基础、分页地址变换。
第2阶段（11-20天）：页面置换、银行家算法、磁盘调度、文件索引计算。
第3阶段（21-30天）：17年真题限时套练，按“概念错/计算错/审题错”分类复盘。

三、408跨学科联动速查表（OS视角）

OS知识点	数据结构	计组	计网
进程调度队列	队列/优先队列（堆）	CPI与中断开销	服务器并发请求调度
银行家算法	矩阵运算/图判定	资源竞争与总线仲裁	并发连接资源控制
分页与TLB	哈希（反置页表）/位图	Cache-TLB-主存层次	无
页面置换（LRU/Clock）	栈/链表/循环队列	局部性原理	路由缓存思想类比
文件索引结构	多叉树/B+树思想	磁盘与总线DMA	文件传输协议语义
I/O中断与DMA	生产者-消费者模型	中断机制/DMA/总线	网卡中断与驱动模型

四、408操作系统高频失分陷阱速查表（⭐ 考前必看）

#	陷阱描述	正确结论	章节
1	并发=并行	并发是“同一时间段交替推进”，并行是“同一时刻同时执行”	Ch1
2	用户态可以执行I/O指令	I/O、关中断、设置时钟等均为特权指令，必须核心态执行	Ch1
3	系统调用是普通函数调用	系统调用会触发用户态→核心态切换	Ch1
4	进程是调度基本单位	引入线程后：进程是资源分配单位，线程是调度单位	Ch2
5	时间片用完进程进入阻塞态	时间片用完：执行态→就绪态，不是阻塞态	Ch3
6	SJF不会饥饿	长作业可能长期得不到调度，存在饥饿风险	Ch3
7	死锁=饥饿	死锁是互相等待；饥饿是长期得不到资源	Ch3
8	银行家算法用于死锁检测	银行家算法属于“死锁避免”，核心是安全序列判断	Ch3
9	Peterson算法可用于多进程通用互斥	Peterson原型只直接适用于两进程	Ch4
10	P/V操作一定忙等	记录型信号量可阻塞等待，不必忙等	Ch4
11	分页没有碎片	分页有“页内碎片”，只是没有外碎片	Ch5
12	段号必须在所有进程中一致	共享段可映射到不同进程的不同段号	Ch5
13	FIFO一定优于LRU	FIFO可能出现Belady异常，LRU通常更稳	Ch6
14	缺页中断是外中断	缺页属于内中断（异常）	Ch6
15	DMA不需要CPU参与	DMA仅数据传输阶段不占CPU，前后处理仍需CPU	Ch7
16	软链接和硬链接都共享iNode	只有硬链接共享iNode；软链接是保存路径名的特殊文件	Ch8
17	FAT和iNode可以等价替换	FAT是分配表机制，iNode是元数据索引机制，定位路径不同	Ch8/9
18	RAID 0也有容错	RAID 0只有条带化无冗余，坏一盘可能全盘数据不可用	Ch9
19	Signal就是信号量	Signal是异步事件通知；信号量用于同步互斥与资源计数	Ch2/4
20	`fork`一定立即复制全部内存	现代系统多用COW：写入时才复制页框	Ch2/5
21	页框分配和页面置换可分开判断	二者耦合：分配过少会抖动，需结合工作集评估	Ch6
22	LOOK与SCAN等价	LOOK到最远请求即折返；SCAN会扫到端点再折返	Ch7/9

五、必记公式与易混淆概念速查

必记公式

公式	适用场景
$\bar{T}=\frac{1}{n}\sum T_i$	平均周转时间
$W_i=T_i/T_{si},\ \bar{W}=\frac{1}{n}\sum W_i$	带权周转时间
$R_P = 1 + \frac{\text{等待时间}}{\text{服务时间}}$	HRRN响应比
$P = \left\lfloor\frac{A}{L}\right\rfloor,\ d = A \bmod L$	分页地址计算
$EAT = h(t_{TLB}+t_m)+(1-h)(t_{TLB}+2t_m)$	含TLB有效访存时间
$EAT = (1-p)\,t_m + p\,t_{pf}$	含缺页有效访存时间
单缓冲: $\max(C,T)+M$	缓冲区传输时间
双缓冲: $\max(C+M,T)$	缓冲区传输时间
$T_a = T_s + \frac{1}{2r} + \frac{b}{rN}$	磁盘访问时间
$\text{松弛度}=\text{截止时间}-\text{剩余时间}-\text{当前时间}$	LLF实时调度
$\sum C_i/P_i \leq 1$	EDF判据（隐式截止期 $D_i=P_i$ 时为充要条件）
$U=\sum_{i=1}^{n}\frac{C_i}{P_i}\le n(2^{1/n}-1)$	RM充分可调度条件
$b=n(i-1)+j,\ i=\left\lfloor\frac{b-1}{n}\right\rfloor+1,\ j=(b-1)\bmod n+1$	位示图计算（默认1起编号）
$Need = Max - Allocation$	银行家算法

易混淆概念对比

概念A	概念B	关键区别
并发	并行	并发=宏观同时微观交替（单CPU）；并行=真正同时（多CPU）
进程	线程	进程=资源分配单位；线程=调度单位
死锁	饥饿	死锁=互相等待（都阻塞）；饥饿=长期等不到资源（可处就绪态）
内碎片	外碎片	内碎片=分区内浪费（固定分区/页式）；外碎片=分区间浪费（动态分区/段式）
分页	分段	页=物理单位（系统行为）；段=逻辑单位（用户行为）
中断	异常	中断=外部（I/O/时钟）；异常=内部（除零/缺页/trap）
信号量P	管程wait	P使value-1，可能阻塞；wait一定阻塞并释放管程
信号量V	管程signal	V使value+1（无等待也+1）；signal无等待则空操作
Signal	Semaphore	Signal=事件通知；Semaphore=同步互斥/资源计数
硬链接	软链接	硬链接=共享iNode（count）；软链接=存路径的特殊文件
抢占式	非抢占式	抢占=可中途剥夺CPU；非抢占=运行到完成/阻塞才让出
LRU	LFU	LRU=最久未使用；LFU=访问频率最低
FIFO Belady	LRU无Belady	FIFO增页框可能增缺页（Belady异常）；LRU不会
LOOK	SCAN	LOOK到最远请求即返；SCAN到磁道端点再返

六、秒杀版口令卡总汇（全12章）

Ch1 操作系统引论

外设中断、内部异常、trap入核。
用户态禁特权，系统调用走内核。
判题三步：来源→态切换→干扰项。

Ch2 进程的描述与控制

时间片到=就绪；等I/O=阻塞；I/O完=就绪。
进程管资源，线程管调度。
共享地址空间，私有栈与寄存器。
Signal看事件通知，Semaphore看同步互斥。

Ch3 处理机调度与死锁

调度先画图，不画必错时刻。
周转=完成-到达，带权=周转/服务。
死锁先四条件，再判安全序列。

Ch4 进程同步

先前驱后PV，不画图不下笔。
互斥用mutex，同步用前驱信号量。
缓冲区三件套：mutex、empty、full。

Ch5 存储器管理

先偏移后页号，最后算页表。
页号=高位，页内偏移=低位。
所有计算先统一单位。

Ch6 虚拟存储器

置换必画表，口算易翻车。
命中不动，缺页才换。
FIFO有Belady，LRU更稳。
先判页框分配，再判局部/全局置换。

Ch7 输入/输出系统

轮询最忙，中断次之，DMA最省CPU。
DMA传块，CPU只管前后处理。
占比=总CPU开销/总时长。

Ch8 文件管理

先算每级扇出，再逐级乘方。
直接+一级+二级+三级，缺一项都丢分。
硬链接同iNode，软链接存路径。

Ch9 磁盘存储器管理

先排顺序，再算移动量。
时间=寻道+旋转+传输。
SSTF快但可能饿死远端请求。
LOOK到最远请求即返，SCAN到端点再返。

Ch10 多处理机操作系统

SMP看均衡，ASMP看主控。
自旋锁短临界区，信号量长临界区。
亲和性提局部性，迁移有代价。

Ch11 虚拟化和云计算

Type1贴硬件，Type2压宿主。
改Guest多半虚拟，不改多全虚拟。
硬件辅助记VT-x/AMD-V。

Ch12 保护和安全

CIA三目标：机密、完整、可用。
病毒要宿主，蠕虫可独立。
安全三层：认证→授权→加密。

📝 后记：操作系统高分的关键不是“背定义”，而是把状态转换、地址变换、P/V建模、访盘次数这四类题训练到“看题即建模、落笔即得分”。

加油，未来的北大学子！💪

访问	7	0	1	2	0	3	0	4	2	3	0	3	2	1	2	0	1	7	0	1
块1	7	7	7	2	2	2	2	4	4	4	0	0	0	0	0	0	0	7	7	7
块2		0	0	0	0	3	3	3	2	2	2	2	2	1	1	1	1	1	0	0
块3			1	1	1	1	0	0	0	3	3	3	3	3	2	2	2	2	2	1
缺页	✗	✗	✗	✗		✗	✗	✗	✗	✗	✗			✗	✗			✗	✗	✗

📖 操作系统（Operating System）—— 408考研完全笔记

第一章 操作系统引论

1.1 操作系统的目标和作用

操作系统的四个目标

操作系统的作用

推动OS发展的主要动力

1.2 操作系统的发展过程

1.3 操作系统的基本特性（重点⭐）

四大基本特性

1.4 操作系统的运行环境

处理器的双重工作模式

特权指令与非特权指令

中断与异常

1.5 操作系统的主要功能

现代OS的新功能

1.6 操作系统的结构（重点⭐）

微内核结构

1.7 系统调用

系统调用与一般过程调用的4个主要区别

系统调用的类型

🎯 本章真题锚点与最短模板

⚡ 秒杀版口令卡（10秒回忆）

第二章 进程的描述与控制

2.1 前趋图和程序执行

前趋图（DAG）

程序顺序执行的特征

程序并发执行的特征

2.2 进程的描述

进程的定义

进程的特征

进程的状态

进程控制块 PCB

2.3 进程控制

2.4 进程通信

2.5 线程

线程的概念

进程 vs 线程

线程控制块 TCB

线程的实现方式

多线程模型

轻量级进程(LWP)

2.6 程序运行环境与进程内存映像（2026趋势）

进程内存映像（Memory Image）

fork 与 COW（写时复制）

2.7 信号（Signal）机制（2025新增）

信号的本质

信号处理方式

常见高频信号

生命周期与检查时机

信号 vs 信号量（常考）

🎯 本章真题锚点与最短模板

⚡ 秒杀版口令卡（10秒回忆）

第三章 处理机调度与死锁

3.1 处理机调度的层次

3.2 调度的目标和准则

调度的共同目标

不同系统的目标

重要公式⭐

3.3 调度算法（核心考点⭐⭐⭐）

3.3.1 先来先服务 FCFS

3.3.2 短作业/进程优先 SJF/SPF

3.3.3 优先级调度

3.3.4 高响应比优先 HRRN

3.3.5 时间片轮转 RR

3.3.6 多级队列调度

3.3.7 多级反馈队列调度 MLFQ（⭐⭐⭐）

3.3.8 公平调度

3.4 实时调度

可调度条件

实时调度分类

最早截止时间优先 EDF

Rate Monotonic（RM）补充

最低松弛度优先 LLF

优先级倒置问题⭐

3.5 Linux CFS调度器

3.6 死锁（核心考点⭐⭐⭐）

死锁的定义

死锁的四个必要条件

死锁的处理策略

死锁预防

第一章操作系统引论

第二章进程的描述与控制

第三章处理机调度与死锁

第四章进程同步（核心考点⭐⭐⭐）

第五章存储器管理

第六章虚拟存储器