《Operating Systems: Three Easy Pieces》选读精读：虚拟化·并发·持久性三大主题核心章 未开始

题记与说明

• 日期：2026-11-05
• 形式：主题研究（先检索并确认官方免费单章 PDF 可用，逐章下载全文精读 7 章，另做外部评价检索作为旁证）
• 本次阅读的来源（全部为在线精读原文，单章 PDF 均标注 [VERSION 1.10]，版权 2008–25/26）：
  1. OSTEP 官方站点（章节目录 + 免费单章 PDF 入口）；主站 ostep.org。注意：页面上的 book-electronic.html（整书电子版）现已跳转 Gumroad 付费，但单章 PDF 仍可直接免费下载（本次逐章实测 HTTP 200）
  2. Ch 4 · The Abstraction: The Process（cpu-intro.pdf，12 页，全读）——虚拟化·CPU 之抽象层
  3. Ch 6 · Mechanism: Limited Direct Execution（cpu-mechanisms.pdf，16 页，全读）——虚拟化·CPU 之机制层
  4. Ch 18 · Paging: Introduction（vm-paging.pdf，15 页，全读）——虚拟化·内存之核心
  5. Ch 26 · Concurrency: An Introduction（threads-intro.pdf，16 页，全读）——并发之问题定义
  6. Ch 28 · Locks（threads-locks.pdf，22 页，全读）——并发之机制构建
  7. Ch 41 · Locality and The Fast File System (FFS)（file-ffs.pdf，14 页，全读）——持久性之"磁盘感知"布局（本版本编号为 41，纸质版不同印次可能标 40）
  8. Ch 42 · Crash Consistency: FSCK and Journaling（file-journaling.pdf，21 页，全读）——持久性之崩溃一致性
  9. 外部评价旁证（用于"局限"维度）：r/compsci 讨论帖、r/osdev 讨论帖——共识：OSTEP 比 Tanenbaum 更现代、章节短、概念深度好，但广度（网络/分布式/安全案例）不及 Tanenbaum
• 选章逻辑：三大主题各挑"问题定义章 + 机制核心章"。虚拟化 = 进程抽象（Ch4）→ 受限直接执行（Ch6）→ 分页（Ch18）；并发 = 竞态问题（Ch26）→ 锁的构建（Ch28）；持久性 = 磁盘感知布局（FFS，Ch41）→ 崩溃一致性（Ch42）。未读章节（调度策略 Ch7–10、TLB/多级页表 Ch19–20、条件变量/信号量 Ch30–31、I/O 与 RAID Ch36–37、VSFS Ch39、LFS Ch43 等）不在本笔记范围内。

0. TL;DR

OSTEP 把操作系统拆成三个"容易的片段"（书名戏仿 Feynman《物理学讲义》）：虚拟化（把少量物理 CPU/内存变成每个进程独享的无限资源）、并发（多线程共享地址空间带来的原子性问题）、持久性（断电崩溃下如何更新磁盘数据结构）。精读的 7 章给出一条贯穿全书的分析骨架：抽象 → 机制（mechanism）→ 策略（policy）。CPU 虚拟化 = 进程抽象 + 受限直接执行（用户态/内核态、trap、时钟中断）+ 调度策略；内存虚拟化 = 分页（灵活性 + 空闲管理简单，代价是页表又大又慢）；并发 = 竞态条件 + "硬件原子指令 + OS 睡眠/唤醒"逐级搭建锁的阶梯（关中断 → flag 失败 → test-and-set → CAS/LL-SC/ticket → yield → 队列 park/unpark → futex 两阶段）；持久性 = "把磁盘当磁盘"的 FFS 分组布局 + 日志（write-ahead logging）把崩溃恢复从 O(整个磁盘) 降到 O(日志)。全书方法论最大的特色是每章一个 THE CRUX 问题、机制与策略分离、以及大量可运行模拟器作业。

1. 核心问题

这组材料共同回答的问题是：操作系统的三大资源（CPU、内存、磁盘）各自面临什么根本矛盾，用什么抽象 + 机制 + 策略组合去化解？ 拆成三个子问题：

