第四章 文件管理

考研考点：

---

一、文件

1. 文件的基本概念

(1) 文件的定义
文件是由操作系统创建和管理的一组相关数据或信息的集合。它可以是文本、图像、音频、视频、程序代码等任何形式的数据。

(2) 文件的属性
除了文件数据，操作系统还会保存与文件相关的信息，如所有者、创建时间等，这些附加信息称为文件属性和文件元数据。包括：

• 名称：用于（在同一目录下）唯一标识文件的名称。
• 标识符：一个系统内的各文件标识符唯一，对用户来说毫无可读性，因此标识符只是操作系统用于区分各个文件的一种内部名称。
• 类型：指示文件的格式或用途，如文本文件（.txt）、图像文件（.jpg）、可执行文件（.exe）等。
• 创建者：文件创建者的ID。
• 所有者：文件当前所有者的ID。
• 位置：指向设备和设备上文件的指针。
• 大小：文件占用的存储空间大小。
• 访问权限（保护）：控制谁可以读取、写入或执行文件的权限。
• 创建时间、最后一次修改时间和最后一次存取时间：文件创建、上次修改和上次访问的相关信息，用于保护和跟踪文件的使用。

(3) 文件的分类
为了便于管理文件，将文件分成了若干类型。由于不同系统对文件的管理方式不同，因此它们的文件分类方法也有很大差异。下面是几种常见的文件分类方法：

• 按性质和用途分类，分为系统文件、用户文件、库文件。
• 按文件中数据的形式分类，分为源文件、目标文件、可执行文件。
• 按存取控制属性分类，分为可执行文件、只读文件、读/写文件。
• 按组织形式和处理方式分类，分为普通文件、目录文件、特殊文件。

(4) 文件内部数据的组织

• 无结构文件（如文本文件）——由一些二进制或字符流组成，又称“流式文件”。
• 有结构文件（如数据库表）——由一组相似的记录组成，又称“记录式文件”。

有结构文件中，各个记录间应该如何组织的问题——应该顺序存放？还是用索引表来表示记录间的顺序？——这是“文件的逻辑结构”重点要探讨的问题。

(5) 文件之间的组织
Windows为例：

用户可以自己创建一层一层的目录，各层目录中存放相应的文件。系统中的各个文件就通过一层一层的目录合理有序的组织起来了。
目录其实也是一种特殊的有结构文件（由记录组成），如何实现文件目录是之后会重点探讨的问题。

2. 文件控制块和索引节点

2.1 文件控制块（FCB）

• 文件控制块(File Control Block，FCB)是用来存放控制文件需要的各种信息的数据结构，以实现按名存取（主要作用）。
• 文件与 FCB 一一对应，FCB 的有序集合称为文件目录（文件夹），一个FCB就是一个文件目录项。通常，一个文件目录也被视为一个文件，称为目录文件。每当创建一个新文件，系统就要为其建立一个FCB，用来记录文件的各种属性。
• FCB 主要包含以下信息:
  • 基本信息：文件名、文件的物理位置、文件的逻辑结构、文件的物理结构等。
  • 存取控制信息：文件主的存取权限、核准用户的存取权限以及一般用户的存取权限
  • 使用信息：文件建立时间、上次修改时间等。

【示例】现有如下图的目录结构

“照片”目录对应的目录文件：

目录文件中的一条记录就是一个“文件控制块（FCB)”。

需要对目录进行哪些操作？

• 搜索：当用户要使用一个文件时，系统要根据文件名搜索目录，找到该文件对应的目录项
• 创建文件：创建一个新文件时，需要在其所属的目录中增加一个目录项
• 删除文件：当删除一个文件时，需要在目录中删除相应的目录项
• 显示目录：用户可以请求显示目录的内容，如显示该目录中的所有文件及相应属性
• 修改目录：某些文件属性保存在目录中，因此这些属性变化时需要修改相应的目录项（如：文件重命名）

2.2 索引节点（inode）

是对FCB的改进，其实在查找各级目录的过程中只需要用到“文件名”这个信息，只有文件名匹配时，才需要读出文件的其他信息。因此可以考虑让目录表“瘦身”来提升效率。

⭐注意点：
① 根目录的信息存储在磁盘的固定位置，这样可以保证开机时，能够找到根目录，再从根目录出发找到任何其他信息。
② 开机时，根目录的内容（根目录下的FCB）通常会被加载到内存，并一直常驻内存。
③ 除根目录外，其他的文件目录是不会自动加载到内存中的，都是存放在磁盘的。
④ 索引节点inode都存储在磁盘上的，查看某个文件的索引节点需要进行一次磁盘I/O操作。
⑤ 除了文件名之外的文件描述信息都放到索引节点。

【举例说明】如何提高效率的呢？
假设一个FCB是64B，磁盘块的大小为1KB，则每个盘块中只能存放16个FCB。若一个文件目录中共有640个目录项，则共需要占用640/16 = 40 个盘块。
按照某文件名检索该目录，平均需要查询320 个目录项，平均需要启动磁盘20次（每次磁盘I/O读入一块）。
若使用索引结点机制，文件名占14B，索引结点指针占2B，则每个盘块可存放64个目录项，那么按文件名检索目录平均只需要读入 320/64 = 5 个磁盘块。显然，这将大大提升文件检索速度。

结论：由于目录项长度减小，因此每个磁盘块可以存放更多个目录项，因此检索文件时磁盘I/0的次数就少了很多。

当找到文件名对应的目录项时，才需要将索引结点调入内存，索引结点中记录了文件的各种信息，包括文件在外存中的存放位置，根据“存放位置”即可找到文件。
存放在外存中的索引结点称为“磁盘索引结点”，当索引结点放入内存后称为“内存索引结点”。
相比之下内存索引结点中需要增加一些信息，比如：文件是否被修改、此时有几个进程正在访问该文件（访问计数器）等。

2.3 考点

FCB和inode（索引结点）不能同时出现，也就是说一个文件系统只能使用FCB模式来存储文件目录项或者inode模式存储文件目录项，不能两个都用。

• FCB类型的文件系统访问文件数据的流程：先找文件的目录项，再根据文件目录项找到实体数据。
• 带索引结点（inode）的文件系统访问文件数据的流程：先找文件的目录项，再根据文件目录项指向的索引结点找到其索引结点，最后根据索引结点找到实体数据。

3. 文件操作

文件操作属于操作系统为应用程序或用户提供的功能。包括：

• 创建文件
• 删除文件
• 读文件
• 写文件
• 打开文件
• 关闭文件

3.1 创建文件

“创建文件”（点击新建后，图形化交互进程在背后调用了“create 系统调用”)。
进行 Create 系统调用时，需要提供的几个主要参数：

• 所需的外存空间大小（如：一个盘块，即1KB）
• 文件存放路径（“D:/Demo”）
• 文件名（这个地方默认为“新建文本文档.txt”）

操作系统在处理 Create 系统调用时，主要做了两件事：

• 在外存中找到文件所需的空间。
• 根据文件存放路径的信息找到该目录对应的目录文件（此处就是 D:/Demo 目录），在目录中创建该文件对应的目录项。目录项中包含了文件名、文件在外存中的存放位置等信息。

3.2 删除文件

“删除文件”（点了“删除”之后，图形化交互进程通过操作系统提供的“删除文件”功能，即 delete 系统调用，将文件数据从外存中删除)。
进行 Delete 系统调用时，需要提供的几个主要参数：

• 文件存放路径（“D:/Demo”）
• 文件名（“test.txt”）

操作系统在处理 Delete 系统调用时，主要做了几件事：

• 根据文件存放路径找到相应的目录文件，从目录中找到文件名对应的目录项。
• 根据该目录项记录的文件在外存的存放位置、文件大小等信息，回收文件占用的磁盘块。
• 从目录表中删除文件对应的目录项。

3.3 打开文件

在很多操作系统中，在对文件进行操作之前，要求用户先使用 open 系统调用“打开文件”，需要提供的几个主要参数：

• 文件存放路径（“D:/Demo”）
• 文件名（“test.txt”）
• 要对文件的操作类型（如：r 只读；rw 读写等）

操作系统在处理 open 系统调用时，主要做了几件事：

• 根据文件存放路径找到相应的目录文件，从目录中找到文件名对应的的目录项，并检查该用户是否有指定的操作权限。
• 将目录项复制到内存中的进程的用户“打开文件表”中。并将对应表目的索引号（文件描述符或句柄）返回给用户。之后用户使用打开文件表的索引号来指明要操作的文件。
• 系统打开文件表（只有在文件实体第一次被打开时才）增加一个表目，并通过文件I/O将对应的索引节点从磁盘读入内存。

注意：open打开文件只是将文件的FCB或inode节点调入内存，而文件的内容还在外存；而我们平时进行的双击打开文件其实进行了open打开文件和read读数据两个操作，不然我们咋可以看到文件的内容呢。

