简单了解文件系统的实现

文件系统由文件管理、被管理文件及实施文件管理所需的数据结构所组成，而文件系统的实现就是将文件通过合理的方式保存到存储空间中。

文件系统层次结构

现代操作系统有多种文件系统类型，它们的文件系统层次结构也不尽相同。下图展示了一种层次结构。

用户调用接口

文件系统为用户提供与文件及目录有关的调用，如新键、打开、读写、关闭、删除文件、建立、删除目录等。此层由若干程序模块组成，每个模块对应一条系统调用，用户发出系统调用时，控制即转入相应的模块。

文件目录系统

文件目录系统的主要功能是管理文件目录，其任务有管理活跃文件目录表、管理读写状态信息表、管理用户进程的打开文件表、管理与组织存储设备上的文件目录结构、调用下一级存取控制模块。

存储控制验证

实现文件保护主要由该级软件完成，它把用户的访问要求与文件控制块中指示的访问控制权限进行比较，以确认访问的合法性。

逻辑文件系统与文件信息缓冲区

逻辑文件系统与文件信息缓冲区的主要功能是，根据文件的逻辑结构将用户要读写的逻辑记录转换成文件逻辑结构内的相应块号。

物理文件系统

物理文件系统的主要功能是把逻辑记录所在的相对块号转换成实际的物理地址。

辅助分配模块

分配模块的主要功能是管理辅存空间，即负责分配辅存空闲空间和回收辅存空间。

设备管理程序模块

设备管理程序模块的主要功能是分配设备、分配设备读写用缓冲区、磁盘调度、启动设备、处理设备中断、释放设备读写缓冲区、释放设备等。

假设用户查看文件 F 中的内容，通过调用用户调用接口，向操作系统发出命令；操作系统得到命令后，通过文件目录系统，查找文件 F 的索引信息；通过目录找到文件控制块后，就查看文件控制块上的信息，使用存储控制验证模块查看用户是否有访问该文件的权限；通过验证后，操作系统通过逻辑文件系统与文件信息缓冲区得到相应文件的内容的逻辑地址，再通过物理文件系统把逻辑地址转换为物理地址；寻址完成后，之后要释放空间，则会将任务交给辅助分配模块，若要分配给设备用户输入输出时，则把任务交给设备管理程序模块。

目录实现

在读文件前，必须先打开文件。打开文件时，操作系统利用路径名找到相应目录项，目录项中提供了查找文件磁盘块所需的信息。目录实现的基本方法有线性列表和哈希表两种，要注意目录的实现就是为了查找，因此线性列表实现对应线性查找，哈希表的实现对应散列查找。

线性列表

很简单的目录实现方法是使用存储文件名和数据块指针的线性表。创建新文件时，必须首先搜索目录表以确定没有同名的文件存在，然后在目录表后增加一个目录项。删除文件则根据给定的文件名搜索目录表，接着释放分配给它的空间。重用目录项有许多方法，可以将目录项标记为不再使用，或将它加到空闲目录项表上，还可以将目录表中的最后一个目录项复制到空闲位置，并降低目录表长度。采用链表结构可以减少删除文件的时间，其优点在于实现简单，不过由于线性表的特殊性，比较费时。

哈希表

哈希表根据文件名得到一个值，并返回一个指向线性列表中元素的指针。这种方法的优点是查找非常迅速，插入和删除也较简单，不过需要一些预备措施来避免冲突。最大的困难是哈希表长度固定以及哈希函数对表长的依赖性。

目录查询是通过在磁盘上反复搜索完成的，需要不断地进行 I/O 操作，开销较大。所以如前所述，为了减少 I/O 操作，把当前使用的文件目录复制到内存，以后要使用该文件时只需在内存中操作，因此降低了磁盘操作次数，提高了系统速度。

文件实现

文件是一种抽象数据类型，研究文件就要研究它的逻辑结构、物理结构以及文件的一系列操作。而文件的实现就是研究文件的物理结构，即文件数据在物理存储设备上是如何分布和组织的。

文件分配方式

文件分配对应于文件的物理结构，是指如何为文件分配磁盘块。常用的磁盘空间分配方法有连续分配、链接分配和索引分配三种分配。

连续分配

连续分配方法为每个文件在磁盘上分配一组连续的块，如下图所示。磁盘地址定义了磁盘上的一个线性排序，这种排序使作业访问磁盘时需要的寻道数和寻道时间最小。采用连续分配方式时，可把逻辑文件中的记录顺序地存储到邻接的各物理盘块中，所形成的文件结构称为顺序文件结构。

