软考系统架构设计师 · 计算题全集（公式+演练+口诀双轨）

文档定位：覆盖软考系统架构设计师考试 90% 以上计算题型的单一总文档。
三层结构：① 公式速查（考前翻阅）→ ② 深度演练（理解应用）→ ③ 速记卡+口诀总表（最后冲刺）
口诀双轨：每类题型配「顺口溜」+「谐音」两套记忆法，任选其一即可牢记。

---

目录

编号	题型	公式速查	演练例题	口诀
一	关键路径法 CPM	✓	3题	✓
二	PERT 三点估算	✓	3题	✓
三	挣值管理 EVM	✓	4题	✓
四	圈复杂度 McCabe	✓	3题	✓
五	功能点分析 FPA	✓	3题	✓
六	COCOMO 模型	✓	3题	✓
七	可靠性计算	✓	4题	✓
八	性能计算	✓	4题	✓
九	存储与 Cache	✓	5题	✓
十	网络计算	✓	5题	✓
十一	风险分析 EMV	✓	3题	✓
十二	数据库计算	✓	3题	✓
十三	面向对象度量	✓	2题	—
十四	PV 操作与同步互斥	✓	5题	✓
十五	内存页面置换算法	✓	5题	✓
十六	内存管理（页式/段式/段页式）	✓	5题	✓
十七	文件索引与磁盘管理	✓	4题	✓
十八	死锁避免与银行家算法	✓	4题	✓
十九	磁盘调度与进程调度	✓	4题	✓
二十	位示图与空闲区管理	✓	2题	✓
二十一	综合速算实战	—	2题	—
二十二	速记卡+口诀总表	—	—	✓

---

第一部分：公式速查

---

一、关键路径法（CPM）

1.1 核心公式

指标	公式	说明
ES（最早开始）	ES = max(所有紧前活动EF)	正向推，遇多入边取最大
EF（最早完成）	EF = ES + 工期	—
LF（最晚完成）	LF = min(所有紧后活动LS)	逆向推，遇多出边取最小
LS（最晚开始）	LS = LF − 工期	—
总时差 TF	TF = LF − EF = LS − ES	=0 则在关键路径上
自由时差 FF	FF = min(紧后ES) − EF	不影响紧后最早开始

关键路径：总时差全为 0 的路径 = 工期最长的路径。

1.2 速算技巧

1. 正向推 ES/EF：从起点出发，加法，遇多入边取最大
2. 逆向推 LS/LF：从终点出发，减法，遇多出边取最小
3. 一眼找关键路径：从终点倒推，每次选 EF 最大的前驱，回溯到起点
4. ⚠️ 易错点：LF = min(紧后LS)，不是 min(紧后LF)！这是最常见的错误。

1.3 口诀双轨

类型	口诀
顺口溜	正早最大加，逆晚最小减，时差零关键
谐音	郑早最大家，李晚最小姐，差零关见

释义：正向推最早时间取最大值相加；逆向推最晚时间取最小值相减；总时差为零的活动在关键路径上。

---

二、PERT 三点估算

2.1 核心公式

$$T_E = \frac{TO + 4TM + TP}{6}$$

$$\sigma = \frac{TP - TO}{6}$$

$$\mu_{路径} = \sum T_{Ei}, \quad \sigma_{路径} = \sqrt{\sum \sigma_i^2}$$

$$Z = \frac{目标工期 - \mu}{\sigma_{路径}}$$

• TO = 乐观估计，TM = 最可能估计，TP = 悲观估计

2.2 速算技巧

• 分子先算 (TO+TP) 再加 4×TM
• 常见凑整组合：(3+4×6+9)=36→6
• 标准差只与极差有关，与 TM 无关

2.3 常用 Z 值表

Z	0	0.5	1.0	1.5	2.0	3.0
概率	50%	69.1%	84.1%	93.3%	97.7%	99.9%

速记：零五十八四九七 → Z=0→50%, Z=1→84%, Z=2→97%, Z=3→99.9%

2.4 口诀双轨

类型	口诀
顺口溜	乐悲加四倍中，除六得期望；极差除以六，标准差便当
谐音	岳飞加四倍中，除六得期望

释义：(乐观+悲观+4×最可能)/6 = 期望工期；(悲观−乐观)/6 = 标准差。

---

三、挣值管理（EVM）

3.1 三基本值

指标	全称	理解
PV	计划价值	“该干的活预算”
EV	挣值	“已干的活预算”
AC	实际成本	“已花的钱”

3.2 偏差与指数

指标	公式	>0 含义
CV	EV − AC	省钱
SV	EV − PV	超前
CPI	EV / AC	>1 省钱
SPI	EV / PV	>1 超前

3.3 完工预测

指标	公式	适用
EAC（典型）	BAC / CPI	当前偏差代表未来
EAC（非典型）	AC + (BAC − EV)	剩余按计划
EAC（最悲观）	AC + (BAC−EV)/(CPI×SPI)	偏差+进度影响
ETC	EAC − AC	还要花多少
VAC	BAC − EAC	完工偏差
TCPI	(BAC−EV)/(BAC−AC)	剩余必须效率

3.4 EV 的三种给法

题目说法	公式
“完成总工作的 X%”	EV = X% × BAC
“完成计划的 X%”	EV = X% × PV
各活动完成率	EV = Σ(预算ᵢ × 完成率ᵢ)

3.5 口诀双轨

类型	口诀
顺口溜	EV 是核心，减 AC 省成本，减 PV 超进度；CPI 除得 EAC，剩余加 ETC
谐音	衣屋是核心，减埃西省成本，减皮维超进度

三值谐音：PV=皮维(计划预算)，EV=衣屋(已干预算)，AC=埃西(实际花钱)

---

四、圈复杂度（McCabe）

4.1 三种公式

方法	公式
边节点法	V(G) = E − N + 2
判定节点法	V(G) = 判定节点数 + 1
区域法	V(G) = 封闭区域数 + 1

4.2 速算技巧

• 首选"判定节点+1"：数 if/while/for/switch-case，最快
• 复合条件 if (a && b) 算 2个 判定节点
• switch 的 n 个 case 算 n 个判定节点
• 独立路径数 = V(G)，测试用例下界 = V(G)

4.3 覆盖标准速记

覆盖标准	用例数
语句覆盖	1
判定覆盖	2
条件覆盖	2
判定/条件覆盖	2
条件组合覆盖	4
路径覆盖	2（单判定）

速记：语一判二条二组四路二

4.4 口诀双轨

类型	口诀
顺口溜	边减点加二，判定加一数，区域数最直
谐音	边减点加二，判官加一数

---

五、功能点分析（FPA）

5.1 信息域权重表

信息域	低	中	高
外部输入 EI	3	4	6
外部输出 EO	4	5	7
外部查询 EQ	3	4	6
内部逻辑文件 ILF	7	10	15
外部接口文件 EIF	5	7	10

5.2 核心公式

$$UFC = \sum (权重 \times 数量)$$

$$FP = UFC \times (0.65 + 0.01 \times \sum F_i)$$

• 14 个复杂性调节因子 Fi，每个 0~5，ΣFi 范围 0~70
• 基准点：ΣFi=35 时系数=0.65+0.35=1.0，FP=UFC
• 速算：ΣFi 每增 10，系数 +0.1

5.3 LOC/FP 语言对照

语言	LOC/FP
C	128
C++/Java	53
Python	27
COBOL	91
汇编	320

5.4 口诀双轨

类型	口诀
顺口溜	输入查询三四六，输出四五七，接口五七十，逻辑七十十五
谐音	三叔四舅（3,4,6）四姑五妻（4,5,7）五姐七姨（5,7,10）七叔十姥（7,10,15）

系数口诀：

类型	口诀
顺口溜	六五加零点一，因子和来调；三十五为中，恰好等于一
谐音	刘武加林丹，因子和来调

---

六、COCOMO 模型

6.1 基本 COCOMO

$$E = a \times (KLOC)^b, \quad D = c \times E^d$$

项目类型	a	b	c	d	KLOC 范围
有机型	2.4	1.05	2.5	0.38	<50
半分离	3.0	1.12	2.5	0.35	50~300
嵌入型	3.6	1.20	2.5	0.32	>300

6.2 中级 COCOMO

$$E = a \times (KLOC)^b \times \prod EAF_i$$

15 个成本驱动因子乘积调整。

6.3 速算技巧

• b≈1 时，E ≈ a × KLOC
• $KLOC^{0.05} ≈ 1 + 0.05 \times \ln(KLOC)$

6.4 口诀双轨

类型	口诀
顺口溜	二四三六，指数一二；二五不变，周期点三八
谐音	二四三六（2.4,3.6），一零五二零（1.05,1.20）

项目类型口诀：小五十大三百，有机半离嵌

---

七、可靠性计算

7.1 串并联

结构	公式
串联	R = ∏Rᵢ
并联	R = 1 − ∏(1−Rᵢ)
k/n 表决	R = Σ C(n,j)×Rʲ×(1−R)ⁿ⁻ʲ, j=k~n

7.2 MTBF 与可用性

$$A = \frac{MTBF}{MTBF + MTTR}$$

$$MTBF = \frac{1}{\lambda}$$

