1. 文件控制块#

文件控制块(FCB)是用于存放控制文件所需各种信息的数据结构，以实现按名存取。每个文件对应一个FCB, 所有FCB的集合构成文件目录(也称目录文件)。每当创建新文件，系统即为其建立一个FCB, 用以记录其属性信息。

FCB 主要包含以下几类信息：

• 基本信息，如文件名、物理位置、逻辑结构、物理结构等。
• 存取控制信息，包括文件主、核准用户和一般用户的访问权限。
• 使用信息，如文件创建时间、最后修改时间等。

2. 索引节点#

然而，当文件数量庞大时，传统FCB目录会占用大量磁盘空间。在查找过程中，系统需逐块读入目录项，并逐一比对文件名；而仅当匹配成功时才需要获取该文件的物理地址。这意味着，在检索阶段，除文件名外的其他描述信息并无必要调入内存。为此，UNIX等系统采用文件名与描述信息分离的设计策略：将文件的描述信息独立组织为索引节点(inode),简称i节点；而目录项则仅由文件名及其对应的索引节点号(或索引节点指针)构成，

例如，假设一个FCB占 64B, 盘块大小为1KB, 则每个盘块可容纳16个FCB(FCB必须连续存放);若目录共含640个FCB, 则平均需启动磁盘20次才能完成一次文件查找。而在UNIX系统中，每个目录项仅占16B(14B文件名+2B索引节点号),每块可容纳64个目录项，从而将平均磁盘启动次数降至原来的1/4,显著降低系统开销。

为兼顾持久存储与高效访问，文件系统将索引节点设计为两种形态：

(1)磁盘索引节点

存储于磁盘上，作为文件的“永久档案”,每个文件有唯一磁盘索引节点，主要包含：

• 文件主标识符，标识文件所属的用户或用户组。
• 文件类型，指明是普通文件、目录文件还是特殊文件。
• 文件存取权限，规定文件主、核准用户及一般用户的访问权限。
• 文件物理地址，通过13个地址项以直接或间接方式记录数据所在盘块编号。
• 文件长度，以字节为单位表示文件的实际大小。
• 文件链接计数，统计本文件系统中指向该文件的目录项(硬链接)数量。
• 文件存取时间，记录文件最近被访问、修改的时间，以及索引节点最近被修改的时间。

(2)内存索引节点

当文件被打开时，系统将对应的磁盘索引节点载入内存，并附加运行时状态信息，以支持高效的并发访问与快速操作。因此，在磁盘索引节点的基础上，额外新增了以下内容：

• 索引节点号，用于在内存中唯一标识该节点。
• 状态，指示 i 节点是否被上锁或已修改，便于缓存一致性管理。
• 访问计数，进程每访问一次，计数加1;访问结束减1,用于判断节点是否可释放。
• 逻辑设备号，标识文件所属文件系统的逻辑设备号，在多文件系统环境中尤为关键。
• 链接指针，分别指向空闲链表与散列队列，便于内核高效调度和回收。

4.2.3 目 录 结 构#

1.单级目录结构

整个文件系统仅维护一张全局目录表，每个文件对应一个目录项。

创建新文件时，系统首先遍历整张目录表，确保无同名文件存在；确认无冲突后，方可新增一个FCB, 并填入该文件的属性信息。访问文件时，系统根据文件名查找对应的FCB, 经合法性 检查后执行相应操作。删除文件时，则先定位其FCB, 回收其所占存储空间，再清除该FCB。

尽管单级目录结构实现了按名存取，但其存在查找效率低、不允许文件重名、难以支持文件 共享等缺点，且完全无法满足多用户环境的需求，因此仅适用于早期单用户的简单文件系统。

2. 两级目录结构

为克服单级目录存在的缺陷，系统可采用两级方案，将文件目录划分为主文件目录(Master File Directory,MFD)和用户文件目录(User File Directory,UFD)。