1. 虚拟化（CPU + 内存）：只有几个物理 CPU、一份物理内存，如何给每个进程"近乎无限"的错觉？核心张力是 Ch6 开篇点明的两个目标——性能（不加过多开销）与控制（OS 必须 retain control，"否则一个进程可以永远占着机器"）；内存侧则是分页如何同时做到灵活、不外部碎片，又不像朴素实现那样"又慢又占内存"。
2. 并发：多个执行流共享同一地址空间时，counter = counter + 1 这种三指令序列为什么会被中断撕碎？需要硬件提供什么最小支持、OS 提供什么支持，才能既互斥、又公平、又高性能？
3. 持久性：断电/崩溃可能发生在任意两次写之间，如何保证磁盘上的元数据自洽？旧文件系统为什么只跑出 2% 磁盘带宽，怎样让文件系统"磁盘感知"？崩溃后恢复为什么 fsck 不可持续，日志凭什么更快？

2. 主要主张

2.1 虚拟化·CPU：抽象（进程）+ 机制（受限直接执行）双支柱

• 进程 = 运行中的程序，其"机器状态"就是地址空间（内存）、寄存器（PC、栈指针等）与 I/O 状态（打开文件）。原文：

"The definition of a process, informally, is quite simple: it is a running program."（Ch4 开篇）

• CPU 虚拟化的illusion来自时分共享：

"THE CRUX OF THE PROBLEM: HOW TO PROVIDE THE ILLUSION OF MANY CPUS? ... The OS creates this illusion by virtualizing the CPU... This basic technique, known as time sharing of the CPU, allows users to run as many concurrent processes as they would like; the potential cost is performance."（Ch4, p.1–2）

• 机制与策略分离是全书反复运用的设计范式（源自 Hydra 论文 [L+75]）：

"The mechanism as providing the answer to a *how* question... The policy provides the answer to a *which* question... Separating the two allows one easily to change policies without having to rethink the mechanism and is thus a form of modularity."（Ch4 TIP 框）

• 受限直接执行（LDE）是让"快"与"受控"兼得的协议：程序直接在 CPU 上跑（快），但硬件提供双模式 + trap + 陷阱表，OS 在开机时用特权指令登记 trap table，之后用户代码只能"按号请求服务"：

"user code cannot specify an exact address to jump to, but rather must request a particular service via number. This level of indirection serves as a form of protection."（Ch6, §6.2）
"without limits on running programs, the OS wouldn't be in control of anything and thus would be 'just a library' -- a very sad state of affairs for an aspiring operating system!"（Ch6, p.2）

• 夺回 CPU 控制权的两级方案：合作式（早期 Macintosh、Xerox Alto，靠系统调用/yield 交还；死循环只能重启）→ 非合作式（时钟中断，[M+63]）：

"a timer device can be programmed to raise an interrupt every so many milliseconds; when the interrupt is raised, the currently running process is halted, and a pre-configured interrupt handler in the OS runs."（Ch6, §6.3）

• 上下文切换 = 两次寄存器保存：中断发生时硬件隐式保存到内核栈；OS 决定切换时，switch() 代码再把内核寄存器显式存入进程结构体 A、从 B 恢复（xv6 swtch 汇编，Ch6 图 6.4）。

2.2 虚拟化·内存：分页用固定大小换掉外部碎片，但引入"又大又慢"两难题

• OS 解空间管理问题只有两招：变长切分（分段→外部碎片）与定长切分（分页）：

"we divide it into fixed-sized units, each of which we call a page. Correspondingly, we view physical memory as an array of fixed-sized slots called page frames."（Ch18 开篇；思想源自 Atlas [KE+62]）

• 分页两大优点：灵活性（不对堆/栈增长方向做假设）与空闲管理简单（free list 上取空闲帧即可，无外部碎片）。
• 但朴素分页的代价被精确量化：32 位地址空间 + 4KB 页 → 20 位 VPN → 每进程页表 2²⁰ × 4B = 4MB；100 个进程仅页表就 400MB：

"we get an immense 4MB of memory needed for each page table! ... this means the OS would need 400MB of memory just for all those address translations!"（Ch18, §18.2）

• 每次访存多一次额外访存（先取 PTE 再取数据）：

"paging requires us to perform one extra memory reference in order to first fetch the translation from the page table. That is a lot of work! Extra memory references are costly, and in this case will likely slow down the process by a factor of two or more."（Ch18, §18.4）

