计算机操作系统中文件的物理结构及管理问题

文件的物理结构指逻辑文件在物理存储空间中的存储组织形式。这不仅与存储介质的存储性能有关，而且与所采用的存放方式有关。

由于磁盘具有可直接访问的特性，故当利用磁盘来存放文件时，具有很大的灵活性。在为文件分配外存空间时所要考虑的主要问题是，在磁盘上存储文件采用怎样的数据结构和如何提高对文件的访问速度。目前常用的存放方法有连续存放、链接方式和索引方式三种。采用不同的存放方式时，将形成不同的文件物理结构。例如，在采用连续存放方式时的文件物理结构，将是顺序式的文件结构；链接方式将形成链接式文件结构；而索引方式则将形成索引式文件结构。

7.3.1 顺序文件

将一个文件中逻辑上连续的信息存放到存储介质的依次相邻的块中便形成顺序结构，这类文件叫顺序文件，又称连续文件。显然，这是一种逻辑记录顺序和物理记录顺序完全一致的文件，通常记录按出现的次序被读出或修改，如图7-4所示是顺序文件示意图。

图7-4 顺序文件

如同内存的动态分区分配一样，随着文件建立时空间的分配和文件删除时空间的回收，将使磁盘空间被分割成许多小块，这些较小的连续区已难以用来存储文件，此即外存的碎片。同样也可以利用紧凑的方法，将盘上所有的文件紧靠在一起，把所有的碎片拼接成一大片连续的存储空间。

顺序文件的主要优点如下：

（1）顺序访问快速容易。访问一个占有连续空间的文件非常容易。系统可从目录中找到该顺序文件所在的第一个盘块号，从此开始顺序地、逐个盘块地往下读／写。另外，顺序文件占用的盘块可能是位于一条或几条相邻的磁道上，这时磁头的移动距离最少，这种对文件访问的速度是几种存储空间分配方式中最高的一种。因此大多数的系统文件采用了顺序文件形式存放在存储设备中。批处理文件也采用了顺序文件方式存储。

（2）随机访问容易。可以很容易地计算任一文件块的磁盘位置，例如，要访问一个从b块开始存放的文件中的第i个盘块的内容，就可直接访问b＋i号盘块。

顺序文件的主要缺点如下：

（1）造成外部碎片。顺序文件要为每一个文件分配一段连续的存储空间，这样当文件被删除，存储设备空间被回收并再次分配时，如果新进入的文件大小小于空闲的物理块数，会剩余一些物理块，产生许多外部“碎片”，严重地降低了外存空间的利用率。如果是定期利用紧凑方法来消除碎片，则又需要花费大量的机器时间。

（2）文件扩展困难。由于顺序文件分配在一个连续的存储区中，当文件逻辑结构中需要插入或修改记录，会引起文件物理结构中的物理块移动，会带来很多的管理问题。

7.3.2 链接文件

如同内存管理一样，连续分配所存在的问题就在于必须为一个文件分配连续的磁盘空间。如果在将一个逻辑文件存储到外存上时，并不要求为整个文件分配一块连续的空间，而是可以将文件装到多个离散的盘块中，这样也就可以消除上述缺点。因此将文件中的各个逻辑记录存放在不相邻的物理块中，通过物理块中的链接指针将它们连接在一起的文件形式称为链接文件。

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

在采用链接方式时，在文件目录的每个目录项中，都须含有指向链接文件第一个盘块和最后一个盘块的指针，没有文件大小，文件物理块之间通过链接指针连接在一起。

图7-5示出了一个链接式文件。该文件从第18号物理块开始存放，180号物理块结束，链接指针为18→19→36→39→55→130→180，共分配有7个物理块。在相应的目录项中，指示了其第一个盘块号是18，最后一个盘块号是180。而在每个盘块中都含有一个指向下一个盘块的指针，如在第一个盘块18中设置了第二个盘块的盘块号是19；在19号盘块中又设置了第三个盘块的盘块号36，以此类推。

图7-5 链接文件

图7-6 使用FAT的链表方式

链接文件优点在于没有磁盘碎片的空间浪费，文件的增长和收缩都比较容易。但是缺点在于它只适合于顺序访问，随机访问效率较低，如果要访问文件所在的第i个盘块，则必须先读出文件的第一个盘块，就这样顺序地查找直至第i块。当i＝50时，须启动50次磁盘去实现读盘块的操作；另外，链接指针信息的存放需要存储空间，使得存储器可利用空间减少，例如，链接文件中如果指针占用4个字节，对于盘块大小为512字节的磁盘，则每个盘块中只有508个字节可供用户使用。(www.xing528.com)

