一、文件的物理结构

文件实际上是一种抽象数据类型，我们要研究它的逻辑结构、物理结构，以及关于它的一系列操作。文件的物理结构就是研究文件的实现，即文件数据在物理存储设备上是如何分布和组织的。同一个问题有两个方面的回答：一是文件的分配方式，讲的是对磁盘非空闲块的管理；二是文件存储空间管理，讲的是对磁盘空闲块的管理。

文件分配对应于文件的物理结构，是指如何为文件分配磁盘块。常用的磁盘空间分配方法有三种：连续分配、链接分配和索引分配。有的系统（如 RDOS 操作系统）对三种方法都支持，但更普遍的是一个系统只支持一种方法。

先了解一下文件块和磁盘块：

磁盘块：

文件块：

1. 连续分配

连续分配方法要求每个文件在磁盘上占有一组连续的块，如下图所示。磁盘地址定义了磁盘上的一个线性排序，这种排序使作业访间磁盘时需要的寻道数和寻道时间最小。

【优点】：

① 支持顺序访问和直接访问（即随机访问）。

② 实现简单、存取速度快。

③ 连续分配的文件在顺序访问（读 / 写）时速度最快。

读取某个磁盘块时，需要移动磁头。访问的两个磁盘块相隔越远，移动磁头所需时间就越长。

【缺点】：

① 文件长度不宜动态增加，即物理上采用连续分配的文件不方便拓展，因为一个文件末尾后的盘块可能已分配给其他文件，一旦需要增加，就需要大量移动盘块。

若此时文件 A 要拓展，需要再增加一个磁盘块（假设总共需要 4 个磁盘块）。由于采用连续结构，所以文件 A 占用的磁盘块必须是连续的，因此只能将文件 A 全部 “迁移” 到有连续的 4 个磁盘块的区域。

② 为保持文件的有序性，删除和插入记录时，需要对相邻的记录做物理上的移动，还会动态改变文件的长度。

③ 存储空间利用率低，反复增删文件后会产生外部碎片（与内存管理分配方式中的碎片相似）。

物理上采用连续分配，存储空间利用率低，会产生难以利用的磁盘碎片，可以用紧凑来处理碎片，但是需要耗费很大的时间代价。

④ 很难确定一个文件需要的空间大小，因而只适用于长度固定的文件。

2. 链接分配

链接分配是一种采用离散分配的方式。它消除了磁盘的外部碎片，提高了磁盘的利用率。可以动态地为文件分配离散的磁盘块，因此无须事先知道文件的大小。此外，对文件的插入、删除和修改也非常方便。链接分配又可分为隐式链接和显式链接两种形式。

1）隐式链接

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

【优点】：

① 采用隐式链接的链接分配方式，很方便文件拓展。（若此时要拓展文件，则可以随便找一个空闲磁盘块，挂到文件的磁盘块链尾，并修改文件的 FCB）

② 所有的空闲磁盘块都可以被利用，不会有碎片问题，外存利用率高。

【缺点】：

① 只适合顺序访问，不支持随机访问。若要访问文件的第 i 个盘块，则只能从第 1 个盘块开始通过盘块指针顺序查找到第 i 块，随机访问效率很低。

② 隐式链接的稳定性也是一个问题，系统在运行过程中由于软件或硬件错误导致链表中的指针丢失或损坏，会导致文件数据的丢失。

③ 指向下一个盘块的指针也需要耗费少量的存储空间。

通常的解决方案是，将几个盘块组成簇（cluster），按簇而不按块来分配，可以成倍地减少查找时间。比如一簇为 4 块，这样，指针所占的磁盘空间比例也要小得多。这种方法的代价是增加了内部碎片。簇可以改善许多算法的磁盘访问时间，因此应用于大多数操作系统。

注意：考试题目中遇到未指明隐式/显式的 “链接分配” ，默认指的是隐式链接的链接分配。

2）显式链接