5 行循环数组的内存 trace 里每轮循环 10 次访存（4 次取指 + 1 次显式写 + 5 次页表访问，Ch18 图 18.7）。

• PTE 的位域（valid/present、R/W、U/S、dirty、accessed）是后续交换与页面替换的物质基础；x86 PTE 实例（P/R/W/U/S/PWT/PCD/PAT/G/A/D + PFN，Ch18 图 18.5）。章末结论把问题挑明：页表"too slow + too much memory"，解法留给 TLB（Ch19）与多级页表/大页（Ch20）——本章刻意只立问题不解题。

2.3 并发：竞态是"未受控调度"的必然，锁 = 硬件原子原语 + OS 睡眠支持的渐进搭建

• 线程与进程只差一件事：

"each thread is very much like a separate process, except for one difference: they share the same address space and thus can access the same data."（Ch26 开篇）

上下文切换不换页表；每个线程一个栈（"this ruins our beautiful address space layout"，Ch26 §26 开头图 26.1 讨论）。

• 用线程的两大理由：并行化（多核分活）与重叠 I/O（一个线程阻塞时调度器切别的线程）："Threading enables overlap of I/O with other activities within a single program"；反之"Processes are a more sound choice for logically separate tasks where little sharing of data structures in memory is needed"（Ch26, §26.1）。
• 竞态实验：两线程各对共享 counter 自增 1e7 次，期望 20,000,000，实测跑出 19345221 / 19221041 且每次不同：

"What we have demonstrated here is called a race condition (or, more specifically, a data race): the results depend on the timing of the code's execution."（Ch26, §26.4）

术语（critical section / race condition / indeterminate / mutual exclusion）皆出自 Dijkstra [D65,D68]；"the OS was the first concurrent program"（Ch26, §26.7）解释了为什么在 OS 课讲并发。

• 锁的构建阶梯（Ch28 全章主线，按递进顺序）：
  1. 关中断：单处理器可行，但要求信任应用持有特权指令、多处理器无效、长期关中断丢中断 → "only used in limited contexts"（OS 内部自用）。
  2. 纯 load/store 的 flag 锁：test 与 set 之间可被切换，双线程同入临界区 → 失败。
  3. test-and-set（x86 xchg、SPARC ldstub）→ 第一个正确的自旋锁；但不公平（可饿死）、单 CPU 上持锁者被抢占后其余线程各白转一整个时间片。Peterson/Dekker 纯软件解被点名淘汰："algorithms like the ones above don't work on modern hardware (due to relaxed memory consistency models)"。
  4. compare-and-swap / load-linked + store-conditional / fetch-and-add：CAS "is a more powerful instruction than test-and-set"（为 lock-free 铺路）；ticket 锁保证公平与进展。
  5. 自旋浪费问题（CRUX: HOW TO AVOID SPINNING）→ 引入 OS：yield() 仍不解决饿死与 99 线程轮转；队列 + park()/unpark()（Solaris）让持锁者直接把锁移交下一位（flag 不归零），并处理 wakeup/waiting race（setpark()）。
  6. Linux futex：一个整数同时编码"持有位（bit 31）+ 等待者计数"，无竞争时 fast path 只有两条原子指令；两阶段锁（先自旋一段再睡）"is yet another instance of a hybrid approach"。
• 锁的定义性评价框架（Ch28, §28.4）：互斥、公平（是否饿死）、性能（无竞争/单 CPU 竞争/多 CPU 竞争三场景）——评价任何同步原语的三把尺子。
• 优先反转专栏把问题抬到工程级：Mars Pathfinder 事故 [R97]、macOS OSSpinLock Is Unsafe [M15]；解法：别用自旋锁、优先级继承、或统一优先级。

2.4 持久性：先"把磁盘当磁盘"（FFS），再"把崩溃当常态"（日志）

• FFS 的出发点是一个难堪的实测数字：

"performance started off bad and got worse over time, to the point where the file system was delivering only 2% of overall disk bandwidth!"（Ch41, §41.1，引 McKusick 等 [MJLF84] 的 Berkeley 实测）

病根："the old UNIX file system treated the disk like it was a random-access memory"——数据与 inode 相距遥远、free list 碎片化、512B 块太小。

