26考研——文件管理_文件目录（4）

408答疑

文章目录

二、文件目录
- 1、目录的作用与结构
- - 1.1、目录的基本概念
  - 1.2、目录的组织形式
  - - 1.2.1、单级目录结构
    - 1.2.2、两级目录结构
    - 1.2.3、多级（树形）目录结构
    - 1.2.4、无环图目录结构
  - 1.3、目录的实现方式
  - - 1.3.1、线性列表
    - 1.3.2、哈希表
- 2、文件共享与链接
- - 2.1、基于索引节点的共享方式（硬链接）
  - 2.2、利用符号链实现文件共享（软链接）
  - 2.3、符号链接与硬链接的比较
五、参考资料
- 鲍鱼科技课件
- 26王道考研书
- 小林coding

二、文件目录

1、目录的作用与结构

1.1、目录的基本概念

FCB 的有序集合称为文件目录，一个 FCB 就是一个文件目录项。
与文件管理系统和文件集合相关联的是文件目录，它包含有关文件的属性、位置和所有权等。
目录管理的基本要求：
- 从用户的角度看，目录在用户（应用程序）所需要的文件名和文件之间提供一种映射，所以目录管理要实现“按名存取”；
- 目录存取的效率直接影响到系统的性能，所以要提高对目录的检索速度；
- 在多用户系统中，应允许多个用户共享一个文件，因此目录还需要提供用于控制访问文件的信息。
此外，应允许不同用户对不同文件采用相同的名字，以便于用户按自己的习惯给文件命名，目录管理通过树形结构来解决和实现。
目录的操作：
- 搜索：当用户使用一个文件时，需要搜索目录，以找到该文件的对应目录项。
- 创建文件：当创建一个新文件时，需要在目录中增加一个目录项。
- 删除文件：当删除一个文件时，需要在目录中删除相应的目录项。
- 创建目录：在树形目录结构中，用户可创建自己的用户文件目录，并可再创建子目录。
- 删除目录（有两种方式）：
  1. 不删除非空目录，删除时要先删除目录中的所有文件，并递归地删除子目录。
  2. 可删除非空目录，目录中的文件和子目录同时被删除。
- 移动目录：将文件或子目录在不同的父目录之间移动，文件的路径名也会随之改变。
- 显示目录：用户可以请求显示目录的内容，如显示该用户目录中的所有文件及属性。
- 修改目录：某些文件属性保存在目录中，因此这些属性的变化需要改变相应的目录项。

1.2、目录的组织形式

1.2.1、单级目录结构

在整个文件系统中只建立一张目录表，每个文件占一个目录项，如下图所示。
单级目录结构实现了“按名存取”，但是存在查找速度慢、文件不允许重名、不便于文件共享等缺点，而且对于多用户的操作系统显然是不适用的。

注意：

当建立一个新文件时，必须先检索所有目录项，以确保没有“重名”的情况，然后在该目录中增设一项，将新文件的属性信息填入该项。
当访问一个文件时，先按文件名在该目录中查找到相应的 FCB，经合法性检查后执行相应的操作。
当删除一个文件时，先从该目录中找到该文件的目录项，回收该文件所占用的存储空间，然后清除该目录项。

1.2.2、两级目录结构

为了克服单级目录所存在的缺点，可以采用两级方案，将文件目录分成主文件目录（Master File Directory，MFD）和用户文件目录（User File Directory，UFD）两级，如下图所示。
主文件目录：主文件目录项记录用户名及相应用户文件目录所在的存储位置。
用户文件目录：
- 用户文件目录项记录该用户所有文件的 FCB。
- 当某用户欲对其文件进行访问时，只需搜索该用户对应的 UFD，这既解决了不同用户文件的“重名”问题，又在一定程度上保证了文件的安全。
优点：
- 两级目录结构提高了检索的速度，解决了多用户之间的文件重名问题，文件系统可以在目录上实现访问限制。
- 但是两级目录结构缺乏灵活性，不能对文件分类。

