4.4 文件系统的结构与空闲空间管理

文件系统在外存和内存中的全局结构（MBR、引导块、超级块、索引结点区）；外存空闲空间管理的空闲表法、空闲链表法、位示图法与成组链接法；文件系统的层次结构、虚拟文件系统 VFS 与文件系统挂载；提高文件访问速度的方法。

文件系统的全局结构

在外存中的结构

一块新磁盘要经过三步才能存放文件：

1. 物理格式化（低级格式化）：把磁盘划分成扇区，检测坏扇区并用备用扇区替换；
2. 分区：把磁盘划分为一个或多个分区（卷），每个分区可以安装一个独立的文件系统；
3. 逻辑格式化（高级格式化）：在分区中建立文件系统，写入超级块、空闲空间管理结构、索引结点区、根目录等初始数据。

• 主引导记录（MBR）：位于磁盘的 0 号扇区，用来引导计算机；MBR 的后面是分区表，给出每个分区的起始和结束地址。计算机启动时，BIOS 读入并执行 MBR，MBR 找到活动分区，读入它的引导块。
• 引导块：每个分区的第一块，含有启动该分区中操作系统所需的信息（若分区中没有操作系统，则可以为空）。
• 超级块：包含文件系统的所有关键信息，如分区的块数、块的大小、空闲块的数量和指针、空闲 FCB（索引结点）的数量和指针等。文件系统被使用时，超级块会被读入内存。
• 随后是空闲空间管理结构（如位示图）、索引结点区、根目录，以及其他文件和目录。

在内存中的结构

内存中的信息用于管理文件系统并通过缓存来提高性能，在文件系统挂载时建立、卸载时释放：

• 内存中的安装表（mount table）：每个已挂载的文件系统分区的有关信息；
• 内存中目录结构的缓存：最近访问过的目录信息；
• 系统打开文件表：每个打开文件的 FCB 副本、打开计数等；
• 进程打开文件表：每个进程打开的文件的读写指针、权限，以及指向系统打开文件表项的指针。

外存空闲空间管理

文件系统要记录哪些盘块是空闲的，以便为文件分配空间、回收被删除文件的空间。

空闲表法

属于连续分配方式。系统为外存上所有空闲区建立一张空闲盘块表，每个空闲区对应一个表项，包括序号、该区第一个空闲盘块号和空闲盘块数。分配时可以采用首次适应、最佳适应等算法；回收时要考虑与前后相邻空闲区的合并。

空闲链表法

把所有空闲盘区拉成一条链：

• 空闲盘块链：以盘块为单位链接。分配时从链首摘下若干块，回收时把盘块挂到链尾；简单，但链很长，为一个文件分配多个盘块时要重复多次操作；
• 空闲盘区链：以盘区（若干连续盘块）为单位链接，每个盘区含有下一个盘区的指针和本区的大小。分配和回收较复杂（要合并相邻盘区），但效率高，链也短。

位示图法

用二进制的一位表示一个盘块的使用情况：0 表示空闲，1 表示已分配（有的题目相反）。磁盘上所有盘块都有一位与之对应，所有位构成一个 m 行 n 列的位示图。

位示图的优点是很容易找到一个或一组相邻的空闲盘块，而且位示图很小，可以放在内存中。

成组链接法

空闲表法和空闲链表法都不适合大型文件系统（表或链太长）。UNIX 采用的成组链接法结合了两者的思想：

• 把空闲盘块分成若干组（如每组 100 块），每组的第一个盘块记录下一组的空闲盘块总数和盘块号，组与组之间形成链；
• 第一组的空闲盘块号和块数存放在内存的超级块中，称为空闲盘块号栈；
• 分配：从栈顶取出一个盘块号分配出去；若取出的是栈底的最后一个盘块号（它记录着下一组），则先把该块的内容读入栈中，再分配该块；
• 回收：把盘块号压入栈顶；若栈已满，则先把栈中的内容写入这个新回收的块，使它成为新一组的第一块，然后栈中只放入该块号。

文件系统的层次结构与虚拟文件系统

现代操作系统的文件系统通常采用层次结构：用户调用接口 → 文件目录系统（管理目录、FCB）→ 存取控制验证模块（文件保护）→ 逻辑文件系统与文件信息缓冲区 → 物理文件系统（逻辑块号到物理块号的转换）→ 辅助分配模块（空闲空间管理）与设备管理模块（启动 I/O）。

虚拟文件系统（VFS）

计算机中可能同时存在多种文件系统（如 ext4、FAT32、NTFS、网络文件系统 NFS）。虚拟文件系统为用户程序提供了文件和文件系统操作的统一接口，屏蔽了不同文件系统的差异和操作细节：用户程序只需调用 open()、read()、write() 等 VFS 提供的统一函数，由 VFS 转去调用具体文件系统的实现。

为了实现 VFS，Linux 抽象出四种对象：超级块对象（表示一个已挂载的文件系统）、索引结点对象（表示一个文件）、目录项对象（表示路径中的一个目录项）和文件对象（表示一个被进程打开的文件）。一个新的文件系统要在 Linux 上使用，就必须实现 VFS 规定的这些接口函数。

文件系统挂载

文件系统在被进程使用之前，必须先挂载（mount，也称安装）。挂载时操作系统要：

1. 在 VFS 中注册新的文件系统：把它的信息（类型、容量等）加入内存中的挂载表；
2. 新文件系统向 VFS 提供一个函数地址列表，供 VFS 调用；
3. 把新文件系统加到挂载点——现有目录树中的某个目录上，此后访问该目录就是访问新文件系统的根目录。例如 mount /dev/sdb1 /mnt/usb。

提高文件访问速度

除了改进文件的目录结构和检索方法外，还可以：

• 磁盘高速缓存：在内存中为磁盘盘块设置缓冲区，存放最近访问过的盘块，访问时先查缓存；
• 提前读：顺序访问文件时，在读当前盘块的同时把下一个盘块也读入缓冲区；
• 延迟写：写入的数据先留在缓冲区中，等缓冲区要被重新分配时再写回磁盘，可以合并多次写操作；
• 优化数据布局：为文件分配连续的盘块（簇），把索引结点放在磁盘的中间位置，以减少寻道；
• 虚拟盘：用内存模拟磁盘（RAM 盘），速度很快，但掉电后数据丢失。

即时练习