【操作系统·考研】目录

1.概述

与文件管理系统和文件集合相关联的是文件目录，它包含有关文件的属性、位置和所有权等。

2.目录的结构

2.1 单级目录结构

在整个FS中只建立一张目录表，每个文件占一个目录项。
当访问一个文件时，先根据文件名在目录表中找到相应的FCB，经合法性校验后，再去执行相应的访问操作。
当创建一个文件时，先根据文件名在目录表中检索一遍，以确保没有重名的情况，然后再目录表中添加新的表项，将新文件的属性信息填入其中。
当删除一个文件时，先根据文件名在目录表中找到相应的FCB，回收该文件占据的存储空间，然后移除掉该文件目录项。

该方式实现了按名存取，但其查找速度慢，文件不允许重名，不便于文件共享，且不适用于多用户的OS。

2.2 两级目录结构

将文件目录分为主文件目录(Master File Dirctory，MFD)和用户文件目录(User File Directory，UFD)两级。
主文件目录用于记录用户名及其相应的用户文件目录所在的存储位置；用户文件目录则记录该用户的文件的FCB信息。
当用户搜索某一文件时，只需要在其UFD中进行搜索即可，这在一定程度上避免了文件的重名问题。

两级目录结构尽管提高了文件的检索速度，但是无法对文件进行分类，缺乏灵活性。

FS采用多级目录的目的是：满足多层次管理的需要、提高文件的查找速度、允许用户创建同名文件。

2.3 树形目录结构

用文件的路径标识文件，文件路径名是一个字符串，由从根路径出发到所找文件通路上所有目录名与数据文件名用分割符“/”分隔开(不同OS的分隔符可能不同)，然后拼接而成。如：
从根目录出发的路径称为绝对路径，相对于当前工作目录出发的路径则称为相对路径。

在该树形目录结构下，层次结构清晰，能进行更有效的文件管理和保护，不同用户、不同性质的文件可呈现在系统目录树下的不同层次或不同子树中，很容易被赋予不同的存取权限。
但是在搜索文件时，需要根据路径名逐级访问中间节点，这增加了磁盘访问次数。
目前，Windows、UNIX、Linux系统均采用了树形文件目录。

2.4 无环图目录结构

在树形目录结构的基础之上，增加了指向同一结点的有向边，使整个目录成为一个有向无环图，以便于实现文件共享。
系统会为每个共享结点设置一个共享计数器，每当图中增加对该结点的共享链时，该计数值+1，若某用户提出删除该结点时，计数值-1，当计数值减至0时，才会真正删除该结点，否则就仅删除用户对该结点的共享链。
共享文件不同于文件拷贝，每个用户所看到的是该文件的原始文件，对其修改也是在本体上进行的。

该结构虽然方便了文件的共享，但使系统的管理更加复杂。

3.目录的操作

搜索：当用户使用一个文件时，需要先搜索目录，以找到该文件对应的目录项。
创建文件：当创建一个文件时，需要在目录中增加一个目录项。
删除文件：当删除一个文件时，需要在目录中删除相应的目录项。
创建目录：在树形目录结构中，用户可以创建自己的用户文件目录，还能再继续创建子目录。
删除目录：
- 不删除非空目录：删除时必须先珊瑚目录中的所有文件，并递归地删除子目录。
- 删除非空目录：将目录中的文件和子目录一并删除。
移动目录：将文件或子目录在不同的父目录之间移动，文件的路径名也随之改变。
显示目录：用户可以请求显示目录的内容。
修改目录：某些文件属性保存在目录中，因而这些属性的变化将改变相应的目录项。

3.目录的实现

目录的实现就是为了实现文件的查找。

3.1 线性列表

最简单的目录实现方法是：采用文件名和数据块指针的线性列表。
创建文件时，会先检索目录以确定是否有同名文件已经存在，若没有则创建文件；删除文件时，同样先会检索目录以确定目标文件是否存在，若存在则删除。

对于删除文件的优化：可以将删除后的条目标记为不再使用或移入空闲链表中，还可以将最后一个条目复制到此，当然使用链表结构可大大节省删除文件的时间。

该方式的优点是实现简单，缺点是查找比较费时。

3.2 哈希表

哈希表会根据文件名通过散列函数得到一个值，并返回指向线性列表中的元素的指针。

该方式的优点是查找、删除比较简单，缺点是可能存在冲突(两个不同的文件名映射到了同一位置)。

4.文件的共享

4.1 基于索引结点的共享方式(硬链接)

在树形结构的目录中，当有两个或多个用户要共享同一个子目录或文件时，必须将共享文件或子目录链接到两个或多个用户的目录中去，才能方便的找到该文件。
在这种共享方式中，文件的物理地址和文件的其他属性信息将被存放在索引节点中，而不存放在目录项中。在索引节点中还配置了一个链接技术count，其作用和前面讲到的共享计数器的作用一致，这里不再赘述。

尽管多个进程可能同时指向同一个文件的索引节点，但进程各自独立维护自己的文件描述符fd(包含的信息：每个进程对该文件的读写位置指针等)。fd1和fd2分别指向进程自己的用户打开文件表中的表项，这两个用户打开文件表的表项又同时指向同一个系统打开文件表的表项。

4.2 利用符号链实现文件共享(软链接)

如果用户B想向用户A共享一个文件F，那么它将通知系统创建一个LINK类型的文件，同样取名为F，然后将文件创建在用户A的目录中去，新创建的文件包含被链接的文件的路径名。当用户A访问该LINK类型的文件时，发现为该文件为LINK类型，于是便根据该文件的路径名找到真正的文件F，然后对它进行读取。
该方式下，只有文件所有者拥有指向文件F的索引节点指针，而共享该文件的用户没有，这样，当宿主删除源文件F时，文件就会真被删除，而其他共享用户再次访问则会失败，并自动撤销该共享的符号链。