显式链接是指把用于链接文件各物理块的指针，从每个物理块的末尾中提取出来，显式地存放在内存的一张链接表中。该表在整个磁盘中仅设置一张，称为文件分配表（File Allocation Table, FAT）。

每个表项中存放链接指针，即下一个盘块号。文件的第一个盘块号记录在目录项 “物理地址” 字段中，后续的盘块可通过查 FAT 找到。

不难看出，文件分配表 FAT 的表项与全部磁盘块一一对应，并且可以用一个特殊的数字 -1 表示文件的最后一块，可以用 -2 表示这个磁盘块是空闲的（当然也可指定为 -3 ，-4）。因此，FAT 不仅记录了文件各块之间的先后链接关系，同时还标记了空闲的磁盘块，操作系统也可以通过 FAT 对文件存储空间进行管理。当某进程请求操作系统分配一个磁盘块时，操作系统只需从 FAT 中找到 -2 的表项，并将对应的磁盘块分配给进程即可。

【优点】：

① 显式链接也不会产生外部碎片，也可以很方便地对文件进行拓展，外存利用率高。

② 采用链式分配（显式链接）方式的文件，支持顺序访问，也支持随机访问（想访问 i 号逻辑块时，并不需要依次访问之前的 0 ~ i-1 号逻辑块）。

③ FAT 表在系统启动时就会被读入内存，因此查找记录的过程是在内存中进行的（块号转换的过程不需要访问磁盘），因而不仅显著地提高了检索速度，而且明显减少了访问磁盘的次数。相比于隐式链接来说，访问速度快很多。

【缺点】：文件分配表的需要占用一定的存储空间。

3. 索引分配

链接分配解决了连续分配的外部碎片和文件大小管理的问题。但依然存在问题：① 链接分配不能有效支持直接访问（FAT 除外）；② FAT 需要占用较大的内存空间。

事实上，在打开某个文件时，只需将该文件对应盘块的编号调入内存即可，完全没有必要将整个 FAT 调入内存。为此，索引分配将每个文件所有的盘块号都集中放在一起构成索引块（表），如下图所示。

索引分配允许文件离散地分配在各个磁盘块中，系统会为每个文件建立一张索引表，索引表中记录了文件的各个逻辑块对应的物理块（索引表的功能类似于内存管理中的页表——建立逻辑页面到物理页之间的映射关系）。索引表存放的磁盘块称为索引块。文件数据存放的磁盘块称为数据块。

【优点】：支持直接访问，且没有外部碎片问题。

每个文件都有其索引块，这是一个磁盘块地址的数组。索引块的第 i 个条目指向文件的第 i 个块。要读第 i 块，通过索引块的第 i 个条目的指针来查找和读入所需的块。可见，索引分配方式可以支持随机访问。文件拓展也很容易实现（只需要给文件分配一个空闲块，并增加一个索引表项即可）。

【缺点】：是由于索引块的分配，增加了系统存储空间的开销（索引表需要占用一定的存储空间）。

索引块的大小是一个重要的问题，每个文件必须有一个索引块，因此索引块应尽可能小，但索引块太小就无法支持大文件。可以采用以下机制来处理这个问题：

1）链接方案

一个索引块通常为一个磁盘块，因此它本身能直接读写。如果索引表太大，一个索引块装不下，那么可以将多个索引块链接起来存放。

缺点：多个索引块链接起来后，想要找到 i 号索引块，必须先依次读入 0~i-1 号索引块，这就导致磁盘 I/O次数过多，查找效率低下。

2）多层索引

多层索引（原理类似于多级页表）通过第一级索引块指向一组第二级的索引块，第二级索引块再指向文件块。查找时，通过第一级索引查找第二级索引，再采用这个第二级索引查找所需数据块。这种方法根据最大文件大小，可以继续建立第三层、第四层索引块。

结论：采用 K 层索引结构，且顶级索引表未调入内存，则访问一个数据块需要 K+1 次读磁盘操作。

缺点：即使是小文件，访问一个数据块依然需要 K+1 次读磁盘。

3）混合索引