• FFS 的核心结构：柱面组（现代继任者叫块组，ext2/3/4 即此），每组一套 S（超块副本，为了可靠性）+ ib/db 双位图 + inode 区 + 数据区；放置口诀：

"keep related stuff together (and its corollary, keep unrelated stuff far apart)."（Ch41, §41.4）

目录放"目录少、空闲 inode 多"的组；文件数据与 inode 同组；同目录文件同组。

• 口诀有 trace 佐证：SEER trace 分析显示约 7% 的文件访问是"紧接着重开上一文件"、约 40% 落在同文件或同目录（距离 0–1），另有约 25% 距离为 2（如 proj/src/foo.c ↔ proj/obj/foo.o）——FFS 策略恰好覆盖前者，未覆盖距离 2（Ch41, §41.5）。
• 大文件例外与摊销数学：大文件分块摊到多组，块要够大才能摊薄寻道——40 MB/s 传输、10ms 定位时，50% 峰值带宽需 409.6KB/块，90% 需约 3.6MB，99% 需 39.6MB（Ch41 式 41.1 与图 41.2）；FFS 实际按 inode 结构切：前 12 个直接块随 inode，此后每个间接块组换一个组（4KB 块 + 32 位地址 ≈ 每 4MB 换组，首 48KB 例外）。
• 易用性也是 FFS 的遗产：长文件名、符号链接、原子 rename；作者的点评颇具工程哲学味：

"Making a system usable is often as or more important than its deep technical innovations."（Ch41 TIP 框）

章末一句话总结："treat the disk like it's a disk."

• 崩溃一致性问题的形式化：一次文件追加 = 3 次写（inode I[v2]、数据位图 B[v2]、数据块 Db），任意两次写之间都可能掉电 → 7 种中间态里有垃圾数据（inode 指向未写的块）、空间泄漏（位图标记但无 inode 指向）、元数据不一致三种坏结果：

"THE CRUX: HOW TO UPDATE THE DISK DESPITE CRASHES ... crashes can occur at arbitrary points in time, how do we ensure the file system keeps the on-disk image in a reasonable state?"（Ch42 开篇）

• 方案一 fsck（事后修复）：开机前扫描全盘，按超块 → 空闲块（信 inode 而非位图）→ inode 状态 → 链接数 → 重复块 → 坏指针 → 目录 七阶段修；问题是"too slow"，作者给了个绝妙类比：

"This situation is akin to dropping your keys on the floor in your bedroom, and then commencing a search-the-entire-house-for-keys recovery algorithm, starting in the basement and working your way through every room."（Ch42, §42.2）

• 方案二日志（write-ahead logging，源自 DB，文件系统首例 Cedar [H87]）：先写 TxB | I[v2] B[v2] Db | TxE 到日志（physical logging），TxE 落盘后事务才算提交，再 checkpoint 到最终位置；关键排序约束是"内容写完才能写 TxE"——因为磁盘可能把一次大写内部乱序，若 ?? 占位被当成有效事务回放，垃圾会覆盖关键元数据。完整协议四步：journal write → journal commit → checkpoint → free（循环日志，journal superblock 记录未 checkpoint 事务边界）。
  • 恢复 = redo logging，只重放已提交事务："Journaling reduces recovery time from O(size-of-the-disk-volume) to O(size-of-the-log)"（Ch42, §42.5）。
  • 数据双写的代价 → metadata/ordered journaling：数据不进日志但先于元数据落盘，"write the pointed-to object before the object that points to it"是崩溃一致性的核心规则；ext3 提供 data/ordered/unordered 三模式，NTFS 与 XFS 走 metadata journaling。
  • 工程细节一网打尽：写缓存与 write barrier（"some disk manufacturers... explicitly ignore write-barrier requests"；Kahan 语："the fast almost always beats out the slow, even if the fast is wrong"）；事务校验和省一次旋转等待（[P+05]，被 ext4 吸收，"including the Android handheld platform"）；批量全局事务（约 5 秒超时合并）；块复用难题（Tweedie："It's deleting files. Everything to do with delete is hairy."）与 revoke 记录。
• 方案三谱系：Soft Updates（全序写，难实现）、copy-on-write（ZFS、LFS——"never overwrites files or directories in place"）、backpointer-based consistency（前向指针必须能被反向指回）、optimistic crash consistency（校验和 + 少等待，部分负载提升一个数量级但需要新的盘上接口）。