系统的打开文件表和用户进程打开文件表

• 打开计数器：记录此时有多少个进程打开了此文件。
• 读/写指针：记录了该进程对文件的读/写操作进行到的位置。
• 访问权限：如果打开文件时声明的是“只读”，则该进程不能对文件进行写操作。

可以方便实现某些文件管理的功能。例如：在Windows系统中，我们尝试删除某个txt文件，如果此时该文件已被某个“记事本”进程打开，则系统会提示我们“暂时无法删除该文件”。其实系统在背后做的事就是先检查了系统打开文件表，确认此时是否有进程正在使用该文件。

⭐⭐考点：计算打开指定文件的I/O次数，以下述代码为例：

fd = open("/aa/bb/z.txt", rw);

(1) 第一种：采用inode方式存储文件元数据：
打开文件 /aa/bb/z.txt 需要 5 次磁盘 I/O：

• 从根目录的文件目录中从磁盘中取出aa目录对应的inode节点 – 第一次
• 根据aa的inode节点从磁盘中取出aa的具体数据（文件目录） – 第二次
• 从aa的文件目录从磁盘中取出bb目录对应的inode节点 – 第三次
• 根据bb的inode节点从磁盘中取出bb的具体数据（文件目录） – 第四次
• 根据bb的文件目录从磁盘中取出z.txt文件的inode节点 – 第五次

此时系统的打开文件表中添加一项并指向z.txt的inode节点。
注：根目录项已缓存在内存。

(2) 第二种：采用FCB方式存储文件元数据
打开文件 /aa/bb/z.txt 需要 2 次磁盘 I/O：

• 从根目录的文件目录中直接得到aa目录的完整FCB（因其已在内存中） – 0次
• 根据aa的FCB中记录的数据块指针，从磁盘中取出aa目录的具体数据（即其包含的FCB列表） – 第一次
• 从aa的文件目录中直接得到bb目录的完整FCB（因其已在上一步被加载到内存） – 0次
• 根据bb的FCB中记录的数据块指针，从磁盘中取出bb目录的具体数据（即其包含的FCB列表） – 第二次
• 从bb的文件目录中直接得到z.txt文件的完整FCB（因其已在上一步被加载到内存） – 0次

此时系统的打开文件表中添加一项并指向z.txt的FCB（已在内存中）。

注：根目录项已缓存在内存。

总结：
① open打开文件操作不涉及读取文件的具体内容。
② 目录的“具体数据”是其文件目录项（即文件名到 inode 号的映射列表），而非用户数据；文件的“具体数据”才是实际的文件内容。
③ inode 方式：目录项只包含（文件名, inode号）。要获取文件的元数据（权限、大小等）或目录的内容，你必须通过这个 inode 号去特定的 inode 区域读取 inode 节点或数据块；FCB 方式：目录项直接就是该文件或子目录的完整 FCB。一个FCB包含了文件的全部元数据（如文件名、大小、权限、创建时间、物理地址等）。

3.4 关闭文件

进程使用完文件后，要“关闭文件”。
关闭文件操作的主要功能是将文件当前的控制信息从内存写回磁盘，需要注意的是关闭文件并不意味着将文件数据写回磁盘，写文件操作才会写回磁盘（不考虑延迟写）。
操作系统在处理 Close 系统调用时，主要做了几件事：

• 将进程的打开文件表相应表项删除。
• 回收分配给该文件的内存空间等资源。
• 系统打开文件表的打开计数器count 减1，若 count =0，则删除对应表项。

3.5 读文件

“读文件”，将文件数据读入内存，才能让CPU处理（双击后，“记事本”应用程序通过操作系统提供的“读文件”功能，即 read 系统调用，将文件数据从外存读入内存，并显示在屏幕上)。

进行read系统调用时，需要提供的几个主要参数：

• 指明是哪个文件（在支持“打开文件”操作的系统中，只需要提供文件在打开文件表中的索引号（文件描述符）即可）
• 指明要读入多少数据（如：读入 1KB）
• 指明读入的数据要放在内存中的什么位置

操作系统在处理 Read 系统调用时，主要做了几件事：

• 从读指针指向的外存中，将用户指定大小的数据读入用户指定的内存区域中。

3.6 写文件

“写文件”，将更改过的文件数据写回外存（我们在“记事本”应用程序中编辑文件内容，点击“保存”后，“记事本”应用程序通过操作系统提供的“写文件”功能，即 write 系统调用，将文件数据从内存写回外存)。

进行write 系统调用时，需要提供的几个主要参数：

• 指明是哪个文件（在支持“打开文件”操作的系统中，只需要提供文件在打开文件表中的索引号（文件描述符）即可）
• 指明要写出多少数据（如：写出 1KB）
• 写回外存的数据放在内存中的什么位置

操作系统在处理 Write 系统调用时，主要做了几件事：

• 从用户指定的内存区域中，将指定大小的数据写回写指针指向的外存。

4. 文件保护

文件共享可能会导致文件被破坏或未经核准的用户修改文件，文件系统必须控制用户对文件的存取，即解决对文件的读、写、执行的许可问题。为此，必须在文件系统中建立相应的文件保护机制，可以通过口令保护、加密保护和访问控制等方式实现。其中，口令和加密是为了防止用户文件被他人存取或窃取，而访问控制则用于控制用户对文件的访问方式。

4.1 口令保护

• 为文件设置一个“口令”（如：abc112233），用户请求访问该文件时必须提供“口令”。
• 口令一般存放在文件对应的 FCB 或索引结点中。用户访问文件前需要先输入“口令”，操作系统会将用户提供的口令与FCB中存储的口令进行对比，如果正确，则允许该用户访问文件。
• 优点：保存口令的空间开销不多，验证口令的时间开销也很小。
• 缺点：正确的“口令”存放在系统内部，不够安全。

4.2 加密保护

使用某个“密码”对文件进行加密，在访问文件时需要提供正确的“密码”才能对文件进行正确的解密。

【示例】一个最简单的加密算法——异或加密
假设用于加密/解密的“密码”为“01001”

优点：保密性强，不需要在系统中存储“密码”。
缺点：编码/译码，或者说加密/解密要花费一定时间。

4.3 访问控制

4.3.1 访问类型

在每个文件的FCB（或索引结点）中增加一个访问控制列表（Access-Control List, ACL），该表中记录了各个用户可以对该文件执行哪些操作。

• 读。从文件中读。
• 写。向文件中写。
• 执行。将文件装入内存并执行。
• 添加。将新信息添加到文件结尾部分。
• 删除。删除文件，释放空间。
• 列表清单。列出文件名和文件属性。

此外还可以对文件的重命名、复制、编辑等加以控制。这些高层的功能可以通过系统程序调用低层系统调用来实现。保护可以只在低层提供。例如，复制文件可利用一系列的读请求来完成，这样，具有读访问权限的用户同时也就具有了复制和打印权限。
如果对某个目录进行了访问权限的控制，那也要对目录下的所有文件进行相同的访问权限控制。

【示例】有三个用户

1表示允许，0表示不允许。

4.3.2 精简的访问列表

有的计算机可能会有很多个用户，因此访问控制列表可能会很大，可以用精简的访问列表解决这个问题。
精简的访问列表：以“组”为单位，标记各“组”用户可以对文件执行哪些操作。系统需要管理分组的信息。
如：分为 系统管理员、文件主、文件主的伙伴、其他用户 几个分组。

当某用户想要访问文件时，系统会检查该用户所属的分组是否有相应的访问权限。

【示例】某文件系统中，针对每个文件，用户类别分为4类：安全管理员、文
件主文件主的伙伴、V其他用户；访问权限分为5种？完全控制、执行、修改、读取、写入。若文件控制块中用二进制位串表示文件权限，为表示不同类别用户对一个文件的访问权限，则描述文件权限的位数至少应为（）。
A. 5    B. 9    C.12    D.20

解析：需要注意的是，二进制位串表示的访问权限是这个文件所持有的，而不是某个用户所持有的，这个二进制位串要表示所有类别的用户的访问权限，每个要访问该文件的用户在访问之前都要查这个二进制位串。对于每类用户来说，都需要用5位来表示5种访问权限中的哪几种访问权限，共有四类用户，因此可将用户访问权限抽象为一个矩阵，其行代表用户类别，列代表访问权限。这个矩阵有4行5列，1代表true，0代表false，所以需要20位。
例如，下表是个用二进制位串表示的文件权限。

本题易误选A，有读者认为用2位来表示用户类别，用3位来表示访问权限，这种情况在于没有理解文件访问权限的二进制位串是文件所持有的，所以当用户需要检查访问权限时，要在二进制位串中查询所属用户类别的访问权限。此外，每类用户的访问权限不是拥有5种访问权限中的哪一种，而是5种访问权限都可能拥有，因此不可能用3位来表示访问权限。

