Lecture 25: 期末复习——全课程知识串联与题型演练 (Exam Review: Putting It All Together)

目录 · ← l24 · appendix →

Lecture 25: 期末复习——全课程知识串联与题型演练 (Exam Review: Putting It All Together)

讲义对应：CMU 15-213 Final Review Session（素材：F25-final.txt，144 页复习讲义；配套 recitation：F25-rec13_slides.txt — Final Exam Review） 教材对应：CS:APP3e 全书 Ch.1–12（复习课不引入新知识点，只做横向串联与题型归纳） 关联 Lab：全部 11 个 lab——L0 C Programming、L1 Data、L2 Bomb、L3 Attack、L4 Cache、L5 Malloc、L6 Shell、L7 Proxy、L8 SFS

本章结构说明：本章按规范仍采用 7 段式，但依复习课性质做两处约定调整——25.3 改为“典型考题精解”（用代码/汇编/表格作答的 6 道跨章节真题，含完整计算过程），25.4 改为“Lab 与期末考点的对应表”。（对应 PLAN.md 对第 25 讲的说明。）

25.1 概述

前 24 讲是一条从”比特”一路向上爬到”并发服务器”的栈式叙事：第 2 讲告诉你内存里只有比特，第 3–6 讲告诉你编译器怎样把这些比特翻译成机器指令与栈帧，第 9–10 讲告诉你 CPU 怎样用缓存掩盖内存延迟，第 11–14 讲告诉你操作系统怎样用虚拟内存和分配器伪造出”独占大内存”的假象，第 7、8 讲告诉链接器与内核怎样把程序装起来并让它与外界交互，第 15 讲教你怎么写得更快，第 16–20 讲把视角推到进程、文件与网络，第 21–24 讲则揭示以上所有抽象在并发下都会崩塌、需要显式同步来重建。

期末考要检的正是这条链是否完整：一道题往往同时需要两层知识（例如”给一段汇编判断缓冲区溢出”= Ch.3 + Ch.5 + Ch.9）。因此本章不重复各讲细节（详见对应章节），而是做三件事：画一张知识依赖地图、列一份按章的高频考点与易错点清单、用 6 道覆盖全课程的真题演练把”会看”变成”会算”。承接 Lecture 24 的并行性能，本章是全书的收束。

25.2 核心概念与底层机制图解

25.2.1 全课程知识地图（Knowledge Dependency Map）

• 定义与目的：把 24 讲抽象成一条自底向上的依赖链：每一层都只能使用它下面的层所提供的抽象，而每一层的”漏洞”（溢出、别名、缺失、竞态）又会在上面的层里表现为 bug。这张图同时标出每一环对应的 lab。
• 直观解释（”它是什么？”）：把它想成一栋正在施工的楼。Ch.2 是地基（比特），Ch.3–6 是钢结构（指令、栈、缓存），Ch.7 是管线（链接与加载），Ch.9–14 是水电与仓库（虚拟内存、堆），Ch.16–20 是外墙与门禁（进程、I/O、网络），Ch.12 是消防与疏散（同步）。你在顶层（并发服务器）看到的所有”漏水”，渗漏点几乎总在下面某一层的接缝处。
• 底层机制图解：

+------------------------------------------------------------+
| Ch.1 系统漫游: 源文件>预处理>编译>汇编>链接>加载           |
+------------------------------------------------------------+

                             |
+------------------+ +------------------+ +------------------+
| Ch.2 表示        | | Ch.3-4 机器码    | | Ch.7 链接        |
| 位/补码/字节序   | | 汇编/控制流      | | 符号/重定位      |
| IEEE 754 浮点    | | set/j/cmp/寻址   | | 静态/共享库      |
| > L1 Data        | | > L2 Bomb        | | PIC/GOT/PLT      |
+------------------+ +------------------+ +------------------+
         |                    |                    |
+---------------------------+ +---------------------------+     +--------------------------------------+
| Ch.3.7 过程               | | Ch.3.8-11 进阶            |     | Ch.6.1-3 存储层次                    |
| 栈帧/调用约定             | | 数组/结构体/联合          |     | 局部性: 时间/空间                    |
| 缓冲区溢出                | | 对齐/填充/浮点            |     | SRAM-DRAM-磁盘                       |
| > L3 Attack               | | > L3 / L1                 |     | > L4 Cache                           |
+---------------------------+ +---------------------------+     +--------------------------------------+
              |                             |                                       |
+---------------------------+                                   +--------------------------------------+
| Ch.9.1-8 虚拟内存         |                                   | Ch.6.4-7 高速缓存                    |
| 页表/TLB/缺页             |                                   | S/E/B 位域/组相联                    |
| mmap / COW                |                                   | AMAT / 3C / 分块                     |
| > L5 Malloc               |                                   | > L4 Cache                           |
+---------------------------+                                   +--------------------------------------+
              |                                                                     |
+---------------------------+                                   +--------------------------------------+
| Ch.9.9-12 分配器          |                                   | Ch.5 代码优化                        |
| 隐式/显式/分离链表        |                                   | CPE / 延迟界限                       |
| 边界标记/碎片/利用率      |                                   | 吞吐量界限/多累加器                  |
| > L5 Malloc               |                                   | 内存别名 / restrict                  |
+---------------------------+                                   | > L4 / L5                            |
                                                                +--------------------------------------+
              |                                                                     |
+---------------------------+
| Ch.8 异常/进程/信号       |
| fork/execve/waitpid       |
| 信号语义/竞态             |
| setjmp/longjmp            |
| > L6 Shell                |
+---------------------------+
              |                             |
+---------------------------+ +---------------------------+
| Ch.10 系统级 I/O          | | Ch.11 网络编程            |
| rio/fd 表/dup2            | | 协议分层/套接字           |
| 重定向                    | | listenfd vs connfd        |
| > L6 / L7                 | | HTTP 报文                 |
+---------------------------+ | > L7 Proxy                |
                              +---------------------------+
              |                             |
+------------------------------------------------------------+
| Ch.12 并发与同步 (全课汇总)                                |
| 线程模型/进度图/信号量                                     |
| 生产者-消费者/读者-写者                                    |
| 线程安全四类/死锁/伪共享                                   |
| Amdahl-Gustafson/强弱扩展                                  |
| > L7 Proxy / L8 SFS                                        |
+------------------------------------------------------------+
^ Ch.12 之下各层提供"正确性"(内存模型); 右侧 Ch.6/5 提供"性能"(缓存一致性)