3. 方法

• 问题驱动的章节模板：每章以一个 THE CRUX 框定根本矛盾，再"抽象 → 机制 → 策略"分层拆解。本次精读 7 章全部遵循此模板（如 Ch18 CRUX "HOW TO VIRTUALIZE MEMORY WITH PAGES"、Ch28 CRUX "HOW TO BUILD A LOCK"、Ch42 CRUX "HOW TO UPDATE THE DISK DESPITE CRASHES"）。
• 失败方案也是教学内容：锁一章按"关中断 → flag 失败 → TAS → CAS/LL-SC/ticket → yield → 队列 → futex/两阶段"的淘汰链推进，每个失败都有具体 interleaving trace（Ch28 图 28.2）或三标准评估（互斥/公平/性能）支撑；崩溃一致性一章同样先穷举 7 种崩溃场景再引出日志。
• 历史锚定：每个机制都挂一个真实系统——分页源自 Atlas [KE+62]、test-and-set 见于 Burroughs B5000（1960s）、日志化文件系统首例 Cedar [H87]、futex 取自 glibc nptl lowlevellock.h 真实代码（Ch28 图 28.10）、xv6 进程结构与 swtch 汇编（Ch4 图 4.5、Ch6 图 6.4）。
• 可运行验证：每章附模拟器作业（process-run.py、paging-linear-translate.py、x86.py、ffs.py、fsck.py）与测量作业（lmbench 测系统调用/上下文切换成本），把理解变成可执行实验。本次为桌面精读，未跑模拟器（见局限）。
• 数据取法：书中数字三类——引用经典论文实测（FFS 2% 带宽 [MJLF84]、lmbench 4μs/6μs [MS96]）、作者组自己的研究（SEER trace 分析、ext4 校验和、optimistic crash consistency）、以及教学用理想化算例（4MB 页表、409.6KB 摊销块）。

4. 数据与证据

充分性评价：证据链是"经典论文实测 + 作者组自己的 trace/系统研究 + 可复算的算例"，对一本教材而言自洽且可核查（每条数字都能追到文末参考文献）；但它是教科书式论证而非系统性实验报告——数字多为单点示例（一个 trace、一个盘参数），不是跨工作负载的系统评测；竞态实验只在作者机器上跑过两个样本。

5. 结论

1. 虚拟化的统一答案是"抽象 + 机制 + 策略"三层解耦：CPU 侧进程抽象靠 LDE（双模式 + trap table + 时钟中断 + 上下文切换）落地，性能与控制缺一不可；内存侧分页用定长切分换来灵活与简单的空闲管理，代价（页表大而慢）正是后续 TLB、多级页表、大页要解决的。
2. 并发的本质是"未受控调度撕碎非原子序列"：正确解 = 硬件最小原子原语（test-and-set/CAS/LL-SC/fetch-and-add）负责互斥正确性 + OS（yield/park/unpark/futex）负责不自旋不饿死；现实锁是"两阶段"混合体。评价锁永远用三把尺：互斥、公平、性能。
3. 持久性的两条主线：性能上"把磁盘当磁盘"（FFS 柱面组/块组 + 相关性放置 + 摊销），正确性上"把崩溃当常态"（write-ahead logging 把恢复降为 O(日志)，ordered metadata journaling 是工业界默认折中）。"先写被指者、后写指人者"是贯穿一切崩溃一致性方案的元规则。
4. 全书真正的元结论是设计范式本身：机制/策略分离、失败方案显式化、每个抽象都付一次可量化的代价。

6. 局限

• 作者自己承认/文中可证的：
  • 硬件假设过时处已自我标注：FFS 的柱面组前提（磁盘暴露几何信息）已被"现代盘只暴露逻辑地址空间"推翻，如今用块组近似（Ch41 §41.3）；parameterized placement 被盘内 track buffer 淘汰（Ch41 §41.7）；Peterson/Dekker 算法在 relaxed memory model 下失效（Ch28 ASIDE）；optimistic crash consistency 需要不同盘上接口才能充分发挥（Ch42 §42.4）。
  • FFS 放置策略"not based on extensive studies of file-system traffic... rather... common sense"，且 SEER 局部性分析显示约 25% 的距离=2 访问模式 FFS 覆盖不了（Ch41 §41.4–41.5）。
  • 崩溃一致性在数据语义层面"remains a work in progress"（Ch42 §42.5，引 [P+14] "All File Systems Are Not Created Equal"）。
