## 3. 树形目录结构
**前置图片** 设置当前工作目录的作用（2010）
将两级目录结构加以推广，就形成了树形目录结构，如图4.14所示。它可以明显地提高对目录的检索速度和文件系统的性能。当用户要访问某个文件时，用文件的路径名标识文件，文件路径名是个字符串，由从根目录出发到所找文件通路上所有目录名与数据文件名用分隔符“/”链接而成。从根目录出发的路径称为绝对路径，系统中的每个文件都有唯一的路径名。一个进程在运行时，其所访问的文件大多局限于某个范围，当层次较多时，每次从根目录查询会浪费时间，因此可为每个进程设置一个当前目录（也称工作目录），此时进程对各文件的访问都只需相对于当前目录而进行。当用户要访问某个文件时，使用相对路径名标识文件，相对路径由从当前目录出发到所找文件通路上所有目录名与数据文件名用分隔符“/”链接而成。
图4.14所示是Linux操作系统的树形目录结构，“/dev/hda”就是一个绝对路径。若当前目录为“/bin”，则“/ls”就是一个相对路径，其中符号“.”表示当前工作目录。
通常，每个用户都有各自的“当前目录”，登录后自动进入该用户的“当前目录”。操作系统提供一个专门的系统调用，供用户随时改变“当前目录”。例如，在UNIX系统中，“/etc/passwd”文件就包含有用户登录时默认的“当前目录”，可用cd命令改变“当前目录”。
树形目录结构可以很方便地对文件进行分类，层次结构清晰，也能够更有效地进行文件的管理和保护。在树形目录中，不同性质、不同用户的文件，可以分别呈现在系统目录树的不同层次
<!-- page: 295 -->
或不同子树中，很容易地赋予不同的存取权限。但是，在树形目录中查找一个文件，需要按路径名逐级访问中间节点，增加了磁盘访问次数，这无疑会影响查询速度。目前，大多数操作系统如UNIX、Linux和Windows系统都采用了树形文件目录。
图4.14 树形目录结构
## 4. 无环图目录结构
树形目录结构能便于实现文件分类，但不便于实现文件共享，为此在树形目录结构的基础上增加一些指向同一节点的有向边，使整个目录成为一个有向无环图，如图4.15所示。这种结构允许目录共享子目录或文件，同一个文件或子目录可以出现在两个或多个目录中。
当某用户要求删除一个共享节点时，若系统只是简单地将它删除，则当另一共享用户需要访问时，会因无法找到这个文件而发生错误。为此，可为每个共享节点设置一个共享计数器，每当图中增加对该节点的共享链时，计数器加1；每当某用户提出删除该节点时，计数器减1。仅当共享计数器为0时，才真正删除该节点，否则仅删除请求用户的共享链。
无环图目录结构方便地实现了文件的共享，但使得系统的管理变得更加复杂。
图4.15 无环图目录结构
## *4.2.4 目录实现
在访问一个文件时，操作系统利用路径名找到相应目录项，目录项中提供了查找文件磁盘块所需要的信息。目录实现的基本方法有线性列表和哈希表两种，要注意目录的实现就是为了查找，因此线性列表实现对应线性查找，哈希表的实现对应散列查找。
### 1. 线性列表
最简单的目录实现方法是，采用文件名和数据块指针的线性列表。当创建新文件时，必须首
<!-- page: 296 -->
先搜索目录以确定没有同名的文件存在，然后在目录中增加一个新的目录项。当删除文件时，则根据给定的文件名搜索目录，然后释放分配给它的空间。当要重用目录项时有许多种方法：可以将目录项标记为不再使用，或将它加到空闲目录项的列表上，还可以将目录的最后一个目录项复制到空闲位置，并减少目录的长度。采用链表结构可以减少删除文件的时间。
线性列表的优点在于实现简单，不过由于线性表的特殊性，查找比较费时。
## 2. 哈希表
除了采用线性列表存储文件目录项，还可以采用哈希数据结构。哈希表根据文件名得到一个值，并返回一个指向线性列表中元素的指针。这种方法的优点是查找非常迅速，插入和删除也较简单，不过需要一些措施来避免冲突（两个文件名称哈希到同一位置）。
目录查询是通过在磁盘上反复搜索完成的，需要不断地进行 I/O 操作，开销较大。所以如前所述，为了减少 I/O 操作，将当前使用的文件目录复制到内存，以后要使用该文件时只需在内存中操作，因此降低了磁盘操作次数，提高了系统速度。
## 4.2.5 文件共享
文件共享使多个用户共享同一个文件，系统中只需保留该文件的一个副本。若系统不能提供共享功能，则每个需要该文件的用户都要有各自的副本，会造成对存储空间的极大浪费。
前面介绍了无环图目录，基于该结构可实现文件共享，当建立链接关系时，必须将被共享文件的物理地址（盘块号）复制到相应的目录。若某个用户向该文件添加新数据，且需要增加新盘块，则这些新增的盘块只会出现在执行操作的目录中，对其他共享用户是不可见的。
### 1. 基于索引节点的共享方式（硬链接）
#### 附属图应
> 硬链接和软链接文件中引用计数值的分析（2009）
#### 附属图应
> 硬链接的原理（2017）
硬链接是基于索引节点的共享方式，它将文件的物理地址和属性等信息不再放在目录项中，而是放在索引节点中，在目录中只设置文件名及指向相应索引节点的指针。如图 4.16 所示，在用户 A 和 B 的目录中，都设置有指向共享文件的索引节点指针。在索引节点中还有一个链接计数 count，也称引用计数，表示链接到本索引节点（文件）上的用户目录项的数量。当 count = 2 时，表示有两个用户目录项链接到本文件上，即有两个用户共享此文件。
图 4.16 基于索引节点的共享方式
当用户 A 创建一个新文件时，他是该文件的所有者，此时将 count 置为 1。当用户 B 要共享此
<!-- page: 297 -->
文件时，在B的目录中增加一个目录项，并设置一个指针指向该文件的索引节点。此时，文件主仍是用户A，count = 2。当用户A不再需要此文件时，能否直接将其删除？答案是否定的。因为若删除该文件，必然也删除该文件的索引节点，这样便使用户B的指针悬空，而B可能正在此文件上执行写操作，此时将因此半途而废。因此用户A不能删除此文件，只是将该文件的count减1，然后删除自己目录中的相应目录项。用户B仍可以使用该文件。当count = 0时，表示没有用户使用该文件，才删除该文件。如图4.17所示为文件共享中的链接计数。
图4.17 文件共享中的链接计数
## 2. 利用符号链实现文件共享（软链接）
为使用户B能共享用户A的一个文件F，可由系统创建一个LINK类型的新文件L，并将文件L写入用户B的目录，以实现B的目录与文件F的链接。文件L中只含有被链接文件F的路径名，如图4.18所示。这种链接方法称为符号链接或软链接，它类似于Windows系统中的快捷方式。当用户B访问文件L时，操作系统看到要读的文件属于LINK类型，则根据其中记录的路径名去查询文件F，然后对F进行读/写操作，从而实现用户B对文件F的共享。
图4.18 利用符号链的共享方式
## 创建建议
软链接方式删除共享文件后的情况（2021）
利用符号链方式实现文件共享时，只有文件主才拥有指向其索引节点的指针。而共享该文件的其他用户只有该文件的路径名，并不拥有指向其索引节点的指针。这样，也就不会发生在文件主删除一个共享文件后留下一个悬空指针的情况。当文件主将一个共享文件删除后，若其他用户又试图通过符号链去访问它时，则会访问失败，于是再将符号链删除，此时不会产生任何影响。
在符号链的共享方式中，当其他用户读共享文件时，系统根据文件路径名依次查找目录，直至找到该文件的索引节点。因此，每次访问共享文件时，都可能要多次地读盘，增大了访问文件的开销。此外，符号链接也是一个文件，其索引节点也要耗费一定的磁盘空间。
利用符号链实现网络文件共享时，只需提供该文件所在机器的网络地址及文件路径名。
<!-- page: 298 -->
可以这样说：文件共享，“软硬”兼施。硬链接就是多个指针指向一个索引节点，保证只要还有一个指针指向索引节点，索引节点就不能删除；软链接就是将到达共享文件的路径保存下来，当要访问文件时，根据路径寻找文件。可见，硬链接的查找速度要比软链接的快。
## 4.2.6 本节小结
本节开头提出的问题的参考答案如下。
1）目录管理的要求是什么？
①实现“按名存取”，这是目录管理最基本的功能。②提高对目录的检索速度，从而提高对文件的存取速度。③为了方便用户共享文件，目录还需要提供用于控制访问文件的信息。④允许不同用户对不同文件采用相同的名字，以便用户按自己的习惯给文件命名。
2）在目录中查找某个文件可以使用什么方法？
可以采用线性列表法或哈希表法。线性列表将文件名组织成一个线性表，查找时依次与线性表中的每个表项进行比较。若将文件名按序排列，则使用折半查找法可以降低平均的查找时间，但建立新文件时会增加维护线性表的开销。哈希表用文件名通过哈希函数得到一个指向文件的指针，这种方法非常迅速，但要注意避免冲突。
## 4.2.7 本节习题精选
### 一、单项选择题
01. 下列关于目录检索的论述中，正确的是（）。
A. 数列法具有较快的检索速度，因此现代操作系统中都用它替代传统的顺序检索方法
B. 在利用顺序检索法时，对树形目录应采用文件的路径名，且应从根目录开始逐级检索
C. 在利用顺序检索法时，只要路径名的一个分量名未找到，就应停止查找
D. 利用顺序检索法查找完成后，即可得到文件的物理地址
02. 一个文件的相对路径名是从（）开始，逐步沿着各级子目录追溯，最后到指定文件的整个道路上所有子目录名组成的一个字符串。
A. 当前目录
B. 根目录
C. 多级目录
D. 二级目录
03. 文件系统采用多级目录结构的目的是（）。
A. 减少系统开销
B. 节省存储空间
C. 解决命名冲突
D. 缩短传送时间
04. 若文件系统中有两个文件重名，则不应采用（）。
A. 单级目录结构
B. 两级目录结构
C. 树形目录结构
D. 多级目录结构
05. 下面的说法中，错误的是（）。
I. 一个文件在同一系统中、不同的存储介质上的复制文件，应采用同一种物理结构
II. 对一个文件的访问，常由用户访问权限和用户优先级共同限制
III. 文件系统采用树形目录结构后，对于不同用户的文件，其文件名应该不同
IV. 为防止系统故障造成系统内文件受损，常采用存取控制矩阵方法保护文件
A. II
B. I、III
C. I、III、IV
D. 全选
06. 设文件F1的当前引用计数为1，先建立F1的硬链接文件F2，再建立F1的符号链接文件F3，然后删除F2，则此时文件F1、F3的引用计数值分别是（）。
A. 1、1
B. 1、2
C. 1、0
D. 2、2
07. 设文件F1的当前引用计数值为1，先建立F1的硬链接文件F2，再建立F2的符号链接文件F3，现有两个进程 $\mathrm{P}_1$ 和 $\mathrm{P}_2$ 分别打开了F1和F2，则下列说法中正确的是（）。
<!-- page: 299 -->
A. 两次打开操作只涉及一次文件索引节点的磁盘读取操作
B. 进程 $\mathrm{P}_1$ 和 $\mathrm{P}_2$ 对F1具有相同的访问权限
C. 若删除文件F3，则F2的引用计数值减1
D. 进程 $\mathrm{P}_1$ 读取F1时需要提供F1的绝对路径作为系统调用参数
08. 在树形目录结构中，文件已被打开后，对文件的访问采用（ ）。
A. 文件符号名
B. 从根目录开始的路径名
C. 从当前目录开始的路径名
D. 文件描述符
09. 在访问文件时，需要根据文件名对目录文件进行检索，其检索性能主要由（ ）决定。
I. 文件大小
II. 目录项数量
III. 目录项的大小
IV. 目录项在目录中的位置
A. I、II和III
B. II、III和IV
C. I、III和IV
D. I、II和IV
10. 在计算机中，不允许两个文件名重名主要指的是（ ）。
A. 不同磁盘的不同目录下
B. 不同磁盘里的同名目录下
C. 同一个磁盘的不同目录下
D. 同一个磁盘的同一目录下
11. 文件系统实现按名存取主要是靠（ ）实现的。
A. 查找位示图
B. 查找文件目录
C. 查找作业表
D. 地址转换机构
12. 在一个文件系统中，FCB占64B，盘块大小为1KB，采用一级目录。假定文件目录中有3200个目录项，则查找一个文件平均需要（ ）次访问磁盘。
A. 50
B. 54
C. 100
D. 200
13. 在一个采用索引节点的文件系统中，目录项分为文件名和索引节点编号两部分，文件名和索引节点编号各占8B，盘块大小为1KB，采用一级目录。假定文件目录中有3200个目录项，则读入一个文件的索引节点平均需要（ ）次访问磁盘。
A. 25
B. 26
C. 51
D. 52
14.【2009 统考真题】设文件 F1 的当前引用计数值为 1，先建立文件 F1 的符号链接（软链接）文件 F2，再建立文件 F1 的硬链接文件 F3，然后删除文件 F1。此时，文件 F2 和文件 F3 的引用计数值分别是（ ）。
A. 0.1
B. 1.1
C. 1.2
D. 2.1
15.【2010 统考真题】设置当前工作目录的主要目的是（ ）。
A. 节省外存空间
B. 节省内存空间
C. 加快文件的检索速度
D. 加快文件的读/写速度
16.【2017 统考真题】若文件 f1 的硬链接为 f2，两个进程分别打开 f1 和 f2，获得对应的文件描述符为 fd1 和 fd2，则下列叙述中正确的是（ ）。
I. f1 和 f2 的读/写指针位置保持相同
II. f1 和 f2 共享同一个内存索引节点
III. fd1 和 fd2 分别指向各自的用户打开文件表中的一项
A. 仅 III
B. 仅 II、III
C. 仅 I、II
D. I、II和III
17.【2021 统考真题】若目录 dir 下有文件 file1，则为删除该文件内核不必完成的工作是（ ）。
A. 删除 file1 的快捷方式
B. 释放 file1 的文件控制块
C. 释放 file1 占用的磁盘空间
D. 删除目录 dir 中与 file1 对应的目录项
<!-- page: 300 -->
# 二、综合应用题
01. 设某文件系统采用两级目录的结构，主目录中有 10 个子目录，每个子目录中有 10 个目录项。在同样多目录的情况下，若采用单级目录结构，所需平均检索目录项数是两级目录结构平均检索目录项数的多少倍？
02. 有文件系统如下图所示，图中的框表示目录，圆圈表示普通文件。
1）可否建立 F 与 R 的链接？试加以说明。
2）能否删除 R？为什么？
3）能否删除 N？为什么？
03. 某树形目录结构的文件系统如下图所示。该图中的方框表示目录，圆圈表示文件。
1）可否进行下列操作？
① 在目录 D 中建立一个文件，取名为 A。
② 将目录 C 改名为 A。
2）若 E 和 G 分别为两个用户的目录：
① 在一段时间内用户 G 主要使用文件 S 和 T。为简化操作和提高速度，应如何处理？
② 用户 E 欧时文件 I 加以保护，不许别人使用，能否实现？如何实现？
04. 有一个文件系统如图 A 所示。图中的方框表示目录，圆圈表示普通文件。根目录常驻内存，目录文件组织成链接文件，不设 FCB，普通文件组织成索引文件。目录表指示下一
<!-- page: 301 -->
级文件名及其磁盘地址（各占2B，共4B）。下级文件是目录文件时，指示其第一个磁盘块地址。下级文件是普通文件时，指示其FCB的磁盘地址。每个目录的文件磁盘块的最后4B供拉链使用。下级文件在上级目录文件中的次序在图中为从左至右。每个磁盘块有512B，与普通文件的一页等长。
图A 某树形结构文件系统框图
普通文件的FCB组织如图B所示。其中，每个磁盘地址占2B，前10个地址直接指示该文件前10页的地址。第11个地址指示一级索引表地址，一级索引表中的每个磁盘地址指示一个文件页地址；第12个地址指示二级索引表地址，二级索引表中的每个地址指示一个一级索引表地址；第13个地址指示三级索引表地址，三级索引表中的每个地址指示一个二级索引表地址。请问：
[tbl-139.md](tbl-139.md)
图B FCB组织
关注公众号【考研小舟】
免费考研资料&无水印PDF
1）一个普通文件最多可有多少个文件页？
2）若要读文件J中的某一页，最多启动磁盘多少次？
3）若要读文件W中的某一页，最少启动磁盘多少次？
4）根据3)，为最大限度地减少启动磁盘的次数，可采用什么方法？此时，磁盘最多启动多少次？
05. 在某个文件系统中，外存为硬盘。物理块大小为 512B，有文件 A 包含 598 条记录，每条记录占 255B，每个物理块放 2 条记录。文件 A 所在的目录如下图所示。文件目录采用多级树形目录结构，由根目录节点、作为目录文件的中间节点和作为信息文件的树叶组成，
<!-- page: 302 -->
每个目录项占127B，每个物理块放4个目录项，根目录的第一块常驻内存。试问：
1）若文件的物理结构采用链式存储方式，链指针地址占2B，则要将文件A读入内存，至少需要存取几次硬盘？
2）若文件为连续文件，则要读文件A的第487条记录至少要存取几次硬盘？
## 4.2.8 答案与解析
### 一、单项选择题
#### 01. C
实现用户对文件的按名存取，系统先利用用户提供的文件名形成检索路径，对目录进行检索。在顺序检索中，路径名的一个分量未找到，说明路径名中的某个目录或文件不存在，不需要继续检索，选项C正确。目录的查询方式有顺序检索法和散列法两种，散列法并不适用于所有的目录结构，而且有冲突和溢出的缺点，解决的开销也较大，因此通常更多采用的是顺序检索法，选项A错误。在树形目录中，为了加快文件检索速度，可设置当前目录，于是文件路径可以从当前目录开始查找，选项B错误。在顺序检索法查找完成后，得到的是文件的逻辑地址，选项D错误。
#### 02. A
相对路径是从当前目录出发到所找文件通路上所有目录名和数据文件名用分隔符连接起来而形成的，注意与绝对路径的区别。
#### 03. C
在文件系统中采用多级目录结构后，符合了多层次管理的需要，提高了文件查找的速度，还允许用户建立同名文件。因此，多级目录结构的采用解决了命名冲突。
#### 04. A
在单级目录文件中，每当新建一个文件时，必须先检索所有的目录项，以保证新文件名在目录中是唯一的。所以单级目录结构无法解决文件重名问题。
#### 05. D
文件在磁带上通常采用连续存放方法，在硬盘上通常不采用连续存放方法，在内存上采用随机存放方法，选项I错误。对文件的访问控制，常由用户访问权限和文件属性共同限制，选项II错误。在树形目录结构中，对于不同用户的文件，文件名可以不同也可以相同，选项III错误。防止文件受损常采用备份的方法，而存取控制矩阵方法用于多用户之间的存取权限保护，选项IV错误。
#### 06. A
建立F2时，F1和F2的引用计数值都变为2。建立F3时，符号链接文件的引用计数值不受被链接文件的影响，始终为1，所以F1和F3的引用计数值为2和1。删除F2时，F1的引用计数值变为 $2 - 1 = 1$ ，F3的引用计数值仍保持不变，因此F1、F3的引用计数值分别是1、1。
#### 07. A
<!-- page: 303 -->
文件F2是F1的硬链接文件，指向同一个索引节点，当进程 $\mathrm{P_1}$ 第一次打开F1时，会将磁盘上的索引节点读入内存，之后进程 $\mathrm{P_1}$ 打开F2及进程 $\mathrm{P_2}$ 打开F1和F2都共享之前已读入内存的索引节点，选项A正确。$\mathrm{P_1}$ 和 $\mathrm{P_2}$ 对同一个文件的访问权限可能有所不同，选项B错误。F3是F2的软链接文件，删除F3不影响F2的引用计数值，选项C错误。读取F1只需传入F1在进程 $\mathrm{P_1}$ 中的文件描述符（F1在进程 $\mathrm{P_1}$ 的进程打开文件表中的索引号），并不需要其路径名，选项D错误。
08. D
文件被打开后，系统为每个打开的文件分配一个文件描述符（索引号），用来标识该文件。之后用户不再使用文件名，而使用文件描述符，来对该文件进行读、写、定位等操作。
09. B
文件大小与对目录进行检索无关。目录项数量越多，检索目录时的平均比较次数就越多，影响检索性能；目录项的大小越大，占用的盘块就越多，I/O时间也就越长，影响检索性能；目录项在目录中的位置不同，可能导致不同的访问路径，影响检索性能。
10. D
A、B和C项的同名文件都有不同的路径名，因此不会造成文件名重名问题。在同一个磁盘的同一目录下，若两个文件名重名，则它们具有相同的路径名，因此无法区别。
11. B
文件目录是实现按名存取的关键，通过查找目录可以获得文件的物理地址和其他属性。
12. C
FCB占64B，盘块大小为1KB，一个盘块能存放 $1024 / 64 = 16$ 个FCB。文件目录有3200个目录项，即3200个FCB（每个目录项一个FCB），文件目录需要占用 $3200 / 16 = 200$ 个盘块。查找一个文件需要在200个盘块中顺序查找目标FCB，平均查找次数为 $200 / 2 = 100$，即平均访问磁盘的次数。
**注意**
在操作系统教材中，平均查找长度通常描述为“总长度/2”；在数据结构教材中，平均查找长度通常描述为“(总长度+1)/2”，相对而言后者更严谨。
13. B
一个目录项的大小是16B，一个磁盘块可以存放 $1024\mathrm{B} / 16\mathrm{B} = 64$ 个目录项，存放3200个目录项共需50个磁盘块。因此，找到一个文件对应的目录项平均读磁盘的次数为 $50 / 2 = 25$，之后根据对应目录项的索引节点编号再启动磁盘读入索引节点，总读磁盘次数为26。
14. B
建立符号链接时，引用计数值直接设置为1，不受被链接文件的影响；建立硬链接时，引用计数值加1。删除文件时，删除操作对于符号链接是不可见的，这并不影响文件系统，当以后再通过符号链接访问时，发现文件不存在，直接删除符号链接；但对于硬链接则不可直接删除，引用计数值减1，若值不为0，则不能删除此文件，因为还有其他硬链接指向此文件。
当建立F2时，F1和F2的引用计数值都为1。当再建立F3时，F1和F3的引用计数值就都变成了2。当后来删除F1时，F3的引用计数值为 $2 - 1 = 1$，F2的引用计数值不变。
15. C
当一个文件系统含有多级目录时，每访问一个文件，都要使用从树根开始到树叶为止、包括各中间节点名的全路径名。当前目录也称工作目录，进程对各个文件的访问都相对于当前目录进行，而不需要从根目录一层一层地检索，加快了文件的检索速度。选项A、B都与相对目录无关；
<!-- page: 304 -->
选项 D，文件的读/写速度取决于磁盘的性能。