Lecture 10：知识 - 文件系统

文件系统在外存保存引导、超级块、目录、索引节点和数据块；在内存维护缓存、挂载与打开文件状态。408 的核心是把“路径 - 目录项 - FCB/inode - 物理块”的访问链，以及不同文件系统的索引方法说清楚。

本讲沿用原题的 KB/MB/GB 写法进行容量计算，数值按 $1024$ 进位；若严格区分单位，相关 KB/MB/GB 应读作 KiB/MiB/GiB。

10.1 文件系统层次结构

原图由五个主处理层和两个底层支撑模块组成；文件访问的典型转换链是：系统调用/路径名 → FCB 或 inode → 逻辑块号 → 物理块号 → 设备操作。

10.2 文件系统的全局结构

外存结构与启动

1. MBR（主引导记录，Master Boot Record） 在本讲的传统 BIOS/MBR 启动模型中位于磁盘 0 号扇区，含磁盘引导程序和分区表。启动时 BIOS 读入并执行 MBR；MBR 根据分区表找到活动分区，并读入该分区的第一块——引导块。UEFI/GPT 机器的启动路径不同，不能把这条链当作所有计算机的通则。
2. 引导块（boot block） 内含启动该分区操作系统的程序。每个分区都从引导块开始，即使该分区暂时不可启动；Windows 中常称为分区引导扇区。
3. 超级块（super block） 保存文件系统的关键控制信息，如分区块数、块大小、空闲块数及其指针、空闲 FCB/inode 数及其指针。系统启动或首次使用该文件系统时，超级块会被调入内存。
4. 索引区（inode 区/FCB 区） 存放许多 inode 或 FCB；可据 inode 号快速定位对应索引节点。
5. 根目录和数据区 保存目录项与文件内容。文件系统须能按约定找到根目录入口（例如固定的根 inode 号）；根目录的数据块本身不必固定在某一物理位置。

磁盘 0 号扇区：MBR（引导程序 + 分区表）
活动分区：引导块 → 超级块 → inode/FCB 区 → 根目录/数据区

文件系统的建立

逻辑卷可以由一个物理磁盘的一部分构成；支持超大文件的系统也可能把多个物理磁盘组织为一个文件卷。目录区主要存储目录/FCB（或 inode）及空闲空间管理信息，文件区主要保存文件数据。

内存中的文件系统结构与 open

内存中的文件系统信息既用于管理，也通过缓存提升性能。

open 一个文件的典型过程：

1. 按路径打开并查找目录，把相关目录读入内存/目录缓存，找到目标文件的 FCB 或 inode。
2. 取得或复用内存中的 inode/vnode 等文件对象，并为本次独立 open 建立打开文件描述；dup/fork 等操作才会让多个 fd 共享既有打开描述及其偏移。
3. 在调用进程的打开文件表中新建条目，返回该条目的文件描述符 fd，并令其指向系统表项。
4. 以后执行 read(fd)、write(fd) 时，先用 fd 查进程表，再到系统打开文件表取得文件控制信息，最后定位数据块。

10.3 外存空闲空间管理

位图法

设一个字有 $n$ 位，块号和位图位置均从 0 开始，$(i,j)$ 表示第 $i$ 个字的第 $j$ 位，则：

$$b=ni+j$$

$$i=\lfloor b/n\rfloor,\qquad j=b\bmod n$$

本讲图例采用“0 表示空闲、1 表示已分配”；考试必须先确认题目约定、块号起点、字号/行号起点和字长。

分配 $K$ 块：顺序扫描位图，找到 $K$ 个相邻（连续分配）或不相邻（离散分配）的 0，按公式换算块号后将位改为 1。回收时按块号反算 $(i,j)$，再把相应位置 0。

成组链接法

空闲表和空闲链表在大型文件系统中可能过大。成组链接法把空闲块按组保存；文件卷目录区专门用一个磁盘块作为超级块。超级块在启动时读入内存，内外存中的对应内容必须保持一致。

• 超级块相当于当前空闲块组的链头，保存下一组的空闲块数和空闲块号集合。
• 若规定每组最多 100 个空闲块，当前组已满又回收一块，则把原超级块的分组信息复制到新回收块中，再修改超级块，使该新块成为下一组的入口。

2024 选择题辨析

若问“空闲块数量变化而额外管理空间不变”的方法，应选位图法：空闲表、空闲链表、成组链接法的管理空间会随空闲块增多而增大；位图的位数只由磁盘总块数决定。

10.4 虚拟文件系统（VFS）

