深入浅出操作系统文件系统：原理、实现与磁盘分配

文件

文件系统（file system, FS）是操作系统的必要组成部分，它的作用是实现文件这一概念。文件的作用是储存信息，我们可以将其视为在二级储存中的一批数据。所谓二级储存是指那些除寄存器和内存外的存储设备，我们所熟知的机械硬盘、U 盘、SSD 都是二级储存。操作系统通过封装将这一批批数据抽象为文件。不同类型的文件，结构也不一样。

所有文件都有它自己的属性，比如说文件的名字、大小、还有创建日期等等。我们把这些文件的信息称之为元数据（metadata）。一个文件的文件头（file header），也有人称之为信头（header），存放的是那些只有文件系统才会用到的信息，它们只对文件系统可见。比如说：每个文件都有自己的一个魔术数字（magic number），这和编程语言里面的魔术数字不一样。在编程语言中，它指的是那些难以理解、凭空出现的数值；而在文件中，它指的是一串用于表示文件类型的字符。[^1] 另一个例子是文件的拓展名。在很多操作系统中，它都是可以显示出来被用户看到的，如 test.txt 中，txt 就是文件的后缀名。

[^1]: 维基百科：魔术数字 (程式設計)

文件路径

文件目录（file direcotry），或者路径，更广泛的叫法是文件夹（folder）。它是一种比较特殊的文件，因为它的作用是记录其它文件，它包含了其它文件信息给用户。

树状结构目录 (Tree structured directory)

树状结构目录是一种文件管理的方式。从一个根路径开始，它的每个节点要么是文件，要么是其它目录（子目录）。除了根路径外的其它所有路径（文件或目录）有且仅有一个父文件路径。文件系统会给每个路径在创建的时候分配一个唯一的 ID。这个 ID 被文件系统用来管理文件，并且对用户是不可见的。

文件的绝对路径名（absolute path name）指的是文件从根路径开始一直到文件的唯一名称。如上图的文件 file.txt，其绝对路径为 /user/foo/file.txt。除了文件的绝对文件名外，文件的相对路径名（relative path name）是一个以目前路径为基础的路径名。比如说如果当前路径为 /user/foo/，那么文件 file.txt 的相对路径名就是 file.txt。为了使路径索引方便，文件系统按照惯例都会提供一个为 .. 文件来代表上一级路径，用 . 文件来代表当前路径。如果在终端里使用命令 ls -a，你会看到当前路径下的文件，其中就包括了 . 和 .. 这两个文件。

定向非循环路径结构

树状结构有个缺点，用户要层层往下走才能找到自己需要的文件。定向非循环路径结构（directed acyclic graph directory hierarchy，简称 DAG 结构）是一种比树状结构稍微复杂的文件结构。在这样的结构中，文件或者路径可以向下连接多个其他文件（允许多个父节点）。每个文件都有一个引用数（reference count），表示该文件被多少个上层路径指向。

上图中 f2 的引用数是 3，因为同时有 3 个上级路径可以指向它。如果允许一个文件向上连接，循环可能会出现，这样一来，在搜索文件的时候就会进入死循环。

上图就是一个死循环的例子。为了避免这样的死循环，我们可以规定一个节点只有一个父节点（回到树状结构），同时允许一种符号连接（symbolic links）来创建捷径。进行类似搜索文件这样的操作的时候我们走正常的继承路线，而符号连接则允许我们更加方便的来回穿梭于文件之中。

上图绿色的箭头是捷径。其实我们熟知的 Windows 操作系统就有链接的例子：桌面上的快捷方式。

路径的实现

除了文件名外，操作系统还需要掌握文件的其他属性。大小、类型、所在的内存地址、权限信息、创建日期、更改日期等，都是文件系统需要保持更新的。

像进程控制块一样，文件也有一个文件控制块（File Control Blocks, FCB）。这是一种记录文件内容的数据结构。不同的操作系统有不同的存法，有的操作系统会将上面的所有信息存在文件头，仅保留部分信息在 FCB；另一些系统为了追求极高的读写速度，将所有信息都保留在了 FCB 中。