• 与机器码/硬件的对应：图的左列（Ch.2→3→9→8→10→11）是”软件把硬件能力包装成抽象”的路径；图的右列（Ch.6→5）是”硬件性能反过来约束软件写法”的路径。两条路径在 Ch.12 汇合，因为并发的正确性取决于内存模型（左），而并发的性能取决于缓存一致性（右）——这正是 L7/L8 同时考”锁”与”伪共享”的原因。

25.2.2 高频考点清单（按章节）

25.2.3 核心机制速查汇总图

虚拟内存与缓存是期末”计算题”的两大主战场，而它们共享同一套位域分解思想，可以画在一张图里：

+--------------------------------------------------------------+
| 虚拟地址 VA (m 位):  VPN (m-p 位)  |  VPO (p 位)             |
+--------------------------------------------------------------+
                                                                  VPO == PPO (页偏移逐位相同)
                                                                  |
                               |                                  v
                               v                                  +--------------------------------------+
+--------------------------------------+                          | 物理地址 PA                          |
| TLB: S_T 组 x E_T 路                 |                          | PPN | 未用 | CI | CO                 |
| TLBI = VPN 低 log2(S_T) 位           |                          | (CI/CT 必须在 PA 上取)               |
| TLBT = VPN 其余高位                  |                          +--------------------------------------+
| 命中 -> 直接得到 PPN                 |
| 缺失 -> 查页表 (可能缺页)            |                          |
+--------------------------------------+                          v
                                                                  +--------------------------------------+
+--------------------------------------+                          | Cache: S 组 x E 路 x B 字节          |
| 地址翻译顺序 (解题五步)              |                          | 命中: valid && tag == CT             |
| 1 由 VA 拆出 VPN / VPO               |                          | 逐出: LRU                            |
| 2 用 TLBI+TLBT 查 TLB                |                          | AMAT = t_hit + mr x t_miss           |
| 3 TLB 命中得 PPN; 否则查页表         |                          | 3C: 强制/容量/冲突                   |
| 4 PPN||VPO 得 PA                     |                          +--------------------------------------+
| 5 PA 拆 CO/CI/CT 查 Cache            |
+--------------------------------------+
       |                                                            |
       +----------------------- 关键区分 ---------------------------+
       从 VA 取: VPN / VPO / TLBI / TLBT
       从 PA 取: PPN / CO / CI / CT  (VPO == PPO 是唯一复用项)

• 直观解释：TLB 是”贴在手边的便利贴”（页表目录的缓存），缓存是”办公桌上的文件夹”（内存内容的缓存），页表是”图书馆总目录”（在 DRAM 里）。查地址就是：先看便利贴（TLB）→ 没有就翻总目录（页表，可能要去书库=磁盘）→ 拿到书架号（PPN）→ 再去桌上找那本书（cache，可能要去书库=内存）。
• 底层机制对应：三次查表由硬件 MMU + L1 dTLB + L1 dCache 流水化完成；movq (%rdi), %rax 这一条指令就会同时触发 TLB 查表与 cache 查询，任何一次缺失都会让流水线停顿上百周期。

25.2.4 易错点 Top 20

1. “负数右移一定补 1。” 错——C 标准中 >> 对负数是实现定义（implementation-defined），只是 x86-64 的 sar 恰好补符号位；跨平台不可依赖。
2. “movzbl 会把高位清零。” 对——零扩展（zero-extension）。但要记住movsbl 不会：它做符号扩展，会把 char 的负值变成负 int。
3. “leaq 会访存。” 错——leaq 只做地址算术，从不访问内存；movq 才访存，这是读汇编题的第一分水岭。
4. “cmp %edx, %edi 是算 edx - edi。” 错——AT&T 是”源在前、目的在后”，该指令算 edi - edx，因此 jg 表示 edi > edx。
5. “结构体大小等于各成员大小之和。” 错——必须按”最大基本类型对齐”补齐内部空洞与尾部填充；struct{int;char;short;char[3];} 是 12 字节而非 10。
6. “select 的 fd_set 可以重复使用。” 错——select 返回时会就地修改 fd_set（只保留就绪位），每次调用前必须重新 FD_ZERO+FD_SET。
7. “信号会排队，发 3 次就能处理 3 次。” 错——标准信号不排队，同类 pending 信号会被合并（coalesce），所以 SIGUSR1 发三次可能只处理一次。
8. “wait 和 waitpid(-1, ...) 完全一样。” 近似但不完全——waitpid 可指定 WNOHANG/WUNTRACED 并等待特定子进程；Shell Lab 里回收”任意子进程”必须靠 waitpid(-1, &status, WNOHANG\|WUNTRACED)。
9. “父进程 fork 后子进程有自己的文件偏移。” 错——fd 表被复制，但打开文件表与 v-node 表共享，父子共用同一个文件偏移（这就是 Shell 重定向会互相影响的根源）。
10. “dup2(oldfd, newfd) 会关闭 oldfd。” 错——它只让 newfd 指向 oldfd 的打开文件表项；oldfd 仍然打开，两个描述符共享偏移。
11. “sem_wait 可以放在 mutex 之后。” 在生产者-消费者中错——消费者若先拿 mutex 再等 full，缓冲区空时它持锁等待，生产者永远拿不到锁 → 死锁（本讲题 5 已实测复现）。
12. “信号量初值就是资源数量，mutex 用 1。” 对但要注意区分：empty=N、full=0 表示”缓冲槽”与”已填项”；把 full 初值写成 N 会让消费者读空数据。
13. “mmap 的 MAP_SHARED 和 MAP_PRIVATE 只是名字差异。” 错——MAP_PRIVATE 采用写时复制（copy-on-write），写不会回写文件；MAP_SHARED 的修改最终写回文件并对其他映射可见。
14. “直接映射缓存一定比组相联慢。” 错——直接映射硬件最简单、命中时间最短；组相联的价值在于降低冲突缺失，代价是更长的命中时间与更多比较器。
15. “t = m - s - b 里的 s 是总组数的位数。” 表述不清易错——s = log2(S) 是组索引位数，S 才是组数；把 S 直接当位数会算错 tag 位宽。
16. “多累加器循环展开后 CPE 可以无限下降。” 错——展开只突破延迟界限，最终会被吞吐量界限（功能单元数量）卡住，CS:APP 中浮点加法吞吐量界限为 1.00。
17. “restrict 只是给编译器的优化提示、无副作用。” 需要小心——它是程序员对编译器的承诺：指针不重叠。若承诺错误（内存确实别名），编译器会生成结果错误的代码，属 UB。
18. “volatile 能保证线程安全。” 错——volatile 只禁止编译器把访问优化掉/合并，不提供原子性、不提供内存序（本讲题 5 中 volatile long++ 实测仍丢更新）。
19. “Amdahl 定律说明多核没用。” 错——它说明的是上限：$p=0.95$ 时理论上限 $20\times$；强扩展关注固定问题规模的加速比，弱扩展（Gustafson）关注固定每核工作量的可扩展性，两者回答不同问题。
20. “伪共享是逻辑错误。” 错——伪共享不影响正确性，只影响性能：不同线程写同一缓存块内的不同变量，会因缓存一致性协议不断使对方的块失效。