• 串联：λ总 = Σλᵢ
• 并联（两相同）：MTBF = 1.5 × 单模块 MTBF
• MTTR≪MTBF 时：A ≈ 1 − MTTR/MTBF

7.3 常用可靠度速记

单元 R	串联(2)	并联(2)
0.9	0.81	0.99
0.8	0.64	0.96
0.99	0.9801	0.9999

7.4 口诀双轨

类型	口诀
顺口溜	串联乘可靠，并联减失效；可用除总时，失效率倒置
谐音	串乘并减，可用除总

补充：两并一倍半（两相同并联 MTBF = 1.5×单模块）

---

八、性能计算

8.1 Little 律

$$L = \lambda \times W$$

L=系统中平均请求数，λ=到达率，W=平均响应时间

8.2 吞吐量与并发

$$并发数 = 吞吐量 \times 平均响应时间$$

8.3 CPI 与 MIPS

$$CPI = \frac{\sum (指令数_i \times CPI_i)}{总指令数}$$

$$MIPS = \frac{主频(MHz)}{CPI}$$

$$执行时间 = \frac{指令数 \times CPI}{主频}$$

8.4 Amdahl 定律

$$S_n = \frac{1}{(1-p) + p/n}$$

$$S_{极限} = \frac{1}{1-p}$$

p	极限加速比
0.5	2
0.8	5
0.9	10
0.95	20
0.99	100

速记：九成十倍，九五二十，九九一百

8.5 口诀双轨

类型	口诀
顺口溜	频除 CPI 得 MIPS，指令乘 CPI 除频得时
谐音	频除 CPI，指 C 除频

---

九、存储与 Cache

9.1 Cache

$$命中率\ h = \frac{命中次数}{总访问次数}$$

$$平均访问时间 = h \times t_{cache} + (1-h) \times t_{内存}$$

9.2 磁盘 IOPS

$$IOPS = \frac{1000}{平均寻道 + 旋转延迟 + 传输时间}(ms)$$

$$旋转延迟 = \frac{30000}{转速(rpm)}$$

转速	旋转延迟
7200	4.17ms
10000	3ms
15000	2ms

9.3 内存编址

• 1KB=2¹⁰, 1MB=2²⁰, 1GB=2³⁰
• 容量 2ⁿ 对应 n 位地址线
• 末地址 = 起始地址 + 容量 − 1
• 芯片数 = 总容量 / 单片容量（向上取整）

9.4 RAID 可用容量

级别	可用容量	最少盘数
RAID 0	N	2
RAID 1	N/2	2
RAID 5	(N−1)	3
RAID 6	(N−2)	4
RAID 10	N/2	4

9.5 口诀双轨

类型	口诀
顺口溜	K 十 M 二十 G 三十，容量除片得片数
谐音	凯十埃姆二十吉三十

RAID 口诀：0 全 1 半 5 减 1，6 减 2 加 10 半

---

十、网络计算

10.1 IP 子网划分

• 子网数 = 2ⁿ（n=借的位数）
• 每子网主机数 = 2ʰ − 2（h=主机位剩余）
• 子网掩码：/(24+n) → 最后段 = 256 − 2ʰ
• 子网步长 = 2ʰ

10.2 海明码

$$2^r \geq m + r + 1$$

数据位 m	校验位 r
1~4	3
5~11	4
12~26	5
27~57	6

码距与检错纠错：

• 检 e 错：码距 ≥ e+1
• 纠 t 错：码距 ≥ 2t+1
• 同时检 e 纠 t（e>t）：码距 ≥ e+t+1

纠错：S 的十进制值 = 出错位号

10.3 CRC

1. 信息位后补 k 个 0（k=生成多项式位数−1）
2. 模 2 除（异或）生成多项式
3. 余数 = CRC 校验码

10.4 口诀双轨

类型	口诀
顺口溜	借 n 位出二 n 网，主机位减二得数
谐音	借位出网，主机减二

海明码口诀：二的 r 次大于等于 m 加 r 加一

---

十一、风险分析（EMV）

11.1 期望货币价值

$$EMV = \sum (概率_i \times 收益_i)$$

11.2 决策树

• 机会节点（圆圈）：取 EMV（加权平均）
• 决策节点（方框）：取 max（选最大收益）
• 从右向左算（叶→根）
• 概率和必须 = 1（验算）

11.3 风险暴露度

$$RE = 概率 \times 影响$$

11.4 口诀双轨

类型	口诀
顺口溜	圆圈算期望，方框取最大；从右向左推，概率和为一
谐音	圆算方取，右左推一

---

十二、数据库计算

12.1 候选键求法

1. 只在左部出现的属性 → 必在候选键中
2. 既不在左部也不在右部 → 必在候选键中
3. 只在右部出现的属性 → 必不在候选键中
4. 剩余属性与必在属性组合，看能否函数决定全属性

12.2 范式判断

范式	条件
1NF	属性不可分
2NF	非主属性完全依赖候选键（消除部分依赖）
3NF	非主属性不传递依赖候选键（消除传递依赖）
BCNF	所有决定因素都是候选键
4NF	消除非平凡多值依赖

12.3 口诀双轨

类型	口诀
顺口溜	一不可分，二消部分，三消传递，BC 决定必键
谐音	一分二部三传，毕决定必键

候选键口诀：左必右必不，待定要组合

---

十三、面向对象度量

13.1 LK 度量

指标	含义
WMC	类中方法复杂度之和
DIT	继承树深度
NOC	直接子类数
CBO	耦合类数
RFC	响应集大小
LCOM	内聚度量（方法交集越小内聚越差）

13.2 内聚类型（从低到高）

级别	名称	说明
1	偶然内聚	无直接关系
2	逻辑内聚	功能相似
3	时间内聚	同时执行
4	过程内聚	按特定顺序
5	通信内聚	同一数据集
6	顺序内聚	输出为输入
7	功能内聚	单一功能

口诀：偶逻时过通顺功 / 谐音：我老师过通顺功

---

附、数学基础速算

14.1 2 的幂次必背

2⁰=1, 2¹=2, 2²=4, 2³=8, 2⁴=16, 2⁵=32, 2⁶=64, 2⁷=128,
2⁸=256, 2⁹=512, 2¹⁰=1024, 2¹¹=2048, 2¹²=4096,
2¹³=8192, 2¹⁴=16384, 2¹⁵=32768, 2¹⁶=65536

14.2 常用平方根

值	√值
20	4.47
29	5.39
50	7.07

14.3 排列组合常用值

$$C_n^r = C_n^{n-r}$$

值	结果
C₅²	10
C₆²	15
C₆³	20
C₇³	35
C₈³	56

14.4 对数

• log₂10 ≈ 3.32
• log₁₀2 ≈ 0.301

14.5 概率

• 独立：P(A∩B) = P(A)×P(B)
• 互斥：P(A∪B) = P(A)+P(B)
• 一般：P(A∪B) = P(A)+P(B)−P(A∩B)
• 条件：P(A|B) = P(A∩B)/P(B)
• 贝叶斯：P(Aᵢ|B) = P(Aᵢ)P(B|Aᵢ) / ΣP(Aⱼ)P(B|Aⱼ)

---

十四、PV 操作与同步互斥

14.1 信号量基本操作

操作	语义	代码	信号量变化
P(S) / wait(S)	申请资源	S = S − 1	S<0 则阻塞等待
V(S) / signal(S)	释放资源	S = S + 1	S≤0 则唤醒一个等待进程

14.2 信号量分类

类型	初值	含义
互斥信号量	1	保护临界区，同一时刻只允许1个进程进入
同步信号量	0	前驱关系：V在前驱之后，P在后继之前
资源信号量	n	表示有n个同类资源可用

14.3 经典模型公式

生产者-消费者（缓冲区容量 N）：

semaphore mutex = 1;    // 互斥
semaphore empty = N;    // 空缓冲区
semaphore full  = 0;    // 满缓冲区

生产者: P(empty); P(mutex); 放产品; V(mutex); V(full);
消费者: P(full);  P(mutex); 取产品; V(mutex); V(empty);

⚠️ P 操作顺序不能颠倒：先 P(empty/full) 再 P(mutex)，否则死锁！

读者-写者（读者优先）：

semaphore mutex = 1;    // 保护 readcount
semaphore wsem  = 1;    // 读写互斥
int readcount = 0;

读者: P(mutex); readcount++; if(readcount==1) P(wsem); V(mutex);
      读书;
      P(mutex); readcount--; if(readcount==0) V(wsem); V(mutex);

写者: P(wsem); 写书; V(wsem);

14.4 前驱图转 PV 操作

规则：每条有向边 A→B 对应一个同步信号量 S=0：

• A 的末尾加 V(S)
• B 的开头加 P(S)

14.5 信号量取值范围分析

• 互斥信号量 S 初值=1：取值范围 [−(n−1), 1]（n个进程竞争）
• 同步信号量 S 初值=0：取值范围 [−m, k]（m个等待，k个释放）
• 资源信号量 S 初值=n：取值范围 [−(m−n), n]

14.6 口诀双轨

类型	口诀
顺口溜	P 申请减一负则等，V 释放加一唤等待；互斥初一同步零，资源初值等于 N
谐音	皮减负等，维加唤等；互一同零资 N

