首发公众号：Rand_cs

文件系统理论部分

文件系统是操作系统的重要组成部分，是对文件的组织管理，本文就主要讲述磁盘上的文件是如何组织的和文件操作两个部分，废话不多说直接来看。

文件存储

$Linux$ 里有一句耳熟能详的话，一切皆文件，这也是 $UNIX$ 系统的哲学体现。不论是普通文件，目录，块/字符设备，网络设备套接字等等，对于 $Linux$ 来说都是文件，虽然它们的类型不同，但是 $Linux$ 系统为它们提供了一套统一的接口来统一对待统一操作。

本文不聊那么多种文件，只来说说存储在磁盘上的文件，文件要存储在磁盘上的关键问题是记录各个文件分别用到哪些磁盘块，一般有着以下一些方法。

连续分配

连续分配，顾名思义，将文件放在连续的物理空间中，如下图所示：

即连续分配就是文件存放在连续的数据块中，两个文件不能共用一个数据块，打个比方说如果一个文件实际利用了 3.5 个数据块，但实际上占用了 4 个数据块。前文也说过，文件系统操作的最小单位就是块，不能够再细分。

连续分配有着如下的优点：

实现比较简单，连续分配的表示只需要记录起始块的地址和长度。
读写效率比较高，因为数据块是紧密连续的，访问文件时基本只需要一次磁盘寻道便能读出整个文件。

但是缺点也很明显：

磁盘碎片，假设删除文件1后来了个新文件，如果这个新文件小于 3 个数据块，那么就能够放下，如果大于 3 个数据块则放不下产生碎片。因为要连续分配，分配空间时必须要找到一段合适的连续空间，若不存在即使所有碎片总和大于文件所需的空间也无济于事。
文件的长度不易扩展，如上图所示文件都是紧密连续挨着的，要想扩展一个文件，当它后面有足够的空闲空间还好说，若没有那就只有另外寻找合适的空闲空间再整体移动，这是非常低效麻烦的。

链表分配

采用链表结构文件占用的各个数据块不必连续放置，每个数据块空出一定空间作为指针指向下一块，就如同链表一般，数据块就相当于结点，示意图如下：

这种组织形式的优缺点也很明显，就是数据结构里面讲的链式结构的优缺点，使用链表文件数据块便不必顺序存放，增删都很灵活，顺序读取比较方便但是随机访问比较麻烦。当某个数据块损坏或丢失便可能导致后续块的丢失。

再者块大小一般是 2 的幂次方大小，但是这种方式组织文件每个数据块的大小不再是 2 的幂次方。许多程序会要求 2 的幂次方来读写数据，这就可能会导致额外的开销。

为解决上述问题，提出了一种解决方案，将所有的块指针拿出来组织在一起形成一个表放在内存中，这个表就是文件分配表(FAT, File Allocation Table)。

如上图所示，文件 A 按先后顺序使用了块 4、0、6、2，文件 B 使用块 5、1、3、10、8。

由于每个磁盘块都会有一项记录所以文件分配表是跟磁盘大小成正比的，磁盘过大时文件分配表便会占用很多的内存，所以这种方案并不适用于大磁盘。

索引结构

上述的 FAT 是将所有的磁盘块指针集中在一起放在内存中，使得文件使用的磁盘块能够前后连起来，而索引结构则是单独地将每个文件用到的磁盘块地址维护起来。也就是说为每个文件建立一个索引数据结构，里面存放的是文件使用的各个磁盘块地址。这是直接索引的方式，还有一级乃至多级索引，意思是存放的地址指向的并不是数据块，而是索引块，这个索引块里面又来存放数据块或者索引块地址。

我们来看看 $Linux$ 操作系统使用的索引结构 $inode$，$inode$ 包含的信息很多，这里我们只是先说有关寻址的部分，直接来看大致结构图：

