======第六章文件管理======（1）：https://developer.aliyun.com/article/1415863
6.5.2 直接文件和哈希文件
- 直接文件
采用前述几种文件结构对记录进行存取时，都须利用给定的记录键值，先对线性表或 链表进行检索，以找到指定记录的物理地址。然而对于直接文件，则可根据给定的记录键 值，直接获得指定记录的物理地址。换言之，记录键值本身就决定了记录的物理地址。这 种由记录键值到记录物理地址的转换被称为键值转换(Key to address transformation)。组织直 接文件的关键，在于用什么方法进行从记录值到物理地址的转换。
哈希文件
这是目前应用最为广泛的一种直接文件。它利用 Hash 函数(或称散列函数)，可将记录 键值转换为相应记录的地址。但为了能实现文件存储空间的动态分配，通常由 Hash 函数所 求得的并非是相应记录的地址，而是指向一目录表相应表目的指针，该表目的内容指向相 应记录所在的物理块，如图 6-6 所示。例如，若令 K 为记录键值，用 A 作为通过 Hash 函数 H 的转换所形成的该记录在目录表中对应表目的位置，则有关系 A=H(K)。通常，把 Hash 函数作为标准函数存于系统中，供存取文件时调用。
6.3 外存分配方式
6.3.1 连续分配
- 连续分配方式
连续分配要求为每一个文件分配一组相邻接的盘块。一组盘块的 地址定义了磁盘上的一段线性地址。例如，第一个盘块的地址为 b，则第二个盘块的地址为 b+1，第三个盘块的地址为 b+2……。通常，它们都位于一条磁道上，在进行读/写时，不必 移动磁头，仅当访问到一条磁道的最后一个盘块后，才需要移到下一条磁道，于是又去连 续地读/写多个盘块。在采用连续分配方式时，可把逻辑文件中的记录顺序地存储到邻接的 各物理盘块中，这样所形成的文件结构称为顺序文件结构，此时的物理文件称为顺序文件。 这种分配方式保证了逻辑文件中的记录顺序与存储器中文件占用盘块的顺序的一致性。为 使系统能找到文件存放的地址，应在目录项的“文件物理地址”字段中，记录该文件第一 个记录所在的盘块号和文件长度(以盘块数进行计量)。图 6-7 示出了连续分配的情况。图中 假定了记录与盘块的大小相同。Count 文件的第一个盘块号是 0，文件长度为 2，因此是在 盘块号为 0 和 1 的两盘块中存放文件 1 的数据。
如同内存的动态分区分配一样，随着文件建立时空间的分配和文件删除时空间的回收， 将使磁盘空间被分割成许多小块，这些较小的连续区已难于用来存储文件，此即外存的碎 片。同样，我们也可以利用紧凑的方法，将盘上所有的文件紧靠在一起，把所有的碎片拼 接成一大片连续的存储空间。例如，可以运行一个再装配例程(repack routine)，由它将磁盘 A 上的大量文件拷贝到一张软盘 B 或几张软盘(C，D，…)上，并释放原来的 A 盘，使之成 为一个空闲盘。然后再将软盘 B(C，D，…)上的文件拷回 A 盘上。这种方法能将含有多个 文件的盘上的所有空闲盘块都集中在一起，从而消除了外部碎片。但为了将外存上的空闲 空间进行一次紧凑，所花费的时间远比将内存紧凑一次所花费的时间多得多。
连续分配的主要优缺点
连续分配的主要优点如下：
(1) 顺序访问容易。访问一个占有连续空间的文件非常容易。系统可从目录中找到该顺 序文件所在的第一个盘块号，从此开始顺序地、逐个盘块地往下读/写。连续分配也支持直 接存取。例如，要访问一个从 b 块开始存放的文件中的第 i 个盘块的内容，就可直接访问 b+i 号盘块。
(2) 顺序访问速度快。因为由连续分配所装入的文件，其所占用的盘块可能是位于一条 或几条相邻的磁道上，这时，磁头的移动距离最少，因此，这种对文件访问的速度是几种 存储空间分配方式中最高的一种。
连续分配的主要缺点如下：
(1) 要求有连续的存储空间。要为每一个文件分配一段连续的存储空间，这样，便会产 生出许多外部碎片，严重地降低了外存空间的利用率。如果是定期地利用紧凑方法来消除 碎片，则又需花费大量的机器时间。
(2) 必须事先知道文件的长度。要将一个文件装入一个连续的存储区中，必须事先知道 文件的大小，然后根据其大小，在存储空间中找出一块其大小足够的存储区，将文件装入。 在有些情况下，知道文件的大小是件非常容易的事，如可拷贝一个已存文件。但有时却很 难，在此情况下，只能靠估算。如果估计的文件大小比实际文件小，就可能因存储空间不足而中止文件的拷贝，须再要求用户重新估算，然后再次执行。这样，显然既费时又麻烦。 这就促使用户往往将文件长度估得比实际的大，甚至使所计算的文件长度比实际长度大得 多，显然，这会严重地浪费外存空间。对于那些动态增长的文件，由于开始时文件很小， 在运行中逐渐增大，比如，这种增长要经历几天、几个月。在此情况下，即使事先知道文 件的最终大小，在采用预分配存储空间的方法时，显然也将是很低效的，即它使大量的存 储空间长期地空闲着。
6.3.2 链接分配
- 隐式链接
在采用隐式链接分配方式时，在文件目录的每个目录项中，都须含有指向链接文件第 一个盘块和最后一个盘块的指针。图 6-8 中示出了一个占用 5 个盘块的链接式文件。在相 应的目录项中，指示了其第一个盘块号是 9，最后一个盘块号是 25。而在每个盘块中都含 有一个指向下一个盘块的指针，如在第一个盘块 9 中设置了第二个盘块的盘块号是 16；在 16 号盘块中又设置了第三个盘块的盘块号 1。如果指针占用 4 个字节，对于盘块大小为 512 字节的磁盘，则每个盘块中只有 508 个字节可供用户使用。
隐式链接分配方式的主要问题在于：它只适合于顺序访问，它对随机访问是极其低效 的。如果要访问文件所在的第 i 个盘块，则必须先读出文件的第一个盘块……，就这样顺序 地查找直至第 i 块。当 i=100 时，须启动 100 次磁盘去实现读盘块的操作，平均每次都要花 费几十毫秒。可见，随机访问的速度相当低。此外，只通过链接指针来将一大批离散的盘 块链接起来，其可靠性较差，因为只要其中的任何一个指针出现问题，都会导致整个链的 断开。
为了提高检索速度和减小指针所占用的存储空间，可以将几个盘块组成一个簇(cluster)。 比如，一个簇可包含 4 个盘块，在进行盘块分配时，是以簇为单位进行的。在链接文件中 的每个元素也是以簇为单位的。这样将会成倍地减小查找指定块的时间，而且也可减小指 针所占用的存储空间，但却增大了内部碎片，而且这种改进也是非常有限的。
显示链接
这是指把用于链接文件各物理块的指针，显式地存放在内存的一张链接表中。该表在 整个磁盘仅设置一张，如图 6-9 所示。表的序号是物理盘块号，从 0 开始，直至 N-1；N 为 盘块总数。在每个表项中存放链接指针，即下一个盘块号。在该表中，凡是属于某一文件 的第一个盘块号，或者说是每一条链的链首指针所对应的盘块号，均作为文件地址被填入 相应文件的 FCB 的“物理地址”字段中。由于查找记录的过程是在内存中进行的，因而不 仅显著地提高了检索速度，而且大大减少了访问磁盘的次数。由于分配给文件的所有盘块 号都放在该表中，故把该表称为文件分配表 FAT(File Allocation Table)。
6.3.3 FAT 和 NTFS 技术
1．FAT12
1) 以盘块为基本分配单位
早期 MS-DOS 操作系统所使用的是 FAT12 文件系统，在每个分区中都配有两张文件分 配表 FAT1 和 FAT2，在 FAT 的每个表项中存放下一个盘块号，它实际上是用于盘块之间的 链接的指针，通过它可以将一个文件的所有的盘块链接起来，而将文件的第一个盘块号放 在自己的 FCB 中。图 6-10 示出了 MS-DOS 的文件物理结构，这里示出了两个文件，文件 A 占用三个盘块，其盘块号依次为 4、6、11；文件 B 则依次占用 9、10 及 5 号三个盘块。 每个文件的第一个盘块号放在自己的 FCB 中。整个系统有一张文件分配表 FAT。在 FAT 的 每个表项中存放下一个盘块号。对于 1.2 MB 的软盘，每个盘块的大小为 512 B，在每个 FAT 中共含有 2.4 K 个表项，由于每个 FAT 表项占 12 位，故 FAT 表占用 3.6 KB 的存储空间。
现在我们来计算以盘块为分配单位时，所允许的最大磁盘容量。由于每个 FAT 表项为 12 位，因此，在 FAT 表中最多允许有 4096 个表项，如果采用以盘块作为基本分配单位， 每个盘块(也称扇区)的大小一般是 512 字节， 那么， 每个磁盘分区的容量为 2 MB (4096×512 B)。同时，一个物理磁盘支持 4 个逻辑磁盘分区，所以相应的磁盘最大容量仅 为 8 MB。这对最早时期的硬盘还可应付，但很快磁盘的容量就超过了 8 MB，FAT12 是否 还可继续用呢，回答虽是肯定的，但需要引入一个新的分配单位——簇。
2) 簇的基本概念
为了适应磁盘容量不断增大的需要，在进行盘块分配时，不再以盘块而是以簇(cluster) 为基本单位。簇是一组连续的扇区，在 FAT 中它是作为一个虚拟扇区，簇的大小一般是 2n (n 为整数)个盘块，在 MS-DOS 的实际运用中，簇的容量可以仅有一个扇区(512 B)、两个 扇区(1 KB)、四个扇区(2 KB)、八个扇区(4 KB)等。一个簇应包含扇区的数量与磁盘容量的 大小直接有关。例如，当一个簇仅有一个扇区时，磁盘的最大容量为 8 MB；当一个簇包含 两个扇区时，磁盘的最大容量可以达到 16 MB；当一个簇包含了八个扇区时，磁盘的最大容量便可达到 64 MB。 由上所述可以看出，以簇作为基本的分配单位所带来的最主要的好处是，能适应磁盘 容量不断增大的情况。值得注意的是，使用簇作为基本的分配单位虽可减少 FAT 表中的项 数(在相同的磁盘容量下，FAT 表的项数是与簇的大小成反比的)。这一方面会使 FAT 表占用 更少的存储空间，并减少访问 FAT 表的存取开销，提高文件系统的效率；但这也会造成更 大的簇内零头(它与存储器管理中的页内零头相似)。
3) FAT12 存在的问题
尽管 FAT12 曾是一个不错的文件系统，但毕竟已老化，已不能满足操作系统发展的需 要，其表现出来的主要问题是，对所允许的磁盘容量存在着严重的限制，通常只能是数十 兆字节，虽然可以用继续增加簇的大小来提高所允许的最大磁盘容量，但随着支持的硬盘 容量的增加，相应的簇内碎片也将随之成倍地增加。此外，它只能支持 8+3 格式的文件名。
FAT16
对 FAT12 所存在的问题进行简单的分析即可看出，其根本原因在于，FAT12 表最多只 允许 4096 个表项，亦即最多只能将一个磁盘分区分为 4096 个簇。这样，随着磁盘容量的 增加，必定会引起簇的大小和簇内碎片也随之增加。由此可以得出解决方法，那就是增加 FAT 表的表项数，亦即应增加 FAT 表的宽度，如果我们将 FAT 表的宽度增至 16 位，最大表 项数将增至 65536 个，此时便能将一个磁盘分区分为 65 536(216 )个簇。我们把具有 16 位表 宽的 FAT 表称为 FAT16。在 FAT16 的每个簇中可以有的盘块数为 4、8、16、32 直到 64， 由此得出 FAT16 可以管理的最大分区空间为 2 16 × 64 × 512 = 2048 MB。
由上述分析不难看出，FAT16 对 FAT12 的局限性有所改善，但改善很有限。当磁盘容 量迅速增加时，如果再继续使用 FAT16，由此所形成的簇内碎片所造成的浪费也越大。例 如，当要求磁盘分区的大小为 8 GB 时，则每个簇的大小达到 128 KB，这意味着内部零头 最大可达到 128 KB。一般而言，对于 1～4 GB 的硬盘来说，大约会浪费 10％～20％的空间。 为了解决这一问题，微软推出了 FAT32。
另外，由于 FAT12 和 FAT16 都不支持长文件名，文件名受到了 8 个字符文件名和 3 个 字符文件扩展名的长度限制，为了满足用户通过文件名更好地描述文件内容的需求， 在 Windows 95 以后的系统中，对 FAT16 进行了扩展，通过一个长文件名占用多个目录项的方 法，使得文件名的长度可以长达 255 个字符，这种扩展的 FAT16 也称为 VFAT。
FAT32
如同存储器管理中的分页管理，所选择的页面越大，可能造成的页内零头也会越大。 为减少页内零头就应该选择适当大小的页面。在这里，为了减小磁盘的簇内零头，也就应 当选择适当大小的簇。问题是 FAT16 表的长度只有 65 535 项，随着磁盘容量的增加，簇的 大小也必然会随之增加，为了减少簇内零头，也就应当增加 FAT 表的长度。为此，需要再 增加 FAT 表的宽度，这样也就由 FAT16 演变为 FAT32。
FAT32 是 FAT系列文件系统的最后一个产品。每一簇在 FAT表中的表项占据4 字节(232 )， FAT 表可以表示 4 294 967 296 项，即 FAT32 允许管理比 FAT16 更多的簇。这样就允许在 FAT32 中采用较小的簇，FAT32 的每个簇都固定为 4 KB，即每簇用 8 个盘块代替 FAT16 的 64 个盘块，每个盘块仍为 512 字节，FAT32 分区格式可以管理的单个最大磁盘空间大到4 KB×2 32 = 2 TB。三种 FAT 类型的最大分区以及所对应的块的大小如图 6-11 所示。
FAT32 比 FAT16 支持更小的簇和更大的磁盘容量，这就大大减少了磁盘空间的浪费， 使得 FAT32 分区的空间分配更有效率，例如，两个磁盘容量都为 2 GB，一个磁盘采用了 FAT16 文件系统，另一个磁盘采用了 FAT32 文件系统，采用 FAT16 磁盘的簇大小为 32 KB， 而 FAT32 磁盘簇只有 4 KB 的大小，这样，FAT32 磁盘碎片减少，比 FAT16 的存储器利用 率要高很多，通常情况下可以提高 15%。FAT32 主要应用于 Windows 98 及后续 Windows 系统，它可以增强磁盘性能，并增加可用磁盘空间，同时也支持长文件名；它不存在最小 存储空间问题，能够有效地节省硬盘空间。
FAT32 仍然有着明显的不足之处：首先，由于文件分配表的扩大，运行速度比 FAT16 格式要慢；其次，FAT32 有最小管理空间的限制，FAT32 卷必须至少有 65 537 个簇，所以 FAT32 不支持容量小于 512 MB 的分区，因此对于小分区，则仍然需要使用 FAT16 或 FAT12； 再之，FAT32 的单个文件的长度也不能大于 4 GB；最后，FAT32 最大的限制在于兼容性方 面，FAT32 不能保持向下兼容。
NTFS
1) NTFS 新特征
NTFS(New Technology File System)是一个专门为 Windows NT 开发的、全新的文件系 统，并适用于 Windows 2000/XP/2003。NTFS 具有许多新的特征：首先，它使用了 64 位磁 盘地址，理论上可以支持 2 的 64 次方字节的磁盘分区；其次，在 NTFS 中可以很好地支持 长文件名，单个文件名限制在 255 个字符以内，全路径名为 32 767 个字符；第三，具有系 统容错功能，即在系统出现故障或差错时，仍能保证系统正常运行，这一点我们将在 6.6 节 中介绍；第四，提供了数据的一致性，这是一个非常有用的功能，我们将在本章的最后一 节介绍；此外，NTFS 还提供了文件加密、文件压缩等功能。
2) 磁盘组织
同 FAT 文件系统一样，NTFS 也是以簇作为磁盘空间分配和回收的基本单位。一个文件 占用若干个簇，一个簇只属于一个文件。通过簇来间接管理磁盘，可以不需要知道盘块(扇 区)的大小，使 NTFS 具有了与磁盘物理扇区大小无关的独立性，很容易支持扇区大小不是 512 字节的非标准磁盘，从而可以根据不同的磁盘选择匹配的簇大小。
在 NTFS 文件系统中，把卷上簇的大小称为“卷因子”，卷因子是在磁盘格式化时确定 的，其大小同 FAT 一样，也是物理磁盘扇区的整数倍，即一个簇包含 2n(n 为整数)个盘块， 簇的大小可由格式化命令或格式化程序按磁盘容量和应用需求来确定，可以为 512 B、1 KB、 2 KB……，最大可达 64 KB。对于小磁盘(≤512 MB)，默认簇大小为 512 字节；对于 1 GB 磁盘，默认簇大小为 1 KB；对于 2 GB 磁盘，则默认簇大小为 4 KB。事实上，为了在传输 效率和簇内碎片之间进行折中，NTFS 在大多数情况下都是使用 4 KB。
对于簇的定位， NTFS 是采用逻辑簇号 LCN(Logical Cluster Number)和虚拟簇号 VCN(Virtual Cluster Number)进行的。LCN 是以卷为单位，将整个卷中所有的簇按顺序进行 简单的编号，NTFS 在进行地址映射时，可以通过卷因子与 LCN 的乘积，便可算出卷上的 物理字节偏移量，从而得到文件数据所在的物理磁盘地址。为了方便文件中数据的引用， NTFS 还可以使用 VCN，以文件为单位，将属于某个文件的簇按顺序进行编号。只要知道 了文件开始的簇地址，便可将 VCN 映射到 LCN。
3) 文件的组织
在 NTFS 中，以卷为单位，将一个卷中的所有文件信息、目录信息以及可用的未分配 空间信息，都以文件记录的方式记录在一张主控文件表 MFT(Master File Table)中。该表是 NTFS 卷结构的中心，从逻辑上讲，卷中的每个文件作为一条记录，在 MFT 表中占有一行， 其中还包括 MFT 自己的这一行。每行大小固定为 1 KB，每行称为该行所对应文件的元数 据(metadata)，也称为文件控制字。
在 MFT 表中，每个元数据将其所对应文件的所有信息，包括文件的内容等，都被组织 在所对应文件的一组属性中。由于文件大小相差悬殊，其属性所需空间大小也相差很大， 因此，在 MFT 表中，对于元数据的 1 KB 空间，可能记录不下文件的全部信息。所以当文 件较小时，其属性值所占空间也较小，可以将文件的所有属性直接记录在元数据中。而当 文件较大时，元数据仅记录该文件的一部分属性，其余属性，如文件的内容等，可以记录 到卷中的其它可用簇中，并将这些簇按其所记录文件的属性进行分类，分别链接成多个队 列，将指向这些队列的指针保存在元数据中。
例如对于一个文件的真正数据，即文件 DATA 属性，如果很小，就直接存储在 MFT 表 中对应的元数据中，这样对文件数据的访问，仅需要对 MFT 表进行即可，减少了磁盘访问 次数，较大地提高了对小文件存取的效率。如果文件较大，则文件的真正数据往往保存在 其它簇中。此时通过元数据中指向文件 DATA 属性的队列指针，可以方便地查找到这些簇， 完成对文件数据的访问。
实际上，文件在存储过程中，数据往往连续存放在若干个相邻的簇中，仅用一个指针 记录这几个相邻的簇即可，而不是每个簇需要一个指针，从而可以节省指针所耗费的空间。 一般地，采用上述的方式，只需十几个字节就可以含有 FAT32 所需几百个 KB 才拥有的信 息量。
NTFS 的不足之处在于，它只能被 Windows NT 所识别。NTFS 文件系统可以存取 FAT 等文件系统的文件，但 NTFS 文件却不能被 FAT 等文件系统所存取，缺乏兼容性。Windows 的 95/98/98SE 和 Me 版本都不能识别 NTFS 文件系统。
======第六章文件管理======（3）：https://developer.aliyun.com/article/1415866?spm=a2c6h.13148508.setting.23.16254f0exsfwiz
