DJ6-5 目录管理

目录

6.5.1  文件控制块和索引结点

1、文件控制块 FCB

2、索引节点

6.5.2  简单文件目录

1、单级目录结构   

2、二级目录结构

3、树形目录结构

6.5.3  目录查询技术

1、线性检索法

2、Hash 方法

---

文件目录：是指由文件说明索引组成的用于文件检索的特殊文件。

• 文件目录通常以文件的形式保存在外存
• 文件目录的内容主要是文件访问的控制信息（不包括文件内容）
• 文件目录也是一种数据结构，用于标识系统中的文件及其物理地址

对目录管理的要求如下：

1. 实现 “按名存取”
2. 提高对文件目录的检索速度
3. 允许文件共享
4. 允许文件重名

6.5.1  文件控制块和索引结点

文件控制块 FCB 是 OS 为管理文件而设置的数据结构，存放了管理文件所需的所有信息，即文件属性。文件控制块是文件存在的标志。

• 文件目录：把所有的 FCB 组织在一起，就构成了文件目录，即文件控制块的有序集合。
• 目录项：构成文件目录的项目，目录项就是 FCB 。
• 目录文件：为通常将文件目录以文件的形式保存在外存，这个文件就称为目录文件。

1、文件控制块 FCB

检索文件目录时，需要把若干个文件的整个 FCB 读入内存。

① 基本信息类

• 文件名：文件标识符
• 文件的物理位置：存放文件的设备名、起始盘块号、文件长度（盘块数或字节数）
• 文件的逻辑结构：有结构文件、无结构文件
• 文件的物理结构：顺序文件、链式文件、索引文件

② 存取控制信息类

• 文件主的存取权限
• 核准用户的存取权限
• 一般用户的存取权限

③ 使用信息类

• 文件的建立日期和时间
• 文件上一次修改的日期和时间
• 当前使用信息（进程数、是否修改等）

2、索引节点

检索文件目录时，只需要把若干个文件的文件名读入内存；找到指定文件后，再根据目录项中的节点指针，把该文件的索引节点读入内存。

① 索引节点的引入

为减少检索文件时启动磁盘的次数，应缩小文件目录的大小。

=> 将文件名和文件的描述信息分开：

• 将文件的描述信息单独形成称为索引节点的数据结构，即 i 节点
• 文件目录的每个目录项中仅包含：文件名和指向该文件的 i 节点的指针

② 磁盘索引节点：是指存放在磁盘上的索引节点。

主要内容包括：

• 文件主标识符
• 文件类型：正规文件、目录文件、特殊文件
• 文件存取权限：各类用户对文件的存取权限
• 文件物理地址：以 iaddr(0)~ iaddr(12) 给出文件所在的盘块号
• 文件长度：以字节数计算
• 文件链接计数：共享该文件的用户数
• 文件存取时间：最近被访问或修改的时间

③ 内存索引节点：是指存放在内存中的索引节点。

文件被打开时，将磁盘索引结点拷贝到内存索引结点中以备将来使用。

增加的主要内容：

• 索引结点编号：用于标识内存索引结点
• 状态：指示 i 结点是否上锁或被修改
• 访问计数：有进程访问时计数器加一，访问完减一
• 文件所属文件系统的逻辑设备号
• 链接指针：指向空闲链表和散列队列的指针

6.5.2  简单文件目录

1、单级目录结构   

① 整个系统中只建立一张目录表，为每个文件分配一个目录项

② 目录项中包含以下内容：

• 文件名及扩展名
• 文件的物理地址
• 其它属性，如文件长度、文件类型等
• 状态位：指示目录项是否空闲等信息

③ 创建文件

1. 查看目录表，判断新文件名是否唯一；
2. 查找空目录项，填写文件名、物理地址、属性等；
3. 置目录项的状态位为 1 。

④ 删除文件

1. 查看目录表，找到该文件对应的目录项；
2. 从中找到该文件的物理地址并回收磁盘空间；
3. 从目录表中清除所占用的目录项。

⑤ 性能分析

 1）实现了按名存取； 2）查找速度慢
 3）不允许重名； 4）不便于实现共享

2、二级目录结构

① 将目录分为两级：主文件目录 MFD 和用户文件目录 UFD

