Runguo Li

Runguo Li

M.S. student in Information Science @ UIUC, advised by Prof. Minjia Zhang. Working on ML systems for large-scale models: MoE inference and expert streaming, distributed training and rollout, GPU compiler correctness.

Lecture 19–21: 文件系统（File Systems）

目录 · ← l14 · l16 →

Lecture 19–21: 文件系统（File Systems）

概述

文件系统解决四个问题：磁盘空间管理（文件如何组织在磁盘上）、命名（从文件名找到数据块）、可靠性（崩溃后数据不丢失）、保护（用户间隔离与受控共享）。本讲从”文件是什么”出发，比较三种块组织方案（连续分配、链表、FAT、多级索引），再深入 BSD inode（12 直接 + 间接 + 双重间接）、块缓存与延迟写、空闲空间位图、块大小权衡与磁盘调度——Assign7 就是实现 Unix V6 的多级索引读取。

核心概念与系统机制图解

文件（File）

  • 用户视角：命名的字节集合，持久存储。
  • 内核视角：磁盘块的集合 + 元数据（属性）。
  • 访问模式：
    • 顺序访问：约 90% 的应用（编辑器、编译器）；逐字节处理。
    • 随机访问：按位置访问任意字节（数据库、请求调页的数据集）。
    • 键控/索引访问：按内容查找（数据库实现，通常不是 OS 提供）。
  • 重要统计事实：大多数文件很小（几 KB 内，每文件开销必须低），但磁盘空间与大部分 I/O 由大文件占据（大文件性能必须好）；文件可能不可预测地增长。

inode（Index Node）

  • 定义：每文件一个的元数据结构，保存：文件大小、占用的扇区、访问时间（最后读/写）、保护信息（owner、group、rwx）。文件打开时 inode 驻留内存，平时存储在磁盘上。

块组织方案比较（Lecture 19–20）

1. 连续分配（Contiguous / Extents）（如 IBM OS/360）

inode: {起始扇区, 长度}
┌──┬──┬──┬──┬──┬──┬──┬──┐
│ 文件A(连续) │ 文件B(连续) │
└──┴──┴──┴──┴──┴──┴──┴──┘
优点: 简单、顺序/随机访问都快、顺序 I/O 最少寻道
缺点: 碎片化使大文件可能无法分配; 创建时必须预知大小; 无法扩展(过度分配)

2. 链接分配（Linked Files）（如 TOPS-10、Xerox Alto）

inode → [数据|→] → [数据|→] → [数据|∅]
每块含指向下一块的指针
优点: 可扩展、无碎片、元数据小
缺点: 随机访问需追链(昂贵); 顺序访问也大量寻道

3. FAT（File Allocation Table，MS-DOS）

目录项: A: 6          FAT表(驻内存): 6→4→3→2→end
把"链接"集中到一张表: 每磁盘块一个表项, 存下一块号/结束标记/空闲标记
优点: 顺序访问快(块基本连续时), 随机访问快(表在内存), FAT 兼作空闲表, 块内无指针
缺点: 空闲空间易碎片化; FAT 必须常驻内存
历史: 16位FAT最多32MB; FAT32(1996) 32位+簇(2-32KB), 4KB簇支持1TB
现状: 闪存盘、相机等仍广泛使用

4. 多级索引（Multi-level Indexes，4.3BSD Unix / Unix V6）——Assign7 的主角

inode(14个块指针):
  0..11: 直接块(前12个数据块)          → 读块5: 直接查 inode[5]
  12:    间接块(1024个4字节指针)        → 读块23: 查 inode[12]→间接块→第11项
  13:    双重间接块(指向1024个间接块)    → 读块1040: inode[13]→双重间接→间接块→...
最大文件 ≈ 4GB(加三重间接可达4TB); 间接块按需分配
优点: 简单、无需预声明大小、小文件访问快(直接块)、比FAT省内存
缺点: 大文件随机访问需多读索引块(双重间接"二次故障"); 链表式空闲表局部性差

块缓存（Block Cache）与延迟写

  • 用部分主存保留最近访问的磁盘块（LRU 置换）——inode、间接块等常用块命中缓存，解决大文件慢访问。
  • 同步写（write-through）：立即写盘——安全但慢。
  • 延迟写（delayed writes）：等约 30 秒再写——快、可合并多次小写、临时文件可能根本不用写盘；风险：崩溃丢失最近数据。

空闲空间管理

  • 早期 Unix：空闲块链表——初始有序时局部性好，随后迅速打乱。
  • 位图（free map/bitmap）：每块一比特（1=空闲）；1TB 磁盘 ≈ 2^28 块 ≈ 32MB 位图；分配时找”靠近文件上一块”的空闲块（局部性）。
  • 接近满盘：位图扫描昂贵、局部性差 → 解法：不让磁盘满——把容量”虚报”少 10%（90% 满即拒绝写入）。

