一. 目录的基本概念
上文说过，FCB （文件控制块）的有序集合称为文件目录，一个 FCB 就是一个文件目录项。与文件管理系统和文件集合相关联的是文件目录，包含有关文件属性、位置和所有权。
- 目录管理实现“按名存取”。
- 目录存取效率影响到系统性能，所以要提高目录检索速度。
- 多用户系统，允许多用户共享一个文件，因此目录提供用于控制访问文件的信息。
二. 目录结构
单级目录
- 早期 OS 不支持多级目录结构，整个文件系统只建立一张目录表，每个文件占一个目录项。如下图：
- 单级目录实现了“按名存取”,但是不允许文件重名。
- 在创建一个文件时，需要先检查目录表中有没有重名 文件，确定不重名后才能允许建立文件，并将新文件对应的目录项插入目录表中。
- 显然，单级目录结构不适用于多用户操作系统。
两级目录
- 早期的多用户操作系统,采用两级目录结构。分为主文件目录(MFD,MasterFileDirectory)和用户文件目录(UFD,UserFlie Directory)。
- 主文件目录记录用户名及相应用户文件目录的存放位置
- 用户文件目录由该用户的文件FCB组成
- 允许不同用户的文件重名。文件名虽然相同,但是对应的其实是不同的文件
- 两级目录结构允许不同用户的文件重名,也可以在目录上实现实现访问限制(检查此时登录的用户名是否匹配)。但是两级目录结构依然缺乏灵活性,用户不能对自己的文件进行分类
树形目录结构（多级目录结构）
- 可以明显地提高对目录的检索速度和文件系统的性能。
当用户要访问某个文件时,用文件的路径名标识文件,文件路径名是个字符串,由从根目录出发到所找文件通路上所有目录名与数据文件名用分隔符“/”链接而成。
- 绝对路径。从根目录出发的路径称为绝对路径,系统中的每个文件都有唯一的路径名。
- 当前目录。由于一个进程在运行时,其所访问的文件大多局限于某个范围,当层次较多时,每次从根目录查询会浪费时间,于是可为每个进程设置一个当前目录(又称工作目录),此时进程对各文件的访问都只须相对于当前目录而进行。
当用户要访问某个文件时,使用相对路径名标识文件
- 相对路径。由从当前目录出发到所找文件通路上所有目录名与数据文件名用分隔符“/”链接而成。下图是Linux操作系统的目录结构,“/dev/hda”就是一个绝对路径。若当前目录为“bin”,则“1s”就是一个相对路径,其中符号“”表示当前工作目录。
- 树形目录结构可以很方便地对文件进行分类,层次结构清晰,也能够更有效地进行文件的管理和保护。
- 容易赋予不同的存取权限。
- 但是,在树形目录中查找一个文件,需要按路径名逐级访问中间节点,增加了磁盘访问次数,这无疑会影响查询速度。目前,大多数操作系统如UNIX、Linux 和 Windows系统都采用了树形文件目录。
无环图目录结构
树形目录结构能便于实现文件分类,但不便于实现文件共享
无环图目录结构允许目录共享子目录或文件,同一个文件或子目录可以出现在两个或多个目录中。
- 可为每个共享节点设置一个共享计数器
- 每当图中增加对该节点的共享链时,计数器加1;
- 每当某用户提出删除该节点时,计数器减1。
仅当共享计数器为0时,才真正删除该节点,否则仅删除请求用户的共享链。无环图目录结构方便地实现了文件的共享,但使得系统的管理变得更加复杂。
三. 目录的操作
- 搜索。用户使用文件，搜索目录以找到该文件对应目录。
- 创建文件。当创建一个新文件时,需要在目录中增加一个目录项。
- 删除文件。当删除一个文件时,需要在目录中删除相应的目录项。
- 创建目录。在树形目录结构中,用户可创建自己的用户文件目录,并可再创建子目录。
- 删除目录。有两种方式
- ①不删除非空目录,删除时要先删除目录中的所有文件,并递归地删除子目录。
- ②可删除非空目录,目录中的文件和子目录同时被删除。
- 移动目录。将文件或子目录在不同的父目录之间移动,文件的路径名也会随之改变。
- 显示目录。用户可以请求显示目录的内容,如显示该用户目录中的所有文件及属性。
- 修改目录。某些文件属性保存在目录中,因而这些属性的变化需要改变相应的目录项。
四. *目录实现
在访问一个文件时,操作系统利用路径名找到相应目录项,目录项中提供了查找文件磁盘块所需要的信息。目录实现的基本方法有线性列表和哈希表两种,要注意目录的实现就是为了查找,因此线性列表实现对应线性查找,哈希表的实现对应散列查找。
线性表
最简单的目录实现方法是,采用文件名和数据块指针的线性列表。
- 当创建新文件时,必须首先搜索目录以确定没有同名的文件存在,然后在目录中增加一个新的目录项。
- 当删除文件时,则根据给定的文件名搜索目录,然后释放分配给它的空间。
- 重用目录项多种方法
- 可以将目录项标记为不再使用,或将它加到空闲目录项的列表上
- 还可以将目录的最后一个目录项复制到空闲位置,并减少目录的长度。
- 采用链表结构可以减少删除文件的时间。
- 线性列表的优点在于实现简单,不过由于线性表的特殊性,查找比较费时。
哈希表
除了采用线性列表存储文件目录项,还可以采用哈希数据结构。
- 哈希表。根据文件名得到一个值,并返回一个指向线性列表中元素的指针。
- 这种方法的优点是查找非常迅速,插入和删除也较简单,不过需要一些措施来避免冲突(两个文件名称哈希到同一位置)。
目录查询是通过在磁盘上反复搜索完成的，需要不断地进行I/O操作，开销较大。所以如前 所述，为了减少I/O操作，将当前使用的文件目录复制到内存，以后要使用该文件时只需在内存 中操作，因此降低了磁盘操作次数，提高了系统速度。
五. 文件共享
共享文件使得多个用户可以共享同一个文件，系统只保留一个文件副本。如果文件库共享不能实现，那么每个用户都需要保留一个副本，会造成极大地空间资源浪费。
基于无环图目录结构可以实现文件共享，建立链接关系时，必须将被共享文件的物理地址（盘块号）复制到相应的目录。如果某个用户向该文件添加数据，且需要增加新盘块，那么这些新增的盘块只会出现在执行操作的目录中，对其他共享用户不可见。
基于索引节点的共享方式（硬链接）
硬链接是基于索引节点的共享方式，将文件的物理地址和属性等信息存放在索引节点中，文件目录中只设置文件名和指向索引节点的指针。
- 索引节点中还有一个 链接计数 count，也称引用计数。表示链接到本索引节点（即文件）上的用户目录项的数目。
count = 2 表示有两个用户目录项链接到本文件。即有两个用户共享该文件。
- 当用户 A 创建新文件 File，此时 count = 1 ，A 是该文件的所有者。
- 如果用户 B 需要共享该文件，则 B 的目录中增加一个目录项，同时 count++。
- 当 count≥2， 用户 A 不再需要该文件，只能删去自己目录的相应的目录项，不能删去文件。【其他共享用户后续可能还需要使用】
- 当 count = 1，此时文件占有者不再需要该文件，则可以一并删除文件和对应目录项。
利用符号链接实现文件共享（软链接）
- 符号链接（软链接）：系统创建一个 LINK 类型的文件 L（仅含有被链接文件文件 F 的路径名），将文件 L 写入用户 B 的目录，以实现 B 的目录与文件 F 的链接。
类似于 Windows 系统中的快捷方式。
- 实现：当用户 B 访问 L 文件，OS 会识别到 LINK 类型，根据其中记录的路径名查询 F 文件，然后进行读/写操作，实现 B 对 F 文件的共享。
- 软链接方式删除共享文件后情况
- 只有文件主拥有指向文件索引节点的指针。
- 共享该文件的用户只有该文件的路径名，没有指向索引节点的指针。
- 文件主删除共享文件后，其他共享用户试图通过符号链接访问该文件，会出现访问失败，然后将符号链接删除，此时不会产生任何影响。
- 由于符号链接记录的是文件路径名，当其他用户读共享文件时，系统会根据路径名依次查找目录，直至找到该文件的索引节点。
- 因此，其他用户访问共享文件可能需要多次读磁盘，增大了访问文件的开销；同时，符号链接作为一个文件，它的索引节点也需要占用一定的磁盘空间。
- 可见，查找速度 V硬链接 > V软链接