为使系统找到文件存放的地址，应在文件的目录条目中记录开始盘块号的地址和该文件以盘块为单位的文件长度。

连续分配支持顺序访问和直接访问，其优点是实现简单、访问速度快。缺点是文件长度不宜动态增加，因为增加文件长度时可能会大量移动文件末尾后已分配出去的盘块；删除时还会产生外部碎片，而且也很难确定一个文件需要的空间大小，因此只适用于长度固定的文件。

链接分配

链接分配采取离散分配的方式，将同属于一个文件的多个离散的盘块链接成一个链表，形成的物理文件称为链接文件。这样可消除外部碎片，提高磁盘空间利用率；根据文件当前需求为其分配所需盘块，适应动态增长。此外，插入、删除和修改也都非常容易。链接分配又分为隐式链接和显式链接两种形式。

隐式链接如下图所示。每个文件对应一个磁盘块的链表，磁盘块分布在磁盘的任何地方，除最后一个盘块外，每个盘块都有指向下一个盘块的指针。目录项中需包含文件第一个盘块的指针和最后一个盘块的指针。

创建新文件时，目录中增加一个新条目。每个目录项都有一个指向文件首块的指针。该指针初始化为 NULL
以表示空文件，大小字段为 0
。写文件会通过空闲空间管理系统找到空闲块，将该块链接到文件的尾部，以便写入。该文件则通过块到块的指针顺序读块。

隐式链接分配的缺点是无法直接访问盘块，只能通过指针顺序访问文件，且盘块指针会消耗一定的存储空间。此外，隐式链接分配通过指针链接各个离散的盘块，运行过程中出错导致链表中指针丢失或损坏，会导致文件数据丢失，稳定性较差。

显式链接是指把用于链接文件各物理块的指针，从物理块中取出，显式地存放在内存的一张链表中。该表在整个磁盘仅设置一张，每个表项中存放以对应盘块的下一个盘块的链接指针，如下图所示。

在该表中，凡属于某个文件的第一个盘块号，或每条链的链首地址所对应的盘块号，均作为文件地址被填入相应文件的文件控制块的物理地址字段。当某文件要查找当前盘块的下一个盘块地址时，只需找到链接表相应的位置，即可找到下一块的指针。由于查找记录的过程是在内存中进行，不仅显著地提高了检索速度，还减少了访问磁盘的次数。由于分配给文件的所有盘块号都放在该表中，故称该表为文件分配表（File Allocation Table，FAT)。

索引分配

索引分配是指把每个文件的所有盘块号都集中放在一起构成索引块或索引表的索引式文件结构，来解决链接分配不能有效支持直接访问的问题，如下图所示。

每个文件都有其索引块，这是一个磁盘块地址的数组。索引块的第 i 个条目指向文件的第 i 个块。目录条目包括索引块的地址。要读第 i 块，通过索引块的第 i 个条目的指针来查找和读入所需的块。

创建文件时，索引块的所有指针都设为空，首次写入第 i 块时，先从空闲空间中取得一个块，再将其地址写到索引块的第 i 个条目。索引分配支持直接访问，且没有外部碎片问题。其缺点是由于索引块的分配，增加了系统存储空间的开销。索引块的大小是一个重要的问题，每个文件必须有一个索引块，因此索引块应尽可能小，但索引块太小就无法支持大文件。索引分配采用以下几种机制来解决。

• 链接索引。一个索引块通常为一个磁盘块，因此它本身能直接读写。为了处理大文件，可以将多个索引块链接起来。
• 多级索引。多级索引使第一级索引块指向第二级的索引块，第二级索引块再指向文件块。这种方法根据最大文件大小的要求，可以继续到第三级或第四级。例如，4096B 的块，能在索引块中存入 1024 个 4B 的指针。两级索引允许 1048576 个数据块，即允许最大文件为 4GB。
• 混合索引。将多种索引分配方式相结合的分配方式。例如，系统既采用直接地址，又采用单级索引分配方式或两级索引分配方式。

文件存储空间管理

一般来说，一个文件存储在一个文件卷中。文件卷可以是物理盘的一部分，也可以是整个物理盘，支持超大型文件的文件卷也可由多个物理盘组成，如下图所示。

在一个文件卷中，文件数据信息的空间（文件区）和存放文件控制信息的文件控制块的空间（目录区）是分离的。由于存在很多种类的文件表示和存放格式，所以现代操作系统中一般都有很多不同的文件管理模块，通过它们可以访问不同格式的逻辑卷中的文件。逻辑卷在提供文件服务前，必须由对应的文件程序进行初始化，划分好目录区和文件区，建立空闲空间管理表格及存放逻辑卷信息的超级快。