块大小权衡

  • 512B 块：I/O 低效（寻道多）、间接块只能装 128 个指针（指针占 1% 空间）。
  • 4KB 块：I/O 高效，但小文件内部碎片严重（可能浪费近一半空间）。
  • 4.3BSD 折中：4KB 大块 + 512B 碎片（fragment）——只有文件最后一块可用碎片；多个文件的碎片可共享一个大块。

磁盘调度（Disk Scheduling）

目标：最小化寻道时间。

FIFO : 按到达顺序执行 —— 简单, 不优化寻道(大量长距离移动)
SPTF : 每次选"定位时间最短"的请求 —— 最小化寻道, 但可能饥饿
SCAN : 电梯算法——磁头单向移动, 途中服务所有请求 —— 单向小寻道
CSCAN: 只朝一个方向服务请求, 到端后快速返回 —— 公平且无回程服务

代码示例与系统调用解说

示例：文件读写与 fsync（Unix 文件 API）

#include <fcntl.h>
#include <unistd.h>
#include <cstdio>
#include <cstring>

int main() {
    int fd = open("notes.txt", O_CREAT | O_WRONLY | O_TRUNC, 0644);
    if (fd < 0) { perror("open"); return 1; }

    const char* msg = "file system lecture\n";
    ssize_t n = write(fd, msg, strlen(msg));      // 写入(可能只进块缓存!)
    if (n < 0) perror("write");

    fsync(fd);                                    // 强制把数据刷到磁盘
    close(fd);

    // 顺序读取
    fd = open("notes.txt", O_RDONLY);
    char buf[256];
    ssize_t r = read(fd, buf, sizeof(buf));
    printf("read %zd bytes: %.*s", r, (int)r, buf);
    close(fd);
    return 0;
}

【代码做了什么？】 创建文件、写入、fsync 刷盘、再顺序读回。

【系统机制透视】

  • write 通常只把数据放进块缓存并返回（延迟写）——崩溃可能丢数据；fsync 强制把脏块写盘（Lecture 23 讲崩溃恢复时会再见到它）。
  • open 背后：内核按路径名逐级查目录（Lecture 22）→ 把 inode 读入内存 → 创建文件描述符（指向”打开文件描述”对象，含当前文件偏移）。read/write 以文件偏移为基础做顺序访问；pread/pwrite 支持随机访问（数据库用）。
  • Assign7 中你将手写从磁盘镜像读出 inode、追间接块、解析目录项的全过程——本讲所有机制都会落地为代码。

关键要点

  1. 文件 = 命名字节集合 + 磁盘块集合 + inode 元数据；访问模式决定结构设计。
  2. 连续分配（简单但有碎片、需预知大小）→ 链表（可扩展但随机访问差）→ FAT（表化链接，随机访问快）→ 多级索引（现代 Unix：直接+间接+双重间接）。
  3. 块缓存 + 延迟写提升性能，但把”耐久性”推迟——fsync 用于关键数据。
  4. 空闲空间位图管理 + “别让磁盘满”策略；4KB 块 + 512B 碎片兼顾 I/O 效率与碎片。
  5. 磁盘调度（FIFO/SPTF/SCAN/CSCAN）用请求排序换寻道时间。

常见陷阱与注意事项

  • 假定 write 已落盘：延迟写 + 崩溃 = 丢数据；关键数据必须 fsync。
  • 假定文件大小固定：文件会增长，设计时考虑块按需分配（间接块）。
  • 小文件也要低开销：为所有文件统一分配大块会浪费空间（内部碎片）。
  • 随机小 I/O 打爆磁盘：顺序 vs 随机延迟差 3–4 个数量级。
  • 空闲位图与 inode 不一致：崩溃恢复问题（Lecture 23 专讲）。

思考题

  1. 问题：为什么多级索引（BSD inode）比 FAT 更省内存，同时又能高效处理小文件？
    • 答案：FAT 表覆盖整个磁盘（1TB → 数十亿表项）必须常驻内存；多级索引只在文件实际使用时分配间接块，inode 只占固定一小块。小文件只用 12 个直接指针，一次访问即得数据。
  2. 问题：读取一个超过 12 块的文件的第 1040 块需要几次磁盘访问（缓存未命中时）？
    • 答案：inode[13]（双重间接）→ 双重间接块 → 间接块 → 数据块，即 4 次访问（其中 3 次是索引块）。这正是”双重间接二次故障”问题，块缓存（常命中索引块）可缓解。
  3. 问题：延迟写为什么能显著减少磁盘 I/O？
    • 答案：多次小写可合并成一次大写（同一块只写一次）、很快被删除的临时文件可能完全不用写盘；代价是崩溃时丢失最近未刷盘的数据——性能与耐久性的经典权衡。