关于文件分配

文件分配方式与元数据的变化

文件分配方式决定了文件数据块在磁盘上的组织方式。FCB 或 i-node 的一个核心功能就是提供这些数据块的物理地址映射。因此，不同的分配方式会要求 FCB/i-node 采用不同的结构来记录这些地址信息。

让我们逐一分析：

1. 连续分配 (Contiguous Allocation)

• 特点：为文件分配一组连续的磁盘块。

• FCB/i-node 中存储的元数据变化：

  • 只需要记录文件起始块的地址（或块号）。

  • 记录文件的长度（占用的块数）。

• 示例 FCB/i-node 结构片段：

• 优点：

  • 简单高效，顺序访问速度快。

  • 寻道次数少，只需一次寻道即可读取整个文件。

• 缺点：

  • 外部碎片问题：文件删除和创建可能导致大量小的空闲块，难以利用。

  • 文件大小难以动态增长：如果文件需要增长，可能需要移动整个文件到一个更大的连续空间。

2. 链接分配 (Linked Allocation)

• 特点：文件数据块可以分散地存放在磁盘的任何位置，每个数据块包含一个指向下一个数据块的指针。

• FCB/i-node 中存储的元数据变化：

  • 记录文件起始块的地址（或块号）。

  • 记录文件结束块的地址（或块号）（可选，用于优化）。

  • 记录文件的总长度（字节数或块数）。

  • 关键：不记录所有数据块的地址，而是通过第一个块的指针链起来。

• 变种：文件分配表 (FAT - File Allocation Table)：

  • 这是一个专门的磁盘区域，存储着一个链表形式的全局文件分配表。每个数据块在 FAT 中有一个对应的条目，记录了下一个数据块的编号。

  • FCB/i-node (或 FAT 目录项) 中只需存储文件第一个数据块的地址（或簇号）**。后续的链接信息全部在 FAT 表中查找。

• 示例 FCB/i-node 结构片段（通用链接分配）：

• 示例 FCB/i-node 结构片段（FAT 文件系统中的目录项）：

• 优点：

  • 无外部碎片：文件可以动态增长，无需移动。

  • 空间利用率高。

• 缺点：

  • 随机访问效率低：需要遍历链表才能找到某个特定数据块。

  • 可靠性问题：链中某个指针损坏可能导致整个文件无法访问。

  • 额外的空间开销：每个数据块需要存储一个指针。

3. 索引分配 (Indexed Allocation)

• 特点：为每个文件分配一个特殊的索引块（Index Block）。这个索引块集中存储了文件所有数据块的地址（指针）。

• FCB/i-node 中存储的元数据变化：

  • 记录索引块的地址（或块号）。

  • 记录文件的总长度（字节数或块数）。

• i-node 的多级索引：为了支持非常大的文件，i-node 通常采用多级索引结构（直接块、一级间接块、二级间接块、三级间接块）。

  • 直接块指针：i-node 中直接包含少量（如10-12个）指针，指向文件的前几个数据块。

  • 一级间接块指针：i-node 中包含一个指针，指向一个新的索引块，该索引块中存储了更多的文件数据块地址。

  • 二级间接块指针：i-node 中包含一个指针，指向一个二级索引块，该二级索引块又指向多个一级索引块。

  • 三级间接块指针：i-node 中包含一个指针，指向一个三级索引块，该三级索引块又指向多个二级索引块。

• 示例 FCB/i-node 结构片段（Unix/Linux i-node）：

• 优点：

  • 支持随机访问：通过索引块可以直接定位到任意数据块。

  • 无外部碎片：文件数据块可以分散存放。

  • 易于文件增长：只需分配新的数据块和更新索引块（或分配新的间接索引块）。

  • 支持大文件：通过多级索引可以管理非常大的文件。

• 缺点：

  • 空间开销：需要为每个文件分配额外的索引块。

  • 访问开销：访问数据块可能需要多次磁盘I/O（先读索引块，再读数据块；多级索引甚至更多）。