5. 文件的逻辑结构

文件的逻辑结构是指从用户角度出发所看到的文件的组织形式。而文件的物理结构（又称存储结构）是指将文件存储在外存上的存储组织形式，是用户所看不见的。
按逻辑结构，文件可划分为无结构文件和有结构文件两大类。

5.1 无结构文件

无结构文件是最简单的文件组织形式，它是由一系列字符流或二进制流构成的文件，所以又称流式文件，其长度以字节为单位。对流式文件的访问，是通过读/写指针来指出下一个要访问的字节的。在系统中运行的大量源程序、可执行文件、库函数等，所采用的就是无结构文件。由于无结构文件没有结构，因而对记录的访问只能通过穷举搜索的方式，因此这种文件形式对很多应用不适用。

5.2 有结构文件

有结构文件：由一组相似的记录组成，又称“记录式文件”。每条记录由若干个数据项组成。如：数据库表文件。一般来说，每条记录有一个数据项可作为关键字（作为识别不同记录的ID）。

5.2.1 定长记录和可变长记录

根据各条记录的长度（占用的存储空间）是否相等，又可分为定长记录和可变长记录两种。

【示例】

这个有结构文件由定长记录组成，每条记录的长度都相同（共 128 B）。各数据项都处在记录中相同的位置，具有相同的顺序和长度（前32B一定是学号，之后32B一定是姓名……)。

这个有结构文件由可变长记录组成，由于各个学生的特长存在很大区别，因此“特长”这个数据项的长度不确定，这就导致了各条记录的长度也不确定。当然，没有特长的学生甚至可以去掉“特长”数据项。

5.2.2 有结构文件的逻辑结构

有结构文件按记录的组织形式可以分为顺序文件、索引文件、索引顺序文件。

5.2.2.1 顺序文件

顺序文件：文件中的记录一个接一个地顺序排列（逻辑上），记录可以是定长的或可变长的。各个记录在物理上可以顺序存储或链式存储。

• 顺序存储：逻辑上相邻的记录物理上也相邻（类似于顺序表）
  
• 链式存储：逻辑上相邻的记录物理上不一定相邻（类似于链表）
  

顺序文件中记录的排列有两种结构：

• 串结构：记录之间的顺序与关键字无关，通常按照记录存入的时间决定记录的顺序。
• 顺序结构：记录之间的顺序按关键字顺序排列。

假设：已经知道了文件的起始地址（也就是第一个记录存放的位置），回答如下两个问题：

• 能否快速找到第 i 个记录对应的地址？（即能否实现随机存取）
• 能否快速找到某个关键字对应的记录存放的位置？

解析：

• 链式存储：无论是定长/可变长记录，都无法实现随机存取，每次只能从第一个记录开始依次往后查找
• 顺序存储
  • 可变长记录：无法实现随机存取。每次只能从第一个记录开始依次往后查找
  • 定长记录：可实现随机存取。记录长度为L，则第i个记录存放的相对位置是i*L
    • 若采用串结构，无法快速找到某关键字对应的记录
    • 若采用顺序结构，可以快速找到某关键字对应的记录（如折半查找）

结论：定长记录的顺序文件，若物理上采用顺序存储，则可实现随机存取；若能再保证记录的顺序结构，则可实现快速检索（即根据关键字快速找到对应记录）。
注：一般来说，考试题目中所说的“顺序文件”指的是物理上顺序存储的顺序文件。之后的讲解中提到的顺序文件也默认如此。可见，顺序文件的缺点是增加/删除一个记录比较困难（如果是串结构则相对简单）。

注意：不同的存储介质有不同的存储特性，如磁带只能顺序存取，磁盘可以随机存取，因此文件组织形式与存储介质特性有关。

5.2.2.2 索引文件

对于可变长记录文件，要找到第 i 个记录，必须先顺序第查找前 i-1 个记录，但是很多应用场景中又必须使用可变长记录。如何解决这个问题？
这个时候索引文件登场了。

建立一张索引表以加快文件检索速度。每条记录对应一个索引项。
文件中的这些记录在物理上可以离散地存放。

索引表本身是定长记录的顺序文件。因此可以快速找到第 i 个记录对应的索引项。
可将关键字作为索引号内容，若按关键字顺序排列，则还可以支持按照关键字折半查找。
每当要增加/删除一个记录时，需要对索引表进行修改。由于索引文件有很快的检索速度，因此主要用于对信息处理的及时性要求比较高的场合。
另外，可以用不同的数据项建立多个索引表。如：学生信息表中，可用关键字“学号”建立一张索引表。也可用“姓名”建立一张索引表。这样就可以根据“姓名”快速地检索文件了。（Eg：SQL 就支持根据某个数据项建立索引的功能）

5.2.2.3 索引顺序文件

思考索引文件的缺点：每个记录对应一个索引表项，因此索引表可能会很大。比如：文件的每个记录平均只占 8B，而每个索引表项占32个字节，那么索引表都要比文件内容本身大4倍，这样对存储空间的利用率就太低了。
这个时候索引顺序文件登场了。

索引顺序文件是索引文件和顺序文件思想的结合。索引顺序文件中，同样会为文件建立一张索引表，但不同的是：并不是每个记录对应一个索引表项，而是一组记录对应一个索引表项。

【示例】学生记录按照学生姓名的开头字母进行分组

索引顺序文件的索引项也不需要按关键字顺序排列，这样可以极大地方便新表项的插入。
每个分组就是一个顺序文件，分组内的记录不需要按关键字排序。

检索效率分析
若一个顺序文件有10000个记录，则根据关键字检索文件，只能从头开始顺序查找（这里指的并不是定长记录、顺序结构 的顺序文件），平均须查找 5000 个记录。
若采用索引顺序文件结构，可把 10000 个记录分为 √10000 = 100 组，每组 100 个记录。则需要先顺序查找索引表找到分组（共100个分组，因此索引表长度为 100，平均需要查 50 次），找到分组后，再在分组中顺序查找记录（每个分组100 个记录，因此平均需要查 50 次）。可见，采用索引顺序文件结构后，平均查找次数减少为 50+50 = 100 次。

5.2.2.4 多级索引顺序文件

为了进一步提高检索效率，可以为顺序文件建立多级索引表。

【示例】对于一个含 10⁶个记录的文件，可先为该文件建立一张低级索引表，每 100 个记录为一组，故低级索引表中共有 10000 个表项（即10000个定长记录），再把这 10000 个定长记录分组，每组100个，为其建立顶级索引表，故顶级索引表中共有 100 个表项。

此时，检索一个记录平均需要查找50+50+50 = 150 次

Tips:

• 要为 N 个记录的文件建立 K 级索引，则最优的分组是每组 N^1/(K+1)个记录。
• 检索一个记录的平均查找次数是 ((N^1/(K+1) )/2) * (K+1)
• 如：本例中，建立 2级索引，则最优分组为每组100000^1/3 = 100 个记录，平均查找次数是 (100/2) * 3 = 150 次

5.2.2.5 直接文件或散列文件

给定记录的键值或通过散列函数转换的键值直接决定记录的物理地址。散列文件具有很高的存取速度，但是会引起冲突，即不同关键字的散列函数值可能相同。
复习了数据结构的读者读到这里时，会有这样的感觉：有结构文件逻辑上的组织，是为在文件中查找数据服务的（顺序查找、索引查找、索引顺序查找、哈希查找）。

6. 文件的物理结构

文件的物理结构就是研究文件的实现，即文件数据在物理存储设备上是如何分布和组织的。同一个问题有两个方面的回答：一是文件的分配方式，讲的是对磁盘非空闲块的管理；二是文件存储空间管理，讲的是对磁盘空闲块的管理（详见文件系统的外存空闲空间管理小节）。

(1) 文件的分配方式
文件分配对应于文件的物理结构，是指如何为文件分配磁盘块。常用的文件分配方法有三种：

• 连续分配
• 链接分配
• 索引分配

(2) 文件块、磁盘块
类似于内存分页，磁盘中的存储单元也被分为一个个的块，称为磁盘块，很多操作系统中，磁盘块的大小与内存块、页面的大小相同。内存与磁盘之间的数据交换（磁盘 I/O）都是以块为单位进行的。
在内存管理中，进程的逻辑地址空间被分为一个个页面。同样的，在外存管理中，为了方便对文件数据的管理，文件的逻辑地址空间也被分为了一个个的文件“块”。于是文件的逻辑地址也可以表示为（逻辑块号，块内地址）的形式。

操作系统为文件分配存储空间都是以块为单位的。
用户通过逻辑地址来操作自己的文件，操作系统要负责实现从逻辑地址到物理地址的映射。

6.1 连续分配

核心思想：连续分配方式要求每个文件在磁盘上占有一组连续的块。

