文件系统基础 (二)——文件的物理结构

一. 前言

文件的物理结构就是研究文件的实现，即文件数据在物理存储设备上是如何分布和组织的。

• 文件的分配方式：对磁盘非空闲块的管理。
• 文件存储空间管理：对磁盘空闲块的管理。

类似于内存分页，磁盘中内存单元也被分为一个个的块，称为磁盘块，大小通常与内存页面大小相同。内存与磁盘之间的数据交换（磁盘 I/O）单位是块。

二. 连续(顺序)分配

• 要求每个文件在磁盘上占有一组连续的块，如下图所示。（磁盘地址定义了磁盘上的一个线性排序，使得进程访问磁盘需要的寻道数和寻道时间最小）

• 优点

• 支持顺序访问和直接访问。
• 顺序访问容易，并且速度快，文件占用的块可能位于一条或几条相邻的磁道，磁头移动距离最小。

• 缺点

• 为一个文件分配连续的存储空间，会产生许多外部碎片。【与内存分配类似】
• 必须事先知道文件长度，无法满足文件动态增长的要求，否则会覆盖物理上相邻的后续文件。
• 为保持文件的有序性，删除和插入记录时，需要对相邻的记录做物理上的移动。

三. 链接分配

链接分配是一种采用离散分配的方式。

• 优点

• 消除了磁盘外部碎片，提高磁盘利用率
• 便于动态为文件分配盘块，因此无需动态知道文件的大小
• 文件的插入，删除和修改很方便。

• 链接分配分为：隐式链接，显式链接。

隐式链接

• 目录项仅含有文件第一块和最后一块的指针（盘块号）。
• 每个文件对应一个磁盘块的链表，磁盘块分布在磁盘任何地方。
• 文件除最后一个盘块外，每个盘块都有一个指向文件下一个盘块的指针，指针对用户透明。

• 优点

• 方便拓展文件，不会有碎片问题，外存利用率高。

• 缺点

• 只支持顺序访问。访问文件的第 i 块，只能从第一块开始，通过盘块指针顺序查找到第 i 块，随机访问效率很低。
• 稳定性问题，文件盘块中任何一个指针出问题，都会导致文件数据丢失。
• 指向下一个盘块的指针也会耗费一定的存储空间。

• 文件空间分配与簇的关系

• 为了提高查找速度和减小指针所占用的存储空间，可以将几个盘块组成一个簇，按簇而不按块来分配
• 可以大幅地减少查找时间，也可以改善许多算法的磁盘访问时间。

比如一簇为4块， 这样，指针所占的磁盘空间比例也要小得多。这种方法的代价是增加了内部碎片。

显式链接

• 将用于链接文件的各物理块指针，显式地存放在内存的一张链接表中，整个磁盘仅设置一张，称为文件分配表（File Allocation Table，FAT）。
• 文件目录只需要记录文件起始块号，后续块号通过 FAT 查得。
• FAT 的作用

• 不难看出,FAT的表项与全部磁盘块一一对应
• 并且可以用一个特殊的数字-1表示文件的最后一块,可以用-2表示这个磁盘块是空闲的(当然也可指定为-3,-4)。

因此,FAT还标记了空闲的磁盘块,操作系统可以通过FAT对磁盘空闲空间进行管理。当某进程请求系统分配一个磁盘块时,系统只需从FAT中找到-2的表项,并将对应的磁盘块分配给该进程即可。

• 优点

• 支持顺序访问和直接访问。
• FAT 启动时就被读入内存，检索记录在内存中进行，显著提高了检索速度

由于不需要查找磁盘，故 显式链接查找速度比隐式链接快得多。

• 方便对文件实现扩展
• 缺点

• FAT 需要占用一定的内存空间。

三. 索引分配

单级索引分配

事实上,在打开某个文件时,只需将该文件对应的盘块的编号调入内存即可,完全没有必要将整个FAT调入内存。

