文件系统的布局

文件系统存放在磁盘上，多数磁盘可以划分为一个或多个分区，每个分区中有一个独立的文件系统，磁盘的0号扇区称为主引导记录（MBR），用来引导计算机。在MBR的结尾是分区表。该表给出了每个分区的起始和结束地址。表中的一个分区被标记为活动分区。在计算机被引导时，BIOS读入并执行MBR，MBR做的第一件事情就是确定活动分区，读入它的第一个块，即引导块，并执行之。引导块中的程序将装载该分区的操作系统。

文件的实现

文件的存储实现的关键问题是记录各个文件分别用到哪些磁盘块。不同的操作系统采用不同方法，本文主要介绍三种方法。

连续分配

最简单的分配方案是把每个文件作为一连串连续数据存储到连续的磁盘块上，也就是说，块大小为1KB的磁盘，存储50KB的文件需要50个连续的磁盘块，若磁盘块大小为2KB，则需要25个连续的磁盘块。

连续磁盘空间分配方案有两个优势：

实现简单，记录每个文件用到的磁盘块简化为只需要记住两个数字就好：第一块的磁盘地址和文件的块数。
读操作性能较好，在单个操作中就可以从磁盘上读出整个文件，数据以磁盘全带宽速率输入，不需要寻道和旋转延迟。

同样不足也很明显：
随着时间的推移，磁盘变的零碎，因为当一些文件被删除时，会释放占用的块，即那些块成为空闲块，磁盘不会在这个位置挤压掉这个空洞，因为这样会导致该空洞后的所有文件的复制移动，开销较大。
或者维护一个空洞链表来记录这些空洞的位置与大小，每次将其分配给新建的文件使其被利用起来，但是这个方法同样存在问题。因为每次新建文件时并不知道这个文件将占用多大空间，它会根据用户需要动态增长或者减小，如果用这种方法进行分配空洞，也就意味着新建文件时需要提前知道其大小，显然不符合实际，就算知道了大小，在后期更改文件使其大于被分配的磁盘空间时也会引发问题。

链表分配

存储文件的第二种方法是为每个文件构造磁盘块链表，每个块的第一个字作为指向下一块的指针，块的其他部分存放数据。

这个方法可以充分利用磁盘碎片，避免了连续分配方案中产生的空洞而浪费空间。在目录项中，只需要存放第一块的磁盘地址，文件的其他块就可以从这个首块地址查找到。

类似数据结构中的顺序存储与随机存储，同样，顺序读文件非常方便，但是随机访问却相当缓慢，要获得块n，必须从头开始读前面的n－1块。而且由于指针占去了一个字节，使得每个磁盘块存储数据的字节数不再是2的整数次幂，这会导致降低系统运行效率，因为许多程序都是以长度为2的整数次幂来读写磁盘块的，由于每个块的前几个字节被指向下一个块的指针所占据，所以要读出一个完整的块大小的信息就需要从两个磁盘块中获得和拼接信息，这就因为复制引发了额外的开销。

采用内存中的表进行链表分配

如果取出每个磁盘块的指针部分，将其放在内存的一个表中，就可以解决链表分配的两个问题。该表即文件分配表（FAT）。

在上图中，文件A依次使用了磁盘块4 7 2 10 12，文件B依次使用了磁盘块6 3 11 14。从文件开始位置开始，顺着链走到最后就能找出文件所占用的所有磁盘块。

按照这种方法，整个块都可以存放数据并且随机访问也容易的多，虽然仍需要顺着链表在文件中查找给定的偏移量，但是整个链都存放在内存中，所以不需要任何磁盘引用。不管文件有多大，在目录项中只需记录一个整数（起始块号），按照它就可以找到文件的全部块。

这种方法的主要缺点是必须把整个表都存放到内存中，对于非常大的磁盘，显然需要非常多的表项。比如说1TB的磁盘，块大小为1KB，则需要10亿个表项。显然FAT的管理方式在大型磁盘计算机中并不实用。

i节点分配

可以给每个文件赋予一个称为i节点的数据结构来记录该文件分别包含哪些磁盘块。其中列出了文件属性和文件块的磁盘地址。

给定i节点就能找到文件的所有块，相对于FAT ，这种方法有很大的优势，即只有在对应的文件打开时，其i节点才在内存中，如果每个i节点占用n个字节，同时打开k个文件，则只占用nk个字节。

i节点的一个问题是：如果每个i节点只能存储固定数量的磁盘地址，那么当一个文件所含的磁盘块的数目超过了i节点所能容纳的数目怎么办？一个解决方案是最后一个磁盘地址不指向数据块，而是指向一个包含额外磁盘块地址的块的地址。更高级的解决方案是可以有两个或多个包含磁盘地址的块，或者指向其他存放地址的磁盘块的磁盘块。

参考资料：
《现代操作系统 3th》