整理《Operating System Concepts》 第七版第十一章文件系统实现部分，内容均为原书和中文版翻译的摘录，其中原书摘录部分由我 按个人理解简化、翻译为中文，可能存在一些不准确之处 。

文件系统结构

• 磁盘具有如下两个特点因而成为大容量多文件存储的方便介质：
  • 可以原地重写
  • 可以直接访问磁盘上任意一块信息
• 内存和磁盘之间的 I/O 转移以 块 为单位而非字节。每块为一个或多个扇区，扇区大小从 32 ~ 4096B 不等，通常是 512B。
• 文件系统包括多层，下图是一个分层的例子，每一层利用较低层的功能创建新功能以为更高层提供服务。
  • I/O 控制 是最底层，由 设备驱动程序（device drivers） 组成。
  • 基本文件系统（basic file system） 只需要向设备驱动程序发送一般指令就可以对磁盘上的物理块做读写，每个块由它的磁盘地址标识（驱动器 1，柱面 73，磁道 3，扇区 10）。
  • 文件组织模块（file-organization module） 直到文件和它的逻辑块、物理块。因为文件组织模块知道文件类型和位置，因此可以将逻辑块地址转换成基本文件系统用的物理块地址。它也包括 空闲空间管理器 用来追踪未分配的块。
  • 逻辑文件系统（logical file system） 管理元数据，元数据包括文件系统的全部结构数据而不包括文件的具体内容。逻辑文件系统为文件组织模块提供所需的信息，通过 文件控制块（file-control block，FCB） 来维护文件结构，同时也负责保护和安全。
• 目前多数操作系统都支持多个文件系统，UNIX 使用 UNIX文件系统（UFS），基于伯克利快速文件系统（FFS）。标准的 Linux 文件系统是 可扩展文件系统（extended file system） ，常见版本有 ext2 和 ext3。

实现

基本结构

• 磁盘上的文件系统涉及如下一些结构：
  • （每个卷的）引导控制块（boot control block） ：从这个卷引导操作系统所需要的信息，如果这个卷没有安装操作系统则这一块内容为空。它通常是卷的第一块，UFS 称之为 引导块（boot block） ，NTFS 系统称之为 分区引导扇区（partition boot sector） 。
  • （每个卷的）卷控制块（volume control block） ：包括卷或分区的详细信息，如分区块数、块大小、空闲块数量和指针、空闲 FCB 的数量和指针等。UFS 称之为 超级块（superblock） ，在 NTFS 中存储在 主控文件表（Master File Table） 。主控文件表采用关系型数据库，每个文件占据一行。
  • 每个文件的 FCB 包含文件的详细信息（文件权限、拥有者、大小、位置）等，UFS 称之为 索引节点（inode） 。
  • 每个文件系统的目录结构，这些目录结构用于组织文件。UFS 中目录结构包括文件名和相关的索引节点号，NTFS 则保存在主控文件表中。
• 内存内信息用于文件系统管理，可以通过缓存来提高性能。这部分数据在文件系统挂载（安装）的时候被加载，文件系统卸载的时候丢弃，可能包括：
  • 内存中的安装表，含有所有已安装卷的信息
  • 内存中的目录结构缓存，保存最近访问过的目录信息
  • 系统范围内的打开文件表 ，在 文件系统接口 中介绍过，包括每个打开文件的 FCB 副本和其它信息
  • 单个进程的打开文件表 ，每个条目包括指向系统范围内打开文件表的条目的指针以及与进程相关的其它文件信息
• 打开文件表的索引有多种名称，UFS 称之为 文件描述符（file descriptor） ，Windows 称之为 文件句柄（file handle） ，只要文件没有关闭，所有对文件的操作都是通过打开文件表执行的。文件系统中用户进程读文件的操作形式如下图所示。
  

分区和挂载

