操作系统 PV/死锁/页面置换/调度深化

一句话定位

操作系统综合知识 4~6 题，PV 操作大题几乎每年案例与分析交叉出现；本篇把三大经典同步模型 + 银行家 + 页面置换落成画图 + 伪代码 + 设信号量的默写程度。

A. 进程与线程

进程 vs 线程对比

维度	进程 Process	线程 Thread
资源分配单位	是（独立地址空间）	否（共享进程资源）
调度单位	传统 OS 是	现代 OS 是
系统开销	大（上下文切换）	小
通信方式	IPC（管道/消息/共享内存/Socket）	同步互斥（共享内存）
并发性	较低	高

进程三态/五态转换

正在加载图表…

• 就绪 → 运行：调度（dispatch）
• 运行 → 就绪：时间片到 / 优先级抢占
• 运行 → 阻塞：I/O 请求 / 等待事件
• 阻塞 → 就绪：事件完成

用户级 vs 内核级线程

类型	说明	优点	缺点
用户级	由应用程序管理（如早期 Java 绿线程）	切换快、不陷内核	单进程多核利用差；阻塞影响全部
内核级	由 OS 内核管理	多核并行；阻塞不影响其他	切换开销大
混合	Solaris/LWP 轻量级进程	兼顾两者	实现复杂

B. 进程调度算法（必考 1 题）

五种调度算法对比

算法	全称	原理	优点	缺点	适用
FCFS	First Come First Served	先来先服务	公平、简单	护航效应、平均等待长	批处理
SJF	Shortest Job First	短作业优先	平均等待最短	饥饿长作业	作业调度
SRTF	Shortest Remaining Time First	SJF 抢占版	响应更好	切换开销	交互系统
RR	Round Robin	时间片轮转	响应快、公平	时间片过大退化 FCFS	分时系统
优先级	Priority	静态/动态优先级	紧急任务优先	低优先级饥饿（动态可解）	实时系统
MLFQ	Multi-Level Feedback Queue	多级反馈队列	兼顾长短作业	调优复杂	通用 OS
HRRN	Highest Response Ratio Next	高响应比 = (W+S)/S	无饥饿	需预估服务时间	批处理

关键公式

• 周转时间 = 完成时间 − 到达时间
• 等待时间 = 周转时间 − 服务时间
• 平均周转/等待 = Σ / n
• 响应比 R = (等待时间 + 服务时间) / 服务时间

真题举一反三

2020-11 综合题：4 进程 P1~P4，到达时间 0/1/2/3，服务时间 6/4/3/2，FCFS 求平均等待时间。

• 解：甘特图：P1(0-6) P2(6-10) P3(10-13) P4(13-15)
• 等待：P1=0, P2=5, P3=8, P4=10；平均 = (0+5+8+10)/4 = 5.75

2023-05 综合题：同上数据，SJF 求平均等待时间。

• 解：t=0 仅 P1 到达，执行 P1(0-6)；t=6 时 P2/P3/P4 都到达，按服务时间排序：P4(6-8) P3(8-11) P2(11-15)
• 等待：P1=0, P2=10, P3=6, P4=3；平均 = (0+10+6+3)/4 = 4.75

2024-11 综合题：3 进程 P1~P3，到达 0/1/2，服务 8/4/2，时间片 q=2 的 RR，求 P2 完成时间。

• 解：

  0-2: P1
  2-4: P2 (剩 2)
  4-6: P3 (完成)
  6-8: P1 (剩 6)
  8-10: P2 (完成) ← P2 完成时间 = 10
  10-14: P1
  

• P2 完成时间 = 10

C. PV 操作与信号量（核心，必考大题）

信号量基础

• 信号量 S：整型变量，初值 ≥ 0
• P 操作 wait(S)：S = S − 1；若 S < 0 则阻塞当前进程
• V 操作 signal(S)：S = S + 1；若 S ≤ 0 则唤醒一个等待进程
• 物理含义：S > 0 时表示可用资源数；S < 0 时 |S| 为等待进程数