25.3 典型考题精解

验证说明：本节所有数值结果均由 /tmp/csapp_final/ 下的 C 程序真实编译运行核对（float_probe.c、asm_probe.c、cache_sim.c、vm_probe.c、num_probe.c、conc_deadlock.c），命令与输出片段随题给出。

题 1（Ch.2 位运算与浮点）——给出 IEEE 754 表示并判断位运算结果

题目：某教学浮点格式为 1 位符号 + 4 位阶码 + 3 位尾数（共 8 位），阶码偏置 $2^{k-1}-1 = 7$。求： (a) 0x48 表示的十进制值；(b) 6.0 的位模式；(c) IEEE 754 半精度（1/5/10，bias 15）中 0x3E00 与 0xC800 的值；(d) -7 / 2 与 -7 >> 1 是否相等。

解答（完整过程）：

(a) 0x48 = 0100 1000。按 1+4+3 拆：符号 $s=0$；阶码 $e=1001_2=9$；尾数 $f=000_2=0$。 因 $e\neq0$（规格化）：$M = 1 + f/2^3 = 1 + 0 = 1.0$，$E = e - \text{bias} = 9-7 = 2$。 \(V = (-1)^0 \times 1.0 \times 2^{2} = 4.0\) 注意非规格化情形：0x08 = 0000 1000 → $e=0$，$f=1$，则 $M = f/8 = 0.125$，$E = 1-\text{bias} = -6$，$V = 0.125/64 = 0.015625$。若误用 $1+f/8$ 会得到 $0.0157$ 之外的错误值。

(b) $6.0 = 1.5 \times 2^2$ → $M=1.5$，$E=2$ → $e = E+\text{bias} = 9 = 1001_2$。 $f = (M-1)\times 2^3 = 0.5\times 8 = 4 = 100_2$。故位模式 $= 0\,\vert \,1001\,\vert \,100 = 0100\,1100 = \mathbf{0x4C}$。

(c) 半精度 1+5+10，bias $= 2^{5-1}-1 = 15$。 0x3E00 = 0011 1110 0000 0000：$s=0$，$e=01111_2=15$，$f=1000000000_2=512$。 $M = 1+512/1024 = 1.5$，$E = 15-15 = 0$ → $V = 1.5\times 2^0 = \mathbf{1.5}$。 0xC800 = 1100 1000 0000 0000：$s=1$，$e=10010_2=18$，$f=0$。 $M=1.0$，$E=18-15=3$ → $V = -1.0\times2^3 = \mathbf{-8.0}$。 （顺带注意：同一 16 位串按 short 解释是 -14336，按 unsigned short 是 51200——同一个比特，三种含义。）

(d) -7 / 2 在 C 中是向零取整 $= -3$；-7 >> 1 在 x86-64 上是 sar（算术右移）$= \lfloor -7/2 \rfloor = -4$。两者不等，且右移结果是实现定义。

实测验证（float_probe.c，gcc -g -Wall -std=c11 float_probe.c -o float_probe -lm）：

[toy]  decode(0x00)=0  decode(0x08)=0.015625  decode(0x48)=4  decode(0x78)=256
[toy]  encode(6.0)=0x4c  encode(1.5)=0x3c  encode(0.03125)=0x10
[toy]  自洽检查 encode(6.0)->0x4c->6
[half] encode(1.9375) = 0x3fc0 ; decode = 1.9375
[half] 0x3E00 -> 1.5 ; 0xC800 -> -8
[bits] -7/2 = -3 , -7>>1 = -4 (实现定义，本机为算术右移)

失分点：忘记非规格化（$e=0$）时 $M$ 不带隐含 1 且 $E=1-\text{bias}$；把 0x48 的 4 位阶码读成 3 位。

题 2（Ch.3/Ch.7 汇编阅读）——把汇编还原成 C，并求输入范围

题目：(a) 下面是 15-213 期中真题 S11 Q3 的 fun 汇编（结构体 struct node {void *data; struct node *next;}），补全 C 代码。(b) 另一段”神秘函数” f（参数为 unsigned y）问：$f$ 返回 8 的输入范围是多少？

# (a) 摘录（AT&T 语法；完整见 rec13 讲义）
114d: push   %r12
114f: push   %rbp
1150: push   %rbx
1151: mov    %rdi,%rbx          # 保存 n
1154: test   %rdi,%rdi
1157: je     1192 <fun+0x49>    # n == NULL -> 返回 NULL
1159: mov    %rsi,%rbp          # 保存函数指针 f
115c: mov    0x8(%rdi),%rdi     # 取 n->next
1160: call   1149 <fun>         # 递归
1165: mov    %rax,%r12          # a = 递归结果
1168: mov    %rbx,%rdi
116b: call   *%rbp              # 调用 f(n)
116d: test   %eax,%eax
116f: jg     1179 <fun+0x30>    # f(n) > 0 时进入分配分支
1171: mov    %r12,%rax          # 否则返回 a
...
1179: mov    $0x10,%edi         # malloc(16)
117e: call   1050 <malloc@plt>
1183: mov    (%rbx),%rdx        # 取 n->data
1186: mov    %rdx,(%rax)        # b->data = n->data
1189: mov    %r12,0x8(%rax)     # b->next = a
118d: mov    %rax,%r12
1190: jmp    1171               # 返回 b