• 一个磁盘可以分成多个分区，一个卷也可能横跨多个磁盘上的多个分区（RAID 的一种形式）。
• 没有文件系统的分区称作 生（raw） 磁盘，含有文件系统的分区称为 熟（cooked） 的。生磁盘通常用于没有合适的文件系统可以使用的地方，例如 UNIX 的交换空间，或者有的数据库使用生磁盘并将其格式化来满足自己的需求。
• 引导信息可以包含在多个分区中，通常是一组有序块，并作为镜像文件读入内存。镜像文件会按照预先指定的位置开始执行，它除了可以启动一个特定的操作系统，还可以支持 双引导（dual-booted） ，即启动加载器知道有哪些操作系统、文件系统位于引导区，并可以引导磁盘上不同分区的不同类型的操作系统。
• 根分区（root partition） 包括操作系统内核以及其它系统文件，它们在引导时装载到内存中，其它卷会根据操作系统的设定，要么在引导时自动装入，要么通过用户手动装入。当有一个新设备挂载（安装）时，操作系统会验证设备上的文件系统是否有效，并根据需要自动/手动纠正。验证通过后，操作系统会在内存中的 挂载表/装入表（mount table） 中标注该文件系统已经装入，并且存储与此文件系统有关的信息。
• 虚拟文件系统（Virtual File System，VFS） 是文件系统接口和文件系统之间的一层，它的目的有：
  • 定义一个 VFS 接口将文件系统的通用操作和具体实现划分，多个 VFS 接口的实现能够在同一台机器共存，因此它允许访问安装在本地的多种类型的文件系统；
  • VFS 提供了在网络上唯一标识一个文件的机制。它基于 vnode 文件表示结构（包括一个唯一的数值标识符，它能够表明位于整个网络范围内的唯一文件，例如 UNIX 的索引节点 inode 在文件系统内是唯一的）。

目录实现

• 线性列表（linear list） 是实现目录最简单的方法，运行非常低效。查找文件需要线性搜索，排序列表可以二分搜索，但排序的需求使文件创建/删除复杂化，它的优点在于可直接生成排序目录信息，可用 B 树实现。
• 哈希表（hash table） ：在线性列表存储目录之上使用哈希表，根据文件名哈希出一个指向线性列表中元素的指针，需要一些措施避免 冲突（collision） 。其困难在于，如果使用固定大小的哈希表，当条目超出哈希表容量时需要扩充哈希表大小，并且设计新的哈希函数将文件名映射到新的范围内。可以使用 chained-overflow 哈希表，使表中元素为一个链表而非单个记录。虽然冲突将使每个链表长度较大，查找可能变慢，但仍比线性搜索快得多。

分配方法

连续分配

• 连续分配（contiguous allocation） 要求每个文件在磁盘上占据连续的块。磁盘地址有一个线性序列，如果只有一个作业按照这个序列的顺序访问磁盘，在访问了块 b 后访问块 b+1 就无需移动磁头，即使需要移动磁头也只需要移动一个磁道（从一个柱面的最后扇区到下个柱面第一扇区）。因此， 访问连续分配文件所需的寻道数最小，即使确实需要寻道，所花费的寻道时间也最小 。在文件连续分配中，一个文件的目录条目包括文件占有的第一个块的地址，以及该文件分配的块的数量（分配区域的长度）。
• 连续分配文件访问非常容易，既可以顺序访问也可以随机访问。它也存在问题，例如如何为新文件寻找空间，这个问题可看作 内存管理 中 动态存储分配 问题的一个具体应用，即如何从一个空闲的孔列表中寻找一个满足大小为 n 的空间，常用首次适应和最佳适应。
• 连续分配方案的另一个问题是需要确定文件需要多少空间，这个知识是无法预知的。如果为一个文件分配的空间过小则文件可能无法原地扩展文件，这时要么终止用户程序并通知用户必须分配更多空间才能运行（这样用户就会过高的预估所需的磁盘空间造成浪费），要么找一个更大的孔，将文件复制到新空间，释放旧空间，但这比较耗时。
• 修正的连续分配方案：开始时为文件分配一块连续空间，一旦空间不够，另一块称为 扩展（extent） 的 连续空间 就会被分配给文件。这种情况下，文件块的位置就需要通过开始块地址、块数、指向下一个扩展的指针三项来确定。如果扩展太大，内部碎片会变得严重；随着扩展的分配、删除，外部碎片也将变得严重。