为了解决链接文件的上述问题，可以提取每个磁盘块中的指针内容，形成文件分配表（FAT），显式地存放在内存中，如图7-6所示。

表的序号是物理盘块号，从0开始，直至N－1；N为盘块总数。在每个表项中存放链接指针，即下一个盘块号。在该表中，凡是属于某一文件的第一个盘块号，或者说是每一条链的链首指针所对应的盘块号，均作为文件地址被填入相应文件的文件控制块（FCB）的“物理地址”字段中。由于查找记录的过程是在内存中进行的，因而不仅显著地提高了检索速度，而且大大减少了访问磁盘的次数。由于分配给文件的所有盘块号都放在该表中，故把该表称为文件分配表（file allocation table，FAT）。

7.3.3 索引文件

1.单级索引文件

无论是顺序文件还是链接文件，每次访问都要从文件逻辑记录的起始物理块开始进行，系统不能对某个文件物理块进行直接访问。

索引文件指文件中的各个记录可存储在不相邻的各个物理块中，系统为每个文件建立一张索引表，在索引表中为每个记录设置一个表项，存放该记录的记录号及其所在的物理块号，实现了逻辑记录和物理块之间的映射关系。在索引文件存储方式中，因为一个物理块对应一条逻辑记录，因此索引文件基本的前提条件是文件的逻辑记录大小等于文件物理块大小。在建立一个文件时，只需在为之建立的目录项中填上指向该索引块的指针。如图7-7所示为索引文件的示意图。

索引文件的优点是文件易于增长，只要文件的尺寸不超过索引头里面预留的指针数×磁盘数据块大小，文件增长十分方便；其次索引文件便于随机访问，当要读文件的第i个盘块时，可以方便地直接从索引块中找到第i个盘块的盘块号；此外，索引分配方式也不会产生外部碎片。

索引文件的缺点在于顺序访问效率不高，仍然需要读取索引表以此查找每个逻辑块对应的物理磁盘块；另外，如果数据块数超过索引头预留的指针数时，文件增长不容易。

图7-7 索引文件示意图

2.多级索引文件

当OS为一个大文件分配磁盘空间时，由于文件记录数目很多，索引表要占用更多的物理块，因此在查找某键对应的索引项时，可能依次需交换很多块。若索引表占用n块，则平均要交换（n＋1）／2次，才能找到所需记录的物理地址，当n很大时，这是很费时间的操作。为了解决这个问题，可以采用二级索引。即为这些索引块再建立一级索引，称为第一级索引，即系统再分配一个索引块，作为第一级索引的索引块，将第一块、第二块等索引块的盘块号填入到此索引表中，这样便形成了二级索引方式。当文件记录数目非常大时，还可以建立三级、四级索引文件。

在通常情况下，一个索引表中有1 024个索引项，则可以寻址1 024个物理块。如果一个物理块大小为1 024 B，则可以访问的文件长达1 MB。如果采用两级索引，每级索引表都有1 024个表项，一个物理块大小为1 024 B，则可以访问的文件长达1 G。目前，UNIX和Linux操作系统都采用了索引文件方式，如图7-8所示为二级索引文件。

3.非对称多级索引文件

大文件可以使用多级索引来实现，但是多级索引带来的问题是访问一个数据块需要的磁盘访问次数增加了，如当访问二级索引文件的某个数据块时，需要先访问一级索引表查找二级索引表的地址，再访问二级索引表查找磁盘块的地址，然后再访问具体的磁盘块，因此每多一级多级索引，磁盘访问次数就增加一次，而每增加一次磁盘访问次数就意味着文件读取效率会降低一点。为了解决这个问题，可采用非对称多级索引结构。

图7-8 二级索引文件

非对称多级索引是指将多种索引方式相结合而形成的一种索引文件结构，例如，系统既采用了一级索引分配方式，又采用了两级索引分配方式，甚至还采用了三级索引分配方式。如图7-9所示为非对称多级索引结构。

图7-9 非对称多级索引结构

在非对称多级索引文件中，大文件可以采用多级索引使得文件扩展更加方便，而小文件可以采用一级索引读取效率较高。