(1) 操作系统如何实现从逻辑地址到物理地址的映射？
（逻辑块号，块内地址）→（物理块号，块内地址）。只需转换块号就行，块内地址保持不变。
用户给出要访问的逻辑块号，操作系统找到该文件对应的目录项（FCB）：

文件目录中记录存放的起始块号和长度（总共占用几个块）
物理块号 = 起始块号 + 逻辑块号
当然，还需要检查用户提供的逻辑块号是否合法（逻辑块号 ≥ 长度 就不合法)

(2) 连续分配的优缺点

• 优点：
  • ① 可以直接算出逻辑块号对应的物理块号，因此连续分配支持顺序访问和直接访问（即随机访问）；
  • ② 连续分配的文件在顺序读/写时速度最快；
    
    • 读取某个磁盘块时，需要移动磁头。访问的两个磁盘块相隔越远，移动磁头所需时间就越长。
• 缺点：
  • ① 物理上采用连续分配的文件不方便拓展；
    
    因此只能将文件A全部“迁移”到绿色区域。
  • ② 物理上采用连续分配，存储空间利用率低，会产生难以利用的磁盘碎片。可以用紧凑来处理碎片，但是需要耗费很大的时间代价。
    

6.2 链接分配

核心思想：链接分配采取离散分配的方式，可以为文件分配离散的磁盘块。
分为隐式链接和显式链接两种。

6.2.1 隐式链接

除文件的最后一个盘块之外，每个盘块中都存有指向下一个盘块的指针。文件目录包括文件第一块的指针和最后一块的指针。

优点：很方便文件拓展，不会有碎片问题，外存利用率高。
缺点：只支持顺序访问，不支持随机访问，查找效率低，指向下一个盘块的指针也需要耗费少量的存储空间。

6.2.2 显式链接（重点）

• 核心思想：把用于链接文件各物理块的指针显式地存放在一张表中。即 文件分配表（FAT，File Allocation Table）。
  • 文件分配表的表项 = 物理块号+下一块
  • 当某表项的下一块为-1表示该物理块为某个文件的最后一块。
  • 当某表项的下一块为≤-2表示该物理块为空闲块，故FAT可用于文件系统管理空闲磁盘块的数据结构。
• 一个磁盘仅设置一张FAT。开机时，将FAT读入内存，并常驻内存。 FAT 的各个表项在物理上连续存储，且每一个表项长度相同，因此物理块号字段可以是隐含的。
• 显式链接对应FAT文件系统，使用文件控制块FCB方式而没有使用索引节点inode方式。

【示例】假设某个新创建的文件“aaa”依次存放在磁盘块 2 → 5 → 0 → 1，某个新创建的文件“bbb”依次存放在磁盘块 4 → 23 → 3，得到对应的磁盘分配情况、文件目录表及其FAT。

解析：
磁盘分配情况如下：

橙色代表文件“aaa”的磁盘分配情况。
紫色代表文件“bbb”的磁盘分配情况。

文件目录内容如下：

目录中只需记录文件的起始块号。

FAT（文件分配表）内容如下：

(1) 如何实现文件的逻辑块号到物理块号的转变？
用户给出要访问的逻辑块号 i，操作系统找到该文件对应的目录项（FCB），从目录项中找到起始块号，若i>0，则查询内存中的文件分配表FAT，往后找到 i 号逻辑块对应的物理块号。
因为FAT在内存中，所以逻辑块号转换成物理块号的过程不需要读磁盘操作。

(2) 优缺点

• 优点
  • 采用链式分配（显式链接）方式的文件，支持顺序访问，也支持随机访问（想访问 i 号逻辑块时，并不需要依次访问之前的 0 ~ i-1号逻辑块，只需要在FAT表中查找）；
  • 由于块号转换的过程不需要访问磁盘，因此相比于隐式链接来说，访问速度快很多。
  • 显式链接也不会产生外部碎片，也可以很方便地对文件进行拓展。
• 缺点
  • 文件分配表的需要占用一定的存储空间。

注意：考试题目中遇到未指明隐式/显式的“链接分配”，默认指的是隐式链接的链接分配。

6.3 索引分配

• 核心思想索引分配允许文件离散地分配在各个磁盘块中，系统会为每个文件建立一张索引表（FAT），索引表中记录了文件的各个逻辑块对应的物理块（索引表的功能类似于内存管理中的页表——建立逻辑页面到物理页之间的映射关系）。
• 索引表存放的磁盘块称为索引块。文件数据存放的磁盘块称为数据块。
• 索引表中的“逻辑块号”可以是隐含的。

【示例】假设某个新创建的文件“aaa”依次存放在磁盘块 2 → 5 → 0 → 1，文件“bbb”的索引块是23号磁盘块 ，得到对应的磁盘分配情况、文件目录表及其文件”aaa“的FAT。

解析：
磁盘分配情况如下：

文件目录内容如下：

目录中需要记录文件的索引块是几号磁盘块，7号磁盘块作为“aaa”的索引块，索引块中保存了索引表的内容。

文件”aaa“对应的FAT内容如下：

注：在显式链接的链式分配方式中，文件分配表FAT 是一个磁盘对应一张。而索引分配方式中，索引表是一个文件对应一张。

(1) 如何实现文件的逻辑块号到物理块号的转换？
用户给出要访问的逻辑块号 i，操作系统找到该文件对应的目录项（FCB）…
从目录项中可知索引表存放位置，将索引表从外存读入内存，并查找索引表即可知 i 号逻辑块在外存中的存放位置。

(2) 优缺点

• 优点：
  • 索引分配方式可以支持随机访问
  • 文件拓展也很容易实现（只需要给文件分配一个空闲块，并增加一个索引表项即可）
• 缺点：
  • 索引表需要占用一定的存储空间

(3) 索引表太大，如何解决？
若文件太大，索引表项太多，可以采取以下三种方法解决：

• 链接方案
• 多层索引
• 混合索引

6.3.1 链接索引

如果索引表太大，一个索引块装不下，那么可以将多个索引块链接起来存放。

假设磁盘块大小为1KB，一个索引表项占4B，则一个磁盘块只能存放256个索引项。若一个文件大小为 256 * 256KB =65,536 KB = 64MB，该文件共有 256 * 256 个块，也就对应256 * 256个索引项，也就需要 256 个索引块来存储，这些索引块用链接方案连起来。

缺点：若文件很大，索引表很长，就需要将很多个索引块链接起来。想要找到 i 号索引块，必须先依次读入 0~i-1号索引块，这就导致磁盘I/O次数过多，查找效率低下。

6.3.2 多层索引

建立多层索引（原理类似于多级页表）。使第一层索引块指向第二层的索引块。还可根据文件大小的要求再建立第三层、第四层索引块。

若采用多层索引，则各层索引表大小不能超过一个磁盘块。

【题型1】求文件的最大长度
假设磁盘块大小为1KB，一个索引表项占4B，则一个磁盘块只能存放256 个索引项。若某文件采用两层索引，则该文件的最大长度可以到256 * 256 * 1KB = 65,536 KB = 64MB。

【题型2】求访问文件的一个数据块需要的磁盘I/O次数
可根据逻辑块号算出应该查找索引表中的哪个表项。
如：要访问 1026 号逻辑块，则1026/256 = 4，1026%256 = 2
因此可以先将一级索引表调入内存，查询 4 号表项，将其对应的二级索引表调入内存，再查询二级索引表的2号表项即可知道 1026 号逻辑块存放的磁盘块号了。
访问目标数据块，需要3次磁盘I/O。

缺点：采用 K 层索引结构，且顶级索引表未调入内存，则访问一个数据块只需要 K + 1 次读磁盘操作。即使是小文件，访问一个数据块依然需要K+1次读磁盘。

6.3.3 混合索引（重点）

多种索引分配方式的结合。例如，一个文件的顶级索引表中，既包含直接地址索引（直接指向数据块），又包含一级间接索引（指向单层索引表）、还包含两级间接索引（指向两层索引表） 。

• 上述这种结构的索引支持的最大文件长度为 (65536+256+8) * 1KB = 65800KB。
• 若顶级索引表还没读入内存：
  • 访问 0~7 号逻辑块：两次读磁盘
  • 访问 8~263：三次读磁盘
  • 访问 264~ 65799：四次读磁盘
• 优点：对于小文件来说，访问一个数据块所需的读磁盘次数更少。
• 混合索引对应的是Unix系统的UFS文件系统，使用索引节点inode方式而没有使用文件控制块FCB方式。

6.4 分配方式总结

		核心思想	目录项内容	优点	缺点
