27 目录管理

现代计算机系统主要通过文件目录对其大量存储的文件进行有效的管理。文件目录是一种数据结构，用于标识系统中的文件及其物理地址，供检索时使用。

目录管理的要求如下：

• 实现“按名存取”，用户能通过文件名字能快速准确找到指定文件在外存上的存储位置。

• 提高对目录的检索速度。通过合理地组织目录结构方法，加快目录检索速度，进而提高文件存取速度。

• 文件共享。在多用户系统中，应允许多个用户共享一个文件。在外存中只保留一份该文件副本，以节省大量存储空间。

• 允许文件重名系统应允许不同用户对不同文件采用相同的名字，便于用户按照自己习惯使用文件。

1 文件控制块

为了能对文件进行正确的存取，必须为文件设置用于描述和控制文件的数据结构，称之为文件控制块FCB。文件管理程序可借助于文件控制块中的信息，对文件施加各种操作，文件与文件控制块一一对应。

人们把文件控制块的有序集合称为文件目录，一个文件控制块就是一个文件目录项。通常，一个文件目录也可被看成是一个文件，称为目录文件。

为了能对系统中大量文件进行有效的管理，通常文件控制块应包含以下三方面信息：

• 基本信息类
  文件名、物理地址位置（文件长度）、文件逻辑结构、文件物理结构。

• 存取控制信息类
  文件主的存取权限、准核用户的存取权限以及一般用户的存取权限。

• 使用信息类
  文件的建立日期、上次修改日期、当前使用信息（打开该文件的进程数、是否被锁定、文件在内存中是否已被修改单尚未拷贝到盘上）

2 索引结点

文件目录通常是存放在磁盘上的，当文件很多时，文件目录可能要占用大量的盘块。

稍加分析可发现，在检索目录文件时，只用到了文件名，仅当找到一个目录项时，才从该目录中读取该文件的物理地址。显然，对文件进行的描述信息在检索目录时一概不用调入内存。

为此，在有的系统中，如UNIX系统，便采用了把文件名和文件描述信息分开的方法，使文件描述信息单独形成一个称为索引结点的数据结构，简称为i结点（iNode），在文件目录中的每个目录项由文件名和指向该文件i结点的指针所构成。

2.1 磁盘索引结点

每个文件都有唯一的磁盘索引结点（磁盘索引结点信息与文件名等信息一起构成了FCB），其主要包括内容如下：

• 1. 文件主标识符，即拥有该文件的个人或小组的标识符。
• 2. 文件类型，包括正规文件、目录文件或特别文件。
• 3. 文件存取权限，指各类用户对该文件的存取权限。
• 4. 文件物理地址，每个索引结点中含有13个地址项（混合索引方式），他们以直接或间接的方式给出数据文件所在的盘块的编号。
• 5. 文件长度，指以字节为单位的文件长度。
• 6. 文件连接计数，表明在本文件系统中所有指向该文件名的指针计数。
• 7. 文件存取时间，指本文件最近被进程存取的时间、最近被修改的时间及索引结点最近被修改的时间。

当文件被打开时，要将磁盘索引结点拷贝到内存索引结点中，便于以后使用，在内存索引结点中又增加了以下内容：

• 1. 索引结点编号，用于标识内存索引结点。
• 2. 状态，指示i结点是否上锁或被修改。
• 3. 访问计数，每当有进程要访问此i结点时，将访问计数加1，访问完再减1。
• 4. 文件所属文件系统的逻辑设备号。
• 5. 链接指针，设置有分别指向空闲链表和散列队列的指针。

3 目录结构

目录结构的组织，关系到文件系统的存取速度，也关系到文件的共享性和安全性，目前常用的目录结构形式有单级目录、两级目录、多级目录。

3.1 单级目录结构

在整个系统中只建立一张目录表，每个文件占一个目录项，目录项中含文件名、文件扩展名、文件长度、文件类型、文件物理地址、状态位（表示目录项是否空闲）等。

每当要建立一个新文件时，必须先检查所有的目录项，以保证新文件名在目录中是唯一的，然后再从目录表中找到一个空白目录项，填入新文件名及其他说明信息，并置状态为1。

删除文件时，先从目录中找到该文件的目录项，回收该文件所占用的存储空间，然后再清除该目录项。

优点

• 简单并且能够实现目录管理的基本功能-按名存取。

缺点

• 查找速度慢
  查找具有N个目录项的单级目录平均要使用N/2次查找。