链接分配

• 链接分配（linked allocation） 解决了连续分配的全部问题。链接分配中，每个文件由分布在磁盘上各个位置的多个磁盘块组成，文件目录条目记录了一个文件第一块的指针和最后一块的指针。每一块都会有一个指向下一块的指针，用户无法使用存储这些指针的空间（例如一块有 512B，磁盘地址为 4B，则用户只可用 508B）。
• 链接分配对于创建/读/写文件的操作如下：
  • 创建新文件时只要简单的在目录中增加一个新条目，条目中有指向文件第一块的指针，初始化为 nil 以表明这是空文件，大小字段也是 0。
  • 写文件时通过空闲空间管理器寻找一个空闲块，这个块会被写入数据、链接到文件最后一个块的尾部，同时要更新这个文件在目录中条目的记录值（大小、最后一个块的地址）。
  • 读文件通过条目中存储的第一个块的地址，逐个向后寻找。
• 链接分配的缺点在于：
  • 只能用于文件的顺序访问，要找到文件的第 i 块必须要从第一块开始寻找，每次访问都需要读磁盘，这还需要涉及磁盘寻道的延迟。因此 链接分配无法有效支持文件直接访问 。
  • 指针需要空间，每一块都有一定空间被指针占用。这个问题的解决方法是将多个块组成 簇（cluster） ，按簇而不是块来分配（如一个簇有 4 块）。这样指针占用的磁盘空间百分比会下降，但增加了内部碎片。簇可以改善多数算法中的磁盘访问时间，因此在绝大多数操作系统中得到应用。
  • 可靠性：文件通过指针链接，一旦有一个指针丢失/损坏，整个文件都将崩溃。一个逃避性的解决方案是采用双向链表，或者给每个块存上文件名和相对块数（相对第一块是第几块），但这又增加了过多的额外开销。
• 链接分配方法的一个变种是 文件分配表（file-allocation table，FAT） ，它被应用于 MS-DOS 和 OS/2 操作系统。每个卷的开始部分存储文件分配表，卷内的每一块都在表中占有一项，这个表可以通过块号码索引， 表中存储的值是这一块指向的下一块块号 。
  • 文件在目录中的条目只含有文件第一块的块号，访问文件时按照 FAT 表中存储的链接关系一直向下寻找，直到最后一块（最后一块在 FAT 表中标记为一个特殊的文件结束值，可以根据这个值判断是否为最后一块）。
  • 要分配一个新的块，只需要在 FAT 表中找到第一个值为 0（值为 0 表示一个块没有被使用）的块，用新块的地址替换掉此前最后一块的文件结束值，并且用文件结束值替换 FAT 表中的 0。
  • FAT 需要采用缓存才能提高效率，否则可能导致大量的磁头寻道时间：磁头要移动到卷的开头读入 FAT 以获得块的位置，然后才能移动到块本身。最坏情况下每块的读取都要移动两次。但它的优点在于改善了随机访问时间， 因为 FAT 的存在，操作系统可以快速找到文件任意一块的位置 。
    

索引分配

• 如果不采用 FAT，链接分配就无法有效支持直接访问，因为块指针散布在整个磁盘，必须顺序读取。 索引分配（indexed allocation） 把所有指针放到一起，通过 索引块（index block） 解决此问题。
• 每个文件都有自己的索引块，它是一个磁盘块地址的数组。索引块的第 i 个条目代表文件的第 i 个块，条目中含有索引块的磁盘地址。要读取第 i 块只需要通过索引块第 i 个条目存储的指针来访问（类似第八章分页）。
  • 创建文件：索引块中所有指针设为 nil。
  • 第一次写入第 i 块：从空闲空间管理器获取一个空闲块，将数据写入块，并将块地址写到索引块的第 i 个条目中