互斥 vs 同步判定

类型	信号量初值	用途	P/V 配对
互斥 mutex	1	保护临界资源	同一进程 P/V 配对
同步 sync	0 或资源数	协调执行顺序	不同进程 V/P 配对（前驱 V，后继 P）

三大经典模型

模型 1：生产者-消费者

场景：n 个缓冲区，生产者放入产品，消费者取出产品。

信号量定义：

• mutex = 1：互斥访问缓冲区
• empty = n：空闲缓冲区数（同步）
• full = 0：已占用缓冲区数（同步）

伪代码：

producer() {
    while (true) {
        生产产品;
        P(empty);       // 申请空闲位（同步）
        P(mutex);       // 进入临界区
        放入产品;
        V(mutex);       // 离开临界区
        V(full);        // 通知消费者有产品
    }
}

consumer() {
    while (true) {
        P(full);        // 等待产品（同步）
        P(mutex);       // 进入临界区
        取出产品;
        V(mutex);       // 离开临界区
        V(empty);       // 通知生产者有空位
        消费产品;
    }
}

模型 2：读者-写者（读优先）

场景：允许多读者同时读，写者独占。

信号量定义：

• wmutex = 1：读写互斥（写者用）
• rmutex = 1：保护 readcount
• readcount = 0：当前读者数（普通变量）

伪代码：

reader() {
    P(rmutex);
    readcount++;
    if (readcount == 1) P(wmutex);   // 第一个读者锁写
    V(rmutex);
    读操作;
    P(rmutex);
    readcount--;
    if (readcount == 0) V(wmutex);   // 最后一个读者释放写
    V(rmutex);
}

writer() {
    P(wmutex);
    写操作;
    V(wmutex);
}

写优先变体：增加 wmutex2=1 / readtry=1，让写者到达时阻塞后续读者。

模型 3：哲学家就餐

场景：5 哲学家围圆桌，每两人间一叉，需左右两叉才能吃。

朴素方案（会死锁）：

philosopher(i) {
    思考;
    P(fork[i]);       // 拿左
    P(fork[(i+1)%5]); // 拿右
    吃;
    V(fork[i]);
    V(fork[(i+1)%5]);
}

防死锁方案：

1. 限 4 人就餐（信号量 seat=4）
2. 奇偶法：奇数号先左后右，偶数号先右后左
3. 同时拿两叉（用 mutex 保护）

真题举一反三

2021-11 案例题：面包店，1 个售货员（一次服务 1 人），N 个顾客。设信号量。

• 解：mutex = 1（互斥售货员）；顾客 P(mutex) → 服务 → V(mutex)

2024-05 案例题：理发店睡觉的理发师问题。M 理发师，N 椅子，K 顾客。

• 信号量：customers = 0（等待顾客数）；barbers = M（空闲理发师）；mutex = 1

2025-11 案例题：3 司机-3 售票员公交车同步。

• 信号量：door = 0（关门信号）；brake = 0（刹车信号）；

D. 死锁

死锁四必要条件

1. 互斥：资源独占
2. 占有并等待：占有资源等下一个
3. 不剥夺：不能强行夺走
4. 循环等待：进程等待链成环

破坏任一条件即可预防死锁：

• 破坏占有并等待 → 一次性申请所有资源
• 破坏不剥夺 → 资源可抢占
• 破坏循环等待 → 资源有序分配

死锁处理四策略

策略	原理	典型
预防 Prevention	破坏四条件	资源有序分配
避免 Avoidance	系统动态判断	银行家算法
检测与解除	允许发生，事后处理	等待图 + 回滚
忽略	鸵鸟策略	大多数通用 OS

银行家算法（必考）

数据结构：

• Available：当前各类资源可用数
• Max：每个进程最大需求
• Allocation：每个进程已分配
• Need = Max − Allocation：还需要的资源

银行家例题

2020-11 案例题：3 进程 P1~P3，资源 A B C，初始状态：