总结：

是的，文件分配方式的变化直接导致了 FCB/i-node 中记录文件物理地址方式的变化。 不同的分配方式有不同的优缺点，这些优缺点也直接反映在其元数据的组织方式上。

• 连续分配：元数据记录起始地址 + 长度。

• 链接分配：元数据记录起始地址（及结束地址），通过链表在数据块中或在 FAT 表中链接。

• 索引分配：元数据记录索引块的地址（可能是多级索引）。

在文件系统中，FCB/i-node 是连接文件的逻辑视图（文件名、属性）和物理视图（数据块地址）的关键桥梁。因此，它们的结构设计必须能够有效地支持所选的文件分配方式。

不同的文件分配方式对应的“分配表”或机制

回顾我们之前讨论的三种基本文件分配方式：

1. 连续分配 (Contiguous Allocation)

2. 链接分配 (Linked Allocation)

3. 索引分配 (Indexed Allocation)

FAT 文件系统是链接分配的一种典型实现，它将链接信息集中存储在一个独立的 FAT 表中。而对于其他分配方式，或者更现代的文件系统，它们有各自不同的“记录文件块位置”的方式：

1. 对于连续分配：

• **没有独立的“分配表”**来存储文件块之间的链接关系。

• 文件的物理地址信息直接存储在文件控制块 (FCB) 或 i-node 中。FCB/i-node 只需要记录：

  • 文件起始块的地址（或块号）

  • 文件占用的块数（长度）

• 如何知道哪些块是空闲的？

  • 通常使用位图 (Bitmap) 或空闲块链表 (Free Block List) 来管理空闲空间。位图中的每一位代表一个磁盘块，0 表示空闲，1 表示已分配。这并非“文件分配表”，而是“空闲空间管理表”。

2. 对于索引分配 (例如：Unix/Linux 的 i-node 文件系统，如 ext2/3/4、XFS、ZFS 等)：

• 没有“文件分配表 (FAT)”。

• 文件的数据块分配信息主要存储在每个文件的i-node (索引节点) 中。

• i-node 中的“分配表”：i-node 内部包含一个或多个数据块指针数组（即索引表）。这些指针直接指向文件的数据块，或者指向包含更多数据块指针的间接索引块。

  • 直接块指针：i-node 中固定数量的指针直接指向文件的前几个数据块。

  • 一级间接块指针：指向一个磁盘块，该块内存储了更多的文件数据块地址。

  • 二级间接块指针：指向一个磁盘块，该块内存储了一级间接块的地址。

  • 三级间接块指针：指向一个磁盘块，该块内存储了二级间接块的地址。

• 如何知道哪些块是空闲的？

  • 同样通常使用位图 (Bitmap) 来管理空闲空间。例如，在 ext2/3/4 文件系统中，每个**块组（Block Group）都有一个独立的块位图（Block Bitmap）**来记录该块组内数据块的分配情况。这也不是“文件分配表”，而是“空闲块管理表”。

3. 其他现代文件系统 (例如：NTFS, APFS, ZFS 等)

这些文件系统通常采用更为复杂和混合的分配策略，结合了连续分配、链接分配、索引分配的优点，并引入了更多高级特性（如日志、快照、数据完整性校验等）。

• NTFS (New Technology File System - Windows)：

  • NTFS 中没有 FAT 表。它将所有文件和目录都视为元文件 (Metafiles)，并将它们的元数据存储在 主文件表 (Master File Table, MFT) 中。

  • MFT 是一个核心数据结构，它包含了一系列可变长度的文件记录 (File Record)，每个文件（包括目录本身）都有一个或多个文件记录。

  • 文件记录中包含了文件的所有元数据（类似 FCB/i-node）以及文件的数据流 (Data Stream) 信息。对于小文件，数据可以直接存储在 MFT 记录中（常驻数据）；对于大文件，MFT 记录会包含一个或多个运行列表 (Run List)，这个列表描述了文件数据在磁盘上的逻辑簇号到物理簇号的映射。这里的“运行列表”可以看作是另一种形式的“分配表”，它能够描述文件数据的连续区域。