注每个块里面应存放了多个地址项，示意图只画出了一个来，关于这个问题操作系统里面有个经典例题，就比如说上图表示的 $inode$，有 12 个直接索引，1 个一级索引，1 个二级索引，1 个三级索引，再假设每个块 1 KB，一个地址项需要 4 字节来表示，则该 $inode$ 最大能表示多大的文件？

直接索引：$12 \times 1 = 12KB$

每个索引块能存放 $1KB\div4B=256$ 个地址

一级索引：$256\times1KB=256KB = 4MB$

二级索引：$256\times256\times1KB=2^{16}KB=64M$

三级索引：$256\times256\times256\times1KB=2^{24}KB=16G$

则支持的最大文件大小为将他们加和起来得到的结果约为 16G。

空闲空间管理

上述是对文件所使用的磁盘块的管理实现方式，对于磁盘上空闲的块也需要管理，这样当需要为一个新文件分配磁盘块的时候才方便操作，对于空闲空间的管理有着以下一些方法

空闲区表法

磁盘上一段连续的未分配区域叫做空闲区，空闲区表属于连续分配的方式，具体做法是建立一张表，记录第一个空闲块的块号和连续空闲块个数。

空闲链表法

每个空闲块里面存放一个指针，指向下一个空闲块，用这种方式将空闲块给串起来，将第一个空闲块保存在磁盘的特殊位置，同时也缓存在内存当中。

当创建文件时则从链头取下几块分配给该文件，当删除文件时将该文件占用的磁盘块连接到链头。

空闲块成组链表法

上述两种方法都不适合大型文件系统，会导致空闲表过大或者链式结构过长。空闲成组链表法顾名思义，先将空闲块分成一个个组，然后将这些组用链表法串起来。

将组中的组长块(一般第一个)作为“指针”指向下一个组，当然整个块是不可能只存放一个指针的，不然未免也太浪费了些，其实这个块里面还要存放下一个组的空闲块数、组长块号、各空闲块号等信息。

位图法

大家应该很熟悉了，就是用一个 bit 来表示一个磁盘块的使用情况，1 代表使用，0 代表空闲。对于 $1G$ 的磁盘，$1KB$ 的块大小，有 $2^{20}$ 个磁盘块，则需要 $2^{20}bit / 8 = 128KB$ 来表示。

使用位图法会增加 CPU 的计算负担。

EXT2

来看一个具体的文件系统 EXT2，捋一捋上面所讲的知识点，看看 EXT2 这种文件系统在磁盘上是怎么布局的。

总体布局

直接先来看总体结构布局图：

名词解释

$MBR/GPT$，操作系统引导块：不用多说了吧，见前文磁盘及分区

超级块：描述整个分区的文件系统信息，$inode$/数据块的大小、总量、使用量、剩余量，文件系统挂载时间、最近一次写入数据时间、最近一次检验磁盘时间等信息。

块组描述符表：块组描述符表存放的是块组描述符，有多少个块组就有多少个块组描述符。块组描述符存储的是 $inode$ 数组，数据区域的起始位置，$inode$ 和数据块的总量剩余量等信息，块组描述符表在每一个块组中都有一份拷贝

块位图：标记块的使用情况，只占用 1 块，加入格式化的时候设置的块大小位 $1KB$，则一个块组最多有

$inode$ 位图：标记 $inode$ 的使用情况，每一个 $bit$ 表示 $inode$ 是否空闲可用。

$inode$ 数组：存储所有 $inode$ 的地方，$inode$ 几乎包括了一个文件除文件名之外的所有信息，主要包括文件大小，拥有者组的 $ID$，读写执行权限，时间戳等属性信息，还有就是数据块指针。

数据块：存放具体的文件内容数据

另一种是相对路径，相对于当前位置的路径，不以 '/' 开头，比如说 a/b.txt，当前目录下查找 a 目录，a 目录下查找 b.txt 文件。c.txt 表示在当前目录下查找 c.txt 文件，一般来说 b.txt 和 ./b.txt 的意思是一样的。../d.txt 表示在当前目录的父目录下查找 d.txt 文件。