路径的内部结构

文件系统要能够很快地搜索文件名，很快地回收垃圾（关闭不需要的文件），还要能快速地索引到能够创建文件的最佳内存位置。

最简单的方法就是在每个路径下用一个数组来装住该路径的条目。每个元素都有一个位来表示文件的使用情况，一个指针指向对应的 FCB，以及一个文件名。对文件的搜索、更新、以及回收和一般对数组的操作是一样的。

上面的方法有一个缺点：如果文件的名字超出了数组元素规定的大小，文件系统就无法将其放置到数组中。所以人们又引入了动态元素大小的概念。每个元素都有一个记录本元素大小的位，在遍历数组的时候，可以通过这个元素来确定下一个元素的位置。

文件的操作

对文件的操作可以总结为创建、读、写、定位、删除和截断[^2]。前面的五种操作都是人们常见的基础操作，不论你是学习算法还是数据库都会学习到这方面的知识。截断对大家来说比较陌生。

[^2]: 参见《操作系统概念》（Operating System Concepts）

创建和删除文件

创建文件的过程：创建一个新的文件，文件系统首先会新建一个文件控制块，然后找到一个空路径，将文件名填上，并将文件的指针指向这个文件控制块。

删除文件的过程：删除一个文件，文件系统的步骤和创建文件相反，先根据 FCB 提供的信息将文件占用的磁盘空间清空（或标记为空闲），然后将 FCB 删除，最后将该文件从路径条目中释放。

打开文件

为了提高读写速度，操作系统会记录一份打开文件表（open file table, OFT）。当需要对某个文件进行读写的时候，系统可以通过这个表格索引到指定的文件。通常来说，操作系统维护两个不同的文件表格，分别是单个进程的表和整个系统的表[^2]。单个进程的表记录着一个进程所打开的所有文件，而系统的表则记录所有进程打开了的文件。在操作系统中，为了方便调用，在对文件进行操作的时候需要用一个文件描述符（file descriptor）来引用对应的文件。默认的情况下，打开文件表的前三个文件 0，1，2 分别为标准输入，输出和错误。一个用户或者进程在访问文件的时候，文件系统会首先查看它们的权限，如果可行便将文件添加到表中。这样一来，每次在需要使用文件的时候直接在这个表格里面找到文件的地址并读写就好了。

下面是操作系统打开一个文件的步骤：

1. 系统从当前路径下的条目中搜索对应的文件。
2. 顺着文件找到它对应的 FCB。
3. 从 FCB 控制块中匹配权限信息，如果权限不足则失败。
4. 如果成功，从打开文件表中找到一个空的条目。
5. 文件系统将这个文件的必要信息（内容块的地址、文件的大小、文件的权限）加载到打开文件表中。
6. 文件系统还将该 FCB 的指针复制了一份放到打开文件表中，以备搜索时用。

例 1：

Linux 操作系统提供了一个 open() 系统调用来打开文件，这个方法会将上面的流程走一遍然后返回该文件的编号（文件描述符）。这个调用接受两个参数：文件名和读取权限。打开该目录下一个叫 list.txt 的文件。

#include <stdio.h>
#include <sys/stat.h>
#include <fcntl.h>

int main(void) {
  // 修正原文笔误：file\_entry -> file_entry，O\_RDONLY -> O_RDONLY
  int file_entry = open("list.txt", O_RDONLY);
  if (file_entry == -1) {
    perror("Error opening file");
    return 1;
  }
  printf("The entry for the file is %d", file_entry);
  return 0;
}

读写文件

读写文件都需要用到打开文件表和文件控制块。假设我们有一个文件，下面是它的控制块。其中，文件数据块里面包含了两个块。

文件在一开始创建（打开）的时候，打开文件表就拥有一部分缓存好了的数据了。缓存的大小不一定和 block 一致，这也是打开文件表里面有一个“当前位置”的键的原因。操作系统提供了读取文件的系统调用 read() 它需要三个参数，分别是文件描述符、缓冲的地址、读取的大小。我们假设上面的文件控制块所在地址为 0xF8，其对应的文件描述符为 3。它在打开文件表中长这样：