解答（完整过程）：

(a) 逐行对应：%rdi 是 n、%rsi 是 f、%rbx/%rbp/%r12 是被调用者保存寄存器（因此入口先 push 三个，保证递归调用不破坏自己）。test %rdi,%rdi; je 对应空指针检查。mov 0x8(%rdi),%rdi; call fun 说明先递归处理 n->next，返回值放 %r12（即 a）。call *%rbp 是通过间接调用使用函数指针。test %eax,%eax; jg 即 f(n) > 0。分配分支里 mov $0x10,%edi 说明 sizeof(node_t) = 8 + 8 = 16；(%rbx) 是 n->data（偏移 0），0x8(%rax) 是 b->next（偏移 8）。等价 C：

node_t *fun(node_t *n, int f(node_t *)) {
    node_t *a, *b;
    if (n == NULL) return NULL;          /* 1154-1157 */
    a = fun(n->next, f);                 /* 115c-1165 */
    if (f(n) > 0) {                      /* 116b-116f */
        b = malloc(16);                  /* 1179-117e */
        b->data = n->data;               /* 1183-1186 */
        b->next = a;                     /* 1189 */
        return b;                        /* 118d-1190 */
    }
    return a;                            /* 1171-1178 */
}

语义：递归地反向重建链表，只保留谓词 f 为正的元素。

(b) 神秘函数 f 的汇编（rec13 讲义原文）：

f:
    leal   1(%rdi), %ecx      # c = y + 1
    movl   $0, %edx           # d = 0
.L5:
    leal   -1(%rcx), %eax     # a0 = c - 1
    cmpl   %edx, %eax
    je     .L8                # c - 1 == d -> 退出
    leal   (%rdx,%rcx), %eax  # a = d + c
    shrl   %eax               # a >>= 1  → a = (c+d)/2（无符号除 2）
    movl   %eax, %esi
    imull  %eax, %esi         # e = a * a
    cmpl   %esi, %edi
    jb     .L9                # y < e（无符号）→ c = a
    movl   %eax, %edx         # 否则 d = a
    jmp    .L5
.L9:
    movl   %eax, %ecx
    jmp    .L5
.L8:
    movl   %edx, %eax
    ret                       # 返回 d

等价 C：

unsigned f(unsigned y) {
    unsigned c = y + 1, d = 0;
    while (d != c - 1) {
        unsigned a = (c + d) / 2;
        if (y < a * a) c = a;      /* jb：无符号比较 */
        else           d = a;
    }
    return d;
}

这是整数平方根的下取整（二分查找）。要求返回 $8$，需 $8^2 \le y < 9^2$，即 $64 \le y \le 80$。

实测验证（asm_probe.c，gcc -g -Wall -std=c11 asm_probe.c -o asm_probe）：

>>> f(y) == 8 的输入范围: [64, 80]  (共 17 个)
>>> 检查 f(64)=8 f(80)=8 f(81)=9 f(63)=7

同时用 gcc -O1 -S asm_gen.c 生成的 filter 汇编与讲义逐行一致（pushq %r12/%rbp/%rbx、movq 8(%rdi),%rdi、call *%rbp、movl $16,%edi），证实”讲义汇编 = 真实 gcc 输出”。

失分点：把 jb（无符号 below）当成有符号 jl；漏看 shrl 的无符号语义（leal+shrl 而非 sarl）；数错 %r12/%rbp/%rbx 的保存/恢复配对。

题 3（Ch.6 缓存计算）——组相联缓存的缺失率与 AMAT

题目：一个 2 路组相联、4 组、64 字节块的缓存。设 A、B 均按块对齐。按讲义流程扫描：pass 1 访问 A[0..63]（步长 4，共 16 次访存）；pass 2 在不清空缓存的前提下访问 B[0..63]（步长 4）。求 (a) 地址位域分解；(b) pass 1 与 pass 2 的缺失率；(c) 若 L1 命中时间 4 周期、L1 缺失率 5%、L2 命中时间 12 周期、L2 缺失率 40%、内存 200 周期，求 AMAT。

解答（完整过程）：

(a) $S=4 \Rightarrow s=\log_2 4 = 2$ 位组索引；$B=64 \Rightarrow b=\log_2 64 = 6$ 位块偏移；标记位 $t = m-2-6$。 \(\underbrace{\cdots\cdots}_{\text{tag }t}\;\underbrace{00}_{\text{CI}(s=2)}\;\underbrace{000000}_{\text{CO}(b=6)}\) 容量 $C = S\times E\times B = 4\times2\times64 = 512$ 字节。

(b) 块偏移 6 位 ⇒ 每块装 $64/4 = 16$ 个 int。步长 4 每次跨 16 字节，故连续 4 次迭代落在同一块内：

• pass 1（16 次访存，4 次冷缺失）：每批 4 次中第 1 次缺失、后 3 次命中 → $mr_1 = \frac{1}{4} = 25\%$。
• pass 2：讲义给出的账是”每批 4 次迭代有 4 次命中 A、1 次 B 的冷缺失、3 次 B 命中” → $mr_2 = \frac{1}{8} = 12.5\%$。这一账成立的前提是 A/B 的对应块被映射到不同的组（2 路，每批恰好占用 2 路而无需逐出）。按讲义结论：缓存大小恰好等于工作集（512B = 4 块 A + 4 块 B），故 pass 2 无逐出（eviction）。

  补充说明：若 A、B 基址差恰好是 256 字节的整数倍，则 A 与 B 的同序号块映射到同一组，2 路正好容纳 2 个块仍不逐出；但若再引入第三个数组 C，就会开始冲突缺失。

(c) AMAT 逐层展开（缺失代价必须逐层递归）： \(\text{AMAT} = t_{L1} + mr_{L1}\times\big(t_{L2} + mr_{L2}\times t_{mem}\big) = 4 + 0.05\times(12 + 0.40\times200) = 4 + 0.05\times92 = 4 + 4.6 = \mathbf{8.6}\ \text{周期}\) 若基准 CPI 为 1.0，则 $\text{CPI} = 1.0 + 0.05\times92 = 5.6$，单靠缓存缺失就慢 5.6 倍。

实测验证（cache_sim.c，gcc -O2 -Wall -std=c11 cache_sim.c -o cache_sim；模拟器实现了 LRU 与 3C 统计）：