• 不允许重名
  在一个目录表中的所有文件，都不能与另一个文件有相同的名字，这是难以避免的

• 不便于实现文件共享
  每一个用户都有自己的名字空间或命名习惯，因此，应该允许不同用户使用不同的文件名来访问同一个文件

3.2 两级目录结构

两级目录结构，为每个用户建立一个单独的用户文件目录UFD（User File Directory），这些文件目录具有相似的结构，由用户所有文件的文件控制块组成。

系统中还有一个主文件目录MFD（Master File Directory），在主文件目录中，每个用户目录文件都占有一个目录项，其目录项包括用户名和指向用户目录文件的指针。

优点

两级目录结构克服了单级目录的缺点，具有如下优点：

• 提高了检索目录的速度
  如果在主目录中有n个子目录，每个用户目录最多为m个目录项，则为查找一指定的目录项，最多只需要检索n+m个目录项。

• 在不同的用户目录中，可以使用相同的文件名
  只要在用户自己的UFD中，每个文件名都是唯一的，不同用户可以有文件名相同的文件。不同用户还可使用不同的文件名来访问系统中同一个共享文件。

缺点

• 在多个用户需要合作完成一个大任务时，不便于用户之间共享文件。

3.3 多级目录结构

对于大型文件系统，通常采用三级或三级以上的目录结构，以提高对目录的检索速度和文件系统的性能。多级目录结构又称为树形目录结构，主目录被称为根目录，把数据文件称为树叶，其他的目录均作为树的结点。

目录结构

方框代表目录文件，圆圈代表数据文件，主目录中有三个用户总目录A、B、C。在B用户的总目录B中，又包括三个分目录F、E、D，其中每个分目录中又包含多个文件。

为提高系统的灵活性，应允许在一个目录文件中的目录项既是作为目录文件的FCB，又是数据文件的FCB，这一信息可用目录项中的一位来指示。如用户A总目录中，目录项A是目录文件FCB，而目录项B和D则是数据文件的FCB。

路径名

在树形目录结构中，从根目录到任何数据文件，都只有一条唯一的通路，在该路径上从树的根开始，把全部目录文件名和数据文件名依次用"/"连接起来，即构成该数据文件的路径名。

为避免每访问一个文件，都要使用从树根开始直到树叶（数据文件）的全路径名，可为每个进程设置一个当前目录（工作目录），进程对各文件的访问都相对于当前目录而进行的。

把从当前目录开始值得数据文件为止所构成的路径名称为相对路径名，而把从树根开始的路径名称为绝对路径名。

3.4 增加和删除目录

增加

在树形目录结构中，用户可为自己建立UFD，并可再创建子目录。

在用户要创建一个新文件时，只需要查看自己的UFD及其子目录中有无与新建文件相同的文件名，若无，便可在UFD或其某个子目录中增加一个新目录项。

删除

在树形目录中，如何删除一个目录，应该视情况而定，若要删除的目录为空，则简单地将其删除，使它在其上一级目录中所对应的目录项为空，若不为空，可采用如下方法：

• 不删除非空目录
  当目录不为空时，为了删除一个非空目录，必须先删除目录中所有的文件，使之称为空目录，然后再删除，如果目录中包含有子目录，则应该递归调用方式删除

• 可删除非空目录
  将目录中的所有文件和子目录同时删除。

4 目录查询技术

当访问一个已存在的文件时：

• 首先，利用文件名在目录中找出该文件的文件控制块或对应索引结点
• 然后，根据FCB或索引结点中所记录的文件物理地址（盘块号），换算出文件在磁盘上的物理位置
• 最后，再通过磁盘驱动程序，将所需文件读入内存。

目前常用的方式有线性检索法和Hash方法。

4.1 线性检索法

其又称为顺序检索法，在树形目录中，用户提供的文件名是由多个文件分量名组成的路径名，此时须对多级目录进行查找，假定用户给定的文件路径名为/usr/ast/mbox，则查找过程如下。

• 在根目录中，由usr找到结点6，定位到132；
• 在usr目录中，由ast找到26，定位到496；
• 在ast目录中，由mbox找到60，查询结束。

如果查询失败，则返回“文件未找到”。

4.2 Hash方法

系统利用用户提供的文件名并将它转换为文件目录的索引值，再利用该索引值到目录中去查找，这将显著提高检索速度。

注意：通配符无法进行Hash目录检索。