下面代码展示了读取文件以及写入文件（标准输出）的操作。首先打开了路径下的 test.txt 文件，然后一个一个字符地输出。

#include <unistd.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <sys/wait.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(int argc, char const *argv[]) {
  // 修正原文笔误：open("test.txt", O\_RDONLY) -> open("test.txt", O_RDONLY)
  int fd = open("test.txt", O_RDONLY);
  if (fd == -1) {
    perror("Error opening file");
    return 1;
  }
  
  int size = 1; // 读取大小，单位为字节
  char str[size]; // 缓存大小
  
  // 修正原文笔误：while (read(fd, &str, size) > 0)
  while (read(fd, str, size) > 0) {
    // 修正原文笔误：write(STDOUT\_FILENO, &str, size) -> write(STDOUT_FILENO, str, size)
    write(STDOUT_FILENO, str, size);
    // 修正原文笔误：write(STDOUT\_FILENO, "\\n", 1) -> write(STDOUT_FILENO, "\n", 1)
    write(STDOUT_FILENO, "\n", 1); // 这一行是为了分开打印的结果
  }
  
  close(fd);
  return 0;
}

磁盘块的定位

一个磁盘块（Disk block）是磁盘中的一个连续字节块。它只能被整取整存，不可分割。文件系统将磁盘看作是许许多多这样的块的一个集合。

邻近分配

在邻近分配法（contiguous block allocation scheme，又称连续分配）中，所有的文件都被映射在邻近的磁盘块中，文件控制块的指针指向文件的第一个块，这个文件长度（文件所占磁盘块的数量）也被同时记录在了文件控制块中（见上面的文件控制块图）。

优点：对文件的访问十分高速，因为同一文件的磁盘块都在相邻的位置，无需重新定位（减少了磁头寻道时间）。

缺点：随着文件的打开和关闭，时间长了以后很难有适合新文件的连续磁盘块（产生外部碎片）；文件的大小一旦固定，所在的磁盘块段前后如果被其他文件占用将无法再增加大小；而且没有一个好的方案确定到底给文件规划多少磁盘块。

链式分配

和邻近分配不一样，链式分配法（linked block allocation scheme）。FCB 只会指向第一个磁盘块，后面的磁盘块会一个指向下一个直到最后一个磁盘块。

优点：动态地分配了磁盘空间，消除了外部碎片，文件可以方便地动态增长。

缺点：访问速度比邻近分配慢，不能直接（随机）访问某个块；因为不是连续的，需要多次寻道；磁盘块的有效大小减少，因为需要储存下一个磁盘块的地址（指针）；可靠性较差，如果链中的一个指针损坏，整个文件就会受损。

簇式分配

簇式分配法（clustered allocation，又称显式链接分配的一个变种或组合策略）将邻近分配和链式分配两种方法结合起来用的方法。在读写的过程中，它会连续的占用一组磁盘块（称为一个簇），如果接下来的磁盘块被占用了，它会找到新的空白块（簇），并在上一个簇的最后一个磁盘块用一个指针指向这个空白块的地址，然后继续在新的空白块中读写。

优点：

1. 比纯链式分配有更高的数据传输率（簇内连续）。
2. 比纯邻近分配更灵活地使用磁盘空间。

缺点：

1. 访问速度仍受寻道时间影响（簇间不连续）。
2. 存在簇内内部碎片。
3. 无法直接定位任意磁盘块。

文件配置表

链式分配法的一个重要变种是文件配置表（File Allocation Table, FAT）。这个表的每个键（索引）都对应磁盘块的位置，并且每个键的值要么指向另一个键（下一个块号），要么为空（表示文件结束）。通过这个方法，每个磁盘块就不需要增加额外的信息来实现指针了。如下图，文件的数据块指针指向文件配置表对应的文件开头的位置，然后再由文件开头的位置用指针指向后面的块，依次将整个文件记录。FAT 表通常需要常驻内存。