• APFS (Apple File System - macOS, iOS)：

  • APFS 采用写时复制 (Copy-on-Write, CoW) 机制，并基于B-树结构来管理文件系统元数据。

  • 文件分配信息存储在 B-树的节点中，可以快速查找。没有传统的 FAT 表。

• ZFS (Zettabyte File System - Solaris, Linux, BSD)：

  • ZFS 也采用 CoW 机制，并使用Merkle Tree (数据完整性校验树) 来管理数据和元数据。

  • ZFS 没有传统的 FAT 表或 i-node 表。所有的文件和目录信息都存储在被称为dnode的结构中，这些dnode组织成树形结构。数据块的物理位置信息分散在这些树结构中。

总结：

“文件分配表 (FAT)”这个名称和具体的表格结构是 FAT 文件系统特有的。

对于其他非 FAT 文件系统，虽然它们没有叫“文件分配表”的结构，但它们必然有：

• 类似的元数据结构（如 i-node、MFT 记录等）来存储文件的属性。

• 在这些元数据结构内部，会有不同的机制来记录文件数据块的物理位置（例如 i-node 的多级索引、NTFS 的运行列表等）。

• 独立的空闲空间管理机制（如位图、空闲块链表）来追踪哪些磁盘块是可用的。

文件系统存储其结构信息（控制信息/元数据）的方式

文件系统通常会将磁盘划分为几个逻辑区域，用于存放不同类型的信息。其中，用于存储控制信息的区域是文件系统的“大脑”。这些控制信息包括：

1. 文件系统引导块 (Boot Block)

2. 文件系统超级块 (Superblock)

3. 空闲空间管理信息 (Free Space Management)

4. 文件控制块 / i-node 区域 (FCB / i-node Area)

5. 目录数据块 (Directory Data Blocks)

6. 文件数据块 (File Data Blocks)

让我们逐一详细说明它们的作用和存储方式。

1. 文件系统引导块 (Boot Block)

• 作用：位于磁盘的第一个扇区（通常是逻辑块 0）。它包含了启动操作系统所需的引导程序。

• 内容：如果磁盘是可引导的，引导块会包含一小段机器代码，这段代码负责加载操作系统内核。如果磁盘不可引导，这个块通常为空或包含一些简单的磁盘识别信息。

• 存储位置：固定在分区的起始位置。

• 是否必须？ 只有可引导分区才需要。

2. 文件系统超级块 (Superblock)

• 作用：是整个文件系统的心脏和灵魂。它包含了文件系统的全局控制信息，用于描述文件系统的整体布局和状态。

• 内容：

  • 文件系统类型 (例如：FAT32, ext4, NTFS)。

  • 文件系统大小 (总的块数、簇数)。

  • 每个块/簇的大小。

  • 空闲块的数量和位置信息（通常是指向空闲块管理数据结构——如位图或空闲链表的指针）。

  • 空闲 i-node 数量和位置信息（指向 i-node 表的起始地址）。

  • 指向根目录 FCB/i-node 的指针。

  • 上次文件系统挂载时间、上次修改时间、文件系统状态（是否干净卸载）。

  • 文件系统的版本信息。

• 存储位置：通常位于文件系统的开头部分（紧随引导块之后），且为了容错，可能会有多个副本分散存储在磁盘的不同位置。

• 是否必须？ 任何文件系统都必须有超级块。如果超级块损坏，整个文件系统将无法识别和访问。

3. 空闲空间管理信息 (Free Space Management)

• 作用：追踪磁盘上哪些数据块是空闲的，可以被分配给新的文件或目录。

• 实现方式：

  • 位图 (Bitmap)：最常用的方式。磁盘上的每个块对应位图中的一位。0 表示空闲，1 表示已分配。位图本身也是存储在磁盘上的一个或多个连续块中。

  • 空闲块链表 (Free Block List)：将所有空闲块组织成一个链表。每个空闲块的第一个字存放指向下一个空闲块的指针。

  • 分组法 (Grouping)：空闲块链表的变种，每个空闲块记录一组空闲块的地址。