pass1: hits=12 misses=4 evictions=0  miss rate=0.2500
pass2(交错 A/B, 缓存含 pass1 现场): hits=28 misses=4 evictions=0  miss rate=0.1250
地址分解: b=6 s=2
[stride8] hits=0 misses=64 evictions=56 miss rate=1.0000

（第 4 行是对照实验：同一直接映射缓存取步长 8，缺失率 100%——说明”步长与块大小的关系”比”缓存总容量”更能决定缺失率。）

失分点：忘记 pass 2 复用 pass 1 的缓存现场而按”全冷”重算；把 AMAT 写成 $t_{L1}+mr_{L1}\times t_{L2}+mr_{L1}\times mr_{L2}\times t_{mem}$ 之外的漏项形式。

题 4（Ch.9 虚拟内存与分配器）——地址翻译 + 页表规模 + 堆利用率

题目：(a) 系统参数：VA 18 位、PA 12 位、页 512 字节、TLB 2 组 8 路、Cache 4 组 2 路 4 字节块。翻译虚拟地址 0x1A9F4，给出 VPN/TLBI/TLBT/PPN/CO/CI/CT（已知 TLB 命中，PPN = 0x3）。(b) 另一系统 32 位 VA、24 位 PA、4KB 页、4 字节 PTE，比较单级与两级页表的空间。(c) 隐式空闲链表堆：序言 8B、A 块（16B 载荷）、B 块（24B 载荷）、一个 24B 空闲块、尾声 8B，头部/脚部各 4 字节，求堆利用率。

解答（完整过程）：

(a) 页 $512 = 2^9$ ⇒ VPO $= 9$ 位，VPN $= 18-9 = 9$ 位。 0x1A9F4 写全 18 位：011010100 111110100（VPN | VPO）。

• VPO $= 0x1F4$；VPN $= 011010100_2 = 0xD4$。
• TLB 共 $2\times8=16$ 项，$S_T=2$ ⇒ TLBI 取 VPN 低 1 位 $= 0$；TLBT 取剩余 8 位 $= 01101010_2 = 0x6A$。
• TLB 命中 → PPN $= 0x3$。$(0x3 \ll 9) + 0x1F4 = 0x7F4$。
• Cache：CO 取 PA 低 $b=2$ 位 $\Rightarrow CO = 0$；CI 取次 $s=2$ 位 $\Rightarrow CI = 01_2 = 1$；CT 为其余 $12-2-2 = 8$ 位 $\Rightarrow CT = 0x7F$。

汇总：VPN=0xD4，TLBI=0x00，TLBT=0x6A，TLB Hit=Y，PPN=0x3，PA=0x7F4，CO=0x00，CI=0x01，CT=0x7F。

(b) 单级：PTE 总数 $=2^{32}/2^{12} = 2^{20} = 1048576$；每页可放 $4096/4 = 1024 = 2^{10}$ 个 PTE。故需 $2^{20}/2^{10} = 2^{10} = 1024$ 页，占 $1048576\times4\text{B} = 4\text{MB} = 4096\text{KB}$。 两级：外层页表页数 $= 2^{10}/2^{10} = 1$ 页；一次访存只需”整个外层（1 页）+ 1 个内层页 = 2 页 = 8KB“，比 4096KB 省 512 倍。

要点：VPN $= 20$ 位，按每级 10 位切分成两级（$20/10 = 2$ 级）；$\log_2(\text{PTE per page}) = 10$ 正是每级的索引位宽。

(c) 逐块列账（头部除序言/尾声外均为 8 字节开销：4B 头 + 4B 脚）： | 块 | 载荷 | 总大小 | |—|—|—| | 序言 | 0 | 8 | | A（已分配） | 16 | 24 | | B（已分配） | 24 | 32 | | C（空闲） | 0 | 24 | | 尾声 | 0 | 8 | | 合计 | 40 | 96 |

\(U = \frac{40}{96} = 0.4167 \approx \mathbf{41.67\%}\) 注意空闲块 C 的载荷不计入利用率分子但计入分母；若把 C 拆分利用，利用率可显著提升。

实测验证（vm_probe.c + num_probe.c）：

VA  = 0x1a9f4 = 011010100111110100 (18 bits)
VPO = 0x1f4  (低 9 位)        VPN = 0xd4  (高 9 位 = 011010100)
TLBI = 0 (VPN 低位 1 位)      TLBT = 0x6a (VPN 其余 8 位)
PA  = 0x7f4 = 011111110100 (12 bits)
CO  = 0    CI  = 0x1    CT  = 0x7f
单级: 1048576 PTE, 1024 页 = 4096 KB      两级: 2 页 = 8 KB (省 512 倍)
载荷合计 = 40, 堆总大小 = 96, 利用率 = 40/96 = 0.4167 = 41.67%

失分点：TLBI 从 VPN（不是 VA）低位取；CO/CI/CT 从 PA（不是 VA）取；算利用率时把空闲块的”载荷”也算进分子。

题 5（Ch.8 + Ch.12 并发推演）——进程数、信号合并、信号量死锁

题目：(a) 父进程连续调用两次 fork，其中 pid1 == 0 的子进程再 fork 一次；四个进程各打印一次自己的局部 count，可能的输出序列有多少种？(b) 子进程在 2–4 次 kill(getppid(), SIGUSR1\|SIGUSR2) 中随机选择，父进程每收到一个信号打印一次，打印 1 的最小/最大次数是多少？如何保证打印 2 次？(c) 生产者-消费者中若消费者写成 sem_wait(&mutex); sem_wait(&full);，会怎样？

解答（完整过程）：

(a) 进程树：父 → 子 1、子 2；子 1 → 孙。共 4 个进程。各进程的 pid1/pid2 判断与 count 变化： | 进程 | pid1 | pid2 | count | |—|—|—|—| | 父 | ≠0 | ≠0 | 3 | | 子 1 | ==0 | ≠0 | 2 | | 子 2 | ≠0 | ==0 | 0 | | 孙 | ==0 | ==0 | 2 | 四个打印值中出现 2 两次（子 1 与孙），故不同输出序列数 $= \frac{4!}{2!} = \mathbf{12}$ 种。若在父/子 1 中插入 wait(NULL)，则子 1 必须等孙结束、父必须等子 1 结束，输出顺序被约束（子 1→孙、子 2→父等偏序成立），序列数减少。