顺序分配		为文件分配的必须是连续的磁盘块	起始块号、文件长度	顺序存取速度快，支持随机访问	会产生碎片，不利于文件拓展
链接分配	隐式链接	除文件的最后一个盘块之外，每个盘块中都存有指向下一个盘块的指针	起始块号、结束块号	可解决碎片问题，外存利用率高，文件拓展实现方便	只能顺序访问，不能随机访问
	显式链接	建立一张文件分配表(FAT)，显式记录盘块的先后关系（开机后FAT常驻内存）	起始块号	除了拥有隐式链接的优点之外，还可通过查询内存中的FAT实现随机访问	FAT需要占用一定的存储空间
索引分配		为文件数据块建立索引表。若文件太大，可采用链接方案、多层索引、混合索引	链接方案记录的是第一个索引块的块号，多层/混合索引记录的是顶级索引块的块号	支持随机访问，易于实现文件的拓展	索引表需占用一定的存储空间。链接方案，查找索引块时可能需要很多次读磁盘操作。

二、目录

1. 目录的基本概念

FCB的有序集合称为文件目录，一个FCB就是一个文件目录项。与文件管理系统和文件集合相关联的是文件目录，它包含有关文件的属性、位置和所有权等。
首先来看目录管理的基本要求：

• 从用户的角度看，目录在用户（应用程序）所需要的文件名和文件之间提供一种映射，所以目录管理要实现“按名存取”；
• 目录存取的效率直接影响到系统的性能，所以要提高对目录的检索速度；
• 在多用户系统中，应允许多个用户共享一个文件，因此目录还需要提供用于控制访问文件的信息；
• 允许不同用户对不同文件采用相同的名字，以便于用户按自己的习惯给文件命名，目录管理通过树形结构来解决和实现。

2. 目录结构

2.1 单极目录结构

整个系统中只建立一张目录表，每个文件占一个目录项，如下图：

优缺点：

• 当建立一个新文件时，必须先检索所有目录项，以确保没有“重名”的情况，然后在该目录中增设一项，将新文件的属性信息填入该项。当访问一个文件时，先按文件名在该目录中查找到相应的 FCB，经合法性检查后执行相应的操作。当删除一个文件时，先从该目录中找到该文件的目录项，回收该文件所占用的存储空间，然后清除该目录项。
• 单级目录结构实现了“按名存取”，但是存在查找速度慢、文件不允许重名、不便于文件共享等缺点，而且对于多用户的操作系统显然是不适用的。

2.2 两级目录结构

早期的多用户操作系统，采用两级目录结构。分为主文件目录（MFD，Master File Directory）和用户文件目录（UFD，User Flie Directory），如下图：

• 主文件目录记录用户名及相应用户文件目录的存放位置
• 用户文件目录由该用户的文件FCB组成

优缺点：

• 两级目录结构允许不同用户的文件重名，也可以在目录上实现实现访问限制（检查此时登录的用户名是否匹配）。
• 两级目录结构依然缺乏灵活性，用户不能对自己的文件进行分类。

2.3 树形目录结构

将两级目录结构加以推广，就形成了树形目录结构，如下图：

用户（或用户进程）要访问某个文件时要用文件路径名标识文件，文件路径名是个字符串。各级目录之间用“/”隔开。

• 从根目录出发的路径称为绝对路径。例如：自拍.jpg 的绝对路径是 “/照片/2015-08/自拍.jpg”。
• 每次都从根目录开始查找，是很低效的。因此可以设置一个“当前目录”。例如，此时已经打开了“照片”的目录文件，也就是说，这张目录表已调入内存，那么可以把它设置为“当前目录”。当用户想要访问某个文件时，可以使用从当前目录出发的“相对路径”，其本质就是该目录的文件目录加载到了内存 。在 Linux 中，“.”表示当前目录，因此如果“照片”是当前目录，则”自拍.jpg”的相对路径为：“./2015-08/自拍.jpg”。
• 可见，引入“当前目录”和“相对路径”后，磁盘I/O的次数减少了。这就提升了访问文件的效率。

优缺点：

• 在该树形目录结构下，层次结构清晰，能进行更有效的文件管理和保护，不同用户、不同性质的文件可呈现在系统目录树下的不同层次或不同子树中，很容易被赋予不同的存取权限。
• 但是在搜索文件时，需要根据路径名逐级访问中间节点，这增加了磁盘访问次数。
• 树形结构不便于实现文件的共享。为此，提出了“无环图目录结构”。

目前，Windows、UNIX、Linux系统均采用了树形文件目录。

2.4 无环图目录结构

在树形目录结构的基础上，增加一些指向同一节点的有向边，使整个目录成为一个有向无环图。可以更方便地实现多个用户间的文件共享，如下图：

• 可以用不同的文件名指向同一个文件，甚至可以指向同一个目录（共享同一目录下的所有内容）。
• 需要为每个共享结点设置一个共享计数器，用于记录此时有多少个地方在共享该结点。
  • 用户提出删除结点的请求时，只是删除该用户的FCB、并使共享计数器减1，并不会直接删除共享结点。
  • 只有共享计数器减为0时，才删除结点。

注意：共享文件不同于复制文件。在共享文件中，由于各用户指向的是同一个文件，因此只要其中一个用户修改了文件数据，那么所有用户都可以看到文件数据的变化。

3. 目录的操作

在理解一个文件系统的需求前，我们首先考虑在目录这个层次上所需要执行的操作，这有助于后面文件系统的整体理解。

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

4. 目录的实现

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

4.1 线性列表

最简单的目录实现方法是，采用文件名和数据块指针的线性列表。

• 当创建新文件时，必须首先搜索目录以确定没有同名的文件存在，然后在目录中增加一个新的目录项。
• 当删除文件时，则根据给定的文件名搜索目录，然后释放分配给它的空间。采用链表结构可以减少删除文件的时间。
• 重用目录项：文件系统中用于优化存储空间和管理效率的一种机制，其核心思想是回收已删除文件的目录项（记录文件元数据的数据结构），供新文件或目录重复使用。
  • 为什么要“重用”目录项？
    直接原因：删除文件后，其对应的目录项并不会被物理擦除，而是被标记为“空闲”。直接复用这些空闲项可以：
    • 节省存储空间：避免频繁分配新目录项导致存储浪费。
    • 提升性能：减少磁盘碎片，加快文件创建速度。
  • 重用目录项的触发条件
    • 文件删除：删除文件时，目录项被标记为“空闲”而非立即擦除，允许后续重用。
    • 空间回收：避免目录项碎片化，提高存储利用率。
  • 当要重用目录项时，有许多种方法：
    • 标记为不再使用：当目录项不再需要时，可以将其标记为“无效”或“不再使用”。这样，当需要新的目录项时，系统可以检查这些标记为无效的目录项，并重新分配它们；
    • 添加到空闲列表：系统可以维护一个空闲目录项列表，用于跟踪当前未使用的目录项。当需要新的目录项时，系统可以从这个列表中分配一个空闲的目录项；
    • 移动并更新：在某些情况下，系统可能会将不再需要的目录项的内容复制到另一个空闲位置，并更新相关的指针或引用以指向新的位置。然后，原始位置可以被视为空闲，并可用于未来的目录项分配。

优缺点：线性列表的优点在于实现简单，不过由于线性表的特殊性，查找比较费时。

4.2 哈希表

除了采用线性列表存储文件目录项，还可以采用哈希数据结构。哈希表根据文件名得到一个值，并返回一个指向线性列表中元素的指针。这种方法的优点是查找非常迅速，插入和删除也较简单，不过需要一些措施来避免冲突(两个文件名称哈希到同一位置)。

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

5. 文件共享

操作系统为用户提供文件共享功能，可以让多个用户共享地使用同一个文件。文件共享的两种方式：

• 硬链接
• 软链接

注意：

• 多个用户共享同一个文件，意味着系统中只有“一份”文件数据。并且只要某个用户修改了该文件的数据，其他用户也可以看到文件数据的变化。
• 如果是多个用户都“复制”了同一个文件，那么系统中会有“好几份”文件数据。其中一个用户修改了自己的那份文件数据，对其他用户的文件数据并没有影响。

5.1 基于索引结点的共享方式（硬链接）

在树形结构的目录中，当有两个或多个用户要共享一个子目录或文件时，必须将共享文件或子目录链接到两个或多个用户的目录中，才能方便地找到该文件，如下图所示：

• 硬链接是基于索引节点的共享方式，诸如文件的物理地址及其他的文件属性等信息，不再放在目录项中，而放在索引结点中。在文件目录中只设置文件名及指向相应索引结点的指针。
• 在索引结点中还应有一个链接计数count，用于表示链接到本索引结点（即文件）上的用户目录项的数目。
  • 若 count = 2，说明此时有两个用户目录项链接到该索引结点上，或者说是有两个用户在共享此文件。若某个用户决定“删除”该文件，则只是要把用户目录中与该文件对应的目录项删除，且索引结点的count值减 1。
  • 若 count>0，说明还有别的用户要使用该文件，暂时不能把文件数据删除，否则会导致指针悬空。
  • 当 count = 0 时系统负责删除文件。

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

