操作系统与并发¶
本页整理操作系统、并发、虚拟内存和指令流水线基础。内容来自本地速记的通用计算机知识补充，具体教材口径待核验。
1. 进程、线程与运行状态¶
进程是资源分配的基本单位，线程是 CPU 调度的基本单位。同一进程内线程共享代码段、数据段和打开的文件等资源，但每个线程拥有独立的栈和程序计数器。
系统调用会引发用户态到内核态的切换，例如文件读写、创建进程、网络通信和内存申请。频繁系统调用可能带来上下文切换开销，实际开销取决于处理器、操作系统和调用路径。
2. 虚拟内存分页与 TLB¶
分页把进程虚拟地址空间划分成固定大小的页，把物理内存划分成同样大小的页框。程序页可以装入不连续的物理页框，页表维护“虚拟页号 → 物理页框号”的映射，并记录存在位、权限位和修改位等状态。分页可消除外部碎片，但最后一页未用满时可能产生内部碎片。
虚拟地址通常拆为“虚拟页号 + 页内偏移量”。页内偏移在转换前后保持不变：
页大小为 4 KB 时，页内偏移需要 12 位，因为 4 KB = 2^12。快表 TLB 是处理器中缓存近期 VPN→PFN 映射的高速小型缓存，不是整个进程或磁盘数据。
地址转换流程：CPU 产生虚拟地址后先查 TLB；命中则直接取得物理页框号；未命中则查内存中的页表；若页表表明页面不在内存，才发生缺页异常，由操作系统从后备存储调入页面，必要时置换页面，再重新执行指令。
TLB 未命中不等于缺页：前者只表示快表没有映射，页面可能仍在内存；后者表示页表也表明页面不在物理内存。页表通常保存在主存，TLB 容量较小但速度更快，利用访问的时间局部性和空间局部性降低地址转换开销。进程切换时是否刷新 TLB 或使用 ASID，取决于处理器机制，待核验。
3. 页面置换¶
请求分页中，页面在访问且不在内存时才调入。缺页且没有空闲页框时需要选择页面换出：
- FIFO：先进先出，可能出现 Belady 异常。
- LRU：淘汰最近最少使用页面。
- OPT：淘汰未来最长时间不会使用的页面，理论最优但实际无法准确预知未来。
- Clock：对 LRU 的近似实现。
页面置换算法与 TLB 项替换策略不是同一个问题。分页的代价包括页表占用内存、地址转换开销、页内内部碎片，以及缺页时磁盘 I/O 的高成本。
4. 死锁¶
死锁的四个必要条件是互斥、请求并保持、不可剥夺、循环等待。处理方式包括：破坏必要条件的死锁预防；使用银行家算法的死锁避免；允许发生后检测并恢复；在特定系统中选择忽略。具体系统是否采用忽略策略待核验。
5. 进程通信与并发¶
常见进程通信方式有管道、消息队列、共享内存、信号量和 Socket。共享内存速度快，但多个执行流同时访问时需要配合锁或信号量解决互斥和同步问题。并发题应区分资源共享、临界区、同步关系和通信方式，不能把线程共享地址空间误认为自动保证数据一致性。
6. 指令流水线¶
指令流水线把一条指令拆成多个阶段并让多条指令的不同阶段重叠执行，经典五段为：取指 IF → 译码 ID → 执行 EX → 访存 MEM → 写回 WB。流水线主要提高整体吞吐率，不一定缩短单条指令经过全部阶段的实际延迟。
流水线冒险¶
| 冒险类型 | 原因 | 例子 | 主要对策 |
|---|---|---|---|
| 结构冒险 | 多条指令争用同一硬件资源 | 取指和访存同时使用同一存储器 | 增加或分离资源，如指令 Cache 与数据 Cache 分开 |
| 数据冒险 | 后一条指令需要前一条尚未写回的结果 | ADD 产生 R1，后续 SUB 立即使用 |
转发/旁路、停顿、调整指令顺序 |
| 控制冒险 | 分支或跳转改变执行流 | 条件结果确定前已取入顺序指令 | 分支预测、尽早计算分支结果 |
RAW（写后读）是按序流水线中最常见的数据冒险。转发是主要解决手段，但 LW 后紧跟使用加载结果时，加载结果通常到 MEM 阶段结束才产生，下一条指令可能来不及使用，常仍需插入一个停顿周期；具体流水线实现待核验。
控制冒险可用静态或动态分支预测、延迟分支等方式处理。预测正确时流水线继续运行，预测错误时清除错误路径指令并从正确目标重新取指。
流水线性能计算¶
设有 k 个阶段，每阶段耗时近似为 t，共有 n 条指令：
- 非流水线时间：
n × k × t。 - 流水线时间：
(k + n - 1) × t。 - 稳态吞吐率约为
1/t条/周期。 - 加速比：
nkt / [(k+n-1)t]，当n很大时接近k，但不会超过阶段数。
5 段流水线执行 10 条、每段 1 周期的指令，非流水线为 50 周期，流水线为 14 周期，加速比约 3.57，而不是 5，因为需要装入和排空流水线。
流水线阶段划分、停顿周期和分支预测代价依 CPU 实现与题设而异，遇到计算题应以题设为准。
考前易错速记¶
分页地址由“虚拟页号 + 页内偏移”组成，页表把虚拟页号映射为物理页框号，偏移保持不变。TLB 未命中只表示快表无映射，不等于缺页；页表发现页面不在内存时才发生缺页异常。页面置换中 FIFO 可能出现 Belady 异常，LRU 淘汰最近最少使用页，OPT 理论最优但需预知未来，Clock 是 LRU 的近似。
进程是资源分配单位，线程是 CPU 调度单位。流水线冒险分为结构、数据和控制冒险；可分别考虑资源分离、转发/停顿及分支预测。k 段流水线执行 n 条指令、每段耗时 t 时，理想耗时约为 (k+n−1)t，性能提升主要体现在吞吐率而非单条指令延迟。
来源：专业课速记/09_考前必背清单.md