操作系统 · 公式与知识点大全

约 35 分（选择题 + 综合题）。进程同步(PV)、内存地址转换与页面置换、磁盘调度、调度指标是高频计算点。橙色=易错 · 蓝色=概念 · 红色=必背

一、进程与线程

1. 进程状态转换

三态：就绪 ↔ 运行（调度/时间到）；运行 → 阻塞（等待事件）；阻塞 → 就绪（事件发生）
五态：加新建、终止
挂起：就绪挂起 / 阻塞挂起

运行→阻塞是主动（等I/O）；阻塞→就绪是被动（被唤醒）。就绪→运行由调度触发。

2. 进程 vs 线程

	进程	线程
资源	独立地址空间	共享进程资源
调度	重量级	轻量、CPU调度基本单位
切换	开销大(需换上下文)	开销小
通信	IPC(管道/消息/共享内存)	直接读共享变量

📌 线程是调度单位，进程是资源分配单位。同一进程内线程切换不换地址空间，故更快。

3. 进程控制块 PCB

PCB 含：进程状态、程序计数器、CPU寄存器、内存指针、调度信息、I/O状态。系统靠 PCB 感知和管理进程；"创建进程=建PCB，撤销=回收PCB"。

二、进程同步与 PV 操作核心

1. 信号量机制

P(S)：S = S − 1；若 S<0 则阻塞（等待队列+1）

V(S)：S = S + 1；若 S≤0 则唤醒一个等待进程

互斥信号量初值=1（临界区前后 P/V）；同步信号量初值=0或资源数（前V后P表示顺序约束）。

2. 经典问题套路

生产者-消费者：empty(初N)、full(初0)、mutex(初1) 三信号量；先P同步后P互斥
读者-写者：count+rw_mutex(写互斥)+count_mutex；读者优先/写者优先差异在锁顺序
哲学家进餐：最多允许4人拿筷 / 奇偶策略 / 同时拿双筷(AND信号量)
理发师：customers/waiting/barbers 信号量

📌 PV 题铁律：先检查资源/同步信号量，再进互斥；否则易死锁。记录型信号量 S 为负时其绝对值=等待进程数。

3. 管程 Monitor

管程把共享变量+操作+条件变量封装，任一时刻仅一个进程在管程内活动，用 condition 的 wait/signal 替代显式 PV，降低编程复杂度。

三、死锁

1. 四个必要条件必背

互斥、占有并等待、不可抢占、循环等待

破坏任一条件即可预防死锁。资源分配图含环路且环路每类资源只有一个实例 → 必死锁。

2. 死锁处理

预防：破坏4条件之一（如一次性申请全部资源）
避免：银行家算法，保证系统始终处于安全状态
检测+解除：资源分配图化简 / 终止进程、剥夺资源

银行家：Need = Max − Allocation；安全性检查找安全序列使每进程可被满足

⚠ 银行家算法：Request ≤ Need 且 ≤ Available 才试分配，分配后做安全性算法；找不到安全序列则拒绝。死锁必要不充分：有环路未必死锁（多实例资源可解）。

四、内存管理核心

1. 地址转换（分页）必背

逻辑地址 = 页号 P + 页内偏移 W（P = 逻辑地址 / 页大小，W = 逻辑地址 % 页大小）

物理地址 = 页框号(块号) × 页大小 + W（页框号由页表 P 查得）

页表项位数 = log₂(物理块数)；页号位数 = log₂(页数)

📌 地址结构：若页大小 4KB=2¹²，则低12位是页内偏移，高位是页号。页表长度(项数)=2^页号位。

2. 分段 / 段页式

分段：逻辑地址 = 段号 S + 段内偏移 W；段表存段基址+段限长（保护）

段页式：段号 + 段内页号 + 页内偏移；需查段表+页表，两次映射

分页物理单位、用户无感；分段逻辑单位、便于共享保护；段页式兼得但地址转换慢。

3. 快表 TLB 与多级页表