释义：P操作将信号量减1，若为负则阻塞；V操作加1，若≤0则唤醒。互斥信号量初值1，同步信号量初值0，资源信号量初值N。

前驱图口诀：前驱末尾 V，后继开头 P，每边一信号

---

十五、内存页面置换算法

15.1 四种算法对比

算法	置换策略	特点
OPT	淘汰未来最久不用的页	理论最优，无法实现
FIFO	淘汰最先进入的页	可能有 Belady 异常
LRU	淘汰最近最久未用的页	无 Belady 异常，性能好
CLOCK	淘汰访问位=0 的页（二次机会）	LRU 的近似实现

15.2 缺页率与缺页次数

$$缺页率 = \frac{缺页次数}{总访问次数}$$

• 首次访问必然缺页
• 置换时必然缺页
• 命中时不缺页

15.3 Belady 异常

• FIFO：分配页面数增加，缺页率可能反而增加
• LRU/OPT：不会出现 Belady 异常（满足栈式算法性质）
• CLOCK：可能出现 Belady 异常

15.4 有效访问时间（含 TLB）

$$EAT = TLB命中率 \times (TLB时间 + 内存时间) + (1 - TLB命中率) \times (TLB时间 + 2 \times 内存时间)$$

• 命中 TLB：查 TLB + 查内存（1次访存取数据）
• 未命中 TLB：查 TLB + 查页表（1次访存）+ 取数据（1次访存）= 2次访存

15.5 口诀双轨

类型	口诀
顺口溜	最优未来最远，先进先出最早，最近最久未用，时钟二次机会
谐音	优远先早近久时二

释义：OPT淘汰未来最久不用的，FIFO淘汰最早的，LRU淘汰最近最久未用的，CLOCK给二次机会。

Belady 口诀：FIFO 可能反常，LRU 永不反常

---

十六、内存管理（页式/段式/段页式）

16.1 页式存储

地址结构：逻辑地址 = 页号 | 页内偏移

参数	公式
页号	页号 = 逻辑地址 / 页大小（整除）
页内偏移	偏移 = 逻辑地址 % 页大小
物理地址	物理地址 = 物理块号 × 页大小 + 页内偏移
页表长度	页表项数 = 逻辑地址空间 / 页大小

例：页面 4KB，逻辑地址 0x3C8A → 页号=0x3C8A/0x1000=3，偏移=0x8A

16.2 段式存储

地址结构：逻辑地址 = 段号 | 段内偏移

参数	公式
段号	段号 = 逻辑地址 / 段大小（或按位划分）
段内偏移	偏移 = 逻辑地址 % 段大小
物理地址	物理地址 = 段基址 + 段内偏移

⚠️ 段式 vs 页式：页大小固定，段大小可变；段表有"段长"字段用于越界检查

16.3 段页式存储

地址结构：逻辑地址 = 段号 | 页号 | 页内偏移

地址转换（3次访存）：

1. 查段表 → 得到页表起始地址
2. 查页表 → 得到物理块号
3. 物理块号 × 页大小 + 偏移 → 物理地址

16.4 多级页表

参数	公式
页目录项数	2^(虚拟地址位数 − 页偏移位数 − 页表索引位数)
每级页表项数	页大小 / 页表项大小

例：32位地址，4KB页，4B页表项 → 每页表1024项 → 10位页号 + 10位页目录 + 12位偏移

16.5 访存次数总结

机制	访存次数（无TLB）	访存次数（有TLB命中）
页式	2（页表+数据）	1（TLB+数据）
段式	2（段表+数据）	1
段页式	3（段表+页表+数据）	1
二级页表	3（目录+页表+数据）	1

16.6 口诀双轨

类型	口诀
顺口溜	页式除余偏移定，段式基址加偏移；段页三次访存，页式两次段式两次
谐音	页除余偏，段基加偏；段页三访，页二段二

---

十七、文件索引与磁盘管理

17.1 索引节点结构

典型 UNIX inode：

索引类型	项数	每项指向
直接索引	10	数据块
一级间接	1	一个索引块（含若干数据块指针）
二级间接	1	一个索引块→多个索引块→数据块
三级间接	1	三层间接索引

17.2 最大文件大小计算

参数：磁盘块大小 B，每个索引项占 I 字节

$$每块索引项数 = n = B / I$$

索引类型	可寻址块数	可寻址字节
直接(10项)	10	10×B
一级间接	n	n×B
二级间接	n²	n²×B
三级间接	n³	n³×B

$$最大文件 = 10B + nB + n^2B + n^3B$$

典型值：B=4KB=4096B, I=4B → n=1024

• 直接：40KB
• 一级：4MB
• 二级：4GB
• 三级：4TB
• 总计 ≈ 4TB + 4GB + 4MB + 40KB

17.3 文件分配方式

方式	特点	优点	缺点
连续分配	文件占连续磁盘块	顺序访问快	外部碎片
链接分配	每块含下一块指针	无外部碎片	随机访问慢
索引分配	索引块存所有块号	随机访问快	索引开销

17.4 磁盘物理地址

$$磁盘容量 = 柱面数 \times 磁头数 \times 扇区数 \times 扇区大小$$

逻辑块号 → 物理地址：

• 柱面号 = LBN / (磁头数 × 扇区数)
• 磁头号 = (LBN % (磁头数 × 扇区数)) / 扇区数
• 扇区号 = LBN % 扇区数

17.5 口诀双轨

类型	口诀
顺口溜	直接十块一级 n，二级 n 方三 n 三方；块大除项得 n 值，最大文件四项加
谐音	直十一 n 二 n 方三 n 三方

释义：直接10块，一级间接n块，二级n²块，三级n³块。n=块大小/索引项大小。

---

十八、死锁避免与银行家算法

18.1 死锁四大必要条件

1. 互斥：资源不能共享
2. 占有并等待：持有资源同时申请新资源
3. 不剥夺：不能强行夺走资源
4. 循环等待：存在进程-资源的环形链

18.2 银行家算法数据结构

矩阵	含义
Available	系统当前可用资源向量
Max	每个进程最大需求矩阵
Allocation	每个进程已分配矩阵
Need	每个进程还需资源 = Max − Allocation

18.3 安全性算法步骤

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 → 安全序列；否则 → 不安全

18.4 资源请求算法

1. 若 Request[i] > Need[i] → 出错（请求超过最大需求）
2. 若 Request[i] > Available → 阻塞等待（资源不足）
3. 试探分配：
   Available = Available − Request[i]
   Allocation[i] = Allocation[i] + Request[i]
   Need[i] = Need[i] − Request[i]
4. 执行安全性算法：
   - 安全 → 真正分配
   - 不安全 → 回滚，进程等待

18.5 死锁避免 vs 预防 vs 检测

策略	时机	方法	代价
预防	事前	破坏四大条件之一	资源利用率低
避免	运行时	银行家算法	计算开销大
检测	运行时	资源分配图化简	需恢复机制

18.6 资源数与死锁关系

• m 个资源，n 个进程，每个最多申请 k 个资源
• 无死锁条件：$m \geq n \times (k - 1) + 1$
• 推导：最坏情况每个进程都拿到 k−1 个（差一个），只要再多1个资源就能让某进程完成

$$m > n \times (k-1) \quad 即 \quad m \geq n(k-1)+1$$

18.7 口诀双轨

类型	口诀
顺口溜	互占不循四条件，安全序列逐个找；Need 小于 Work 则分配，全完成则安全
谐音	互占不循，需小工则分，全成则安

资源数口诀：资源大于进程乘减一加一 → m ≥ n(k−1)+1

---

十九、磁盘调度与进程调度

19.1 磁盘调度算法

算法	策略	特点
FCFS	按请求顺序服务	公平，寻道距离大
SSTF	最短寻道时间优先	性能好，可能饥饿
SCAN	电梯算法，单向扫描到端再折返	无饥饿
C-SCAN	单向扫描到端，直接跳回起点	响应均匀
LOOK	SCAN 改进，到最后一个请求即折返	不走到底
C-LOOK	C-SCAN 改进，到最后请求即跳回	不走到底

19.2 寻道距离计算

• FCFS：依次计算相邻请求柱面差的绝对值之和
• SSTF：每次选离当前磁头最近的请求
• SCAN：先向一个方向走到端点（或最后请求），再折返
• C-SCAN：只向一个方向服务，到端后直接跳回起点

19.3 进程调度算法

算法	策略
FCFS	先来先服务
SJF	短作业优先（非抢占）
SRTF	最短剩余时间优先（抢占式SJF）
优先级调度	按优先级（高/低）
时间片轮转 RR	每个进程分配固定时间片
多级反馈队列	多个队列+不同时间片+降级

19.4 调度指标

指标	公式
周转时间	完成时间 − 到达时间
等待时间	周转时间 − 运行时间
带权周转时间	周转时间 / 运行时间
平均周转时间	Σ周转时间 / 进程数
CPU利用率	CPU忙时间 / 总时间

19.5 口诀双轨

类型	口诀
顺口溜	先来先服务最公平，最短寻道性能好；电梯扫描到端折返，循环扫描只走一边
谐音	先先公，短短好，电扫折返环扫单