• 存储位置：通常紧随超级块之后，或分散在每个块组（Block Group）的头部（如 ext 系列文件系统）。

• 是否必须？ 必须有，否则文件系统无法知道如何分配新空间。

4. 文件控制块 / i-node 区域 (FCB / i-node Area)

• 作用：存储所有文件（包括目录文件自身）的元数据，如文件类型、大小、权限、创建/修改时间、数据块物理地址等。

• 内容：一系列固定大小的 FCB 或 i-node 结构。

• 存储位置：

  • 在 Unix/Linux 文件系统（如 ext4）中，磁盘被划分为多个块组（Block Group）。每个块组都有自己的**i-node 表（i-node Table）**区域，存储该块组内文件的 i-node。

  • 在 FAT 文件系统中，由于目录项直接包含大部分 FCB 信息，所以FAT 表和**目录项（存在于目录数据块中）**共同构成了对文件元数据和分配信息的管理。

  • 在 NTFS 中，所有文件元数据都存储在特殊的 MFT (Master File Table) 文件中，MFT 自身也是一个文件。

• 是否必须？ 必须有，它是文件属性和数据块地址映射的载体。

5. 目录数据块 (Directory Data Blocks)

• 作用：存储目录文件本身的“内容”，即文件名与文件 FCB/i-node 的映射关系。

• 内容：一系列目录项（Directory Entry）。每个目录项通常包含：

  • 文件名

  • 指向对应 FCB/i-node 的指针或 i-node 号

• 存储位置：与其他普通文件数据一样，存储在文件系统的数据区中。只不过，它们的文件类型被标记为“目录”，并且其内容是结构化的目录项。

• 是否必须？ 必须有，否则无法通过文件名查找文件。

6. 文件数据块 (File Data Blocks)

• 作用：实际存储用户文件内容的区域。

• 内容：用户创建的各种文件（文本、图片、程序等）的原始数据。

• 存储位置：文件系统数据区的主体部分，由 FCB/i-node 中记录的物理地址指向。

• 是否必须？ 必须有，这是用户数据存放的地方。

示例：Unix/Linux 文件系统（ext4）的磁盘布局简化示意图

以下是 ext4 文件系统一个分区（或文件系统）的简化逻辑布局：

表格补充说明：

• 块组（Block Group）：ext4 将磁盘划分为多个块组，每个块组都是一个自包含的文件系统小单元，拥有自己的位图、i-node 表和数据块区域。这种设计有以下优点：

  • 减少碎片：相关文件的数据和元数据倾向于存储在同一个块组内，减少寻道时间。

  • 提高可靠性：如果一个块组损坏，不一定会影响整个文件系统。

  • 支持大容量磁盘：易于扩展，每个块组管理相对较小的区域。

• 超级块和块组描述符表的冗余：为了提高文件系统的鲁棒性，超级块和块组描述符表通常会在多个块组的起始位置存有副本。这样即使主副本损坏，系统也能通过副本恢复。

• 根目录 i-node：根目录 / 的 i-node 永远是 i-node 表中的第一个 i-node（通常为 i-node 2，i-node 0和1通常保留），其位置由超级块指向。

• 数据块中的内容：数据块不仅存储用户数据，也存储目录文件的内容（即目录项）。

这个表格清晰地展示了 ext4 文件系统在磁盘上的主要组成部分及其逻辑分布。

总结：

文件系统通过在磁盘上划分出专门的区域来存储其自身的控制信息（元数据），这些元数据包括引导信息、全局配置信息（超级块）、空闲资源追踪信息（位图/链表）、文件和目录的详细属性及物理位置信息（FCB/i-node），以及目录项本身。

这些控制信息相互关联，共同构成了文件系统的骨架，使得操作系统能够在复杂的磁盘结构上高效、可靠地管理和访问文件。