进程	Max	Allocation	Need
P1	3 2 2	1 0 0	2 2 2
P2	6 1 3	5 1 1	1 0 2
P3	3 1 4	2 1 1	1 0 3

Available = (10−8, 2−2, 4−2) = (2, 0, 2)

安全性检查：

• Work=(2,0,2)，Need(P1)=(2,2,2) > Work ✗；Need(P2)=(1,0,2) ≤ Work ✓ → P2 执行；Work=(7,1,3)
• Need(P1)=(2,2,2) ≤ (7,1,3)? ✗（B 不足）
• Need(P3)=(1,0,3) ≤ (7,1,3)? ✓ → P3 执行；Work=(9,2,4)
• Need(P1)=(2,2,2) ≤ (9,2,4)? ✓ → P1 执行；Work=(10,2,4)

安全序列：P2 → P3 → P1；状态 安全。

E. 内存管理与页面置换（必考 1~2 题）

分页 / 分段 / 段页式对比

方式	地址结构	优点	缺点
分页	页号 + 页内偏移	无外部碎片、内存利用率高	有内部碎片、不便共享
分段	段号 + 段内偏移	逻辑清晰、便于共享保护	有外部碎片
段页式	段号 + 页号 + 页内偏移	综合优点	地址变换 3 次访存

页面置换算法对比

算法	思想	优点	缺点	Belady 异常
OPT	淘汰未来最久不用	命中率最高	不可实现（需预知未来）	无
FIFO	淘汰最早进入内存	简单	命中率低	有
LRU	淘汰最近最久未用	接近 OPT	实现开销（计数器/栈）	无
CLOCK	二次机会 + 访问位	近似 LRU、开销小	命中率略低于 LRU	无
改进 CLOCK	访问位 + 修改位	进一步区分	复杂	无

Belady 异常

FIFO 特有：增加页框数，缺页率反增。

经典例：访问串 1,2,3,4,1,2,5,1,2,3,4,5

• 3 页框：缺页 9 次
• 4 页框：缺页 10 次 ⚠️

真题举一反三

2021-05 综合题：访问串 1,2,3,4,2,1,5,6,2,1,2,3,6,2，3 页框，LRU 求缺页次数。

• 解： | 访问 | 1 | 2 | 3 | 4 | 2 | 1 | 5 | 6 | 2 | 1 | 2 | 3 | 6 | 2 | |------|---|---|---|---|---|---|---|---|---|---|---|---|---|---| | 页框 | 1 | 1,2 | 1,2,3 | 2,3,4 | 3,4,2 | 4,2,1 | 2,1,5 | 1,5,6 | 5,6,2 | 6,2,1 | 6,2,1* | 2,1,3 | 1,3,6 | 3,6,2 | | 缺页 | ✓ | ✓ | ✓ | ✓ | | ✓ | ✓ | ✓ | ✓ | ✓ | | ✓ | ✓ | ✓ |

• 缺页 12 次（命中 2 次）

2024-11 综合题：改进型 CLOCK（访问位 A + 修改位 M），4 类优先级。

• 解：①(0,0) ②(0,1) ③(1,0) ④(1,1)，从指针扫，扫一遍若找到 (0,0) 替换；否则把扫描到的 A 改 0，再扫一遍找 (0,0)/(0,1)。

F. 磁盘调度

算法对比

算法	原理	优点	缺点
FCFS	先来先服务	公平	寻道长
SSTF	最短寻道优先	性能较好	远端饥饿
SCAN	电梯算法（双向扫到端）	无饥饿	中间请求等待
C-SCAN	单向扫描（到端回起点）	响应均匀	回程空跑
LOOK	SCAN 改进（不扫到端，扫到最远请求）	节省寻道	—
FSCAN	多队列（防单调粘连）	公平	复杂

真题举一反三

2022-11 综合题：当前柱面 53，请求队列 98,183,37,122,14,124,65,67，SCAN（向柱面增大方向），总柱面 0~199，求总寻道距离。