调度指标口诀：周转等于完成减到达，等待等于周转减运行

---

二十、位示图与空闲区管理

20.1 位示图法

• 每个磁盘块对应 1 bit：1=已分配，0=空闲
• 位示图大小 = 磁盘总块数 / 8 字节
• 块号 → 位示图位置：行 = 块号 / 字长，列 = 块号 % 字长

20.2 空闲区表/链

管理方式	说明
空闲表	连续分配，记录(起始块, 长度)
空闲链	链接各空闲区
位示图	位映射，紧凑
成组链接	UNIX 方式，空闲块成组链接

20.3 空闲区分配算法

算法	策略	特点
首次适应	从头找第一个足够大的	简单，低址碎片多
最佳适应	找最小的足够大的	小碎片多
最坏适应	找最大的	大请求难满足
循环首次适应	从上次位置继续找	碎片分布均匀

20.4 口诀双轨

类型	口诀
顺口溜	位图一位代表一块，一为分配零空闲；首适最佳最坏循环，分配策略各不同
谐音	位图一零，首佳最循

---

第二部分：深度演练

---

演练一：关键路径法

例题 1（正向+逆向+时差）

某项目活动如下表，求关键路径、总工期及各活动总时差。

活动	紧前	工期(天)
A	—	3
B	—	5
C	A	4
D	A	6
E	B,C	5
F	D,E	4
G	F	2

网络图：

起点 → A(3) → C(4) ↘
起点 → B(5) ────────→ E(5) → F(4) → G(2) → 终点
        A(3) → D(6) ↗

第一步：正向推 ES/EF（正早最大加）

活动	ES	EF
A	0	3
B	0	5
C	3	7
D	3	9
E	max(5,7)=7	12
F	max(9,12)=12	16
G	16	18

总工期 = 18 天

第二步：逆向推 LS/LF（逆晚最小减）

⚠️ 关键：LF = min(紧后LS)，不是 min(紧后LF)！

活动	LF	LS
G	18	16
F	16	12
E	12	7
D	12	6
C	E的LS=7	7−4=3
B	E的LS=7	7−5=2
A	min(C的LS=3, D的LS=6)=3	3−3=0

第三步：总时差 TF = LF − EF

活动	TF
A	3−3=0
B	7−5=2
C	7−7=0
D	12−9=3
E	12−12=0
F	16−16=0
G	18−18=0

关键路径：A→C→E→F→G，工期 18 天。

速算验证：从终点倒推最大 EF 前驱：G←F(16)←E(12)←C(7)←A(3)←起点，路径和=3+4+5+4+2=18 ✓

口诀回顾：正早最大加，逆晚最小减，时差零关键

---

例题 2（自由时差）

接上题，FF = min(紧后ES) − EF：

活动	紧后	min(紧后ES)	EF	FF
A	C,D	min(3,3)=3	3	0
B	E	7	5	2
C	E	7	7	0
D	F	12	9	3
E	F	12	12	0
F	G	16	16	0
G	—	18	18	0

规律：关键路径上 FF=0；若唯一紧后在关键路径上，FF=TF。

---

例题 3（赶工决策）

需将工期从 18 天压缩到 15 天（压缩 3 天）。

活动	正常工期	赶工工期	正常成本	赶工成本	可压天数	赶工斜率
A	3	2	3000	5000	1	2000
C	4	3	4000	6000	1	2000
E	5	3	5000	8000	2	1500
F	4	2	4000	7000	2	1500
G	2	1	2000	4000	1	2000

$$赶工斜率 = \frac{赶工成本 - 正常成本}{正常工期 - 赶工工期}$$

策略：优先赶关键路径上斜率最低的活动。

1. 赶 E 压 1 天 → 工期 17，成本 +1500
2. 赶 F 压 1 天 → 工期 16，成本 +1500
3. 赶 E 再压 1 天 → 工期 15，成本 +1500

总赶工成本 = 1500×3 = 4500

口诀：斜率最低优先赶，关键路径要盯紧；赶后重查路径变，非键变键要调整

---

演练二：PERT 三点估算

例题 1（单活动）

TO=8, TM=15, TP=20：

$$T_E = \frac{8 + 4×15 + 20}{6} = \frac{88}{6} = 14.67天$$

$$\sigma = \frac{20 - 8}{6} = 2天$$

速算：先算 8+20=28，再加 60=88，88/6≈14.67

---

例题 2（路径概率）

活动	TO	TM	TP	TE	σ
A	2	4	6	4	0.667
B	3	5	10	5.5	1.167
C	4	6	14	7	1.667

$$\mu = 4 + 5.5 + 7 = 16.5$$

$$\sigma_{总} = \sqrt{0.667^2 + 1.167^2 + 1.667^2} = \sqrt{4.586} = 2.14$$

$$Z = \frac{18 - 16.5}{2.14} = 0.70 → 概率 ≈ 75.8\%$$

---

例题 3（标准差平方速算）

σ₁=2, σ₂=3, σ₃=4：

$$\sigma_{总} = \sqrt{4+9+16} = \sqrt{29} ≈ 5.39$$

速算：√25=5, √36=6, 29 偏左 → ≈5.4

---

演练三：挣值管理

例题 1（基础指标）

BAC=200万，PV=120万，AC=130万，实际完成计划的 80%。

EV = 80% × PV = 0.8 × 120 = 96万

指标	计算	结果	判断
CV	96−130	−34万	超支
SV	96−120	−24万	落后
CPI	96/130	0.738	<1 超支
SPI	96/120	0.800	<1 落后

结论：成本超支且进度落后

---

例题 2（三种 EAC 对比）

BAC=200, EV=96, AC=130, CPI=0.738, SPI=0.800

假设	EAC 公式	EAC	ETC	VAC
典型	BAC/CPI	271	141	−71
非典型	AC+(BAC−EV)	234	104	−34
最悲观	AC+(BAC−EV)/(CPI×SPI)	306	176	−106

口诀：典型除 CPI，非典型加剩余，悲观再除 SPI

---

例题 3（TCPI）

$$TCPI = \frac{BAC - EV}{BAC - AC} = \frac{200-96}{200-130} = \frac{104}{70} = 1.486$$

剩余必须以 1.486 效率完成，当前 CPI=0.738 远不够 → 几乎不可能在原预算内完成。

---

例题 4（EV 三种给法辨析）

题目说法	公式	示例
“完成总工作 40%”	EV=40%×BAC	100万→40万
“完成计划 80%”	EV=80%×PV	PV=60→48万
各活动完成率	EV=Σ(预算×完成率)	30×1+50×0.6+20×0=60万

口诀：占总预算乘 BAC，占计划乘 PV，分活动各自算

---

演练四：圈复杂度

例题 1（判定节点法）

void example(int a, int b, int c) {
    if (a > 0) {           // 判定1
        if (b > 0) {       // 判定2
            printf("1");
        }
    }
    while (a < 10) {       // 判定3
        a++;
    }
    if (a > 0 && b > 0) {  // 判定4,5（&&拆开）
        printf("2");
    }
    switch(c) {
        case 1: break;     // 判定6
        case 2: break;     // 判定7
        case 3: break;     // 判定8
    }
}

$$V(G) = (1+1+1+2+3) + 1 = 9$$

至少需要 9 个测试用例实现路径覆盖。

---

例题 2（边节点法验证）

E=15, N=10：

$$V(G) = 15 - 10 + 2 = 7$$

区域法：6 个封闭区域 + 1 = 7 ✓

---

例题 3（覆盖标准）

if (a > 0 && b > 0)：

标准	用例数
语句	1
判定	2
条件	2
判定/条件	2
条件组合	4
路径	2

速记：语一判二条二组四路二

---

演练五：功能点分析

例题 1（UFC）

信息域	数量	复杂度	权重	小计
EI	5	中	4	20
EO	4	高	7	28
EQ	3	低	3	9
ILF	2	中	10	20
EIF	1	高	10	10

$$UFC = 20+28+9+20+10 = 87$$

---

例题 2（FP 完整计算）

ΣFi=53：

$$FP = 87 × (0.65 + 0.01×53) = 87 × 1.18 = 102.66 ≈ 103$$

速算：ΣFi=35 时系数=1.0，53 比 35 多 18，系数=1.0+0.18=1.18

---

例题 3（FP 转 LOC）

Java 开发，FP=103：

$$LOC = 103 × 53 = 5459行 ≈ 5.5KLOC$$

---

演练六：COCOMO

例题 1（有机型）

32KLOC，有机型（a=2.4, b=1.05）：

$$E = 2.4 × 32^{1.05} = 2.4 × 38.05 = 91.3人月$$

$$D = 2.5 × 91.3^{0.38} = 2.5 × 5.56 = 13.9月$$

速算：$32^{0.05} ≈ 1 + 0.05×\ln32 = 1+0.05×3.47 = 1.17$，$32^{1.05}=32×1.17=37.5$

---

例题 2（类型判断）

KLOC	类型
<50	有机
50~300	半分离
>300	嵌入

---

例题 3（中级调整）

基本 E=50人月，EAF=1.35：

$$E_{调整} = 50 × 1.35 = 67.5人月$$