• 在 MFD 中，每个 UFD 占用一个目录项，内容包括：用户名和指向该 UFD 文件的指针。
• 再为每个用户建立一个单独的 UFD，由用户所有文件的 FCB 组成。

② 创建文件：创建用户文件目录 UFD 的目录项。

1. 查看 UFD，判断是否有同名文件；
2. 有：为新文件重新命名；
3. 无：建立新的目录项，填写文件信息；
4. 置目录项状态位为 1 。

③ 删除文件

1. 查看 UFD，找到该文件对应的目录项；
2. 查找该文件的所有盘块并回收；
3. 从目录表中清除所占用的目录项。

④ 优缺点

• 提高了检索目录的速度：由 n*m 提高到 n+m
• 在不同的 UFD 中，可以使用相同的文件名
• 不同用户可以使用不同的文件名访问系统中的同一个共享文件
• 用户间的隔离使文件共享不方便

假设 MFD 有 n 个目录项，UFD 有 m 个目录项，那么整个系统可以存放 n*m 个文件。采用一级目录结构时，检索目录最后一个文件需要查询 n*m 次；采用二级目录结构时，先查询 MFD 花费 n 次，再查询 UFD 花费 m 次，共需要查询 n+m 次。

3、树形目录结构

树形目录：把三级或三级以上的目录结构称树形目录。

树形目录文件中的目录项，既可作为目录文件的 FCB，也能作为数据文件的 FCB，可由目录项中的属性位来表示。

① 路径名：系统中的每一个文件都有唯一的路径名。因为在树形目录结构中，从根目录到任何数据文件，都只有一条唯一的通路。

绝对路径：在该路径上从树的根目录开始，把所有目录文件名与数据文件名，依次地用 “/” 连接起来，即构成该数据文件的绝对路径。

② 当前目录：系统向用户提供一个当前正在使用的目录。

当前目录可根据需要任意改变；查找一个文件可从当前目录开始，使用部分路径名。

相对路径：在该路径上从当前目录开始，把所有目录文件名与数据文件名，依次地用 “/” 连接起来，即构成该数据文件的相对路径。

③ 增加目录项

• 用户可创建自己的 UFD，并可再创建子目录
• 在同一个子目录下创建新文件时，必须保证不同名

④ 删除目录项

• 不删除非空目录
• 可删除非空目录

⑤ 优点

• 层次结构清晰，便于管理和保护
• 有利于文件分类
• 解决重名问题
• 提高文件检索速度
• 能进行存取权限的控制

⑥ 缺点：查找一个文件按路径名逐层检查，由于每个文件都放在外存，多次访盘影响速度。

6.5.3  目录查询技术

按名存取的实现步骤：

1. 根据文件名查询文件目录，找到该文件的 FCB 或 i 节点；
2. 根据 FCB 或 i 节点中的起始盘块号，计算文件在磁盘上的物理位置；
3. 启动磁盘驱动程序，将需要的文件读入内存。

要么采用 FCB 的方式存储文件，要么采用索引节点的方式存储文件

查询目录有两种方法：

• 线性检索法
• Hash 方法

1、线性检索法

检索目录：/usr/ast/mbox

首先，系统读入第一个文件分量名 usr，用它与根目录文件中各目录项中的文件名顺序地进行比较。得到匹配项的索引节点是 6 号，然后访问 6 号索引节点，得到 usr 目录文件存放在 132 号盘块中，将该盘块内容读入内存。

然后，系统再读入第二个文件分量名 ast，用它与 usr 目录文件中各目录项中的文件名顺序地进行比较。得到匹配项的索引节点是 26 号，然后访问 26 号索引节点，得到 ast 目录文件存放在 496 号盘块中，将该盘块内容读入内存。

最后，系统再读入第三个文件分量名 mbox，用它与 ast 目录文件中各目录项中的文件名顺序地进行比较。得到匹配项的索引节点是 60 号，然后访问 60 号索引节点，得到 mbox 普通文件所存放的盘块号。

目录查询操作到此结束。

2、Hash 方法

基本思想：建立一张 Hash 索引文件目录，利用一个易于实现的变换函数（Hash 函数），把用户提供的文件名唯一地转换为文件目录的索引值，再利用该索引值到 Hash 索引文件目录中进行查找该文件对应的索引节点。

• Hash 函数
• Hash 冲突的解决