文件系统

基础

什么是文件

以硬盘为载体的存储在计算机上的信息集合，可以使文本文档、图片、程序等，是用户进行输入输出的基本单位，大多数进程的输入都是通过文件来实现的。

文件一般由几个部分组成：

1. 数据项，描述对象的某种属性的一个值，可以分为 基本数据项 和 组合数据项，前者是数据中的最小逻辑单元，后者由多个基本数据项组成；
2. 记录，一组相关数据项的集合，描述一个对象在某方面的属性；
3. 文件，分为有结构和无结构，前者由若干相似的记录组成，后者是一个字符流，如二进制文件。

文件控制块和索引结点

为了便于管理文件，操作系统中引入了文件控制块的数据结构；首先要保存文件的相关信息，如所有者、创建时间、大小和名称等，这些数据被称为 文件属性 或 文件元数据；文件控制块（$FCB$）用来存放控制文件所需要的的各种信息，主要包含基本信息、存取控制信息和使用信息，以实现 按名存取，$FCB$ 的有序集合被称为 目录。

文件目录通常放在磁盘上，当文件很多时，查找会不方便，因此需要建立索引；UNIX 采用了文件名和文件描述信息分离的形式，这样一个盘块中可以存放更多的“文件”，减少了磁盘启动的次数。

文件的操作

操作系统提供系统调用对文件进行操作，有创建、写、读、重定位、删除和截断（所有文件属性不变，删除所有内容）文件。

为了避免多次的重复检索目录，大多数操作系统提供 open 系统调用，显式地打开文件，操作系统会将打开文件的信息存入 打开文件表，当用户发出文件操作请求时，需在打开文件表中搜索，并返回其索引，避免了重复查找；当用户使用 close 时，系统会从打开文件表删除这一文件。

为了允许多个继承同时打开文件，通常才用两级表—— 系统表 和 进程表，前者存储对应文件的索引，后者存储对应文件在系统表中的索引。

info

文件名并不是打开文件表的一部分，因为一旦完成对 FCB 在磁盘上的定位，系统就不再使用文件名，对于访问打开文件表的索引，UNIX 称之为 文件描述符，Windows 称之为 文件句柄；每个打开文件都具有如下关联信息：

1. 文件指针，跟踪上次读写位置，对于打开文件的某个进程是唯一的；与磁盘文件属性分开保存；
2. 文件打开计数，跟踪当前文件打开和关闭的次数，主要用于多进程打开同一个文件，系统表在删除该文件时必须等到所有进程释放该文件；
3. 文件磁盘位置；
4. 访问权限，如创建、只读、读写、添加等。

文件保护

用于防止文件共享对文件本身造成破坏或未经批准的修改，主要有：

1. 访问类型，读、写、执行、添加、删除、列表清单，此外还有重命名、复制和编辑等，这些是高层功能，可以通过系统调用实现；
2. 访问权限，根据用户身份进行控制，为每个文件和目录增加一个 访问控制列表（Access-Control List， ACL），常用精简版简化空间管理，包括拥有者、组和其他，分别表示创建文件的用户，需要共享文件且具有类似访问的用户，系统内的其他用户；
3. 口令，用户创建文件时添加一个口令，系统在 FCB 上附上相应口令，同时告诉其余的共享用户，进行文件操作时必须提供相应的口令；时间和空间开销低，但是口令存在系统内部，安全性低；
4. 密码，对文件进行加密，保密性强，但是编码和译码需要一定时间。

现代操作系统的常用文件保护方法是将访问控制列表与用户、组和其他成员访问控制方案结合；对于多级目录结构，对目录提供的保护机制和文件保护并不相同。

文件的逻辑结构

从用户出发看到的文件组织形式，可分为：