为使用户B能共享用户A的一个文件F，可以由系统创建一个Link 类型的新文件，取名为L，并将文件L写入用户B的目录中，以实现用户B的目录与文件F的链接。在新文件中只包含被链接文件F的路径名。这样的链接方法被称为符号链接。

Link 类型的文件，记录了文件的存放路径。类似于 Windows 操作系统的“快捷方式”。

【示例】创建一个QQ的快捷方式

双击打开时，操作系统判断这个文件是Link类型的“快捷方式”文件，于是会根据其中记录的“路径信息”检索目录，最终找到“QQScLauncher.exe”。

软链接的特点：

• 操作系统根据路径一层层查找目录，最终找到共享文件。由于用软链接的方式访问共享文件时要查询多级目录，会有多次磁盘I/O，因此用软链接访问共享文件的速度要比硬链接更慢。
• 利用符号链方式实现文件共享时，只有文件主才拥有指向其索引节点的指针。而共享该文件的其他用户只有该文件的路径名，并不拥有指向其索引节点的指针。这样，也就不会发生在文件主删除一个共享文件后留下一个悬空指针的情况。当文件主将一个共享文件删除后，若其他用户又试图通过符号链去访问它时，则会访问失败，于是再将符号链删除，此时不会产生任何影响。
• 利用符号链实现文件共享存在一个微妙的问题。例如，一个文件采用符号链方式共享，当文件拥有者将其删除，而在共亨的其他用户使用其符号链接访问该文件之前，又有人在同一路径下创建了另一个具有同样名称的文件，则该符号链将仍然有效，但访问的文件已经改变，从而导致错误。

三、文件系统

1. 文件系统的层次结构

• 用户接口：文件系统需要向上层的用户提供一些简单易用的功能接口。这层就是用于处理用户发出的系统调用请求（Read、Write、Open、Close 等系统调用）。
• 文件目录系统：用户是通过文件路径来访问文件的，因此这一层需要根据用户给出的文件路径找到相应的FCB或索引结点。所有和目录、目录项相关的管理工作都在本层完成，如：管理活跃的文件目录表、管理打开文件表等。
• 存取控制模块：为了保证文件数据的安全，还需要验证用户是否有访问权限。这一层主要完成了文件保护相关功能。
• 逻辑文件系统与文件信息缓冲区：用户指明想要访问文件记录号，这一层需要将记录号转换为对应的逻辑地址。
• 物理文件系统：这一层需要把上一层提供的文件逻辑地址转换为实际的物理地址。
• 辅助分配模块：负责文件存储空间的管理，即负责分配和回收存储空间。
• 设备管理模块：直接与硬件交互，负责和硬件直接相关的一些管理工作。如：分配设备、分配设备缓冲区、磁盘调度、启动设备、释放设备等。

【示例】假设某用户请求删除文件 “D:/工作目录/学生信息.xlsx” 的最后100条记录。

• ① 用户需要通过操作系统提供的接口发出上述请求 —— 用户接口
• ② 由于用户提供的是文件的存放路径，因此需要操作系统一层一层地查找目录，找到对应的目录项 —— 文件目录系统
• ③ 不同的用户对文件有不同的操作权限，因此为了保证安全，需要检查用户是否有访问权限 —— 存取控制模块（存取控制验证层）
• ④ 验证了用户的访问权限之后，需要把用户提供的“记录号”转变为对应的逻辑地址 —— 逻辑文件系统与文件信息缓冲区
• ⑤ 知道了目标记录对应的逻辑地址后，还需要转换成实际的物理地址 —— 物理文件系统
• ⑥ 要删除这条记录，必定要对磁盘设备发出请求 —— 设备管理程序模块
• ⑦ 删除这些记录后，会有一些盘块空闲，因此要将这些空闲盘块回收 —— 辅助分配模块

2. 文件系统的全局结构（layout）

文件系统的全局结构描述了数据在存储设备上的物理和逻辑组织形式，涵盖外存（磁盘、U盘等）的持久化存储和内存中的动态管理。理解这一结构的关键在于明确外存与内存的协作机制，以及它们在文件操作中的具体分工。以下从逻辑分层角度重新梳理，重点强调内存与外存的交互流程。

2.1 文件系统在外存中的结构

文件系统在外存中的结构是数据存储的物理基础。

(1) 物理格式化

• 划分磁盘为扇区（Sector），检测并标记坏扇区，由硬件控制器管理替换。
  
  • 扇区是磁盘的最小物理单元（通常512B或4KB）。
  • 坏扇区对操作系统是透明的，操作系统不知道坏扇区的存在。

(2) 逻辑格式化

• 逻辑格式化在物理格式化的基础上，将磁盘分区（Volume）初始化为特定文件系统（如ext4、NTFS）。例如下图中，C盘中建立了UNIX文件系统：
  

模块	功能	类比
引导块	存储启动代码（如操作系统引导程序），仅系统盘需要。	计算机的“开机按钮”
超级块	存储文件系统元数据（总容量、块大小、inode总数、空闲块列表等）。	文件系统的“身份证”
空闲空间管理	通过位图（ext4）或链表（FAT）记录空闲块。	仓库的“库存清单”
i-node区	存储索引节点（i-node），每个i-node对应一个文件的元数据（权限、时间戳、数据块指针等）。	文件的“档案柜”
根目录	文件系统的起点，通过目录项（Directory Entry）记录子文件和子目录的i-node号。	图书馆的“总目录索引”

注：逻辑格式化完成后，文件系统已具备基本框架，但数据区（白色部分）尚未存储用户文件。

2.2 文件系统在内存中的结构

内存中的数据结构用于加速文件访问和管理运行时状态，其内容在挂载文件系统时加载，卸载时释放。以下是核心模块及其与外存的协作关系：

主要包括如下信息：

• 文件描述符：通过文件描述符，用户可以对文件进行相应操作。
• 目录的缓存：最近访问的目录的数据会被暂时缓存在内存中，能加快目录检索速度。
• 系统打开文件表：整个系统只有一张，包含每个打开文件的FCB副本、打开计数等信息。
• 进程（用户）打开文件表：每个进程都有一个打开文件表，这个打开文件表被保存在每个进程的PCB中。记录了每个进程当前打开了哪些文件。

当用户想要对某文件进行相应操作，内存和外存如何配合工作，例如我们现在想要打开目录M中的文件A：
① open(…/M/A,只读)；根据路径一级一级读入目录；
② 找到目标文件的FCB，复制到系统打开文件表，同时将其“打开计数”设为1；
③ 在进程打开文件表中新建一个条目，记录打开方式，并不会记录A文件的FCB，只会通过索引指向系统打开文件表对应的条目，进而得到FCB；
④ 接下来，返回文件描述符，通过这一文件描述符就可以对文件A进行打开操作。

如果想要对文件A进行读操作系统调用，就只需要传入文件描述符fd，同时指明要读多少字节，读的范围：read(fd,xxx,xxx)，接着找到对应的进程打开文件表，根据索引信息，找到系统打开文件表，通过系统打开文件表找到文件A对应的FCB，操作系统就可以确定文件A在外存中的存放位置。如下图所示：

3. 外存空闲空间管理

3.1 存储空间的划分和初始化

(1) 文件卷（逻辑卷）的概念
一个存储设备可以按整体用于文件系统，也可以细分。包含文件系统的分区通常称为卷（volumn）。
逻辑卷和物理盘的关系：

• 卷是磁盘的一部分；
• 卷是整个磁盘；
• 卷是多个磁盘组成的RAID集。

(2) 目录区与文件区
存储空间的初始化：将各个文件卷划分为文件区、目录区。

• 文件区用于存放文件数据。
• 目录区主要存放文件目录信息（FCB）、用于磁盘存储空间管理的信息。

3.2 磁盘空闲空间管理的方法

3.2.1 空闲表法

空闲表法属于连续分配方式，它与内存的动态分区分配类似，为每个文件分配一块连续的存储空间。系统为外存上的所有空闲区建立一张空闲表，每个空闲区对应一个空闲表项，其中包括表项序号（可省）、该空闲区的第一个空闲盘块号、该空闲区的空闲盘块数等信息。再将所有空闲区按其起始盘块号递增的次序排列，如下图所示：

注：绿色表示空闲块，橙色表示非空闲块

盘块的分配：
空闲盘区的分配与内存的动态分配类似，也是采用首次适应算法、最佳适应算法等。例如，在系统为某新创建的文件分配空闲盘块时，先顺序地检索空闲盘块表的各表项，直至找到第一个其大小能满足要求的空闲区，再将该盘区分配给用户，同时修改空闲盘块表。

