第27 管理之目录管理.doc

第二十七讲 文件管理之目录管理1 引言1.1 概述 为什么引入文件目录？实现对文件的按名存取，就要求每个文件必须有一个文件名和文件对应；一般用户文件的文件名由用户指定，系统文件和特殊文件的文件名由系统指定。为了准确迅速的由文件名检索到文件物理块，我们把文件名及其结构信息等按一定的组织结构排列，用来方便文件检索。这里。我们把文件名和对该文件实施控制管理的控制管理信息称为该文件的文件说明。并把一个文件说明按一定的逻辑结构存放到物理存储块的一个表目中。这样，就利用文件说明信息，可以对文件进行创建、检索、维护等管理。我们把一个文件的文件说明信息称为文件的目录（文件说明有时也叫文件控制块）。对文件目录的管理就是对文件说明信息的管理。总之，现代计算机系统中，存储大量文件，为了对文件进行有效管理，引入了文件目录，通过文件目录对文件进行管理。1.2 什么是文件目录？v 目录是由文件说明索引组成的用于文件检索的特殊文件。v 文件目录的内容主要是文件访问的控制信息（不包括文件内容）。v 它是一张记录所有文件名及其存放地址、文件的说明和控制信息的表格。v 每个文件有一个文件的目录项。文件目录也是一种数据结构，用于标识文件及其物理地址，对目录管理要求如下：实现“按名存取”、提高对目录的检索速度、文件共享、允许文件重名2 文件控制块和索引节点 文件说明信息2.1 什么是文件控制块?1 文件控制块（FCB）是用于描述和控制文件的数据结构。存放了文件的有关说明信息,是文件存在的标志。2 FCB中的信息： 基本信息类：文件名、文件长度、类型、属性文件物理位置 存取控制信息类：文件存取权限、用户名、口令、共享计数 使用信息类：文件的建立日期、最后修改日期、保存期限、最后访问日期,3 说明：文件与文件控制块一一对应，而人们把文件控制块的有序集合称为文件目录，即一个文件控制块就是一个文件目录项。通常一个文件目录也被看作是一个文件，称为目录文件。4 下面是MS-DOS的文件控制块：文件名扩展名属性备用时间日期第一块号盘块数2.2 索引节点2.2.1 索引节点引入 什么是索引节点为什么引入它？文件目录通常是存放在磁盘上的，当文件很多时，文件目录要占用大量的盘块。在检索目录文件的时候，需要将目录调入内存后比较文件名，但是只用到文件名，而不需要其它那些对文件的描述信息，显然，目录中有许多信息不需要调入内存。所以便把文件名与文件信息分开，使文件描述信息单独形成一个索引结点。索引结点的引入，便于快速检索文件目录！UNIX文件目录如下图：文件名索引结点编号文件名1文件名22.2.2 磁盘索引结点存放在磁盘上的索引节点，每个文件有唯一的一个磁盘索引节点。包括以下内容:主标识、类型、存取权限、物理地址、长度、连接计数、存取时间2.2.3 内存索引结点放在内存中的索引结点。当文件被打开后，将磁盘索引结点拷贝到内存索引结点中。比磁盘索引结点又增加了以下内容：索引结点编号、状态、访问计数、逻辑设备号、链接指针3 目录结构目录结构的组织，关系到文件系统的存取速度，也关系到文件的共享性和安全性。因此，要组织好文件的目录。目录结构形式有单级目录、两级目录和多级目录。3.1单级目录结构Single-Level Directory概念：整个文件系统中只建立一张目录表，每个文件一个目录项，目录项含有文件相关信息。单级目录如图：文件名物理地址文件说明状态位文件名1文件名2单级目录结构图：操作：每建立一个新文件要先检索所有的目录项保证文件名唯一。然后找出一空白目录项填入相关信息，并修改状态位。删除文件是找到对应目录项，回收所占用空间，清除该目录。优点: 简单，易实现按名存取缺点: 限制了用户对文件的命名（即易重名） 文件平均检索时间长(查找速度慢) 不便于实现文件共享 只适用于单用户环境3.2 两级目录Two-Level Directory 原理：在整个系统中建立两级目录： 为每个用户建立一个单独的用户文件目录（UFD） 系统为所有用户建立一个主文件目录（MFD）其中包括用户名和指向该用户目录文件的指针。如图：两级目录结构图：优点:提高了检索目录的速度；不同用户目录中可重名；不同用户可用不同文件名来访问系统中一共享文件缺点: 限制了各用户对文件的共享，增加了系统开销，缺乏灵活性，无法反映真实世界复杂的文件结构形式。3.2 多级目录/树兴目录Tree-Structured Directories在两级目录中若允许用户建立自己的子目录，则形成3级或多级目录结构（即树型目录结构）路径名：访问数据文件的一条路径，绝对路径、相对路径当前目录操作：增加和删除目录优点：层次结构清晰,实现分组,便于管理和保护；解决重名问题；查找速度加快缺点查找一个文件按路径名逐层检查,由于每个文件都放在外存,多次访盘影响速度一些概念：目录的上下级关系：当前目录(current directory, working directory)、父目录(parent directory)、子目录(subdirectory)、根目录(root directory)等；路径(path)：每个目录或文件，可以由根目录开始依次经由的各级目录名，加上最终的目录名或文件名来表示4 目录查询技术基本过程：当用户要访问一个已存文件时，系统首先利用用户提供的文件名对目录进行查询，找出该文件控制块或对应索引结点；然后根据FCB或索引结点中所记录的文件物理地址，换算出文件在磁盘上的物理位置；最后通过磁盘驱动程序，将所需文件读入内存。目前对目录进行查询的方式有两种：4.1 线性检索法基本过程：又叫顺序检索法。在单级目录中，利用用户提供的文件名，用顺序查找法直接从文件目录中找到指名文件的目录项。在树型目录中，用户提供的文件名是由多个文件分量名组成的路径名，此时需对多级目录进行查找。查找/usr/ast/mbox的步骤 如图4.2 Hash方法基本过程：前面介绍了Hash文件。如果我们建立了一张Hash索引文件目录，便可利用Hash方法进行查询，即系统利用用户提供的文件名并将它变换为文件目录的索引值，再利用该索引值到目录中去查找，将显著的提高检索速度。注意：对于使用通配符*，？的文件名系统无法利用Hash法检索目录，还是需用线性查找法。冲突：在进行文件名转换时，可能把若干