• 索引分配支持直接访问且没有外部碎片问题，但索引分配会浪费空间 ：如果一个文件只有两块长，链接分配只需要每块浪费一个指针，而索引分配需要为这个只有两块的文件创建一个完整的索引块，这个索引块里只有两个指针被使用到。
• 索引块的大小需要经过仔细考量：每个文件都有一个索引块，索引块太大会造成浪费，太小又不足以满足大文件存储需求。针对这一问题的处理机制有如下几点：
  • 链接方案（Linked scheme） ：一个索引块就是一个磁盘块。它本身能够直接读写，当遇到大文件存储时可以将多个索引块链接。例如一个索引块可以包含一个头部（头部包含文件名）以及 100 个磁盘块的地址。索引块的最后一个存储单元存储着指向下一个索引块的地址如果是小文件则这个指针为 nil，如果是大文件则指向了另一个索引块。
  • 多层索引（Multilevel index） ：设置两层索引块，第一层指向第二层，第二层指向文件块。根据最大文件大小的不同，可以继续到第三/四层。对于块大小为 4KB 的情况，可以在一个索引块里装入 1024 个 4B 指针，两层索引就可以容纳 1048 576 个数据块，即最大文件为 4GB。
  • 组合方案（Combined scheme） ：在 UFS 中使用了这种方案。将索引块的前 15 个指针存在文件的 inode 里，这 15 个指针中：前 12 个直接指向了数据块，这样不超过 12 块的文件就不需要其它索引块；后 3 个指针分别是一级间接块、二级间接块、三级间接块指针。这种方法允许一个文件的块数超过 4B 文件指针能访问的空间。许多 UNIX 系统支持 64 位文件指针，这时允许文件/文件系统达到数 T 字节。UNIX 的inode 大致如下：
    
• 索引分配方案和链接分配方案在性能上都有欠缺，虽然索引块能够缓存在内存里，但数据块会分布到整个分区中。

性能

• 连续分配对于任意类型的访问都只需要访问一次，链接分配可以将下一块的地址放到内存中并能直接读取，但对于直接访问需要读多次磁盘。所以有些系统通过使用连续分配支持文件直接访问，通过链接分配支持顺序访问。这种系统在创建文件时就要指明文件的类型（顺序访问还是直接访问），如果是直接访问还必须说明最大文件大小。
• 索引分配非常复杂。如果索引块已在内存中则可以直接访问，但将索引块保存在内存中需要非常大的空间。尤其是多级索引，对于一个大文件来说，如果要访问文件末尾部分的数据，可能需要将所有索引块读入内存才能读到需要的数据库。所以索引分配的性能依赖于索引结构、文件大小和所需要的块的位置。
• 有的系统把连续分配和索引分配结合，对于小文件（3、4块大小的）采用连续分配，大文件切换到索引分配。因为文件系统中大多数文件较小，所以小文件连续分配效率较高，平均性能较好。
• 由于 CPU 和磁盘速度不等，花费数千条 CPU 指令来节省一些磁头移动都是值得的，随着时间推移，这种不等程度还会增加。

空闲空间管理

• 系统需要维护 空闲空间链表（free-space list） 以记录空闲磁盘空间，创建文件时会从空闲空间链表分配，删除文件时磁盘空间会加回到空闲空间链表上（称之为链表但不一定表现为链表）。

位向量

• 将空闲空间用 位图（bit map） 或 位向量（bit vector） 表示，每块用一位说明是否为空闲，1 表示空闲，0 表示已经分配。
• 此方式查找磁盘上第 1 个空闲块和 n 个连续空闲块时简单高效：
  • 按顺序检查位图中的每个字是否为 0 即可确定对应的块是否已经全部分配，第一个非 0 的字中，第一个 1 位偏移旧对应着第一个空闲块；
  • 连续 n 个空闲块只需要判断是否有连续 [n / 字的位数] 个字均为最大值（如一个字就是一个字节时，只要连续有 [n / 8] 个字节全为 255 就说明这部分块都空闲）。