1. 无结构、流式，最简单的文件形式，按照顺序组成为记录，以字节为单位；
2. 有结构、记录式，可分为：
   1. 顺序文件，文件中的记录顺序排序，记录通常是定长的，顺序存储或链式存储；顺序文件可以是串结构，按照存入时间排序，检索必须从头开始顺序查找，另一种是顺序结构，对所有记录按照关键字排序，可以采用折半查找；
   2. 索引文件，对于定长记录文件，采用类似数组的下标方式查找记录；对于边长记录文件，需要顺序查找，效率较低，因此可以建立索引表，按照关键字排序，标记每个记录的起始地址和长度，索引表本身也是一个 定长记录的顺序文件，相当于进行了转化，加快了检索速度；
   3. 索引顺序文件，前两种的结合，将顺序文件中的所有记录分为若干组，为顺序文件建立一张索引表，在索引表中为每组第一条建立索引项；同一个组内的关键字可以无序，但是组间必须有序；对于长为 $N$ 的顺序文件，平均查找需要 $N/2$，但若将其分为 $\sqrt N$ 组，则在索引表顺序查找为 $\sqrt N/2$，组内顺序查找 $\sqrt N/2$，总计 $\sqrt N$，这就是数据结构中的分块查找；当记录数太多了，可以使用多级索引；
   4. 直接文件、散列文件（Hash File）。

文件的物理结构

连续分配

每个文件在磁盘上占有一组连续的块，支持顺序访问和直接访问，实现简单、存取速度快，但是文件长度不宜动态增加，否则可能需要大量移动盘块，删除和插入文件记录会改变文件长度，反复增删文件后会产生 外部 碎片。

目录中存有文件的起始地址和长度。

链接分配

离散分配方式，消除了外部碎片，无须事先知道文件的大小，对于文件的插入、删除和修改都十分方便，有：

1. 隐式链接，目录中存储第一个记录的地址和最后一个记录的地址，其余指针存在盘块中（类似链表结构体），因此叫隐式；只能顺序查找，且 稳定性较差，链接可能丢失或损坏，通常的解决方案是将几个盘块组成 簇（cluster），按照簇来链接；
2. 显式链接，将所有指针单独存在一个链接表中，整个磁盘只设置一张表，称为 文件分配表（File Allocation Table, FAT）；文件目录中存储这每个文件在 FAT 中的起始块号，FAT 是一个 静态链表，存储的是下一个块的块号，若是最后一块，则下一个块号为 -1；若是空闲则使用其他值；FAT 在启动时就会被读入内存，提高了检索速度，减少访问磁盘次数；

索引分配

链接分配解决了连续分配的外部碎片的文件大小管理的问题，但是不能有效支持直接访问（除了 FAT），并且 FAT 占用空间较大；打开文件时，只需要调入该文件的盘号即可，没必要调入整个 FAT，因此引入了 索引块（表），由每个文件所有的盘块号组成

每个文件都有其索引块，这是一个磁盘块地址的数据；索引块的大小应该竟可能小，但是太小就无法支持大文件，方式有：

1. 链接，一个索引块通常为一个磁盘块，可以将多个索引块链接；
2. 多层索引；
3. 混合索引，后面介绍。

混合索引分配

tip

主要用于全面的照顾到小型、中型、大型和特大型文件：

1. 对于小文件，最好直接将其盘块地址放入 FCB，称为 直接寻址；
2. 对于中型文件，采用单级索引，先从 FCB 中找到其索引表位置，称为 一次间址；
3. 对于大型和特大型文件，采用两级和三级索引。

UNIX 系统中，文件不大于 40K 是小文件，文件不大于 4MB 是中、大型文件，二次间址允许文件不大于 4GB，三次间址是 4TB。

目录

tip

FCB 的有序集合就是目录，一个 FCB 就是一个目录项。

目录在用户所需要的文件名和文件之间提供一种映射，因此目录管理要实现 按名存取，同时目录的存取效率直接影响到操作系统，因此要提高对目录的检索速度；多用户系统中，目录应该提供控制访问机制。

目录结构

