文件是由大量性质相同的记录组成的集合1，其中每一个记录由一个或多个数据项组成，数据项是数据的基本单位(数据项又称为域)，在同一个记录中各个数据项可取不同的数据类型。文件扩充空间是指一个文件动态扩充已经超出了系统分配给它的空间，需要系统再给文件分配存储空间。文件扩充空间的原因有很多，例如数据动态增长；文件合并等。文件扩充空间一般与外存分配方式和文件存储空间有关。

由于磁盘具有可直接访问的特性，故当利用磁盘来存放文件时，具有很大的灵活性。在为文件分配外存空间时所要考虑的主要问题是：怎样才能有效地利用外存空间和如何提高对文件的访问速度。目前，常用的外存分配方法有连续分配、链接分配和索引分配三种。通常，在一个系统中，仅采用其中的一种方法来为文件分配外存空间2。

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

文件的连续分配可以用第一块的磁盘地址和连续块的数量来定义。如果文件有n块长并从位置b开始，那么该文件将占有b，b+1，b+2……b+n-1.一个文件的目录条目包括开始块的地址和该文件所分配区域的长度。

连续分配支持顺序访问和直接访问。其优点是实现简单、存取速度快。缺点在于，文件长度不宜动态增加，因为一个文件末尾后的盘块可能已经分配给其他文件，一旦需要增加，就需要大量移动盘块。此外，反复增删文件后会产生外部碎片（与内存管理分配方式中的碎片相似），并且很难确定一个文件需要的空间大小，因而只适用于长度固定的文件。

链接分配解决了连续分配的碎片和文件大小问题。采用链接分配，每个文件对应一个磁盘块的链表；磁盘块分布在磁盘的任何地方，除最后一个盘块外，每个盘块都有指向下一个盘块的指针，这些指针对用户是透明的。目录包括文件第一块的指针和最后一块的指针。

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

链接分配方式没有外部碎片，空闲空间列表上的任何块都可以用来满足请求。创建文件时并不需要说明文件大小。只要有空闲块文件就可以增大，也无需合并磁盘空间。

链接分配的缺点在于无法直接访问盘块，只能通过指针顺序访问文件，以及盘块指针消耗了一定的存储空间。链接分配方式的稳定性也是一个问题。系统在运行过程中由于软件或者硬件错误导致链表中的指针丢失或损坏，会导致文件数据的丢失。

连接分配解决了连续分配的外部碎片和文件大小管理的问题。但是，链接分配不能有效支持直接访问（FAT除外）。索引分配解决了这个问题，他把每个文件的所有的盘块号都集中在一起构成索引块。

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

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

链接方案：一个索引块通常为一个磁盘块，因此，他本身能直接读写。为了处理大文件，可以将多个索引块链接起来。

多层索引：多层索引使第一层索引块指向第二层的索引块，第二层的索引块再指向文件块。这种方法根据最大文件的大小的要求，可以继续到第三层或第四层。例如，4096B的块，能在索引块中存入1024个4B的指针。两层索引允许1048576个数据块，即允许最大文件为4G。

混合索引：将多种索引分配方式相结合的分配方式。例如，系统即采用直接地址，又采用单级索引分配方式或两级索引分配方式。

此外，访问文件需要两次访问外存——手想要读取索引块的内容，然后在访问具体的磁盘块，因而降低了文件的存取速度。为了解决这一问题，通常将文件的索引块读入内存的缓冲区，以加快文件的访问速度。

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

空闲盘区的分配与内存的动态分配类似，同样是采用首次适应算法、循环首次适应算法等。例如，在系统为某新创建的文件分配空闲盘块时，先顺序地检索空闲表的各表项，直至找到第一个其大小能满足要求的空闲区，再将该盘区分配给用户(进程)，同时修改空闲表。系统在对用户所释放的存储空间进行回收时，也采取类似于内存回收的方法，即要考虑回收区是否与空闲表中插入点的前区和后区相邻接，对相邻接者应予以合并。[1]

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

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

(2)空闲盘区链。这是将磁盘上的所有空闲盘区(每个盘区可包含若干个盘块)拉成一条链。在每个盘区上除含有用于指示下一个空闲盘区的指针外，还应有能指明本盘区大小(盘块数)的信息。分配盘区的方法与内存的动态分区分配类似，通常采用首次适应算法。在回收盘区时，同样也要将回收区与相邻接的空闲盘区相合并。在采用首次适应算法时，为了提高对空闲盘区的检索速度，可以采用显式链接方法，亦即，在内存中为空闲盘区建立一张链表。

位示图是利用二进制的一位来表示磁盘中一个盘块的使用情况。当其值为“0”时，表示对应的盘块空闲；为“1”时，表示已分配。有的系统把“0”作为盘块已分配的标志，把“1”作为空闲标志。(它们在本质上是相同的，都是用一位的两种状态来标志空闲和已分配两种情况。)磁盘上的所有盘块都有一个二进制位与之对应，这样，由所有盘块所对应的位构成一个集合，称为位示图。通常可用 m × n 个位数来构成位示图，并使 m × n 等于磁盘的总块数。

位示图也可描述为一个二维数组 map：

Var map: array of bit；