---

演练七：可靠性

例题 1（串并联混合）

A(0.95)与B(0.9)串联，再与两个C(0.8)并联冗余串联：

$$R_{AB} = 0.95 × 0.9 = 0.855$$

$$R_{CC} = 1 - (1-0.8)^2 = 1 - 0.04 = 0.96$$

$$R_{系统} = 0.855 × 0.96 = 0.8208$$

---

例题 2（2/3 表决）

R=0.9：

$$R_{2/3} = 3×0.9^2×0.1 + 0.9^3 = 0.243 + 0.729 = 0.972$$

对比：单模块 0.9 < 2/3表决 0.972 < 3并联 0.999

---

例题 3（可用性）

MTBF=1000h, MTTR=10h：

$$A = \frac{1000}{1010} = 0.9901 ≈ 99.01\%$$

速算：A ≈ 1 − 10/1000 = 0.99

---

例题 4（并联 MTBF）

两相同模块并联，单模块 MTBF=1000h：

$$MTBF_{并联} = 1.5 × 1000 = 1500h$$

口诀：两并一倍半

---

演练八：性能计算

例题 1（Little 律）

λ=50请求/秒, W=0.2秒：

$$L = 50 × 0.2 = 10个$$

---

例题 2（MIPS）

主频 2GHz，CPI=1.9：

$$MIPS = \frac{2000}{1.9} = 1052.6$$

$$T = \frac{10^9 × 1.9}{2×10^9} = 0.95秒$$

---

例题 3（Amdahl）

p=0.9, n=10：

$$S_{10} = \frac{1}{0.1+0.09} = \frac{1}{0.19} = 5.26倍$$

$$S_{极限} = \frac{1}{0.1} = 10倍$$

---

例题 4（并发数）

吞吐量 100 TPS，响应时间 0.05s：

$$并发数 = 100 × 0.05 = 5$$

---

演练九：存储与 Cache

例题 1（Cache 平均时间）

h=0.9, t_cache=20ns, t_mem=100ns：

$$T = 0.9×20 + 0.1×100 = 18+10 = 28ns$$

---

例题 2（Cache stalls）

缺失率 5%，每指令访存 1.5 次，缺失代价 100 周期：

$$Stalls = 0.05 × 1.5 × 100 = 7.5周期$$

---

例题 3（磁盘 IOPS）

7200 RPM，寻道 8ms：

$$旋转延迟 = 4.17ms$$

$$IOPS = \frac{1000}{8+4.17} = \frac{1000}{12.17} = 82.2$$

---

例题 4（内存编址）

起始 A0000H，容量 32KB：

$$32KB = 8000H$$

$$末地址 = A0000H + 8000H - 1 = A7FFFH$$

---

例题 5（RAID 容量）

6 块 2TB 硬盘：

RAID	可用容量
0	12TB
1	6TB
5	10TB
6	8TB
10	6TB

---

演练十：网络计算

例题 1（子网划分）

192.168.1.0/24，需 6 个子网，每子网≥25 主机：

• 子网位 n=3（2³=8≥6）
• 主机位 h=5（2⁵−2=30≥25）
• 掩码 /27 → 255.255.255.224
• 步长 32

子网	网络地址	可用范围	广播
1	.0	.1~.30	.31
2	.32	.33~.62	.63
3	.64	.65~.94	.95
4	.96	.97~.126	.127
5	.128	.129~.158	.159
6	.160	.161~.190	.191

---

例题 2（同子网判断）

IP1=192.168.1.130, IP2=192.168.1.165, /26：

步长 64，边界 0/64/128/192。130 和 165 都在 128~191 → 同子网

---

例题 3（海明码校验位）

m=16：

• r=4: 16≥21 ✗
• r=5: 32≥22 ✓

r=5，总长 21 位

---

例题 4（海明码纠错）

接收 1011001（位7~位1）：

• S1 = 位1⊕位3⊕位5⊕位7 = 1⊕1⊕0⊕1 = 1
• S2 = 位2⊕位3⊕位6⊕位7 = 0⊕1⊕0⊕1 = 0
• S4 = 位4⊕位5⊕位6⊕位7 = 1⊕0⊕0⊕1 = 0

S=S4S2S1=001=1 → 位1出错，纠错后：1011000

---

例题 5（CRC）

信息位 1010，G(x)=1011：

1. 补 3 个零：1010000
2. 模 2 除 1011：

        1100
      -------
1011 ) 1010000
       1011
       ---
        0010
        0000
        ----
         0100
         0000
         ----
          100

3. 余数=100，发送码=1010100

---

演练十一：风险分析

例题 1（决策树）

方案	高需求(0.6)	低需求(0.4)	投资
大厂	年100万	年20万	300万
小厂	年40万	年30万	100万

10 年净收益：

方案	高需求	低需求
大厂	700	−100
小厂	300	200

$$EMV_{大厂} = 0.6×700+0.4×(-100) = 380万$$

$$EMV_{小厂} = 0.6×300+0.4×200 = 260万$$

选建大厂（380>260）

---

例题 2（含机会成本）

方案	成功(0.7)净收益	失败(0.3)净收益
A	170	−80
B	140	−30
不做	0	0

$$EMV_A = 0.7×170+0.3×(-80) = 95万$$

$$EMV_B = 0.7×140+0.3×(-30) = 89万$$

选方案 A

---

例题 3（风险暴露度）

概率 5%，损失 200 万：

$$RE = 0.05 × 200 = 10万元$$

缓解措施投入不应超过 10 万。

---

演练十二：数据库

例题 1（候选键）

R(A,B,C,D,E)，F={A→B, B→C, C→D, DE→A}

属性分析：

• E 只在左部 → 必在候选键
• 其余属性左右都出现 → 待定

从 E 出发组合：

组合	闭包	是否=U
{E,A}	{A,B,C,D,E}	✓
{E,B}	{A,B,C,D,E}	✓
{E,C}	{A,B,C,D,E}	✓
{E,D}	{A,B,C,D,E}	✓

候选键：EA, EB, EC, ED

---

例题 2（范式判断）

R(A,B,C,D)，F={A→B, A→C, C→D}，候选键=A

• 1NF ✓
• 2NF ✓（A 单属性，无部分依赖）
• 3NF ✗（A→C→D 传递依赖）

属于 2NF，不属于 3NF

分解为 3NF：R1(A,B,C), R2(C,D)

---

例题 3（无损连接）

R(A,B,C,D)，F={A→B, B→C}，分解 R1(A,B) 和 R2(B,C,D)

R1∩R2={B}，B→C 已知但 B→D 未知 → 有损连接

---

演练十三：面向对象度量

例题 1（类实例）

abstract class Shape { }
class Circle extends Shape { }
class Rectangle extends Shape { }
interface Drawable { }
class GraphicCircle extends Circle implements Drawable { }

• 可实例化：Circle, Rectangle, GraphicCircle（3个）
• Shape 后代：Circle, Rectangle, GraphicCircle
• Drawable 实现：GraphicCircle

---

例题 2（继承度量）

A←B←C, D继承B：

类	DIT	NOC	所有后代
A	0	1	B,C,D
B	1	2	C,D
C	2	0	—
D	2	0	—

---

演练十四：综合速算实战

例题 1（多知识点综合）

UFC=120, ΣFi=42, Java(53 LOC/FP), COCOMO 有机型

$$FP = 120×(0.65+0.42) = 120×1.07 = 128.4$$

$$LOC = 128.4×53 = 6805 ≈ 6.8KLOC$$

$$E = 2.4×6.8^{1.05} ≈ 2.4×6.8×1.096 ≈ 17.9人月$$

$$D = 2.5×17.9^{0.38} ≈ 7.5月$$

---

例题 2（30 秒速算挑战）

题目	速算	答案
EV=BAC×40%, BAC=200	200×0.4	80
CPI=EV/AC=80/100	—	0.8
EAC=BAC/CPI=200/0.8	—	250
0.9 并联 0.9	1−0.01	0.99
5个if+1个while	6+1	7
PERT (5+4×8+11)/6	48/6	8
子网 /28 主机数	2⁴−2	14
海明码 m=7	2⁴=16≥12	r=4
Amdahl p=0.8 极限	1/0.2	5
Little L=100×0.3	—	30

---

演练十五：PV 操作与同步互斥

例题 1（前驱图转 PV 操作）

有前驱图：S1→S2, S1→S3, S2→S4, S3→S4, S4→S5。写出 PV 操作实现同步。

解题：

每条边对应一个信号量，初值为 0：

边	信号量
S1→S2	a=0
S1→S3	b=0
S2→S4	c=0
S3→S4	d=0
S4→S5	e=0

S1: ...; V(a); V(b);
S2: P(a); ...; V(c);
S3: P(b); ...; V(d);
S4: P(c); P(d); ...; V(e);
S5: P(e); ...;

口诀回顾：前驱末尾 V，后继开头 P，每边一信号

---

例题 2（信号量取值范围）

3 个进程共享一个互斥信号量 S（初值=1），求 S 的取值范围。

解题：

• 1 个进程 P 操作后：S=0（1个进入临界区）
• 第 2 个进程 P 操作后：S=−1（1个等待）
• 第 3 个进程 P 操作后：S=−2（2个等待）