1.2.3、多级（树形）目录结构

将两级目录结构加以推广，就形成了树形目录结构，如下图所示。它可以明显地提高对目录的检索速度和文件系统的性能。
- 路径：当用户要访问某个文件时，用文件的路径名标识文件，文件路径名是个字符串，由从根目录出发到所找文件通路上所有目录名与数据文件名用分隔符 “/” 链接而成。
- 绝对路径：从根目录出发的路径称为绝对路径，系统中的每个文件都有唯一的路径名。
- 当前目录：一个进程在运行时，其所访问的文件大多局限于某个范围，当层次较多时，每次从根目录查询会浪费时间，因此可为每个进程设置一个当前目录（也称工作目录），此时进程对各文件的访问都只需相对于当前目录而进行。
- 相对路径：当用户要访问某个文件时，使用相对路径名标识文件，相对路径由从当前目录出发到所找文件通路上所有目录名与数据文件名用分隔符 “/” 链接而成。
- 上图所示是 Linux 操作系统的树形目录结构，“/dev/hda” 就是一个绝对路径。若当前目录为 “/bin”，则 “./ls” 就是一个相对路径，其中符号 “.” 表示当前工作目录。
通常，每个用户都有各自的“当前目录”，登录后自动进入该用户的“当前目录”。操作系统提供一个专门的系统调用，供用户随时改变“当前目录”。例如，在 UNIX 系统中，“/etc/passwd” 文件就包含有用户登录时默认的“当前目录”，可用 “cd” 命令改变“当前目录”。
优点：
- 树形目录结构可以很方便地对文件进行分类，层次结构清晰，也能够更有效地进行文件的管理和保护。
- 在树形目录中，不同性质、不同用户的文件，可以分别呈现在系统目录树的不同层次或不同子树中，很容易地赋予不同的存取权限。
缺点：在树形目录中查找一个文件，需要按路径名逐级访问中间节点，增加了磁盘访问次数，这无疑会影响查询速度。
目前，大多数操作系统如 UNIX、Linux 和 Windows 系统都采用了树形文件目录。

1.2.4、无环图目录结构

树形目录结构能便于实现文件分类，但不便于实现文件共享，为此在树形目录结构的基础上增加一些指向同一节点的有向边，使整个目录成为一个有向无环图，如下图所示。
- 这种结构允许目录共享子目录或文件，同一个文件或子目录可以出现在两个或多个目录中。
- 当某用户要求删除一个共享节点时，若系统只是简单地将它删除，则当另一共享用户需要访问时，会因无法找到这个文件而发生错误。
  - 为此，可为每个共享节点设置一个共享计数器，每当图中增加对该节点的共享链时，计数器加 1；每当某用户提出删除该节点时，计数器减 1。
  - 仅当共享计数器为 0 时，才真正删除该节点，否则仅删除请求用户的共享链。
无环图目录结构方便地实现了文件的共享，但使得系统的管理变得更加复杂。

1.3、目录的实现方式

在访问一个文件时，操作系统利用路径名找到相应目录项，目录项中提供了查找文件磁盘块所需要的信息。
目录实现的基本方法有线性列表和哈希表两种，要注意目录的实现就是为了查找，因此线性列表实现对应线性查找，哈希表的实现对应散列查找。

1.3.1、线性列表

最简单的目录实现方法是，采用文件名和数据块指针的线性列表。
当创建新文件时，必须首先搜索目录以确定没有同名的文件存在，然后在目录中增加一个新的目录项。
当删除文件时，则根据给定的文件名搜索目录，然后释放分配给它的空间。
- 当要重用目录项时有许多种方法：可以将目录项标记为不再使用；或将它加到空闲目录项的列表上；还可以将目录的最后一个目录项复制到空闲位置，并减少目录的长度。
- 采用链表结构可以减少删除文件的时间。
线性列表的优点在于实现简单，不过由于线性表的特殊性，查找比较费时。

1.3.2、哈希表

