6.2.6　文件系统的实现

1.目录实现

目录实现的基本方法有线性表和散列（hash）表。

（1）线性表

最为简单的目录实现方法是使用存储文件名和数据块指针的线性表（包括数组、链表等）。该方法实现简单，但查找耗时较长。

（2）散列表

采用该方法时，在使用线性列表存储目录条目外，还使用了散列数据结构。散列表根据文件名得到一个值，并返回一个指向线性表中元素的指针。该方法降低了目录表的搜索时间，插入和删除也比较简单。

2.文件实现

文件实现主要是指文件物理结构的实现，包括外存分配方式、文件记录的成组和分解，以及文件存储空间的管理。

（1）外存分配方式

文件的物理结构是指一个文件在外存上的存储组织形式，它与外存的分配方式有关。外存分配方式指的是如何为文件分配磁盘块。在采用不同的分配方式时，将形成不同的文件物理结构。常用的外存分配方式有连续分配、链接分配以及索引分配。

1）连续分配要求为每一个文件分配一组相邻接的盘块。一组盘块的地址定义了磁盘上的一段线性地址。连续分配支持顺序访问和直接访问。

2）链接分配中每个文件对应一个磁盘块的链表，盘块分布在磁盘的任何地方。链接方式可分为隐式链接和显式链接两种。隐式链接指在文件目录的每个目录项中，都必须含有指向链接文件第一个盘块和最后一个盘块的指针。显式链接是指将用于链接文件各物理块的指针，显式地存放在内存的一张链表中。

3）索引分配是一种离散分配方式，它为每个文件分配一个索引块，索引块是一个磁盘块地址的数组，分配给文件的所有盘块号放在该索引块中。索引块中第i个条目指向文件的第i块。

（2）文件记录的成组和分解

逻辑记录的大小与盘块的大小不一定相同，因为逻辑记录是按照信息在逻辑上的独立含义由用户划分的单位，而磁盘块是由系统划分的。将若干个逻辑记录合并成一个组存入一个盘块中称为“记录的成组”。成组操作先在系统输出缓冲区内进行，凑满一块后才将缓冲区内的信息写入存储介质上。当需要某一记录时，必须把含有该记录的盘块信息读出。从一组记录中把所需要的逻辑记录分离出来称为“记录的分解”。文件记录的成组和分解操作不仅节省存储空间，还能减少I/O操作次数，提高系统效率。

（3）文件存储空间的管理

为了实现文件存储管理空间的分配，文件系统应为分配存储空间设置相应的数据结构，另外，还应提供对存储空间进行分配和回收的方法。

1）位示图法。位示图是利用二进制的一位来表示磁盘中一个盘块的使用情况，如图6-7所示。系统从内存中划出若干个字节，为每个文件存储设备建立一张位示图，位示图反映了每个文件存储设备的使用情况。在位示图中，当其值为“0”时，表示对应的盘块空闲；为“1”时，表示已分配。磁盘上的所有盘块都有一个二进制位与之对应，这样，由所有盘块所对应的位构成一个集合，称为位示图。位示图描述能力强，一个二进位就描述一个物理块的状态，因而位示图较小，可以复制到内存，使查找既方便又快速。位示图适用于各种文件物理结构的文件系统。

图　6-7　文件存储空间的位示图

2）空闲区表法。磁盘上连续的空闲磁盘块组成一个空闲区，系统为所有的空闲区建立一张空闲区表。每个空闲区对应于一个空闲空间表项，表项内容包括表项序号（区号）、该空闲区的起始块号、该区的空闲盘块数等信息。空闲区表法属于连续分配方式，它与内存的动态分配方式类似，当有文件请求分配存储空间时，系统依次扫描空闲区表，将满足需求的空闲块进行分配，并修改空闲区表。当删除文件时，系统收回它所占用的物理块，若回收的物理块有相邻的空闲块，则合并成更大的空闲区域，最后修改有关表项。该方法特别适合于文件物理结构为顺序结构的文件系统。

3）空闲块链表法。空闲块链表法是将所有空闲磁盘块用链表链接起来，并将指向第一个空闲块的指针保存在磁盘上并缓存在内存中。当申请分配空间时，从该空闲块链的链首依次摘取所需的空闲盘块，然后调整链首指针。反之，当回收空闲盘块时，将释放的空闲盘块插入到空闲块链中。

空闲块链表法节省内存，但申请释放速度较慢，实现效率较低。一种改进办法是把所有空闲块按固定数量分组，即空闲块成组链接法。

4）成组链接法。将空闲块分成若干组，把指向一组中各空闲块的指针集中一起。这样既可方便查找，又可减少为修改指针而启动磁盘的次数。例如，每50个空闲盘块为一组。将第一组的50个空闲盘块的块号放在第二组的头一块中，而第二组的其余49块是完全空闲的。第二组的50个块号又放在第三组的头一块中，依次类推，组与组之间形成链接关系。最后一组的块号（可能不足50块）通常放在内存的一个专用栈结构中。如图6-8所示。

图　6-8　空闲块成组链接

UNIX系统采用空闲块成组链接的方法。