不同设备可使用 UFS、NTFS、FAT 等不同具体文件系统，它们的内部格式与操作函数并不相同。VFS 向用户进程提供统一的 POSIX 风格接口，如 open(x,y,z)、read、write、close，并把请求分派到具体文件系统，从而屏蔽底层差异。

一个新文件系统要挂入某 OS，必须实现 VFS 规定的操作（例如 open/read/write）。VFS 的四类对象如下。

vnode：统一不同文件系统的文件表示

不同文件系统的文件控制结构并不一致。一些 UNIX/VFS 实现使用主存中的 vnode 统一表示文件，保存或关联文件属性，并通过操作函数指针调用具体文件系统的实现；读 FAT 文件便可分派到 FAT 的读操作。同一文件的内存对象可被复用，不是每次 open 都必须新建一个 vnode。Linux VFS 的内存 inode、dentry、file 等对象承担相应角色，不必与这里的 vnode 教学模型逐项等同。

• vnode 只存在于主存。
• 磁盘上的 inode（以及被调入内存的 inode 副本）属于具体文件系统；不要把 vnode 与 inode 混为同一持久结构。

10.5 UNIX 文件系统：结构与路径查找

基本布局

在本讲简化模型中，磁盘块大小为 4 KB，目录结构中方形为目录文件、圆形为普通文件。典型布局为：引导块、超级块、位图、inode 区和数据区。

目录项和目录文件

UNIX 目录项只需保存文件名与 inode 号，文件类型、权限、大小、数据块位置等属性存于 inode。每个目录默认含：

• .：当前目录；
• ..：上一级目录。

根目录特殊，没有真正的上一级目录，故其 .. 指向自身。目录文件所需块数可按下式估算（整除时向上取整）：

$$\left\lceil\frac{\text{目录项数}\times\text{每项大小}}{\text{块大小}}\right\rceil$$

访问 /A/Dm 的过程

设根目录常驻内存，目录 A 对应 1 号 inode，A 的数据块为 6、7，普通文件 Dm 的数据块为 $m,k$：

1. 在内存根目录中查目录项 A，得到 A 的 inode 号 1。
2. 从磁盘 inode 区读入 1 号 inode，得到 A 的索引信息。
3. 按 A 的索引读入 A 的第一块（6 号物理块）；若未找到 Dm，再读第二块（7 号物理块）。
4. 找到 Dm 的目录项后，取其中的 inode 号并从磁盘读入对应 inode。
5. 根据 Dm 的 inode，读入 Dm 的数据块 $m$、$k$。

路径名查找中，“目录项给 inode 号，inode 给数据块号”是关键两跳。

2022 真题：UNIX inode 与硬链接

题设：块大小 4 KB；目录项含文件名和 inode 号；每个 inode 占 256 B、含 10 个直接地址项及一级、二级、三级间接地址项各一个；根目录下有 stu、course、doc，course 下有 course1、course2。图中 doc 与 course1 的 inode 均为 10，course1 数据块为 30，course2 为 6 MB。

10.6 FAT 文件系统：结构与路径查找

FAT 的基本思想

FAT（文件分配表）为每个磁盘块/簇设置一个表项；目录项记录文件名、类型、大小、起始块号等信息。访问文件时，先从目录项取起始块号，再连续查 FAT 表项，得到后续块号直至文件结束标志。

• 开机时通常把整个 FAT 表调入内存并常驻，因此查 FAT 多为内存访问，无须每次读盘。
• 在本讲简化模型中，根目录置于固定位置并常驻内存；固定位置保证启动时能从根目录出发查找初始化所需文件。
• 一个目录文件可增长为多块，不要求物理连续：若原末块为 7，新分配一块后，只需把 FAT[7] 改为该新块号。

每个 FAT 表项的位数决定可表示的最大块号，从而影响文件系统可管理的最大块数；同时：

$$\text{FAT 总大小}=\text{表项数量}\times\text{单个表项大小}$$

目录文件所需块数同样是：

$$\left\lceil\frac{\text{目录项数}\times\text{每项大小}}{\text{块大小}}\right\rceil$$

访问 /A/Dm 的过程

设根目录常驻内存，A 的首块为 5，FAT 指示 A 后续块依次为 6、7，Dm 的两块为 $m,k$：

1. 在内存根目录查 A，取得其首块号 5。
2. 读入 A 的第 1 块（5 号块），在其中找 Dm；未找到则查内存 FAT，依次读 A 的第 2 块（6 号）和第 3 块（7 号）。
3. 找到 Dm 目录项后得到其首块 $m$；查内存 FAT 得到后继块 $k$，读入 $m,k$ 即得文件内容。

