主题
第六章 文件系统：持久化的抽象
1. 为什么应用不直接读写磁盘块
进入三大主线的最后一条：持久化。内存断电即失，重要数据必须落到磁盘。但磁盘的原始接口极其简陋：它只认识"读第 x 块、写第 y 块"，每块固定 512 字节或 4KB。如果让应用直接面对这个接口，每个程序都要自己回答一堆难题：
- 我的数据放在哪些块上？块号自己记？
- 两个程序都想用第 100 块怎么办？
- 别的用户能不能偷看我的块？
- 断电时写到一半怎么办？
操作系统的回答是再造一层抽象——文件系统。它把"编号的块的海洋"包装成两个友好概念：
- 文件：一段有名字的、长度可变的字节序列。应用只管按名字打开、按偏移读写，数据具体落在哪些块由文件系统记账。
- 目录：把文件组织成树，提供"路径名"这种人类友好的定位方式。目录本质上也是一种文件，内容是"名字 → 文件元数据位置"的对照表。
一句话点透：文件系统之于磁盘，就像页表之于内存——都是把"用户看到的连续逻辑空间"映射到"零散的物理空间"的翻译账本。
2. 文件的逻辑结构与物理结构
先分清两个"结构"：逻辑结构是用户看到的文件内部组织（流式的无结构文件、有格式的记录式文件）；物理结构是文件的字节实际怎样摆到磁盘块上。考试重头戏是物理结构的三种分配方式。
2.1 三种分配方式
连续分配：文件占据磁盘上一段连续的块，账本只需记"起始块 + 长度"。
链接分配：文件的块散落各处，每块尾部存一个指针指向下一块（隐式链接）；或把所有指针集中到一张表里（显式链接，FAT 文件分配表就是这个思路）。
索引分配：为每个文件建一个索引块，把它所有数据块的块号列成清单。想读第 i 块，查索引清单第 i 项即可。
| 对比项 | 连续分配 | 链接分配 | 索引分配 |
|---|---|---|---|
| 顺序访问 | 极快 | 可以，逐块跟指针 | 快 |
| 随机访问 | 极快，起始块加偏移直接算 | 很慢，必须从头顺藤摸瓜 | 快，查索引表直达 |
| 文件增长 | 困难，后面没空位就得整体搬家 | 容易，链上再挂一块 | 容易，索引表加一项 |
| 碎片 | 产生外碎片 | 无外碎片 | 无外碎片 |
| 额外开销 | 几乎没有 | 每块一个指针；显式链接需整张 FAT 常驻内存 | 每个文件一个索引块，小文件也要付这笔账 |
| 可靠性 | 好 | 一个指针坏，后半截全丢 | 索引块坏则全文件丢，通常有备份 |
记忆抓手：连续分配像一排连号座位，链接分配像寻宝游戏每站给下一站地址，索引分配像目录页直接列出所有座位号。
2.2 UNIX 多级索引：inode 的直觉
索引分配有个尴尬：索引块大小固定，大文件的块号清单装不下。UNIX 的 inode（索引节点，每个文件一个，存放文件的所有元数据和索引信息）用分级解决：
设计动机很漂亮：绝大多数文件很小，少数文件很大。小文件只用直接块，零额外开销；文件越大，才逐级动用间接块，支持的容量按"每级乘以每块可存的块号数"指数扩张。这和多级页表是同一个思想——按需展开的树。
顺带一个高频计算题型：块大小 1KB、块号 4 字节，则一个间接块可存 256 个块号；一级间接支持 256KB，二级间接支持 256 × 256KB = 64MB，以此类推。
3. 目录实现与路径解析
目录项的最简形式是"文件名 + inode 号"的二元组。注意 UNIX 设计的一个要点：文件名不存在 inode 里，而存在目录里——这使得多个目录项可以指向同一个 inode（硬链接），一个文件因此可以有多个名字。
解析路径 /home/user/note.txt 的过程是逐级查表：
- 从根目录（inode 号固定，如 2 号）出发，读根目录内容，找到表项
home对应的 inode 号。 - 读 home 的 inode，取其数据块（还是目录内容），找到
user的 inode 号。 - 同法找到
note.txt的 inode 号，读出它的 inode——权限、大小、块号索引全在这里。 - 权限检查通过后，按 inode 的索引找到数据块。
每一级都要"读 inode → 读目录数据 → 匹配名字"，路径越深访盘越多，所以系统都会缓存热门目录项。相对路径则从"当前目录"而非根出发，省去前几级解析。
4. 空闲空间管理
分配块之前得先知道哪些块是空的。两种主流账本：
| 方法 | 思路 | 优点 | 缺点 |
|---|---|---|---|
| 位图 | 每块用 1 个比特：0 空闲 1 占用 | 省空间；找连续空块方便；可整体放内存 | 磁盘很大时位图也不小 |
| 空闲链表 | 空闲块串成链，分配摘头、回收接上 | 实现简单，不占额外空间（链就存在空闲块里） | 找连续区域困难，遍历慢 |
位图小算术常考：磁盘 4GB、块大小 4KB，共 1M 个块，位图需 1M 比特 = 128KB。此外还有成组链接法（UNIX 传统方案，把空闲块号分组登记），考试知道名字即可。
5. 磁盘结构与磁盘调度算法
5.1 一次磁盘访问的时间构成
机械磁盘由盘片、磁道（同心圆）、扇区组成，读写靠磁头臂移动定位。一次访问的时间 = 寻道时间（磁头移到目标磁道，最慢，毫秒级）+ 旋转延迟（等目标扇区转到磁头下）+ 传输时间（真正读数据，最快）。既然寻道最贵，优化 I/O 的核心就是减少磁头移动——这正是磁盘调度算法的使命。
5.2 四种调度算法与手算例题
例题：磁头当前在 53 道，请求队列为 98、183、37、122、14、124、65、67（磁道号范围 0～199）。
FCFS 先来先服务：按请求顺序移动。 路径 53→98→183→37→122→14→124→65→67，移动 = 45+85+146+85+108+110+59+2 = 640 道。公平但磁头来回瞎跑。
SSTF 最短寻道时间优先：每次去离当前位置最近的请求。 路径 53→65→67→37→14→98→122→124→183，移动 = 12+2+30+23+84+24+2+59 = 236 道。大幅减少移动，但边缘请求可能饥饿——中间不断来新请求，磁头一直被"就近"黏住。
SCAN 扫描（电梯算法）：磁头沿一个方向走到头（或走到该方向最远请求），服务沿途请求，然后掉头。设当前向大号方向： 路径 53→65→67→98→122→124→183→（掉头）→37→14，移动 = 130 +（183−14）= 130 + 169 = 299 道。像电梯一样顺路捎人，无饥饿，但刚被扫过的区域要等一个来回。
C-SCAN 循环扫描：只在一个方向服务，到头后直接空车返回起点再来一轮。 路径 53→65→67→98→122→124→183→（到 199 后跳回 0）→14→37。服务方向上的移动 =（199−53）+ 199（回程按惯例记满程）+ 37 = 382 道（若按"直达最远请求后跳回"的简化口径则为 130 + 169 + 37 = 336，考试按题目给定口径算）。C-SCAN 的价值不在移动量小，而在各磁道等待时间更均匀——SCAN 对两端磁道不公平，C-SCAN 拉平了。
| 算法 | 本例移动道数 | 优点 | 缺点 |
|---|---|---|---|
| FCFS | 640 | 绝对公平、实现最简单 | 磁头乱跑，性能最差 |
| SSTF | 236 | 平均寻道最短 | 远端请求饥饿 |
| SCAN | 299 | 无饥饿，性能好 | 两端与刚扫过区域等待偏长 |
| C-SCAN | 略高于 SCAN | 等待时间最均匀 | 回程空跑浪费 |
6. RAID 概念级一览
RAID 用多块磁盘组合出"更快或更稳"的逻辑盘，只需记定位：
| 级别 | 手法 | 一句话定位 |
|---|---|---|
| RAID 0 | 条带化，数据分散多盘并行读写 | 只快不稳，坏一块全完 |
| RAID 1 | 镜像，两盘互为副本 | 只稳不省，容量减半 |
| RAID 5 | 条带 + 奇偶校验分散各盘 | 快稳兼顾，允许坏一块，最常用 |
| RAID 10 | 先镜像再条带 | 性能可靠都要，成本最高 |
7. 文件权限与常见文件系统家族
UNIX 权限模型：每个文件三组权限位——属主、属组、其他人，每组"读 r、写 w、执行 x"三位，常用八进制表示（如 755 = 属主可读写执行，组和他人可读可执行）。目录的 x 位表示"能否进入/穿越该目录"。
| 家族 | 一句话定位 |
|---|---|
| FAT / FAT32 / exFAT | 用文件分配表（显式链接分配）的老将，结构简单、兼容性无敌，U 盘存储卡首选，但无权限管理 |
| NTFS | Windows 主力，支持权限、日志、加密、大文件 |
| ext2 / ext3 / ext4 | Linux 主力家族，基于 inode 索引；ext3 起加入日志，ext4 是当前常见默认 |
"日志"一句话：先把要做的修改记到日志区再真正落盘，崩溃后按日志重放或回滚，避免文件系统半途而废的不一致。
8. 本章要点回顾
| 主题 | 必须记住的结论 |
|---|---|
| 文件系统定位 | 把"编号的块"抽象成"命名的文件 + 目录树"，作用类似内存的页表 |
| 三种分配 | 连续利随机访问但难增长有外碎片；链接易增长但随机访问慢；索引两者兼顾，代价是索引块 |
| FAT | 显式链接分配的代表，链表指针集中成表放内存 |
| inode 多级索引 | 直接块伺候小文件，间接块逐级扩容伺候大文件；文件名在目录里不在 inode 里 |
| 路径解析 | 从根逐级"读 inode、读目录、找名字"，层层查表 |
| 空闲管理 | 位图省空间易找连续区；空闲链表简单但遍历慢 |
| 磁盘时间 | 寻道 > 旋转 > 传输；调度算法都在省寻道 |
| 磁盘调度 | FCFS 公平、SSTF 最短但饥饿、SCAN 电梯无饥饿、C-SCAN 等待均匀 |
| RAID | 0 快、1 稳、5 折中、10 全都要 |
9. 做题提醒
- "链接分配适合随机访问"是错的——随机访问恰恰是它的死穴；随机访问选连续或索引。
- 磁盘调度手算：SSTF 每一步都要重新找离当前位置最近的请求，别按初始距离一次排完序。
- SCAN 掉头位置看题意：有的题走到"最远请求"就掉头，有的要走到磁道边界（0 或最大道号），两种口径结果不同，审题第一。
- 位图大小计算：块数 = 容量 ÷ 块大小，位图字节数 = 块数 ÷ 8，单位换算别掉进 KB 与 Kb 的坑。
- 一个文件可有多个目录项（硬链接）指向同一 inode——"文件名是文件的一部分"在 UNIX 语境下是错的。
- 多级索引计算题：先算一个块能装多少个块号（块大小 ÷ 块号长度），再逐级相乘，别忘了把直接块也计入文件最大长度。