查找

上面一直在抽象地说查找，下面来具体看看怎么根据路径来找到相应的文件。前面说过单看路径这一串字符的话，会发现其实路径就是被分隔符 '/' 隔开的一个个文件名，有了文件名那就好办了，目录项里面就存储着文件名和 inode 编号的对应关系，所以查找文件就是在目录项中根据文件名找到相应 inode 编号，具体的可以分为以下四步：

在根目录或当前目录中寻找文件名对应的目录项
从目录项中获取 inode 编号，然后在 inode 数组中找到相应 inode
从 inode 中获取文件/目录的数据块地址
重复上述步骤找到到最后需要的文件

文件操作

inode 存储的是文件本身的信息，对于文件我们经常要不停的操作，所以也得有记录文件操作信息的结构。

文件结构体和文件表

这个数据结构就是文件结构体(struct file)，打开一个文件就会产生一个文件结构体，所有的这些文件结构体由内核集中管理组成文件表，文件结构体也就是文件表的表项。文件表是全局的，不是某个进程私有的。

文件结构体主要包含的信息路径，inode 指针，打开次数，文件偏移位置等等。都应该很好理解吧，不详细解释了。

文件描述符和打开文件描述符表

但每个进程操作的文件不应该隔离开吗？对头，所以每个进程又有一个打开文件描述符表(struct file *fd_array[NR_OPEN_DEFAULT])，可以看出它是一个指针数组，指向的是文件表项(文件结构体)。

这个数组的索引便是文件描述符，它是一个数组的索引，所以文件描述符都是非负整数。

dup 和 dup2

这是两个关于文件描述符的函数，dup 的函数原型如下：

int dup(int oldfd);

函数 dup 复制文件描述符 oldfd，返回一个新描述符 newfd，这个 newfd 有以下两个特点：

newfd 是当前可用文件描述符中最小的
oldfd、newfd 两个描述符指向同一个文件表项

dup2 与 dup 很相似，函数原型如下：

int dup2(int oldfd, int newfd);

该函数的功能与 dup 相似，只是可以自己决定返回的文件描述符，而不是返回最小可用的文件描述符。

当 newfd 是空闲的或者等于 oldfd 的时候，返回 newfd。
当 newfd 不是空闲的指向某个文件时，先关闭那个文件再返回 newfd。

文件指针和文件流指针

文件指针就是打开文件描述符表的元素，即 fd_array[i] ，指向的是文件表项。

文件流指针式 c 语言里面用的，c 语言头文件 stdio.h 中定义了一个 FILE 结构体，名字与 file 结构相同，不要搞混淆了，来看看怎么定义的：

struct _iobuf {
   
   
        char *_ptr;      //文件输入的下一个位置
        int   _cnt;      //当前缓冲区的相对位置
        char *_base;     //指基础位置(即是文件的其始位置)
        int   _flag;     //文件标志
        int   _file;     //文件的有效性验证，实际上就是文件描述符
        int   _charbuf;  //检查缓冲区状况,如果无缓冲区则不读取
        int   _bufsiz;   //缓冲区大小
        char *_tmpfname; //临时文件名
        };
typedef struct _iobuf FILE;

上面那个 int _file 实际上就是文件描述符，所以 c 语言的 FILE 结构体其实就是文件描述符的封装，然后多了一个缓冲区以及一些其他信息。

这下捋清楚有关文件操作的这些名词了吧，弄清楚上面的内容后我们再来看一看关于文件描述符和文件表项需要注意的一些地方：

打开文件描述符表在进程的 PCB 中，就是那个 task_struct，不太清楚的可以看看前文
每次打开一个文件便会创建一个文件结构(文件表项)，即使多次打开同一个文件也是如此，不论是同一个进程多次打开相同文件还是不同进程打开同一文件都是如此。
一个文件对应一个 inode，一个文件可以打开多次，也就对应多个文件表项，所以一个 inode 也就对应多个文件表项。
同一个进程的不同文件描述符可以指向同一个文件表项，用 dup 函数实现
fork 创建子进程时会复制父进程的打开文件描述符表，所以父子进程共享文件表项。

