4.2 文件的物理结构（文件分配方式）

连续分配、隐式链接与显式链接（FAT）分配、索引分配（链接方案、多层索引、混合索引）的原理与比较；访问第 i 块需要读盘的次数；混合索引下最大文件长度的计算。

文件的物理结构（文件分配方式）研究的是：文件的数据在磁盘上如何存放，即逻辑块号如何映射到物理块号。磁盘空间以盘块（或由若干盘块组成的簇）为单位分配。

连续分配

连续分配要求每个文件在磁盘上占有一组连续的盘块，目录项中记录文件的起始块号和长度（块数）。逻辑块号 i 对应的物理块号 = 起始块号 + i。

• 优点：实现简单；既支持顺序访问，又支持随机访问；顺序访问时磁头移动距离最小，存取速度快。
• 缺点：要求有连续的存储空间，反复分配和回收会产生外部碎片（可以用紧凑消除，但很耗时）；文件长度不宜动态增加，因为相邻的盘块可能已被占用；创建文件时很难确定它需要多大的空间。

链接分配

链接分配采取离散分配的方式，文件的各个盘块可以分散在磁盘的任何位置，通过指针链接起来。它消除了外部碎片，文件长度也可以动态增长。

隐式链接

目录项中记录文件第一块和最后一块的块号，每个盘块的末尾存放指向下一个盘块的指针（对用户透明）。

• 只适合顺序访问，随机访问效率极低：要访问第 i 块，必须从第一块开始依次读出前面的 i 块，共读盘 i + 1 次；
• 每个盘块都要拿出一部分空间存放指针；
• 可靠性差，任何一个指针出问题都会导致整个链断开。可以把几个盘块组成一个簇来分配，以减少指针开销和读盘次数。

显式链接（FAT）

把链接各物理块的指针显式地集中存放在一张文件分配表（FAT，File Allocation Table）中。整个磁盘只设一张 FAT，每个盘块对应一个表项，表项中存放文件下一块的块号（−1 表示文件结束，−2 表示该块空闲）。目录项中只需记录文件的起始块号。

• FAT 在系统启动时读入内存，查找下一块号是在内存中进行的，因此可以随机访问：先在内存的 FAT 中顺着链找到第 i 块的块号，再读盘 1 次；
• FAT 同时也记录了哪些块空闲，可以用于空闲空间管理；
• 缺点是 FAT 要常驻内存，磁盘越大、FAT 越大。

FAT 表项的位数限制了能管理的盘块（簇）数：FAT12 最多 2¹² = 4096 个表项，FAT16 最多 2¹⁶ = 65 536 个，FAT32 实际使用 28 位。例如 1.2 MB 的软盘、1 KB 的盘块，共 1.2 K 个表项，每项 12 位（1.5 B），FAT 共占 1.8 KB。为了支持更大的磁盘，可以把若干相邻盘块组成一个簇作为分配单位（如 FAT16 每簇 32 KB 时最多管理 65 536 × 32 KB = 2 GB），但簇越大，簇内的碎片越多。为了安全，每个分区通常配有两张相同的 FAT（FAT1、FAT2）。

索引分配

链接分配不能有效支持随机访问（FAT 又要占用大量内存）。索引分配为每个文件分配一个索引块，按逻辑顺序存放该文件所有盘块的块号——第 i 个表项就是第 i 个逻辑块的物理块号。目录项中记录该文件索引块的块号。

• 优点：支持随机访问，没有外部碎片，文件可以动态增长；
• 缺点：索引块要占用额外的空间。对于只有一两个盘块的小文件，也要分配一整个索引块，利用率低。

在下面的演示中切换四种方式，比较读取同一个逻辑块所需的读盘次数：

索引块的组织

一个索引块能存放的块号有限（如 4 KB 的块、每项 4 B，只能存 1024 个块号），大文件需要更多的索引块，有以下三种组织方式：

1. 链接方案：一个索引块通常是一个盘块，大文件可以把多个索引块链接起来；
2. 多层索引：第一层索引块指向第二层索引块，第二层索引块再指向文件的盘块。例如 4 KB 的块、4 B 的表项，两层索引可支持 1024 × 1024 个块，即 4 GB 的文件；访问一个数据块需要依次读两个索引块；
3. 混合索引：把多种索引方式结合起来。UNIX 的索引结点中有 13 个地址项：前 10 个是直接地址（直接给出数据块号），第 11 个是一次间接地址（指向一个索引块），第 12 个是二次间接地址，第 13 个是三次间接地址。小文件只用直接地址，访问快；大文件才用到间接地址。

设盘块大小为 B、地址项占 a 字节，则每个索引块可存放 n = B / a 个地址项，混合索引下单个文件的最大长度为

三种分配方式的比较

即时练习