和内存的分配方式一样,磁盘也有连续分配和离散分配两种方式。

连续分配的缺点第一是容易产生碎片,第二是没有办法动态增长,想象下面一种情景:我打开一个 word(或者 vim),敲进去一段文字,这个时候我想要先保存一下,于是点了保存(或输入 :w),这个时候操作系统会根据这个文档的大小去磁盘上找一段连续的盘块,然后进行写操作。我每隔一段时间都保存一下,操作系统每次都只要把我新输入的内容追加地写到磁盘里,直到文件已经触碰到空闲盘块的底部,再增长就要破坏其他文件的盘块,这时系统就要重新去找一段更大的连续空间,把原来的文件搬过去,以保证文件的连续。这样最后一次保存需要花很长的时间,而且从提倡节能减排的角度看也是不合理的,这意味着前面几次保存白忙了,我们完全可以把同一个文件放在不相邻的盘块中,即链接分配的形式。但是链表的指针不能放在盘块节点里,否则如果要访问链表中第 n 个节点时,需要历经 n 次的磁盘 IO,而是将指向下一个节点的指针单独提取出来,放在内存中以便于快速查找出与一个文件关联的所有盘块号,这就是 FAT(File Allocation Table)的思想。

UNIX 为什么没有用 FAT 呢?我们算一笔账,根据当年 Ritchie 和 Thompson 在 acm 上发表的那篇 paper,它们的 pdp-11 有 400Mb 的磁盘(Our own PDP-11 has two 200-Mb moving-head disks for file system storage and swapping),因为一个盘块是 0.5Kb,400Mb 相当于 800K 个盘块,FAT 表就应该有 800K 个表项,以 FAT16 计算(每个表项用 16 位二进制表示),FAT 表的大小为 2b * 800K = 1600Kb!而当时的 UNIX 不过占了 768K 的内存(其中系统内核才 70K),因此 FAT 表对于 UNIX 的设计者来说是不屑于的,否则他们拿什么吹嘘 UNIX 的内存占多小呢?

UNIX 的设计者于是采用了一种折中的方法。我们可以回想一下单纯的链接分配遇到的瓶颈是什么?是过于频繁的 IO,因为我们把一部分信息(指针)留在了磁盘上,取出时需要很长时间,而 FAT 的解决方案又太过偏激,它把所有可能需要的信息全放在了内存中,但并不是所有信息对我们来说都是有用的,比如我们在读一个文件的时候,只有这个文件所对应的那一部分 FAT 表对我们来说有用的,而其余的都可以暂时放在磁盘上。

UNIX 的索引分配就是指把一个文件的所有信息以文件控制块 FCB(File Control Block)的形式保存在磁盘的某个块中,等到要用的时候再一次性地读到内存中,它在 UNIX 中是一个名字叫 inode 的结构体,其中用一个数组保存盘块的索引,对于小文件来说就是物理盘块号,对于大文件来说需要二级索引,数组中保存的索引先指向一个盘块,这个盘块中存的还是盘块号。

就像我们打牌的时候,如果一张张地摸牌会很慢,如果把所有的牌都拿在手上,又嫌手不够大。怎么办?看一个小孩是怎么打牌就知道了,他会在理牌的时候顺便就把“炸弹”、“顺子”之类的牌找出来,扣在地上(可以看作初始化的过程),用到的时候再把它们取到手中。