$$取值范围：[-(n-1), 1] = [-2, 1]$$

一般公式：n 个进程竞争互斥信号量(初值1)，取值范围 [−(n−1), 1]

---

例题 3（生产者-消费者信号量初值）

缓冲区容量 5，2 个生产者，3 个消费者。写出信号量设置。

semaphore mutex = 1;    // 互斥信号量
semaphore empty = 5;    // 空缓冲区数 = 容量
semaphore full  = 0;    // 满缓冲区数 = 0

关键：empty 初值=缓冲区容量，full 初值=0，mutex 初值=1。

---

例题 4（前驱关系判断死锁）

4 个进程，4 个信号量 S1~S4（初值均为 0）：

P1: P(S4); ...; V(S1);
P2: P(S1); ...; V(S2);
P3: P(S2); ...; V(S3);
P4: P(S3); ...; V(S4);

分析：形成循环等待 P1→P2→P3→P4→P1，每个都在等待前一个的 V 操作。

结论：死锁。所有信号量初值为 0，没有任何进程能先执行 V。

修复：打破循环，如将 P1 的 P(S4) 移到 V(S1) 之后，或改变某个信号量初值。

---

例题 5（读者-写者信号量分析）

读者优先模型中，5 个读者同时读，1 个写者等待。分析各信号量值。

readcount = 5
wsem = 0  (被读者P了，写者无法进入)
mutex = 1 (读者进出临界区时短暂占用)

关键：第一个读者执行 P(wsem) 锁住写者，最后一个读者执行 V(wsem) 释放。

---

演练十六：内存页面置换算法

例题 1（FIFO 置换）

页面访问序列：7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1
分配 3 个物理块，用 FIFO 求缺页次数。

解题（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
缺页	✓	✓	✓	✓		✓	✓	✓	✓	✓	✓			✓	✓			✓	✓

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

速算：FIFO 维护一个队列，先进先出，命中不移动。

---

例题 2（LRU 置换）

同一序列，分配 3 块，用 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	0	0	0	0	3	3	3	3	3	3	0	0	0	0	0
块3			1	1	1	3	3	3	2	2	2	2	2	2	2	2	2	7	7	7
缺页	✓	✓	✓	✓		✓		✓	✓	✓				✓		✓		✓

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

速算：LRU 每次命中时将该页移到"最近使用"位置（栈顶），淘汰栈底。

---

例题 3（OPT 置换）

序列：1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5，分配 3 块，用 OPT 求缺页次数。

访问	1	2	3	4	1	2	5	1	2	3	4	5
块1	1	1	1	1	1	1	1	1	1	1	1	5
块2		2	2	2	2	2	2	2	2	3	3	3
块3			3	4	4	4	5	5	5	5	4	4
缺页	✓	✓	✓	✓			✓			✓	✓	✓

缺页次数 = 7

速算：OPT 淘汰未来最久不用的页。如第4步访问4时，1/2/3中3最久不用→淘汰3。

---

例题 4（Belady 异常验证）

序列：3, 2, 1, 0, 3, 2, 4

FIFO 分配 3 块：缺页 = 7（全缺页，每次都置换）

FIFO 分配 4 块：

访问	3	2	1	0	3	2	4
块1	3	3	3	3	3	3	4
块2		2	2	2	2	2	2
块3			1	1	1	1	1
块4				0	0	0	0
缺页	✓	✓	✓	✓			✓

缺页 = 5

本例无 Belady 异常。经典 Belady 异常序列：1,2,3,4,1,2,5,1,2,3,4,5（3块缺页9次，4块缺页10次）。

结论：FIFO 可能出现 Belady 异常（块数↑缺页↑），LRU/OPT 不会。

---

例题 5（有效访问时间）

TLB 命中率 95%，TLB 查找时间 20ns，内存访问时间 100ns。求有效访问时间。

$$EAT = 0.95 \times (20 + 100) + 0.05 \times (20 + 100 + 100)$$

$$= 0.95 \times 120 + 0.05 \times 220 = 114 + 11 = 125ns$$

速算：命中=TLB+1次访存=120ns；未命中=TLB+2次访存=220ns。

---

演练十七：内存管理（页式/段式/段页式）

例题 1（页式地址转换）

页面大小 4KB，页表如下。逻辑地址 0x3C8A 的物理地址？

页号	物理块号
0	2
1	5
2	7
3	8

解题：

• 4KB = 0x1000，页内偏移占 12 位
• 页号 = 0x3C8A / 0x1000 = 3
• 页内偏移 = 0x3C8A % 0x1000 = 0xC8A
• 查页表：页号 3 → 物理块号 8
• 物理地址 = 8 × 0x1000 + 0xC8A = 0x8000 + 0xC8A = 0x8C8A

---

例题 2（段式地址转换）

段表如下，逻辑地址 (段号=2, 段内偏移=0x500) 的物理地址？

段号	段基址	段长
0	0x1000	0x800
1	0x2000	0x1000
2	0x5000	0x1000

解题：

• 查段表：段号 2 → 基址 0x5000，段长 0x1000
• 越界检查：0x500 < 0x1000 ✓
• 物理地址 = 0x5000 + 0x500 = 0x5500

---

例题 3（段页式地址转换）

段页式系统，段表如下，每段页表如下。逻辑地址 (段号=1, 页号=2, 页内偏移=0x0FF)，页大小 1KB。

段表：

段号	页表起始地址
0	0x1000
1	0x2000

段1的页表：

页号	物理块号
0	3
1	7
2	10

解题：

1. 查段表：段号 1 → 页表起始 0x2000
2. 查页表：页号 2 → 物理块号 10
3. 物理地址 = 10 × 1KB + 0x0FF = 0x2800 + 0x0FF = 0x28FF

访存次数：3次（段表+页表+数据），有 TLB 命中则 1 次。

---

例题 4（多级页表位数划分）

32 位虚拟地址，4KB 页面，4B 页表项。求二级页表结构。

解题：

• 页面 4KB = 2¹² → 页内偏移 12 位
• 每页表项数 = 4KB/4B = 1024 = 2¹⁰ → 每级索引 10 位
• 32 位 = 10(页目录) + 10(页表) + 12(偏移)

验证：10+10+12=32 ✓

---

例题 5（页表占用内存）

进程逻辑地址空间 4GB，页面 4KB，页表项 4B。求页表占多少内存。

解题：

• 页表项数 = 4GB / 4KB = 2³² / 2¹² = 2²⁰ = 1M 项
• 页表大小 = 1M × 4B = 4MB

二级页表：每页表 4KB（1024项），共 1024 个页表 + 1 个目录 = 1025 × 4KB ≈ 4MB（但只需加载当前用到的页表）

---

演练十八：文件索引与磁盘管理

例题 1（一级索引最大文件）

磁盘块大小 4KB，索引项 4B，inode 有 10 个直接索引 + 1 个一级间接索引。求最大文件大小。

解题：

$$n = 4KB / 4B = 1024$$

$$最大文件 = 10 \times 4KB + 1024 \times 4KB = 40KB + 4MB = 4MB + 40KB$$

---

例题 2（三级索引最大文件）

磁盘块 1KB，索引项 4B，inode 有 10 直接 + 1 一级 + 1 二级 + 1 三级。

解题：

$$n = 1KB / 4B = 256$$

类型	块数	字节
直接	10	10KB
一级	256	256KB
二级	256² = 65536	64MB
三级	256³ = 16777216	16GB

$$最大文件 = 10KB + 256KB + 64MB + 16GB ≈ 16GB$$

---

例题 3（磁盘容量计算）

磁盘 200 个柱面，16 个磁头，每磁道 63 扇区，每扇区 512B。求磁盘容量。

$$容量 = 200 \times 16 \times 63 \times 512 = 103,219,200B ≈ 98.4MB$$

---

例题 4（逻辑块号转物理地址）

磁盘 4 个磁头，每磁道 16 扇区。逻辑块号 LBN=50 对应哪个物理位置？

解题：

• 每柱面扇区数 = 4 × 16 = 64
• 柱面号 = 50 / 64 = 0
• 磁头号 = (50 % 64) / 16 = 50 / 16 = 3
• 扇区号 = 50 % 16 = 2

物理地址：(柱面=0, 磁头=3, 扇区=2)

---

演练十九：死锁避免与银行家算法

例题 1（安全性判断）

3 个进程 P1/P2/P3，3 类资源 A/B/C。

Available = (3, 3, 2)

进程	Max	Allocation	Need
P1	(7,5,3)	(0,1,0)	(7,4,3)
P2	(3,2,2)	(2,0,0)	(1,2,2)
P3	(9,0,2)	(3,0,2)	(6,0,0)

安全性算法：

步骤	进程	Work	Need	可分配?	Work+Allocation
1	P2	(3,3,2)	(1,2,2)	✓	(5,3,2)
2	P1	(5,3,2)	(7,4,3)	✗	—
2	P3	(5,3,2)	(6,0,0)	✗	—

P1 和 P3 都无法满足，但 P2 完成后 Work=(5,3,2)，再试：