哈希表根据文件名得到一个值，并返回一个指向线性列表中元素的指针。
优点：查找非常迅速，插入和删除也较简单。
缺点：需要一些措施来避免冲突（两个文件名称哈希到同一位置）。

目录查询优化：

目录查询是通过在磁盘上反复搜索完成的，需要不断地进行 I/O 操作，开销较大。
为了减少 I/O 操作，将当前使用的文件目录复制到内存，以后要使用该文件时只需在内存中操作，因此降低了磁盘操作次数，提高了系统速度。

2、文件共享与链接

文件共享使多个用户共享同一个文件，系统中只需保留该文件的一个副本。若系统不能提供共享功能，则每个需要该文件的用户都要有各自的副本，会造成对存储空间的极大浪费。
以无环图目录为例，基于该结构可以实现文件共享，当建立链接关系时，必须将被共享文件的物理地址（盘块号）复制到相应的目录。如果某个用户向该文件添加新数据，且需要增加新盘块，那么这些新增的盘块只出现在执行操作的目录中，对其他共享用户是不可见的。

2.1、基于索引节点的共享方式（硬链接）

硬链接是基于索引节点的共享方式，它将文件的物理地址和属性等信息不再放在目录项中，而是放在索引节点中，在目录中只设置文件名及指向相应索引节点的指针。
如下图所示，在用户 A 和 B 的目录中，都设置有指向共享文件的索引节点指针。
- 在索引节点中还有一个链接计数 count，也称引用计数，表示链接到本索引节点（文件）上的用户目录项的数量。
- 当 $co u n t = 2$ 时，表示有两个用户目录项链接到本文件上，即有两个用户共享此文件。
文件创建与共享：
- 当用户 A 创建一个新文件时，他是该文件的所有者，此时将 count 置为 1。
- 当用户 B 要共享此文件时，在 B 的目录中增加一个目录项，并设置一个指针指向该文件的索引节点。此时，文件主仍是用户 A， $co u n t = 2$ 。
文件删除：
- 当用户 A 不再需要此文件时，能否直接将其删除？
  - 答案是否定的。
  - 因为若删除该文件，必然也删除该文件的索引节点，这样便使用户 B 的指针悬空，而 B 可能正在此文件上执行写操作，此时将因此半途而废。
  - 因此用户 A 不能删除此文件，只是将该文件的 count 减 1，然后删除自己目录中的相应目录项。
  - 用户 B 仍可以使用该文件。
- 当 count = 0 时，表示没有用户使用该文件，才删除该文件。
如下图所示为文件共享中的链接计数。

2.2、利用符号链实现文件共享（软链接）

为使用户 B 能共享用户 A 的一个文件 F，可由系统创建一个 LINK 类型的新文件 L，并将文件 L 写入用户 B 的目录，以实现 B 的目录与文件 F 的链接。
文件 L 中只含有被链接文件 F 的路径名，如下图所示。
- 这种链接方法称为符号链接或软链接，它类似于 Windows 系统中的快捷方式。
- 当用户 B 访问文件 L 时，操作系统看到要读的文件属于 LINK 类型，则根据其中记录的路径名去查询文件 F，然后对 F 进行读/写操作，从而实现用户 B 对文件 F 的共享。
文件主与共享用户：
- 利用符号链方式实现文件共享时，只有文件主才拥有指向其索引节点的指针。
- 而共享该文件的其他用户只有该文件的路径名，并不拥有指向其索引节点的指针。这样，也就不会发生在文件主删除一个共享文件后留下一个悬空指针的情况。
文件删除：当文件主将一个共享文件删除后，若其他用户又试图通过符号链去访问它时，则会访问失败，于是再将符号链删除，此时不会产生任何影响。
访问开销：
- 在符号链的共享方式中，当其他用户读共享文件时，系统根据文件路径名依次查找目录，直至找到该文件的索引节点。
- 因此，每次访问共享文件时，都可能要多次地读盘，增大了访问文件的开销。
- 此外，符号链接也是一个文件，其索引节点也要耗费一定的磁盘空间。