有效访问时间 ≈ 命中率×TLB+页表访问 + (1−命中率)×(TLB+2×页表)

TLB 命中则省一次内存页表访问。多级页表（如二级）把页表本身分页，减少连续内存占用；64位系统多用4级页表。

4. 虚拟内存

虚拟地址空间 >> 物理内存；局部性原理支撑按需调页

请求分页：访问时若页不在内存则缺页中断，调入。驻留集大小影响缺页率。

五、页面置换算法核心

1. 各类算法

算法	思想	特点
OPT	淘汰最远将来才用到的页	最佳但不可实现（理论下界）
FIFO	淘汰最先进入	实现简单；有Belady异常（分配多反而缺页多）
LRU	淘汰最久未使用	近似OPT，性能好，需硬件支持
CLOCK	环形+访问位，扫到0淘汰	LRU近似，开销小
改进CLOCK	访问位+修改位 (0,0)优先	减少写回开销

⚠ FIFO 是唯一会出现 Belady 异常的算法；LRU 不会。手算题常给页面访问序列，逐帧模拟缺页次数。

2. 缺页率 / 抖动

缺页率 = 缺页次数 / 总访问次数

抖动(Thrashing)：分配页面太少，进程频繁缺页，CPU利用率骤降。工作集 = 某窗口内访问的页面集合；驻留集应≥工作集。

六、文件管理与磁盘

1. 文件物理结构

连续：支持随机访问、易碎片
链接：隐式/显式(FAT)，无外部碎片、随机访问慢
索引：单级/多级/混合索引(Unix)，支持大文件随机访问

混合索引：直接块 + 一级/二级/三级间接；最大文件 = Σ(各级块数)×块大小

2. 磁盘调度（求平均寻道）必背

FCFS：按序，公平
SSTF：最近磁道，可能饥饿
SCAN(电梯)：单向到端再返
C-SCAN：到端回起点，单向服务
LOOK / C-LOOK：到最远请求即返

平均寻道长度 = Σ|移动磁道| ÷ 请求数

3. 磁盘容量与访问时间

容量 = 磁头数 × 柱面数 × 每道扇区数 × 512B

访问时间 = 寻道 + 旋转延迟(1/(2r)) + 传输(b/(r·N))

磁盘空闲管理：位示图、空闲块表、空闲链表、成组链接法（Unix）。

七、I/O 管理

1. I/O 控制方式

程序查询：CPU轮询，忙等
中断驱动：完成后中断
DMA：块传输，仅起止中断
通道：专用处理器执行通道程序

2. 缓冲与 SPOOLing

缓冲：缓解速度 mismatch、减少中断次数、实现DMA。单/双/循环缓冲。

SPOOLing：预输入/缓输出 + 输入/输出井，把独占设备变"共享"，典型打印机

设备独立性：应用程序用逻辑设备名，由系统映射到物理设备。虚拟设备技术核心即 SPOOLing。

八、处理机调度与指标核心计算

1. 调度层次与算法

作业/高级调度：调入内存
中级调度：挂起/激活（调出内存）
低级/进程调度：分派CPU（最频繁）

算法	规则	特点
FCFS	先到先做	公平，长作业友好
SJF/SPF	最短作业/进程优先	平均周转最短，可能饥饿
HRRN	响应比最高优先	兼顾等待与服务
时间片RR	轮流，到时让出	公平，时间片影响吞吐
多级反馈	多级队列+降级	兼顾I/O与CPU型

2. 关键性能指标必背

周转时间 T = 完成时间 − 到达时间

带权周转 W = T / 服务时间　（≥1，越小越好）

平均周转 = ΣT / n；平均带权周转 = ΣW / n

响应比 R = (等待时间 + 服务时间) / 服务时间 = 1 + 等待/服务

📌 调度题：画甘特图逐进程算完成时间，再求 T/W。SJF 使平均周转最小；RR 时间片越小响应越快但切换开销大。