MFD 中的每个目录项记录一个用户名及其对应的UFD存储位置；每个UFD则包含该用户所有文件的FCB. 当用户访问其文件时，系统仅需在其专属UFD中进行查找。这一机制不仅有效解决了不同用户间文件重名的问题，还通过隔离用户命名空间增强了安全性。

两级目录结构提升了检索效率,并支持基于目录的访问控制。然而，由于每个用户仅拥有一个扁平的UFD,无法对文件进行分类管理,因此在组织复杂文件集合时显得灵活性不足。

3. 树形目录结构

将两级目录结构加以推广，便形成了树形目录结构。

树形目录结构显著提升了目录检索效率与文件系统的整体性能。在该结构中，用户通过文件路径名来标识文件。路径名是一个字符串，由从根目录出发到目标文件路径上所有目录名和文件名，用分隔符“/”连接而成。若路径从根目录开始，则称为绝对路径；系统中每个文件都具有唯一的绝对路径。例如，在Linux 系统中，“/dev/hda” 就是一个典型的绝对路径。然而，当目录层次较深时，每次从根目录逐级查找会耗费大量时间。为此，系统为每个进程设置一个当前目录(也称工作目录),进程对文件的访问通常以当前目录为基准。此时，用户可使用相对路径进行定位：它由从当前目录出发至目标文件路径上的目录名与文件名，用“I” 连接构成。例如，若当前目录为“/bin”, 则“./ls” 即为相对路径，其中符号“.”表示当前工作目录。

通常，每个用户都拥有专属的“当前目录”,登录后系统自动将其切换至该默认目录。操 作系统提供专门的系统调用，允许用户随时更改当前目录。例如，Linux系统的 /etc/passwd 文件记录了各用户登录时的默认当前目录，而cd命令通过调用该接口动态更新当前目录。

树形目录结构支持灵活的文件分类，层次清晰，便于管理与保护。不同性质或归属的文件可分布于目录树的不同分支或子树中，并能针对各节点设置独立的存取权限，实现精细化控制。然而，该结构也存在局限：查找一个文件需按路径名逐级访问中间目录节点，导致磁盘 I/O 次数增加，可能影响查询速度。尽管如此，凭借其良好的组织性、扩展性以及对多用户环境的支持，目前绝大多数现代操作系统(如UNIX 、Linux 和 Windows) 都采用了树形目录结构。

4. 无环图目录结构

树形目录结构便于实现文件分类，但难以支持文件共享。为此，在其基础上引入指向同一节点的有向边，使整个目录结构演变为一个有向无环图。该结构允许目录共享子目录或文件，同一个文件或子目录可出现在两个或多个目录中，从而实现跨目录的共享。

然而，共享也带来了删除操作的复杂性：当某用户请求删除一个共享节点时，若系统直接将其物理删除，其他共享用户后续访问将因节点缺失而失败。为此，系统为每个共享节点维护一个共享计数器——新增共享链时计数器加1,收到删除请求时减1。仅当计数器归零，才真正删除该节点，否则仅断开请求用户的共享链，保留节点供他人继续使用。无环图目录结构虽有效支持灵活的文件共享，但也因此增加了管理开销，需额外维护引用计数等共享状态。

1. 连续分配#

连续分配方法要求每个文件在磁盘上占有一组连续的块。由于磁盘地址本身具有线性顺序，这种布局使得进程访问文件时所需的寻道次数和寻道时间最小。

采用连续分配时，逻辑文件中的记录依次存放在相邻的物理块中。文件的目录项需要记录该文件起始块的块号及其所占用的总块数。若文件长度为n块，且从块b开始存放，则该文件占据的块为b,b+1,b+2,…,b+n-1;要访问第i 块，可直接计算并访问块b+i-1。

连续分配的优点：

1. 支持顺序访问和直接访问。
2. 顺序访问高效且速度快，因为文件所占的块通常位于一条或少数几条相邻磁道上，磁头移动距离最小。