盘块的回收：
与内存管理中的动态分区分配很类似，当回收某个存储区时需要有四种情况：
① 回收区的前后都没有相邻空闲区；
② 回收区的前后都是空闲区；
③ 回收区前面是空闲区；
④ 回收区后面是空闲区。
总之，回收时需要注意表项的合并问题。

空闲表法的优点是具有较高的分配速度，可减少访问磁盘的I/O频率。对于较小的文件(1~5个盘块)，可以采用连续分配方式为文件分配几个相邻的盘块。

3.2.2 空闲链表法

空闲链表法是指将所有空闲盘区拉成一条空闲链，可分为以下两种：

• 空闲盘块链：以盘块为单位组成一条空闲链
• 空闲盘区链：以盘区为单位组成一条空闲链

(1) 空闲盘块链
以盘块为单位组成一条空闲链，示意图：

• 空闲盘块中存储着下一个空闲盘块的指针。
• 操作系统保存着链头、链尾指针。

盘块的分配：若某文件申请 K 个盘块，则从链头开始依次摘下 K 个盘块分配，并修改空闲链的链头指针。
盘块的回收：回收的盘块依次挂到链尾，并修改空闲链的链尾指针。

(2) 空闲盘区链
以盘区为单位组成一条空闲链，示意图：

• 连续的空闲盘块组成一个空闲盘区。
• 空闲盘区中的第一个盘块内记录了盘区的长度、下一个盘区的指针。
• 操作系统保存着链头、链尾指针。

盘块的分配：若某文件申请 K 个盘块，则可以采用首次适应、最佳适应等算法，从链头开始检索，按照算法规则找到一个大小符合要求的空闲盘区，分配给文件。若没有合适的连续空闲块，也可以将不同盘区的盘块同时分配给一个文件，注意分配后可能要修改相应的链指针、盘区大小等数据。

盘块的回收：若回收区和某个空闲盘区相邻，则需要将回收区合并到空闲盘区中。若回收区没有和任何空闲区相邻，将回收区作为单独的一个空闲盘区挂到链尾。

离散分配、连续分配都适用。为一个文件分配多个盘块时效率更高。

3.2.3 位示图法

位示图：每个二进制位对应一个盘块。在本例中，“0”代表盘块空闲，“1”代表盘块已分配。位示图一般用连续的“字”来表示，如本例中一个字的字长是16位，字中的每一位对应一个盘块。因此可以用（字号，位号）对应一个盘块号。当然有的题目中也描述为（行号，列号）。

重要重要重要：要能自己推出盘块号与（字号, 位号）相互转换的公式。注意题目条件：盘块号、字号、位号到底是从0开始还是从1开始。盘块号、字号、位号都从0开始的情况：

• (字号, 位号)=(i, j) 的二进制位对应的 盘块号 b = ni + j
• b号盘块对应的字号 i = b/n，位号 j = b%n

盘块的分配：若文件需要K个块，
① 顺序扫描位示图，找到K个相邻或不相邻的“0”；
② 根据字号、位号算出对应的盘块号，将相应盘块分配给文件；
③ 将相应位设置为“1”。

盘块的回收：
① 根据回收的盘块号计算出对应的字号、位号；
② 将相应二进制位设为“0”。

3.2.4 成组链接法

空闲表法、空闲链表法不适用于大型文件系统，因为空闲表或空闲链表可能过大。UNIX系统中采用了成组链接法对磁盘空闲块进行管理。
文件卷的目录区中专门用一个磁盘块作为“超级块”，当系统启动时需要将超级块读入内存。并且要保证内存与外存中的“超级块”数据一致。

成组链接法思想：将空闲盘块分成若干组，如100个盘块作为一组，每组的第一个盘块记录下一组的空闲盘块总数和空闲盘块号。这样，由各组的第一个盘块可以链接成一条链。第一组的空闲盘块总数和空闲盘块号保存在内存的专用栈中，称为空闲盘块号栈。假设系统空闲区为 第201~7999号 盘块，则第一组的盘块号为201~300……次末组的盘块号为 7801~7900 ，最末一组的盘块号为7901~7999。最末一组只有99个盘块，它们的块号记录在前一组的7900号盘块中，该块中存放的第一个盘块号是“0”，以作为空闲盘块链的结束标记，如下图所示：

简而言之，每组（除了最后一组)的第一块作为索引块，然后将这些索引块链接起来。
注意：一个分组中的块号不需要连续，此处只是为了让大家更方便看出各个分组的数量。

盘块的分配：两种情况
Eg ：需要1个空闲块
① 检查第一个分组的块数是否足够。1<100，因此是足够的；
② 分配第一个分组中的1个空闲块，并修改相应数据。
分配过后空闲块的情况如下图：

Eg ：需要100个空闲块
① 检查第一个分组的块数是否足够。100=100，是足够的。
② 分配第一个分组中的100个空闲块。但是由于300号块内存放了再下一组的信息，因此300号块的数据需要复制到超级块中。
分配过后空闲块的情况如下图：

盘块的回收：两种情况
Eg ：假设每个分组最多为100个空闲块，此时第一个分组已有99个块，还要再回收一块
回收过后空闲块的情况如下图：

Eg ：假设每个分组最多为100个空闲块，此时第一个分组已有100个块，还要再回收一块。
需要将超级块中的数据复制到新回收的块中，并修改超级块的内容，让新回收的块成为第一个分组。
回收过后空闲块的情况如下图：

4. 虚拟文件系统

虚拟文件系统（Virtual File System，VFS）是操作系统内核中的抽象层，其核心目标是屏蔽不同文件系统的差异，为用户提供统一的文件操作接口，如下图所示：

通过VFS，用户无需关心文件存储在何种文件系统（如ext4、NTFS、FAT）或介质（磁盘、U盘、网络存储）中，只需调用标准API（如open()、read())即可操作文件。

(1) 为什么需要VFS？

• 问题：不同文件系统（ext4、NTFS、FAT）的底层实现差异大，若用户直接操作具体文件系统，需为每个系统编写不同代码。
• 解决方案： VFS定义通用文件模型，要求所有文件系统实现统一的接口（如open()、read()）。
  • 对用户透明：用户通过统一API操作文件。
  • 对开发者透明：新文件系统只需适配VFS接口即可被内核支持。

(2) VFS的四大核心对象
VFS通过四个对象抽象文件系统的核心元素，这些对象在内存中动态创建，是逻辑实体（无持久化存储）：

对象	角色	类比	生命周期
超级块对象	代表一个已挂载的文件系统（如某个ext4分区），用于存储已安装文件系统的元信息	公司总部（统筹管理分支部门）	挂载时创建，卸载时销毁
索引节点对象	代表一个文件（含元数据：权限、时间戳、数据块指针等）	员工档案（记录个人详细信息）	文件被访问时创建，关闭后可能缓存
目录项对象	代表路径中的一个组成部分（如/home/user中的home或user）	导航路标（标识路径分支）	解析路径时动态生成，缓存后复用
文件对象	代表进程已打开的文件实例（含访问模式、文件指针等上下文）	工作台（进程操作文件的接口）	open()时创建，close()时释放

【VFS的工作流程示例】以用户调用open(“/home/user/file.txt”)为例，说明VFS如何协调四大对象完成操作：

步骤①：解析路径

• 分解路径：将路径拆解为目录层级（/ → home → user → file.txt）。
• 逐级查找目录项：
  • VFS从根目录（/）的索引节点开始，查找home对应的目录项（dentry）。
  • 若目录项未缓存，则触发文件系统的lookup()方法，从磁盘读取目录数据并生成目录项对象。
• 递归解析：重复上述过程，直到找到file.txt的索引节点（inode）。

步骤②：创建文件对象

• 初始化文件对象：
  • 根据索引节点创建文件对象，记录访问模式（如只读）、文件指针位置等。
• 关联进程：
  • 在进程的打开文件表中添加条目，指向该文件对象。
• 返回文件描述符：
  • 用户获得一个整型文件描述符（如fd=3），用于后续操作（read/write）。

步骤③：数据访问

• 用户调用read(fd)时：
  • 通过fd找到文件对象→索引节点→数据块指针→读取磁盘数据。

(3) 虚拟文件系统的特点
虚拟文件系统采用了面向对象的思想，它抽象出了一个通用的文件系统模型，定义了通用文件系统都支持的接口。

① 向上层用户进程提供统一标准的系统调用接口，屏蔽底层具体文件系统的实现差异；
② VFS要求下层的文件系统必须实现某些规定的函数功能，如：open/read/write。一个新的文件系统想要在某操作系统上被使用，就必须满足该操作系统VFS的要求；
③ 每打开一个文件，VFS就在主存中新建一个 vnode，用统一的数据结构表示文件，无论该文件存储在哪个文件系统。

注意：vnode 只存在于主存中，而 inode 既会被调入主存，也会在外存中存储。