步骤	进程	Work	Need	可分配?
1	P2	(3,3,2)	(1,2,2)	✓ → Work=(5,3,2)
2	P1	(5,3,2)	(7,4,3)	✗
2	P3	(5,3,2)	(6,0,0)	✗

不安全！ 无法找到安全序列。

---

例题 2（安全序列求解）

Available = (10, 5, 7)

进程	Max	Allocation	Need
P1	(7,5,3)	(0,1,0)	(7,4,3)
P2	(3,2,2)	(2,0,0)	(1,2,2)
P3	(9,0,2)	(3,0,2)	(6,0,0)
P4	(2,2,2)	(2,1,1)	(0,1,1)
P5	(4,3,3)	(0,0,2)	(4,3,1)

安全性算法：

步骤	进程	Work	Need≤Work?	Work+Alloc
1	P1	(10,5,7)	(7,4,3)✓	(10,6,7)
2	P2	(10,6,7)	(1,2,2)✓	(12,6,7)
3	P3	(12,6,7)	(6,0,0)✓	(15,6,9)
4	P4	(15,6,9)	(0,1,1)✓	(17,7,10)
5	P5	(17,7,10)	(4,3,1)✓	(17,7,12)

安全序列：<P1, P2, P3, P4, P5>，系统安全。

---

例题 3（资源请求判定）

接例题 2，P1 请求资源 Request=(1,0,2)。

步骤 1：Request ≤ Need? (1,0,2) ≤ (7,4,3) ✓

步骤 2：Request ≤ Available? (1,0,2) ≤ (10,5,7) ✓

步骤 3：试探分配：

• Available = (10,5,7)−(1,0,2) = (9,5,5)
• Allocation[P1] = (0,1,0)+(1,0,2) = (1,1,2)
• Need[P1] = (7,4,3)−(1,0,2) = (6,4,1)

步骤 4：安全性检查（用新值）：

步骤	进程	Work	Need≤Work?
1	P1	(9,5,5)	(6,4,1)✓ → (10,6,7)
2	P2	(10,6,7)	(1,2,2)✓ → (12,6,7)
3	P3	(12,6,7)	(6,0,0)✓ → (15,6,9)
4	P4	(15,6,9)	(0,1,1)✓ → (17,7,10)
5	P5	(17,7,10)	(4,3,1)✓ → (17,7,12)

安全！ 真正分配 P1 的请求。

---

例题 4（资源数与死锁）

系统有 m 个同类资源，n 个进程，每个进程最多申请 k 个资源。求无死锁条件。

公式：$m \geq n(k-1) + 1$

例：m=12, n=3, k=4 → 12 ≥ 3×3+1=10 ✓ 无死锁

例：m=9, n=3, k=4 → 9 < 10 ✗ 可能死锁

推导：最坏情况每个进程拿到 k−1 个（差一个就满足），共 n(k−1) 个。只要再多 1 个资源，某进程就能完成并释放。

---

演练二十：磁盘调度与进程调度

例题 1（磁盘调度算法对比）

磁头当前在柱面 53，请求队列：98, 183, 37, 122, 14, 124, 65, 67。磁头向柱面号增大方向移动。

FCFS（按请求顺序）：

53→98→183→37→122→14→124→65→67

$$总寻道 = 45+85+146+85+108+110+59+2 = 640$$

SSTF（每次选最近）：

53→65→67→37→14→98→122→124→183

$$总寻道 = 12+2+30+23+84+24+2+59 = 236$$

SCAN（向大方向走到端，再折返）：

53→65→67→98→122→124→183→37→14

$$总寻道 = 12+2+31+24+2+59+146+23 = 299$$

C-SCAN（只向大方向，到端跳回0）：

53→65→67→98→122→124→183→14→37

$$总寻道 = 12+2+31+24+2+59+(183-0)+14+23 = 350$$

对比：SSTF(236) < SCAN(299) < C-SCAN(350) < FCFS(640)

---

例题 2（进程调度 FCFS vs SJF）

进程	到达时间	运行时间
P1	0	7
P2	2	4
P3	4	1
P4	5	4

FCFS（按到达顺序）：

进程	开始	完成	周转	等待
P1	0	7	7	0
P2	7	11	9	5
P3	11	12	8	7
P4	12	16	11	7

$$平均周转 = (7+9+8+11)/4 = 8.75$$

$$平均等待 = (0+5+7+7)/4 = 4.75$$

SJF（非抢占，选最短）：

时刻	就绪队列	选择
0	P1	P1(7)
7	P2(4),P3(1),P4(4)	P3(1)
8	P2(4),P4(4)	P2(4)
12	P4(4)	P4(4)

进程	开始	完成	周转	等待
P1	0	7	7	0
P3	7	8	4	3
P2	8	12	10	6
P4	12	16	11	7

$$平均周转 = (7+4+10+11)/4 = 8.0$$

$$平均等待 = (0+3+6+7)/4 = 4.0$$

对比：SJF 平均周转(8.0) < FCFS(8.75)，SJF 更优。

---

例题 3（时间片轮转 RR）

进程	到达	运行
P1	0	5
P2	1	3
P3	2	1

时间片 q=1：

时刻	0-1	1-2	2-3	3-4	4-5	5-6	6-7	7-8	8-9
进程	P1	P2	P3	P1	P2	P1	P2	P1	—

• P1: 完成=8, 周转=8, 等待=3
• P2: 完成=7, 周转=6, 等待=3
• P3: 完成=3, 周转=1, 等待=0

$$平均周转 = (8+6+1)/3 = 5$$

---

例题 4（SRTF 抢占式）

进程	到达	运行
P1	0	7
P2	2	4
P3	4	1

SRTF（每次选剩余时间最短的，可抢占）：

时刻	0-2	2-4	4-5	5-8	8-12
进程	P1	P2	P3	P2	P1

• P1: 完成=12, 周转=12, 等待=5
• P2: 完成=8, 周转=6, 等待=2
• P3: 完成=5, 周转=1, 等待=0

$$平均周转 = (12+6+1)/3 = 6.33$$

---

演练二十一：位示图与空闲区管理

例题 1（位示图计算）

磁盘 1000 块，位示图每个字 16 位。块号 35 对应位示图第几行第几列？

解题：

• 行号 = 35 / 16 = 2（第3行，从0开始）
• 列号 = 35 % 16 = 3（第4列）

位示图大小 = 1000 / 16 = 62.5 → 63 个字 = 126 字节

---

例题 2（空闲区分配）

空闲区表：(起始, 长度) = {(10,30), (50,10), (80,50), (120,20)}

请求分配 20 块，分别用首次适应、最佳适应、最坏适应。

首次适应（从头找第一个≥20的）：

• (10,30) ≥ 20 ✓ → 分配 (10,20)，剩余 (30,10)
• 结果：空闲区 = {(30,10), (50,10), (80,50), (120,20)}

最佳适应（找最小且≥20的）：

• (80,50)=50, (120,20)=20 → 选 (120,20)
• 分配 (120,20)，剩余无
• 结果：空闲区 = {(10,30), (50,10), (80,50)}

最坏适应（找最大的）：

• (80,50)=50 最大 → 分配 (80,20)，剩余 (100,30)
• 结果：空闲区 = {(10,30), (50,10), (100,30), (120,20)}

---

第三部分：速记卡 + 口诀总表

---

速记卡（考前一页纸）

【进度】
PERT: (O+4M+P)/6, σ=(P-O)/6, σ总=√(Σσ²)
CPM: ES=max(前EF), LF=min(后LS), TF=LF-EF
FF=min(后ES)-EF, 关键路径 TF=0
赶工斜率=(赶工成本-正常成本)/(正常工期-赶工工期)

【挣值】
EV=BAC×完成%, CPI=EV/AC, SPI=EV/PV
EAC_典型=BAC/CPI, EAC_非典型=AC+(BAC-EV)
EAC_悲观=AC+(BAC-EV)/(CPI×SPI)
ETC=EAC-AC, VAC=BAC-EAC, TCPI=(BAC-EV)/(BAC-AC)

【功能点】
UFC=Σ(权重×数量), FP=UFC×(0.65+0.01×ΣFi)
权重: EI/EQ=3,4,6; EO=4,5,7; EIF=5,7,10; ILF=7,10,15
ΣFi=35 时系数=1.0

【COCOMO】
E=a×KLOC^b, D=c×E^d
有机: 2.4,1.05,2.5,0.38 | 半分离: 3.0,1.12,2.5,0.35 | 嵌入: 3.6,1.20,2.5,0.32

【圈复杂度】
V(G)=判定+1=E-N+2=区域数
复合条件&&拆开算, case各算一个

【可靠性】
串联: R=ΠRi | 并联: R=1-Π(1-Ri)
A=MTBF/(MTBF+MTTR), MTBF=1/λ
2/3表决: 3R²(1-R)+R³
两并一倍半

【性能】
Little: L=λW | MIPS=主频(MHz)/CPI | T=指令×CPI/主频
Amdahl: S=1/((1-p)+p/n), 极限=1/(1-p)
并发数=吞吐量×响应时间

【存储】
Cache: T=h×快+(1-h)×慢
IOPS=1000/(寻道+旋转), 旋转=30000/RPM
7200转→4.17ms, 10000转→3ms, 15000转→2ms
RAID: 0全1半5减1, 6减2加10半
内存: 1K=2¹⁰, 1M=2²⁰, 1G=2³⁰, 末地址=起始+容量-1