将多种索引分配方式相结合的分配方式。例如，一个文件的顶级索引表中，既包含直接地址索引（直接指向数据块），又包含一级间接索引（指向单层索引表）、还包含两级间接索引（指向两层索引表） 。

优点：对于小文件来说，访问一个数据块所需的读磁盘次数更少。

此外，访问文件需两次访问外存，先读取索引块的内容，然后访问具体的磁盘块，因而降低了文件的存取速度。为了解决这一问题，通常将文件的索引块读入内存，以提高访问速度。

4）总结

	概念	目录项内容	优点	缺点
顺序分配	为文件分配的必须是连续的磁盘块	起始块号、文件长度	顺序存取速度快，支持随机访问	会产生碎片，不利于文件拓展
隐式链接	除文件的最后一个盘块之外，每个盘块中都存有指向下一个盘块的指针	起始块号、结束块号	可解决碎片问题，外存利用率高，文件拓展实现方便	只能顺序访问，不能随机访问
显式链接	建立一张文件分配表(FAT)，显式记录盘块的先后关系(开机后FAT常驻内存)	起始块号	除了拥有隐式链接的优点之外，还可通过查询内存中的FAT实现随机访问	FAT需要占用一定的存储空间
索引分配	为文件数据块建立索引表。若文件太大，可采用链接方案、多层索引、混合索引	链接方案记录的是第一个索引块的块号，多层/混合索引记录的是顶级索引块的块号	支持随机访问，易于实现文件的拓展	索引表需占用一定的存储空间。访问数据块前需要先读入索引块。若采用链接方案，查找索引块时可能需要很多次读磁盘操作

重要考点：

① 要会根据多层索引、混合索引的结构计算出文件的最大长度。
（Key：各级索引表最大不能超过一个块）

② 要能自己分析访问某个数据块所需要的读磁盘次数。
（Key：FCB 中会存有指向顶级索引块的指针，因此可以根据 FCB 读入顶级索引块。每次读入下一级的索引块都需要一次读磁盘操作。另外，要注意题目条件——顶级索引块是否已调入内存）

随机访问的概念：

二、文件存储空间管理（外存空闲空间管理）

【总结】：

一个存储设备可以按整体用于文件系统，也可以细分。例如，一个磁盘可以划分为 4 个分区，每个分区都可以有单独的文件系统。包含文件系统的分区通常称为卷（volume）。卷可以是磁盘的一部分，也可以是整个磁盘，还可以是多个磁盘组成 RAID 集，如下图所示。

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

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

1. 空闲表法

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

2. 空闲链表法

将所有空闲盘区拉成一条空闲链。根据构成链所用基本元素的不同，分为两种形式：

1）空闲盘块链

将磁盘上的所有空闲空间以盘块为单位拉成一条链。当用户因创建文件而请求分配存储空间时，系统从链首开始，依次摘下适当数目的空闲盘块分配给用户。当用户因删除文件而释放存储空间时，系统将回收的盘块依次插入空闲盘块链的末尾。

这种方法的优点是分配和回收一个盘块的过程非常简单，但在为一个文件分配盘块时可能要重复操作多次， 效率较低。又因它是以盘块为单位的，空闲盘块链会很长。

2）空闲盘区链

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

这种方法的优缺点刚好与第一种方法的相反，即分配与回收的过程比较复杂，但效率通常较高，且空闲盘区链较短。

3. 位示图法

位示图法属于连续分配、离散分配都适用的方式。位示图是利用二进制的一位来表示磁盘中一个盘块的使用情况，磁盘上所有的盘块都有一个二进制位与之对应。当其值为 “0” 时，表示对应的盘块空闲；为 “1” 时，表示已分配。这样，一个 m×n 位组成的位示图就可用来表示 m×n 个盘块的使用清况，如下图所示。

位示图一般用连续的 “字” 来表示，如上图中一个字的字长是 16 位，字中的每一位对应一个盘块。因此可以用（字号，位号）对应一个盘块号。（字号，位号）也可描述为（行号，列号）。