(b) 标准信号不排队：若多次只发 SIGUSR1，多次信号合并为一次待处理（pending），父进程可能只打印 1 次；若每次 SIGUSR1 与 SIGUSR2 交替，两类信号不合并，最多打印 4 次。故范围是 1–4 次。保证打印 2 次的办法：精确地发一次 SIGUSR1 和一次 SIGUSR2（不同编号的信号不会互相合并）。

(c) 死锁。消费者持有 mutex 后去等 full；缓冲区空时 full=0 使它永久阻塞，而生产者又必须先拿 mutex 才能放入数据 → 循环等待（circular wait），四个死锁必要条件（互斥、持有并等待、无抢占、循环等待）齐备。

实测验证（conc_deadlock.c，用 fork 隔离以免挂住终端）：

--- BAD ---
父进程观察：子进程 3 秒内未退出，被强杀 → 判定为【死锁】
原因：消费者先 sem_wait(&mutex) 再 sem_wait(&full)；缓冲区空时它持锁等待，
      生产者无法取得 mutex 来填充缓冲区 → 循环等待（circular wait）。
--- GOOD ---
child: 正常结束 produced=2000 consumed=2000
父进程观察：子进程在 0.1 秒内正常退出（code=0）→ 无死锁

同一程序的竞态实验也印证了”不可靠的同步”：

naive   counter = 992875  (期望 4000000)   ← volatile long++ 仍丢更新
atomic  counter = 4000000 (期望 4000000)
mutex   counter = 4000000 (期望 4000000)

失分点：把”信号会排队”当默认；在进度图中漏画”同一进程内指令不可跨越”的约束；把 sem_wait(&mutex) 与 sem_wait(&full) 的顺序当成无关紧要。

题 6（Ch.5 + Ch.12 性能计算）——CPE、吞吐量界限与 Amdahl 上限

题目：单累加器循环 for (i=0;i<n;i++) acc += a[i]; 与 4 累加器展开版（每元素 1 次加法，共 4 个独立依赖链）。已知浮点加法延迟 3 周期、吞吐量界限 1.00 加法/周期。(a) 两版本的 CPE 界限各是多少？理论最大加速比？(b) 实测 (a) 并解释差距。(c) 若程序 95% 可并行，$N=16$ 时的强扩展加速比与 Amdahl 上限？

解答（完整过程）：

(a) 单累加器中每次 acc += a[i] 依赖上一次结果 ⇒ 受延迟界限约束： \(\text{CPE}_{1} \ge \text{加法延迟} = 3.00\) 4 累加器把依赖链拆成 4 条独立链，流水线可连续发射 ⇒ 受吞吐量界限约束： \(\text{CPE}_{4} \ge \frac{1}{\text{吞吐量}} = 1.00\) 理论最大加速比 $= 3.00/1.00 = \mathbf{3\times}$。这正是”循环展开 + 多累加器”的全部意义：突破延迟界限，逼近吞吐量界限。

(b) 实测（cpe_probe.c，rdtscp 计时，100 万元素 × 200 轮取最小值）：

combine1: 2374907 cycles  -> CPE = 2.375
combine4:  612451 cycles  -> CPE = 0.612
speedup(1/4) = 3.88x

combine4 的 0.612 < 1.00 是因为 gcc 同时启用了向量化/超标量发射（每周期可完成多于一条加法），而吞吐量界限 1.00 是 CS:APP 依据”单发射 + 无向量化”模型给出的教学值；combine1 的 2.375 < 3.00 则是因为部分元素命中了已计算的依赖流水。关键结论不变：加速比约 3–4 倍，量级与理论一致。

(c) Amdahl 强扩展：$S(N) = \dfrac{1}{(1-p) + p/N}$，$p=0.95$： \(S(16) = \frac{1}{0.05 + 0.95/16} = \frac{1}{0.05+0.059375} = \frac{1}{0.109375} \approx \mathbf{9.14}\) \(S(\infty) = \frac{1}{1-p} = \frac{1}{0.05} = \mathbf{20}\) 即 $N=16$ 时已到上限的 45.7%，再堆核心收益递减；若换成弱扩展（Gustafson，固定每核工作量），则加速比可随 $N$ 线性增长——所以”要不要堆核”取决于你问的是哪个问题。

实测验证（num_probe.c）：N=16 : 强扩展 = 9.143、N->inf 上限 = 20.0、N=16 时达到上限的 45.7%。

失分点：把”展开”说成能突破吞吐量界限；Amdahl 公式分母写成 $p/N$ 而漏掉串行项 $(1-p)$。

25.4 Lab 与期末考点的对应表

期末命题与 lab 高度同源——每一个 lab 都对应一类必考题型。下表是复习时的”以 lab 为索引”的检索表：

说明：L1/L2/L4/L5 是计算题的主要来源；L6/L7/L8 是推演题的主要来源；L3 常与 Ch.3 汇编题合并出题（”这段汇编是否存在溢出漏洞？”）。复习时若时间紧张，按”L1→L2→L4→L5→L8”的顺序回看 lab 的 handout（源码在 csapp_data/handouts/），覆盖了分值最密集的五类题。

25.5 常见错误与调试技巧

25.5.1 期末八大失分点与对应调试命令