严格来说，VFS并不是一种实际的文件系统，它只存在于内存中，不存在于任何外存空间中。VFS在系统启动时建立，在系统关闭时消亡。

5. 文件系统挂载（mounting）

文件系统挂载（mounting），即文件系统安装/装载——如何将一个文件系统挂载到操作系统中？
文件系统挂载要做的事：
① 在VFS中注册新挂载的文件系统。内存中的挂载表（mount table）包含每个文件系统的相关信息，包括文件系统类型、容量大小等。
② 新挂载的文件系统，要向VFS提供一个函数地址列表。
③ 将新文件系统加到挂载点（mount point），也就是将新文件系统挂载在某个父目录下。

注意：Windows 默认不将 U 盘挂载到 目录，而是分配 驱动器号（如 E:）。

四、大题考点总结

1. 在一级目录中查找某个文件平均访问的磁盘次数
关键点：计算所有文件目录项占多少个簇或盘。分为：

• FCB类型
• inode类型

注意：查找一个文件是指找到文件对应的目录项或inode结点，而不是找到文件的数据。

【示例1】在一个文件系统中，FCB占64B，盘块大小为1KB，采用一级目录。假定文件目录中有3200个目录项，则查找一个文件平均需要（）次访问磁盘。
A. 50    B. 54    C. 100    D. 200

解析：FCB类型
所有目录项所占的磁盘块数：(3200*64B)/1KB=200块
故找到某个文件的目录项平均需要100.5≈100次访问磁盘

【示例2】设某文件系统中每个盘块占1KB，索引节点编号占4B，文件名也占4B。则对一个具有640个文件的目录而言，为了找到某个文件的索引节点平均需要启动（）次磁盘。
A. 3    B. 4    C. 5    D. 6

解析：inode类型
所有目录项所占的磁盘块数：(640*(4B+4B))/1KB=5块
故找到某个文件的目录项平均需要3次访问磁盘
而inode类型，还需要根据文件目录项找到指向的inode结点，故总共3+1=4次

2. 计算文件的最大长度
(1) 显式链接方式
关键点：FAT的表项中存放的是下一个簇的簇号（或下一个盘的盘号），故根据FAT的表项大小可知总共有多少个簇或盘块。

【2016统考真题】某磁盘文件系统使用链接分配方式组织文件，簇大小为4KB。目录文件的每个目录项包括文件名和文件的第一个簇号，其他簇号存放在文件分配表FAT中。若FAT的每个表项仅存放簇号，占2B，则FAT的最大长度为多少字节？该文件系统支持的文件长度最大是多少？

解析：
簇号占2B→有2¹⁶个簇，
故FAT的最大长度为：2¹⁶×2B=128KB，
该文件系统支持的文件长度最大是2¹⁶×4KB=256MB

(2) 混合索引方式
关键点：计算出一个簇或一个盘块能存放多少个地址项。

【2018统考真题】某文件系统采用索引节点存放文件的属性和地址信息，簇大小为4KB。每个文件索引节点占64B，有11个地址项，其中直接地址项8个，一级、二级和三级间接地址项各1个，每个地址项长度为4B。该文件系统能支持的最大文件长度是多少？（给出计算表达式即可）

解析：
簇大小为4KB，每个地址项长度为4B，因此每簇有4KB/4B=1024个地址项。最大文件的物理块数可达8+1×1024+1×1024²+1×1024³，每个物理块（簇）大小为4KB，因此最大文件长度为(8+1×1024+1×1024²+1×1024³)×4KB=32KB+4MB+4GB+4TB。

3. 访问文件的某个数据块所需的读磁盘次数
关键点：文件系统一般采用混合索引，此时关键是分析数据在第几个簇或盘。

【2026王道4】某操作系统提供了文件操作的接口，包括open()、read()、write()和close()等函数。文件系统采用混合索引分配方式，每个索引节点(inode）占64B，每个地址项占4B，包含10个直接索引地址项、1个一级间接索引地址项和1个二级
间接索引地址项，磁盘块大小为4KB，整个文件系统最多拥有4TB 的空间。现有一个文件系统，它包含如右图所示的文件和目录结构。

（1）假设文件系统已将用户user1的文件 file1.txt 和 file2.txt 的索引节点加载到内存中，用户user1打开文件file1.txt并读取其中的某块，如果 file1.txt 的大小为5MB，则打开该文件并将其读入内存需要几次读磁盘块操作？说明理由。
（2)假设文件系统已将用户user2 的文件 file3.txt 的索引节点加载到内存中，用户user2打开文件file3.txt并写入12KB的数据需要进行几次磁盘块的写入操作？假设文件长度小于4124KB，若修改了磁盘索引节点，则需要将磁盘索引节点重新写回外存。

解析：
（1）磁盘块大小为4KB，file1.txt占5MB，即占5MB/4KB=1280块，其中10个直接地址项指向10个磁盘块，1个一级间接索引地址项指向4KB/4B=1024个磁盘块，1个二级间接索引地址项指向1024×1024个磁盘块。因此，分三种情况讨论：
① 若读取的数据在文件的前40KB，对应直接地址项，则只需1次读磁盘块操作；
② 若读取的数据在文件的40KB和(1024+10)×4KB=4136KB之间，对应一级间接索引地址项，则需要先读取1次一级间接索引块，再读取1次对应的数据块，共需2次读磁盘块操作；
③ 同理，若读取的数据在文件的4136KB和5MB之间，对应二级间接索引地址项，则需3次读磁盘块操作。

（2）插入12KB的数据，即向文件中插入3个磁盘块，如果原文件长度小于或等于28KB（7个磁盘块），就不需要修改一级间接索引，只需修改直接索引项并写回索引节点所在的磁盘块，加上写回3个插入的磁盘块，共需4次写磁盘块操作。
如果原文件长度大于28KB且小于4124KB（10+1021个磁盘块)，就需要修改索引节点中的一级间接索引项所指向的磁盘块，并写回索引节点所在的磁盘块（文件大小发生变化）和一级间接索引项所指向的磁盘块，加上写回3个插入的磁盘块，共需5次写磁盘操作。

4. 一个文件会使用索引结点的哪几类地址项
关键点：根据文件的大小计算出所占的簇数或磁盘块数，然后与各级地址项的的包含的块数进行比较。

【2022统考真题】某文件系统的磁盘块大小为4KB，目录项由文件名和索引节点号构成，每个索引节点占256字节，其中包含直接地址项10个，一级、二级和三级间接地址项各1个，每个地址项占4字节。若存在文件course的大小为6MB，则为了存取course需要使用该文件索引节点的哪几级间接地址项？说明理由。

解析：存取course需要使用索引节点的一级和二级间接地址项。
6MB大小的文件需要占用6MB/4KB=1536个磁盘块。直接地址项可以记录10个磁盘块号，一级间接地址块可以记录4KB/4B=1024个磁盘块号，二级间接地址块可以记录1024×1024个磁盘块号，而10+1024<1536<10+1024+1024×1024。因此，6MB大小的文件，需要使用一级间接地址项和二级间接地址项（拓展：若文件的总大小超出10+1024+1024×1024块，则还需使用三级间接地址项）。

五、本章疑难点

1. 文件的物理分配方式的比较

	访问第n条记录	优点	缺点
连续分配	需访问磁盘１次	顺序存取时速度快，文件定长时可根据文件起始地址及记录长度进行随机访问	文件存储要求连续的存储空问，会产生碎片，不利于文件的动态扩充
链接分配	需访问磁盘n次	可解决外存的碎片问题，提高外存空问的利用率，动态增长较方便	只能按照文件的指针链顺序访问，查找效率低，指针信息存放消耗外存空间
索引分配	m级需访问磁盘m+1次	可以随机访问，文件易于增删	索引表增加存储空问的开销，索引表的查找策略对文件系统效率影响较大

2. 文件打开的过程描述

① 检索目录，要求打开的文件应该是已经创建的文件，它应登记在文件目录中，否则会出错。在检索到指定文件后，就将其磁盘inode复制到活动inode表中。
② 将参数mode所给出的打开方式与活动inode中在创建文件时所记录的文件访问权限相比较，若合法，则此次打开操作成功。
③ 当打开合法时，为文件分配用户打开文件表表项和系统打开文件表表项，并为后者设置初值，通过指针建立表项与活动inode之间的联系，再将文件描述符fd返回给调用者。

3. 几个专业数据

• 索引块：存放索引信息的磁盘块。例如inode节点的一级间接索引的指针直接指向的是索引块。
• 数据块：存放文件具体数据的磁盘块。例如inode节点的直接索引的指针指向的是数据块，inode节点的一级间接索引的指针的指针指向的也是数据块。
• 文件控制块FCB：保存完整的文件信息。

将索引块或数据块从磁盘读入内存都要进行一次I/O操作。