文件分配方式

复习定位

文件在磁盘上的数据块是如何组织起来的——这就是文件分配方式要解决的问题。连续分配(一次占用连续的一组磁盘块)随机访问爽但不够灵活。链接分配(逐块链接)灵活但随机访问慢——索引分配(集中管理块指针)灵活且随机访问快——但需要额外的索引块空间。操作系统权衡后——现代文件系统(ext4, NTFS)都采用索引分配或其变体。

连续分配

文件占用一组连续的磁盘块。文件的目录项只需记录文件起始块号和文件占用总块数。

优点：顺序读(读整个文件)非常高效——磁头一次定位后移动较少——因为连续的块在磁盘上物理相邻，减少了磁臂搜寻的机械耗时。随机访问也非常快——给定块号=起始块+偏移块数——直接计算出磁盘块地址。顺序读和随机读的性能都好。

缺点：外碎片——删除一个文件后留下一段空闲空间——新分配的文件不一定会和旧的碎片大小一致而产生碎片。文件大小必须在创建前确定——无法动态增长——如果要扩大文件继续分配但后续块已经被别的占用——无法扩展。因此不适用于动态增长的文件(日志文件、数据库文件)。

链接分配

将文件的每个块用指针串联起来。目录项记录文件的第一块和最后一块(便于追加)。

隐式链接——每个数据块的末尾(或开头)几字节存放下一个数据块号。读取文件的第n块需要从第一块开始逐块向后访问到第n次。随机访问极慢——若要读第1000块——即使知道起始块号也必须连续读出前999个块来跟踪链接指针。隐式链接目前很少作为主要的分配方式——但FAT文件系统(Windows早期)以单独的文件分配表的方式实现了类似的功能。

显式链接(FAT)——文件分配表(FAT)单独存放在磁盘的一个连续区域中——每个磁盘块在FAT表中对应一个条目——存放该文件的下一个块号。FAT表常驻内存——查找文件第i块时只需在内存中按下标寻找FAT表项——避免了磁盘寻道来跟踪链接——但仍需在内存中"跳动"。FAT表的致命问题——FAT表本身巨大(大容量的磁盘需要庞大的FAT表常驻内存)且不支持权宜的权限控制。

索引分配

为每个文件分配一个专门的索引块——索引块存储该文件的所有数据块地址指针。目录项只需记录该索引块的编号。

优点：不需要连续的磁盘空间——文件可以动态增长——只要在索引块中新增一个指针指向新的空闲块。随机访问——读第i块只需从索引块中找到第i个指针。无外碎片。

缺点：索引块需要占用空间——如果文件小(只有几KB)——索引块本身可能比数据块大。UNIX的inode混合索引方案(直接块+一级间接+二级间接+三级间接)完美解决了这个问题——小文件用直接块(无需索引块I/O消耗)——大文件用间接索引(间接块也可以根据需要动态扩展)。

Unix inode通常有15个指针——前12个是直接数据块指针(覆盖48KB)——第13个是一级间接指针(覆盖4MB)——第14个是二级间接(覆盖4GB)——第15个是三级间接(覆盖4TB)。大多数文件(90%以上)在48KB之内——所以只使用直接块——无需访问间接块——性能极好。

三种分配方式对比

特性	连续	隐式链接	索引
是否需连续空间	是	否	否
顺序读写性能	极好	好	好
随机读写性能	极好	极差	好
文件扩展	困难	简单	简单
外碎片	有	无	无
额外空间开销	无	部分(指针)	索引块

复习检查

1. 连续分配中文件的起始块号和占用块数——假设文件起始块号为100、占用10块——则文件的第2块在磁盘上的实际块号是多少(101)？如果连续分配在此文件增长后要分配第11块且在后续的110号块上有其他文件占据——无法扩展——什么原因导致？

2. 隐式链接——每个块内使用指针指向下一块——读取文件的第500块需要读取前499块吗？FAT表如何解决这个问题(将指针放在一个集中区域FAT表——在内存中快速跳过——不需要读取每个中间数据块本体——但需要读取FAT表的对应项)。

3. 为什么说UNIX的混合inode索引方案既解决了小文件的高效访问又解决可大文件的存储——12个直接块(48KB)覆盖了大多数小文件——不需要额外I/O读取间接块——大文件通过多级间接索引可以存储巨量数据(三级间接映射约4TB)。

4. 删除一个文件时——索引分配和连续分配回收空间的过程有何不同——索引分配只需释放索引块和所有数据块——连续分配释放起始块开始的连续区域。

5. FAT文件系统为什么不能有效支持千兆磁盘——FAT表条目大小和表总大小随磁盘容量同比增大——磁盘大了FAT表更大——耗尽内存占用且大容量访问的管理效率太低。