• 索引分配的思想：应该将每个文件所有的盘块号集中地放在一起,当访问到某个文件时,将该文件对应的盘块号一起调入内存即可。

它为每个文件分配一个索引块(表),将分配给该文件的所有盘块号都记录在该索引块中

• 优点

• 支持直接访问,当要访问第 i 块时,索引块的第i个条目指向的便是文件的第i个块。
• 索引分配也不会产生外部碎片。缺点是索引块增加了额外的存储空间开销

• 缺点：每个文件必须有一个索引块

• 当文件很小时,比如只有数个盘块,该方式仍为之分配一个索引块,此时索引块的利用率很低;
• 当文件很大时,若其盘块号需要占用若干索引块,此时可通过链指针将各索引块按序链接起来,但这种方法是低效的。

多级索引分配

显然,当文件太大而索引块太多时,应该为这些索引块再建立一级索引,称为主索引,将第一个索引块的盘块号、第二个索引块的盘块号……填入该主索引表,这样,便形成了二级索引分配方式。

其原理类似于内存管理中的多级页表,如图4.10所示。查找时,通过主索引查找第二级索引,再通过第二级索引查找所需数据块。如果文件非常大,那么还可使用三级、四级索引分配方式。

例如,假设盘块大小为4KB,每个盘块号占4B,一个索引块中可存放1024个盘块号,若采用两级索引,则支持的最大文件为1024×1024×4KB=4GB。

• 优点

• 极大加快了对大型文件的查找速度。

• 缺点

• 当访问一个盘块时,其所要启动磁盘的次数随着索引级数的增加而增多,即使是对数量众多的小文件也是如此。

由此可见,如果在文件系统中仅采用了多级索引组织方式,那么并不能获得理想的效果。

混合索引分配

为了能够较全面地照顾到小型、中型、大型和特大型文件,可采用混合索引分配方式。

• 对于小文件,为了提高对众多小文件的访问速度,最好能将它们的每个盘块地址直接放入FCB,这样就可以直接从FCB中获得该文件的盘块地址,即为直接寻址。
• 对于中型文件,可以采用单级索引分配,需要先从FCB中找到该文件的索引表,从中获得该文件的盘块地址,即为一次间址。
• 对于大型或特大型文件,可以采用两级和三级索引分配。UNIX 系统采用的就是这种分配方式,在其索引节点中,共设有13个地址项,即i.addr(0)～i.addr(12),如图4.11所示。

混合索引分配相关计算

• 直接地址。为了提高对小文件的检索速度,在索引节点中可设置10个直接地址项,即用i.addr(0)～i.addr(9)来存放直接地址,即文件数据块的盘块号。假如每个盘块的大小为4KB,当文件不大于40KB时,便可直接从索引节点中读出该文件的全部盘块号。
• 一次间接地址。对于中、大型文件,只采用直接地址并不现实的。为此,可再利用索引节点中的地址项i.addr(10)来提供一次间接地址,即采用一级索引分配。一次间接地址中记录了文件的一次间址块号,一次间址块就是索引块,其中记录了文件数据块的盘块号。一次间址块中可以存放1024个盘块号,可以表示1K×4KB=4MB大小的文件。因此,同时采用直接地址和一次间址,允许的文件最大长度为4MB+40KB。
• 多次间接地址。当文件长度大于4MB+40KB时,还需利用地址项i.addr(11)来提供二次间接地址,即采用两级索引分配。二次间接地址中记录了文件的主索引块号,主索引块中记录了文件的一次间址块号。当地址项 i.addr(11)作为二次间址块时,可以表示1K×1K×4KB=4GB大小的文件。因此,同时采用直接地址、一次间址和二次间址时,允许的文件最大长度为4GB+4MB+40KB。同理,同时采用直接地址、一次间址、二次间址和三次间址时,允许的文件最大长度为4TB+4GB+4MB+40KB。

五. 总结