本目录存放按“主干道 → 旁路”组织的科目知识图谱。每个板块先回答四个问题：
- 它要解决什么问题？
- 没有它会怎样？
- 输入和输出是什么？
- 数据经过了哪些通用流程？
当前先整理 存储系统知识图谱、CPU + 指令系统知识图谱、输入输出系统知识图谱、进程与同步知识图谱、数制与数据表示知识图谱、计算机网络层次知识图谱 和 程序执行与内存知识图谱。图谱中的节点链接到对应的 408 知识点页面，适合在开始刷题前建立全局地图，也适合做完题后定位自己断开的知识边。
核心知识图谱
用主干问题把 408 四门科目的零散知识连接起来。
1 - 存储系统
从存储层次到一次虚拟地址访问，建立存储系统的主干和旁路。
一句话模型
存储系统用多层次的容量、速度和成本折中，把 CPU 产生的地址和数据请求，最终转换成对某个存储介质的访问；局部性让高速的小容量层有效，映射和替换机制负责在层之间搬运数据。
三层递进
本板块的图谱遵循同一条学习路径：
- 简单：只看主要模块和上下层关系，先回答“存储系统有哪些层”。
- 中等：加入一次访问的主干流程，回答“地址和数据怎样在层之间流动”。
- 复杂：叠加异常分支、操作系统参与、文件系统和持久化 I/O，回答“不同 miss 发生后谁负责、状态如何改变”。
后续新增的子模块也遵循这个约定：先给模块总览，再逐步展开地址字段、策略、状态和边界条件。
简单图谱：存储层次
这张图先建立“谁和谁相邻”的地图。越靠近 CPU，访问通常越快、容量越小、单位成本越高；越靠近外存，容量越大但延迟越高。
# 存储系统
## CPU 可见的访问路径
- 虚拟地址
- MMU：地址翻译与保护
- TLB：缓存页表项
- Cache：缓存主存块
- 主存：DRAM 页面与内核数据
## 数据保存的介质
- 外存：SSD / HDD
- 文件系统：把块组织成文件和目录
- 交换区：缺页时的后备存储
## 每层都在解决的问题
- Cache：如何利用时间局部性和空间局部性降低平均访问时间
- 虚拟存储：如何让进程拥有独立、连续且大于物理内存的地址空间
- 文件系统：如何为持久化数据提供命名、组织和保护
- 磁盘调度：如何降低寻道与旋转带来的 I/O 延迟
对应的基础知识：
中等图谱：一次访问如何完成
主干问题是：CPU 给出一个虚拟地址后，数据怎样被找到；如果当前层没有，下一步由谁决定？
最小路径
- 指令产生虚拟地址
VA = VPN + offset。 - MMU 先查 TLB；命中后得到物理页框号
PPN，拼出物理地址PA = PPN + offset。 - Cache 用
PA（具体实现也可能使用 VIPT 等变体）拆分标记、组号和块内偏移。 - Cache 命中，直接把数据返回 CPU。
一次 miss 如何展开
- TLB 未命中：硬件或操作系统按体系结构查页表；页表项无效时触发缺页异常。
- Cache 未命中：按映射方式定位主存块，必要时依据替换策略淘汰旧块，再把整块装入 Cache。
- 缺页：操作系统从可执行文件或交换区换入页面；内存不足时先置换页面，更新页表和 TLB，再重新执行访问。
- 持久化写入：文件系统把文件偏移映射到磁盘/SSD 块，设备控制器和 DMA 完成介质 I/O。
复杂图谱：从虚拟地址到持久化 I/O
这张图在中等图谱上继续叠加三类细节：地址翻译的页表分支、Cache 的命中/填充分支，以及缺页后由操作系统和文件系统驱动的外存访问。
阅读时可以沿三条路径追踪：
- 命中路径：CPU → TLB → Cache → 数据返回。
- 容量 miss 路径：TLB miss → 页表；Cache miss → 主存块填充。
- 持久化路径：缺页或文件读写 → 文件系统 → 块设备 → SSD/HDD → DMA/中断通知。
子模块图谱：Cache 内部
整块存储系统建立后，再单独放大 Cache 这个高频子模块。它把“地址如何定位”和“未命中后如何处理”拆开，便于继续添加具体计算题中的位数和替换策略。
Cache 子图的阅读顺序是：物理地址拆分 → 依据映射方式定位候选行 → 比较 Tag 和 Valid → 命中返回或 miss → 按替换策略装入 → 按写策略更新下层。
子模块图谱：虚拟存储器内部
再看一个由硬件和操作系统共同完成的子模块。它把“地址翻译成功”和“页面尚未驻留”两条路径分开，突出页表有效位是从正常访问转入缺页处理的决策点。
虚拟存储子图的阅读顺序是：虚拟地址拆分 → 查询 TLB → 未命中时遍历页表 → 检查 Valid → 有效时拼出物理地址，无效时进入缺页异常 → 选择空闲页框或置换页面 → 从后备存储换入并更新页表/TLB → 重新执行访存。
关键问题
为什么要分层？
单一存储器无法同时满足低延迟、大容量和低成本。分层把高频数据放在更快的层，把容量压力推向更慢的层；局部性是这种折中的前提。
Cache 和虚拟存储解决的是同一个问题吗？
它们都利用局部性，但管理对象不同：Cache 搬运主存块，主要由硬件透明管理；虚拟存储搬运页面，由操作系统参与并提供进程隔离、保护和换入换出。
地址翻译和数据访问谁负责？
操作系统创建并维护页表，MMU 执行地址翻译；地址翻译得到的物理地址随后交给 Cache/主存路径完成数据访问。不要把“维护页表”和“查页表”混为一谈。
地址翻译和数据访问的流程是什么？
一次读操作可以沿着下面的顺序追踪：
- 形成虚拟地址：CPU 根据指令得到
VA = VPN + offset，其中offset是页内偏移。 - 翻译页面号：MMU 先用
VPN查询 TLB。命中时直接得到PPN；未命中时查页表，若页表项有效则把映射结果写入 TLB。 - 处理缺页分支：若页表项无效，MMU 触发缺页异常，操作系统从可执行文件或交换区换入页面，必要时置换一个物理页框，更新页表后重新执行这次访问。
- 拼接物理地址：
PPN与原来的offset拼成PA = PPN + offset。地址翻译只改变页号，页内偏移保持不变。 - 访问 Cache：Cache 根据物理地址拆分出的
Tag / Index / Block Offset定位候选行；Tag 相等且 Valid 有效时命中，直接返回数据。 - 处理 Cache miss：未命中时访问主存，把包含目标字的整个主存块装入 Cache；若需要淘汰旧块，则先依据替换策略选择牺牲行，再按写策略处理被替换数据。
- 返回数据：Cache 或主存将目标字返回 CPU；如果是写操作，还要根据写直达/写回等策略更新下层。
因此，地址翻译解决“这个虚拟地址对应哪个物理页框”，数据访问解决“物理地址所在的数据块在哪里”；前者主要由 MMU、TLB 和页表完成，后者主要由 Cache 和主存完成。
旁路清单
主干建立后，再展开这些容易在真题中组合出现的细节：
- Cache 的直接映射、全相联、组相联，以及 LRU / FIFO 等替换策略
- 写直达、写回、写分配与一致性问题
- 多级页表、TLB 有效位/脏位/访问位和页面置换算法
- SSD 的页、块、垃圾回收、磨损均衡与闪存写入限制
- HDD 的寻道时间、旋转延迟、传输时间和 SCAN/C-SCAN 调度
- 文件系统的索引分配、空闲空间管理、挂载和 VFS
2 - CPU + 指令系统
从 ISA 抽象到一条指令的执行，再到流水线和异常控制。
一句话模型
指令系统定义软件可观察的机器接口，CPU 的控制器把指令译码为控制信号，数据通路依次驱动寄存器、ALU、存储器和 PC 完成状态更新；流水线再把不同指令的阶段重叠起来提高吞吐量。
三层递进
本板块同样遵循“简单 → 中等 → 复杂”的叠加方式：
- 简单：先区分 ISA、CPU 组成和控制器/数据通路的职责。
- 中等：追踪一条
LOAD或ADD指令从取指到写回的主干数据流。 - 复杂：加入流水线重叠、数据/控制冒险、异常中断和访存等待，观察控制状态如何改变。
简单图谱：CPU 与指令系统的边界
先回答“软件交给 CPU 什么、CPU 内部由谁完成”：ISA 规定指令语义和可见状态，微架构用控制器和数据通路实现这些语义。
# CPU + 指令系统
## 软件可见接口：ISA
- 指令操作码与语义
- 指令格式和操作数
- 寻址方式与数据类型
- 通用寄存器、PC、状态寄存器
- 异常、中断与特权规则
## CPU 内部实现
- 控制器：取指、译码、时序和控制信号
- 数据通路：寄存器、ALU、内部总线和存储器接口
- 执行单元：算术逻辑、分支、访存
## 性能扩展
- 多周期与流水线
- 冒险处理与转发
- 多核、SIMD 与硬件多线程
中等图谱：一条指令的执行流程
主干问题是：一条机器指令如何从二进制编码变成寄存器或内存状态的变化？
以 LOAD R1, [R2 + imm] 为例：
- 取指 IF：PC 提供指令地址，指令进入 IR，同时 PC 更新为下一条指令地址。
- 译码 ID：控制器解析 opcode、寄存器字段和立即数，读取
R2并生成后续控制信号。 - 执行 EX：ALU 计算有效地址
R2 + imm。 - 访存 MEM：用有效地址读取数据存储器，结果进入数据寄存器或流水线寄存器。
- 写回 WB：把数据写入
R1，提交这条指令对寄存器状态的改变。
对 ADD R1, R2, R3，EX 阶段改为计算 R2 + R3，MEM 阶段为空操作，WB 仍把 ALU 结果写入 R1。
复杂图谱：流水线与异常控制
复杂图在中等流程上叠加“多条指令同时处于不同阶段”，并标出三种冒险和异常/中断如何打断正常提交。
阅读时沿三条路径追踪：
- 正常路径：IF → ID → EX → MEM → WB，每个时钟周期推进一个阶段。
- 数据冒险路径：后一条指令依赖前一条尚未写回的结果，通过转发、暂停或插入气泡保持数据正确。
- 控制/异常路径：分支改变下一条 PC，预测错误需要冲刷流水线；中断或异常保存现场、转入处理程序，返回后再恢复执行。
子模块图谱：指令格式与寻址方式
指令系统内部可以先单独展开“编码如何指定操作数”。这张图把 opcode、地址字段和有效地址计算连接起来，适合继续添加零地址/一地址/二地址/三地址指令的例题。
子图阅读顺序是：指令字 → opcode 译码 → 地址字段解释 → 按寻址方式得到操作数或有效地址 → 送入寄存器/ALU/存储器。
子模块图谱：CPU 结构
再把 CPU 本身拆开，观察“控制信号由谁产生、数据经过哪些部件、结果如何回到状态寄存器”。这张图适合和上一张指令格式图连起来阅读：上一张解释输入如何编码，这一张解释编码进入 CPU 后如何驱动硬件。
CPU 结构子图的阅读顺序是：PC/IR 取指 → 指令译码器识别操作 → 控制器按时序发出控制信号 → 寄存器组提供操作数 → ALU 或访存单元执行 → 数据写回寄存器、PC 和状态寄存器。
关键问题
ISA 和微架构为什么要分开？
ISA 规定软件能观察到的行为，微架构决定内部如何实现。同一 ISA 可以由不同的流水线、Cache、执行单元和分支预测器实现。
控制器和数据通路如何配合？
控制器根据 opcode 和时序产生控制信号，数据通路按照这些信号完成寄存器传送、ALU 运算和存储器读写；控制器决定“做什么微操作”，数据通路真正搬运和计算数据。
为什么流水线能提高吞吐量却不能让单条指令变快？
流水线让不同指令的 IF/ID/EX/MEM/WB 阶段重叠，稳态下每周期可完成一条指令；单条指令仍需经过全部阶段，冒险和流水线寄存器还会引入额外停顿。
异常和中断为什么必须进入执行流程？
它们会改变 PC、特权状态和现场保存位置。CPU 必须在规定的边界暂停或完成当前指令，转到处理程序，处理完后依据保存的返回地址恢复或重新执行。
旁路清单
- 控制器：硬布线控制器与微程序控制器、微指令编码
- 数据通路：寄存器传送语言、ALU 标志位、单总线/多总线结构
- 指令格式：定长/变长、操作码扩展、端序与对齐
- 寻址方式：立即、直接、间接、寄存器、基址变址、相对寻址
- 流水线：结构冒险、数据冒险、控制冒险、分支预测和超标量
- 异常机制：精确异常、现场保护、中断响应与 DMA 协同
3 - 输入输出系统
把总线、设备控制器、CPU、主存和操作系统 I/O 软件串成一条完整路径。
一句话模型
I/O 系统把外部设备的请求转换成 CPU、主存和设备控制器之间的总线事务，再由操作系统通过驱动程序、中断、DMA 和缓冲区把硬件能力包装成进程可使用的文件或设备接口。
三层递进
- 简单：认识总线、CPU、主存、设备控制器和外设的连接关系。
- 中等：追踪一次设备读请求如何经过端口、总线和内存完成数据传输。
- 复杂：加入程序查询、中断、DMA、缓冲、驱动和系统调用，区分组成原理与操作系统各自负责的部分。
简单图谱：总线与 I/O 硬件
总线是部件之间的共享通信通道，通常包含数据、地址和控制信号；I/O 接口或设备控制器位于总线与外设之间，负责速度匹配、状态保存和协议转换。
# 输入输出系统
## 总线
- 数据总线：传输数据
- 地址总线：选择主存或 I/O 端口
- 控制总线：读写、时钟、中断、复位
- 总线事务：申请、寻址、传输、释放
- 同步定时与异步握手
## I/O 硬件
- CPU
- 主存
- I/O 接口 / 设备控制器
- 数据、状态、控制端口
- 外部设备：块设备、字符设备、网络设备
中等图谱：一次设备读请求
主干问题是：CPU 发出“读设备”请求后，数据如何从外设到达主存，并让 CPU 知道操作完成？
以读取磁盘一个数据块为例：
- 进程通过系统调用提出读请求，操作系统驱动程序把请求写入设备控制器的控制端口。
- CPU 或 DMA 控制器通过总线向设备控制器发送地址、读写和控制信号。
- 设备控制器驱动外设读取数据，暂存于数据端口或控制器缓冲区。
- 数据通过程序查询、中断或 DMA 传送到主存缓冲区。
- 操作系统更新设备状态、唤醒等待进程，并把数据返回用户缓冲区。
复杂图谱：组成原理与操作系统的协同
复杂图谱把一次 I/O 拆成三个边界：硬件总线事务、设备控制方式、操作系统软件栈。重点观察数据搬运和控制权在 CPU、DMA、设备控制器之间如何转移。
阅读时沿三条路径追踪：
- 查询路径：CPU 发出命令 → 反复读取状态端口 → 设备就绪后读写数据端口。
- 中断路径：设备就绪 → 控制器发中断 → CPU 保存现场 → 中断处理程序读取状态/数据并唤醒进程。
- DMA 路径：CPU 初始化 DMA 描述信息 → DMA 获得总线控制权 → 设备与主存直接批量传输 → 完成中断通知 OS。
子模块图谱：I/O 控制方式
三种控制方式的共同目标都是完成“设备 ↔ 主存”的数据传输，但 CPU 参与程度不同：查询方式持续占用 CPU，中断方式在设备就绪时打断 CPU，DMA 方式把成块搬运交给 DMA 控制器。
子模块图谱：操作系统 I/O 软件层次
硬件传输完成后，操作系统还要提供设备无关的抽象。用户层 I/O、设备独立软件、驱动程序和中断处理程序依次把文件/设备操作转换成具体控制器动作。
关键问题
总线和 I/O 接口分别解决什么问题？
总线解决部件之间如何共享传输通道，I/O 接口解决主机与具体设备之间的速度、格式、状态和控制差异；设备控制器通常是接口功能的具体硬件载体。
组成原理和操作系统的 I/O 边界在哪里？
组成原理关注端口、总线事务、设备控制器、中断信号和 DMA 传输；操作系统关注系统调用、驱动程序、设备分配、缓冲区、队列和进程唤醒。
为什么 DMA 仍然需要 CPU 和中断？
CPU 负责初始化 DMA 的源地址、目的地址和传输长度，DMA 只负责传输期间的数据搬运；传输结束后仍需通过中断通知操作系统更新状态和唤醒进程。
I/O 中断和异常有什么区别？
外部设备异步发出的请求属于中断，通常在指令边界响应；当前指令执行过程中检测到的非法操作或缺页属于异常，来源和返回点不同。
旁路清单
- 总线：单总线/多总线、集中式/分布式仲裁、突发传送、总线带宽
- I/O 端口：统一编址（MMIO）与独立编址（PMIO）
- 控制方式：轮询开销、中断屏蔽与优先级、DMA 周期窃取
- I/O 软件：设备独立性、驱动程序接口、中断处理、SPOOLing
- 性能机制：缓冲、双缓冲、环形缓冲、DMA 与 Cache 一致性
- 设备类型：块设备、字符设备、网络设备及其访问语义
4 - 进程与同步
从进程/线程并发执行，到同步互斥，再到死锁处理的完整知识主干。
一句话模型
进程拥有资源、线程执行代码；多个执行流共享资源时需要同步和互斥来约束执行顺序，若资源分配形成循环等待，就会进入死锁，需要通过预防、避免或检测解除来处理。
三层递进
- 简单：区分进程、线程、资源和调度状态，建立并发执行的参与者模型。
- 中等：从临界区出发，连接互斥锁、信号量、条件变量和生产者/消费者流程。
- 复杂：把资源分配图、死锁四个必要条件、银行家算法和检测解除策略叠加起来。
简单图谱：进程与线程
进程主要解决“资源归谁所有”，线程主要解决“由谁执行代码”。PCB 保存进程级资源和状态，线程控制块保存各执行流的寄存器、PC、栈和调度状态。
# 进程与同步
## 并发执行主体
- 程序：静态指令和数据
- 进程：程序的一次执行，资源分配基本单位
- 线程：进程内的执行流，调度基本单位
- PCB / TCB：保存管理信息和处理机现场
## 共享状态
- 进程地址空间与打开文件
- 线程共享进程资源
- 临界资源与临界区
## 风险
- 竞态条件：结果依赖执行交错
- 不一致：复合操作被切换打断
- 资源等待：可能导致死锁
中等图谱：同步与互斥
主干问题是：多个执行流同时访问共享资源时，如何保证结果正确，并在需要时建立先后顺序？
一次临界区访问可以这样追踪：线程先执行非临界区；进入临界区前获取锁或执行 P/wait；获得许可后访问共享资源；离开临界区时解锁或执行 V/signal，唤醒等待者。
- 互斥约束“同一时刻最多一个执行流进入临界区”。
- 同步约束“多个执行流之间满足某种先后关系”，例如消费者必须等待缓冲区非空。
- 信号量既能实现互斥锁，也能用计数表示可用资源数量。
- 条件变量通常与互斥锁配合，等待条件不满足时释放锁并阻塞。
复杂图谱：资源等待与死锁
死锁不是普通的阻塞，而是多个进程互相等待、任何一个都无法继续推进的闭环。复杂图把同步原语造成的资源占用，连接到死锁的检测和处理策略。
阅读时沿三条路径追踪：
- 正常路径：申请资源 → 获得资源 → 执行 → 释放资源。
- 死锁形成路径：互斥 + 占有并等待 + 非抢占 + 循环等待同时成立。
- 处理路径：预防破坏必要条件；避免在分配前做安全性检查；检测发现环后解除或回收资源。
子模块图谱：同步原语
同步原语的差异可以归结为“保护什么状态、阻塞在哪里、由谁唤醒”。互斥锁保护临界区，信号量管理许可或资源计数，条件变量等待谓词成立。
子模块图谱：死锁处理
死锁处理策略对应不同的系统取舍：预防限制并发资源申请，避免需要知道最大需求并运行银行家算法，检测解除则允许风险发生后再恢复。
关键问题
进程和线程为什么要分成两个抽象？
进程隔离地址空间和系统资源，线程共享进程资源并承担执行与调度；这样既能保护资源，又能在同一进程内低成本并发。
同步和互斥有什么区别？
互斥是排他访问，回答“谁能进入临界区”；同步是执行顺序约束，回答“谁应该先做、谁需要等待”。一个同步问题可以同时包含互斥和条件等待。
为什么加锁后仍然可能死锁？
锁只保证单个临界区的互斥，不自动保证多个锁的申请顺序。如果线程 A 持有锁 1 等锁 2，线程 B 持有锁 2 等锁 1，就形成循环等待。
银行家算法检查的是什么？
它检查的是“试探性分配后是否仍存在安全序列”，不是判断当前是否已经死锁。安全状态表示存在一个顺序，使所有进程都能获得剩余资源并完成。
旁路清单
- 进程状态：创建、就绪、运行、阻塞、终止与状态转换
- 线程实现：用户级线程、内核级线程和多线程模型
- 同步实现：禁用中断、原子指令、自旋锁、互斥锁、信号量
- 经典问题：生产者/消费者、读者/写者、哲学家进餐
- 死锁模型：资源分配图、可达性、安全序列和安全性检查
- 死锁解除：抢占资源、终止进程、回滚和重新分配
5 - 数制与数据表示
从进位计数制和位模式出发，连接整数、补码、浮点数、类型转换与运算电路。
一句话模型
计算机只保存有限长度的二进制位，数制决定位的权值，数据类型决定如何解释同一串位模式，运算电路负责变换这些位，并通过标志位说明结果是否为零、进位或溢出。
三层递进
- 简单：先建立二、八、十、十六进制之间的表示和转换关系。
- 中等：加入无符号数、补码和 IEEE 754，理解有限位模式如何解释为整数或浮点数。
- 复杂：叠加加减运算、位宽转换、溢出、舍入和状态标志，追踪“数值 → 编码 → 运算 → 解释”的完整流程。
简单图谱：数制与位模式
数制的核心是“每一位的权值”。二进制适合硬件存储，八进制和十六进制可以按三位、四位二进制直接分组，十进制则需要通过按权展开、除基取余或乘基取整进行转换。
# 数制与数据表示
## 进位计数制
- 基数：每一位可使用的数字个数
- 位权：第 i 位的权值为基数的 i 次幂
- 二进制、八进制、十进制、十六进制
- 整数：除基取余
- 小数：乘基取整
## 二进制位模式的解释
- 无符号整数：所有位表示数值
- 补码整数：最高位权值为负
- 浮点数：符号、阶码、尾数
- BCD：每四位表示一个十进制数字
中等图谱：同一位模式的不同解释
主干问题是：内存中的一串 0 和 1 为什么可以表示完全不同的数值？
以 8 位位模式 1111 1111 为例：
- 按无符号整数解释，它是 (255)。
- 按补码有符号整数解释，它是 (-1)。
- 按两个 BCD 数字解释，它不是合法的 8421 BCD 编码，因为每组
1111都超过十进制数字 9。 - 位模式本身没有类型，类型决定各位的权值和合法编码范围。
复杂图谱：从数值到运算结果
复杂图把表示与运算连接起来：输入数值先编码为固定位宽，运算电路处理位模式，再由类型规则和标志位解释结果。整数关注截断与溢出，浮点数还要处理对阶、规格化和舍入。
阅读时沿三条路径追踪：
- 整数路径：选择位宽和有无符号 → 编码 → 加减/移位 → 检查 CF、OF、ZF、SF。
- 浮点路径：十进制实数转二进制 → 规格化 → 编码
s/exp/frac→ 对阶运算 → 规格化和舍入。 - 类型转换路径：保持位模式重新解释，或改变位宽/类型后进行符号扩展、零扩展、截断和舍入。
子模块图谱：整数与补码
补码把减法转换成加法，使同一套加法器既能处理无符号数，也能处理有符号数。区别不在加法器，而在结果如何解释以及查看 CF 还是 OF。
整数子图的阅读顺序是：确定位宽 → 选择有符号/无符号解释 → 正数直接编码、负数取反加一 → 加法器运算 → 根据类型判断进位或溢出。
子模块图谱：IEEE 754 浮点数
IEEE 754 用符号位、偏置阶码和尾数表示范围很大的实数，同时保留 ±0、非正规数、±∞ 和 NaN 等特殊编码。
浮点子图的阅读顺序是：判断符号 → 把二进制实数规格化 → 阶码加 Bias → 保存小数部分 → 根据 exp/frac 区分正常值、非正规数和特殊值。
关键问题
位模式和数值为什么不能混为一谈？
位模式只是存储的二进制序列；无符号、补码、浮点或 BCD 等解释规则为每一位赋予不同含义。同一位模式在不同类型下可以对应不同数值。
补码为什么能统一加法和减法？
在固定位宽下，补码运算等价于模 (2^n) 运算，减去 (B) 可以转化为加上 ~B + 1，超出位宽的最高进位直接舍弃。
CF 和 OF 有什么区别？
CF 描述无符号运算是否产生最高位进位或借位，OF 描述补码有符号结果是否超出表示范围。同一加法结果可能 CF 与 OF 不同。
为什么浮点数会有误差？
许多十进制小数在二进制中无限循环，而尾数位数有限，只能舍入为邻近的可表示值；浮点加减还可能因对阶丢失低位精度。
旁路清单
- 数制转换：按权展开、除基取余、乘基取整、二进制分组
- 整数编码：原码、反码、补码、移码和 BCD
- 位宽变化：零扩展、符号扩展、高位截断
- 整数运算：加减、逻辑移位、算术移位、乘除
- 标志位：ZF、SF、CF、OF 的计算和使用边界
- 浮点表示：Bias、隐藏位、正常值、非正规数、无穷和 NaN
- 浮点运算：对阶、尾数运算、规格化、舍入和溢出
- 类型转换：有符号/无符号、整数/浮点、宽类型/窄类型
6 - 计算机网络层次
从分层模型和协议边界出发，追踪数据封装、路由转发和端到端交付。
一句话模型
计算机网络把通信问题拆成层次：应用产生数据，传输层负责进程到进程，网络层负责跨网络寻址与路由，数据链路层负责相邻结点传输，物理层负责比特信号；发送端逐层封装，接收端逆序解封装。
三层递进
- 简单：认识 OSI 七层、TCP/IP 四层和常用协议的归属。
- 中等：追踪应用数据从进程到网卡的封装，以及接收端的解封装。
- 复杂：加入 DNS、TCP、IP、ARP、以太网交换和路由转发，完整解释一次访问如何跨越多个网络。
简单图谱：网络分层
分层的价值是隔离变化：上层只使用下层提供的服务，通过接口和协议完成协作。OSI 更细致地划分会话、表示和应用功能，TCP/IP 将其合并为应用层。
# 计算机网络
## OSI 七层
- 应用层：面向用户的网络应用
- 表示层：编码、压缩、加密
- 会话层：会话建立、管理和恢复
- 传输层：进程到进程的端到端传输
- 网络层：主机寻址和路由选择
- 数据链路层：帧、MAC、差错与介质访问
- 物理层：比特、信号和传输介质
## TCP/IP 四层
- 应用层：HTTP、DNS、FTP、SMTP
- 传输层：TCP、UDP
- 网际层：IP、ICMP、路由协议
- 网络接口层：以太网、ARP、物理介质
中等图谱：数据封装与解封装
主干问题是：应用层的一段数据如何变成链路上的比特，又如何在接收端还原为应用数据？
发送端每经过一层就增加本层首部：传输层形成 TCP 报文段或 UDP 数据报，网络层形成 IP 分组，数据链路层形成帧，物理层发送比特。接收端按相反顺序检查首部、去除首部并交付上层。
| 层次 | 典型 PDU | 关键标识 |
|---|---|---|
| 应用层 | 数据 | URL、域名、应用语义 |
| 传输层 | 报文段/用户数据报 | 端口号、序号、确认号 |
| 网络层 | IP 分组 | 源/目的 IP、TTL |
| 数据链路层 | 帧 | 源/目的 MAC、FCS |
| 物理层 | 比特 | 电/光/无线信号 |
复杂图谱：一次端到端访问
复杂图在封装流程上叠加名称解析、邻居发现、交换、路由和可靠传输，展示访问远端 Web 服务时不同协议的职责边界。
阅读时沿三条路径追踪：
- 应用路径：浏览器 → DNS 解析域名 → HTTP/HTTPS 生成请求。
- 端到端路径：TCP 建立连接、分配端口、序号确认和拥塞控制。
- 逐跳路径：IP 查路由表决定下一跳，ARP 获取邻居 MAC，交换机按 MAC 转发，路由器逐跳重封装链路帧。
子模块图谱：协议分层与寻址
不同层使用不同的寻址对象：应用层使用域名或资源名，传输层使用端口，网络层使用 IP，数据链路层使用 MAC。地址解析把高层标识逐步落实到下一跳可达的链路地址。
子模块图谱：封装与解封装
封装是“向下逐层加首部”，解封装是“向上逐层检查并剥离首部”。中间路由器通常只处理网络层及以下信息，不会把 IP 分组解封装到应用层。
关键问题
为什么网络要分层？
分层把复杂通信拆成可组合的功能，每层通过服务接口为上层提供能力。某一层内部协议变化时，只要接口保持稳定，上层不必全部修改。
端到端和逐跳有什么区别？
传输层的可靠性、流量控制和拥塞控制是源主机进程到目的主机进程的端到端问题；数据链路层帧传输和 MAC 转发只负责相邻结点之间的一跳。
IP 地址和 MAC 地址为什么都需要？
IP 用于跨网络定位最终主机并支持路由选择，MAC 用于当前链路上的帧交付。数据经过路由器时，IP 通常保持端到端语义，而每一跳的链路首部会重新封装。
为什么路由器不负责 TCP 可靠传输？
路由器主要处理网络层转发，依据目的 IP 和路由表选择下一跳；TCP 的序号、确认、重传和拥塞控制属于端系统之间的传输层职责。
旁路清单
- 物理层：奈奎斯特/香农、编码调制、交换方式和传输介质
- 数据链路层：组帧、CRC、滑动窗口、CSMA/CD、以太网交换
- 网络层：IPv4/IPv6、子网划分、CIDR、NAT、路由算法、ICMP
- 传输层：TCP 三次握手/四次挥手、可靠传输、流量控制、拥塞控制、UDP
- 应用层：DNS、HTTP、FTP、邮件、DHCP 及其端口和下层依赖
- 横向概念：PDU、协议三要素、服务与接口、MTU 与分片
7 - 程序执行与内存
用递归和动态数据结构串起算法、函数调用、CPU、进程地址空间与虚拟存储。
一句话模型
递归在算法层把一个问题不断拆成规模更小的同类问题。程序运行时，每次递归调用都会创建一个栈帧，用来保存这一层调用的参数、局部变量和返回位置。若递归过程中通过 malloc 创建链表或树的结点，这些对象会保存在堆中；程序使用指针访问结点时，虚拟地址经过页表翻译，最终访问 Cache 或主存中的数据。
三层递进
- 简单：只看一次递归调用如何创建栈帧，并在递归返回时销毁栈帧。
- 中等：加入动态创建的树结点，区分“栈上的执行现场”和“堆上的长期对象”。
- 复杂：从 C 源码出发，经过编译器、指令、CPU、虚拟地址翻译、Cache 和主存，解释一次函数调用和指针访问如何真正执行。
简单图谱：递归与函数调用栈
递归并不是 CPU 的特殊功能。递归函数会被编译为普通的函数调用，每次调用建立一个新的栈帧；到达终止条件后，再按照后进先出的顺序逐层返回。
# 递归执行
## 算法层
- 定义子问题
- 设置递归终止条件
- 递归调用
- 合并子问题结果
## 运行时层
- CALL 保存返回位置并转移控制流
- 建立 callee 栈帧
- 保存参数、局部变量和寄存器
- RET 恢复 caller 并继续执行
## 复杂度
- 同时存在的栈帧数量等于递归深度
- 每层栈帧空间乘以最大深度得到调用栈空间
- 递归过深可能发生栈溢出
基础知识页面：算法复杂度、函数定义和调用、函数调用时内存结构。
中等图谱：栈帧与堆对象同时存在
主干问题是：递归创建一棵树时，哪些数据随着函数返回而消失，哪些数据在返回后仍然存在？
先把递归调用和 malloc 放回完整的进程虚拟地址空间：递归调用使用栈区保存执行现场，malloc 从堆区或内存映射区域取得动态对象空间。
图中最重要的关系是：栈帧中的 node 是一个指针变量，而它指向的 TreeNode 才是堆对象。两者位于不同的内存区域，也具有不同的生命周期。
再放大递归构造二叉树的过程，观察多个栈帧如何创建堆中的多个结点：
可以用下面的简化代码理解：
TreeNode *build(int depth) {
if (depth == 0) return NULL;
TreeNode *node = malloc(sizeof(TreeNode));
node->left = build(depth - 1);
node->right = build(depth - 1);
return node;
}
depth、node这个指针变量和返回地址属于当前调用的栈帧。malloc创建的TreeNode对象位于堆中，栈帧只保存指向它的指针。- 递归返回会销毁当前栈帧，但不会自动释放堆中的树结点。
- 最外层调用者仍可通过根指针访问整棵树；不再使用时需要遍历并
free每个结点。
复杂图谱：从源码到物理内存
复杂图把算法、指令、进程地址空间和存储系统叠加起来。一条 C 语句并不会直接操作“树”，CPU 最终执行的是调用、算术、加载和存储指令。
阅读时沿三条路径追踪：
- 控制流路径：递归源码 → 编译器生成
CALL/RET→ PC 改变 → SP/BP 建立或销毁栈帧。 - 数据生命周期路径：
malloc→ 用户态堆分配器 → 堆或内存映射区 → 树结点 →free回收。 - 实际访存路径：虚拟地址 → TLB/页表 → 物理地址 → Cache → 主存；页面尚未驻留时触发缺页。
子模块图谱：动态数据生命周期
malloc 不是“每调用一次就向操作系统申请一个物理页”。它通常先从用户态分配器已经管理的堆块中分配；空间不足时才通过 brk 或 mmap 等机制扩展虚拟地址空间，页面也可能在第一次访问时才真正获得物理页框。
动态对象的完整生命周期是：提出大小需求 → 分配器查找并切分空闲块 → 必要时向操作系统扩展虚拟空间 → 首次访问触发按需分配 → 指针连接成链表/树/图 → 删除结构时逐个 free → 合并空闲块 → 条件允许时归还部分页面。
子模块图谱：三个容易混淆的“栈”
- 栈 ADT 是后进先出的逻辑结构，可以用数组或链表实现。
- 函数调用栈 是进程虚拟地址空间中的运行时区域，由编译器约定和 CPU 指令共同使用。
- 递归调用 是一种程序控制结构，通常借助函数调用栈保存每层执行现场。
关键问题
递归为什么会消耗额外空间？
每个尚未返回的调用都要保留参数、局部变量、返回地址和部分寄存器。最大递归深度决定同时存在的栈帧数量，而不是递归调用的总次数。
栈上的指针和堆上的对象是什么关系？
指针变量可以位于栈帧，但它保存的虚拟地址可以指向堆对象。栈帧销毁只会让指针变量失效，不会自动释放它指向的堆内存。
为什么 malloc 成功不代表物理内存已经准备好？
分配器可能只返回一段可用虚拟地址。进程第一次读写对应页面时，页表项尚未建立或页面尚未驻留，操作系统才通过缺页处理分配物理页框。
递归、栈溢出和内存泄漏有什么区别？
递归过深可能耗尽有限的调用栈；内存泄漏是堆对象失去可达指针却没有被释放。前者与调用深度有关，后者与动态对象生命周期管理有关。
旁路清单
- 数据结构：树/图递归遍历、链式存储、递归空间复杂度
- 指令系统：
CALL、RET、PUSH、POP、栈寻址和调用约定 - CPU：PC、SP、BP、通用寄存器、加载/存储指令
- 进程内存：代码区、数据区、堆、栈和内存映射区域
- 动态分配：空闲链表、块切分、相邻合并、碎片和伙伴算法
- 虚拟存储：页表、TLB、缺页、页框分配和页面置换
- 存储层次：Cache 命中/未命中、主存访问和局部性