[科普中国]-文件空间分配

连续分配

连续分配(continuous allocation)要求为每一个文件分配一组相邻接的盘块。若物理块的大小为2 K，则50 K的文件需要分配25个连续的物理块，其地址是线性的。例如，第一个盘块的地址为b，则第二个盘块的地址为b+l，第三个盘块的地址为b+2……。通常，它们都位于一条磁道上，在进行读/写时不必移动磁头。仅当访问到一条磁道的最末一个盘块时，才需要移到下一条磁道，于是又去连续地读/写多个盘块。为使系统能找到文件存放的地址，应在目录项的“文件物理地址”字段中，记录该文件第一个记录所在的盘块号和文件长度(以盘块进行计量)。

在采用连续分配方式时，可把逻辑文件中的记录顺序地存储到邻接的各物理盘块中，这样形成的物理文件称为顺序文件。这种分配方式保证了逻辑文件中的记录顺序与存储器中文件占用盘块的顺序的一致性。如同内存的动态分区分配一样，随着文件空间的分配和文件删除时的收回，将使磁盘空间被分割成许多小块，这些较小的连续区已难于用来存储文件，称为外部碎片。同样，也可利用紧凑的方法，来将盘上所有的文件紧靠在一起，使所有的碎片拼接成一大片连续的存储空间。例如，可以运行磁盘整理程序，使之成为一个连续的存储空间，从而消除了外部碎片。但是将外存上的空闲空间进行一次紧凑所花费的时间，远比将内存紧凑一次所花费的时间多得多。

连续分配的主要优点如下：

(1)顺序访问容易。访问一个占有连续空间的文件非常容易。系统可从目录中找到该顺序文件所在的第一个盘块号，从此开始顺序地、逐个盘块地往下读/写。连续分配也支持直接存取。例如，要访问一个从b块开始存放的文件中的第i个盘块内容，就可直接访问b+i号盘块。

(2)顺序访问速度快。因为由连续分配所装入的文件，其所占用的盘块可能是位于一条或几条相邻的磁道上。这时，磁头的移动距离最少。因此，用这种方法对文件访问，其速度是几种存储空间分配方式中最高的一种。

连续分配的主要缺点是：

(1)要求有连续的存储空间。要为每一个文件分配一段连续的存储空间。因此，便会产生出许多外部碎片，严重地降低了外存空间的利用率。如果是定期地利用紧凑的方法来消除碎片，则又需花费大量的机器时间。

(2)必须事先知道文件的长度。要将一个文件装入到一个连续的存储区中，必须事先知道文件的大小，然后根据其大小，在存储空间中找出一块大小足够的存储区，将文件装入。在有些情况下，知道文件的大小是件非常容易的事，如拷贝一个已存文件。但有时却很难，只能靠估算。如果估计的文件大小比实际文件小。就可能因存储空间不足而中止文件的拷贝，需再要求用户重新估算，然后再次执行。这样，既费时又麻烦。这就使用户往往将文件长度估得比实际要大，甚至使所计算的文件长度比实际长度大得多，这严重地浪费了外存空间。对于那些动态增长的文件，虽然开始时文件很小，但在运行中逐渐增大。比如，这种增长要经历几天、几个月。在此情况下，即使事先知道文件的最终大小，采用预分配存储空间的方法，显然也将是很低效的，而且它使大量的存储空间长期地空闲。

链接分配如同内存管理一样，连续分配所存在的问题在于：必须为一个文件分配连续的磁盘空间。如果将一个逻辑文件存储到外存上时，并不要求为整个文件分配一块连续的空间，而是可以将文件装到多个离散的盘块中，这样就可以消除上述的缺点。在采用链接分配(linked allocation)方式时，可通过在每个盘块上的链接指针，将同属于一个文件的多个离散的盘块链接成一个链表，由此所形成的物理文件称为链接文件。