缺点：

1. 必须为文件分配连续的存储空间，与内存连续分配类似，易产生大量外部碎片。
2. 需要预先知道文件长度，难以支持文件的动态增长——若强行扩展，可能覆盖物理上相邻的其他文件。
3. 为维持文件的逻辑顺序，在删除或插入记录时，往往需要对后续记录进行物理移动，开销较大。

2. 链接分配#

链接分配是一种采用离散方式分配磁盘块的策略。其主要优点包括：

1. 消除了外部碎片，显著提高磁盘空间的利用率。
2. 支持动态分配盘块，无须事先预知文件大小。
3. 文件的插入、删除和修改操作十分便捷。

根据指针存储方式的不同，链接分配可分为隐式链接和显式链接。

(1)隐式链接

隐式链接目录项中包含指向文件第一块和最后一块的指针(盘块号)。每个文件对应一个由磁盘块构成的链表，这些块可分散存储于磁盘的任意位置。除最后一块外，每个盘块均存有指向下一个盘块的指针，这些指针对用户完全透明。

隐式链接的缺点：

1. 仅支持顺序访问，若要访问文件的第 i 块，必须从首块开始，依次跟随指针遍历至第 i 块，随机访问效率极低。
2. 可靠性较差，一旦链中任一指针损坏，整个链将断开,导致后续数据无法访问。
3. 每个盘块需要存储指向下一块的指针，占用一定的存储空间。

为缓解上述问题，可引入簇(cluster)的概念：将若干连续的盘块组合成一个簇(基本分配单位),文件的分配与链接均以簇为单位进行。如此，指针数量大幅减少，不仅降低存储开销，也显著缩短链式查找时间，从而提升整体 I/O 性能。但这一优化的代价是可能产生内部碎片—-当文件大小不是簇大小的整数倍时，最后一个簇的剩余空间无法被其他文件利用。

(2)显式链接

显式链接将用于链接文件各物理块的指针集中 存放在内存中的一张全局表中，该表在整个文件系统中仅设一张，称为文件分配表(File Allocation Table,FAT)。FAT的每个表项对应一个磁盘块，并存放指向下一个盘块的指针。因此，文件目录项只需记录该文件的起始块号，后续所有块号均可通过 依次查询FAT获得。例如，某磁盘共有100个盘块，其中存放了两个文件：文件“aaa” 占用三个块，链接顺序为2 → 8 → 5;文件“bbb” 占用两个块，链接顺序为7→ 1。其余盘块均为空闲块。

不难看出，FAT的表项与所有磁盘块一一对应。通常，可用特殊值-1标记文件的最后一块，用-2表示该盘块空闲(也可指定为-3、-4等)。因此，FAT不仅记录了文件的链式结构，还标识了空闲盘块，系统可直接利用FAT管理磁盘的空闲空间。当某进程请求分配一个磁盘块时，系统只需在FAT中查找值为-2的表项，并将对应的磁盘块分配给该进程即可。

显式链接的优点：

1. 支持顺序访问，也支持直接访问，要访问第i块，无须依次遍历前i-1块；
2. FAT在系统启动时即被载入内存，后续检索操作均在内存中完成，不仅显著提升查找速度，也大幅减少磁盘I/O 次数。

缺点：FAT需要常驻内存，磁盘容量越大，内存开销越显著。

3. 索引分配#

(1)单级索引分配方式

事实上，在打开某个文件时，只需将该文件所占用的盘块编号调入内存即可，无须加载整个FAT。为此，可将每个文件的所有盘块号集中存放于一处；当访问该文件时，只需将其对应的盘块号集合一次性载入内存，这正是索引分配的思想。具体而言，系统为每个文件分配一个专用的索引块(或称索引表),并将分配给该文件的所有盘块号记录其中。