• 位运算题忽略类型宽度：把 int 当 32 位以外的宽度，或 int 溢出后仍按数学值推理。调试：gcc -fsanitize=undefined,address 跑一遍，用 printf("%d %u %#x\n", x, (unsigned)x, (unsigned)x) 三视图对照。
• 汇编题读反 AT&T 操作数顺序：cmp %edx,%edi 误读成 edx-edi，sub %rax,%rbx 误读成 rbx-rax。调试：objdump -d -M intel 对照 Intel 语法确认方向；gdb -tui 单步看 info registers。
• 缓存题算错位宽：把组数 $S$ 当作索引位数 $s$；忘记 $t=m-s-b$。调试：先列 $S,E,B$ → 算 $s,b$ → 再画位域框，务必让 $b+s+t=m$ 闭合。
• VM 题从 VA 取 CI/CT：CI/CT 必须在 PA 上取（VPO=PPO 是唯一可以从 VA 复用的部分）。调试：先手算 PA，再分解；用本讲 vm_probe.c 的思路写 10 行 C 验算。
• 进程/信号题假设信号排队：忘记同类信号合并，导致算错输出次数。调试：strace -f -e trace=process,signal ./prog 观察真实 SIGUSR1 递达次数与 wait4 返回顺序。
• 文件 I/O 题混淆三张表：把 fd 表当作共享（实际按进程复制），或以为 dup2 会关闭源 fd。调试：lsof -p <pid> 看 FD/TYPE/OFFSET 列，父子进程对比同一文件的偏移是否同步增长。
• 并发推演漏画进度图：直接给出”一个线程跑完再跑另一个”的简单答案。调试：在草稿纸上画出两轴为两线程指令序的二维进度图，标出不可跨越区域（临界区）与”禁止区域”（$H_1,L_1,U_1,S_1,H_2,L_2,U_2,S_2$ 造成的 $H_2$ 不得在 $U_1$ 前）。
• 分配器题把空闲块载荷算进利用率：利用率分子只含已分配的载荷。调试：用 gdb 打印堆区 x/32gx heap_start，配 python 脚本逐块解析头部的 size & ~0x7 与最低位 alloc 标志。

25.5.2 考试形式与应试策略

• 形式（依课程 exam 页面与 F25 复习讲义）：闭卷纸质考试，3 小时；可带 2 张双面 A4/letter 手写或打印的”cheat sheet”（期中为 1 张、80 分钟）；不许使用计算器与任何电子设备；可能要求手绘图表，字迹不可辨认直接 0 分。课程明确提示”考卷只使用 64 位 x86 汇编（旧卷中的 32 位 IA-32 题不会出现）”，且题目与书面作业风格相近但可能更难。
• 题型分布（归纳自官方题库）：① 概念辨析（术语/机制选择与判断，约占 20–25%）；② 计算（缓存、VM、CPE、利用率、加速比，约占 25–30%）；③ 代码/汇编阅读（补全 C、写出等价 C、判断溢出，约占 25%）；④ 推演（多进程/信号/信号量输出与死锁判断，约占 20%）。
• 时间分配建议（180 分钟）：第 1 遍 90 分钟只做有把握的 60%，并在题号前标记把握度；第 2 遍 60 分钟攻计算题（先把公式写在草稿上再代数，避免心算错）；最后 30 分钟回查标记题与单位/进制（每道计算题至少留 1 分钟做量纲自检，如”缺失率必须在 $[0,1]$”）。
• cheat sheet 该写什么：$C=S\times E\times B$ 全套位域公式；AMAT 递归式；$S(N)=1/((1-p)+p/N)$；IEEE 754 的 $M/E$ 规则（含非规格化）；x86-64 参数寄存器顺序与 callee-saved 清单；隐式/显式空闲链表的块结构与边界标记；生产者-消费者/读者-写者的信号量初值；三张表（fd/打开文件/v-node）的共享关系。不要抄大段代码——考场上抄代码的时间成本高于现推。

25.6 关键要点

25.6.1 六条收束性结论

• 一切抽象都是”伪造”，考试考的正是伪造的接缝：栈帧、cache、虚拟内存、文件描述符都在隐藏真实硬件，而期末题几乎总落在”抽象失效处”（溢出、冲突缺失、缺页、信号合并、竞态）。
• 位域思维贯穿全课：IEEE 754 的 $s\vert e\vert f$、缓存的 $t\vert s\vert b$、虚拟地址的 $\text{VPN}\vert \text{VPO}$，本质是同一套”切位—解释”技巧；能把三者画在同一张图里，就掌握了半张卷子。
• 性能 = 消除串行依赖 + 提升局部性：Ch.5 的展开与多累加器攻”依赖”，Ch.6 的分块与循环顺序攻”局部性”；两者都是”改代码改不变复杂度”的免费午餐。
• 并发的正确性只能靠同步原语，不能靠 volatile 或”指令看起来是原子的”：题 5 实测 volatile long++ 在 4 线程 × 100 万次下丢掉了 75% 的更新。
• Amdahl 给上限、Gustafson 给希望：$p=0.95$ 时强扩展上限 $20\times$；”是否继续加核”取决于你固定的是问题规模还是每核工作量。
• Lab 即题库：11 个 lab 的机制与期末四类题型一一对应，”回看 lab 的代码 + 重做 lab 的坑”是最省时的复习法。

25.6.2 三种剩余时间的复习路线

剩 1 周（约 42 小时，最稳）

• Day 1–2（12h）：Ch.2 + Ch.3。重做 L1 全部位运算函数；用 L2 的 6 个 phase 逐题读汇编，做到”看到 set/j 就能反推 C 条件”。
• Day 3（6h）：Ch.6。手推 6–8 道缓存题（不同 $s/E/b$ + 不同步长），把缺失率与 AMAT 算到能反射性写出公式。
• Day 4（6h）：Ch.9 + 分配器。重画 L5 的隐式/显式/分离链表结构，练 4 道利用率与边界标记题。
• Day 5（6h）：Ch.8 + Ch.10 + Ch.11。把 L6 Shell 的 eval/信号处理逻辑默写一遍；写一个最小 HTTP 响应头。
• Day 6（6h）：Ch.12。画进度图、推演生产者-消费者/读者-写者、做 20 道”输出是什么/是否死锁”。
• Day 7（6h）：Ch.5 + Ch.7 + 全真模拟。限时 3 小时做官方 practice final，把错题整理进 cheat sheet。

剩 3 天（约 18 小时，抓大放小）

• Day 1：计算题主攻——Ch.2 浮点/位运算、Ch.6 缓存、Ch.9 VM 与利用率（这三类占计算分的大头），每类 5 题。
• Day 2：阅读与推演——Ch.3 汇编阅读（L2 精读）+ Ch.8/Ch.12（进程、信号、信号量推演），各花半天。
• Day 3：模拟 + 补漏——上午限时真题，下午只补错题对应的那一个问题点，晚上整理 cheat sheet。

剩 1 天（约 6 小时，保底策略）

