计算机原理 学习路线与考试题型

学习路线

依赖关系：

1. 位和数字：进制、端序、整数、浮点、位运算。
2. 机器级程序：x86-64 寄存器、寻址、条件码、函数栈。
3. 实验方法：Data Lab 的位级构造，Bomb Lab 的反汇编，Attack Lab 的栈与 ROP，Cache Lab 的模拟和转置优化。
4. 系统机制：流水线、存储器、链接、ECF、虚拟内存、I/O、网络。
5. 题型模板：浮点转换、Cache 模拟、多级页表、fork 输出、信号竞争、socket 代码。

考试高频题：

• 选择题：判断概念边界和易错说法。
• 填空题：寄存器、权限码、页偏移、Cache 组数、系统调用名称。
• 解答题：解释机制、推导公式、写代码片段、根据汇编还原 C。
• 实验迁移题：不要求照抄实验答案，但会考实验背后的机制。

镜像卷子题型地图

题型	出现主题	必会能力
IEEE 754 判断	C/E 卷	规格化、非规格化、偏置、无穷、NaN、舍入
自定义浮点格式	C/E 卷	计算最大规格化数，十进制转位模式
x86-64 汇编反推 C	C/E 卷	识别递归、参数寄存器、%rbx 保存、返回值
Cache 地址拆分	C/E/F 卷	由容量、块大小、相联度求组数、索引、tag
Cache 访问模拟	C/F 卷	按 LRU 或直接映射逐步更新缓存
AMAT	E 卷	命中时间、缺失率、缺失惩罚
链接强弱符号	C/E 卷	强符号、弱符号、重复定义规则
静态库/动态库/PIC	E 卷	加载时区别、共享库为何需要位置无关
ECF 与信号	C/E 卷	pending/blocked、不排队、安全 handler、竞争修复
fork 输出	D 卷	进程数翻倍、输出缓冲影响
多级页表	C/E 卷	页偏移、PTE 数、每级索引位、页表空间
TLB vs Page Fault	D 卷	TLB miss 不等于缺页
I/O 与 DMA	E 卷	设备交互方式、DMA 优势
Unix I/O	D 卷	权限码、文件描述符、重定向
网络编程	C/D/F 卷	listen、TCP 连接、HTTP 持久连接、服务器框架
扩展 OS	D/F 卷	线程、协程、死锁、信号量、NAT、RAID

做题时总结的策略

概念题找“绝对化错误”：

• “总是”“一定”“完全消除”“所有”通常危险。
• TLB miss 不一定 page fault，malloc 不一定立即分配物理页。
• 信号不是可靠队列，同类型 pending 信号最多记一个。
• TCP 是字节流，不保留应用层消息边界。

计算题写参数表：

主题	参数	关键公式
Cache	$C,E,B,S,s,b,t,m$	$C=S\times E\times B$，$S=2^s$，$B=2^b$，$t=m-s-b$
页表	VA 位数、页大小、PTE 大小、级数	页偏移 $p={\log }_{2}P$，每页 PTE 数 $P/\text{PTE size}$
浮点	符号位、阶码位、尾数位、Bias	规格化 $V=(-1{)}^s\times M\times 2^E$
AMAT	命中时间、缺失率、缺失惩罚	$\text{AMAT}=T_{hit}+r_{miss}\times T_{miss}$
Amdahl	被优化部分占比、加速倍数	$S=\frac{1}{(1-\alpha )+\alpha /k}$

从几次实验到考试

Data Lab：

• 用掩码取字段，用 ~x+1 表示 -x。
• 比较大小时先考虑符号不同，再考虑减法溢出。
• 浮点位级题按 sign/exponent/fraction 拆分，先处理 NaN/Inf/0/denorm。

Bomb Lab：

• 先从字符串、跳转目标和比较指令定位 phase 目标。
• 看到递归汇编时，先写 base case，再写 recursive step。
• cmpq a,b 在 AT&T 中等价于计算 b-a 后设置条件码。

Attack Lab：

• ret 取栈顶 8 字节写入 %rip。
• x86-64 前 6 个整数/指针参数：%rdi,%rsi,%rdx,%rcx,%r8,%r9。
• 小端序写地址：最低有效字节放在最低地址。
• ROP 的本质是把栈布置成 gadget 地址和数据的序列。

Cache Lab：

• M 操作是 load + store，同地址第二次必 hit。
• 矩阵转置优化关注空间局部性、冲突不命中、对角线处理。
• 64 x 64 比 32 x 32 更容易冲突，常用 8x8 拆成 4x4 的策略。

易错清单

• 单精度阶码全 0 的指数不是普通的 $1-\text{Bias}$ 以外再减 1；非规格化数使用 $E=1-\text{Bias}$，尾数无隐含 1。
• float 只有 24 位有效精度，并非所有 int 都能无损转回；double 对 32 位 int 可以精确表示。
• leaq 不访存，常被编译器当整数加法/乘法组合使用。
• movq 和 leaq 通常不修改条件码，addq/subq/andq/xorq/cmpq/testq 会影响条件码。
• 写回 Cache 的主存不总是最新，脏块替换时才写回。
• printf 不是 async-signal-safe，信号处理函数中应尽量只设置 volatile sig_atomic_t 标志或调用安全函数。
• HTTP/1.1 持久连接复用 TCP 连接，但代理必须正确解析请求边界、响应长度和连接关闭语义。