1）盘块的分配

假设盘块号、字号（行号）、位号（列号）均从 1 开始，n 表示字长。

• 顺序扫描位示图，从中找出一个或一组其值为 “0” 的二进制位。

• 将找到的一个或一组二进制位，转换成与之对应的盘块号。若找到的其值为 “0” 的二进制位位于位示图的第 i 行、第 j 列，则其相应的盘块号应按下式计算（n 为每行位数）：b = n × (i - 1) + j 。

• 修改位示图，令 map[i, j] = 1 。

2）盘块的回收

假设盘块号、字号（行号）、位号（列号）均从 1 开始，n 表示字长。

• 将回收盘块的盘块号转换成位示图中的行号和列号。转换公式为：i = (b - 1) / n + 1 ；j = (b - 1) MOD n + 1 。

• 修改位示图，令 map[i, j] = 0 。

4. 成组链接法

空闲表法和空闲链表法都不适用于大型文件系统，因为这会使空闲表或空闲链表太大。在 UNIX 系统中采用的是成组链接法对磁盘空闲块进行管理，这种方法结合了空闲表和空闲链表两种方法，它具有上述两种方法的优点，克服了两种方法均有的表太长的缺点。

先来介绍 “超级块” 的概念：文件卷的目录区中专门用一个磁盘块作为 “超级块” ，当系统启动时需要将超级块预先读入系统空闲的主存，并且要保证内存与外存中的 “超级块” 数据一致。

用来存放一组空闲盘块号（空闲盘块的块号）的盘块称为成组链块。成组链接法的大致思想是：把顺序的 n 个空闲盘块号保存在第一个成组链块中，其最后一个空闲盘块（作为成组链块）则用于保存另一组空闲盘块号，如此继续，直至所有空闲盘块均予以链接。系统只需保存指向第一个成组链块的指针。假设磁盘最初全为空闲盘块，其成组链接如下图所示。

1）盘块的分配

根据第一个成组链块的指针，将其对应的盘块分配给用户，然后将指针下移一格。若该指针指向的是最后一个盘块（即成组链块），由于该盘块记录的是下一组空闲盘块号，因此要将该盘块读入内存，并将指针指向新的成组链块的第一条记录，然后执行上述分配操作。

2）盘块的回收

成组链块的指针上移一格，再记入回收盘块号。当成组链块的链接数达到 n 时，表示已满，便将现有已记录 n 个空闲盘块号的成组链块号记入新回收的盘块（作为新的成组链块）。

三、小结

1、单个文件的逻辑结构和物理结构之间是否存在某些制约关系？

• 文件的逻辑结构是用户可见的结构，即从用户角度看到的文件的全貌。

• 文件的物理结构是文件在存储器上的组织结构，它表示一个文件在辅存上安置、链接、编目的方法，它和文件的存取方法以及存储设备的特性等都有着密切的联系。

单个文件的逻辑结构和物理结构之间虽无明显的制约或关联关系，但是如果物理结构选择不慎，也很难体现出逻辑结构的特点，比如一个逻辑结构是顺序结构，而物理结构是隐式链接结构的文件，即使理论上可以很快找出某条记录的地址，而实际找时仍然需要在磁盘上一块一块地找。

2、文件的物理分配方式的比较

文件的三种物理分配方式的比较如下表所示。

	访问第 n 条记录	优点	缺点
连续分配	需访问磁盘 1 次	顺序存取时速度快，文件定长时可根据文件起始地址及记录长度进行随机访问	文件存储要求连续的存储空间，会产生碎片，不利于文件的动态扩充
链接分配	需访问磁盘 n 次	可解决外存的碎片问题，提高外存空间的利用率，动态增长较方便	只能按照文件的指针链顺序访问，查找效率低，指针信息存放消耗外存空间
索引分配	m 级需访问磁盘 m+1 次	可以随机访问，文件易于增删	索引表增加存储空间的开销，索引表的查找策略对文件系统效率影响较大