由于链接分配采取了离散分配方式，从而消除了外部碎片，故可显著地提高外存空间的利用率，而且也无需事先知道文件的长度，只是根据文件的当前需要，为它分配必需的盘块。当文件动态增长时，可动态地再为它分配盘块。此外，对文件的增、删、改也十分方便。

链接方式又可分为隐式链接和显式链接两种。

隐式链接在采用隐式链接分配方式时，在文件目录的每个目录项中，都需含有指向链接文件第一个盘块和最后一个盘块的指针。隐式链接分配方式的主要问题是：它只适合于顺序访问，对于随机访问是极其低效的。如果要访问文件所在的第i个盘块，就必须先读出文件的第一个盘块，从中得到其第二个盘块的盘块号，然后再读出第二个盘块，从中得到其第三个盘块的盘块号……，就这样顺序地查找直至第i块。当i=100时，就需启动磁盘100次去实现读盘块的操作，平均每次都要花费几十毫秒。可见，随机访问是非常耗时的。此外，只通过链接指针来将一大批离散的盘块链接起来，其可靠性较差，因为只要其中的任何一个指针出现问题，都会导致整个链的断开。

为提高检索速度和减小指针所占用的存储空间，可以将几个盘块组成一个簇(cluster)。比如，一个簇可包含4个盘块，在进行盘块分配时是以簇为单位的，像FAT文件系统盘块的分配就是以簇为单位的。这样将会成倍地减小查找指定块的时间，而且也可减小指针所占用的存储空间。但缺点是增大了内部碎片，而且这种改进也是非常有限的。

显式链接显示链接是指把链接文件各物理块的指针，显式地存放在内存的一张链接表中。该表是整个磁盘仅有的一张表，表的序号是物理盘块号，从0开始直至N一1，N为盘块总数。在每个表项中，存放链接指针，即下一个盘块号。在该表中，凡是属于某一文件的第一个盘块号，或说是每一个链的链首指针所对应的盘块号，均作为文件地址被填入相应文件的

FCB的“物理地址”字段中。由于查找记录的过程是在内存中进行的，因而不仅显著地提高了检索速度，而且大大减少了访问磁盘的次数。由于分配给文件的所有盘块号都放在该表中，故把该表称为文件分配表FAT(File Allocation Table)，MS-DOS及OS/2等操作系统都采用FAT。

链接分配方式虽然解决了连续分配方式所存在的问题，但又出现另外两个问题：

(1)不能支持高效的直接存取。要对一个较大的文件进行直接存取，需要首先在FAT中顺序地查找许多盘块号。

(2)FAT需占用较大的内存空间。由于一个文件所占用盘块的盘块号是随机地分布在FAT中的，因而只有将整个FAT调入内存，才能保证在FAT中找到一个文件的盘块号。当磁盘容量较大时，比如几百MB以上，FAT可能要占用数百KB以上的内存空间。1

索引分配链接分配文件存在不少缺点。首先，当要求随机访问文件上一个记录时，需要按链指针进行查找，这是十分缓慢的操作。其次，链指针要占用盘块空间的几个字节，这使得盘块的可用空间大小已不再是2的幂。这就使得这些盘块无法在要求是2的幂的大小的情况下使用。索引分配文件没有这些缺点。

在索引分配方法中，系统在文件分配表(FAT)中为每一个文件分配一个表目，指出该文件的索引表所在的物理块。索引表所在块并不是物理地属于文件分配表中所指出的分给文件的磁盘块之一，索引块是与文件盘块分离的(实际上索引表物理块是由文件目录中的文件属性指出的)。文件索引表的每个表目对应分给文件的每一个物理块。索引表通常是以文件的逻辑块号为索引的，但必要时也可以以记录中的关键字值为索引。

如果对索引表增加一个长度域，用以指出每个索引表目相应分区的起始块和长度。那么这种方法就支持索引分配和变长连续分配的结合(也可以说支持变长分区索引分配)，这将节省索引表空间，有助于提高效率。