• 解：向大：65,67,98,122,124,183（到 199 前停，LOOK 改进）；向小：37,14
• 距离 = (183-53) + (183-14) = 130+169 = 299 柱面

G. 文件系统

文件物理结构

结构	原理	优缺点
连续	起始块 + 长度	简单、读快；碎片
链接	块内指针	无碎片；随机访问慢
索引	索引表	灵活；索引块开销
多级索引	直接 + 一级间接 + 二级间接 + 三级间接	兼顾小大文件

混合索引例：inode 含 12 直接块 + 1 一级间接 + 1 二级间接 + 1 三级间接

• 块大小 4KB，每块 4B 指针（1024 指针/块）
• 直接：48KB；一级：4MB；二级：4GB；三级：4TB

真题举一反三

2023-11 综合题：块大小 1KB，地址 4B，inode 含 10 直接 + 1 一级 + 1 二级，求最大文件。

• 解：直接 10KB；一级 256KB；二级 64MB；总 ≈ 64.266 MB

---

H. 反查表

考点	套路	真题	锚点
进程状态转换	五态图	2024-05	§A
FCFS/SJF/RR 调度	甘特图四步法	2020-11, 2023-05, 2024-11	§B
HRRN 响应比	(W+S)/S	2024-05	§B
互斥 vs 同步信号量	互斥=1，同步=0/资源	2021-11, 2024-05, 2025-11	§C
PV 大题四步法	同步在前互斥在后	2024-05, 2025-11	§C
生产者-消费者	empty/full/mutex	2021-11	§C
读者-写者	readcount + wmutex	2024-05	§C
哲学家就餐	防死锁策略	2022-05	§C
死锁四条件	互斥/占有/不剥夺/循环	2024-11	§D
银行家安全性算法	Work+Finish 五步	2020-11, 2023-05	§D
LRU 缺页率	栈式维护	2021-05	§E
FIFO Belady	增页框反增缺页	2025-05	§E
CLOCK 改进型	A+M 四类优先级	2024-11	§E
SCAN 磁盘调度	电梯算法距离	2022-11	§F
混合索引最大文件	直接+一级+二级+三级	2023-11	§G

---

记忆口诀 / 易错点汇总

1. PV 大题口诀：同步在前互斥在后，资源数 = 信号量初值
2. 银行家五步：Work+Finish → 找 Need≤Work → 加 Allocation → 全 Finish 即安全
3. 页面置换四算法：OPT 最优不可实现；FIFO 异常；LRU 开销大；CLOCK 近似
4. 死锁四条件：互斥占有不剥夺循环
5. 调度算法选择：交互选 RR；批处理选 SJF；实时选优先级

---

交叉引用

本系列笔记

• 计算机基础速查表：OS 概念速查，本篇是其深化版
• 计算机基础硬核计算题：流水线 / Cache / 可靠度计算
• 数据库网络深化：数据库事务并发与 OS 死锁对照

主计划文档

详见 主计划 §3.2 操作系统 的对应内容。

外部延伸

• 官方教材：《系统架构设计师教程（第 2 版）》§3.2
• 真题练习：2020-2025 综合+案例 PV 大题

---

自测题

1. 调度：4 进程 P1~P4，到达 0/1/2/3，服务 5/3/8/6，SJF 求平均等待时间。（答：≈ 4.5）
2. PV：写 barber sleeping 问题伪代码（M 理发师，N 椅子）。
3. 银行家：5 进程 A B C D，可用 (3,3,2)，能否安全分配？给出安全序列。
4. 页面置换：访问串 7,0,1,2,0,3,0,4,2,3,0,3,2，4 页框，LRU 求缺页次数。（答：6 次）
5. 磁盘：当前 100，请求 55,58,39,18,90,160,150,38,184，SCAN 向小，总寻道？（答：≈ 382）

---

下一篇导引：数据库网络深化 将讲述范式判定决策树、子网划分五步公式、TCP 三次握手四次挥手，帮助你掌握 DB+网络全部考点。