1. 单级目录，整个文件系统中仅有一张目录表，虽然实现了按名存取，但是查找速度慢、文件不允许重名、不便于文件共享等；
2. 两级目录，分为主文件目录和用户文件目录，解决了不同用户文件的重名问题，提高了检索速度，也可以实现控制访问，但缺乏灵活性、不能对文件分类；
3. 树形目录，在两级目录的基础上进行推广，可以明显提高检索速度和文件系统的性能，支持绝对路径和相对路径；可以很方便地对文件进行分类，层次结构清晰，有效地对文件进行管理和保护；大多数操作系统都采用了树形目录；
4. 无环图目录，树形目录不便于实现文件共享，则树形目录的基础上，增加一些执行同一节点的有向边，共享节点有一个共享计数器，当计数器为 0 时才会被文件系统真正删除。

目录实现

1. 线性列表，采用文件名和数据块指针构成的线性列表，实现简单，但是查询费时（线性查找）；
2. 哈希表，查找迅速，插入删除都简单，但是查询的 I/O 操作开销较大，需要尽可能减小操作磁盘次数，可以将目录表复制到内存；

文件共享

1. 基于索引节点的共享方式（硬链接），即上文的无环图；但是这样文件所有者不能直接删除文件，反而要等共享者都主动删除才行；
2. 符号连接（软连接），系统创建一个 LINK 类型的新文件，若系统读取 LINK 类型的文件，就会根据该文件中的路径寻找对应的源文件；这样文件所有者可以直接删除文件；

文件系统

tip

提供高效和便捷的磁盘访问，允许存储、定位、提取数据；文件系统层次结构如下：

1. I/O 控制，包括设备驱动和中断处理程序，在内存和磁盘系统之间传输信息；
2. 基本文件系统给，向对应的设备驱动程序发送通用命令，以读写磁盘；该层也管理内存缓冲区，保存各种文件系统、目录和数据块的缓存，对于系统性能优化至关重要；
3. 文件组织模块，组织文件及其逻辑块和物理块，将逻辑地址转换为物理地址，并且还包括空闲空间管理器，跟踪未分配的块；
4. 逻辑文件系统，管理元数据，包括文件系统的所有结构，但不包括实际数据；通过 FCB 维护文件结构和文件保护。

文件系统布局

磁盘的每个分区都有单独的文件系统，整个磁盘中包含：

1. 主引导记录（Master Boot Record, MBR） 位于磁盘第 0 号扇区，用于引导计算机启动，后面是分区表，给出每个分区启动和结束的地址；分区表中有一个活动分区，计算机启动时，BIOS 读入并执行 MBR，MBR 的第一件事就是确定活动分区，读入其第一块，即引导块；
2. 引导块（boot block） 是每个分区的第一块，MBR 启动其中的程序，负责启动该分区的操作系统；
3. 超级块（super block） 包含文件系统的所有关键信息，如块的数量、大小、空闲块的数量和指针、空闲 FCB 数量和 FCB 指针等；每个分区中都有；
4. 文件系统中空闲块的信息，后面可能是一个 i 结点，然后是根目录，最后是所有的文件和目录；

文件系统可以加载到内存中以提高性能，可能的数据有：

1. 安装表，包含每个已安装文件系统分区的有关信息；
2. 目录结构缓存，包含最近访问目录的信息，对安装分区的目录，可以包括一个指向分区表的指针；
3. 整个系统的打开文件表；
4. 每个进程的打开文件表。

外存空闲空间管理

包含文件系统的分区通常成为 卷（volume），可以是磁盘的一部分，也可以是整个磁盘，还可以是多个磁盘组成的 RAID 集；卷中存放 FCB 的目录区和存放文件数据的文件区是分离的；由于存在很多种文件表示和存放格式，所以现代操作系统中有很多不同的文件管理模块，可以访问不同格式卷中的文件；卷在提供文件服务前，必要有对应的文件进程进行初始化，划分目录区和文件区，建立空闲空间管理表格和存放卷信息的超级块。

对空闲块的管理有：

1. 空闲表法，连续分配方式，为外存上所有的空闲区建一张空闲表，每个空闲区对应一个空闲表项，包括表项序号、空闲区中的第一个盘块号，空闲盘块数量等，再按照其起始盘块号讯号递增排列；空闲盘区的分配可以采用首次首映或最佳适应；释放空间时也要注意能否和相邻的空闲盘块合并；
2. 空闲链表法，有两种形式：
   1. 空闲盘块链，以盘块为单位连接为一条链，申请空间时，从链首向后，取下适当数目的盘块；释放时，将空闲盘块插入尾部；分配和回收十分简单，但是为一个文件分配盘块时可能要重复多次，效率低，因此链表会拉的很长；
   2. 空闲盘区链，以若干个盘块为单位，通常采用首次使用，分配和回收过程复杂，但是效率高，链表短。