• 除非整个位向量都能保存在内存中，否则位向量的效率不高。对于小磁盘，位向量的大小可以接受，但对于大磁盘而言（如 40GB，每块 1KB）就需要超过 5MB 空间存储位图。

链表和组

• 将所有空闲磁盘块用 链表（Linked List） 链接，将指向第一个空闲块的指针放在磁盘的一个特殊位置，同时也缓存到内存里。第一块空闲块中包含了指向下一个空闲磁盘块的指针。
• 此方案效率不高，要遍历整个空闲块列表需要从磁盘读出每一块，这要耗费大量 I/O 时间。不过通常操作系统只需要获得一个空闲块以提供给文件，因此一般只需要分配空闲表的第一块。
• 组（grouping） 是对空闲链表的改进：将 n 个空闲块的地址存在第一个空闲块里，前 n-1 个地址都指向真正的空闲块， 最后一个地址指向了另一个包含另外 n 个空闲块的块地址 。

计数

• 通常会有多个连续的块需要同时分配、释放，尤其是采用了连续分配或簇的情况下。因此可以不记录 n 个空闲块地址，而是记录连续多块空闲块的第一块的地址，以及连续的空闲块的数量。这样空闲空间表的每个条目包含了第一个空闲块地址和连续空闲块数量，虽然每个条目占用的空间增长了，但表的总长度会缩短（连续空闲块的数量往往大于 1）。

UNIX 成组链接（补充）

• 将文件存储设备中的所有的空闲块 从后向前 按 50 块为一组进行划分，每组的第一块用于存放 前一组 的总块数和每块的块号，因为第一组前面已经没有其他组存在，所以第一组实际有 49 块。因为存储空间不一定正好是 50 的整数倍，所以最后一组可能不足 50 块。因为最后一组后面没有其他组，所以最后一组的总块数和每块块号的信息存放到管理文件存储设备的文件资源表中。如下图所示。
  
• 操作系统启动时将文件资源表复制到内存，此时文件资源表中包含了最后一组的空闲块总数以及空闲块的块号。操作系统还会设置一个用于空闲块分配、回收的堆栈，堆栈存储着空闲块的块号，栈指针 ptr 的初值等于最后一组的空闲块的总块数。
• 成组链接分配方法：申请者请求获得 n 块空闲块，操作系统将按照先进先出的原则，将栈顶指向的块号分配给请求者，同时 ptr 自减。重复此操作直到 n 块分配完毕，或者堆栈中只剩下最后一个空闲块的块号（此块实际存储的是下一组的空闲块块数和各块块号）。当堆栈只剩下最后一个空闲块的块号时：
  • 从堆栈中弹出该块的块号，系统启动 I/O 设备，将该块存放的内容读入内存（即将下一组空闲块号和总块数读入空闲资源表），并设置 ptr 为下一组的空闲块数
  • 文件存储设备的最后一个空闲块中设置有尾部标识，表示空闲块已经分配完毕
• 成组链接回收方法：用户删除某个文件时，ptr 自增并将空闲块号入栈。若 ptr 为 50 则表明当前已经凑足一组，该组回收结束。
  • 如果还有空闲物理块 F 需要回收，则将块 F 回收，并且启动设备 I/O，把栈中记录的 50 个块号和块数（50）写入到块 F 中。设置 ptr 为 1，将块 F 的块号入栈，开始新的一组空闲块回收。
  • 对空闲块的分配和回收操作必须互斥进行（栈操作要互斥）。

专栏目录：计算机理论基础
此专栏的上一篇文章：操作系统（十）：文件系统接口
此专栏的下一篇文章：操作系统（十二）：大容量存储器结构

参考资料：《操作系统概念 英文第七版》，恐龙书，英文名《Operating System Concepts》，作者 Abraham Silberschatz、Peter Baer Galvin、Greg Gagne

原创作品，允许转载，转载时无需告知，但请务必以超链接形式标明文章原始出处(http://blog.forec.cn/2017/01/05/os-concepts-11/) 、作者信息（Forec）和本声明。