• 0–2h：默写 cheat sheet 的全部公式（缓存位域、AMAT、IEEE 754、Amdahl、利用率、传参寄存器）。公式不会，计算题全丢。
• 2–4h：做 2 道缓存题 + 2 道 VM 题 + 2 道信号量推演题（这 6 道覆盖约 50% 的计算与推演分）。
• 4–5h：读 L2 的两个 phase 汇编 + 讲义里的 S11 Q3（本讲题 2），恢复”读汇编”手感。
• 5–6h：过一遍本讲 25.2.4 易错点 Top 20 与 25.5.1 八大失分点，然后早睡。放弃冷门细节（如 CLOCK 算法实现、setjmp 的寄存器保存细节），性价比太低。

25.6.3 全课程一句话总结（15 句）

1. 内存里只有比特，含义完全由程序赋予——同一串 16 位可以是 1.5、-14336 或 51200。
2. 整数运算在 $2^w$ 上做模运算，溢出不是错误而是定义；无符号与有符号的转换会静默改变比较结果（-1 < 1 为真，但 (unsigned)-1 < 1 为假）。
3. IEEE 754 用 $V=(-1)^sM2^E$ 统一表示，规格化隐含 1、非规格化不隐含且阶码固定 $1-\text{bias}$。
4. 编译器把 C 翻译成几类固定”套路”：lea 做算术、cmp+set/j 做条件、call/ret 配栈帧做过程。
5. 参数走 %rdi,%rsi,%rdx,%rcx,%r8,%r9，返回值在 %rax，callee-saved 寄存器必须由被调用者保全、%rsp 16 字节对齐。
6. 栈向下增长且返回地址就躺在局部数组上方——这是缓冲区溢出与 ROP 攻击的全部物质基础。
7. 结构体按最大成员对齐并补齐空洞，“能编译”不等于”内存布局如你所想”。
8. 缓存用 $C=S\times E\times B$ 换取时间：命中率由访问模式决定，而非仅由容量决定（题 3 的步长实验缺失率 0% → 100%）。
9. 优化只有两条主线：消除关键路径上的串行依赖（展开、多累加器）与提升局部性（分块、循环重排）；$\text{CPE}$ 永远不会低于吞吐量界限。
10. 链接器做符号解析与重定位，强符号只能有一个；共享库靠 PIC + GOT + PLT 实现”代码位置无关的延迟绑定”。
11. 虚拟内存把”地址”变成了”查表结果”，同时给出了隔离、按需加载与离散分配三大能力。
12. 多级页表 + TLB 是”时间与空间的折中”：页表省内存，TLB 省时间；mmap 与 COW 让 fork 与共享库变得廉价。
13. 好的分配器要在吞吐量（快速适配）与利用率（最佳适配/分离链表）之间权衡，边界标记是”常数时间合并”的关键。
14. 进程是”独享地址空间的执行流”，fork 复制 fd 表但共享打开文件表；信号不排队、处理函数必须异步信号安全。
15. 系统级 I/O 只有”字节流 + 文件描述符”两个概念，网络是”字节流 + 套接字地址”，而并发是”把同步问题显式化”——用信号量或互斥锁把竞态变成正确性，用扩大并行比例把 Amdahl 上限推高。

25.7 思考题（带答案）

Q1（计算题·缓存）：缓存 $S=8, E=2, B=32$，字长 4 字节，地址 16 位。求 $s,b,t$；若访问序列为 $0x0000, 0x0020, 0x0040, 0x0060, 0x0000$（字节地址），逐次判命中并给出最终各行内容。

答：$s=\log_2 8=3$，$b=\log_2 32=5$，$t=16-3-5=8$。组索引 $=$ 地址的 bit[5..7]：

• 0x0000 → 组 0，tag 0：缺失（冷缺失），装入。
• 0x0020 → 组 1，tag 0：缺失（冷缺失）。
• 0x0040 → 组 2，tag 0：缺失（冷缺失）。
• 0x0060 → 组 3，tag 0：缺失（冷缺失）。
• 0x0000 → 组 0，tag 0：命中。 共 4 次缺失 1 次命中，$mr = 4/5 = 80\%$；最终组 0–3 各有一行有效（tag 均为 0），另一路为空。

Q2（推演题·”看起来对但错在哪”）：有同学说”既然 fork 会复制地址空间，那父子的全局变量互不影响，所以 Shell Lab 里在子进程 dup2 重定向不会影响父进程，因此子进程也不需要恢复 fd“。这句话错在哪？

答：前一半对、后一半错。fork 确实复制了 fd 表，所以子进程中 dup2 只改变子进程的 fd 表项，父进程不受影响——但反过来说明：如果父进程自己做了 dup2（例如 Shell 在内建命令里重定向），它必须保存并恢复原 fd（典型做法 int saved = dup(STDOUT_FILENO)，用后 dup2(saved, STDOUT_FILENO); close(saved);），否则重定向会永久污染父 Shell 的标准输出，后续所有外部命令都会写进文件。此外容易忽略：fd 表虽复制，打开文件表与其文件偏移是共享的，所以父子对同一文件的读写会互相推进偏移。

Q3（计算题·性能）：某程序串行部分占 8%。求 $N=8$ 时的强扩展加速比，以及 $N\to\infty$ 的上限；若改用弱扩展（固定每核工作量），阐明加速比为何可能接近线性。

答：$p=0.92$，$S(8)=\dfrac{1}{0.08+0.92/8}=\dfrac{1}{0.08+0.115}=5.13$。上限 $S(\infty)=\dfrac{1}{0.08}=12.5\times$。弱扩展固定每核工作量，故问题规模随 $N$ 增长，串行部分 $s$ 与总串行开销 $s$（而非占比）保持不变，总时间 $= s + p\cdot N/N_{\text{core}}$，$S(N)\approx (s+pN)/s$ 随 $N$ 近似线性——这就是为什么”是否加核”取决于问题是固定规模还是固定每核规模。

Q4（辨析题）：为什么说”直接映射缓存不缺容量却可能表现极差”？请用题 3 的对照实验数据说明。

答：直接映射每组只有 1 路，任何两个映射到同一组的块都会互相逐出，这就是冲突缺失（conflict miss），与容量无关。题 3 的对照实验里，8 组、32 字节块、共 256 字节的直接映射缓存，按 32 字节步长扫描 512 个 int（每个块只取 1 个字）时缺失率 = 100%（64 次缺失、56 次逐出）——缓存完全没起到作用，因为每次访问都换了一个块。改成组相联（增加 $E$）或改变访问顺序（分块）就能消除这类缺失。结论：缺失率是访问模式与缓存几何结构的函数，容量只是其中一个变量。