与 UNIX 对比：FAT 不需先读 inode，但文件块链的后继关系在 FAT 中；UNIX 目录项先给 inode，inode 再给索引/数据块。

2016 真题：FAT 访问分析

题设：块大小 4 KB；目录项含文件名及第一个簇号，其余簇号存于 FAT；目录树为 dir/dir1/file1、dir/dir1/file2。目录项中 dir → 1、dir1 → 48、file1 → 100、file2 → 200，且 file1 的 FAT 链为 $100\to106\to108$。

10.7 文件系统的挂载

挂载（安装/装载）是把一个独立文件系统接入现有目录树。其实现要点：

1. 在挂载表注册：在 VFS 的内存挂载表中登记新文件系统的类型、容量等信息。
2. 提供操作函数地址：新文件系统向 VFS 提供 read、write 等函数地址/操作表。
3. 接到挂载点：选择父目录树中的一个目录作为 mount point，新文件系统从此处成为统一目录树的一部分。

10.8 Linux/Ext2 的磁盘数据结构

Linux 早期文件系统的发展脉络可概括为先使用 MINIX filesystem，后开发 Extended filesystem、Ext2；Ext3 在 Ext2 基础上增加日志，现代 Linux 常用 Ext4。块大小与 inode 数量均需结合负载选择：块太大浪费内部碎片，块太小增加管理和寻址开销；inode 数量限制可创建文件数。

本讲的 Ext2 简化布局从 Boot Block 开始，其后划分为顺序排列、大小相同的多个 Block Group，内核可按组号（index）定位某一组。原图列出的组内结构如下；前两项是否在某一组保留副本，取决于修订版和文件系统特性：

1. 超级块（或其副本）；
2. 组描述符表（或其副本）；
3. 数据块位图；
4. inode 位图；
5. inode 表；
6. 若干数据块。

这样分组有利于把同一文件的数据尽量放在同一 Block Group，减少文件碎片。原 PDF 说每组都有超级块和组描述符副本，适用于早期 Ext2 revision 0；启用 sparse_super 的版本只在第 0、1 组及组号为 3、5、7 的幂的组中保存备份，不能一概说“每组都有”。正常使用 Block Group 0 中的主副本，发生错误时可由 e2fsck 使用现存备份恢复；见 Linux 内核 Ext2 文档。

Block Group 数量由分区大小、块大小及位图容量共同约束。例：32 GB Ext2 分区、块大小 4 KB；每个 4 KB 数据块位图有 $32\text{ Kbit}$，可表示本组最多 32K 个组内块（包含占用块号的元数据块，而非 32K 个可存文件内容的数据块），即每组覆盖至多约 $32\text{K}\times4\text{ KB}=128\text{ MB}$ 的地址空间，实际可用数据容量更小。按这一简化上限估算，约需：

$$32\text{ GB}/128\text{ MB}=256\text{ 个 Block Group}$$

10.9 图示复核

• 外存图明确了启动链：BIOS → MBR → 活动分区引导块 → 操作系统；并区分了引导块、超级块、inode/FCB 区、根目录和数据区。
• 内存图明确了“进程打开文件表 → 系统打开文件表 → FCB/inode/数据块”的两级打开文件表关系。
• UNIX 图明确了位图一位对应一块、目录项仅保存文件名与 inode 号、inode 的 10 直接 + 三级间接混合索引，以及根目录中 ./.. 的含义。
• FAT 图明确了目录项给首块、FAT 表项给后继块；因此目录/普通文件均可由非连续块组成。
• VFS 图明确了用户进程经统一 POSIX 接口调用 VFS，再分派至 UFS、NTFS、FAT 等具体文件系统；Ext2 图明确了 Boot Block 后按 Block Group 组织的元数据与数据块。

相关知识

• 科目导航：操作系统导航
• 阅读顺序：上一篇：目录 · 下一篇：I/O 管理概述
• 关联专题：磁盘与存储器

10.10 本节复盘

• 路径解析主线：目录项给 inode 号（UNIX）或起始块号（FAT）；inode 或 FAT 再给出数据块位置。
• 区分外存持久结构和内存运行时结构；系统/进程打开文件表的“全局共享 + 进程私有”关系是高频考点。
• 位图题先确认位值含义、编号起点、字长以及是否要求连续块；容量题要同时计算位图/FAT/inode 表能表示的数量。
• 硬链接的本质是多个目录项指向同一 inode；删除一个目录项不必然删除文件数据。
• 挂载把独立文件系统纳入统一目录树，VFS 用统一对象与操作表屏蔽文件系统实现差异。