3. 位示图法，使用二进制的一位来表示盘块是否空闲，1 表示占用；
   1. 分配，顺序扫描，从中找出一个或一组空闲二进制位；转换为对应盘号，分配；修改位示图为 1；
   2. 回收，将要回收的盘块号转换为行号和列好；释放；对应位置 0；
4. 成组链接法，空闲表法和空闲链表法都不适用于大型文件系统，会使空闲表或空闲链表太大，UNIX 中所采用的方法，结合了空闲表法和空闲链表法；其中存储空闲盘号的盘块被称为 成组链块，该盘块中按顺序存储着空闲盘块号，只有最后一个块号指向另一个 成组链块；
   1. 分配时，指针默认在第一个成组链块，指针会不断下移，直到最后一个空闲盘块（成组链块），因此将其读入内存，指针移动到第一个块号；
   2. 回收时，指针上移；当块号存满时，将该盘块记入刚回收的新盘块 （作为成组链块）；

info

表示空闲空间的位向量或者第一个成组链块，以及卷中的目录区、文件区划分信息都要存放在磁盘中，一般存放在卷头，在 UNIX 系统中成为 超级块；在对卷中文件操作前，系统要先读入超级块，并且需要经常保持内存和磁盘间超级块的一致性。

虚拟文件系统

tip

虚拟文件系统（VFS）为用户程序提供了文件系统操作的 统一接口，屏蔽了不同文件系统的差异和操作细节；其采用面向对象的思想，抽象出一个通用的文件系统模型，定义了通用文件系统都支持的接口。

如 Linux 中调用 write()，在 VFS 中通过 sys_write() 函数处理，sys_write() 找到具体文件系统，将控制权交给该文件系统。

为了实现 VFS，Linux 主要抽象了四种对象类型：

1. 超级块对象：表示一个已安装（挂载）的特定文件系统，包含文件系统的元信息，如文件系统类型、基本块大小、所挂载设备、操作方法指针，可以通过操作方法指针指向的操作方法表来调用超级块对象上的操作函数，如分配、销毁、读写 inode 和文件同步等；
2. 索引结点对象：表示一个特定的文件，对文件是唯一的，只有文件被访问时，内存中才会创建索引结点对象，其中包含磁盘索引结点的一些数据；该对象中有一个表示是否被修改的 脏位，此外还提供许多操作接口，如创建新索引结点、创建硬链接、创建新目录等；索引结点对象会指向超级块对象和磁盘文件；
3. 目录项对象：表示一个特定的目录项，主要为了解决 VFS 经常切换目录的情况，VFS 在遍历路径的过程中，将其逐个解析为目录项对象；
4. 文件对象：表示一个与进程相关的已打开文件；

Linux 将目录也当作文件对象处理（操作相同），文件系统由层次目录组成，可以层层嵌套；VFS 将常使用的目录存在目录项高速缓存的磁盘缓存中，提高系统性能；其只存在于系统中，系统启动时建立，关闭时消亡。

分区和安装

一个磁盘可以划分为多个分区，每个分区可以安装不同的文件系统和操作系统，没有安装文件系统可以是用原始磁盘，UNIX 交换空间就可以使用原始磁盘。

Windows 系统维护一个扩展的两级目录结构，用驱动器字母表示设备和卷，卷具有常规树结构的目录，与驱动器相关联；启动时，系统自动发现所有设备，并安装所有找到的文件系统。

UNIX 使用系统的根文件系统，由内核在引导阶段直接安装；其他文件系统要么由初始化脚本安装，要么由用户安装在已安装文件系统的目录下；每个文件系统都有自己的根目录，但是安装在其他文件系统下时就成为了子目录。