文件系统的演进与实现

1. 文件系统布局

文件系统被存放在磁盘上，磁盘一般都会被划分为一个或多个分区，每个分区中会存放一个独立的文件系统。 磁盘的0号扇区称为“主引导记录”（MBR），用来引导计算机，MBR的结尾是分区表，该表给出每个分区的起始和结束地址。 在计算机被引导时，BIOS读入并执行MBR，MBR做的第一件事是确定活动分区，读入他的第一个块，称为“引导块”，并执行它，引导块中的程序将装载该分区上的操作系统。 磁盘分区的布局是随着文件系统的不同而变化的。

2. 文件的实现

文件存储的关键问题是记录各个文件分别用到哪些磁盘块，不同的操作系统采用不同的方法。

2.1. 连续分配

最简单的分配方案就是把文件作为一个连续数据块存在磁盘上，如下图所示：

连续分配方案的优点在于：

1. 实现简单
2. 读操作性能好

但是，连续分配方案也有明显的不足：

1. 如上图所示，随着时间推移磁盘碎片会越来越多
2. 不能动态增加文件大小超出要填充的空洞大小

2.2. 链表分配

存储文件的第二种方案是为每个文件构造磁盘块链表，每个块的第一个字作为指向下一个块的指针，块其余部分用来存放数据。

这种方案的优点是可以充分利用每个磁盘块，不会因为磁盘碎片而浪费空间，而且只需第一块的磁盘地址就可以找到其他所有块的地址。 但是这种方案在随机存取时却是非常耗时的，同时由于指针占用了一个字节的空间，导致无法使用2的整数次幂来操作整个磁盘块，这样也会降低系统的运行效率。

2.3. 文件分配表（FAT）

解决链表分配的两个问题的方法就是将指针域提取出来组成一个表格，被称为“文件分配表”（FAT），如下图所示：

但是由于大磁盘拥有过多的块，文件分配表会异常巨大，FAT方案就不太合适了。

2.4. i节点

解决上述问题的一个方案就是为每个文件赋予一个称为“i 节点”的数据结构，i 节点中记录了文件属性和文件块的物理地址，如下图所示：

只有在对应文件被打开时，才会加载相应的 i 节点结构进入内存，而不是在开始的时候就将整个FAT表载入内存。

3. 文件共享

解决文件共享的问题首先要解决文件的同步问题，因为其他用户可能在使用该文件的过程中并不知道该文件拥有者做的修改，解决这个问题的方法有两种：

1. 不将磁盘块放入目录，而是列入一个与文件本身相关联的小型数据结构中，而目录指向这个数据结构（目录项），UNIX操作系统就是使用这种方案的
2. 通过让系统给文件共享者创建符号连接实现共享，虽然共享者的目录中存在的只有一个符号连接文件，但他实际操作的是原文件

第一个方案的问题是，i 节点记录的文件所有者是第一个指向该文件目录项的用户，如果该用户想要删除该文件，则他的所有共享者的目录项都将指向一个无效的 i 节点，而如果该 i 节点被分配给另一个文件，则所有这些共享者都在不知情的情况下分享了一个错误的文件。 解决方法是只删除该文件持有用户的目录项，而该文件的i节点依然存在，并且记录了指向他的目录项的计数，而所有的文件共享者都仍然持有正确的目录项，虽然文件所有者已经不再具备指向该文件的目录项，但是依然可以在文件目录项计数变成 0 的时候删除这个文件。 对于符号连接就不会出现上面的问题，因为文件共享者可以接受符号连接的失效，而同时，删除符号连接也不会对文件本身造成任何影响，但是符号连接的创建和访问需要消耗大量的磁盘存取时间，同时在各种操作中都需要考虑操作的对象究竟是符号连接本身还是他指向的文件。

4. 日志结构文件系统 — LFS

文件系统的瓶颈在于，CPU、内存的访问速度越来越快，而磁盘的访问速度却没有多大提升，为了解决这个问题，伯克利大学设计了一种全新的文件系统 — 日志结构文件系统（LFS） 由于磁盘主要的操作是写操作，所以一些文件系统中使用的提前预读机制并不能获得很好的性能提升。 LFS 的基本思想是将整个磁盘结构化为一个日志，所有写操作都被缓存在内存中，每过一段时间就将所有未决的写操作放到一个单独的段中，作为日志的末尾，一次性写入磁盘，这样可以最大限度的使用磁盘的完整带宽。 LFS 的最大的问题是日志会不断增长，直到占满整个磁盘，因此 LFS 有一个清理线程，周期扫描日志进行磁盘压缩。

5. 日志文件系统

由于日志结构文件系统需要操作系统的支持而没有得到广泛应用，但是其思想却得到了很大的借鉴。 日志文件系统的基本想法是保存一个用来记录系统下一步要做什么的日志，这样当系统在完成任务前崩溃的时候可以在再次启动时查看日志以完成未完成操作，NTFS、ext3、ReiserFS 等文件系统都是日志文件系统。

6. 虚拟文件系统 — VFS

即使在同一台计算机上同一个操作系统下，也会使用不同的操作系统，一个windows很可能有一个NTFS文件系统同时包含FAT32或FAT16的数据分区，当然，也需要不时地添加CD-ROM或DVD的特有文件系统，windows通过分配不同的盘符来让他们独立地处理这些不同的文件系统。 而UNIX系统则做了一个认真的尝试，将多种文件系统整合到一个统一的结构中，因此，对于用户和进程没有必要再去关心文件系统是否可以相互兼容。 绝大多数 UNIX 系统使用虚拟文件系统（VFS），将多种文件系统尝试统一成一个文件框架。 VFS 的关键思想是抽象出所有文件系统共有的部分，并且将这部分代码放到单独的一层，该层调用底层的实际文件系统来具体管理数据。

同时，VFS 的实现让运行于 VFS 上的程序不需要关心数据具体的存储位置，这些问题由 VFS 的底层接口来解决和实现，这样，就可以构建 NFS（网络文件系统），将所有数据都保存在网络。 VFS在解析路径的时候首先搜索已经装载文件的超块表来找到他的超块（用来描述实际的文件系统），然后 VFS 创建一个 v 节点并调用实际的文件系统，以返回对应文件的 i 节点信息，然后将这个信息复制到 v 节点中，最后返回一个包含当前文件位置和指向 v 节点的指针的文件描述符，调用者即可使用它来进行文件的读写等操作。