• 我基于本次精读推断的（推断处已标"推断"）：
  • 选读覆盖面：只精读了三大主题的 7 章，调度策略（MLFQ/彩票）、TLB/多级页表、条件变量/信号量/死锁、I/O 与 RAID、LFS 等均未读，本笔记不能替代全书（推断，依据本笔记开头的选章逻辑）。
  • 例子偏 32 位 x86 与机械盘时代（4MB 页表算例、10ms 寻道、40MB/s），对 64 位地址空间、NVMe/SSD、ARM/RISC-V 需读者自行换算；未覆盖多核缓存一致性、内存序的现代系统论述（Ch28 只点到 relaxed consistency 一句）、以及网络/分布式（外部评价共识：广度不及 Tanenbaum）。
  • 书中数字是教学算例与历史实测的混合，直接搬去指导现代硬件调优需重新验证（推断，依据 §4 的数据性质分析）。
• 本次精读过程局限：PDF 文本经 pdftotext -layout 提取（每章词数 4.3k–9.3k，全程全读），图表仅以文本残迹呈现，Figure 细节按正文描述理解；模拟器作业（process-run.py 等）未实际运行；单章 PDF 页码为本版次独立编号，与纸质版可能有 ±1 差异。

7. 对我的启发

1. "机制/策略分离"可以直接搬进我的系统设计与工作流工程：how（怎么切、怎么存、怎么重试）与 which（选哪个、给谁、何时触发）分开演进，是所有"可替换策略层"的母型——从调度器到 LLM agent 的工具选择策略皆然。
2. "treat the disk like it's a disk"是一切性能工程的原话：性能问题先问介质特性再谈代码。这条在现代依然成立——vLLM 的 PagedAttention 把 OS 分页思想搬进 KV cache 管理、数据库把 WAL 思想搬进存储，都是同一个"抽象跨层移植"套路；我之前精读的 SQLite WAL（2026-10-31 笔记）正是 Ch42 write-ahead logging 在单文件数据库里的直系后代，两边对"commit 时刻 = 写一条提交记录"的定义完全同构。
3. 受限直接执行 = "fast path + 受控慢路径"模式的原型：futex 的无竞争 fast path、vDSO、用户态运行时 fast path 全是它的变体——先让 99% 的情况零干预跑过去，把控制权问题留给 1% 的 trap。
4. 锁的构建阶梯是绝佳的"从第一性原理推导工程"教学样本：每个失败方案都有具体的 interleaving 证据；这提示我在评审并发代码时，与其背规则，不如随手画 interleaving 表格（Ch28 图 28.2 的做法）。
5. 崩溃一致性的"先写被指者"规则可迁移到任何持久化管道：写 checkpoint/写索引/写元数据的顺序设计，本质都是这条规则；日志"用顺序追加的便宜写，买恢复时只看日志的便宜读"是经典的摊销交易。
6. 读书方法收获：OSTEP 的 CRUX 框 + 失败方案阶梯 + 模拟器作业，值得套用到我读任何系统论文/源码——先找"crux"，再列失败方案，最后跑一个最小模拟验证。

附 A：关键原文引述对照表（章节 → 定位）

附 B：本次运行的实际命令记录

• 网络探测：curl -sI https://pages.cs.wisc.edu/~remzi/OSTEP/ → HTTP 200（Last-Modified: Thu, 19 Feb 2026）。
• 章节可用性探测：对 21 个候选文件名逐一 curl -o /dev/null -w "%{http_code}"，确认 7 个目标章节 PDF 均为 200（file-crash.pdf/fs-crash.pdf 等 404，实际文件名为 file-journaling.pdf）。
• 下载：7 个 PDF 各放入独立空目录（ostep-dl/<章名>/，符合下载隔离要求）。
• 文本提取：pdftotext -layout <章>.pdf <章>.txt 后 iconv -f ISO-8859-1 -t UTF-8 修编码，7 章词数 4,300–9,278，全部通读。
• 外部检索：WebSearch 一次（OSTEP vs Tanenbaum 评价），来源见文件头来源第 9 条。