最后来看一看示意图从头捋一捋：

具体操作

关于文件我们在内存里面维护了三种数据结构：文件描述符，文件结构体，以及内存中的 inode，这三种结构集合起来就是上面所讲过的各种表，内存中的 inode 基本上和磁盘上的一样，可以看作是磁盘上的 inode 缓存。

当然文件的部分具体数据在内存里面也是有缓存的，操作文件在内存中的缓存和为其维护的结构，再同步到磁盘就是有关文件的系统调用实际干的事情。

同步到磁盘可以看作是写磁盘，有关磁盘的读写操作都是有具体的指令 in 和 out。可以使用内联汇编等方式将这两条指令封装成函数便于调用。

下面来看一些具体的文件操作的大致原理。

创建文件：一个文件对应一个 inode，创建一个文件就要使用一个 inode，所以要在 inode 位图和 inode 数组中申请空闲的 inode。当然创建的还有文件本身，所以也要在块位图中申请数据块。文件肯定也要属于某个目录，所以该目录要增加一个目录项。

打开文件：一般是根据给定的路径和标识打开文件，所以首先要进行路径解析，得到文件的 inode，将其加载到内存中的 inode 缓存中，然后创建文件表项，创建文件描述符。

关闭文件：回收相应文件描述符，文件表项中的文件打开数减一，如果减到 0 的话再删除文件表项，回收缓存中的 inode。

读写文件：大致就是对磁盘的读写，使用上述说的 in 和 out 指令，但是磁盘 I/O 速度很慢，所以都需要一个缓存区中转来减少 I/O 次数。当然还有一些其他技术比如说 DMA，这儿就不展开了。

文件的读写指针定位(lseek)：其实就是设置文件表项中的文件偏移属性。

删除文件：基本上就是创建文件的逆操作。

创建目录：为新目录分配 inode，分配块，新目录中添加两个目录项 . 和 .. ，新目录的父目录中添加新目录的目录项。

删除目录：也基本上就是创建目录的逆操作

至于目录的其他操作原理基本也和普通文件类似，或者说对于磁盘上文件的所有操作基本原理都类似。记住 CPU 是不能和磁盘直接交换数据的，直接与 CPU 打交道的是内存，所以要对磁盘上的文件做什么操作都是要先读取到内存，在内存中操作完之后同步到磁盘。

虚拟文件系统

操作系统可能支持多个文件系统，各个文件系统对文件操作管理实现的方式可能不尽相同，而为了统一，在文件系统之上添加一个代理虚拟文件系统，使其对外表现出统一的接口。

进程，虚拟文件系统，文件系统，外存的大致关系如下所示：

虚拟文件对外提供统一的接口供进程调用，这个接口一般是 POSIX 标准的系统调用，比如说 open，write 之类的，各个文件系统提供实际的功能函数进行实际的操作。

$Linux$ 不像 $Windows$ 为每一个分区分配一个字母作为盘符，每一个分区直接摆在那了，Linux 要使用某个分区必须要挂载到某个目录才行。

挂载是一种访问文件系统的方法，实际上就是将某个文件系统和当前目录树中的一个目录联系起来的一个过程。举个例子，我要将一个新分区上的文件系统挂载到 /a 底下，那么 /a 这个目录就会显示新的分区上的信息，之后就可以对其上的文件进行操作。

这个目录原则上应该是空目录，否则这个目录下的东西会被暂时隐藏掉，直到卸载之后才会重新出来。

有关文件系统本文就先说到这，后面看 xv6 的文件系统是如何设计的。好了本节就这样吧，有什么问题还请批评指正，也欢迎大家来同我讨论交流学习进步。
首发公众号：Rand_cs

xv6(9) 文件系统理论部分