【网络】
子网: 2^n网, 2^h-2主机, 掩码=256-2^h, 步长=2^h
海明: 2^r≥m+r+1, 纠错位=S的十进制
码距: 检e→≥e+1, 纠t→≥2t+1, 检e纠t→≥e+t+1
CRC: 补零→模2除→余数

【风险】
EMV=Σ(概率×收益), RE=概率×损失
决策树: 圆算期望, 方框取最大, 从右向左

【数据库】
候选键: 左必入, 右必不入, 待定要组合
范式: 1NF不可分, 2NF消部分, 3NF消传递, BCNF决定必键

【PV操作】
P: S=S-1, S<0则阻塞; V: S=S+1, S<=0则唤醒
互斥初值1, 同步初值0, 资源初值N
前驱图: 每边一信号量, 前驱末尾V, 后继开头P
互斥信号量(n进程)取值: [-(n-1), 1]
生产者-消费者: empty=N, full=0, mutex=1
  P操作顺序不能颠倒: 先P(empty/full)再P(mutex)

【页面置换】
OPT: 淘汰未来最久不用; FIFO: 淘汰最早进入
LRU: 淘汰最近最久未用; CLOCK: 二次机会
缺页率=缺页次数/总访问次数
FIFO可能Belady异常, LRU/OPT不会
EAT=h×(TLB+内存)+(1-h)×(TLB+2×内存)

【内存管理】
页式: 页号=地址/页大小, 偏移=地址%页大小, 物理地址=块号×页大小+偏移
段式: 物理地址=段基址+段内偏移, 需检查段长越界
段页式: 段号→页表→块号, 3次访存
访存次数: 页式2次, 段式2次, 段页式3次, 二级页表3次
多级页表: 32位/4KB页/4B项 → 10+10+12

【文件索引】
n=块大小/索引项大小
最大文件=10B+nB+n²B+n³B (直接10+一级1+二级1+三级1)
磁盘容量=柱面×磁头×扇区×扇区大小
LBN→物理: 柱面=LBN/(磁头×扇区), 磁头=(LBN%(磁头×扇区))/扇区, 扇区=LBN%扇区

【死锁】
四条件: 互斥/占有等待/不剥夺/循环等待
银行家: Need=Max-Allocation, 安全序列逐个找Need≤Work
资源数无死锁: m≥n(k-1)+1

【磁盘调度】
FCFS按序, SSTF最近, SCAN电梯折返, C-SCAN单向跳回
寻道距离=相邻柱面差之和

【进程调度】
周转=完成-到达, 等待=周转-运行, 带权周转=周转/运行
SJF平均周转最优, SRTF抢占式SJF

【位示图】
位图大小=块数/8字节, 行=块号/字长, 列=块号%字长
空闲区: 首次适应(从头找), 最佳适应(最小够用), 最坏适应(最大)

【2的幂次】
1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536

【覆盖标准】
语一判二条二组四路二

---

口诀总表（谐音双轨）

#	题型	顺口溜	谐音
1	CPM 正向逆向	正早最大加，逆晚最小减，时差零关键	郑早最大家，李晚最小姐，差零关见
2	PERT 期望	乐悲加四倍中，除六得期望；极差除以六，标准差便当	岳飞加四倍中，除六得期望
3	EVM 三值	EV 是核心，减 AC 省成本，减 PV 超进度	衣屋是核心，减埃西省成本，减皮维超进度
4	EVM 预测	典型除 CPI，非典型加剩余，悲观再除 SPI	—
5	圈复杂度	边减点加二，判定加一数，区域数最直	边减点加二，判官加一数
6	功能点权重	输入查询三四六，输出四五七，接口五七十，逻辑七十十五	三叔四舅四姑五妻五姐七姨七叔十姥
7	功能点系数	六五加零点一，因子和来调；三十五为中，恰好等于一	刘武加林丹，因子和来调
8	COCOMO 系数	二四三六，指数一二；二五不变，周期点三八	二四三六一零五二零
9	COCOMO 类型	小五十大三百，有机半离嵌	—
10	可靠性	串联乘可靠，并联减失效；可用除总时，失效率倒置	串乘并减，可用除总
11	并联 MTBF	两并一倍半	—
12	MIPS	频除 CPI 得 MIPS，指令乘 CPI 除频得时	频除 CPI，指 C 除频
13	Amdahl	九成十倍，九五二十，九九一百	—
14	内存编址	K 十 M 二十 G 三十，容量除片得片数	凯十埃姆二十吉三十
15	RAID	0 全 1 半 5 减 1，6 减 2 加 10 半	—
16	子网划分	借 n 位出二 n 网，主机位减二得数	借位出网，主机减二
17	海明码	二的 r 次大于等于 m 加 r 加一	—
18	EMV 决策树	圆圈算期望，方框取最大；从右向左推，概率和为一	圆算方取，右左推一
19	范式	一不可分，二消部分，三消传递，BC 决定必键	一分二部三传，毕决定必键
20	候选键	左必右必不，待定要组合	—
21	内聚排序	偶逻时过通顺功	我老师过通顺功
22	覆盖标准	语一判二条二组四路二	—
23	Z 值概率	零五十八四九七	—
24	赶工	斜率最低优先赶，关键路径要盯紧	—
25	PV 操作	P 申请减一负则等，V 释放加一唤等待；互斥初一同步零，资源初值等于 N	皮减负等，维加唤等；互一同零资 N
26	前驱图	前驱末尾 V，后继开头 P，每边一信号	—
27	页面置换	最优未来最远，先进先出最早，最近最久未用，时钟二次机会	优远先早近久时二
28	Belady	FIFO 可能反常，LRU 永不反常	—
29	内存管理	页式除余偏移定，段式基址加偏移；段页三次访存，页式两次段式两次	页除余偏，段基加偏；段页三访，页二段二
30	文件索引	直接十块一级 n，二级 n 方三 n 三方；块大除项得 n 值，最大文件四项加	直十一 n 二 n 方三 n 三方
31	死锁条件	互占不循四条件，安全序列逐个找；Need 小于 Work 则分配，全完成则安全	互占不循，需小工则分，全成则安
32	资源数	资源大于进程乘减一加一	m≥n(k−1)+1
33	磁盘调度	先来先服务最公平，最短寻道性能好；电梯扫描到端折返，循环扫描只走一边	先先公，短短好，电扫折返环扫单
34	调度指标	周转等于完成减到达，等待等于周转减运行	—
35	位示图	位图一位代表一块，一为分配零空闲；首适最佳最坏循环，分配策略各不同	位图一零，首佳最循

---

高频考点速算清单

题型	关键公式	速算要点
关键路径	TF=LF−EF	找最长路径
PERT	(O+4M+P)/6	先算 O+P 再加 4M
挣值	EV=BAC×完成%	先定 EV 再套公式
EAC 典型	BAC/CPI	CPI>1 省钱
圈复杂度	判定+1	数 if/while/for
功能点	UFC×(0.65+0.01ΣF)	ΣF=35 时系数=1
串联可靠	∏Ri	0.9×0.9=0.81
并联可靠	1−∏(1−Ri)	0.9 并 0.9=0.99
Cache	h×快+(1−h)×慢	命中率转小数
海明码	2^r≥m+r+1	m=4→r=3
子网	2^n 子网, 2^h−2 主机	借位 n，主机 h
Amdahl	1/((1−p)+p/n)	p=0.9→≤10 倍
EMV	Σ概率×收益	圆算方取
Little	L=λW	单位统一
MIPS	主频/CPI	GHz→×1000
PV 互斥取值	[−(n−1), 1]	n 个进程竞争
页面置换	缺页率=缺页/访问	LRU 永不 Belady
页式地址	块号×页大小+偏移	页号=地址/页大小
段页式访存	3次	段表+页表+数据
文件索引	10B+nB+n²B+n³B	n=块大小/索引项
银行家	Need≤Work 则安全	逐个找安全序列
无死锁	m≥n(k−1)+1	m资源n进程k最大
磁盘 SCAN	到端折返	SSTF 最近优先
周转时间	完成−到达	等待=周转−运行

---

考前复习路线

阶段	内容	重点
第一遍	通读公式速查	理解每个公式含义
第二遍	盖住解答做演练	对照速算技巧
第三遍	只看速记卡+口诀总表	默写公式
考前一晚	速记卡 + 口诀总表	口诀默诵

必考重点（每年出现）：

1. 挣值管理（EVM）— 三值、偏差、EAC 预测
2. 关键路径（CPM）— ES/EF/LS/LF/TF/FF
3. 圈复杂度 — 判定节点+1
4. 可靠性 — 串并联混联
5. 页面置换（FIFO/LRU/OPT）— 缺页次数与缺页率
6. PV 操作 — 前驱图转 PV、信号量取值范围
7. 页式/段式地址转换 — 逻辑地址转物理地址
8. 银行家算法 — 安全性序列判断
9. 文件索引 — 最大文件大小计算
10. 磁盘调度 — FCFS/SSTF/SCAN 寻道距离