例如，若盘块大小为4KB,每个盘块号占4B, 则一个索引块可容纳4KB/4B=1024个盘块号。采用单级索引时，可支持的最大文件为1024 X 4KB=4MB。

索引分配的优点：

1. 支持高效的直接访问，要访问文件的第i块，只需读取索引块中第i项，即可直接获得对应的盘块号；
2. 不会产生外部碎片，因为文件的盘块可离散分配。

缺点：引入了额外的存储开销，每个文件必须配备一个索引块。当文件较小时，如仅占用几个盘块，仍需要为其分配一个完整的索引块，导致索引块的利用率极低；当文件较大时，若所需盘块号超出单个索引块容量，虽可借助链式指针将多个索引块链接起来，但这种方法效率低下。

(2)多级索引分配方式

显然，当文件过大而索引块较多时，可为这些索引块再建立一级索引，称为主索引。主索引表 中依次存放各二级索引块的盘块号，从而形成二级索引分配方式。其设计思想与内存管理中的多级页表高度相似。访问数据时，系统首先通过主索引定位对应的二级索引块，再通过该二级索引块找到目标数据块。若文件非常大，还可进一步扩展为三级、四级的索引分配结构。

例如，假设盘块大小为4KB,每个盘块号占4B,则一个索引块可容纳1024个盘块号。采用两级索引时，可支持的最大文件为 1024 X 1024 X 4KB=4GB。

多级索引的优点：显著提升大型文件的可扩展性与查找效率。缺点：当访问一个盘块时，所需的磁盘I/O次数随索引级数增加而增多。若文件系统仅采用多级索引作为组织方式，则即使对于大量小文件，访问单个盘块仍需要多次磁盘 I/O,导致整体I/O性能难以达到理想水平。

(3)混合索引分配方式

为兼顾小、中、大乃至特大型文件的访问效率，需要根据文件大小动态选用最合适的分配策略，在空间开销与访问性能之间取得最佳平衡，因此通常采用混合索引分配方式。对于小文件，为提升大量小文件的访问速度，可将其全部盘块地址直接存放在inode(或FCB)中，系统直接从中获取所有盘块地址，无须额外读取索引结构，即直接寻址。对于中型文件，采用单级索引分配，inode中存放一个索引块的地址，系统需要先读取该索引块，再从中获取文件的盘块地址，即一次间址。对于大型或特大型文件，则分别采用两级和三级索引分配。UNIX系统正是采用这种混合策略。在其索引节点中，共设有13个地址项，即i.addr(O)~i.addr(12)。

1. 直接地址。为了提升对小文件的检索速度，索引节点中设置了10个直接地址项，记为 i.addr(O)～i.addr(9), 每个项直接存放一个文件数据块的盘块号。假设每个盘块大小为 4KB, 当文件不大于40KB 时，则可直接从索引节点中读取该文件的全部盘块号。
2. 一次间接地址。对于中、大型文件，仅靠直接地址显然无法满足需求。为此，索引节点中的地址项i.addr(10)被设计为一次间接地址，用于实现一级索引分配。一次间接地址指向一个专门的一次间址块(索引块),其中存放的是文件数据块的盘块号。一个索引块可容纳1024个盘块号，通过一次间接地址最多可寻址1K×4KB=4MB的数据。因此，同时使用直接地址和一次间址时，最大可表示的文件长度为4MB+40KB。
3. 多次间接地址。 当文件长度超过4MB+40KB时，还需要利用地址项i.addr(11)作为二次间接地址，以实现两级索引分配。二次间接地址指向文件的主索引块，该主索引块中的每一项又指向一个一次间址块，而每个一次间址块再指向1024个数据块。通过二次间接 地址最多可寻址1K×1K×4KB=4GB的数据。因此，同时使用直接地址、一次间址和二次 间址时，最大可表示的文件长度为4GB+4MB+40KB。同理，同时采用直接地址、一次 间址、二次间址和三次间址时，最大可表示的文件长度为4TB+4GB+4MB+40KB。