一、文件系统结构

磁盘提供大多数的外存，以便维护文件系统。磁盘在这方面有以下两个优势：

  • 磁盘可以原地重写。可以从磁盘上读取一块，修改该块，并写回原来的位置。
  • 磁盘可以直接访问所包含的任何信息块。因此，可以简单地按顺序或随机访问文件。从一个文件切换到另一个文件时只需要移动读写磁头，并等待磁盘旋转。

文件系统本身通常由许多不同的层块组成。如下图所示就是一个分层设计的例子。

OS

​ 每层利用更底层的功能创建新的功能，以用于更高层的服务。采用分层结构实现文件系统时，也可以最小化代码重复率。

二、文件系统操作

在存储上，文件系统一般包含以下一些结构：

  • （每个卷的）引导控制块：包含从该卷引导操作系统所需的所有信息。如果磁盘不包含操作系统，则该块为空，通常是卷的第一块。
  • （每个卷的）卷控制块：包含卷的详细信息。
  • （每个文件系统的）目录结构用于组织文件。
  • 每个文件的文件控制块（FCB）包括该文件的许多详细信息。它有唯一的标识号，以便与目录条目相关联。

内存中的信息用于管理文件系统并通过缓存来提高性能。这些结构的类型可能包括：

  • 内存中的安装表：包括每个安装卷的信息。
  • 内存中的目录结构的缓存含有最近访问目录的信息。
  • 整个系统的打开文件表：包括每个打开文件的 FCB 副本以及其他信息。
  • 对于进程已打开的所有文件，单个进程的打开文件表包括指针，指向整个系统的打开文件表中的适当条目以及其它信息。

下图总结了文件系统实现的操作结构。

OS

三、目录实现

3.1 线性列表

实现目录最简单的方法是采用文件名称和数据块指针的线性列表。这种方式简单但是费时。在创建，删除，查找文件时都需要线性搜索。即便使用排序列表可以利用二分搜索减少时间，但排序可能导致文件的创建和删除变得复杂。

3.2 哈希表

哈希表根据文件名称获得一个值，并返回指向线性列表内文件名称的一个指针。因此，哈希表大大减少了目录搜索的时间。但哈希表需要保证不同的文件对应的哈希函数值不一样，这并不容易。同时，对于已经固定的条目数大小进行调整时，必须重新组织现有目录条目，这非常麻烦。

四、分配方法

由于很多文件都存储在同一个设备上，因此，存在的主要问题是如何为这些文件分配空间，以便有效使用存储空间和快速访问文件。

4.1 连续分配

连续分配要求每个文件在设备上占有一组连续的块。这种分配方式不仅在寻道时所需的寻道时间最小，并且很容易实现访问，可以支持顺序访问和直接访问。

但它也有问题。当从一组空闲孔中寻找一个大小合适的空闲孔时，不管用什么方式寻找，都会有外部碎片产生。同时，文件的大小不能增加，必须提前知道一个文件需要多少空间，接着才能根据需要分配适当空间假如文件大小减小，又会产生内部碎片。

为了解决这些问题，有些操作系统使用了修正后的连续分配方案。当最初分配的空间不足时，会添加另一块连续空间，称为扩展。但实际上这种方法并不能很好地解决外部碎片和内部碎片问题。

4.2 链接分配

链接分配解决了连续分配的所有问题。采用链接分配时，每个文件都是存储块的链表，存储块可能散布在设备的任何地方。每一块都有下一块的一个指针。但链接分配也有缺点。主要问题时，它只能有效用于顺序访问文件，不能有效支持文件的直接访问。

这个问题的解决方案时使用多个块组成的簇，并按簇而不是块来分配。这样，指针所占空间的百分比就要小得多了，只不过代价是增加了内部碎片，可能浪费更多空间。

链接分配的一个变种是文件分配表（FAT）。每个卷的开头部分的磁盘用于存储该表。在该表中，每个块都有一个条目，并可按块号来索引。如果该块被使用了，则保存下一个块的地址；如果是结束块则保存文件结束值；如果未使用，则保存 0。目录条目包含文件首块的块号。接下来的使用过程与链表类似只不过，这样改善了随机访问的时间，因为通过读入 FAT 的信息，磁头能找到任何块的位置。

4.3 索引分配

为了解决链接分配不支持高效的直接访问这个问题，我们采用了索引分配这种策略，即使用索引块解决这个问题。

每个文件都有自己的索引块，这是一个磁盘块地址的数组。它的第 i 个条目指向第 i 个块。目录中则包含索引块的地址。

OS

虽然索引分配支持直接访问，并且不会有外部碎片问题。但仔细看来，这时比较浪费空间的。假如一个文件只有一两块，采用链接分配，每块只浪费一个指针的空间，但采用索引分配时，必须分配一个完整的索引块。

五、空闲空间管理

为了跟踪空闲磁盘空间，系统需要维护一个空闲空间列表。它记录了所有的空闲存储空间。尽管空闲空间列表被称为列表，但是不必按照列表来实现。

5.1 位向量

通常，空闲空间列表按位向量来实现。每一块用以为来表示。如果块是空闲的，位为 0；如果块是分配的，位为 1。

假设磁盘中的块 2、3、4、5、10、11 为空闲。则位图如下：001111000011000……

这种方法对于查找磁盘上的第 1 个空闲块，或是 n 个连续空闲块比较方便。比如寻找第一个值为 1 的位，它从头开始对于所有值为 0 的字，都可以直接跳过，直到第一个值为 1 的字，接着在这个字中找到哪一位为 1。综合而言就是：每个字的位数 * 值为0的字数 + 第一个值为1的位的偏移。

5.2 链表

另一种方法是将所有空闲块用链表连接起来，将指向第一个空闲块的指针保存在文件系统的特殊位置上，同时将其缓存在内存中。

5.3 组合

一种改进的方法是在第一个空闲块中存储 n 个空闲块的地址。这些块的前 n-1 个确实为空，最后一块包含另外 n 个空闲块的地址，如此继续。大量空闲块的地址可以很快找到。

5.4 计数

这种方法不是记录 n 个空闲块的地址，而是记录第一块的地址和紧跟第一块的连续空闲块的数量 n。这样，空闲空间列表的每个条目包括设备地址和数量。这样虽然每个条目的空间更大，但列表会变短很多。

六、效率和性能

存储空间的有效使用很大程度上取决于存储分配和目录算法。比如说：索引节点的分配以减少寻道时间；调整簇的大小；考虑保存在文件目录条目中的数据类型；指针大小的选择。