文件存储设备分成许多大小相同的物理块，并以块为单位交换信息，因此，文件存储设备的管理实质上是对空闲块的组织和管理，它包括空闲块的组织、分配与回收等问题。

空闲表法

空闲表法属于连续分配方式，它为每个文件分配一块连续的存储空间。即系统为外存上的所有空闲区建立一张空闲盘块表，每个空闲区对应于一个空闲表项，其中包括表项序号、该空闲区第一个盘块号、该区的空闲盘块数等信息。再将所有空闲区按其起始盘块号递增的次序排列，如下表所示。

空闲盘区的分配与内存的动态分配类似，同样采用首次适应算法和最佳适应算法等。在系统为某新创建的文件分配空闲盘块时，先顺序地检索空闲盘块表的各表项，直至找到第一个其大小能满足要求的空闲区，再将该盘区分配给用户，同时修改空闲盘块表。

系统在对用户所释放的存储空间进行回收时，也采取类似于内存回收的方法，即要考虑回收区是否与空闲表中插入点的前区和后区相邻接，对相邻接者应予以合并。

空闲链表法

空闲链表法是将所有空闲盘区拉成一条空闲链。根据构成链所用的基本元素不同，可把链表分成空闲盘块链和空闲盘区链两种形式。

空闲盘块链将磁盘上的所有空闲空间以盘块为单位拉成一条链，其中的每个盘块都有指向后继盘块的指针。当用户因创建文件而请求分配存储空间时，系统从链首开始，依次摘下适当数目的空闲盘块分配给用户。当用户因删除文件而释放存储空间时，系统将回收的盘块依次挂在空闲盘块链的末尾。优点是分配和回收一个盘块的过程非常简单，但为一个文件分配盘块时可能要重复多次操作。

空闲盘区链将磁盘上的所有空闲盘区拉成一条链，每个盘区可包含若干盘块。在每个盘区上除含有用于指示下一个空闲盘区的指针外，还应能有指明本盘区大小（盘块数）的信息。分配盘区的方法与内存的动态分区分配类似，通常采用首次适应算法。在回收盘区时，同样也要将回收区与相邻接的空闲盘区合并。

位示图法

位示图利用二进制的一位来表示磁盘中一个盘块的使用情况，磁盘上所有的盘块都有一个二进制位与之对应。值为0
时，表示对应的盘块空闲；值为1
时，表示对应的盘块已分配。位示图法示意如下图所示。

盘块的分配可分为三步，如下所示。

1. 顺序扫描位示图，从中找出一个或一组其值为 0
   的二进制位。
2. 将找到的一个或一组二进制位转换成与之对应的盘块号。其值为0
   的二进制位在第 i
   行  j
   列，相应盘块号为 ，其中n为每行位数。
3. 修改位示图，令 。

盘块的回收分为两步，如下所示。

1. 将回收盘块的盘块号转换成位示图中的行号和列号。行号为 ，列号为 。

2. 修改位示图，令 。

这种方法的主要优点是从位示图中很容易找到一个或一组相邻接的空闲盘块。例如，我们需要找到 6 个相邻接的空闲盘块，这只需在位示图中找出 6 个其值连续为0的位即可。此外，由于位示图很小，占用空闲小，因而可将它保存在内存中，进而使在每次进行盘区分配时，无需首先把盘区分配表读入内存，从而节省了许多磁盘的启动操作。因此，位示图常用于微型机和小型机中。

成组链接法

空闲表法和空闲链表法都不适用于大型文件系统，因为这会使空闲表或空闲链表太大。而成组链接法结合了空闲表和空闲链表两种方法，克服了表太大的缺点。

成组链接法是把顺序的 n 个空闲扇区地址保存在第一个空闲扇区内，其后一个空闲扇区内则保存另一顺序空闲扇区的地址，如此继续，直至所有空闲扇区均予以链接。系统只需要保存一个指向第一个空闲扇区的指针。假设磁盘最初全为空闲扇区，其成组链接如下图所示。通过这种方式可以迅速找到大批空闲块地址。

表示文件存储器空闲空间的位向量
表或第一个成组链块，以及卷中的目录区、文件区划分信息都需要存放在辅存储器中，一般放在卷头位置，Unix中称为超级块。在对卷中的文件进行操作前，超级块需要预先读入系统空闲的主存，并且经常保持主存超级块与辅存卷中超级块的一致性。