======第六章文件管理======（2）：https://developer.aliyun.com/article/1415865
6.3.4 索引分配
- 单级索引分配
链接分配方式虽然解决了连续分配方式所存在的问题，但又出现了下述另外两个问题：
(1) 不能支持高效的直接存取。要对一个较大的文件进行直接存取，须首先在 FAT 中顺 序地查找许多盘块号。
(2) FAT 需占用较大的内存空间。由于一个文件所占用盘块的盘块号是随机地分布在 FAT 中的，因而只有将整个 FAT 调入内存，才能保证在 FAT 中找到一个文件的所有盘块号。 当磁盘容量较大时，FAT 可能要占用数兆字节以上的内存空间，这是令人难以接受的。 事实上，在打开某个文件时，只需把该文件占用的盘块的编号调入内存即可，完全没 有必要将整个 FAT 调入内存。为此，应将每个文件所对应的盘块号集中地放在一起。索引 分配方法就是基于这种想法所形成的一种分配方法。它为每个文件分配一个索引块(表)，再 把分配给该文件的所有盘块号都记录在该索引块中，因而该索引块就是一个含有许多盘块 号的数组。在建立一个文件时，只需在为之建立的目录项中填上指向该索引块的指针。图 6-12 示出了磁盘空间的索引分配图。
索引分配方式支持直接访问。当要读文件的第 i 个盘块时，可以方便地直接从索引块中 找到第 i 个盘块的盘块号；此外，索引分配方式也不会产生外部碎片。当文件较大时，索引 分配方式无疑要优于链接分配方式。
索引分配方式的主要问题是：
可能要花费较多的外存空间。每当建立一个文件时，便 须为之分配一个索引块，将分配给该文件的所有盘块号记录于其中。但在一般情况下，总 是中、小型文件居多，甚至有不少文件只需 1～2 个盘块，这时如果采用链接分配方式，只 需设置 1～2 个指针。如果采用索引分配方式，则同样仍须为之分配一索引块。通常是采用 一个专门的盘块作为索引块，其中可存放成百个、甚至上千个盘块号。可见，对于小文件 采用索引分配方式时，其索引块的利用率将是极低的。
多级索引分配
当 OS 为一个大文件分配磁盘空间时，如果所分配出去的盘块的盘块号已经装满一个索引块时，OS 便为该文件分配另一个索引块，用于将以后继续为之分配的盘块号记录于其中。 依此类推，再通过链指针将各索引块按序链接起来。显然，当文件太大，其索引块太多时， 这种方法是低效的。此时，应为这些索引块再建立一级索引，称为第一级索引，即系统再 分配一个索引块，作为第一级索引的索引块，将第一块、第二块……等索引块的盘块号填 入到此索引表中，这样便形成了两级索引分配方式。如果文件非常大时，还可用三级、四 级索引分配方式。
图6-13示出了两级索引分配方式下各索引块之间的链接情况。如果每个盘块的大小为1 KB，每个盘块号占4个字节，则在一个索引块中可存放256个盘块号。这样，在两级索引时，最多可包含的存放文件的盘块的盘块号总数N= 256x256= 64K个盘块号。由此可得出结论：采用两级索引时，所允许的文件最大长度为64 MB。倘若盘块的大小为4 KB,在采用单级索引时所允许的最大文件长度为4 MB;而在采用两级索引时所允许的最大文件
长度可达4 GB。
混合索引分配方式
所谓混合索引分配方式，是指将多种索引分配方式相结合而形成的一-种分配方式。 例如，系统既采用了直接地址，又采用了一级索引分配方式，或两级索引分配方式，甚至还采用了三级索引分配方式。这种混合索引分配方式已在UNIX系统中采用。在UNIX SystemV的索引结点中,共设置了13 个地址项,即iaddr(0)~ iaddr(12),如图6- 14所示。在BSD UNIX的索引结点中，共设置了13个地址项，它们都把所有的地址项分成两类，即直接地址和间接地址。
1) 直接地址
为了提高对文件的检索速度，在索引结点中可设置 10 个直接地址项，即用 iaddr(0)～ iaddr(9)来存放直接地址。换言之，在这里的每项中所存放的是该文件数据所在盘块的盘块 号。假如每个盘块的大小为 4 KB，当文件不大于 40 KB 时，便可直接从索引结点中读出该 文件的全部盘块号。
2) 一次间接地址
对于大、中型文件，只采用直接地址是不现实的。为此，可再利用索引结点中的地址 项 iaddr(10)来提供一次间接地址。这种方式的实质就是一级索引分配方式。图中的一次间 址块也就是索引块，系统将分配给文件的多个盘块号记入其中。在一次间址块中可存放 1 K 个盘块号，因而允许文件长达 4 MB。
3) 多次间接地址
当文件长度大于 4 MB + 40 KB 时(一次间址与 10 个直接地址项)，系统还须采用二次间 址分配方式。这时，用地址项 iaddr(11)提供二次间接地址。该方式的实质是两级索引分配 方式。系统此时是在二次间址块中记入所有一次间址块的盘号。在采用二次间址方式时， 文件最大长度可达 4 GB。同理，地址项 iaddr(12)作为三次间接地址，其所允许的文件最大 长度可达 4 TB。
6.4 目录管理
通常，在现代计算机系统中，都要存储大量的文件。为了能对这些文件实施有效的管 理，必须对它们加以妥善组织，这主要是通过文件目录实现的。文件目录也是一种数据结 构，用于标识系统中的文件及其物理地址，供检索时使用。对目录管理的要求如下：
(1) 实现“按名存取”，即用户只须向系统提供所需访问文件的名字，便能快速准确地 找到指定文件在外存上的存储位置。这是目录管理中最基本的功能，也是文件系统向用户 提供的最基本的服务。
(2) 提高对目录的检索速度。通过合理地组织目录结构的方法，可加快对目录的检索速 度，从而提高对文件的存取速度。这是在设计一个大、中型文件系统时所追求的主要目标。
(3) 文件共享。在多用户系统中，应允许多个用户共享一个文件。这样就须在外存中只 保留一份该文件的副本，供不同用户使用，以节省大量的存储空间，并方便用户和提高文 件利用率。
(4) 允许文件重名。系统应允许不同用户对不同文件采用相同的名字，以便于用户按照 自己的习惯给文件命名和使用文件。
6.4.1 文件控制块和索引结点
文件控制块
为了能对系统中的大量文件施以有效的管理，在文件控制块中，通常应含有三类信息， 即基本信息、存取控制信息及使用信息。
1) 基本信息类
基本信息类包括:
① 文件名，指用于标识一个文件的符号名。在每个系统中，每一个 文件都必须有惟一的名字，用户利用该名字进行存取。
② 文件物理位置，指文件在外存上 的存储位置，它包括存放文件的设备名、文件在外存上的起始盘块号、指示文件所占用的 盘块数或字节数的文件长度。
③ 文件逻辑结构，指示文件是流式文件还是记录式文件、记 录数；文件是定长记录还是变长记录等。
④ 文件的物理结构，指示文件是顺序文件，还是 链接式文件或索引文件。
2) 存取控制信息类
存取控制信息类包括：文件主的存取权限、核准用户的存取权限以及一般用户的存取 权限。
3) 使用信息类
使用信息类包括: 文件的建立日期和时间、文件上一次修改的日期和时间及当前使用信 息(这项信息包括当前已打开该文件的进程数、是否被其它进程锁住、文件在内存中是否已 被修改但尚未拷贝到盘上)。应该说明，对于不同 OS 的文件系统，由于功能不同，可能只 含有上述信息中的某些部分。
图 6-15 示出了 MS-DOS 中的文件控制块，其中含有文件名、文件所在的第一个盘块号、 文件属性、文件建立日期和时间及文件长度等。FCB 的长度为 32 个字节，对于 360 KB 的 软盘，总共可包含 112 个 FCB，共占 4 KB 的存储空间。
索引结点
1) 索引结点的引入 文件目录通常是存放在磁盘上的，当文件很多时，文件目录可能要占用大量的盘块。 在查找目录的过程中，先将存放目录文件的第一个盘块中的目录调入内存，然后把用户所 给定的文件名与目录项中的文件名逐一比较。若未找到指定文件，便再将下一个盘块中的 目录项调入内存。设目录文件所占用的盘块数为 N，按此方法查找，则查找一个目录项平均 需要调入盘块(N+1)/2 次。假如一个 FCB 为 64 B，盘块大小为 1 KB，则每个盘块中只能存 放 16 个 FCB；若一个文件目录中共有 640 个 FCB，需占用 40 个盘块，故平均查找一个文 件需启动磁盘 20 次。 稍加分析可以发现，在检索目录文件的过程中，只用到了文件名，仅当找到一个目录 项(即其中的文件名与指定要查找的文件名相匹配)时，才需从该目录项中读出该文件的物理 地址。而其它一些对该文件进行描述的信息，在检索目录时一概不用。显然，这些信息在 检索目录时不需调入内存。为此，在有的系统中，如 UNIX 系统，便采用了把文件名与文 件描述信息分开的办法，亦即，使文件描述信息单独形成一个称为索引结点的数据结构， 简称为 i 结点。在文件目录中的每个目录项仅由文件名和指向该文件所对应的 i 结点的指针 所构成。在 UNIX 系统中一个目录仅占 16 个字节，其中 14 个字节是文件名，2 个字节为 i 结点指针。在 1 KB 的盘块中可做 64 个目录项，这样，为找到一个文件，可使平均启动磁 盘次数减少到原来的 1/4，大大节省了系统开销。图 6-16 示出了 UNIX 的文件目录项。
2) 磁盘索引结点
这是存放在磁盘上的索引结点。每个文件有惟一的一个磁盘索引结点，它主要包括以 下内容：
(1) 文件主标识符，即拥有该文件的个人或小组的标识符。
(2) 文件类型，包括正规文件、目录文件或特别文件。
(3) 文件存取权限，指各类用户对该文件的存取权限。
(4) 文件物理地址，每一个索引结点中含有 13 个地址项，即 iaddr(0)～iaddr(12)，它们 以直接或间接方式给出数据文件所在盘块的编号。
(5) 文件长度，指以字节为单位的文件长度。
(6) 文件连接计数，表明在本文件系统中所有指向该(文件的)文件名的指针计数。
(7) 文件存取时间，指本文件最近被进程存取的时间、最近被修改的时间及索引结点最 近被修改的时间。
3) 内存索引结点
这是存放在内存中的索引结点。当文件被打开时，要将磁盘索引结点拷贝到内存的索 引结点中，便于以后使用。在内存索引结点中又增加了以下内容：
(1) 索引结点编号，用于标识内存索引结点。
(2) 状态，指示 i 结点是否上锁或被修改。
(3) 访问计数，每当有一进程要访问此 i 结点时，将该访问计数加 1，访问完再减 1。
(4) 文件所属文件系统的逻辑设备号。
(5) 链接指针。设置有分别指向空闲链表和散列队列的指针。
6.4.2 目录结构
- 单级目录结构
这是最简单的目录结构。在整个文件系统中只建立一张目录表，每个文件占一个目录 项，目录项中含文件名、文件扩展名、文件长度、文件类型、文件物理地址以及其它文件 属性。此外，为表明每个目录项是否空闲，又设置了一个状态位。单级目录如图 6-17 所示。
每当要建立一个新文件时，必须先检索所有的目录项，以保证新文件名在目录中是惟 一的。然后再从目录表中找出一个空白目录项，填入新文件的文件名及其它说明信息，并 置状态位为 1。删除文件时，先从目录中找到该文件的目录项，回收该文件所占用的存储空 间，然后再清除该目录项。
单级目录的优点是简单且能实现目录管理的基本功能——按名存取，但却存在下述一 些缺点：
(1) 查找速度慢。对于稍具规模的文件系统，会拥有数目可观的目录项，致使为找到一 个指定的目录项要花费较多的时间。对于一个具有 N 个目录项的单级目录，为检索出一个 目录项，平均需查找 N/2 个目录项。
(2) 不允许重名。在一个目录表中的所有文件，都不能与另一个文件有相同的名字。然 而，重名问题在多道程序环境下却又是难以避免的；即使在单用户环境下，当文件数超过数百个时，也难于记忆。
(3) 不便于实现文件共享。通常，每个用户都有自己的名字空间或命名习惯。因此，应 当允许不同用户使用不同的文件名来访问同一个文件。然而，单级目录却要求所有用户都 用同一个名字来访问同一文件。简言之，单级目录只能满足对目录管理的四点要求中的第 一点， 因而，它只能适用于单用户环境。
两级目录
为了克服单级目录所存在的缺点，可以为每一个用户建立一个单独的用户文件目录 UFD(User File Directory)。这些文件目录具有相似的结构，它由用户所有文件的文件控制块 组成。此外，在系统中再建立一个主文件目录 MFD(Master File Directory)；在主文件目录中， 每个用户目录文件都占有一个目录项，其目录项中包括用户名和指向该用户目录文件的指 针。如图 6-18 所示，图中的主目录中示出了三个用户名，即 Wang、Zhang 和 Gao。
在两级目录结构中，如果用户希望有自己的用户文件目录 UFD，可以请求系统为自己 建立一个用户文件目录；如果自己不再需要 UFD，也可以请求系统管理员将它撤消。在有 了 UFD 后，用户可以根据自己的需要创建新文件。每当此时，OS 只需检查该用户的 UFD， 判定在该 UFD 中是否已有同名的另一个文件。若有，用户必须为新文件重新命名；若无， 便在 UFD 中建立一个新目录项，将新文件名及其有关属性填入目录项中，并置其状态位为 “1”。当用户要删除一个文件时，OS 也只需查找该用户的 UFD，从中找出指定文件的目录 项， 在回收该文件所占用的存储空间后，将该目录项删除。
两级目录结构基本上克服了单级目录的缺点，并具有以下优点：
(1) 提高了检索目录的速度。如果在主目录中有 n 个子目录，每个用户目录最多为 m 个 目录项，则为查找一指定的目录项，最多只需检索 n + m 个目录项。但如果是采用单级目录 结构，则最多需检索 n × m 个目录项。假定 n = m，可以看出，采用两级目录可使检索效率 提高 n/2 倍。
(2) 在不同的用户目录中，可以使用相同的文件名。只要在用户自己的 UFD 中，每一 个文件名都是惟一的。例如，用户 Wang 可以用 Test 来命名自己的一个测试文件；而用户 Zhang 则可用 Test 来命名自己的一个并不同于 Wang 的 Test 的测试文件。
(3) 不同用户还可使用不同的文件名来访问系统中的同一个共享文件。采用两级目录结 构也存在一些问题。该结构虽然能有效地将多个用户隔开，在各用户之间完全无关时，这种 隔离是一个优点；但当多个用户之间要相互合作去完成一个大任务，且一用户又需去访问其 他用户的文件时，这种隔离便成为一个缺点，因为这种隔离会使诸用户之间不便于共享文件。
多级目录结构
1) 目录结构
对于大型文件系统，通常采用三级或三级以上的目录结构，以提高对目录的检索速度 和文件系统的性能。多级目录结构又称为树型目录结构，主目录在这里被称为根目录，把 数据文件称为树叶，其它的目录均作为树的结点。图 6-19 示出了多级目录结构。图中，用 方框代表目录文件，圆圈代表数据文件。在该树型目录结构中，主(根)目录中有三个用户的 总目录项 A、B 和 C。在 B 项所指出的 B 用户的总目录 B 中，又包括三个分目录 F、E 和 D， 其中每个分目录中又包含多个文件。如 B 目录中的 F 分目录中，包含 J 和 N 两个文件。为 了提高文件系统的灵活性，应允许在一个目录文件中的目录项既是作为目录文件的 FCB， 又是数据文件的 FCB，这一信息可用目录项中的一位来指示。例如，在图 6-19 中，用户 A 的总目录中，目录项 A 是目录文件的 FCB，而目录项 B 和 D 则是数据文件的 FCB。
2) 路径名
在树形目录结构中，从根目录到任何数据文件，都只有一条惟一的通路。在该路径上 从树的根(即主目录)开始，把全部目录文件名与数据文件名依次地用“/”连接起来，即构 成该数据文件的路径名(path name)。系统中的每一个文件都有惟一的路径名。例如，在图 6-19 中用户 B 为访问文件 J，应使用其路径名/B/F/J 来访问。
3) 当前目录(Current Directory)
当一个文件系统含有许多级时，每访问一个文件，都要使用从树根开始直到树叶(数据 文件)为止的、包括各中间节点(目录)名的全路径名。这是相当麻烦的事，同时由于一个进 程运行时所访问的文件大多仅局限于某个范围，因而非常不便。基于这一点，可为每个进 程设置一个“当前目录”，又称为“工作目录”。进程对各文件的访问都相对于“当前目录”而进行。此时各文件所使用的路径名，只需从当前目录开始，逐级经过中间的目录文件， 最后到达要访问的数据文件。把这一路径上的全部目录文件名与数据文件名用“/”连接形 成路径名。如用户 B 的当前目录是 F，则此时文件 J 的相对路径名仅是 J 本身。这样，把从 当前目录开始直到数据文件为止所构成的路径名，称为相对路径名(relative path name)；而 把从树根开始的路径名称为绝对路径名(absolute path name)。
就多级目录较两级目录而言，其查询速度更快，同时层次结构更加清晰，能够更加有 效地进行文件的管理和保护。在多级目录中，不同性质、不同用户的文件可以构成不同的 目录子树，不同层次、不同用户的文件分别呈现在系统目录树中的不同层次或不同子树中， 可以容易地赋予不同的存取权限。
但是在多级目录中查找一个文件，需要按路径名逐级访问中间节点，这就增加了磁盘 访问次数，无疑将影响查询速度。
目前，大多数操作系统如 UNIX、Linux 和 Windows 系列都采用了多级目录结构。
增加和删除目录
在树型目录结构中，用户可为自己建立 UFD，并可再创建子目录。在用户要创建一个 新文件时，只需查看在自己的 UFD 及其子目录中有无与新建文件相同的文件名。若无，便 可在 UFD 或其某个子目录中增加一个新目录项。
在树型目录中，对于一个已不再需要的目录，应如何删除其目录项，须视情况而定。 这时，如果所要删除的目录是空的，即在该目录中已不再有任何文件，就可简单地将该目 录项删除，使它在其上一级目录中对应的目录项为空；如果要删除的目录不空，即其中尚 有几个文件或子目录，则可采用下述两种方法处理：
(1) 不删除非空目录。当目录(文件)不空时，不能将其删除，而为了删除一个非空目录， 必须先删除目录中的所有文件，使之先成为空目录，然后再予以删除。如果目录中还包含 有子目录，还必须采取递归调用方式来将其删除，在 MS-DOS 中就是采用这种删除方式。
(2) 可删除非空目录。当要删除一个目录时，如果在该目录中还包含有文件，则目录中 的所有文件和子目录也同时被删除。 上述两种方法实现起来都比较容易，第二种方法则更为方便，但比较危险。因为整个 目录结构虽然用一条命令即能删除，但如果是一条错误命令，其后果则可能很严重。
6.4.3 目录查询技术
线性检索法
线性检索法又称为顺序检索法。在单级目录中，利用用户提供的文件名，用顺序查找 法直接从文件目录中找到指名文件的目录项。在树型目录中，用户提供的文件名是由多个 文件分量名组成的路径名， 此时须对多级目录进行查找。 假定用户给定的文件路径名是 /usr/ast/mbox，则查找/usr/ast/mbox 文件的过程如图 6-20 所示。
具体查找过程说明如下： 首先，系统应先读入第一个文件分量名 usr，用它与根目录文件(或当前目录文件)中各 目录项中的文件名顺序地进行比较，从中找出匹配者，并得到匹配项的索引结点号 6，再从 6 号索引结点中得知 usr 目录文件放在 132 号盘块中，将该盘块内容读入内存。
接着，系统再将路径名中的第二个文件分量名 ast 读入，用它与放在 132 号盘块中的第二 级目录文件中各目录项的文件名顺序进行比较，又找到匹配项，从中得到 ast 的目录文件放在 26 号索引结点中，再从 26 号索引结点中得知/usr/ast 是存放在 496 号盘块中，再读入 496 号盘块。
然后，系统又将该文件的第三个分量名 mbox 读入，用它与第三级目录文件/usr/ast 中各 目录项中的文件名进行比较，最后得到/usr/ast/mbox 的索引结点号为 60，即在 60 号索引结 点中存放了指定文件的物理地址。目录查询操作到此结束。如果在顺序查找过程中发现有 一个文件分量名未能找到，则应停止查找，并返回“文件未找到”信息。
Hash 方法
在 6.2.5 节中曾介绍了 Hash 文件。如果我们建立了一张 Hash 索引文件目录，便可利用 Hash 方法进行查询，即系统利用用户提供的文件名并将它变换为文件目录的索引值，再利 用该索引值到目录中去查找，这将显著地提高检索速度。
顺便指出，在现代操作系统中，通常都提供了模式匹配功能，即在文件名中使用了通 配符“*”、“？”等。对于使用了通配符的文件名，系统此时便无法利用 Hash 方法检索目 录，因此，这时系统还是需要利用线性查找法查找目录。
在进行文件名的转换时，有可能把 n 个不同的文件名转换为相同的 Hash 值，即出现了 所谓的“冲突”。一种处理此“冲突”的有效规则是:
(1) 在利用 Hash 法索引查找目录时，如果目录表中相应的目录项是空的，则表示系统 中并无指定文件。
(2) 如果目录项中的文件名与指定文件名相匹配，则表示该目录项正是所要寻找的文件 所对应的目录项，故而可从中找到该文件所在的物理地址。
(3) 如果在目录表的相应目录项中的文件名与指定文件名并不匹配，则表示发生了“冲 突”，此时须将其 Hash 值再加上一个常数(该常数应与目录的长度值互质)，形成新的索引值，再返回到第一步重新开始查找。
======第六章文件管理======（4）：https://developer.aliyun.com/article/1415867?spm=a2c6h.13148508.setting.22.16254f0exsfwiz
